# MetaGrad: Adaptation using Multiple Learning Rates in Online Learning

arXiv: https://arxiv.org/abs/2102.06622 · HTML: https://mlsanity.com/paper/2102.06622/

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 56 references that are in the map.
- First posted on arXiv 12 Feb 2021.

## Builds on (most cited first, 25 of 25)

- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Deep Learning in Neural Networks: An Overview](https://mlsanity.com/paper/1404.7828/) (2014)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [Lipschitz and Comparator-Norm Adaptivity in Online Learning](https://mlsanity.com/paper/2002.12242/) (2020)
- [Second-order Quantile Methods for Experts and Combinatorial Games](https://mlsanity.com/paper/1502.08009/) (2015)
- [Fast rates in statistical and online learning](https://mlsanity.com/paper/1507.02592/) (2015)
- [MetaGrad: Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1604.08740/) (2016)
- [Frequent Directions : Simple and Deterministic Matrix Sketching](https://mlsanity.com/paper/1501.01711/) (2015)
- [Lipschitz Adaptivity with Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1902.10797/) (2019)
- [Online Learning Without Prior Information](https://mlsanity.com/paper/1703.02629/) (2017)
- [Efficient Second Order Online Learning by Sketching](https://mlsanity.com/paper/1602.02202/) (2016)
- [The Many Faces of Exponential Weights in Online Learning](https://mlsanity.com/paper/1802.07543/) (2018)
- [On the optimality of the Hedge algorithm in the stochastic regime](https://mlsanity.com/paper/1809.01382/) (2018)
- [Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning](https://mlsanity.com/paper/1406.3816/) (2014)
- [A Generalized Online Mirror Descent with Applications to Classification and Regression](https://mlsanity.com/paper/1304.2994/) (2013)
- [Adaptive scale-invariant online algorithms for learning linear models](https://mlsanity.com/paper/1902.07528/) (2019)
- [Adaptivity and Optimality: A Universal Algorithm for Online Convex Optimization](https://mlsanity.com/paper/1905.05917/) (2019)
- [Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functions](https://mlsanity.com/paper/1906.10851/) (2019)
- [Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning](https://mlsanity.com/paper/1605.06439/) (2016)
- [Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities](https://mlsanity.com/paper/1702.03040/) (2017)
- [Efficient Full-Matrix Adaptive Regularization](https://mlsanity.com/paper/1806.02958/) (2018)
- [Artificial Constraints and Lipschitz Hints for Unconstrained Online Learning](https://mlsanity.com/paper/1902.09013/) (2019)

## Built on by (most cited first, 26 of 26)

- [Efficient Projection-Free Online Convex Optimization with Membership Oracle](https://mlsanity.com/paper/2111.05818/) (2021)
- [A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00557/) (2022)
- [Non-Stationary Learning of Neural Networks with Automatic Soft Parameter Reset](https://mlsanity.com/paper/2411.04034/) (2024)
- [Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees](https://mlsanity.com/paper/2305.11726/) (2023)
- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [Grad-GradaGrad? A Non-Monotone Adaptive Stochastic Gradient Method](https://mlsanity.com/paper/2206.06900/) (2022)
- [Adaptive Probabilistic Forecasting of Electricity (Net-)Load](https://mlsanity.com/paper/2301.10090/) (2023)
- [Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound](https://mlsanity.com/paper/2501.14349/) (2025)
- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [Accelerated Rates between Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2303.03272/) (2023)
- [Simple Projection-Free Algorithm for Contextual Recommendation with Logarithmic Regret and Robustness](https://mlsanity.com/paper/2603.20826/) (2026)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [Universal Online Convex Optimization Meets Second-order Bounds](https://mlsanity.com/paper/2105.03681/) (2021)
- [Exact Solution to Data-Driven Inverse Optimization of MILPs in Finite Time via Gradient-Based Methods](https://mlsanity.com/paper/2405.14273/) (2024)
- [Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting](https://mlsanity.com/paper/2305.12131/) (2023)
- [Local Risk Bounds for Statistical Aggregation](https://mlsanity.com/paper/2306.17151/) (2023)
- [Robust forecast aggregation via additional queries](https://mlsanity.com/paper/2512.05271/) (2025)
- [Explicit Iteration Complexity of Exact Data-Driven Inverse Optimization for Integer Linear Programs](https://mlsanity.com/paper/2607.22263/) (2026)
- [Prediction with Expert Advice: Anytime Regret with Many Experts Matches the Fixed-Time Constant](https://mlsanity.com/paper/2609.27206/) (2026)
- [Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets](https://mlsanity.com/paper/2402.12868/) (2024)
- [Tracking solutions of time-varying variational inequalities](https://mlsanity.com/paper/2406.14059/) (2024)
- [Non-stationary Bandit Convex Optimization: A Comprehensive Study](https://mlsanity.com/paper/2506.02980/) (2025)
- [Online Learning Approach for Survival Analysis](https://mlsanity.com/paper/2402.05145/) (2024)
- [Score-based change point detection via tracking the best of infinitely many experts](https://mlsanity.com/paper/2408.14073/) (2024)
- [Improved Impossible Tuning and Lipschitz-Adaptive Universal Online Learning with Gradient Variations](https://mlsanity.com/paper/2505.21095/) (2025)
- [Nonparametric Learning and Earning with One-Point Feedback under Nonstationarity](https://mlsanity.com/paper/2605.21263/) (2026)

## Abstract (arXiv)

We provide a new adaptive method for online convex optimization, MetaGrad, that is robust to general convex losses but achieves faster rates for a broad class of special functions, including exp-concave and strongly convex functions, but also various types of stochastic and non-stochastic functions without any curvature. We prove this by drawing a connection to the Bernstein condition, which is known to imply fast rates in offline statistical learning. MetaGrad further adapts automatically to the size of the gradients. Its main feature is that it simultaneously considers multiple learning rates, which are weighted directly proportional to their empirical performance on the data using a new meta-algorithm. We provide three versions of MetaGrad. The full matrix version maintains a full covariance matrix and is applicable to learning tasks for which we can afford update time quadratic in the dimension. The other two versions provide speed-ups for high-dimensional learning tasks with an update time that is linear in the dimension: one is based on sketching, the other on running a separate copy of the basic algorithm per coordinate. We evaluate all versions of MetaGrad on benchmark online classification and regression tasks, on which they consistently outperform both online gradient descent and AdaGrad.