# Can SGD Handle Heavy-Tailed Noise?

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 58 references that are in the map.
- First posted on arXiv 6 Aug 2025.

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

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization](https://mlsanity.com/paper/1308.6594/) (2013)
- [Linear attention is (maybe) all you need (to understand transformer optimization)](https://mlsanity.com/paper/2310.01082/) (2023)
- [Unified Optimal Analysis of the (Stochastic) Gradient Method](https://mlsanity.com/paper/1907.04232/) (2019)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance](https://mlsanity.com/paper/2302.00999/) (2023)
- [Efficiency of minimizing compositions of convex functions and smooth maps](https://mlsanity.com/paper/1605.00125/) (2016)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)
- [Stochastic Heavy Ball](https://mlsanity.com/paper/1609.04228/) (2016)
- [Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping](https://mlsanity.com/paper/2412.19529/) (2024)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2312.08531/) (2023)
- [Revisiting the Noise Model of Stochastic Gradient Descent](https://mlsanity.com/paper/2303.02749/) (2023)
- [The Complexity of Finding Stationary Points with Stochastic Gradient Descent](https://mlsanity.com/paper/1910.01845/) (2019)
- [Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance](https://mlsanity.com/paper/2102.10346/) (2021)
- [The Complexity of Making the Gradient Small in Stochastic Convex Optimization](https://mlsanity.com/paper/1902.04686/) (2019)
- [Stochastic subgradient method converges at the rate O(k-1/4) on weakly convex functions](https://mlsanity.com/paper/1802.02988/) (2018)
- [On Proximal Policy Optimization's Heavy-tailed Gradients](https://mlsanity.com/paper/2102.10264/) (2021)
- [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)
- [Deterministic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2302.08300/) (2023)
- [Exact convergence rate of the last iterate in subgradient methods](https://mlsanity.com/paper/2307.11134/) (2023)
- [On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization](https://mlsanity.com/paper/1307.5001/) (2013)
- [Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance](https://mlsanity.com/paper/2202.11632/) (2022)
- [Two Sides of One Coin: the Limits of Untuned SGD and the Power of Adaptive Methods](https://mlsanity.com/paper/2305.12475/) (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)
- [Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailed](https://mlsanity.com/paper/2406.04443/) (2024)

## Built on by (most cited first, 17 of 17)

- [Accelerated stochastic first-order method for convex optimization under heavy-tailed noise](https://mlsanity.com/paper/2510.11676/) (2025)
- [Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences](https://mlsanity.com/paper/2512.13123/) (2025)
- [Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits](https://mlsanity.com/paper/2510.10690/) (2025)
- [In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise](https://mlsanity.com/paper/2606.00520/) (2026)
- [Muon Converges under Heavy-Tailed Noise: Nonconvex H"older-Smooth Empirical Risk Minimization](https://mlsanity.com/paper/2603.15059/) (2026)
- [Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization](https://mlsanity.com/paper/2602.05657/) (2026)
- [Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis](https://mlsanity.com/paper/2603.19648/) (2026)
- [Beyond a Single Explanation of the Adam--SGD Gap](https://mlsanity.com/paper/2606.14259/) (2026)
- [Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization](https://mlsanity.com/paper/2607.08104/) (2026)
- [Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential](https://mlsanity.com/paper/2510.02735/) (2025)
- [Bias-Variance Trade-off for Clipped Stochastic First-Order Methods: From Bounded Variance to Infinite Mean](https://mlsanity.com/paper/2512.14686/) (2025)
- [Constrained Stochastic Spectral Preconditioning Converges for Nonconvex Objectives](https://mlsanity.com/paper/2605.11850/) (2026)
- [Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2607.25492/) (2026)
- [The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization](https://mlsanity.com/paper/2609.06064/) (2026)
- [Why Clipping Matters in AdaGrad? Toward a High-Probability Theory under Generalized Smoothness](https://mlsanity.com/paper/2609.30276/) (2026)
- [Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2609.32962/) (2026)
- [A stochastic subgradient method with optimal failure exponent](https://mlsanity.com/paper/2609.37425/) (2026)

## Abstract (arXiv)

Stochastic Gradient Descent (SGD) is a cornerstone of large-scale optimization, yet its theoretical behavior under heavy-tailed noise -- common in modern machine learning and reinforcement learning -- remains poorly understood. In this work, we rigorously investigate whether vanilla SGD, devoid of any adaptive modifications, can provably succeed under such adverse stochastic conditions. Assuming only that stochastic gradients have bounded p-th moments for some p ∈ (1, 2], we establish sharp convergence guarantees for (projected) SGD across convex, strongly convex, and non-convex problem classes. In particular, we show that SGD achieves minimax optimal sample complexity under minimal assumptions in the convex and strongly convex regimes: O(varepsilon^-fracpp-1) and O(varepsilon^-fracp2(p-1)), respectively. For non-convex objectives, under standard smoothness and a bounded central p-th moment, we prove convergence to a stationary point with O(varepsilon^-frac2pp-1) complexity, and complement this with a matching SGD-specific lower bound, showing that this rate cannot be improved by any deterministic positive non-increasing step-size schedule. These results challenge the prevailing view that heavy-tailed noise renders SGD ineffective, and establish vanilla SGD as a robust and theoretically principled baseline -- even in regimes where the variance is unbounded.