High-Probability Guarantees for SGD under $β$-Heavy-Tailed Gradient Noise

Qijun Tong; Masahiro Ikeda; Ryota Kawasumi

stat.MLSep 26, 2026

High-Probability Guarantees for SGD under $β$ -Heavy-Tailed Gradient Noise

Authors: Qijun Tong, Masahiro Ikeda, Ryota Kawasumi

Organizations: The University of Electro-Communications · The University of Osaka · Gunma University

Abstract

Stochastic gradient descent (SGD) is widely used to train machine learning models, but subsampling the training data introduces noise into its updates. The strength and applicability of high-probability guarantees therefore depend critically on how the tails of gradient noise are modeled. Reports of heavy-tailed gradient noise in deep learning motivate relaxing the bounded-noise and sub-Gaussian assumptions commonly used in high-probability analyses of SGD. We use Young functions from Orlicz space theory to describe noise tails in a common framework. We model SGD gradient noise by adopting a Young function that preserves the finiteness of all polynomial moments while allowing tails heavier than sub-Weibull, including lognormal distributions. The resulting class is called $β$ -heavy-tailed, with $β$ controlling the tail heaviness. We establish concentration inequalities for $β$ -heavy-tailed noise and combine them with a uniform bound on the difference between empirical and population gradients along the SGD trajectory to obtain high-probability bounds on optimization and population-risk stationarity for smooth nonconvex losses under trajectory assumptions. The bounds are not restricted to a particular learning-rate decay rule and make explicit the effects of noise tails and learning-rate schedules. Under the Polyak-Łojasiewicz condition, we bound the risk at the last iterate. We also analyze SGD with gradient clipping under the $β$ -heavy-tailed noise model.

Figures & tables

Schedule	$\eta_{t}$	$\sum_{t\in[T]}\eta_{t}$	$\sum_{t\in[T]}\eta_{t}^{2}$
$1/t$ (Prop. E.1 )	$\dfrac{\eta_{0}}{t}$	$\eta_{0}(\log T+\mathcal{O}(1))$	$\mathcal{O}(\eta_{0}^{2})$
$1/\sqrt{t}$ (Prop. E.2 )	$\dfrac{\eta_{0}}{\sqrt{t}}$	$\eta_{0}(2\sqrt{T}+\mathcal{O}(1))$	$\eta_{0}^{2}(\log T+\mathcal{O}(1))$
Cosine (Prop. E.3 )	$\dfrac{\eta_{0}}{2}\left(1+\cos\dfrac{\pi t}{T}\right)$	$\dfrac{\eta_{0}}{2}(T-1)$	$\dfrac{\eta_{0}^{2}}{8}(3T-4)$

Table 1: Step-size sums for the three schedules.

Explore similar work

Mar 15, 2026

High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise

We present the first uniform-in-time high-probability bound for SGD under the PL condition, where the gradient noise contains both Markovian and martingale difference components. This significantly broadens the scope of finite-time guarantees, as the PL condition arises in many machine learning and deep learning models while Markovian noise naturally arises in decentralized optimization and online system identification problems. We further allow the magnitude of noise to grow with the function value, enabling the analysis of many practical sampling strategies. In addition to the high-probability guarantee, we establish a matching

1/k

decay rate for the expected suboptimality. Our proof technique relies on the Poisson equation to handle the Markovian noise and a probabilistic induction argument to address the lack of almost-sure bounds on the objective. Finally, we demonstrate the applicability of our framework by analyzing three practical optimization problems: token-based decentralized linear regression, supervised learning with subsampling for privacy amplification, and online system identification.

Avik Kar, Siddharth Chandak, Rahul Singh +3

Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India. · Department of Electrical Engineering, Stanford University, Stanford, CA, USA. · CMAP, CNRS, École polytechnique, Institut Polytechnique ´de Paris, Palaiseau, France.

Optimization Convergence Analysis Stochastic Optimization Convergence Stochastic Gradient Descent

Ask PDF

Sep 26, 2026

Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise

Gradient clipping is widely used to stabilize training, but it need not improve the statistical accuracy of averaged SGD, even under heavy-tailed noise. We derive a finite-sample comparison of clipped and unclipped Polyak-Ruppert averaged SGD under finite conditional

p

-th moments,

p\ge2

. Our main result gives explicit accuracy and confidence conditions under which, for

p>2

, the Gaussian term dominates the unclipped deviation bound, so clipping need not improve its leading order. By balancing clipping bias and concentration, we obtain a bound in which the heavy-tail correction depends logarithmically rather than polynomially on the inverse failure probability. At

p=2

, this improves the confidence dependence of the leading bound. We establish sharpness of the unclipped heavy-tail term through an exact one-dimensional quadratic recursion and extend the comparison to projected convex SGD. We also prove concrete costs of clipping: every fixed finite threshold increases asymptotic variance on a scalar Gaussian quadratic, while whole-gradient clipping can shift the limiting point under asymmetric noise.

Alexandra Suvorikova, Egor Gladin, Darina Dvinskikh +5

Independent Researcher · HSE University · MBZUAI +3

Stochastic Optimization Gradient Clipping Stochastic Gradient Descent Heavy-Tailed Stochastic Optimization

Ask PDF

Sep 11, 2026

Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness

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\in(0,1]

, and gradient noise satisfying only a bounded

α

-th moment condition for

α\in(1,2]

. We establish three convergence results. Firstly, that standard SGD converges at rate

O(T^{-s/(1+s)})

whenever

α\ge1+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

α\ge1+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.

Misbah Uz Zaman, Anirbit Mukherjee

Department of Mathematics and Statistics Indian Institute of Science Education and Research Kolkata · Department of Computer Science The University of Manchester

Gradient Clipping Nonconvex Stochastic Optimization Heavy-Tailed Stochastic Optimization Stochastic Gradient Descent

Ask PDF