Publication Types:

Sort by year:

The Multiplicative Weights Update Method: A Meta-Algorithm and Applications

Sanjeev Arora, Elad Hazan and Satyen Kale
JournalIn Theory of Computing , 2012

Near-Optimal Algorithms for Online Matrix Prediction

Elad Hazan, Satyen Kale and Shai Shalev-Shwartz
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

Elad Hazan, Satyen Kale, and Manfred K. Warmuth
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 (NIPS), 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 (NIPS), 2009

Noise Tolerance of Expanders and Sublinear Expander Reconstruction

Satyen Kale, Yuval Peres and C. Seshadhri
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

Sanjeev Arora and Satyen Kale
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

Elad Hazan, Amit Agarwal and Satyen Kale
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

Abhiram Ranade, Srikanth S. M. and Satyen Kale
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

Sanjeev Arora, Elad Hazan and Satyen Kale
ConferenceJournalIn SIAM Journal on Computing (SICOMP), 2010. Also in proceedings of 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2004