mlsanityData to 14 Oct 2026

Gradient Methods with Online Scaling Part I. Theoretical Foundations

arXiv 2505.23081 ↗First posted 29 May 2025math.OC cs.LG stat.MLcited by 3

Not on the map. Why?

Abstract (arXiv)

This paper establishes the theoretical foundations of the online scaled gradient methods (OSGM), a framework that utilizes online learning to adapt stepsizes and provably accelerate first-order methods. OSGM quantifies the effectiveness of a stepsize by a feedback function motivated from a convergence measure and uses the feedback to adjust the stepsize through an online learning algorithm. Consequently, instantiations of OSGM achieve convergence rates that are asymptotically no worse than the optimal stepsize. OSGM yields desirable convergence guarantees on smooth convex problems, including 1) trajectory-dependent global convergence on smooth convex objectives; 2) an improved complexity result on smooth strongly convex problems, and 3) local superlinear convergence. Notably, OSGM constitutes a new family of first-order methods with non-asymptotic superlinear convergence, joining the celebrated quasi-Newton methods. Finally, OSGM explains the empirical success of the popular hypergradient-descent heuristic in optimization for machine learning.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 43 of its 70 references that are in the map. First posted on arXiv 29 May 2025.

Builds on

43 of 70 references.

References · 43

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2019On the Convergence of Adam and Beyondcited by 841
  3. 2019Introduction to Online Convex Optimizationcited by 803
  4. 2018Shampoo: Preconditioned Stochastic Tensor Optimizationcited by 426
  5. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  6. 2020AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradientscited by 283
  7. 2024Adam-mini: Use Fewer Learning Rates To Gain Morecited by 137
  8. 2016Coin Betting and Parameter-Free Online Learningcited by 133
  9. 2017Online Learning Rate Adaptation with Hypergradient Descentcited by 118
  10. 2019Adaptive Gradient Descent without Descentcited by 79
  11. 2019Revisiting the Polyak step sizecited by 55
  12. 2024Clarabel: An interior-point solver for conic programs with quadratic objectivescited by 44
31 more
  1. 2020Disentangling Adaptive Gradient Methods from Learning Ratescited by 42
  2. 2021Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradientcited by 32
  3. 2020A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performancecited by 26
  4. 2023Unconstrained Online Learning with Unbounded Lossescited by 25
  5. 2020Greedy Quasi-Newton Methods with Explicit Superlinear Convergencecited by 21
  6. 2023Adaptive Proximal Gradient Method for Convex Optimizationcited by 21
  7. 2021No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimizationcited by 20
  8. 2023Acceleration by Stepsize Hedging II: Silver Stepsize Schedule for Smooth Convex Optimizationcited by 20
  9. 2023Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedulecited by 19
  10. 2023A simple uniformly optimal method without line search for convex optimizationcited by 18
  11. 2020Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methodscited by 16
  12. 2020New Results on Superlinear Convergence of Classical Quasi-Newton Methodscited by 15
  13. 2020Rates of superlinear convergence for classical quasi-Newton methodscited by 13
  14. 2023Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergencecited by 11
  15. 2024Gradient Methods with Online Scalingcited by 11
  16. 2018An ADMM-Based Interior-Point Method for Large-Scale Linear Programmingcited by 10
  17. 2021On the Convergence of Stochastic Gradient Descent with Bandwidth-based Step Sizecited by 9
  18. 2023Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtrackingcited by 9
  19. 2023Scalable Approximate Optimal Diagonal Preconditioningcited by 9
  20. 2018Non-monotone Behavior of the Heavy Ball Methodcited by 8
  21. 2023cuPDLP-C: A Strengthened Implementation of cuPDLP for Linear Programming by C languagecited by 7
  22. 2024MADA: Meta-Adaptive Optimizers through hyper-gradient Descentcited by 6
  23. 2025Provable and Practical Online Learning Rate Adaptation with Hypergradient Descentcited by 5
  24. 2024Non-asymptotic Global Convergence Analysis of BFGS with the Armijo-Wolfe Line Searchcited by 4
  25. 2024Uniformly Optimal and Parameter-free First-order Methods for Convex and Function-constrained Optimizationcited by 4
  26. 2019Surrogate Losses for Online Learning of Stepsizes in Stochastic Non-Convex Optimizationcited by 3
  27. 2024Non-asymptotic Global Convergence Rates of BFGS with Exact Line Searchcited by 3
  28. 2024Restarted Primal-Dual Hybrid Conjugate Gradient Method for Large-Scale Quadratic Programmingcited by 3
  29. 2024Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergencecited by 3
  30. 2025A Practical GPU-Enhanced Matrix-Free Primal-Dual Method for Large-Scale Conic Programscited by 3
  31. 2024The Role of Level-Set Geometry on the Performance of PDHG for Conic Linear Optimizationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 1.

3 papers.

  1. 2025Learning to accelerate distributed ADMM using graph neural networkscited by 3
  2. 2025Gradient Methods with Online Scaling Part II. Practical Aspectscited by 1
  3. 2026Tight Nonasymptotic Local Convergence of Sinkhorn-Knoppcited by 0