mlsanityData to 7 Oct 2026

A High Probability Analysis of Adaptive SGD with Momentum

arXiv 2007.14294 ↗First posted 28 Jul 2020stat.ML cs.LGcited by 61

Not on the map. Why?

Abstract (arXiv)

Stochastic Gradient Descent (SGD) and its variants are the most used algorithms in machine learning applications. In particular, SGD with adaptive learning rates and momentum is the industry standard to train deep networks. Despite the enormous success of these methods, our theoretical understanding of these variants in the nonconvex setting is not complete, with most of the results only proving convergence in expectation and with strong assumptions on the stochastic gradients. In this paper, we present a high probability analysis for adaptive and momentum algorithms, under weak assumptions on the function, stochastic gradients, and learning rates. We use it to prove for the first time the convergence of the gradients to zero in high probability in the smooth nonconvex setting for Delayed AdaGrad with momentum.

Key facts. Cited by 61 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 Jul 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 11; 2023: 13; 2024: 16; 2025: 7; 2026: 8.

61 papers.

Sort:

  1. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  2. 2022The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variancecited by 60
  3. 2023Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptionscited by 55
  4. 2023High Probability Convergence of Stochastic Gradient Methodscited by 48
  5. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 48
  6. 2022Understanding AdamW through Proximal Methods and Scale-Freenesscited by 46
  7. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  8. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  9. 2023Momentum Provably Improves Error Feedback!cited by 31
  10. 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
  11. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 26
  12. 2023Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methodscited by 23
38 more
  1. 2023Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problemscited by 21
  2. 2024On Convergence of Adam for Stochastic Optimization under Relaxed Assumptionscited by 21
  3. 2022Stochastic linear optimization never overfits with quadratically-bounded losses on general datacited by 16
  4. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  5. 2024Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimizationcited by 16
  6. 2024Revisiting Convergence of AdaGrad with Relaxed Assumptionscited by 14
  7. 2022On the Convergence of AdaGrad(Norm) on Rd: Beyond Convexity, Non-Asymptotic Rate and Accelerationcited by 13
  8. 2024Tuning-Free Stochastic Optimizationcited by 13
  9. 2024How Free is Parameter-Free Stochastic Optimization?cited by 12
  10. 2025Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothnesscited by 12
  11. 2021On the Last Iterate Convergence of Momentum Methodscited by 9
  12. 2022A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimizationcited by 8
  13. 2023Convergence and concentration properties of constant step-size SGD through Markov chainscited by 8
  14. 2023High Probability Convergence of Adam Under Unbounded Gradients and Affine Variance Noisecited by 8
  15. 2024AdAdaGrad: Adaptive Batch Size Schemes for Adaptive Gradient Methodscited by 8
  16. 2022On the Convergence of mSGD and AdaGrad for Stochastic Optimizationcited by 7
  17. 2022TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimizationcited by 7
  18. 2023High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noisecited by 7
  19. 2024Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetrycited by 7
  20. 2023High Probability Analysis for Non-Convex Stochastic Optimization with Clippingcited by 5
  21. 2023High Probability Guarantees for Random Reshufflingcited by 5
  22. 2024Stochastic Approximation with Biased MCMC for Expectation Maximizationcited by 5
  23. 2025Decision-Dependent Stochastic Optimization: The Role of Distribution Dynamicscited by 5
  24. 2024Clip Body and Tail Separately: High Probability Guarantees for DPSGD with Heavy Tailscited by 4
  25. 2021Dynamic Regret Analysis for Online Meta-Learningcited by 3
  26. 2025Stochastic Bilevel Optimization with Heavy-Tailed Noisecited by 3
  27. 2022Local Model Reconstruction Attacks in Federated Learning and their Usescited by 2
  28. 2024Probabilistic Guarantees of Stochastic Recursive Gradient in Non-Convex Finite Sum Problemscited by 2
  29. 2026MGUP: A Momentum-Gradient Alignment Update Policy for Stochastic Optimizationcited by 2
  30. 2024A General Reduction for High-Probability Analysis with General Light-Tailed Distributionscited by 1
  31. 2024Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guaranteescited by 1
  32. 2024Sketched Adaptive Federated Deep Learning: A Sharp Convergence Analysiscited by 1
  33. 2024Attribute Inference Attacks for Federated Regression Taskscited by 1
  34. 2025Online Learning-guided Learning Rate Adaptation via Gradient Alignmentcited by 1
  35. 2025Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Boundscited by 1
  36. 2025High-Probability Convergence Guarantees of Decentralized SGDcited by 1
  37. 2026Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimizationcited by 1
  38. 2026Robust and Fast Training via Per-Sample Clippingcited by 1

50 most cited of 61 All 61 (JSON)