mlsanityData to 7 Oct 2026

Step-Size Stability in Stochastic Optimization: A Theoretical Perspective

arXiv 2602.09842 ↗First posted 10 Feb 2026math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

We present a theoretical analysis of stochastic optimization methods in terms of their sensitivity with respect to the step size. We identify a key quantity that, for each method, describes how the performance degrades as the step size becomes too large. For convex problems, we show that this quantity directly impacts the suboptimality bound of the method. Most importantly, our analysis provides direct theoretical evidence that adaptive step-size methods, such as SPS or NGN, are more robust than SGD. This allows us to quantify the advantage of these adaptive methods beyond empirical evaluation. Finally, we show through experiments that our theoretical bound qualitatively mirrors the actual performance as a function of the step size, even for non-convex problems.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 30 of its 49 references that are in the map. First posted on arXiv 10 Feb 2026.

Builds on

30 of 49 references.

References · 30

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 20242 OLMo 2 Furiouscited by 302
  3. 2023Small-scale proxies for large-scale Transformer training instabilitiescited by 182
  4. 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 158
  5. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  6. 2020Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergencecited by 137
  7. 2016Coin Betting and Parameter-Free Online Learningcited by 131
  8. 2023Prodigy: An Expeditiously Adaptive Parameter-Free Learnercited by 129
  9. 2023Learning-Rate-Free Learning by D-Adaptationcited by 113
  10. 2023DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedulecited by 85
  11. 2019Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learningcited by 71
  12. 2024Scaling Exponents Across Parameterizations and Optimizerscited by 71
18 more
  1. 2018Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivitycited by 61
  2. 2022Making SGD Parameter-Freecited by 50
  3. 2019Training Neural Networks for and by Interpolationcited by 45
  4. 2023Optimal Linear Decay Learning Rate Schedules and Further Refinementscited by 41
  5. 2015Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methodscited by 36
  6. 2019The importance of better models in stochastic optimizationcited by 32
  7. 2025The Surprising Agreement Between Convex Optimization Theory and Learning-Rate Scheduling for Large Model Trainingcited by 31
  8. 2025An Exploration of Non-Euclidean Gradient Descent: Muon and its Many Variantscited by 25
  9. 2023MoMo: Momentum Models for Adaptive Learning Ratescited by 24
  10. 2022Cutting Some Slack for SGD with Adaptive Polyak Stepsizescited by 18
  11. 2023A Stochastic Proximal Polyak Step Sizecited by 15
  12. 2022PEPit: computer-assisted worst-case analyses of first-order optimization methods in Pythoncited by 10
  13. 2024An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizescited by 10
  14. 2025New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Resultscited by 6
  15. 2022A Semismooth Newton Stochastic Proximal Point Algorithm with Variance Reductioncited by 5
  16. 2025Revisiting Stochastic Proximal Point Methods: Generalized Smoothness and Similaritycited by 5
  17. 2025How far away are truly hyperparameter-free learning algorithms?cited by 2
  18. 2025Enhancing Optimizer Stability: Momentum Adaptation of The NGN Step-sizecited by 1

Built on by

Not cited yet.