mlsanityData to 7 Oct 2026

High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize

arXiv 2204.02833 ↗First posted 6 Apr 2022math.OC cs.LGcited by 40

Not on the map. Why?

Abstract (arXiv)

In this paper, we propose a new, simplified high probability analysis of AdaGrad for smooth, non-convex problems. More specifically, we focus on a particular accelerated gradient (AGD) template (Lan, 2020), through which we recover the original AdaGrad and its variant with averaging, and prove a convergence rate of mathcal O (1/ √T) with high probability without the knowledge of smoothness and variance. We use a particular version of Freedman's concentration bound for martingale difference sequences (Kakade & Tewari, 2008) which enables us to achieve the best-known dependence of log (1 / δ ) on the probability margin δ. We present our analysis in a modular way and obtain a complementary mathcal O (1 / T) convergence rate in the deterministic setting. To the best of our knowledge, this is the first high probability result for AdaGrad with a truly adaptive scheme, i.e., completely oblivious to the knowledge of smoothness and uniform variance bound, which simultaneously has best-known dependence of log( 1/ δ). We further prove noise adaptation property of AdaGrad under additional noise assumptions.

Key facts. Cited by 40 papers in the map (data through 7 Oct 2026). Builds on 25 of its 42 references that are in the map. First posted on arXiv 6 Apr 2022.

Builds on

25 of 42 references.

References · 25

  1. 2017Attention Is All You Needcited by 59,932
  2. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  3. 2019On the Convergence of Adam and Beyondcited by 834
  4. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  5. 2017A General and Adaptive Robust Loss Functioncited by 236
  6. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  7. 2019Adaptive Gradient Methods with Dynamic Bound of Learning Ratecited by 181
  8. 2018On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimizationcited by 173
  9. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 155
  10. 2018A Sufficient Condition for Convergences of Adam and RMSPropcited by 124
  11. 2020An Improved Analysis of Stochastic Gradient Descent with Momentumcited by 117
  12. 2018On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcited by 91
13 more
  1. 2018Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networkscited by 89
  2. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  3. 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 74
  4. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  5. 2014Linear Coupling: An Ultimate Unification of Gradient and Mirror Descentcited by 58
  6. 2019UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimizationcited by 56
  7. 2018Online Adaptive Methods, Universality and Accelerationcited by 51
  8. 2020A new regret analysis for Adam-type algorithmscited by 35
  9. 2019On the Convergence Proof of AMSGrad and a New Versioncited by 21
  10. 2020Momentum via Primal Averaging: Theoretical Insights and Learning Rate Schedules for Non-Convex Optimizationcited by 19
  11. 2020Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalitiescited by 18
  12. 2018Nostalgic Adam: Weighting more of the past gradients when designing the adaptive learning ratecited by 16
  13. 2020Convergence of adaptive algorithms for weakly convex constrained optimizationcited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 8; 2023: 8; 2024: 12; 2025: 7; 2026: 5.

40 papers.

Sort:

  1. 2023Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptionscited by 55
  2. 2023High Probability Convergence of Stochastic Gradient Methodscited by 48
  3. 2023Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGDcited by 41
  4. 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
  5. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 26
  6. 2023Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methodscited by 23
  7. 2024AdaGrad under Anisotropic Smoothnesscited by 22
  8. 2024On Convergence of Adam for Stochastic Optimization under Relaxed Assumptionscited by 21
  9. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  10. 2024Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimizationcited by 16
  11. 2022Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimizationcited by 15
  12. 2024Revisiting Convergence of AdaGrad with Relaxed Assumptionscited by 14
28 more
  1. 2022On the Convergence of AdaGrad(Norm) on Rd: Beyond Convexity, Non-Asymptotic Rate and Accelerationcited by 13
  2. 2023Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Casecited by 13
  3. 2024Tuning-Free Stochastic Optimizationcited by 13
  4. 2024How Free is Parameter-Free Stochastic Optimization?cited by 12
  5. 2022Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methodscited by 8
  6. 2023High Probability Convergence of Adam Under Unbounded Gradients and Affine Variance Noisecited by 8
  7. 2024AdAdaGrad: Adaptive Batch Size Schemes for Adaptive Gradient Methodscited by 8
  8. 2025On the O(frac√dK1/4) Convergence Rate of AdamW Measured by ℓ1 Normcited by 8
  9. 2022TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimizationcited by 7
  10. 2022META-STORM: Generalized Fully-Adaptive Variance Reduced SGD for Unbounded Functionscited by 5
  11. 2023High Probability Analysis for Non-Convex Stochastic Optimization with Clippingcited by 5
  12. 2024Dynamic Byzantine-Robust Learning: Adapting to Switching Byzantine Workerscited by 5
  13. 2022PAC-Bayesian Learning of Optimization Algorithmscited by 4
  14. 2026Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGradcited by 3
  15. 2025Temperature is All You Need for Generalization in Langevin Dynamics and other Markov Processescited by 2
  16. 2025Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimizationcited by 2
  17. 2025Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequencescited by 2
  18. 2026A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad and Muoncited by 2
  19. 2024A General Reduction for High-Probability Analysis with General Light-Tailed Distributionscited by 1
  20. 2024Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizescited by 1
  21. 2025Adaptive Lipschitz-Free Proximal Gradient Methods for Stochastic Composite Nonconvex Optimizationcited by 1
  22. 2025Online Learning-guided Learning Rate Adaptation via Gradient Alignmentcited by 1
  23. 2024On the O(frac√dT1/4) Convergence Rate of RMSProp and Its Momentum Extension Measured by ℓ1 Normcited by 0
  24. 2024An Energy-Based Self-Adaptive Learning Rate for Stochastic Gradient Descent: Enhancing Unconstrained Optimization with VAV methodcited by 0
  25. 2025Learning Rate Annealing Improves Tuning Robustness in Stochastic Optimizationcited by 0
  26. 2026High-Probability Convergence of SGD via Batched Updatescited by 0
  27. 2026Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothnesscited by 0
  28. 2026Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Boundscited by 0