# Linear Convergence of Adaptive Stochastic Gradient Descent

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Aug 2019.

## Built on by (most cited first, 29 of 29)

- [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)
- [ASGO: Adaptive Structured Gradient Optimization](https://mlsanity.com/paper/2503.20762/) (2025)
- [Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysis](https://mlsanity.com/paper/2105.01650/) (2021)
- [On the Convergence of Muon and Beyond](https://mlsanity.com/paper/2509.15816/) (2025)
- [Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapes](https://mlsanity.com/paper/2102.09385/) (2021)
- [Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction](https://mlsanity.com/paper/2308.06058/) (2023)
- [Optimal Algorithms for Stochastic Multi-Level Compositional Optimization](https://mlsanity.com/paper/2202.07530/) (2022)
- [Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization](https://mlsanity.com/paper/2206.00743/) (2022)
- [Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case](https://mlsanity.com/paper/2307.11782/) (2023)
- [Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization](https://mlsanity.com/paper/2111.06328/) (2021)
- [On the Convergence of AdaGrad(Norm) on Rd: Beyond Convexity, Non-Asymptotic Rate and Acceleration](https://mlsanity.com/paper/2209.14827/) (2022)
- [Adaptive Preconditioners Trigger Loss Spikes in Adam](https://mlsanity.com/paper/2506.04805/) (2025)
- [Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2305.19838/) (2023)
- [TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization](https://mlsanity.com/paper/2210.17478/) (2022)
- [Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGrad](https://mlsanity.com/paper/2403.02648/) (2024)
- [On Faster Convergence of Scaled Sign Gradient Descent](https://mlsanity.com/paper/2109.01806/) (2021)
- [Improved Policy Optimization for Online Imitation Learning](https://mlsanity.com/paper/2208.00088/) (2022)
- [Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion](https://mlsanity.com/paper/2208.11246/) (2022)
- [AdaLoss: A computationally-efficient and provably convergent adaptive gradient method](https://mlsanity.com/paper/2109.08282/) (2021)
- [Towards Understanding Adam Convergence on Highly Degenerate Polynomials](https://mlsanity.com/paper/2603.09581/) (2026)
- [The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithms](https://mlsanity.com/paper/2405.19585/) (2024)
- [Adaptivity via a Parallel Architecture for Stochastic Gradient Methods](https://mlsanity.com/paper/2607.28902/) (2026)
- [Painless step size adaptation for SGD](https://mlsanity.com/paper/2102.00853/) (2021)
- [Neurons learn slower than they think](https://mlsanity.com/paper/2104.02578/) (2021)
- [Local Quadratic Convergence of Stochastic Gradient Descent with Adaptive Step Size](https://mlsanity.com/paper/2112.14872/) (2021)
- [Beyond adaptive gradient: Fast-Controlled Minibatch Algorithm for large-scale optimization](https://mlsanity.com/paper/2411.15795/) (2024)
- [A regret minimization approach to fixed-point iterations](https://mlsanity.com/paper/2509.21653/) (2025)
- [Arithmetic Simplicity in Stochastic Gradient Methods](https://mlsanity.com/paper/2609.32240/) (2026)

## Abstract (arXiv)

We prove that the norm version of the adaptive stochastic gradient method (AdaGrad-Norm) achieves a linear convergence rate for a subset of either strongly convex functions or non-convex functions that satisfy the Polyak Lojasiewicz (PL) inequality. The paper introduces the notion of Restricted Uniform Inequality of Gradients (RUIG)---which is a measure of the balanced-ness of the stochastic gradient norms---to depict the landscape of a function. RUIG plays a key role in proving the robustness of AdaGrad-Norm to its hyper-parameter tuning in the stochastic setting. On top of RUIG, we develop a two-stage framework to prove the linear convergence of AdaGrad-Norm without knowing the parameters of the objective functions. This framework can likely be extended to other adaptive stepsize algorithms. The numerical experiments validate the theory and suggest future directions for improvement.