Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness
Abstract
Classical convergence guarantees for stochastic gradient methods typically assume Lipschitz-smooth objectives and finite-variance gradient noise, both frequently violated in practice. In contrast, we study nonconvex stochastic optimization under the joint relaxation of these assumptions: objectives with (L,s)-Hölder continuous gradients, s∈(0,1], and gradient noise satisfying only a bounded α-th moment condition for α∈(1,2]. We establish three convergence results. Firstly, that standard SGD converges at rate O(T−s/(1+s)) whenever α≥1+s, extending the classical nonconvex SGD rate to heavy-tailed noise and Hölder smoothness simultaneously. Secondly, we analyze δ-regularized gradient clipping (δ-GClip), a provable trainer of wide and deep nets, and establish a stationarity rate of O(T−2s(α−1)/[(1+s)(2α−1)]) under the same condition. Thirdly, we analyze standard gradient clipping (G-Clip) and show that it recovers the above rate for α≥1+s while in the very heavy-tailed regime α<1+s, it has a convergence rate O(T−2s(α−1)/[(α−1)+s(2α−1)]) --- the first convergence guarantee in this regime for any stochastic gradient based method.
Related
- Last-Iterate Convergence of Stochastic Gradient Methods for Unbounded Problems
- Almost Sure Convergence Analysis of Stochastic Gradient Methods with Clipping and Additive Noise
- Accelerated Stochastic Method under (H0,H1)-Smoothness and Heavy-Tailed Noise
- Last-Iterate Convergence Rate of Normalized Gradient Descent under Hölder Smoothness
- Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping
BibTeX
@misc{zaman2026convergence,
title = {{Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness}},
author = {Misbah Uz Zaman and Anirbit Mukherjee},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12785},
eprint = {2609.12785},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12785},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness
AU - Misbah Uz Zaman
AU - Anirbit Mukherjee
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.12785
UR - https://arxiv.org/abs/2609.12785
AB - Classical convergence guarantees for stochastic gradient methods typically assume Lipschitz-smooth objectives and finite-variance gradient noise, both frequently violated in practice. In contrast, we study nonconvex stochastic optimization under the joint relaxation of these assumptions: objectives with (L,s)-Hölder continuous gradients, s∈(0,1], and gradient noise satisfying only a bounded α-th moment condition for α∈(1,2]. We establish three convergence results. Firstly, that standard SGD converges at rate O(T^−s/(1+s)) whenever α≥1+s, extending the classical nonconvex SGD rate to heavy-tailed noise and Hölder smoothness simultaneously. Secondly, we analyze δ-regularized gradient clipping (δ-GClip), a provable trainer of wide and deep nets, and establish a stationarity rate of O(T^−2s(α−1)/[(1+s)(2α−1)]) under the same condition. Thirdly, we analyze standard gradient clipping (G-Clip) and show that it recovers the above rate for α≥1+s while in the very heavy-tailed regime α<1+s, it has a convergence rate O(T^−2s(α−1)/[(α−1)+s(2α−1)]) --- the first convergence guarantee in this regime for any stochastic gradient based method.
ER -