# Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and H"older Smoothness

arXiv: https://arxiv.org/abs/2609.12785 · HTML: https://mlsanity.com/paper/2609.12785/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 20 references that are in the map.
- First posted on arXiv 11 Sep 2026.

## Builds on (most cited first, 16 of 16)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping](https://mlsanity.com/paper/2412.19529/) (2024)
- [Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variance](https://mlsanity.com/paper/2102.10346/) (2021)
- [High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noise](https://mlsanity.com/paper/2006.05610/) (2020)
- [Differentially Private SGD with Non-Smooth Losses](https://mlsanity.com/paper/2101.08925/) (2021)
- [Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailed](https://mlsanity.com/paper/2406.04443/) (2024)
- [Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Acceleration](https://mlsanity.com/paper/2410.16561/) (2024)
- [Stochastic Gradient Descent on Nonconvex Functions with General Noise Models](https://mlsanity.com/paper/2104.00423/) (2021)
- [Regularized Gradient Clipping Provably Trains Wide and Deep Neural Networks](https://mlsanity.com/paper/2404.08624/) (2024)
- [Adaptive Heavy-Tailed Stochastic Gradient Descent](https://mlsanity.com/paper/2508.21353/) (2025)
- [Convergence of Gradient Algorithms for Nonconvex C^{1+alpha} Cost Functions](https://mlsanity.com/paper/2012.00628/) (2020)

## Abstract (arXiv)

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"older 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"older 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.