Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Holder Smoothness

arXiv:2609.12785v1 Announce Type: new 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)-Holder continuous gradients, sin(0,1], and gradient noise satisfying only a bounded alpha-th moment condition for alphain(1,2]. We establish three convergence results. Firstly, that standard SGD converges at rate O(T^{-s/(1+s)}) whenever alphage1+s, extending the classical nonconvex SGD rate to heavy-tailed noise and Holder smoothness simultaneously. Secondly, we analyze elta-regularized gradient clipping (elta-GClip), a provable trainer of wide and deep nets, and establish a stationarity rate of O(T^{-2s(alpha-1)/[(1+s)(2alpha-1)]}) under the same condition. Thirdly, we analyze standard gradient clipping (G-Clip) and show that it recovers the above rate for alphage1+s while in the very heavy-tailed regime alpha<1+s, it has a convergence rate O(T^{-2s(alpha-1)/[(alpha-1)+s(2alpha-1)]}) --- the first convergence guarantee in this regime for any stochastic gradient based method.

Related

• In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise
• On the Interaction of Batch Noise, Adaptivity, and Compression, under (L_0,L_1)-Smoothness: An SDE Approach
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and (L_0, L_1)-Smoothness
• Learning from the Descent Direction: Adaptive Gradient Descent under One-Sided Holder Regularity

Source: arXiv cs.LG | 2026-09-14