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

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

## 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 (most cited first, 14 of 14)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization](https://mlsanity.com/paper/1808.02941/) (2018)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization](https://mlsanity.com/paper/1808.05671/) (2018)
- [A High Probability Analysis of Adaptive SGD with Momentum](https://mlsanity.com/paper/2007.14294/) (2020)
- [UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization](https://mlsanity.com/paper/1910.13857/) (2019)
- [Scale-Free Algorithms for Online Linear Optimization](https://mlsanity.com/paper/1502.05744/) (2015)
- [Asymptotic study of stochastic adaptive algorithm in non-convex landscape](https://mlsanity.com/paper/2012.05640/) (2020)
- [Domain-independent Dominance of Adaptive Methods](https://mlsanity.com/paper/1912.01823/) (2019)
- [On the Convergence of mSGD and AdaGrad for Stochastic Optimization](https://mlsanity.com/paper/2201.11204/) (2022)

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

- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions](https://mlsanity.com/paper/2305.18471/) (2023)
- [High Probability Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2302.14843/) (2023)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD](https://mlsanity.com/paper/2302.06570/) (2023)
- [Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity](https://mlsanity.com/paper/2310.17998/) (2023)
- [DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method](https://mlsanity.com/paper/2305.16284/) (2023)
- [Provable Adaptivity of Adam under Non-uniform Smoothness](https://mlsanity.com/paper/2208.09900/) (2022)
- [SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2302.08783/) (2023)
- [Parameter-Agnostic Optimization under Relaxed Smoothness](https://mlsanity.com/paper/2311.03252/) (2023)
- [Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods](https://mlsanity.com/paper/2305.12475/) (2023)
- [AdaGrad Meets Muon: Adaptive Stepsizes for Orthogonal Updates](https://mlsanity.com/paper/2509.02981/) (2025)
- [AdaGrad under Anisotropic Smoothness](https://mlsanity.com/paper/2406.15244/) (2024)
- [On Convergence of Adam for Stochastic Optimization under Relaxed Assumptions](https://mlsanity.com/paper/2402.03982/) (2024)
- [Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation](https://mlsanity.com/paper/2303.12277/) (2023)
- [Towards Quantifying the Preconditioning Effect of Adam](https://mlsanity.com/paper/2402.07114/) (2024)
- [Complexity of Single Loop Algorithms for Nonlinear Programming with Stochastic Objective and Constraints](https://mlsanity.com/paper/2311.00678/) (2023)
- [Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization](https://mlsanity.com/paper/2406.04592/) (2024)
- [Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization](https://mlsanity.com/paper/2211.01851/) (2022)
- [Revisiting Convergence of AdaGrad with Relaxed Assumptions](https://mlsanity.com/paper/2402.13794/) (2024)
- [On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyond](https://mlsanity.com/paper/2403.15146/) (2024)
- [Convergence Guarantees for RMSProp and Adam in Generalized-smooth Non-convex Optimization with Affine Noise Variance](https://mlsanity.com/paper/2404.01436/) (2024)
- [On the Convergence of AdaGrad(Norm) on Rd: Beyond Convexity, Non-Asymptotic Rate and Acceleration](https://mlsanity.com/paper/2209.14827/) (2022)
- [Tuning-Free Stochastic Optimization](https://mlsanity.com/paper/2402.07793/) (2024)
- [Efficient Sign-Based Optimization: Accelerating Convergence via Variance Reduction](https://mlsanity.com/paper/2406.00489/) (2024)
- [How Free is Parameter-Free Stochastic Optimization?](https://mlsanity.com/paper/2402.03126/) (2024)
- [An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes](https://mlsanity.com/paper/2407.04358/) (2024)
- [A Theoretical Analysis of Noise Geometry in Stochastic Gradient Descent](https://mlsanity.com/paper/2310.00692/) (2023)
- [High Probability Convergence of Adam Under Unbounded Gradients and Affine Variance Noise](https://mlsanity.com/paper/2311.02000/) (2023)

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