mlsanityData to 7 Oct 2026

SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance

arXiv 2302.08783 ↗First posted 17 Feb 2023cs.LG math.OC stat.MLcited by 30

Not on the map. Why?

Abstract (arXiv)

We study Stochastic Gradient Descent with AdaGrad stepsizes: a popular adaptive (self-tuning) method for first-order stochastic optimization. Despite being well studied, existing analyses of this method suffer from various shortcomings: they either assume some knowledge of the problem parameters, impose strong global Lipschitz conditions, or fail to give bounds that hold with high probability. We provide a comprehensive analysis of this basic method without any of these limitations, in both the convex and non-convex (smooth) cases, that additionally supports a general ``affine variance'' noise model and provides sharp rates of convergence in both the low-noise and high-noise~regimes.

Key facts. Cited by 30 papers in the map (data through 7 Oct 2026). Builds on 21 of its 29 references that are in the map. First posted on arXiv 17 Feb 2023.

Builds on

21 of 29 references.

References · 21

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  3. 2019On the Convergence of Adam and Beyondcited by 834
  4. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  5. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  6. 2018Time-uniform, nonparametric, nonasymptotic confidence sequencescited by 220
  7. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  8. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 155
  9. 2016Coin Betting and Parameter-Free Online Learningcited by 131
  10. 2018Black-Box Reductions for Parameter-free Online Learning in Banach Spacescited by 124
  11. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
  12. 2018On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcited by 91
9 more
  1. 2016Scale-Free Online Learningcited by 83
  2. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  3. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  4. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 60
  5. 2020Lipschitz and Comparator-Norm Adaptivity in Online Learningcited by 57
  6. 2022Making SGD Parameter-Freecited by 50
  7. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  8. 2020A new regret analysis for Adam-type algorithmscited by 35
  9. 2019On the Convergence Proof of AMSGrad and a New Versioncited by 21

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 14; 2025: 7; 2026: 7.

30 papers.

Sort:

  1. 2024AdaGrad under Anisotropic Smoothnesscited by 22
  2. 2024On Convergence of Adam for Stochastic Optimization under Relaxed Assumptionscited by 21
  3. 2024Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimizationcited by 16
  4. 2024Revisiting Convergence of AdaGrad with Relaxed Assumptionscited by 14
  5. 2024Tuning-Free Stochastic Optimizationcited by 13
  6. 2024How Free is Parameter-Free Stochastic Optimization?cited by 12
  7. 2023High Probability Convergence of Adam Under Unbounded Gradients and Affine Variance Noisecited by 8
  8. 2024AdAdaGrad: Adaptive Batch Size Schemes for Adaptive Gradient Methodscited by 8
  9. 2025On the O(frac√dK1/4) Convergence Rate of AdamW Measured by ℓ1 Normcited by 8
  10. 2025Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Ratescited by 8
  11. 2024Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workerscited by 5
  12. 2024Preconditioning for Accelerated Gradient Descent Optimization and Regularizationcited by 4
18 more
  1. 2025Simple Convergence Proof of Adam From a Sign-like Descent Perspectivecited by 4
  2. 2024The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithmscited by 3
  3. 2026Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGradcited by 3
  4. 2025Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimizationcited by 2
  5. 2026A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad and Muoncited by 2
  6. 2024A General Reduction for High-Probability Analysis with General Light-Tailed Distributionscited by 1
  7. 2024Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batchingcited by 1
  8. 2024Lean and Mean Adaptive Optimization via Subset-Norm and Subspace-Momentum with Convergence Guaranteescited by 1
  9. 2025Design Criteria for SGD Preconditioners: Local Conditioning, Noise Floors, and Basin Stabilitycited by 1
  10. 2026On Adaptivity in Zeroth-Order Optimizationcited by 1
  11. 2023Locally Optimal Descent for Dynamic Stepsize Schedulingcited by 0
  12. 2024On the O(frac√dT1/4) Convergence Rate of RMSProp and Its Momentum Extension Measured by ℓ1 Normcited by 0
  13. 2025Learning Rate Annealing Improves Tuning Robustness in Stochastic Optimizationcited by 0
  14. 2025A regret minimization approach to fixed-point iterationscited by 0
  15. 2026Stochastic convergence of parallel asynchronous adaptive first-order methodscited by 0
  16. 2026Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuningcited by 0
  17. 2026Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothnesscited by 0
  18. 2026Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Boundscited by 0