Data to 7 Oct 2026

Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping

arXiv 2005.10785 ↗First posted 21 May 2020math.OC cs.LGcited by 104

Not on the map. Why?

Abstract (arXiv)

In this paper, we propose a new accelerated stochastic first-order method called clipped-SSTM for smooth convex stochastic optimization with heavy-tailed distributed noise in stochastic gradients and derive the first high-probability complexity bounds for this method closing the gap in the theory of stochastic optimization with heavy-tailed noise. Our method is based on a special variant of accelerated Stochastic Gradient Descent (SGD) and clipping of stochastic gradients. We extend our method to the strongly convex case and prove new complexity bounds that outperform state-of-the-art results in this case. Finally, we extend our proof technique and derive the first non-trivial high-probability complexity bounds for SGD with clipping without light-tails assumption on the noise.

Key facts. Cited by 104 papers in the map (data through 7 Oct 2026). First posted on arXiv 21 May 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 18; 2023: 17; 2024: 19; 2025: 14; 2026: 27.

104 papers.

Sort:

2023Noise Is Not the Main Factor Behind the Gap Between SGD and Adam on Transformers, but Sign Descent Might Becited by 114
2023Revisiting Gradient Clipping: Stochastic bias and tight convergence guaranteescited by 83
2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
2022Robustness to Unbounded Smoothness of Generalized SignSGDcited by 80
2021Stochastic Training is Not Necessary for Generalizationcited by 63
2023High Probability Convergence of Stochastic Gradient Methodscited by 48
2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 48
2025Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noisecited by 38
2021Stability and Convergence of Stochastic Gradient Clipping: Beyond Lipschitz Continuity and Smoothnesscited by 37
2021Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variancecited by 34
2023Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noisecited by 27
2022Parameter-free Regret in High Probability with Heavy Tailscited by 26

38 more

2022Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variancecited by 22
2023Adam-family Methods for Nonsmooth Optimization with Convergence Guaranteescited by 22
2024AdaGrad under Anisotropic Smoothnesscited by 22
2022A Communication-Efficient Distributed Gradient Clipping Algorithm for Training Deep Neural Networkscited by 20
2023Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptationcited by 20
2024Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Accelerationcited by 18
2022Stochastic linear optimization never overfits with quadratically-bounded losses on general datacited by 16
2022Nonlinear gradient mappings and stochastic optimization: A general framework with applications to heavy-tail noisecited by 16
2022Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noisecited by 13
2022Federated Learning and Meta Learning: Approaches, Applications, and Directionscited by 12
2025Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0, L1)-Smoothnesscited by 12
2024The Price of Adaptivity in Stochastic Convex Optimizationcited by 11
2021Heavy-tailed Streaming Statistical Estimationcited by 10
2022AdaTerm: Adaptive T-Distribution Estimated Robust Moments for Noise-Robust Stochastic Gradient Optimizationcited by 10
2022Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Surveycited by 10
2022Taming Fat-Tailed ("Heavier-Tailed'' with Potentially Infinite Variance) Noise in Federated Learningcited by 10
2023Clip21: Error Feedback for Gradient Clippingcited by 10
2024Adaptive Gradient Clipping for Robust Federated Learningcited by 10
2022High Probability Bounds for Stochastic Subgradient Schemes with Heavy Tailed Noisecited by 9
2022Large deviations rates for stochastic gradient descent with strongly convex functionscited by 9
2023Convergence and concentration properties of constant step-size SGD through Markov chainscited by 8
2023EPISODE: Episodic Gradient Clipping with Periodic Resampled Corrections for Federated Learning with Heterogeneous Datacited by 7
2023High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noisecited by 7
2023General Tail Bounds for Non-Smooth Stochastic Mirror Descentcited by 7
2025Efficient Distributed Optimization under Heavy-Tailed Noisecited by 7
2023High Probability Analysis for Non-Convex Stochastic Optimization with Clippingcited by 5
2023High Probability Guarantees for Random Reshufflingcited by 5
2026Enhancing LLM Training via Spectral Clippingcited by 5
2021First-Order Methods for Convex Optimizationcited by 4
2021From inexact optimization to learning via gradient concentrationcited by 4
2024Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remediescited by 4
2024Clip Body and Tail Separately: High Probability Guarantees for DPSGD with Heavy Tailscited by 4
2022Flexible risk design using bi-directional dispersioncited by 3
2023Robust Stochastic Optimization via Gradient Quantile Clippingcited by 3
2024Stochastic Weakly Convex Optimization Beyond Lipschitz Continuitycited by 3
2024AdaBatchGrad: Combining Adaptive Batch Size and Adaptive Step Sizecited by 3
2024Privacy of SGD under Gaussian or Heavy-Tailed Noise: Guarantees without Gradient Clippingcited by 3
2025Stochastic Bilevel Optimization with Heavy-Tailed Noisecited by 3

50 most cited of 104 All 104 (JSON)