mlsanityData to 7 Oct 2026

Linear Convergence of Adaptive Stochastic Gradient Descent

arXiv 1908.10525 ↗First posted 28 Aug 2019stat.ML cs.LG math.OCcited by 29

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 7; 2023: 3; 2024: 3; 2025: 4; 2026: 3.

29 papers.

Sort:

By area:

  1. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 413
  2. 2022Adaptive Gradient Methods at the Edge of Stabilitycited by 88
  3. 2025ASGO: Adaptive Structured Gradient Optimizationcited by 55
  4. 2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 38
  5. 2025On the Convergence of Muon and Beyondcited by 28
  6. 2021Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapescited by 27
  7. 2023Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reductioncited by 23
  8. 2022Optimal Algorithms for Stochastic Multi-Level Compositional Optimizationcited by 17
  9. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  10. 2022On the Convergence of AdaGrad(Norm) on Rd: Beyond Convexity, Non-Asymptotic Rate and Accelerationcited by 13
  11. 2023Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Casecited by 13
  12. 2021Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterizationcited by 10
17 more
  1. 2025Adaptive Preconditioners Trigger Loss Spikes in Adamcited by 10
  2. 2023Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimizationcited by 8
  3. 2024Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGradcited by 8
  4. 2022TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimizationcited by 7
  5. 2021On Faster Convergence of Scaled Sign Gradient Descentcited by 6
  6. 2022Improved Policy Optimization for Online Imitation Learningcited by 6
  7. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6
  8. 2021AdaLoss: A computationally-efficient and provably convergent adaptive gradient methodcited by 3
  9. 2024The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithmscited by 3
  10. 2026Towards Understanding Adam Convergence on Highly Degenerate Polynomialscited by 3
  11. 2026Adaptivity via a Parallel Architecture for Stochastic Gradient Methodscited by 1
  12. 2021Painless step size adaptation for SGDcited by 0
  13. 2021Neurons learn slower than they thinkcited by 0
  14. 2021Local Quadratic Convergence of Stochastic Gradient Descent with Adaptive Step Sizecited by 0
  15. 2024Beyond adaptive gradient: Fast-Controlled Minibatch Algorithm for large-scale optimizationcited by 0
  16. 2025A regret minimization approach to fixed-point iterationscited by 0
  17. 2026Arithmetic Simplicity in Stochastic Gradient Methodscited by 0