mlsanityData to 7 Oct 2026

Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems

arXiv 2311.04161 ↗First posted 7 Nov 2023math.OC cs.DS cs.LGcited by 21

Not on the map. Why?

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.

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

Builds on

7 of 41 references.

References · 7

  1. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 335
  2. 2020A High Probability Analysis of Adaptive SGD with Momentumcited by 61
  3. 2023High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noisecited by 22
  4. 2023High Probability Convergence of Clipped-SGD Under Heavy-tailed Noisecited by 19
  5. 2021High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noisecited by 18
  6. 2023Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailscited by 11
  7. 2016Universal fast gradient method for stochastic composit optimization problemscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 7; 2025: 9; 2026: 5.

21 papers.

Sort:

  1. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 48
  2. 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
  3. 2025Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noisecited by 38
  4. 2025Can SGD Handle Heavy-Tailed Noise?cited by 15
  5. 2025Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothnesscited by 12
  6. 2024Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-tailed Noise and Power of Symmetrycited by 7
  7. 2025Efficient Distributed Optimization under Heavy-Tailed Noisecited by 7
  8. 2024Fast UCB-type algorithms for stochastic bandits with heavy and super heavy symmetric noisecited by 3
  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. 2025Approximation Capabilities of Feedforward Neural Networks with GELU Activationscited by 2
  12. 2026Why is Normalization Preferred? A Worst-Case Complexity Theory for Stochastically Preconditioned SGD under Heavy-Tailed Noisecited by 2
9 more
  1. 2026In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noisecited by 2
  2. 2024Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guaranteescited by 1
  3. 2025High-Probability Convergence Guarantees of Decentralized SGDcited by 1
  4. 2024Tracking the Median of Gradients with a Stochastic Proximal Point Methodcited by 0
  5. 2024Subsampled Ensemble Can Improve Generalization Tail Exponentiallycited by 0
  6. 2025Bias-Variance Trade-off for Clipped Stochastic First-Order Methods: From Bounded Variance to Infinite Meancited by 0
  7. 2026High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Trackingcited by 0
  8. 2026Robust stochastic first order methods in heavy-tailed noise via medoid mini-batch gradient samplingcited by 0
  9. 2026High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependencecited by 0