# Gradient Methods with Online Scaling

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 48 references that are in the map.
- First posted on arXiv 4 Nov 2024.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Meta-Learning in Neural Networks: A Survey](https://mlsanity.com/paper/2004.05439/) (2020)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [Learning to Optimize: A Primer and A Benchmark](https://mlsanity.com/paper/2103.12828/) (2021)
- [Learning to Optimize](https://mlsanity.com/paper/1606.01885/) (2016)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [The Road Less Scheduled](https://mlsanity.com/paper/2405.15682/) (2024)
- [Online Meta-Learning](https://mlsanity.com/paper/1902.08438/) (2019)
- [Adam-mini: Use Fewer Learning Rates To Gain More](https://mlsanity.com/paper/2406.16793/) (2024)
- [Preconditioned Stochastic Gradient Langevin Dynamics for Deep Neural Networks](https://mlsanity.com/paper/1512.07666/) (2015)
- [Online Learning Rate Adaptation with Hypergradient Descent](https://mlsanity.com/paper/1703.04782/) (2017)
- [Preconditioned Stochastic Gradient Descent](https://mlsanity.com/paper/1512.04202/) (2015)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient](https://mlsanity.com/paper/2106.04756/) (2021)
- [Towards Quantifying the Preconditioning Effect of Adam](https://mlsanity.com/paper/2402.07114/) (2024)
- [PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimates](https://mlsanity.com/paper/2309.02014/) (2023)
- [Fast and Near-Optimal Diagonal Preconditioning](https://mlsanity.com/paper/2008.01722/) (2020)
- [Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking](https://mlsanity.com/paper/2306.02527/) (2023)
- [Scalable Approximate Optimal Diagonal Preconditioning](https://mlsanity.com/paper/2312.15594/) (2023)
- [Dual Space Preconditioning for Gradient Descent](https://mlsanity.com/paper/1902.02257/) (2019)

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

- [Preconditioned Norms: A Unified Framework for Steepest Descent, Quasi-Newton and Adaptive Methods](https://mlsanity.com/paper/2510.10777/) (2025)
- [Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent](https://mlsanity.com/paper/2502.11229/) (2025)
- [Gradient Methods with Online Scaling Part I. Theoretical Foundations](https://mlsanity.com/paper/2505.23081/) (2025)
- [DynMuon: A Dynamic Spectral Shaping View of Muon](https://mlsanity.com/paper/2605.17109/) (2026)
- [Glocal Smoothness: Line search and adaptive step sizes can help in theory too!](https://mlsanity.com/paper/2506.12648/) (2025)
- [Online Learning-guided Learning Rate Adaptation via Gradient Alignment](https://mlsanity.com/paper/2506.08419/) (2025)
- [Gradient Methods with Online Scaling Part II. Practical Aspects](https://mlsanity.com/paper/2509.11007/) (2025)
- [OSDN: Improving Delta Rule with Provable Online Preconditioning in Linear Attention](https://mlsanity.com/paper/2605.13473/) (2026)
- [GradES: Significantly Faster Training in Transformers with Gradient-Based Early Stopping](https://mlsanity.com/paper/2509.01842/) (2025)
- [Optimal Diagonal Preconditioning Beyond Worst-Case Conditioning: Theory and Practice of Omega Scaling](https://mlsanity.com/paper/2509.23439/) (2025)
- [Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles](https://mlsanity.com/paper/2607.17607/) (2026)

## Abstract (arXiv)

We introduce a framework to accelerate the convergence of gradient-based methods with online learning. The framework learns to scale the gradient at each iteration through an online learning algorithm and provably accelerates gradient-based methods asymptotically. In contrast with previous literature, where convergence is established based on worst-case analysis, our framework provides a strong convergence guarantee with respect to the optimal scaling matrix for the iteration trajectory. For smooth strongly convex optimization, our results provide an O(kappa^star log(1/varepsilon)) complexity result, where kappa^star is the condition number achievable by the optimal preconditioner, improving on the previous O(√nkappa^star log(1/varepsilon)) result. In particular, a variant of our method achieves superlinear convergence on convex quadratics. For smooth convex optimization, we show for the first time that the widely-used hypergradient descent heuristic improves on the convergence of gradient descent.