mlsanityData to 7 Oct 2026

Revisiting Convergence of AdaGrad with Relaxed Assumptions

arXiv 2402.13794 ↗First posted 21 Feb 2024math.OC cs.LG stat.MLcited by 14

Not on the map. Why?

Abstract (arXiv)

In this study, we revisit the convergence of AdaGrad with momentum (covering AdaGrad as a special case) on non-convex smooth optimization problems. We consider a general noise model where the noise magnitude is controlled by the function value gap together with the gradient magnitude. This model encompasses a broad range of noises including bounded noise, sub-Gaussian noise, affine variance noise and the expected smoothness, and it has been shown to be more realistic in many practical applications. Our analysis yields a probabilistic convergence rate which, under the general noise, could reach at (tildeO(1/√T)). This rate does not rely on prior knowledge of problem-parameters and could accelerate to (tildeO(1/T)) where (T) denotes the total number iterations, when the noise parameters related to the function value gap and noise level are sufficiently small. The convergence rate thus matches the lower rate for stochastic first-order methods over non-convex smooth landscape up to logarithm terms [Arjevani et al., 2023]. We further derive a convergence bound for AdaGrad with mometum, considering the generalized smoothness where the local smoothness is controlled by a first-order function of the gradient norm.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Builds on 34 of its 45 references that are in the map. First posted on arXiv 21 Feb 2024.

Builds on

34 of 45 references.

References · 34

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2016An overview of gradient descent optimization algorithmscited by 1,021
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  4. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 335
  5. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  6. 2019SGD: General Analysis and Improved Ratescited by 206
  7. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  8. 2020A Simple Convergence Proof of Adam and Adagradcited by 169
  9. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  10. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 155
  11. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  12. 2018A Sufficient Condition for Convergences of Adam and RMSPropcited by 124
22 more
  1. 2018On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcited by 91
  2. 2020Improved Analysis of Clipping Algorithms for Non-convex Optimizationcited by 88
  3. 2022Robustness to Unbounded Smoothness of Generalized SignSGDcited by 80
  4. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  5. 2014Global convergence of the Heavy-ball method for convex optimizationcited by 60
  6. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 60
  7. 2023Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptionscited by 55
  8. 2018Online Adaptive Methods, Universality and Accelerationcited by 51
  9. 2023High Probability Convergence of Stochastic Gradient Methodscited by 48
  10. 2023Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGDcited by 41
  11. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  12. 2016Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimizationcited by 34
  13. 2018Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketchingcited by 34
  14. 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
  15. 2023Variance-reduced Clipping for Non-convex Optimizationcited by 22
  16. 2024On Convergence of Adam for Stochastic Optimization under Relaxed Assumptionscited by 21
  17. 2017Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuitycited by 18
  18. 2017Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theorycited by 16
  19. 2018A Unified Analysis of AdaGrad with Weighted Aggregation and Momentum Accelerationcited by 15
  20. 2022On the Convergence of AdaGrad(Norm) on Rd: Beyond Convexity, Non-Asymptotic Rate and Accelerationcited by 13
  21. 2021On the Convergence of Stochastic Gradient Descent with Bandwidth-based Step Sizecited by 9
  22. 2023High Probability Convergence of Adam Under Unbounded Gradients and Affine Variance Noisecited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 8; 2025: 2; 2026: 4.

14 papers.

Sort:

  1. 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
  2. 2024AdaGrad under Anisotropic Smoothnesscited by 22
  3. 2024Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimizationcited by 16
  4. 2024Non-convergence of Adam and other adaptive stochastic gradient descent optimization methods for non-vanishing learning ratescited by 14
  5. 2024Convergence rates for the Adam optimizercited by 14
  6. 2024Convergence Rate Analysis of LIONcited by 11
  7. 2025On the O(frac√dK1/4) Convergence Rate of AdamW Measured by ℓ1 Normcited by 8
  8. 2025Sharp higher order convergence rates for the Adam optimizercited by 7
  9. 2024Adaptive Gradient Normalization and Independent Sampling for (Stochastic) Generalized-Smooth Optimizationcited by 4
  10. 2026A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad and Muoncited by 2
  11. 2024Lean and Mean Adaptive Optimization via Subset-Norm and Subspace-Momentum with Convergence Guaranteescited by 1
  12. 2026Stochastic convergence of parallel asynchronous adaptive first-order methodscited by 0
2 more
  1. 2026Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothnesscited by 0
  2. 2026Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Boundscited by 0