Acceleration Survives Heavy Tails and Generalized Smoothness
Abstract
We establish high-probability accelerated convergence guarantees for convex (L0,L1)-smooth optimization with unbiased stochastic gradients under heavy-tailed noise, assuming a central α-th noise moment bounded by σα, α∈(1,2]. Such guarantees are known under classical L-smoothness, but extending them through localization over an O(R)-radius ball may introduce an eO(L1R) factor. We avoid this dependence in two ways. First, a two-phase scheme uses Clip-SGD to reach a low-curvature regime, after which clipped stochastic similar triangles (Clip-SSTM) attains, with probability at least 1−δ, f(yK)−f⋆≤𝒪̃(L0R2/K2+σRK−(α−1)/α), where R bounds the distance from the Phase-II starting point to a minimizer. Second, a modified deterministic weight schedule allows Clip-SSTM to start directly from the initial point, controlling the high-curvature transient before recovering acceleration. With the prescribed initialization, both approaches recover the classical accelerated rate, with L1 confined to an accuracy-independent transient, up to logarithmic factors. The two-phase analysis uses two coupled potentials to preserve the low-curvature regime despite momentum; the one-phase analysis controls the initial high-curvature regime using a modified version of the classical SSTM weight schedule.
Related
- Optimal Parameter-Free Second-order Acceleration with Inexact Hessians under Generalized Smoothness
- Stationary activated random walk: regularity, heavy tails, and remixing
- A One-Sided McDiarmid-Type Inequality for Heavy Tails via Reverse KL Tensorization
- Nonlocal Fisher--KPP propagation with heavy tails
- Accelerated Stochastic Method under (H0,H1)-Smoothness and Heavy-Tailed Noise
BibTeX
@misc{kadi2026acceleration,
title = {{Acceleration Survives Heavy Tails and Generalized Smoothness}},
author = {Taha El Bakkali El Kadi and Eduard Gorbunov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23301},
eprint = {2610.23301},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23301},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Acceleration Survives Heavy Tails and Generalized Smoothness
AU - Taha El Bakkali El Kadi
AU - Eduard Gorbunov
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.23301
UR - https://arxiv.org/abs/2610.23301
AB - We establish high-probability accelerated convergence guarantees for convex (L_0,L_1)-smooth optimization with unbiased stochastic gradients under heavy-tailed noise, assuming a central α-th noise moment bounded by σ^α, α∈(1,2]. Such guarantees are known under classical L-smoothness, but extending them through localization over an O(R)-radius ball may introduce an e^O(L_1R) factor. We avoid this dependence in two ways. First, a two-phase scheme uses Clip-SGD to reach a low-curvature regime, after which clipped stochastic similar triangles (Clip-SSTM) attains, with probability at least 1−δ, f(y_K)−f^⋆≤𝒪̃(L_0R^2/K^2+σRK^−(α−1)/α), where R bounds the distance from the Phase-II starting point to a minimizer. Second, a modified deterministic weight schedule allows Clip-SSTM to start directly from the initial point, controlling the high-curvature transient before recovering acceleration. With the prescribed initialization, both approaches recover the classical accelerated rate, with L_1 confined to an accuracy-independent transient, up to logarithmic factors. The two-phase analysis uses two coupled potentials to preserve the low-curvature regime despite momentum; the one-phase analysis controls the initial high-curvature regime using a modified version of the classical SSTM weight schedule.
ER -