Weak-Lα Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails
Abstract
Gradient clipping is a key tool for obtaining high-probability convergence guarantees for stochastic first-order methods under heavy-tailed noise. Existing analyses typically assume a bounded central moment of order α∈(1,2], which excludes distributions with tails of order u−α at the critical exponent. In this paper, we consider smooth convex optimization under affine heavy-tailed noise, whose scale may grow with the gradient norm. We derive high-probability convergence guarantees for clipped SGD (Clip-SGD) and its accelerated variant Clip-SSTM under a weak-Lα tail condition, which is strictly weaker than the corresponding moment bound. For 1<α<2, the clipping bounds have the same powers of the clipping level as in the moment case, and both methods attain the additive stochastic rate K−(α−1)/α. The gradient-dependent noise contributes a faster-decaying term of order K−2(α−1)/α, up to logarithmic factors. At α=2, we characterize the additional logarithmic factor on the Lorentz scale and establish its necessity for the additive error at fixed confidence. We also analyze Clip-SGD with prescribed clipping levels and derive finite-horizon guarantees for reaching a neighborhood determined by the clipping bias. For additive noise, matching lower bounds show that this neighborhood is unavoidable, up to constants and the natural error cap. Numerical experiments with Pareto noise illustrate the theoretical results.
Related
- Almost Sure Convergence Analysis of Stochastic Gradient Methods with Clipping and Additive Noise
- Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping
- High-Probability Guarantees for SGD under β-Heavy-Tailed Gradient Noise
- Theoretical guarantees for stochastic gradient Langevin dynamics
- Estimation of the Label-Noise Transition Matrix with Performance Guarantees via Selective Classification
BibTeX
@misc{nekrasova2026weaklα,
title = {{Weak-$L^α$ Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails}},
author = {Alyona Nekrasova and Makar Sidorov and Savelii Chezhegov and Alexander Gasnikov and Margarita Preobrazhenskaia and Igor Preobrazhensky and Eduard Gorbunov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.28107},
eprint = {2610.28107},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.28107},
}
RIS
TY - UNPB
TI - Weak-L^α Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails
AU - Alyona Nekrasova
AU - Makar Sidorov
AU - Savelii Chezhegov
AU - Alexander Gasnikov
AU - Margarita Preobrazhenskaia
AU - Igor Preobrazhensky
AU - Eduard Gorbunov
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.28107
UR - https://arxiv.org/abs/2610.28107
AB - Gradient clipping is a key tool for obtaining high-probability convergence guarantees for stochastic first-order methods under heavy-tailed noise. Existing analyses typically assume a bounded central moment of order α∈(1,2], which excludes distributions with tails of order u^−α at the critical exponent. In this paper, we consider smooth convex optimization under affine heavy-tailed noise, whose scale may grow with the gradient norm. We derive high-probability convergence guarantees for clipped SGD (Clip-SGD) and its accelerated variant Clip-SSTM under a weak-L^α tail condition, which is strictly weaker than the corresponding moment bound. For 1<α<2, the clipping bounds have the same powers of the clipping level as in the moment case, and both methods attain the additive stochastic rate K^−(α−1)/α. The gradient-dependent noise contributes a faster-decaying term of order K^−2(α−1)/α, up to logarithmic factors. At α=2, we characterize the additional logarithmic factor on the Lorentz scale and establish its necessity for the additive error at fixed confidence. We also analyze Clip-SGD with prescribed clipping levels and derive finite-horizon guarantees for reaching a neighborhood determined by the clipping bias. For additive noise, matching lower bounds show that this neighborhood is unavoidable, up to constants and the natural error cap. Numerical experiments with Pareto noise illustrate the theoretical results.
ER -