mlsanityData to 14 Oct 2026

Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping

arXiv 2412.19529 ↗First posted 27 Dec 2024math.OC cs.LG stat.MLcited by 42

Not on the map. Why?

Abstract (arXiv)

Recently, the study of heavy-tailed noises in first-order nonconvex stochastic optimization has gotten a lot of attention since it was recognized as a more realistic condition as suggested by many empirical observations. Specifically, the stochastic noise (the difference between the stochastic and true gradient) is considered to have only a finite mathfrakp-th moment where mathfrakp∈left(1,2right] instead of assuming it always satisfies the classical finite variance assumption. To deal with this more challenging setting, people have proposed different algorithms and proved them to converge at an optimal O(T^frac1-mathfrakp3mathfrakp-2) rate for smooth objectives after T iterations. Notably, all these new-designed algorithms are based on the same technique - gradient clipping. Naturally, one may want to know whether the clipping method is a necessary ingredient and the only way to guarantee convergence under heavy-tailed noises. In this work, by revisiting the existing Batched Normalized Stochastic Gradient Descent with Momentum (Batched NSGDM) algorithm, we provide the first convergence result under heavy-tailed noises but without gradient clipping. Concretely, we prove that Batched NSGDM can achieve the optimal O(T^frac1-mathfrakp3mathfrakp-2) rate even under the relaxed smooth condition. More interestingly, we also establish the first O(T^frac1-mathfrakp2mathfrakp) convergence rate in the case where the tail index mathfrakp is unknown in advance, which is arguably the common scenario in practice.

Key facts. Cited by 42 papers in the map (data through 14 Oct 2026). Builds on 34 of its 50 references that are in the map. First posted on arXiv 27 Dec 2024.

Builds on

34 of 50 references.

References · 34

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  2. 2019Large Batch Optimization for Deep Learning: Training BERT in 76 minutescited by 674
  3. 2017Large Batch Training of Convolutional Networkscited by 535
  4. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 341
  5. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 307
  6. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 214
  7. 2020Momentum Improves Normalized SGDcited by 139
  8. 2018Convergence of Gradient Descent on Separable Datacited by 110
  9. 2023Convergence of Adam Under Relaxed Assumptionscited by 99
  10. 2020Improved Analysis of Clipping Algorithms for Non-convex Optimizationcited by 89
  11. 2022Robustness to Unbounded Smoothness of Generalized SignSGDcited by 81
  12. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
22 more
  1. 2015Beyond Convexity: Stochastic Quasi-Convex Optimizationcited by 76
  2. 2023High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variancecited by 61
  3. 2023Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptionscited by 57
  4. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 49
  5. 2023Convex and Non-convex Optimization Under Generalized Smoothnesscited by 44
  6. 2019On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networkscited by 43
  7. 2023Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGDcited by 41
  8. 2021Non-convex Distributionally Robust Optimization: Non-asymptotic Analysiscited by 39
  9. 2023Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimizationcited by 35
  10. 2016The Power of Normalization: Faster Evasion of Saddle Pointscited by 29
  11. 2023Parameter-Agnostic Optimization under Relaxed Smoothnesscited by 29
  12. 2022Parameter-free Regret in High Probability with Heavy Tailscited by 28
  13. 2015On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalitiescited by 27
  14. 2023Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noisecited by 27
  15. 2023High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noisecited by 24
  16. 2023Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problemscited by 21
  17. 2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
  18. 2024Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Accelerationcited by 18
  19. 2024Revisiting Convergence of AdaGrad with Relaxed Assumptionscited by 15
  20. 2024On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyondcited by 14
  21. 2023Accelerated Zeroth-order Method for Non-Smooth Stochastic Convex Optimization Problem with Infinite Variancecited by 10
  22. 2023Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothnesscited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 14; 2026: 28.

42 papers.

Sort:

  1. 2025Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noisecited by 41
  2. 2025Can SGD Handle Heavy-Tailed Noise?cited by 17
  3. 2025Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applicationscited by 17
  4. 2025Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noisecited by 11
  5. 2026Muon with Nesterov Momentum: Heavy-Tailed Noise and (Randomized) Inexact Polar Decompositioncited by 8
  6. 2025On Provable Benefits of Muon in Federated Learningcited by 7
  7. 2025Stochastic Bilevel Optimization with Heavy-Tailed Noisecited by 4
  8. 2025Accelerated stochastic first-order method for convex optimization under heavy-tailed noisecited by 4
  9. 2025Sharp High-Probability Rates for Nonlinear SGD under Heavy-Tailed Noise via Symmetrizationcited by 3
  10. 2025Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limitscited by 3
  11. 2026Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGradcited by 3
  12. 2026In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noisecited by 3
30 more
  1. 2025Federated Stochastic Minimax Optimization under Heavy-Tailed Noisescited by 2
  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. 2026Muon Converges under Heavy-Tailed Noise: Nonconvex H"older-Smooth Empirical Risk Minimizationcited by 2
  5. 2026Tight Complexity of Muon under Heavy-Tailed Noisecited by 2
  6. 2026LionMuon: Alternating Spectral and Sign Descent for Efficient Trainingcited by 2
  7. 2026Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Successcited by 2
  8. 2026When to use what Schatten-p norm in deep learning?cited by 2
  9. 2025Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noisecited by 1
  10. 2026Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noisecited by 1
  11. 2026Convergence Analysis of Randomized Subspace Normalized SGD under Heavy-Tailed Noisecited by 1
  12. 2026Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimizationcited by 1
  13. 2026RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimizationcited by 1
  14. 2026A Note on Stability for Orthogonalized Matrix Momentum with Client Samplingcited by 1
  15. 2026Open Problem: Is AdamW Effective Under Heavy-Tailed Noise?cited by 1
  16. 2026Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalizationcited by 1
  17. 2026Parameter-Free Dynamic Regret under Heavy-Tailed Noisecited by 1
  18. 2025Stochastic Weakly Convex Optimization Under Heavy-Tailed Noisescited by 0
  19. 2025Decentralized Stochastic Nonconvex Optimization under the (L0,L1)-Smoothnesscited by 0
  20. 2025Bias-Variance Trade-off for Clipped Stochastic First-Order Methods: From Bounded Variance to Infinite Meancited by 0
  21. 2026Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationaritycited by 0
  22. 2026Constrained Stochastic Spectral Preconditioning Converges for Nonconvex Objectivescited by 0
  23. 2026Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noisecited by 0
  24. 2026Can Entry-Wise Clipping Give Spectral Control of Stochastic Gradients?cited by 0
  25. 2026Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithmcited by 0
  26. 2026Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and H"older Smoothnesscited by 0
  27. 2026Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Boundscited by 0
  28. 2026TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noisecited by 0
  29. 2026High-Probability Guarantees for SGD under β-Heavy-Tailed Gradient Noisecited by 0
  30. 2026LionMuon: Alternating Spectral and Sign Descent for Efficient Trainingcited by 0