# From Gradient Clipping to Normalization for Heavy Tailed SGD

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 79 references that are in the map.
- First posted on arXiv 17 Oct 2024.

## Builds on (most cited first, 30 of 50)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (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)
- [Regularizing and Optimizing LSTM Language Models](https://mlsanity.com/paper/1708.02182/) (2017)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [Linear attention is (maybe) all you need (to understand transformer optimization)](https://mlsanity.com/paper/2310.01082/) (2023)
- [Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees](https://mlsanity.com/paper/2305.01588/) (2023)
- [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)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [A High Probability Analysis of Adaptive SGD with Momentum](https://mlsanity.com/paper/2007.14294/) (2020)
- [High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance](https://mlsanity.com/paper/2302.00999/) (2023)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Online to Offline Conversions, Universality and Adaptive Minibatch Sizes](https://mlsanity.com/paper/1705.10499/) (2017)
- [Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothness](https://mlsanity.com/paper/2102.06489/) (2021)
- [Revisiting the Noise Model of Stochastic Gradient Descent](https://mlsanity.com/paper/2303.02749/) (2023)
- [Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance](https://mlsanity.com/paper/2102.10346/) (2021)
- [Algorithms of Robust Stochastic Optimization Based on Mirror Descent Method](https://mlsanity.com/paper/1907.02707/) (2019)
- [High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noise](https://mlsanity.com/paper/2006.05610/) (2020)

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

- [Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping](https://mlsanity.com/paper/2412.19529/) (2024)
- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Acceleration](https://mlsanity.com/paper/2410.16561/) (2024)
- [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)
- [Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothness](https://mlsanity.com/paper/2502.07923/) (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)
- [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)
- [Smoothed Normalization for Efficient Distributed Private Optimization](https://mlsanity.com/paper/2502.13482/) (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)
- [Improved Convergence in Parameter-Agnostic Error Feedback through Momentum](https://mlsanity.com/paper/2511.14501/) (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)
- [Gradient Clipping Beyond Vector Norms: A Spectral Approach for Matrix-Valued Parameters](https://mlsanity.com/paper/2605.11838/) (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)
- [Gradient Shaping Beyond Clipping: A Functional Perspective on Update Magnitude Control](https://mlsanity.com/paper/2510.01578/) (2025)
- [High-Probability Convergence Guarantees of Decentralized SGD](https://mlsanity.com/paper/2510.06141/) (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)

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