mlsanityData to 7 Oct 2026

High Probability Analysis for Non-Convex Stochastic Optimization with Clipping

arXiv 2307.13680 ↗First posted 25 Jul 2023cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

Gradient clipping is a commonly used technique to stabilize the training process of neural networks. A growing body of studies has shown that gradient clipping is a promising technique for dealing with the heavy-tailed behavior that emerged in stochastic optimization as well. While gradient clipping is significant, its theoretical guarantees are scarce. Most theoretical guarantees only provide an in-expectation analysis and only focus on optimization performance. In this paper, we provide high probability analysis in the non-convex setting and derive the optimization bound and the generalization bound simultaneously for popular stochastic optimization algorithms with gradient clipping, including stochastic gradient descent and its variants of momentum and adaptive stepsizes. With the gradient clipping, we study a heavy-tailed assumption that the gradients only have bounded α-th moments for some α ∈ (1, 2], which is much weaker than the standard bounded second-moment assumption. Overall, our study provides a relatively complete picture for the theoretical guarantee of stochastic optimization algorithms with clipping.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 37 of its 65 references that are in the map. First posted on arXiv 25 Jul 2023.

Builds on

37 of 65 references.

References · 37

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  4. 2019Introduction to Online Convex Optimizationcited by 793
  5. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  6. 2017Exploring Generalization in Deep Learningcited by 595
  7. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  8. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 335
  9. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 213
  10. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  11. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  12. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 155
25 more
  1. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
  2. 2020Momentum Improves Normalized SGDcited by 136
  3. 2017Non-convex Optimization for Machine Learningcited by 132
  4. 2020The Heavy-Tail Phenomenon in SGDcited by 122
  5. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  6. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  7. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
  8. 2018On the Convergence of Adaptive Gradient Methods for Nonconvex Optimizationcited by 91
  9. 2020Improved Analysis of Clipping Algorithms for Non-convex Optimizationcited by 88
  10. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  11. 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 74
  12. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  13. 2014Linear Coupling: An Ultimate Unification of Gradient and Mirror Descentcited by 58
  14. 2019On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networkscited by 42
  15. 2022High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsizecited by 40
  16. 2018Uniform Convergence of Gradients for Non-Convex Learning and Optimizationcited by 38
  17. 2021Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothnesscited by 37
  18. 2019Why are Adaptive Methods Good for Attention Models?cited by 35
  19. 2020High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noisecited by 31
  20. 2017A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descentcited by 29
  21. 2019Non-Gaussianity of Stochastic Gradient Noisecited by 22
  22. 2018On the Generalization of Stochastic Gradient Descent with Momentumcited by 20
  23. 2021High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noisecited by 18
  24. 2021Better SGD using Second-order Momentumcited by 14
  25. 2021Asymmetric Heavy Tails and Implicit Bias in Gaussian Noise Injectionscited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 2; 2026: 1.

5 papers.

  1. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 48
  2. 2025Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noisecited by 38
  3. 2024Clip Body and Tail Separately: High Probability Guarantees for DPSGD with Heavy Tailscited by 4
  4. 2025Stochastic Weakly Convex Optimization Under Heavy-Tailed Noisescited by 0
  5. 2026Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothnesscited by 0