mlsanityData to 14 Oct 2026

On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes

arXiv 1805.08114 ↗First posted 21 May 2018stat.ML cs.LG math.OCcited by 156

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient descent is the method of choice for large scale optimization of machine learning objective functions. Yet, its performance is greatly variable and heavily depends on the choice of the stepsizes. This has motivated a large body of research on adaptive stepsizes. However, there is currently a gap in our theoretical understanding of these methods, especially in the non-convex setting. In this paper, we start closing this gap: we theoretically analyze in the convex and non-convex settings a generalized version of the AdaGrad stepsizes. We show sufficient conditions for these stepsizes to achieve almost sure asymptotic convergence of the gradients to zero, proving the first guarantee for generalized AdaGrad stepsizes in the non-convex setting. Moreover, we show that these stepsizes allow to automatically adapt to the level of noise of the stochastic gradients in both the convex and non-convex settings, interpolating between O(1/T) and O(1/√T), up to logarithmic terms.

Key facts. Cited by 156 papers in the map (data through 14 Oct 2026). First posted on arXiv 21 May 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 33; 2022: 36; 2023: 28; 2024: 29; 2025: 15; 2026: 15.

156 papers.

Sort:

  1. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 427
  2. 2022Adaptive Gradient Methods at the Edge of Stabilitycited by 101
  3. 2022Robustness to Unbounded Smoothness of Generalized SignSGDcited by 81
  4. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  5. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 61
  6. 2023Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptionscited by 57
  7. 2023Toward Understanding Why Adam Converges Faster Than SGD for Transformerscited by 53
  8. 2021A Novel Convergence Analysis for Algorithms of the Adam Familycited by 50
  9. 2023High Probability Convergence of Stochastic Gradient Methodscited by 49
  10. 2022Understanding AdamW through Proximal Methods and Scale-Freenesscited by 46
  11. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 45
  12. 2023Optimal Linear Decay Learning Rate Schedules and Further Refinementscited by 43
38 more
  1. 2023Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGDcited by 41
  2. 2021SUPER-ADAM: Faster and Universal Framework of Adaptive Gradientscited by 40
  3. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  4. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 36
  5. 2022FedADMM: A Federated Primal-Dual Algorithm Allowing Partial Participationcited by 36
  6. 2023DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Methodcited by 35
  7. 2021BiAdam: Fast Adaptive Bilevel Optimization Methodscited by 33
  8. 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
  9. 2021Adaptivity without Compromise: A Momentumized, Adaptive, Dual Averaged Gradient Method for Stochastic Optimizationcited by 28
  10. 2021Parameter-free Stochastic Optimization of Variationally Coherent Functionscited by 27
  11. 2024Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguisecited by 26
  12. 2021Towards Practical Adam: Non-Convexity, Convergence Theory, and Mini-Batch Accelerationcited by 25
  13. 2021An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangianscited by 25
  14. 2021Toward Communication Efficient Adaptive Gradient Methodcited by 25
  15. 2022Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problemscited by 25
  16. 2022Improved Representation of Asymmetrical Distances with Interval Quasimetric Embeddingscited by 24
  17. 2023Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methodscited by 23
  18. 2023Efficient Federated Learning via Local Adaptive Amended Optimizer with Linear Speedupcited by 23
  19. 2025AdaGrad Meets Muon: Adaptive Stepsizes for Orthogonal Updatescited by 23
  20. 2021Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsizecited by 22
  21. 2024AdaGrad under Anisotropic Smoothnesscited by 22
  22. 2024Geometry of Polynomial Neural Networkscited by 21
  23. 2024On Convergence of Adam for Stochastic Optimization under Relaxed Assumptionscited by 21
  24. 2023Normalized Gradients for Allcited by 20
  25. 2024Online Cascade Learning for Efficient Inference over Streamscited by 20
  26. 2021On Expressivity and Trainability of Quadratic Networkscited by 19
  27. 2023Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradientcited by 19
  28. 2024Towards Quantifying the Preconditioning Effect of Adamcited by 19
  29. 2023A simple uniformly optimal method without line search for convex optimizationcited by 18
  30. 2024ADOPT: Modified Adam Can Converge with Any β2 with the Optimal Ratecited by 18
  31. 2021On the Convergence of Decentralized Adaptive Gradient Methodscited by 17
  32. 2021Global Convergence and Stability of Stochastic Gradient Descentcited by 17
  33. 2022A General Theory for Federated Optimization with Asynchronous and Heterogeneous Clients Updatescited by 17
  34. 2021Towards Noise-adaptive, Problem-adaptive (Accelerated) Stochastic Gradient Descentcited by 16
  35. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  36. 2024Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimizationcited by 16
  37. 2021AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methodscited by 15
  38. 2022Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimizationcited by 15

50 most cited of 156 All 156 (JSON)