Library

On the Universality of Online Mirror Descent

We show that for a general class of convex online learning problems, Mirror Descent can always achieve a (nearly) optimal regret guarantee.

cs.LGComputer ScienceMathematics
Source

Paper

References (29)

01Stochastic Approximation approach to Stochastic ProgrammingA. Juditsky, Guanghui Lan, A. Nemirovski et al.2013 · 1.7k citations
02Stochastic Optimization for Machine LearningAndrew Cotter2013 · 26 citations In Library
03A Dirty Model for Multi-task LearningA. Jalali, Pradeep Ravikumar, S. Sanghavi et al.2010 · Neural Information Processing Systems · 410 citations
04Online Learning: Random Averages, Combinatorial Parameters, and LearnabilityA. Rakhlin, Karthik Sridharan, Ambuj Tewari2010 · Neural Information Processing Systems · 145 citations
05Information-theoretic lower bounds on the oracle complexity of convex optimizationAlekh Agarwal, P. Bartlett, Pradeep Ravikumar et al.2009 · Neural Information Processing Systems · 226 citations
06Applications of strong convexity--strong smoothness duality to learning with matricesS. Kakade, S. Shalev-Shwartz, Ambuj Tewari2009 · arXiv.org · 56 citations
07Sparse and low-rank matrix decompositionsV. Chandrasekaran, S. Sanghavi, P. Parrilo et al.2009 · Allerton Conference on Communication, Control, and Computing · 174 citations
08Efficient projections onto the l1-ball for learning in high dimensionsJohn C. Duchi, S. Shalev-Shwartz, Y. Singer et al.2008 · International Conference on Machine Learning · 1.6k citations
09Sparse Online Learning via Truncated GradientJohn Langford, Lihong Li, Tong Zhang2008 · Neural Information Processing Systems · 502 citations In Library
10Optimal Stragies and Minimax Lower Bounds for Online Convex GamesJacob D. Abernethy, P. Bartlett, A. Rakhlin et al.2008 · Annual Conference Computational Learning Theory · 194 citations
11Convex Repeated Games and Fenchel DualityS. Shalev-Shwartz, Y. Singer2006 · Neural Information Processing Systems · 136 citations
12Addendum: Regularization and variable selection via the elastic netH. Zou, T. Hastie2005 · 11k citations

Scroll for more · 17 remaining

Similar papers

Non-convex online learning via algorithmic equivalenceUdaya Ghai, Zhou Lu, Elad Hazan2022 · Neural Information Processing Systems · 15 citations In Library
Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit FeedbackAnas Barakat, A. Kontogiannis, Vasilis Pollatos et al.2026 · 0 citations In Library
Improving Dynamic Regret in Distributed Online Mirror Descent Using Primal and Dual InformationNima Eshraghi, Ben Liang2021 · arXiv (Cornell University) In Library
Mirror Descent Meets Fixed Share (and feels no regret)N. Cesa-Bianchi, Pierre Gaillard, G. Lugosi et al.2012 · Neural Information Processing Systems · 106 citations In Library
Temporal Variability in Implicit Online LearningNicolò Campolongo, Francesco Orabona2020 · Neural Information Processing Systems · 29 citations In Library
Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise VarianceN. Mert Vural, Yu Lu, Krishnakumar Balasubramanian et al.2022 · arXiv (Cornell University) In Library
Online mirror descent and dual averaging: keeping pace in the dynamic caseHuang Fang, Nicholas J. A. Harvey, V. S. Portella et al.2020 · International Conference on Machine Learning · 40 citations In Library
Online Learning with Local Permutations and Delayed FeedbackOhad Shamir, Liran Szlak2017 · International Conference on Machine Learning · 18 citations In Library
Joint Online Learning and Decision-making via Dual Mirror DescentAlfonso Lobos, Paul Grigas, Zheng Wen2021 · International Conference on Machine Learning · 12 citations In Library
Connections Between Mirror Descent, Thompson Sampling and the Information RatioJulian Zimmert, Tor Lattimore2019 · Neural Information Processing Systems · 37 citations In Library
© 2026 NYSGPT2525 LLC