mlsanityData to 14 Oct 2026

The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance

arXiv 2202.05791 ↗First posted 11 Feb 2022stat.ML cs.LG math.OCcited by 61

Not on the map. Why?

Abstract (arXiv)

We study convergence rates of AdaGrad-Norm as an exemplar of adaptive stochastic gradient methods (SGD), where the step sizes change based on observed stochastic gradients, for minimizing non-convex, smooth objectives. Despite their popularity, the analysis of adaptive SGD lags behind that of non adaptive methods in this setting. Specifically, all prior works rely on some subset of the following assumptions: (i) uniformly-bounded gradient norms, (ii) uniformly-bounded stochastic gradient variance (or even noise support), (iii) conditional independence between the step size and stochastic gradient. In this work, we show that AdaGrad-Norm exhibits an order optimal convergence rate of Oleft(fracpolylog(T)√Tright) after T iterations under the same assumptions as optimally-tuned non adaptive SGD (unbounded gradient norms and affine noise variance scaling), and crucially, without needing any tuning parameters. We thus establish that adaptive gradient methods exhibit order-optimal convergence in much broader regimes than previously understood.

Key facts. Cited by 61 papers in the map (data through 14 Oct 2026). Builds on 14 of its 28 references that are in the map. First posted on arXiv 11 Feb 2022.

Builds on

14 of 28 references.

References · 14

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  4. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  5. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  6. 2018On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimizationcited by 174
  7. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 156
  8. 2018On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcited by 91
  9. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  10. 2019UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimizationcited by 56
  11. 2015Scale-Free Algorithms for Online Linear Optimizationcited by 30
  12. 2020Asymptotic study of stochastic adaptive algorithm in non-convex landscapecited by 16
2 more
  1. 2019Domain-independent Dominance of Adaptive Methodscited by 13
  2. 2022On the Convergence of mSGD and AdaGrad for Stochastic Optimizationcited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 15; 2024: 23; 2025: 11; 2026: 9.

61 papers.

Sort:

  1. 2023Convergence of Adam Under Relaxed Assumptionscited by 99
  2. 2023DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedulecited by 85
  3. 2023Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptionscited by 57
  4. 2023High Probability Convergence of Stochastic Gradient Methodscited by 49
  5. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 45
  6. 2023Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGDcited by 41
  7. 2023Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexitycited by 38
  8. 2023DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Methodcited by 35
  9. 2022Provable Adaptivity of Adam under Non-uniform Smoothnesscited by 30
  10. 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
  11. 2023Parameter-Agnostic Optimization under Relaxed Smoothnesscited by 29
  12. 2023Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methodscited by 23
38 more
  1. 2025AdaGrad Meets Muon: Adaptive Stepsizes for Orthogonal Updatescited by 23
  2. 2024AdaGrad under Anisotropic Smoothnesscited by 22
  3. 2024On Convergence of Adam for Stochastic Optimization under Relaxed Assumptionscited by 21
  4. 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
  5. 2024Towards Quantifying the Preconditioning Effect of Adamcited by 19
  6. 2023Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraintscited by 16
  7. 2024Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimizationcited by 16
  8. 2022Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimizationcited by 15
  9. 2024Revisiting Convergence of AdaGrad with Relaxed Assumptionscited by 15
  10. 2024On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyondcited by 14
  11. 2024Convergence Guarantees for RMSProp and Adam in Generalized-smooth Non-convex Optimization with Affine Noise Variancecited by 14
  12. 2022On the Convergence of AdaGrad(Norm) on Rd: Beyond Convexity, Non-Asymptotic Rate and Accelerationcited by 13
  13. 2024Tuning-Free Stochastic Optimizationcited by 13
  14. 2024Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reductioncited by 13
  15. 2024How Free is Parameter-Free Stochastic Optimization?cited by 12
  16. 2024An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizescited by 10
  17. 2023A Theoretical Analysis of Noise Geometry in Stochastic Gradient Descentcited by 9
  18. 2023High Probability Convergence of Adam Under Unbounded Gradients and Affine Variance Noisecited by 8
  19. 2024AdAdaGrad: Adaptive Batch Size Schemes for Adaptive Gradient Methodscited by 8
  20. 2024Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGradcited by 8
  21. 2025On the O(frac√dK1/4) Convergence Rate of AdamW Measured by ℓ1 Normcited by 8
  22. 2025Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Ratescited by 8
  23. 2024Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workerscited by 5
  24. 2024Preconditioning for Accelerated Gradient Descent Optimization and Regularizationcited by 4
  25. 2025Simple Convergence Proof of Adam From a Sign-like Descent Perspectivecited by 4
  26. 2024Reevaluating Theoretical Analysis Methods for Optimization in Deep Learningcited by 3
  27. 2026Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGradcited by 3
  28. 2024Parallel Momentum Methods Under Biased Gradient Estimationscited by 2
  29. 2024Lean and Mean Adaptive Optimization via Subset-Norm and Subspace-Momentum with Convergence Guaranteescited by 2
  30. 2025Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimizationcited by 2
  31. 2025Design Criteria for SGD Preconditioners: Local Conditioning, Noise Floors, and Basin Stabilitycited by 2
  32. 2026A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad and Muoncited by 2
  33. 2024A General Reduction for High-Probability Analysis with General Light-Tailed Distributionscited by 1
  34. 2024Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batchingcited by 1
  35. 2024Analysis of regularized federated learningcited by 1
  36. 2025Online Learning-guided Learning Rate Adaptation via Gradient Alignmentcited by 1
  37. 2026AdaGrad-Diff: A New Version of the Adaptive Gradient Algorithmcited by 1
  38. 2026Unified convergence analysis for gradient descent optimization methods in the training of deep neural networkscited by 1

50 most cited of 61 All 61 (JSON)