mlsanityData to 14 Oct 2026

High Probability Convergence of Stochastic Gradient Methods

arXiv 2302.14843 ↗First posted 28 Feb 2023math.OC cs.DS cs.LGcited by 49

Not on the map. Why?

Abstract (arXiv)

In this work, we describe a generic approach to show convergence with high probability for both stochastic convex and non-convex optimization with sub-Gaussian noise. In previous works for convex optimization, either the convergence is only in expectation or the bound depends on the diameter of the domain. Instead, we show high probability convergence with bounds depending on the initial distance to the optimal solution. The algorithms use step sizes analogous to the standard settings and are universal to Lipschitz functions, smooth functions, and their linear combinations. This method can be applied to the non-convex case. We demonstrate an O((1+σ2log(1/δ))/T+σ/√T) convergence rate when the number of iterations T is known and an O((1+σ2log(T/δ))/√T) convergence rate when T is unknown for SGD, where 1-δ is the desired success probability. These bounds improve over existing bounds in the literature. Additionally, we demonstrate that our techniques can be used to obtain high probability bound for AdaGrad-Norm (Ward et al., 2019) that removes the bounded gradients assumption from previous works. Furthermore, our technique for AdaGrad-Norm extends to the standard per-coordinate AdaGrad algorithm (Duchi et al., 2011), providing the first noise-adapted high probability convergence for AdaGrad.

Key facts. Cited by 49 papers in the map (data through 14 Oct 2026). Builds on 14 of its 33 references that are in the map. First posted on arXiv 28 Feb 2023.

Builds on

14 of 33 references.

References · 14

  1. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  2. 2020A Simple Convergence Proof of Adam and Adagradcited by 171
  3. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 156
  4. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  5. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 97
  6. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  7. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  8. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 61
  9. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  10. 2019Algorithms of Robust Stochastic Optimization Based on Mirror Descent Methodcited by 32
  11. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 28
  12. 2021High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noisecited by 19
2 more
  1. 2020Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalitiescited by 18
  2. 2022High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noisecited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 5; 2024: 20; 2025: 11; 2026: 13.

49 papers.

Sort:

By area:

  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 15
  5. 2024Tuning-Free Stochastic Optimizationcited by 13
  6. 2024How Free is Parameter-Free Stochastic Optimization?cited by 12
  7. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  8. 2024Convergence Rate Analysis of LIONcited by 11
  9. 2023Federated Zeroth-Order Optimization using Trajectory-Informed Surrogate Gradientscited by 8
  10. 2023High Probability Convergence of Adam Under Unbounded Gradients and Affine Variance Noisecited by 8
  11. 2024AdAdaGrad: Adaptive Batch Size Schemes for Adaptive Gradient Methodscited by 8
  12. 2024Understanding Stochastic Natural Gradient Variational Inferencecited by 8
37 more
  1. 2025On the O(frac√dK1/4) Convergence Rate of AdamW Measured by ℓ1 Normcited by 8
  2. 2023High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noisecited by 7
  3. 2023General Tail Bounds for Non-Smooth Stochastic Mirror Descentcited by 7
  4. 2024Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetrycited by 7
  5. 2024Almost sure convergence rates of stochastic gradient methods under gradient dominationcited by 5
  6. 2025Accelerated stochastic first-order method for convex optimization under heavy-tailed noisecited by 4
  7. 2025Sharp High-Probability Rates for Nonlinear SGD under Heavy-Tailed Noise via Symmetrizationcited by 3
  8. 2025Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limitscited by 3
  9. 2026Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGradcited by 3
  10. 2023A Large Deviations Perspective on Policy Gradient Algorithmscited by 2
  11. 2024Lean and Mean Adaptive Optimization via Subset-Norm and Subspace-Momentum with Convergence Guaranteescited by 2
  12. 2025Adaptive Algorithms with Sharp Convergence Rates for Stochastic Hierarchical Optimizationcited by 2
  13. 2025Statistical Guarantees for High-Dimensional Stochastic Gradient Descentcited by 2
  14. 2024A General Reduction for High-Probability Analysis with General Light-Tailed Distributionscited by 1
  15. 2024A Mathematical Model of the Hidden Feedback Loop Effect in Machine Learning Systemscited by 1
  16. 2024Faster Stochastic Optimization with Arbitrary Delays via Asynchronous Mini-Batchingcited by 1
  17. 2024Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Ratescited by 1
  18. 2024Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guaranteescited by 1
  19. 2025Addressing Label Shift in Distributed Learning via Entropy Regularizationcited by 1
  20. 2025Online Learning-guided Learning Rate Adaptation via Gradient Alignmentcited by 1
  21. 2025High-Probability Convergence Guarantees of Decentralized SGDcited by 1
  22. 2026Convergence Analysis of Randomized Subspace Normalized SGD under Heavy-Tailed Noisecited by 1
  23. 2026Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimizationcited by 1
  24. 2024On the O(frac√dT1/4) Convergence Rate of RMSProp and Its Momentum Extension Measured by ℓ1 Normcited by 0
  25. 2024OptEx: Expediting First-Order Optimization with Approximately Parallelized Iterationscited by 0
  26. 2025Learning Rate Annealing Improves Tuning Robustness in Stochastic Optimizationcited by 0
  27. 2025Stochastic Weakly Convex Optimization Under Heavy-Tailed Noisescited by 0
  28. 2026A Short and Unified Convergence Analysis of the SAG, SAGA, and IAG Algorithmscited by 0
  29. 2026Markov Decision Processes of the Third Kind: Learning Distributions by Policy Gradient Descentcited by 0
  30. 2026High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Trackingcited by 0
  31. 2026High-Probability Convergence of SGD via Batched Updatescited by 0
  32. 2026Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothnesscited by 0
  33. 2026Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Boundscited by 0
  34. 2026Gap-free Differentially Private PCA for Gaussian Datacited by 0
  35. 2026Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Boundscited by 0
  36. 2026A stochastic subgradient method with optimal failure exponentcited by 0
  37. 2026Adam under Generalized Smoothness with Second-Moment-Type Stochastic Gradientscited by 0