mlsanityData to 7 Oct 2026

Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods

arXiv 2305.12475 ↗First posted 21 May 2023math.OC cs.LG stat.MLcited by 23

Not on the map. Why?

Abstract (arXiv)

The classical analysis of Stochastic Gradient Descent (SGD) with polynomially decaying stepsize ηt = η/√t relies on well-tuned η depending on problem parameters such as Lipschitz smoothness constant, which is often unknown in practice. In this work, we prove that SGD with arbitrary η > 0, referred to as untuned SGD, still attains an order-optimal convergence rate widetildeO(T-1/4) in terms of gradient norm for minimizing smooth objectives. Unfortunately, it comes at the expense of a catastrophic exponential dependence on the smoothness constant, which we show is unavoidable for this scheme even in the noiseless setting. We then examine three families of adaptive methods unicodex2013 Normalized SGD (NSGD), AMSGrad, and AdaGrad unicodex2013 unveiling their power in preventing such exponential dependency in the absence of information about the smoothness parameter and boundedness of stochastic gradients. Our results provide theoretical justification for the advantage of adaptive methods over untuned SGD in alleviating the issue with large gradients.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). Builds on 47 of its 80 references that are in the map. First posted on arXiv 21 May 2023.

Builds on

47 of 80 references.

References · 47

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  3. 2020Language Models are Few-Shot Learnerscited by 32,199
  4. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  5. 2019On the Convergence of Adam and Beyondcited by 834
  6. 2014Deep Learning in Neural Networks: An Overviewcited by 765
  7. 2019On the Variance of the Adaptive Learning Rate and Beyondcited by 763
  8. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  9. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 335
  10. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
  11. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  12. 2020Understanding the Difficulty of Training Transformerscited by 210
35 more
  1. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  2. 2019Adaptive Gradient Methods with Dynamic Bound of Learning Ratecited by 181
  3. 2018On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimizationcited by 173
  4. 2022Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Modelscited by 172
  5. 2020A Simple Convergence Proof of Adam and Adagradcited by 169
  6. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  7. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 155
  8. 2017Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradientscited by 136
  9. 2020Momentum Improves Normalized SGDcited by 136
  10. 2017Lower Bounds for Finding Stationary Points Icited by 125
  11. 2020Towards Theoretically Understanding Why SGD Generalizes Better Than ADAM in Deep Learningcited by 125
  12. 2018A Sufficient Condition for Convergences of Adam and RMSPropcited by 124
  13. 2022Adam Can Converge Without Any Modification On Update Rulescited by 112
  14. 2018On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcited by 91
  15. 2022Understanding the unstable convergence of gradient descentcited by 84
  16. 2020On the Convergence of SGD with Biased Gradientscited by 79
  17. 2015Beyond Convexity: Stochastic Quasi-Convex Optimizationcited by 75
  18. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  19. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 60
  20. 2019UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimizationcited by 56
  21. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  22. 2021A Novel Convergence Analysis for Algorithms of the Adam Familycited by 50
  23. 2019Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptionscited by 48
  24. 2020The Implicit Bias for Adaptive Optimization Algorithms on Homogeneous Neural Networkscited by 43
  25. 2020Adaptive Inertia: Disentangling the Effects of Adaptive Learning Rate and Momentumcited by 40
  26. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  27. 2019The Complexity of Finding Stationary Points with Stochastic Gradient Descentcited by 34
  28. 2022Provable Adaptivity of Adam under Non-uniform Smoothnesscited by 30
  29. 2016The Power of Normalization: Faster Evasion of Saddle Pointscited by 29
  30. 2017Revisiting Normalized Gradient Descent: Fast Evasion of Saddle Pointscited by 28
  31. 2021On the Convergence of Step Decay Step-Size for Stochastic Optimizationcited by 21
  32. 2022VectorAdam for Rotation Equivariant Geometry Optimizationcited by 17
  33. 2021Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descentcited by 16
  34. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  35. 2022Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimizationcited by 15

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 8; 2025: 6; 2026: 5.

23 papers.

Sort:

  1. 2023Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptionscited by 55
  2. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 48
  3. 2023Momentum Provably Improves Error Feedback!cited by 31
  4. 2023Parameter-Agnostic Optimization under Relaxed Smoothnesscited by 29
  5. 2025On the Convergence of Muon and Beyondcited by 28
  6. 2025Beyond the Ideal: Analyzing the Inexact Muon Updatecited by 23
  7. 2023Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraintscited by 16
  8. 2025Can SGD Handle Heavy-Tailed Noise?cited by 15
  9. 2024On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyondcited by 13
  10. 2025Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothnesscited by 12
  11. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  12. 2024An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizescited by 10
11 more
  1. 2024Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptionscited by 5
  2. 2024The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithmscited by 3
  3. 2025Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limitscited by 3
  4. 2026Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGradcited by 3
  5. 2026Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noisecited by 2
  6. 2024Towards Stability of Parameter-Free Optimizationcited by 1
  7. 2024Beyond adaptive gradient: Fast-Controlled Minibatch Algorithm for large-scale optimizationcited by 0
  8. 2025On the Performance of Differentially Private Optimization with Heavy-Tail Class Imbalancecited by 0
  9. 2026Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationaritycited by 0
  10. 2026TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noisecited by 0
  11. 2026Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Boundscited by 0