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

Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness
Sep 11, 2026Misbah Uz Zaman, Anirbit MukherjeeGradient Clipping Nonconvex Stochastic Optimization
Department of Mathematics and Statistics Indian Institute of Science Education and Research Kolkata · Department of Computer Science The University of Manchester
Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise
Sep 26, 2026Alexandra Suvorikova, Egor Gladin, Darina Dvinskikh +5Polyak-Ruppert Averaging Stochastic Optimization
Independent Researcher · HSE University · MBZUAI +3
The Cost of an Unknown Horizon for the Last Iterate of Clipped SGD under Heavy-Tailed Noise
Oct 24, 2026Yuxing Peng, Zhiqing Tang, Weijia JiaLast-Iterate Convergence Convergence Analysis
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

Sep 11, 2026J/K move · Enter open · S save

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

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

Open paper AskPDF 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ö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.

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