# Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 41 references that are in the map.
- First posted on arXiv 7 Nov 2023.

## Builds on (most cited first, 7 of 7)

- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [A High Probability Analysis of Adaptive SGD with Momentum](https://mlsanity.com/paper/2007.14294/) (2020)
- [High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise](https://mlsanity.com/paper/2310.01860/) (2023)
- [High Probability Convergence of Clipped-SGD Under Heavy-tailed Noise](https://mlsanity.com/paper/2302.05437/) (2023)
- [High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2106.05958/) (2021)
- [Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tails](https://mlsanity.com/paper/2304.01119/) (2023)
- [Universal fast gradient method for stochastic composit optimization problems](https://mlsanity.com/paper/1604.05275/) (2016)

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

- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)
- [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)
- [Can SGD Handle Heavy-Tailed Noise?](https://mlsanity.com/paper/2508.04860/) (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)
- [Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetry](https://mlsanity.com/paper/2410.15637/) (2024)
- [Efficient Distributed Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2502.04164/) (2025)
- [Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noise](https://mlsanity.com/paper/2402.07062/) (2024)
- [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)
- [In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise](https://mlsanity.com/paper/2606.00520/) (2026)
- [Approximation Capabilities of Feedforward Neural Networks with GELU Activations](https://mlsanity.com/paper/2512.21749/) (2025)
- [Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noise](https://mlsanity.com/paper/2602.13413/) (2026)
- [Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees](https://mlsanity.com/paper/2410.13954/) (2024)
- [High-Probability Convergence Guarantees of Decentralized SGD](https://mlsanity.com/paper/2510.06141/) (2025)
- [Tracking the Median of Gradients with a Stochastic Proximal Point Method](https://mlsanity.com/paper/2402.12828/) (2024)
- [Subsampled Ensemble Can Improve Generalization Tail Exponentially](https://mlsanity.com/paper/2405.14741/) (2024)
- [Bias-Variance Trade-off for Clipped Stochastic First-Order Methods: From Bounded Variance to Infinite Mean](https://mlsanity.com/paper/2512.14686/) (2025)
- [High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking](https://mlsanity.com/paper/2605.00281/) (2026)
- [Robust stochastic first order methods in heavy-tailed noise via medoid mini-batch gradient sampling](https://mlsanity.com/paper/2605.07634/) (2026)
- [High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence](https://mlsanity.com/paper/2606.26316/) (2026)

## Abstract (arXiv)

We consider stochastic optimization problems with heavy-tailed noise with structured density. For such problems, we show that it is possible to get faster rates of convergence than O(K-2(α - 1)/α), when the stochastic gradients have finite moments of order α ∈ (1, 2]. In particular, our analysis allows the noise norm to have an unbounded expectation. To achieve these results, we stabilize stochastic gradients, using smoothed medians of means. We prove that the resulting estimates have negligible bias and controllable variance. This allows us to carefully incorporate them into clipped-SGD and clipped-SSTM and derive new high-probability complexity bounds in the considered setup.