mlsanityData to 14 Oct 2026

Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Acceleration

arXiv 2410.16561 ↗First posted 21 Oct 2024cs.LG math.OC stat.MLcited by 18

Not on the map. Why?

Abstract (arXiv)

Gradient clipping has long been considered essential for ensuring the convergence of Stochastic Gradient Descent (SGD) in the presence of heavy-tailed gradient noise. In this paper, we revisit this belief and explore whether gradient normalization can serve as an effective alternative or complement. We prove that, under individual smoothness assumptions, gradient normalization alone is sufficient to guarantee convergence of the nonconvex SGD. Moreover, when combined with clipping, it yields far better rates of convergence under more challenging noise distributions. We provide a unifying theory describing normalization-only, clipping-only, and combined approaches. Moving forward, we investigate existing variance-reduced algorithms, establishing that, in such a setting, normalization alone is sufficient for convergence. Finally, we present an accelerated variant that under second-order smoothness improves convergence. Our results provide theoretical insights and practical guidance for using normalization and clipping in nonconvex optimization with heavy-tailed noise.

Key facts. Cited by 18 papers in the map (data through 14 Oct 2026). Builds on 28 of its 39 references that are in the map. First posted on arXiv 21 Oct 2024.

Builds on

28 of 39 references.

References · 28

  1. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,352
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  3. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  4. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  5. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  6. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  7. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 214
  8. 2020Momentum Improves Normalized SGDcited by 139
  9. 2017Lower Bounds for Finding Stationary Points Icited by 126
  10. 2020PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimizationcited by 119
  11. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  12. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
16 more
  1. 2024Heavy-Tailed Class Imbalance and Why Adam Outperforms Gradient Descent on Language Modelscited by 80
  2. 2018Stochastic Nested Variance Reduction for Nonconvex Optimizationcited by 63
  3. 2023High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variancecited by 61
  4. 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
  5. 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
  6. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 49
  7. 2019First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noisecited by 44
  8. 2019Sharp Analysis for Nonconvex SGD Escaping from Saddle Pointscited by 40
  9. 2019Hybrid Stochastic Gradient Descent Algorithms for Stochastic Nonconvex Optimizationcited by 32
  10. 2023Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noisecited by 27
  11. 2022Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variancecited by 24
  12. 2019Lower Bounds for Smooth Nonconvex Finite-Sum Optimizationcited by 20
  13. 2019Stochastic Recursive Variance-Reduced Cubic Regularization Methodscited by 12
  14. 2018Stochastic Variance-Reduced Cubic Regularized Newton Methodcited by 10
  15. 2018Finding Local Minima via Stochastic Nested Variance Reductioncited by 9
  16. 2023Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitzcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 5; 2026: 12.

18 papers.

Sort:

By area:

  1. 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
  2. 2025Memory-Efficient LLM Pretraining via Minimalist Optimizer Designcited by 13
  3. 2025Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noisecited by 11
  4. 2025Accelerated stochastic first-order method for convex optimization under heavy-tailed noisecited by 4
  5. 2026Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGradcited by 3
  6. 2026In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noisecited by 3
  7. 2025Federated Stochastic Minimax Optimization under Heavy-Tailed Noisescited by 2
  8. 2026Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noisecited by 2
  9. 2026Tight Complexity of Muon under Heavy-Tailed Noisecited by 2
  10. 2026Convergence Analysis of Randomized Subspace Normalized SGD under Heavy-Tailed Noisecited by 1
  11. 2026Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimizationcited by 1
  12. 2025Bias-Variance Trade-off for Clipped Stochastic First-Order Methods: From Bounded Variance to Infinite Meancited by 0
6 more
  1. 2026Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationaritycited by 0
  2. 2026Towards Batch-to-Streaming Deep Reinforcement Learning for Continuous Controlcited by 0
  3. 2026Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithmcited by 0
  4. 2026Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and H"older Smoothnesscited by 0
  5. 2026TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noisecited by 0
  6. 2026MeqMuon: Matrix-Equilibrating Muon for LLM Pretrainingcited by 0