mlsanityData to 7 Oct 2026

High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails

arXiv 2106.14343 ↗First posted 28 Jun 2021cs.LG math.OC stat.MLcited by 80

Not on the map. Why?

Abstract (arXiv)

We consider non-convex stochastic optimization using first-order algorithms for which the gradient estimates may have heavy tails. We show that a combination of gradient clipping, momentum, and normalized gradient descent yields convergence to critical points in high-probability with best-known rates for smooth losses when the gradients only have bounded mathfrakpth moments for some mathfrakp∈(1,2]. We then consider the case of second-order smooth losses, which to our knowledge have not been studied in this setting, and again obtain high-probability bounds for any mathfrakp. Moreover, our results hold for arbitrary smooth norms, in contrast to the typical SGD analysis which requires a Hilbert space norm. Further, we show that after a suitable "burn-in" period, the objective value will monotonically decrease for every iteration until a critical point is identified, which provides intuition behind the popular practice of learning rate "warm-up" and also yields a last-iterate guarantee.

Key facts. Cited by 80 papers in the map (data through 7 Oct 2026). Builds on 34 of its 44 references that are in the map. First posted on arXiv 28 Jun 2021.

Builds on

34 of 44 references.

References · 34

  1. 2017Attention Is All You Needcited by 59,932
  2. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  3. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  4. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  5. 2020Language Models are Few-Shot Learnerscited by 32,199
  6. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,491
  7. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,479
  8. 2019On the Convergence of Adam and Beyondcited by 834
  9. 2019On the Variance of the Adaptive Learning Rate and Beyondcited by 763
  10. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  11. 2019Large Batch Optimization for Deep Learning: Training BERT in 76 minutescited by 671
  12. 2017Large Batch Training of Convolutional Networkscited by 529
22 more
  1. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  2. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 335
  3. 2019Learning Deep Transformer Models for Machine Translationcited by 309
  4. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  5. 2018Time-uniform, nonparametric, nonasymptotic confidence sequencescited by 220
  6. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 213
  7. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  8. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 155
  9. 2019Transformers without Tears: Improving the Normalization of Self-Attentioncited by 153
  10. 2020Momentum Improves Normalized SGDcited by 136
  11. 2019Mean estimation and regression under heavy-tailed distributions--a surveycited by 133
  12. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  13. 2018The Best of Both Worlds: Combining Recent Advances in Neural Machine Translationcited by 101
  14. 2020Improved Analysis of Clipping Algorithms for Non-convex Optimizationcited by 88
  15. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  16. 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
  17. 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
  18. 2019On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networkscited by 42
  19. 2019Sharp Analysis for Nonconvex SGD Escaping from Saddle Pointscited by 40
  20. 2020Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitationscited by 39
  21. 2021Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variancecited by 34
  22. 2019Reducing the variance in online optimization by transporting past gradientscited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 8; 2023: 17; 2024: 9; 2025: 17; 2026: 29.

80 papers.

Sort:

  1. 2022Robustness to Unbounded Smoothness of Generalized SignSGDcited by 80
  2. 2023High Probability Convergence of Stochastic Gradient Methodscited by 48
  3. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 48
  4. 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
  5. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  6. 2025Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noisecited by 38
  7. 2022Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimizationcited by 35
  8. 2023Momentum Provably Improves Error Feedback!cited by 31
  9. 2023SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variancecited by 30
  10. 2025On the Convergence of Muon and Beyondcited by 28
  11. 2023Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noisecited by 27
  12. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 26
38 more
  1. 2022Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variancecited by 22
  2. 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
  3. 2024Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Accelerationcited by 18
  4. 2025Can SGD Handle Heavy-Tailed Noise?cited by 15
  5. 2022Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noisecited by 13
  6. 2025Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothnesscited by 12
  7. 2022Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Lojasiewicz Functions when the Non-Convexity is Averaged-Outcited by 11
  8. 2025Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noisecited by 11
  9. 2023Clip21: Error Feedback for Gradient Clippingcited by 10
  10. 2023Provably Robust Temporal Difference Learning for Heavy-Tailed Rewardscited by 9
  11. 2023Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothnesscited by 7
  12. 2023EPISODE: Episodic Gradient Clipping with Periodic Resampled Corrections for Federated Learning with Heterogeneous Datacited by 7
  13. 2025Efficient Distributed Optimization under Heavy-Tailed Noisecited by 7
  14. 2023Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimizationcited by 5
  15. 2023High Probability Analysis for Non-Convex Stochastic Optimization with Clippingcited by 5
  16. 2023High Probability Guarantees for Random Reshufflingcited by 5
  17. 2022Flexible risk design using bi-directional dispersioncited by 3
  18. 2023Soft ascent-descent as a stable and flexible alternative to floodingcited by 3
  19. 2024Limit Theorems for Stochastic Gradient Descent with Infinite Variancecited by 3
  20. 2025Sharp High-Probability Rates for Nonlinear SGD under Heavy-Tailed Noise via Symmetrizationcited by 3
  21. 2025Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limitscited by 3
  22. 2025Accelerated stochastic first-order method for convex optimization under heavy-tailed noisecited by 3
  23. 2025Noise-Adaptive Layerwise Learning Rates: Accelerating Geometry-Aware Optimization for Deep Neural Network Trainingcited by 3
  24. 2026Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGradcited by 3
  25. 2026Solving Stochastic Fixed-Point Equations with High Probabilitycited by 3
  26. 2023Demystifying the Myths and Legends of Nonconvex Convergence of SGDcited by 2
  27. 2023Using Stochastic Gradient Descent to Smooth Nonconvex Functions: Analysis of Implicit Graduated Optimizationcited by 2
  28. 2025Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequencescited by 2
  29. 2026Rethinking LoRA for Data Heterogeneous Federated Learning: Subspace and State Alignmentcited by 2
  30. 2026Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noisecited by 2
  31. 2026Muon Converges under Heavy-Tailed Noise: Nonconvex H"older-Smooth Empirical Risk Minimizationcited by 2
  32. 2026Scale-Invariant Neural Network Optimization: Norm Geometry and Heavy-Tailed Noisecited by 2
  33. 2026In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noisecited by 2
  34. 2023Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed banditscited by 1
  35. 2024A General Reduction for High-Probability Analysis with General Light-Tailed Distributionscited by 1
  36. 2024Sketched Adaptive Federated Deep Learning: A Sharp Convergence Analysiscited by 1
  37. 2024Lean and Mean Adaptive Optimization via Subset-Norm and Subspace-Momentum with Convergence Guaranteescited by 1
  38. 2025Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Boundscited by 1

50 most cited of 80 All 80 (JSON)