Weak-$L^α$ Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails

Alyona Nekrasova; Makar Sidorov; Savelii Chezhegov; Alexander Gasnikov; Margarita Preobrazhenskaia; Igor Preobrazhensky; Eduard Gorbunov

math.OCOct 20, 2026

Weak- $L^α$ Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails

Authors: Alyona Nekrasova, Makar Sidorov, Savelii Chezhegov, Alexander Gasnikov, Margarita Preobrazhenskaia, Igor Preobrazhensky, Eduard Gorbunov

Organizations: Independent researcher · Yaroslavl State University · Moscow Independent Research Institute of Artificial Intelligence · Innopolis University ·

Abstract

Gradient clipping is a key tool for obtaining high-probability convergence guarantees for stochastic first-order methods under heavy-tailed noise. Existing analyses typically assume a bounded central moment of order $α\in(1,2]$ , which excludes distributions with tails of order $u^{-α}$ at the critical exponent. In this paper, we consider smooth convex optimization under affine heavy-tailed noise, whose scale may grow with the gradient norm. We derive high-probability convergence guarantees for clipped SGD (Clip-SGD) and its accelerated variant Clip-SSTM under a weak- $L^α$ tail condition, which is strictly weaker than the corresponding moment bound. For $1<α<2$ , the clipping bounds have the same powers of the clipping level as in the moment case, and both methods attain the additive stochastic rate $K^{-(α-1)/α}$ . The gradient-dependent noise contributes a faster-decaying term of order $K^{-2(α-1)/α}$ , up to logarithmic factors. At $α=2$ , we characterize the additional logarithmic factor on the Lorentz scale and establish its necessity for the additive error at fixed confidence. We also analyze Clip-SGD with prescribed clipping levels and derive finite-horizon guarantees for reaching a neighborhood determined by the clipping bias. For additive noise, matching lower bounds show that this neighborhood is unavoidable, up to constants and the natural error cap. Numerical experiments with Pareto noise illustrate the theoretical results.

Figures & tables

Method	Result	Noise condition	Oracle calls
Clip-SGD	Sadiev et al., (2023)	$\mathbb{E}\\|\zeta\\|^{\alpha}\leq\sigma^{\alpha}$ , $\alpha\in(1,2]$	$\max\left\{\frac{LR^{2}}{\varepsilon},\left(\frac{\sigma R}{\varepsilon}\right)^{\frac{\alpha}{\alpha-1}}\right\}$
Clip-SGD	Theorem 5.1	Assumption 3.4 or 3.5	$\max\left\{\frac{LR^{2}}{\varepsilon},\left(\frac{\sigma_{0}R}{\varepsilon}\right)^{\frac{\alpha}{\alpha-1}},\left(\frac{\sigma_{1}^{2}LR^{2}}{\varepsilon}\right)^{\frac{\alpha}{2(\alpha-1)}}\right\}$
Clip-SSTM	Gorbunov et al., (2020)	$\mathbb{E}\\|\zeta\\|^{2}\leq\sigma^{2}$	$\max\left\{\sqrt{\frac{LR^{2}}{\varepsilon}},\frac{\sigma^{2}R^{2}}{\varepsilon^{2}}\right\}$
Clip-SSTM	Sadiev et al., (2023)	$\mathbb{E}\\|\zeta\\|^{\alpha}\leq\sigma^{\alpha}$ , $\alpha\in(1,2]$	$\max\left\{\sqrt{\frac{LR^{2}}{\varepsilon}},\left(\frac{\sigma R}{\varepsilon}\right)^{\frac{\alpha}{\alpha-1}}\right\}$
Clip-SSTM	uniform scale (Cor. I.9 )	Assumption 3.4 or 3.5	$\max\left\{\sqrt{\frac{LR^{2}}{\varepsilon}},\left(\frac{\sigma_{0}R}{\varepsilon}\right)^{\frac{\alpha}{\alpha-1}},\left(\frac{\sigma_{1}LR^{2}}{\varepsilon}\right)^{\frac{\alpha}{\alpha-1}}\right\}$
Clip-SSTM	Theorem 5.2	Assumption 3.4 or 3.5	$\max\left\{\sqrt{\frac{LR^{2}}{\varepsilon}},\left(\frac{\sigma_{0}R}{\varepsilon}\right)^{\frac{\alpha}{\alpha-1}},\left(\frac{\sigma_{1}^{2}LR^{2}}{\varepsilon}\right)^{\frac{\alpha}{2(\alpha-1)}}\right\}$

Table 1: Summary of known and new high-probability complexity results for Clip-SGD and Clip-SSTM with the clipping level tuned to the horizon. Complexity is the total number of oracle calls needed for a method to guarantee

f-f^{*}\leq\varepsilon

with probability at least

1-\beta

; the constants depending only on

\alpha

and the logarithmic factors are omitted for simplicity. Notation:

\zeta:=g(x,\xi)-\nabla f(x)

is the noise,

\alpha\in(1,2]

is its tail index and

\sigma

its level;

R\geq\|x^{0}-x^{*}\|

is any upper bound on the initial distance;

\beta\in(0,1)

is the failure probability. Under the affine conditions,

\mathbb{E}\|\zeta\|^{\alpha}\leq\sigma_{0}^{\alpha}+\sigma_{1}^{\alpha}\|\nabla f(x)\|^{\alpha}

(Assumption 3.4 ) or

\mathbb{P}\{\|\zeta\|>u\}\leq(\sigma_{0}^{\alpha}+\sigma_{1}^{\alpha}\|\nabla f(x)\|^{\alpha})u^{-\alpha}

for all

u>0

(Assumption 3.5 ). The error

f-f^{*}

is measured at the averaged iterate

\bar{x}^{K}

for Clip-SGD and at the last iterate

y^{K}

for Clip-SSTM . The results of this paper are highlighted in blue.

Figure 1: Influence of the clipping level under centered asymmetric Pareto noise on

f(x)=x^{2}/2

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Definition	Introduced in
Problem, oracle and method
$\left\langle\cdot,\cdot\right\rangle$ , $\\|\cdot\\|$ , $B_{r}(x)$ , $(a)_{+}$ , $\mathbf{1}_{A}$	Euclidean inner product and norm; closed ball of radius $r$ around $x$ ; positive part; indicator of $A$	Section 3
$f$ , $g(x,\xi)$ , $\mathcal{D}$ , $x^{}$ , $f^{}$	objective, unbiased stochastic oracle with $\xi\sim\mathcal{D}$ ( $\mathbb{E}_{\xi}g(x,\xi)=\nabla f(x)$ on $Q$ ), a minimizer $x^{}$ and $f^{}=f(x^{*})$	( 1 ), Section 3
$x^{0}$ , $R$	starting point and a number $R\geq\\|x^{0}-x^{*}\\|>0$	Section 3
$Q=B_{\rho R}(x^{*})$	ball on which all assumptions are imposed; $\rho=2$ for Clip-SGD , $\rho=3$ for Clip-SSTM	Section 3
$L$	local smoothness constant on $Q$	Assumption 3.1

Appendix

Table 2: Notation.

Result	Level	Criterion	Neighborhood term	Vanishing terms
Koloskova et al., (2023) , Thm. 3.3 (1)	any $\lambda>0$	$\min_{t\leq K}\mathbb{E}\\|\nabla f(x^{t})\\|$	$O(\min\{\sigma_{0},\sigma_{0}^{2}/\lambda\})$	$(LF_{0}\sigma_{0}^{2}/K)^{1/4}$ ${}+\max\{1,\sigma_{0}/\lambda\}\sqrt{LF_{0}/K}$ ${}+LF_{0}/(\lambda K)$
Khah et al., (2026) (2)	$\lambda>4LR$	$\min_{t\leq K}f(x^{t})-f^{*}$	$O(R\sigma_{0}^{\alpha}/\lambda^{\alpha-1})$	$\lambda R/K+R\sqrt{\lambda^{2-\alpha}\sigma_{0}^{\alpha}/K}$
Theorem 5.3	$\lambda\geq 2\sqrt{2}LR$	$f(\bar{x}^{K})-f^{*}$	$120\,b\,R\sigma_{0}^{\alpha}/\lambda^{\alpha-1}$	$\lambda R/K+R\sqrt{\lambda^{2-\alpha}\sigma_{0}^{\alpha}/K}$
Theorem 5.4 (3)	any $\lambda>0$	$\min_{t\leq K}f(x^{t})-f^{*}$	$48\sqrt{2}\,c_{\perp}R\times{}$ $\min\{\sigma_{0},\sigma_{0}^{\alpha}/\lambda^{\alpha-1}\}$	$(LR^{2}+\lambda R)/K$ ${}+R\sqrt{\lambda^{2-\alpha}\sigma_{0}^{\alpha}/K}$ ${}+L^{3}R^{4}/(\lambda^{2}K^{2})$
Koloskova et al., (2023) , Thms. 3.1–3.2 (4)	any $\lambda>0$	lower bound: $\\|\nabla f(\hat{x})\\|$ at the fixed points $\hat{x}$	$\geq\min\{\sigma_{0}/12,\,\sigma_{0}^{2}/(6\lambda)\}$	—
Theorem H.1 (5)	any $\lambda>0$	lower bound: $\mathbb{E}f(\hat{x})-f^{*}$ , $\hat{x}$ an iterate or a deterministic average; deterministic stepsizes	$\geq\frac{1}{48\cdot 4^{\alpha}}\times{}$ $\min\{R\sigma_{0}^{\alpha}/\lambda^{\alpha-1},R\sigma_{0},LR^{2}\}$	—

Appendix

Table 3: Bounds for Clip-SGD with a prescribed clipping level under additive noise. Our results are highlighted in light blue.

Figure 2: Mean error of the averaged iterate on

f(x)=x^{2}/2

under symmetric Pareto noise

Figure 3: Mean objective gap of the averaged iterate for ridge regression on the Diabetes dataset with asymmetric Pareto noise along the eigenvector of the smallest Hessian eigenvalue

Figure 4: Mean averaged-iterate gap for Clip-SGD on the smooth convex chain with vanishing curvature, under the full horizon-dependent prescription from Theorem F.1

Gradient Clipping

Gradient clipping limits unusually large updates to stabilize optimization, reduce sensitivity to heavy-tailed noise, and support private or distributed training.

See all 22 papers

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

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

Polyak-Ruppert Averaging Stochastic Optimization Gradient Clipping Stochastic Gradient Descent Heavy-Tailed Stochastic Optimization

Ask PDF

Oct 24, 2026

The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise

Training is often stopped at a data-dependent time, so guarantees for the last iterate must hold at all times simultaneously. We determine the optimal time-uniform rate for the last iterate of clipped SGD on smooth convex objectives under heavy-tailed noise with a bounded central

p

th moment,

1<p\le2

. A schedule without horizon or confidence inputs attains

\tilde O(t^{-β_p})

at all times, with

β_p=2(p-1)/(3p-1)

, also almost surely, and no rule that steps along the stochastic gradient at its current iterate attains

\tilde O(t^{-r})

for any

r>β_p

, even with adaptive step sizes and thresholds. This rate lies between the optimal rate

O(T^{-α_p})

for a known horizon

T

α_p=(p-1)/p

, and the previous time-uniform rate

\tilde O(t^{-2(p-1)/(3p)})

(Chezhegov et al., ICLR 2026); under finite variance, the exponents are

1/2

2/5

, and

1/3

. Their conjecture that a better schedule reaches the optimal rate thus holds with a known horizon (Liu; Jiang et al.) but fails without one. Querying gradients at the running average attains

\tilde O(t^{-α_p})

at all times, whereas heavy-ball momentum with geometric forgetting and polynomially bounded steps cannot improve on

β_p

Yuxing Peng, Zhiqing Tang, Weijia Jia

Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, China · Institute of Artificial Intelligence and Future Networks, Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, China · Guangdong Key Lab of AI and Multi-Modal Data Processing, Beijing Normal-Hong Kong Baptist University, Zhuhai 519087, China

Last-Iterate Convergence Convergence Analysis Heavy-Tailed Stochastic Optimization Stochastic Gradient Descent Learning Rate Scheduling

Ask PDF

Abstract

Gradient Clipping

Explore similar work

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

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

The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise