Satyen Kale
Google Research
Journal
Publication Types:
Sort by year:
The Multiplicative Weights Update Method: A Meta-Algorithm and Applications
JournalIn Theory of Computing , 2012
Near-Optimal Algorithms for Online Matrix Prediction
ConferenceJournalIn SIAM Journal on Computing (SICOMP), 2017. Proceedings of 25th Conference on Learning Theory (COLT), 2012
Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization
ConferenceJournalIn Journal of Machine Learning Research (JMLR), 2014. Also in proceedings of 24th Conference on Learning Theory (COLT), 2011
Learning rotations with little regret
ConferenceJournalIn Machine Learning Journal (MLJ), (2016). Also in proceedings of 23rd Conference on Learning Theory (COLT), 2010. Corrigendum to conference version, 2010
Online Submodular Minimization
ConferenceJournalIn Journal of Machine Learning Research (JMLR), 2012. Also in proceedings of 23rd Annual Conference on Neural Information Processing Systems (NeurIPS), 2009
Better Algorithms for Benign Bandits
ConferenceJournalIn Journal of Machine Learning Research (JMLR), 2011. Also in proceedings of 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009
An online portfolio selection algorithm with regret logarithmic in price variation
ConferenceJournalIn Mathematical Finance, 2012. Originally appeared as "On Stochastic and Worst-case Models for Investing" in proceedings of 23rd Annual Conference on Neural Information Processing Systems (NeurIPS), 2009
Noise Tolerance of Expanders and Sublinear Expander Reconstruction
ConferenceJournalIn SIAM Journal on Computing (SICOMP), 2014. Also in proceedings of 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2008
Extracting Certainty from Uncertainty: Regret Bounded by Variation in Costs
ConferenceJournalIn Machine Learning Journal (MLJ), 2010. Also in proceedings of 21st Conference on Learning Theory (COLT), 2008
An Expansion Tester for Bounded Degree Graphs
ConferenceJournalTech ReportIn SIAM Journal on Computing (SICOMP), 2011. Also appeared as ECCC Report TR07-131 and in proceedings of 35th International Colloquium on Automata, Languages and Programming (ICALP), 2008
A Combinatorial, Primal-Dual approach to Semidefinite Programs
ConferenceJournalIn Journal of the ACM, 2016. Also in proceedings of 39th ACM Symposium on Theory of Computing (STOC), 2007
Logarithmic Regret Algorithms for Online Convex Optimization
ConferenceJournalIn Machine Learning Journal (MLJ), 2007. An earlier version with Adam Kalai appeared in proceedings of 19th Conference on Learning Theory (COLT), 2006
A Variation on SVD Based Image Compression
ConferenceJournalIn Image and Vision Computing, 2007. In proceedings of 3rd Workshop on Computer Vision, Graphics, and Image Processing (WCVGIP), 2006
\(O(\sqrt{\log n})\) approximation to SPARSEST CUT in \(\tilde{O}(n^2)\) time
ConferenceJournalIn SIAM Journal on Computing (SICOMP), 2010. Also in proceedings of 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2004