# On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes

arXiv: https://arxiv.org/abs/1805.08114 · HTML: https://mlsanity.com/paper/1805.08114/

## Key facts

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

## Built on by (most cited first, 30 of 156)

- [Gradient Descent on Neural Networks Typically Occurs at the Edge of Stability](https://mlsanity.com/paper/2103.00065/) (2021)
- [Adaptive Gradient Methods at the Edge of Stability](https://mlsanity.com/paper/2207.14484/) (2022)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2202.05791/) (2022)
- [Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions](https://mlsanity.com/paper/2305.18471/) (2023)
- [Toward Understanding Why Adam Converges Faster Than SGD for Transformers](https://mlsanity.com/paper/2306.00204/) (2023)
- [A Novel Convergence Analysis for Algorithms of the Adam Family](https://mlsanity.com/paper/2112.03459/) (2021)
- [High Probability Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2302.14843/) (2023)
- [Understanding AdamW through Proximal Methods and Scale-Freeness](https://mlsanity.com/paper/2202.00089/) (2022)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Optimal Linear Decay Learning Rate Schedules and Further Refinements](https://mlsanity.com/paper/2310.07831/) (2023)
- [Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD](https://mlsanity.com/paper/2302.06570/) (2023)
- [SUPER-ADAM: Faster and Universal Framework of Adaptive Gradients](https://mlsanity.com/paper/2106.08208/) (2021)
- [High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize](https://mlsanity.com/paper/2204.02833/) (2022)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [FedADMM: A Federated Primal-Dual Algorithm Allowing Partial Participation](https://mlsanity.com/paper/2203.15104/) (2022)
- [DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method](https://mlsanity.com/paper/2305.16284/) (2023)
- [BiAdam: Fast Adaptive Bilevel Optimization Methods](https://mlsanity.com/paper/2106.11396/) (2021)
- [SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2302.08783/) (2023)
- [Adaptivity without Compromise: A Momentumized, Adaptive, Dual Averaged Gradient Method for Stochastic Optimization](https://mlsanity.com/paper/2101.11075/) (2021)
- [Parameter-free Stochastic Optimization of Variationally Coherent Functions](https://mlsanity.com/paper/2102.00236/) (2021)
- [Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguise](https://mlsanity.com/paper/2402.01567/) (2024)
- [Towards Practical Adam: Non-Convexity, Convergence Theory, and Mini-Batch Acceleration](https://mlsanity.com/paper/2101.05471/) (2021)
- [An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangians](https://mlsanity.com/paper/2102.05320/) (2021)
- [Toward Communication Efficient Adaptive Gradient Method](https://mlsanity.com/paper/2109.05109/) (2021)
- [Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems](https://mlsanity.com/paper/2206.07082/) (2022)
- [Improved Representation of Asymmetrical Distances with Interval Quasimetric Embeddings](https://mlsanity.com/paper/2211.15120/) (2022)
- [Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods](https://mlsanity.com/paper/2305.12475/) (2023)
- [Efficient Federated Learning via Local Adaptive Amended Optimizer with Linear Speedup](https://mlsanity.com/paper/2308.00522/) (2023)

## 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.