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

arXiv: https://arxiv.org/abs/2412.19529 · HTML: https://mlsanity.com/paper/2412.19529/

## 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 (most cited first, 30 of 34)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Large Batch Optimization for Deep Learning: Training BERT in 76 minutes](https://mlsanity.com/paper/1904.00962/) (2019)
- [Large Batch Training of Convolutional Networks](https://mlsanity.com/paper/1708.03888/) (2017)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [Convergence of Gradient Descent on Separable Data](https://mlsanity.com/paper/1803.01905/) (2018)
- [Convergence of Adam Under Relaxed Assumptions](https://mlsanity.com/paper/2304.13972/) (2023)
- [Improved Analysis of Clipping Algorithms for Non-convex Optimization](https://mlsanity.com/paper/2010.02519/) (2020)
- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [Beyond Convexity: Stochastic Quasi-Convex Optimization](https://mlsanity.com/paper/1507.02030/) (2015)
- [High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance](https://mlsanity.com/paper/2302.00999/) (2023)
- [Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions](https://mlsanity.com/paper/2305.18471/) (2023)
- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)
- [Convex and Non-convex Optimization Under Generalized Smoothness](https://mlsanity.com/paper/2306.01264/) (2023)
- [On the Heavy-Tailed Theory of Stochastic Gradient Descent for Deep Neural Networks](https://mlsanity.com/paper/1912.00018/) (2019)
- [Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD](https://mlsanity.com/paper/2302.06570/) (2023)
- [Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis](https://mlsanity.com/paper/2110.12459/) (2021)
- [Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization](https://mlsanity.com/paper/2303.02854/) (2023)
- [The Power of Normalization: Faster Evasion of Saddle Points](https://mlsanity.com/paper/1611.04831/) (2016)
- [Parameter-Agnostic Optimization under Relaxed Smoothness](https://mlsanity.com/paper/2311.03252/) (2023)
- [Parameter-free Regret in High Probability with Heavy Tails](https://mlsanity.com/paper/2210.14355/) (2022)
- [On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities](https://mlsanity.com/paper/1510.03925/) (2015)
- [Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2302.06763/) (2023)
- [High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise](https://mlsanity.com/paper/2310.01860/) (2023)
- [Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems](https://mlsanity.com/paper/2311.04161/) (2023)
- [Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation](https://mlsanity.com/paper/2303.12277/) (2023)
- [Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Acceleration](https://mlsanity.com/paper/2410.16561/) (2024)

## Built on by (most cited first, 30 of 42)

- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [Can SGD Handle Heavy-Tailed Noise?](https://mlsanity.com/paper/2508.04860/) (2025)
- [Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications](https://mlsanity.com/paper/2508.07473/) (2025)
- [Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise](https://mlsanity.com/paper/2506.11214/) (2025)
- [Muon with Nesterov Momentum: Heavy-Tailed Noise and (Randomized) Inexact Polar Decomposition](https://mlsanity.com/paper/2605.06884/) (2026)
- [On Provable Benefits of Muon in Federated Learning](https://mlsanity.com/paper/2510.03866/) (2025)
- [Stochastic Bilevel Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2509.14952/) (2025)
- [Accelerated stochastic first-order method for convex optimization under heavy-tailed noise](https://mlsanity.com/paper/2510.11676/) (2025)
- [Sharp High-Probability Rates for Nonlinear SGD under Heavy-Tailed Noise via Symmetrization](https://mlsanity.com/paper/2507.09093/) (2025)
- [Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits](https://mlsanity.com/paper/2510.10690/) (2025)
- [Can Adaptive Gradient Methods Converge under Heavy-Tailed Noise? A Case Study of AdaGrad](https://mlsanity.com/paper/2605.18694/) (2026)
- [In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise](https://mlsanity.com/paper/2606.00520/) (2026)
- [Federated Stochastic Minimax Optimization under Heavy-Tailed Noises](https://mlsanity.com/paper/2511.04456/) (2025)
- [Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2601.19379/) (2026)
- [Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2602.13413/) (2026)
- [Muon Converges under Heavy-Tailed Noise: Nonconvex H"older-Smooth Empirical Risk Minimization](https://mlsanity.com/paper/2603.15059/) (2026)
- [Tight Complexity of Muon under Heavy-Tailed Noise](https://mlsanity.com/paper/2605.18528/) (2026)
- [LionMuon: Alternating Spectral and Sign Descent for Efficient Training](https://mlsanity.com/paper/2605.19811/) (2026)
- [Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success](https://mlsanity.com/paper/2606.14560/) (2026)
- [When to use what Schatten-p norm in deep learning?](https://mlsanity.com/paper/2606.15268/) (2026)
- [Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2509.15543/) (2025)
- [Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2601.11435/) (2026)
- [Convergence Analysis of Randomized Subspace Normalized SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2601.20399/) (2026)
- [Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization](https://mlsanity.com/paper/2602.05657/) (2026)
- [RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimization](https://mlsanity.com/paper/2602.06824/) (2026)
- [A Note on Stability for Orthogonalized Matrix Momentum with Client Sampling](https://mlsanity.com/paper/2606.01720/) (2026)
- [Open Problem: Is AdamW Effective Under Heavy-Tailed Noise?](https://mlsanity.com/paper/2606.23676/) (2026)
- [Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization](https://mlsanity.com/paper/2607.08104/) (2026)
- [Parameter-Free Dynamic Regret under Heavy-Tailed Noise](https://mlsanity.com/paper/2607.27073/) (2026)
- [Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises](https://mlsanity.com/paper/2507.13283/) (2025)

## 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.