mlsanityData to 7 Oct 2026

From Gradient Clipping to Normalization for Heavy Tailed SGD

arXiv 2410.13849 ↗First posted 17 Oct 2024math.OC cs.LG stat.MLcited by 48

Not on the map. Why?

Abstract (arXiv)

Recent empirical evidence indicates that many machine learning applications involve heavy-tailed gradient noise, which challenges the standard assumptions of bounded variance in stochastic optimization. Gradient clipping has emerged as a popular tool to handle this heavy-tailed noise, as it achieves good performance in this setting both theoretically and practically. However, our current theoretical understanding of non-convex gradient clipping has three main shortcomings. First, the theory hinges on large, increasing clipping thresholds, which are in stark contrast to the small constant clipping thresholds employed in practice. Second, clipping thresholds require knowledge of problem-dependent parameters to guarantee convergence. Lastly, even with this knowledge, current sampling complexity upper bounds for the method are sub-optimal in nearly all parameters. To address these issues, we study convergence of Normalized SGD (NSGD). First, we establish a parameter-free sample complexity for NSGD of Oleft(varepsilon^-frac2pp-1right) to find an varepsilon-stationary point. Furthermore, we prove tightness of this result, by providing a matching algorithm-specific lower bound. In the setting where all problem parameters are known, we show this complexity is improved to Oleft(varepsilon^-frac3p-2p-1right), matching the previously known lower bound for all first-order methods in all problem dependent parameters. Finally, we establish high-probability convergence of NSGD with a mild logarithmic dependence on the failure probability. Our work complements the studies of gradient clipping under heavy tailed noise improving the sample complexities of existing algorithms and offering an alternative mechanism to achieve high probability convergence.

Key facts. Cited by 48 papers in the map (data through 7 Oct 2026). Builds on 50 of its 79 references that are in the map. First posted on arXiv 17 Oct 2024.

Builds on

50 of 79 references.

References · 50

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 13,958
  3. 2022OPT: Open Pre-trained Transformer Language Modelscited by 3,464
  4. 2016Pointer Sentinel Mixture Modelscited by 2,992
  5. 2016Deep Learning with Differential Privacycited by 2,682
  6. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  7. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  8. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 561
  9. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
  10. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  11. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 213
  12. 2017Regularizing and Optimizing LSTM Language Modelscited by 205
38 more
  1. 2020Momentum Improves Normalized SGDcited by 136
  2. 2017Lower Bounds for Finding Stationary Points Icited by 125
  3. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  4. 2023Linear attention is (maybe) all you need (to understand transformer optimization)cited by 97
  5. 2023Revisiting Gradient Clipping: Stochastic bias and tight convergence guaranteescited by 83
  6. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  7. 2022Robustness to Unbounded Smoothness of Generalized SignSGDcited by 80
  8. 2015Beyond Convexity: Stochastic Quasi-Convex Optimizationcited by 75
  9. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 67
  10. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  11. 2023High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variancecited by 60
  12. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  13. 2017Online to Offline Conversions, Universality and Adaptive Minibatch Sizescited by 39
  14. 2021Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothnesscited by 37
  15. 2023Revisiting the Noise Model of Stochastic Gradient Descentcited by 35
  16. 2021Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variancecited by 34
  17. 2019Algorithms of Robust Stochastic Optimization Based on Mirror Descent Methodcited by 32
  18. 2020High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noisecited by 31
  19. 2021On Proximal Policy Optimization's Heavy-tailed Gradientscited by 30
  20. 2016The Power of Normalization: Faster Evasion of Saddle Pointscited by 29
  21. 2023Parameter-Agnostic Optimization under Relaxed Smoothnesscited by 29
  22. 2023Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noisecited by 27
  23. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 26
  24. 2023The Crucial Role of Normalization in Sharpness-Aware Minimizationcited by 26
  25. 2023Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methodscited by 23
  26. 2023High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noisecited by 22
  27. 2023Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problemscited by 21
  28. 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
  29. 2023High Probability Convergence of Clipped-SGD Under Heavy-tailed Noisecited by 19
  30. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  31. 2022Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noisecited by 16
  32. 2020Optimal Mean Estimation without a Variancecited by 13
  33. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  34. 2023Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variancecited by 10
  35. 2023Provably Robust Temporal Difference Learning for Heavy-Tailed Rewardscited by 9
  36. 2023High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noisecited by 7
  37. 2023High Probability Analysis for Non-Convex Stochastic Optimization with Clippingcited by 5
  38. 2024Clip Body and Tail Separately: High Probability Guarantees for DPSGD with Heavy Tailscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 18; 2026: 28.

48 papers.

Sort:

  1. 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
  2. 2025Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noisecited by 38
  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. 2025Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applicationscited 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. 2025Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noisecited by 11
  8. 2026Muon with Nesterov Momentum: Heavy-Tailed Noise and (Randomized) Inexact Polar Decompositioncited by 8
  9. 2025Sharp High-Probability Rates for Nonlinear SGD under Heavy-Tailed Noise via Symmetrizationcited by 3
  10. 2025Stochastic Bilevel Optimization with Heavy-Tailed Noisecited by 3
  11. 2025Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limitscited by 3
  12. 2025Accelerated stochastic first-order method for convex optimization under heavy-tailed noisecited by 3
36 more
  1. 2026Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGradcited by 3
  2. 2026Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noisecited by 2
  3. 2026Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noisecited by 2
  4. 2026Gradient Clipping Beyond Vector Norms: A Spectral Approach for Matrix-Valued Parameterscited by 2
  5. 2026Scale-Invariant Neural Network Optimization: Norm Geometry and Heavy-Tailed Noisecited by 2
  6. 2026LionMuon: Alternating Spectral and Sign Descent for Efficient Trainingcited by 2
  7. 2026In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noisecited by 2
  8. 2025Smoothed Normalization for Efficient Distributed Private Optimizationcited by 1
  9. 2025Gradient Shaping Beyond Clipping: A Functional Perspective on Update Magnitude Controlcited by 1
  10. 2025High-Probability Convergence Guarantees of Decentralized SGDcited by 1
  11. 2025Federated Stochastic Minimax Optimization under Heavy-Tailed Noisescited by 1
  12. 2026Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noisecited by 1
  13. 2026Convergence Analysis of Randomized Subspace Normalized SGD under Heavy-Tailed Noisecited by 1
  14. 2026Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimizationcited by 1
  15. 2026RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimizationcited by 1
  16. 2026Robust and Fast Training via Per-Sample Clippingcited by 1
  17. 2026Beyond a Single Explanation of the Adam--SGD Gapcited by 1
  18. 2026Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Successcited by 1
  19. 2025Stochastic Weakly Convex Optimization Under Heavy-Tailed Noisescited by 0
  20. 2025Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noisecited by 0
  21. 2025Improved Convergence in Parameter-Agnostic Error Feedback through Momentumcited by 0
  22. 2025Learnability Window in Gated Recurrent Neural Networkscited by 0
  23. 2025Bias-Variance Trade-off for Clipped Stochastic First-Order Methods: From Bounded Variance to Infinite Meancited by 0
  24. 2026Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationaritycited by 0
  25. 2026Byzantine-Robust Optimization under (L0, L1)-Smoothnesscited by 0
  26. 2026High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Trackingcited by 0
  27. 2026Constrained Stochastic Spectral Preconditioning Converges for Nonconvex Objectivescited by 0
  28. 2026Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noisecited by 0
  29. 2026Can Entry-Wise Clipping Give Spectral Control of Stochastic Gradients?cited by 0
  30. 2026Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglerscited by 0
  31. 2026When to use what Schatten-p norm in deep learning?cited by 0
  32. 2026High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependencecited by 0
  33. 2026Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalizationcited by 0
  34. 2026Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothnesscited by 0
  35. 2026TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noisecited by 0
  36. 2026LionMuon: Alternating Spectral and Sign Descent for Efficient Trainingcited by 0