High-Probability Guarantees for SGD under β-Heavy-Tailed Gradient Noise
Abstract
Stochastic gradient descent (SGD) is widely used to train machine learning models, but subsampling the training data introduces noise into its updates. The strength and applicability of high-probability guarantees therefore depend critically on how the tails of gradient noise are modeled. Reports of heavy-tailed gradient noise in deep learning motivate relaxing the bounded-noise and sub-Gaussian assumptions commonly used in high-probability analyses of SGD. We use Young functions from Orlicz space theory to describe noise tails in a common framework. We model SGD gradient noise by adopting a Young function that preserves the finiteness of all polynomial moments while allowing tails heavier than sub-Weibull, including lognormal distributions. The resulting class is called β-heavy-tailed, with β controlling the tail heaviness. We establish concentration inequalities for β-heavy-tailed noise and combine them with a uniform bound on the difference between empirical and population gradients along the SGD trajectory to obtain high-probability bounds on optimization and population-risk stationarity for smooth nonconvex losses under trajectory assumptions. The bounds are not restricted to a particular learning-rate decay rule and make explicit the effects of noise tails and learning-rate schedules. Under the Polyak-Łojasiewicz condition, we bound the risk at the last iterate. We also analyze SGD with gradient clipping under the β-heavy-tailed noise model.
Related
- Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithm
- Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness
- Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping
- Weak-Lα Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails
- A Flexible Heavy-Tailed Probability Model for Skewed Positive Data: Theory, Estimation, and Empirical Assessment
BibTeX
@misc{tong2026highprobability,
title = {{High-Probability Guarantees for SGD under $β$-Heavy-Tailed Gradient Noise}},
author = {Qijun Tong and Masahiro Ikeda and Ryota Kawasumi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32195},
eprint = {2609.32195},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32195},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - High-Probability Guarantees for SGD under β-Heavy-Tailed Gradient Noise
AU - Qijun Tong
AU - Masahiro Ikeda
AU - Ryota Kawasumi
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32195
UR - https://arxiv.org/abs/2609.32195
AB - Stochastic gradient descent (SGD) is widely used to train machine learning models, but subsampling the training data introduces noise into its updates. The strength and applicability of high-probability guarantees therefore depend critically on how the tails of gradient noise are modeled. Reports of heavy-tailed gradient noise in deep learning motivate relaxing the bounded-noise and sub-Gaussian assumptions commonly used in high-probability analyses of SGD. We use Young functions from Orlicz space theory to describe noise tails in a common framework. We model SGD gradient noise by adopting a Young function that preserves the finiteness of all polynomial moments while allowing tails heavier than sub-Weibull, including lognormal distributions. The resulting class is called β-heavy-tailed, with β controlling the tail heaviness. We establish concentration inequalities for β-heavy-tailed noise and combine them with a uniform bound on the difference between empirical and population gradients along the SGD trajectory to obtain high-probability bounds on optimization and population-risk stationarity for smooth nonconvex losses under trajectory assumptions. The bounds are not restricted to a particular learning-rate decay rule and make explicit the effects of noise tails and learning-rate schedules. Under the Polyak-Łojasiewicz condition, we bound the risk at the last iterate. We also analyze SGD with gradient clipping under the β-heavy-tailed noise model.
ER -