Sharp High-Probability Rates for Nonlinear SGD Under Heavy-Tailed Noise via Symmetrization
IEEE Transactions on Information Theory · 2026-08 · 72 (8) · 6071-6092
DOI: 10.1109/tit.2026.3682577 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-08. Verfasst von Aleksandar Armacki und 3 weiteren Autor:innen. Die Arbeit nennt 56 Literaturangaben. Gefördert von: NSF, European Union’s Horizon Europe Research and Innovation Program, Ministry of Science, Technological Development and Innovation of Republic of Serbia.
Abstract (Originalsprache)
We study convergence in high-probability of SGD -type methods in non-convex optimization and the presence of heavy-tailed noise. To combat the heavy-tailed noise, a general black-box nonlinear framework is considered, subsuming nonlinearities like sign, clipping, normalization and their smooth counterparts. Our first result shows that nonlinear SGD ( N-SGD ) achieves the rate $\widetilde {\mathcal {O}}(t^{-1/2})$ , where $t$ denotes the time index, for any noise with unbounded moments and a symmetric probability density function (PDF). Crucially, N-SGD has exponentially decaying tails, matching the performance of linear SGD under light-tailed noise. To handle non-symmetric noise, we propose two novel estimators, based on the idea of noise symmetrization. The first, dubbed Symmetrized Gradient Estimator ( SGE ), assumes a noiseless gradient at any reference point is available at the start of training, while the second, dubbed Mini-batch SGE ( MSGE ), uses mini-batches to estimate the noiseless gradient. Combined with the nonlinear framework, we get N-SGE and N-MSGE methods, respectively, both achieving the same convergence rate and exponentially decaying tails as N-SGD , while allowing for non-symmetric noise with unbounded moments and PDF satisfying a mild technical condition, with N-MSGE additionally requiring bounded noise moment of order $p \in (1,2$ ]. Compared to works assuming noise with bounded $p$ -th moment, our results: 1) are based on a novel symmetrization approach; 2) provide a unified framework and relaxed moment conditions; 3) imply an oracle complexity of N-SGD and N-SGE that is strictly better than existing works when $p \lt 2$ , while the complexity of N-MSGE is close to existing works. Compared to works assuming symmetric noise with unbounded moments, we: 1) provide a sharper analysis and improved rates; 2) facilitate state-dependent symmetric noise; 3) extend the strong guarantees to non-symmetric noise.
Förderung
- NSF
- European Union’s Horizon Europe Research and Innovation Program
- Ministry of Science, Technological Development and Innovation of Republic of Serbia
- Science Fund of Republic of Serbia, Project LASCADO
Zitieren
APA
Armacki, A., Bajović, D., Jakovetić, D., & Kar, S. (2026). Sharp High-Probability Rates for Nonlinear SGD Under Heavy-Tailed Noise via Symmetrization. IEEE Transactions on Information Theory, 72(8), 6071-6092. https://doi.org/10.1109/tit.2026.3682577
Vancouver
Armacki A, Bajović D, Jakovetić D, Kar S. Sharp High-Probability Rates for Nonlinear SGD Under Heavy-Tailed Noise via Symmetrization. IEEE Transactions on Information Theory. 2026;72(8):6071-6092. doi:10.1109/tit.2026.3682577
BibTeX
@article{Armacki2026,
author = {Armacki, Aleksandar and Bajović, Dragana and Jakovetić, Dušan and Kar, Soummya},
title = {Sharp High-Probability Rates for Nonlinear SGD Under Heavy-Tailed Noise via Symmetrization},
journal = {IEEE Transactions on Information Theory},
year = {2026},
volume = {72},
number = {8},
pages = {6071--6092},
doi = {10.1109/tit.2026.3682577}
}
EUVIMED