Clipped Gradient Methods for Nonsmooth Convex Optimization under Heavy-Tailed Noise: A Refined Analysis
Authors: Zijian Liu
Venue: ICLR 2026 Poster (2026)
Keywords: Convex Optimization
Heavy-Tailed Noise
Gradient Clipping
Primary area: optimization

Abstract: Optimization under heavy-tailed noise has become popular recently, since it better fits many modern machine learning tasks, as captured by empirical observations. Concretely, instead of a finite second moment on gradient noise, a bounded $\mathfrak{p}$-th moment where $\mathfrak{p}\in(1,2]$ has been recognized to be more realistic (say being upper bounded by $\sigma_{\mathfrak{l}}^{\mathfrak{p}}$ for some $\sigma_{\mathfrak{l}}\geq0$). A simple yet effective operation, gradient clipping, is known to handle this new challenge successfully. Specifically, Clipped Stochastic Gradient Descent (Clipped SGD) guarantees a high-probability rate $\mathcal{O}(\sigma_{\mathfrak{l}}\ln(1/\delta)T^{\frac{1}{\mathfrak{p}}-1})$ (resp. $\mathcal{O}(\sigma_{\mathfrak{l}}^{2}\ln^{2}(1/\delta)T^{\frac{2}{\mathfrak{p}}-2})$) for nonsmooth convex (resp. strongly convex) problems, where $\delta\in(0,1]$ is the failure probability and $T\in\mathbb{N}$ is the time horizon. In this work, we provide a refined analysis for Clipped SGD and offer two faster rates, $\mathcal{O}(\sigma_{\mathfrak{l}}d_{\mathrm{eff}}^{-\frac{1}{2\mathfrak{p}}}\ln^{1-\frac{1}{\mathfrak{p}}}(1/\delta)T^{\frac{1}{\mathfrak{p}}-1})$ and $\mathcal{O}(\sigma_{\mathfrak{l}}^{2}d_{\mathrm{eff}}^{-\frac{1}{\mathfrak{p}}}\ln^{2-\frac{2}{\mathfrak{p}}}(1/\delta)T^{\frac{2}{\mathfrak{p}}-2})$, than the aforementioned best results, where $d_{\mathrm{eff}}\geq1$ is a quantity we call the generalized effective dimension. Our analysis improves upon the existing approach in two respects: better utilization of Freedman's inequality and finer bounds for clipping error under heavy-tailed noise. In addition, we extend the refined analysis to convergence in expectation and obtain new rates that break the known lower bounds. Lastly, to complement the study, we establish new lower bounds for both high-probability and in-expectation convergence. Notably, the in-expectation lower bounds match our new upper bounds, indicating the optimality of our refined analysis for convergence in expectation.

Published as a conference paper at ICLR 2026
CLIPPED GRADIENT METHODS FOR NONSMOOTH CONVEX OPTIMIZATION UNDER HEAVY-TAILED
NOISE: A REFINED ANALYSIS"
Zijian Liu
Stern School of Bussiness, New York University z
ABSTRACT
Optimization under heavy-tailed noise has become popular recently, since it bet- ter fits many modern machine learning tasks, as captured by empirical observa- tions. Concretely, instead of a finite second moment on gradient noise, bounded p-th moment where p [1, has been recogmized
be more realistic (say be- ing upper bounded by of for some ot 2 0). A simple yet effective operation, gradient clipping. known to handle this new challenge successfully. Specif- ically, Clipped Stochastic Gradient Descent (Clipped SGD) guarantees a high- probability rate Oor In(1/8yTb-) (resp. O In In2
(1/8)T² =)) for nonsmooth convex (resp. strongly convex) problems, where E (0, 1] is the failure proba- bility and T N the time horizon. In this work, we provide refined anal-
ysis for Clipped SGD and offer two faster rates, Olard In (1/8)r+
and Olofd off In2 (1/8)Tē-3) than the aforementioned best results, where detf 2 a quantity we call the generalized effective dimension. Our analysis improves upon the existing approach in two respects: better utilization of Freed- man's 's inequality and finer bounds for clipping error under heavy-tailed noise. addition, extend the refined analysis convergence in expectation and obtain new rates that break the known lower bounds. Lastly, to complement the study, we establish lower bounds for both high-probability and In-expectation con- vergence. Notably, the in-expectation lower bounds match our new upper bounds, indicating the optimality of our refined analysis for convergence in expectation.
INTRODUCTION
In first-order methods for stochastic optimization, one only query an unbiased though noisy gradient and then implement a gradient descent step, which is known as Stochastic Gradient De- scent (SGD) (Robbins & Monro [951). Under the widely assumed finite variance condition, i.e., the gradient noise has a finite second moment, the in-expectation convergence of SGD has been substantially studied (Bottou al. 2018 Lan 2020).
However, many recent empirical observations suggest that the finite variance assumption might be strong and could be violated in different tasks (Simsekli al.) 2019 Zhang al. 2020 Zhou
et al. 2020 Garg el al. 2021 Gurbuzbalaban et al. [2021] Hodgkinson & Mahoney] [022] || Battash al. 2024p. Instead, bounded p-th moment condition where p E (1, 2] (say with an upper bound of for some 2 0) better fits modern machine learning, which is named heavy-tailed noise, Fac- ing this new challenge, SGD has been proved to exhibit undesirable behaviors (Zhang et al., 2020) Sadiev et al. 2023). Therefore, an algorithmic change is necessary. A simple yet effective operation, gradient clipping, known to handle this harder situation successfully with both favorable practi- cal performance and provable theoretical guarantees (see, e.g., Pascanu et al. (2013); Zhang et al. (2020)). The clipping mechanism replaces the stochastic gradient ge in every iterate of SGD with
* *This a self-contained conference version full paper available at httts:://aa/t www.riiwwooooooooooo abs/
1.... 2512.23173 Compared to the full version, we omit the formal statements of lower bounds and their proofs.
"This refers the difference hetween the stochastic estimate and the true gradient.

---

Published as a conference paper at ICLR 2026
its truncated counterpart clip,, (gt), resulting method known Clipped SGD, where Ty is called the clipping threshold and clip, (g) _ min (1,7//lsl) g is the clipping function.
Specifically, for nonsmooth convex (resp_ strongly convex) optimization, Clipped SGD achieves a high- beeh--rbbbbility rate Oo In(1/8)r -1
(resp. Oo In (1/0)2 (Liu & Zhou 2023). where ō E (0, 1] is the failure probability and T E N is the time horizon. These two results seem to be optimal as they match the existing in-expectation lower bounds (Nemirovski & Yudin 1983 Vural
et al. 2022 Zhang et al. 2020), if viewing the poly(In(1/5)) term as a constant. However, a recent
advance (Das et al. 2024) established a better rate ( v /Im(n(()/85/TT) for general convex problems when p 2, where S deff S is known as the effective dimension (also named intrinsic dimension (Tropp 2013) ) and d is the true dimension. This reveals that the in-expectation lower bound does not necessarily apply to the term containing poly(In(1/6)). More importantly, such a result hints that a general improvement may exist for all p E (1,
This work confirms that a general improvement does exist by providing a refined analysis for Clipped SGD. Concretely, we offer two faster rates, O(ord off In- 1-1 (1/6)T* -1) for general convex prob-
lems with a known T and Of known T, improved upon the aforementioned best results, where S detf S ((d) is a quantity that we call the generalized effective dimension Moreover, we devise an algorithmic variant of Clipped SGD named Stabilized Clipped SGD that achieves the same rate for convex objectives listed above in an anytime fashion, i.c., no extra poly (In T) factor even without T'
off In2 (1/8)T for strongly convex problems with an un-
We highlight that our analysis improves upon the existing approach in two respects: 1. better way to apply Freedman's 's inequality when analyzing Clipped SGD, which leads to provably tighter concentration. Remarkably, our approach is fairly simple in contrast to the previous complex iterative refinement strategy (Das et al. 2024). 2. We establish finer bounds for clipping error under heavy-tailed noise, which is another essential ingredient in the analysis for Clipped SGD when the noise has a heavy tail. We believe both of these new insights could be of independent interest and potentially useful for future research.
We observe a
Furthermore, equipped with the new finer bounds for clipping error, we extend the analysis in- expectation convergence and obtain two new rates, (ardd 2-p T -1) for general convex objectives and Ofoid 2-p T -2) for strongly convex problems. Notably, once p < these two rates are both faster by a poly(1/datt factor than the known optimal lower bounds (arT and 2o0T 2
in the corresponding setting (Nemirovski & Yudin 1983 Vural et al.. 2022 Zhang et al. 2020).
Lastly, to complement the study, we establish new lower bounds for both bigh-probaiility and in- expectation convergence. Notably, the in-expectation lower bounds match our new upper bounds, indicating the optimality of our refined analysis for convergence in expectation.
1.1 RELATED WORK
We review the literature that studies nonsmooth (strongly) convex optimization under heavy-tailed noise. For other different settings, e.g., smooth (strongly) convex smooth/nonsmoott nonconvex
problems under heavy-tailed noise, the interested reader could refer to, for example. Nazin et al.
2019): Davis& & Drusvyatskiy (2020) Gorbunov et al. (2020) Mai & Johansson (2021) y Cutkosky
& Mehta (202)) Wang et al. (222)) ): Tsai et al. (2022): Holland (2022); Jakovetić et al. (2023);
Sadiev et al. (2023) Liu et al. (2023); Nguyen et al. (2023); Puchkin et al. (2024): Gorbunov et al.
2024b): Liu et al. (2024): Armacki et al. (2025): Hübler et al. (2025) Liu & Zhou (2025) Sun et al. 2025), for recent progress.
High-probability rates. p 2, Gorbunov et al. (2024a) proves the first (Tor//((T/)//TT (resp. In(T/8)TT high-probability rate for nonsmooth convex (resp. strongly convex) prob-
WWhen stating rates in this section, we only keep the dominant term when T and 5 + 0 for simplicity. We use the same notation to denote the effective dimension and the generalized version proposed by us, since our new quantity can recover the previous one when p = 2. See discussion after (1) for details. "To clarify, "the same rate" refers to the same lower-order term. The full bound is sligtlly different.
2

---

Published as a conference paper at ICLR 2026
lems under standard assumptions. If additionally assuming bounded domain, improved rate ((olyI((1/0) for convex objectives is obtained by Parletta et al. (2024). Still for convex problems, Das al. (2024) recently gives the first refined bound (a v //n()((T//)/TT)) but additionally requiring 7 (([In(In d)), where detr (resp. d) is the effective (resp. true) dimension, satisfying S deff S d. For general p (1, 21. Zhang & Cutkosky (2022) studies the harder online convex optimization, whose result implies a rate ((apoly(In) (In)))y(()())))))))) -)) )) for heavy-tailed con- vex optimization, Later on. Liu & Zhou 2023) establishes two bounds, In(1/8T)) and Oaa (1/5)TT))) for convex and strongly convex problems, respectively. These two rates are the best-known results for general p E [1 and have been recognized as optimal since they match the in-expectation lower bounds (see below), if viewing the poly(In(1/6) term as a constant.
In-expectation rates. Note that the in-expectation rates for p are not worth much attention as they are standard results (Bottou et al. 2018 Lan 2020). As for general p E (1,2), many existing
works prove the rates O and
T 2) (Zhang al.
2020:
Vural et al. 2022 Liu &
Zhou 2023 2024
Parletta et al. 2025
Fatkhullin et al. 2025 Liu
2025
Lower bounds. The high-probability lower bounds are not fully explored in the literature. To the best of our knowledge, there are only few results for the general convex case and no lower bounds for the strongly convex case. Therefore, the following discussion is only for convex problems. For p 2. Carmon & Hinder (2024) shows a lower bound (( /I((//))/T However, it is only proved for d' d'= [or at most d d= 4). As such, it cannot reveal useful information for the case that d should also be viewed as parameter (if more accurately, d.tr). In other words. does not contradict our new refined upper bound. For general E (1, 2). Raginsky & Rakhlin (2009) is the only work that we are aware of. However, as far as we can check, only the time horizon i' in the right order of Q(T ))). For other parameters, they are either hidden or not tight.
Next, we summarize the in-expectation lower bounds. For convex problems, it is known that any first-order method cannot do better than [o -1) (Nemirovski & Yudin 1983 Vural et al. 2022).
If strong convexity additionally holds, Zhang et al. (220)) establishes the lower bound MoFTT ?).
2 PRELIMINARY
Notation. N is the set of natural numbers (excluding 0). We denote by [T] -
{1, T VT E N. (;.)) represents the standard Euclidean inner product. ||x[] is the Euclidean norm of the vector x and |X| is the operator norm of the matrix X. Tr(X) is the trace of a square matrix X. gd-1 stands for the unit sphere in Idd, Given a convex function Rd + R. Vh(x) denotes an arbitrary element in (x) where (x) is the subgradient set of h at sgn(x) is the sign function with sgn(0)= 0.
We study the composite optimization problem in the form of inf (x) A f(x) - r(x),
XEX
where X C Rdd is a nonempty closed convex set. Our analysis relies on the following assumptions.
Assumption 1. There exists x, E X such that F. & F(x.) infxex Fx).
Assumption 2. Both f Rd - R and r: Red + IR. are convex. In addition, is p-strongly convex on X for some μ 2 0, i.e., r(x) 2 r(y) + (Vr(y), - y) + 1| yl1 Vx.y E X.
Assumption 3. f is G-Lipschitz on X, ie., [[ S G
The above assumptions are standard in the literature (Bottou et al. 2018 Nesterov et al. 2018 Lan 2020). Next, we consider fine lne-grained heavy-tailed noise assumption, the key to obtaining renned convergence for Clipped SGD.
Assumption 4. There exists function g: x = - Rd and probability distribution ID on such that Eg-D [g( xx { = fx)), Vx E X. In addition, for some p E (1,2), we have
EEDD [I(e, g(x,)) V (x)) < <o EEND [||g(x E vf(x) Sof, XxEX,ess" gd-1
where 0g and a are two constants satisfying 0 20 S Sa S vnd/2o..
3

---

Published as a conference paper at ICLR 2026
Remark 1. In the remaining paper, if the context is clear, we drop the subseript I in Eg to case the notation. Moreover, d(x, <) _ g(x. {) V fx) denotes the error in estimating the gradient.
Remark It noteworthy that Assumption actually implicitly exists prior works for heavy- tailed stochastic optimization, since Cauchy-Schwarr Schwarz inequality gives us
E [lke, d(x, <)M*] - E |||/|| [x 1) = EE [[] e)Il") , Vx E e S
In other words, once the condition E |||d(x, [P] I of. Vx E X is assumed like in prior works, there must exist real number 0 S S o such that E [I(e, d(x, <)>*] S Sog Vx E X, e Sd-1 Remark 3. The reason we can assume - / md/2o, is that E [|] [)1" < (md/2) of holds provided E [I(e, {))* o., Ve E Sd-1, due to Lemma 4.1 in Cherapanamjeri et al. 2022).
Now define the following quantity named generalized effective dimension (where we use the convention 0 = 0/0).
dart of of/0? E [0) U [1, md/2] (d)), in which der 0 if and only if at 0, 0, i.e., the noiseless case. As discussed later, this definition recovers the effective dimension used in Das et al. (2024) when =
(1)
To better understand Assumption 4 we first take p 2. Note that finite second moment of c E) implies the covariance matrix Σ(x) - [d(x, c)d (x, <)] Rddd is well defined. As such, we can interpret at and 0g as of = supxex Tr(E(x)) and o = supxex [[(x]]
particular,
(x)) < Σ, Vx E X holds for some positive semidefinite E as assumed in Das et al. (2024), then one can directly take of (r()) and oī = |اا||| which also recovers the effective dimension defined
as Tr(2)/EE)| in Das et al. 2022
For general p E (1, 2]. as discussed in Remark one can view Assumption 4 as a finer version the classical heavy-tailed noise condition, the latter omits the existence of dg,. Therefore, Assumption 4 describes the behavior of noise more precisely. Such refinement was only introduced to the classical mean estimation problem (Cherapanamjeri et al.) (2022) far
know, and hence is optimization literature. In Appendix/A. A| we provide more discussions on how large dest can be across different settings.
the
CLIPPED STOCHASTIC GRADIENT DESCENT
Algorithm Clipped Stochastic Gradient Descent (Clipped SGD)
Input: initial point X1 X, stepsize m 0, clipping threshold n. 0
for t = to T do
gi clip., (g:) where g: g(x,, E and & D is sampled independently from the history X srgminxexr(x + (gf x) + |x-x.112
2n
end for
We present the main method studied in this work, Clipped Stochastic Gradient Descent (Clipped SGD), in Algorithm []] Strictly speaking, the algorithm should be called Proximal Clipped SGD it contains proximal update step. However, we drop the word "Proximal" for simplicity. We remark that Clipped SGD with a proximal step has not been fully studied yet and is different from the Prox-CIl Clwpped---piiii SGD-Shift method introduced in Gorbunov et al.) (2024b), the only work considering composite optimization under heavy-tailed noise that we are aware of.
In comparison to the classical Proximal SGD, Algorithm T oonly contains an extra clipping operation on the stochastic gradient. As pointed out in prior works (e.g.. (adiev et al. (2023)). the additional clipping step is the key to proving the high- gigobprbbability convergence.
REFINED HIGH-PROBABILLTY RATES
In this section, will establish refined high-probabilityy convergence results for Clipped SGD. To simplify the notation in the upcoming theorems, denote by D a ||x, X1
|| the distance between
4

---

Published as a conference paper at ICLR 2026
the optimal solution and the initial point. Moreover, given ò (0, 1], introduce the quantity
0
0
7.
min
In
1
which is an important value used in the clipping threshold. be equivalently written into
Recall that deft =of of/03. then T, can
3 { (Vaat in g datt 1p <
= 01/pp!
where
x+ - max
(3)
4.1 GENERAL CONVEX CASE
Ei= X in the following denotes the average iterate after T steps. To clarify, T is assumed to be known in advance in this subsection. Though Clipped SGD can provably handle an unknown time horizon T, it is well- known to incur extra poly(In T') factors (Liu & Zhou, 2023). To deal with this issue, propose a variant of Clipped SGD named Stabilized Clipped SGD Appendix C which incorporates the stabilization trick introduced by Fang al. (2022). As example, Theorem [1 in Appendix E shows that Stabilized Clipped SGD converges at an almost identical rate to Theorem below, but in an anytime fashion without incurring any poly (In 7') factor.
We start from the general convex case (i.e., 1 = Assumption 2p. evx
T
Theorem 1. Under Assumptions
(with 0). and 4 for any T E N and â E (0, 1], setting = T/. Ft = max {2G, T vt E [T] where 77 is a properly picked stepsize (explicated guarantees that with probability at least 1 6,
7
in Theorem 10p, then Clipped SGD (Algorithm 7
F F( F. converges at the rate of
( t GD T
G +GDD (0
2-1 2-2 + to 01
1 1-2
In
1
VT
T²-
where ip S up+ is constant (explicated in Theorem 10) and equals ip+ when T S (f p.).
To better understand Theorem we first consider a special case of p = (i.e., the classical finite variance condition) and obtain rate being at most (1) (n( Vo,a, In()))
vT
In comparison, the previous best nigh-probabiliin bound in the finite variance setting proved by Das CT + (Vaat 2) In( JGD (or
ct al. (2024)
but under an extra
T
/T
requirement T 2 (Inn(In d)), where Cr is term in the order of 2) but will blow up too when the variance approaches As one can see, even in this special case, our result immediately improves upon Das al. (2024) from the following three folds: 1. Our theory works for any time horizon E N. 2. Our bound is strictly better than theirs by shaving off many redundant terms. Especially, the dependence on is only (n(1/)) in contrast to their In (IIn /8)). 3. Our rate will not blow up when σ - (equivalently, a, + and instead recover the standard O(GD/VT) result for deterministic nonsmooth convex optimization Nesterov et al. 2018).
GD VT
+ oiDin 7
Next, the prior best result for p E (1,2) is O
(Liu Zhou 2023), whose
dominant term is Dn
T becomes larger. In comparison, using def 0f.03. the lower-order term in Theorem can be written as (dd + d In--3 (1/8)) Therefore, Theorem
I
improves upon Liu & Zhou 2023) for large T by factor of
p 2
off
+
78 cff
In
θ
(4)
In
8
d
2F
In
deff
In
Remark Especially, when desf = (d)), p could be in the order @(poly(1/4) In(1/6))). We provide example in Appendix A showing that detf (dd) is attainable.
5

---

Published as a conference paper at ICLR 2026
For general T N. note that O ln + last two terms) in Theorem 1 are always smaller
than the rate of Liu & Zhou 2023) due to 0s S or and Olo -) < O(a G) by Young's inequality. Theretore, we only need to pay attention to the redundant term O DD/T). Observe that a critical time could be T. = ( = (dett In (1/6) + Let 1 [p < 2] Once 2 T., we can ignore (gGGD/T) as it is at most O(GD/VT) now. It is currently unknown whether the term OgG (T) is inevitable or can be removed to obtain a better bound than Liu & Zhou (2033 for any T E N. We remark that similar additional terms also appear in the refined rate for p = 2 by Das
al. (2024) as discussed before.
4.2 STRONGLY CONVEX CASE
We now move to the strongly convex case (i.e., / > 0 in Assumption Dx L (++4))+++)) (((((+4)((-5)) in the following denotes the weighted average iterate after T steps. Unlike the general convex case, do not need to know T in advance to remove the extra plly(In T) factor. Theorem 2. Under Assumptions
T+1
7 (with > 0), 3 and for any T E N and E (0, 1J, setting Vt E [T], then Clipped SGD (Algorithm guarantees that with probability at least 8, both F ((x#+)
T Ta = max 2G, T,tP
F. and u ||
x.1?² converge at the rate of
$ --2
O HD2
(sp2 ln2 G
(of + ot o le + os 11
+
In
T +
pTz
PT
nT
where yp S. (px is the same constant as in Theorem and equals sp when T
Ω
Remark The problem studied in prior works (e.g.. Liu & Zhou (2023 Gorbunov al. (2024a)
considers strongly convex and Lipschitz f with r = 0, which seems different from our assumption of strongly convex r. However, simple reduction can convert their instance to fit our setting. Moreover, the first term O(uD2/T9 in Theorem [ can also be omitted in that case (as we will do so the following discussion). We refer the interested reader to Appendix for the reduction and why the term ((DD2/TT) can be ignored.
G In2 (oi+op Piln? pf
To save space, we only compare with the rate O
Liu & Zhou
"T" b
2023 for general p E (1, For the special case p 2, the rate of Liu & Zhou (2023) is almost identical to the bound of Gorbunov et al. (2024a); moreover, as far as we know, no improved result
like Das al. (2024) has been obtained give a better bound for the term containing poly(In(1/o)
Similar to the discussion after Theorem
[. one can find that for large T, the improvement over Liu
& Zhou 2023) is at least by factor of
-polyy poly (1
dell In 11)))
1
1
2-P d
=
In
di
I
For general T E N, every term in Theorem 2 still better except for Ol+2 //TT((TT)) However, this extra term has no effect once T> T, ( = (ddet In (1/6) + Lar [p <)), the same critical time for Theorem (a similar discussion to Footnote al applies here), since it is at most (G /(TT) now, being dominated by other terms. Same as before, it is unclear whether this redundant term (r(2(//((()))) can be shaved off to conclude faster rate for any T N or not. We leave it as future work and look forward to it being addressed.
PROOF SKETCH AND NEW INSIGHTS
In this section, we sketch the proof of Theorem I as an example and introduce our new insights in the analysis. To start with, given T E N and suppose 7):
r, Vt E [T] for simplicity, we
'Actually, any T. that makes ((pGD/T) in Theorem smaller than the sum of the terms left is enough. Hence, it possible find smaller critical time. We keep this one here due its clear expression.

---

Published as a conference paper at ICLR 2026
have the following inequality for Clipped SGD (see Lemma 4 in Appendix which holds almost surely without any restriction on T,
where IT is a residual term in the order of D + 217
cvx F F(xT+1)
F. v
T O
1
Σ
dd Ys)
|
+G2T
(5)
EE(T]
II
III
in which di - of - E [gf] and db - E [
V (x,)) respectively denote the unbiased and biased part in the clipping eιror, where IE, [-] _ E Fil for F. _ of.. .Et) being the natural filtration, and Y: is some predictable vector (i.e., Yr E 1) satisfying lyv.ll S almost surely.
The term r/CT in 1 is standard. Hence, the left task to bound terms II and III in high probability. In particular, for I and III, we will move beyond the existing approach via refined analysis. To formalize the difference, we borrow the following bounds for clipping error commonly used in the literature (see, e.g., (Sadiev et al. (2033 Liu & Zhou (003); Nguyen et al. (202)))
|| < O(T), B--1
[|ay1]]
22 S O
||db||
if < O
(6)
Term I. Note that X₂ man's inequality (Lemma
(d), yt) is a martingale difference sequence (MDS), then Freed- 10 Appendix FD implies with probability at least 1 8, vI 1
O(maxee(T) X₂] ln(1/8) + E E. [X]] Im(1/6)) (this inequality is for illustration, not en- tirely rigorous in math). To the best of our knowledge, prior works studying Clipped SGD under heavy-tailed noise always bound similar terms in the following manner
lxv SI S
Xx
|
O(T)
and E,-
E,-1
[|a!1]]
O(op+2-P).
However, critical observation is that the above-desccrbed widely adopted way is very likely to be loose, as the conditional variance can be better controlled by
E X
E. (d)
(d))
Yt
Note that || (d:)
[| most R.-1
|
but could be much smaller. Inspired by this,
in Lemma Consequently, this better utilization of Freedman's 's inequality concludes tighter high-probability bound for term I.
we develop a new bound for ||E,- (d))
Actually, this simple but effective idea has been implicitly used in Das et al. (2024) when p = 2. However, their proof finally falls complex due to argument they call the iterative refinement strategy, which not only imposes extra undesired factors like In ( in their final bound but also leads an additional requirement T 2 [Inn d)) in their theory. Our analysis indicates that such a complication is unnecessary, instead, one can keep it simple.
Term II. For this term, follow the same way employed in many previous works (e.g., Cutkosky
& Mehta 2021 Zhang & Cutkosky (0022)) i.e., let X, A ||رbl| E,- [[ali]]] and decompose
Ei=1 |d
O + of72-PT) then use Freedman's is inequality bound Σt= X..
Remark 6. Although the above analysis follows the literature, we still obtain a refined inequality for E,11 [| in Lemma in the sense of dropping the condition > 2G required in (6).
Term III. Estimating the clipping error ||]]] is another key ingredient when analyzing Clipped SGD. As far ever, we show that this important inequality still has room for improvement. In other words, it is in fact not tight, revealed by finer bounds in Lemma Thus, our result is more refined.
know, all existing works apply the inequality ||dح]| - O(ap~'~p) in (6). How-

---

Published as a conference paper at ICLR 2026
From the above discussion, in addition to better utilization of Freedman's inequality, the improve- ment heavily relies on finer bounds for clipping error under heavy-tailes noise, which we give in the following Lemma Under Assumptions
Lemma 1.
aadd and assuming T
> 0, there are:
fr22G
|d [ OT),,
| (dr) IIll
O + ofG²T
Ex-1 ||d))|]]] - O(
|
fr22G 2G
0 o(GT
Remark 7. We highlight that Theorem 9 Appendix provides further generalization of clipping error bounds under heavy-tailed noise not limited clipped gradient methods (even without the requirement in the form of r 2 2G), which could be potentially useful for future research.
Except for the standard bound ||d!|| < O(T), the other three inequalities in Lemma | are either new or improve over the existing results. 1. The bound on || [d))) is new in the heavy- tailed setting. Importantly, observe that ? + GP) S (apr>=p) due to S ot and 2 2G, which thereby leads to a tighter high-probability bound for term combination with better application of Freedman's 's inequality (see the paragraph before starting with Term 1.). 2. For term E ||]]1]] in contrast to 66, Lemma removes the condition т 2 2G. Moreover, the
hidden constant in our lemma is actually slightly better. 3. As mentioned above (see the paragraph before starting with Term III.), the bound of || is another key to obtaining refined result. ofGT improves upon ((a"ri-P) in (o) because of o, I oi and r 2 2G. Therefore, Lemma guarantees a better control for term III.
Precisely, we note that the new bound Moa.op-11111
Combining all the new insights mentioned, we can finally prove Theorem ! As one can imagine, the analysis sketched above is essentially more refined than previous works, since we apply tighter bounds for the two central parts analyzing Clipped SGD, i.e., concentration inequalities and esti- mation of clipping error. To confirm this claim, we discuss how to recover the existing rate through our finer analysis, the details which are deferred to Appendix E
Lastly, we mention that Theorem 2 for strongly convex problems is also inspired by the above two new insights. The full proofs of both Theorems T [nndd] can be found in Appendix
EXTENSION TO FASTER IN-EXPECTATION CONVERGENCE
In this section, we show that Lemma I presented before can also lead to faster in-expectation con- vergence for Clipped SGD, further highlighting the value of refined clipping eπror bounds. Proofs of both theorems given below can be found in Appendix
This time, we consider new quantity A oz ((f '1 [p < 2)) for the clipping threshold. Recall that dest = of /02 then can be equivalently written into
F. = =
where 2
2].
(7)
Remark 8. When 2, G. 0 - F. +oo, i.e., no clipping operation is required. This matches the well-known fact that SGD provably converges in expectation under the finite variance condition.
6.1 GENERAL CONVEX CASE
Theorem 3. Under Assumptions
7 (with μ 0). and for any T N, setting Tit max (2G, j, ,, [T] where T, is properly picked stepsize (explicated in Theorem guarantees that IE [F(xXX))
Ts Ti
12 then
Clipped SGD (Algorithm T
F.] converges at the rate of
+ ( G +
3 2-1 2-1 2-2
GGD T
01
D
o
T!-
where T S Φ. is constant (explicated in Theorem 12 and equals G. when T = Ω
8

---

Published as a conference paper at ICLR 2026
Theorem 3 gives a better lower-order term Olodd - (recall des = of / than the
existing lower bound DT (T>>)) ) (Nemirovski & Yudin 1983: Vural et al. 2022) by a factor of
@11/d " ). strict improvement being polynomial in 1 /dett. if (1,2). For the case of an unknown T, the interested reader could refer to Theorem 13 in Appendix
6.2 STRONGLY CONVEX CASE
Theorem 4. Under Assumptions
(with J 0), and 4 for any T N, sefting Re
6 R = max 32G,,tt. Vt E [T' then Clipped SGD (Algorithm guarantees that both
||XT+I - 11 converge at the rate of E [(((+))) F.] and μB
$ 4-2 4-4
nD²
G G
G²
G
01
0
+
T3
nT2
pf
2
where @0 4x is the same constant as Theorem and equals G when T Ω
GP
o pp
Theorem 4 provides a faster rate O 1-2 PT than the known lower bound M(o -2
P-n
Zhang et al. 2020) by factor of @ /1 this is again strict improvement once p < 2, and could be in the order of poly(1/d) if dea = ((d)..
LOWER BOUNDS
To complement the study, we provide new high-probabilit and in-expectation lower bounds for We employ information-hhen theooreiic methods to establish these new lower bounds, following the existing literature (Raginsky & Rakhlin 2009 Agarwal et al., 2012 Duchi jet al., 2013 Vural et al. 2022 Carmon Hinder 2024 Ma et al. 2024). For their formal statements and corresponding proofs. the interested reader could refer to Appendix G in the full version of this work available at https::////// arxiv. org abtp///ss//21.... 23178
both fr and i
Remark 9. One may wonder why our upper bounds can beat the existing lower bounds, and also where the difference between our new lower bounds and the prior ones lies. The key is our fine- grained Assumption 4 Roughly speaking, the existing lower bounds are proved for the following oracle class (we slightly abuse the notation by still using g to denote the stochastic gradient oracle),
GP g Rd x Rd
Big(x.)) xx flxx /[()) [xx Vx Rd f
where p (1, 2] and 2 0 are two parameters and is the function class that we interested in (e.g., the family of G-Lipschitz convex functions). In contrast, the oracle class we study is parame- terized by one more parameter o, | V rd/2,
follows,
E Eig(s.f)ss.fl=V//ceeee)
RP 00.01
g Rdd x Rd
BB| =[(e=xxx./)VVV//>) [x) bees "eE [
Vx RR, SEf/
Note that there is GP Therefore, our upper bounds can surpass the existing lower bounds, and our new lower bounds are established for the fine- rreegga oracle class BP G..a.'
could be loose for GP GP . implying the lower bound proved for @ d,
7.1 PROBABBIBY LOWER BOUNDS
Theorem (Informal). Under Assumptions with μr 0). and assuming d ' desf 2 1 and
(0, 1.), any algorithm converges at least at the rate of Ω (a to, la 1- 1)D with
T 71
probability least 8 when T is large enough.

---

Published as a conference paper at ICLR 2026
Theorem 6 (Informal). Under Assumptions 0 (with μ 0), and 4 assuming d 2 delf 2
and ó E (0, to). any algorithm converges at least at the rate of Ω2
with
PT
probability least 8 when 'I' is large enough.
Compared to upper bounds in high probability, i.e., Theorems [ are still differences between the terms that contain the poly(In(1/o)) factor. Closing this important gap is an interesting task, which leave for future work.
0) and 2 (fu >> 0), there
7.2 IN-EXPECTATION LOWER BOUNDS
Theorem 7 (Informal). Under Assumptions 7 (with 0).
and assuming d 2 dett 2 1,
o 2-
any algorithm converges at least at the rate of n
T in expectation when T large
enough.
Theorem 8 (Informal). Under Assumptions 7
2 (with μ
> 0), 3 andd assuming d 2 deff 1, any
algorithm converges at least at the rate Q
wT in expectation when is large enough.
For in-expectation convergence, the above lower bounds match our new upper bounds, i.e., Theo- rems 3 (1u 0) and 4 (μ 0), indicating the optimality of our refined analysis for convergence in expectation.
CONCLUSION AND FUTURE WORK
In this work, we provide a refined analysis of Clipped SGD and obtain faster high-probability rates than the previously best-known bounds. The improvement is achieved by better utilization of Freed- man's inequality and finer bounds for clipping error under heavy-tailed noise. Moreover, we ex- tend the analysis in-expectation convergence and show bounds. To complement the study, we establish new lower bounds for both high-probability and in-expectation convergence. Notably, the in-expectation upper and lower bounds match each other, indicating the optimality of our refined analysis for convergence in expectation.
rates that break the existing lower
There are still some directions worth exploring in the future, which list below:
The extra term. Each of our refined rates has a higher-order term related to desr (e.g.. O(pGD/T) in Theorem and Oyp² (pz?²)) in Theorem 2). Although proving/disproving it can be removed for any T E N could be an interesting task.
negligible when T is large,
Gaps in high-prohhe probabbiiyyi bounds. As discussed in Section there are still gaps between high- probability upper and lower bounds for both convex and strongly convex cases. Closing them is an important direction for the future.
Other optimization problems. We remark that our two new insights are not limited to nonsmooth convex problems. Instead, they are general concepts/results. Therefore, we believe that it possi- ble to apply them to other optimization problems under heavy-tailed noise (e.g., smooth (strongly) convex/nonconvex problems) and obtain improved upper bounds faster than existing ones.
ACKNOWLEDGMENTS
The author thanks anonymous reviewers for their helpful comments and valuable feedback.
REPRODUCIBILITY STATEMENT
We include the full proofs of all theorems in the appendix.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Alckh Agarwal, Peter L. Bartlett, Pradeep Ravikumar, and Martin J. Wainwright. Information- theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Trans- actions on Information Theory, 58(5):3335-322 3249,,2499999 2012. doi: 10. 10.1/T9TT1 1019/TTTT201122122777 21822778
Alcksandar Armacki, Shuhua Yu, Pranay Sharma, Gauri Joshi, Dragana Bajovic, Dusan Jakovetic, and Soummya Kar. High-probability convergence bounds for online nonlinear stochastic gradient descent under heavy-tailed noise. In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan (eds.), Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pp. 1774-1782. PMLR, 03 05 May 2025. html
URL https: http::::/poccceddeee
ml: wwwpsppssss...... www.ee///////aaaaaaaaa art.55i2aaaaaa225.....
Barak Battash, Lior Wolf, and Ofir Lindenbaum. Revisiting the noise model of stochastic gradient descent. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 4780-4788. PMLR, 02-04 May 2024. URL https://
sansss/vv2333 vv.3//22.//////// httpsss///////tttahhh44444 wttpb/attaaaaaaaaaaa proceeding ngs .ms.mml. momlr press/
html
Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003. ISSN 0167-6377. doi:
URL https: www. http:///wwwcceecc.eee...tt
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311, 2018.
doi: 10.1137/1610080173. URL https://
doi wwwoor/110 /00 1tt///0.1111/771 1137/1 6M1 080173
D. L. Burkholder. Distribution Function Incqualities for Martingales. The Annals of Probability, 1(1):19 - 42, 1973. doi: 10. 22224//0//117997700 URI. /ttp://////..r0/1111111/
Bop/1176997023
Yair Carmon and Oliver Hinder. The price of adaptivity stochastic convex optimization. In Shipra Agrawal and Aaron Roth (eds.), Proceedings of Thirty Seventh Conference Learning Theory, volume 247 of Proceedings of Machine Learning Research, pp. 772-774. PMLR, 30 Jun-03 Jul
2024. URL httpattt///prrceainnngee mww.sssss..pp.ess...... www.spessss...............eee..e serres//v44.. v21 http:///22/22/222222a/ cwrm///mmmnn2mcccc 4a html
Yeshwanth Cherapanamjeri, Nilesh Tripuraneni. Peter Bartlett, and Michael Jordan. Optimal mean estimation without a variance. In Po-Ling Loh and Maxim Raginsky (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 356 357. PMLR, 02-05 Jul 2022. htt.:ttts:///// //rpocee/ ngs mlr. press/v11.. ngs.mlrr.reas//1117 cherapanamjeri 12a..2222... html
Ashok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and. J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 4883-4895. Cur- ran Associates, Inc., 2021. wtt.p////...Lpeee/pppeeeeeeeee.e
cctpspe..ppppppppppppeeeee files/
Aniket Das, Dhceraj Nagaraj. Soumyabrata Pal, Arun Sai Suggala, and Prateck Varshney. Near- optimal streaming heavy-tailed statistical estimation with clipped sgd. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomezak, and C. Zhang (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 8834-8900. Curran Associates, Inc., 2024. URL |tttpss:/prrceeddinngg wtwp:iinnnsn.euuuueee www.ipsuuip.... wttp:pppp.cpppppppppeee fttp:peerfilleespppee/2222. File/
.pff
Damek Davis and Dmitriy Drusvyatskiy. High probability guarantees for stochastic convex opti- mization. In Jacob Abernethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference Learning Theory, volume 125 of Proceedings Machine Learning Research, pp. 1411-1427. PMLR. 09-12 Jul 2020. URL ht https: https::/ .mm.iiinnns.m........mm.m... prwss/ www.ss/veiss. vitss//vvi/////./ davis2aa.
htm

---

Published as a conference paper at ICLR 2026
John Duchi, Michael I Jordan, and Brendan McMahan. Estimation, optimization, and paral- lelism when data is sparse. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger (eds.). Advances in Neural Information Processing Systems. volume 26. Curran Associates, Inc., 2013. URL htt httttp:://procceddngge http:nngs.nnerippsc..eeeeeeeeeee files/
Rick Durrett, Probubility: Theory and Exumples. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 5 edition, 2019.
Huang Fang, Nicholas J. A. Harvey, Victor S. Portella, and Michael P. Friedlander. Online mirror
descent and dual averaging: Keeping pace in the dynamic case. Journal of Machine Learning Research, 23(121):1-335 2022. URL http: /estp://mmll wtt.m.rrr.................oooere http//apperrs//// / 22 -0027 .tmll
llyas Fatkhullin, Florian Hübler, and Guanghui Lan. Can sgd handle heavy-tailed noise? arXiv
preprint arXiv:2508.04880 2025.
David A. Freedman. On Tail Probabilities for Martingales. The Annals of Probability, 3(1):100 118, 1975.
doi: 10. 10.1214/ap/11176999/ 176996452. URL
1176996452
Saurabh Garg, Joshua Zhanson, Emilio Parisotto, Adarsh Prasad, Zico Kolter, Zachary Lipton, Sivaraman Balakrishnan, Ruslan Salakhutdinov, and Pradeep Ravikumar. On proximal policy optimization's 's heavy-tailed gradients. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3610-3619 3619. PMLR, 18-24 Jul 2021. URL http:: / //tp://edcc.ceed........ mlr. wtw.press/vve ptress/v139/garg//
html
Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimiza- tion with heavy-tailed noise via accelerated gradient clipping. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural In- formation Processing Systems, volume 33, pp. 15042-15053. Curran Associates, Inc., 2020. URL. htttps::/prooceeddiin neurrieeerrppp ct wttpcc/pppppeeeeeeeeeeee ftwess//pppee//00// File/ htt.:///ww..../000////1///0aaaa. Paper...pp
Eduard Gorbunov, Marina Danilova, Innokentiy Shibaev, Pavel Dvurechensky, and Alexander Gas- nikov. High-probability complexity bounds for non-smooth stochastic convex optimization with heavy-tailed noise. Journal of Optimization Theory and Applications, pp. 1-60, 2024a.
Eduard Gorbunov, Abdurakhmon Sadiev, Marina Danilova, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. Higgh-probbillity convergence for composite and distributed stochastic minimization and variational inequalitics with heavy- tailed noise. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 15951-16070. PMLR, 21 Jul 2024b. URLhttps. http::///cccceeegs..oo / mir. press/ 22335gorbunow2455 html
Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. The heavy-tail phenomenon in sgd. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Confer- ence on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3964-3975. PMLR, 18-24 Jul 2021. gurbuzbalaban21e htmml
mlr. wtt.:/sssm.......///...3..
Liam Hodgkinson and Michael Mahoney. Multiplicative noise and heavy tails in stochastic opti- mization. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Con- ference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pp. PMLR. 18-23 24 Jul 2021. URL httpss:/ .tt.://d.....m.....r....s////.
mlr presssv139/
h inon2 1 html
Matthew J. Holland. Anytime guarantees under heavy-tailed data. Proceedings of the AAAI Con- ference on Artificial Intelligence. 36(6))618--6))) 6925, Jun. 2022. doi:
URL htt.lhttss://tt //os: aaai www....r//iae....../////
e/v1e//20649
12

---

Published as a conference paper at ICLR 2026
Florian Hübler, Ilyas Fatkhullin, and Niao He. From gradient clipping to normalization for heavy tailed sgd. In Yingzhen Li, Stephan Mandt, Shipra Agrawal, and Emtiyaz Khan (eds.), Proceed- ings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 PMLR, 03-05 May 2025. URI.
of Proceedings of Machine Learning Research, pp. https: fttt:s://pprceedii iggeeeiiingg.... 1 press w2/8/
Maor Ivgi, Oliver Hinder, and Yair Carmon. DoG is SGD's best friend: parameter-free dynamic step size schedule. In Andreas Krause, Emma Brunskill, Kyunghyun Cho. Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.). Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 14465-14499. mlr wtwpt/gg.....ss.e.a/...peee.eeee
PMLR, 23-29 Jul 2023. URL
html
Dušan Jakovetić, Dragana Bajović, Anit Kumar Sahu, Soummya Kar, Nemanja Milošević, and Dušan Stamenković. Nonlinear gradient mappings and stochastic optimization: A general frame- work with applications to heavy-tail noise. SIAM Journal on Optimization, 33(2):394-42 2023. doi: 10.1137/2 1 URLhetos:: /oii wttp///..1../..1.......
Guanghui Lan, First-order and stochastic optimization methods for machine learning. Springer, 2020.
Langgi Liu, Yiho Wang, and Lijun Zhang. High-probability bound for non-smooth non-convex stochastic optimization with heavy tails. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceed- ings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 32122-32138. PMLR, 21-27 Jul 2024. URL https: 7/proceedings mlr pwwps/
wexess/v2355 v235 11////iu2bb.o.. html
Zijian Liu. Online convex optimization with heavy tails: Old algorithms, regrets, and applica- tions. arXiv preprint arXiv:2508.07473, 2025.
Zijian Liu and Zhengyuan Zhou. Stochastic nonsmooth convex optimization with heavy-tailed noises: High-probatee bound, in-expectation rate and initial distance adaptation. arXiv preprint 12X2: 2023.
Zijian Liu and Zhengyuan Zhou Revisiting the last-iterate convergence of stochastic gradient methods. In The Twelfth International Conference on Learning Representations, 2024. URL
attps://openreet wtwpeeewwnee//ooumddeeeeeeeee /oormmmddxxxxaacc111
net
Zijian Liu and Zhengyuan Zhou, Nonconvex stochastic optimization under heavy-tailed noises: Optimal convergence without gradient clipping. In The Thirteenth International Confer- ence on Learning Representations, 2025. URL https://///........ /ttp:::////peeeeee... net wottt/foummiiom NKot.PUUeTT
Zijian Liu, Jiawei Zhang, and Zhengyuan Zhou, Breaking the lower bound with (little) structure: Acceleration in non-convex stochastic optimization with heavy-tailed noise. In Gergely Neu and Lorenzo Rosasco (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp.
PMLR, 12-15 Jul 2023. URL
https: :ttpp:://pxoceeeingg mlr . www.:rarrrr.p.r...... wwtp//il23............... html
Tianyi Ma, Kabir A Verchand, and Richard J Samworth. high-probability minimax lower bounds.
arXiv preprint urXiv:2406. 13447, 2024.
Vien V. Mai and Mikael Johansson. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. In Marina Meila and Tong Zhang (eds.), Pro- ceedings of the 38th International Conference on Machine Learning, volume 139 of Proceed- ings of Machine Learning Research, pp. 7325-7335. PMLR, 18-24 Jul 2021. URL https:
mir.iiinnn............m.mm..m..m //proceedings.oo mlr wwwpssewsss... vtt./vl3////// 2tl/33/mmaaiie mawila.......................lmm html
Alexander V Nazin, Arkadi S Nemirovsky, Alexandre B Tsybakov, and Anatoli B Juditsky. Algo- rithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 6077 2019.
13

---

Published as a conference paper at ICLR 2026
Arkadi Nemirovski and David Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience, 1983.
Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
Ta Duy Nguyen, Thien H Nguyen, Alina Ene, and Huy Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. In A. Oh, T. Nau- mann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 24191-24222. Curran Associates, Inc., 2023. URL / ngs neur ips ps http:/papperrfsspepeeepe /2023/ fi hile:/4455ee44444446664464111113 Poppaeeecccappppe---oeeeeeeeeeee
John P Nolan. Univariate stable distributions. Springer, 2020. 2020..
Daniela Angela Parletta, Andrea Paudice, Massimiliano Pontil, and Saverio Salzo. High probability bounds for stochastic subgradient schemes with heavy tailed noise. SIAM Journal on Mathematics of Data Science, 6 6(4):953 997,, 2024. doi: 10. 00.1137/2211336558. URL htt.h:tps///// /do1. / 10. 1t.1137/22M151
Daniela Angela Parletta, Andrea Paudice, and Saverio Salzo. An improved analysis of the clipped stochastic subgradient method under heavy-tailed noise, 2025, URL /ttps:///axy
245/2410.00573
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference on Machine Learning, volume of Proceedings of Muchine Leurning Reseurch, pp. 1310-1318, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. URL https: /ttp:///rceeiiic/oeooooooc ngs.
m1 r. wttpppsss////p/caaan..
html
Nikita Puchkin, Eduard Gorbunov, Nickolay Kutuzov, and Alexander Gasnikov. Breaking the heavy-tailed noise barrier in stochastic optimization problems. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), Proceedings of The 27th International Conference Artifi- cial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp- 856-864. PMLR, 02-04 May 2024. URL puchkin24a. html
mlr ptwps//22s////////
Maxim Raginsky and Alexander Rakhlin. Information complexity of black-box convex opti- mization: A new look via feedback information theory. In 2009 47th Annual Allerton Con- ference on Communication, Control, and Computing (Allerton), pp. 803-510 2009. doi:
Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Math- ematical Statistics, 22(3):400~ 407, 1951. doi: (0.1214/aomm//17777995 URL https:
7/ ///oi.org/0...ooo 1214/ att.//om//////////////// /117m7211177758
Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. High-probability bounds for stochastic optimization and variational inequalities: the of unbounded variance. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 29563-29644 PMLR, 23-29 Jul 2023. URL https:///proceednngs mlr press// /202 sadiev23a.hhnm..mm
Gennady Samorodnitsky and Murad S Taqqu. Stable non-Gaussian random processes: stochastic models with infinite variance, volume 1. CRC press, 1994.
Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5827-5831 PMLR, 09-15 Jun 2019. URL httpss://procese
www..mm......s.mmmm wwrpessvvvii / msek 11111.111111. 1t.htmm.
14

---

Published as a conference paper at ICLR 2026
Tao Sun, Xinwang Liu, and Kun Yuan. Revisiting gradient normalization and clipping for non- convex sgd under heavy-tailed noise: Necessity, sufficiency, and acceleration. Journal of Ma- chine Learning Research, 26(237):1-42, 2025. URL http://jmlz wwggpaapes//2225
124-1930 html
Joel A. Tropp. An introduction to matrix concentration inequalities. Foundations and Trends@) in Machine Learning, 8(1-2):1-230, 2015. ISSN 1935-8237. doi: 10.1561/2200000048.. URL http:/ dx. www.ooooooo....
Che-Ping Tsai, Adarsh Prasad, Sivaraman Balakrishnan, and Pradeep Ravikumar. Heavy-tailed streaming statistical estimation. Gustau Camps- Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceedings of The 25th International Conference Artificial Intelligence and Statisties, volume 151 of Proceedings of Machine Learning Research, pp. 1251-1282, PMLR, 28-30 Mar 2022. URL wtw.hhttss//cm
ngs ml www.s/eesvvvv... /
html
Nuri Mert Vural, Lu Yu, Krishna Balasubramanian, Stanislav Volgushev, and Murat A Erdogdu, Mir- ror descent strikes again: Optimal stochastic convex optimization under infinite noise variance. In Po-Ling Loh and Maxim Raginsky (eds.). Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 65-102. PMLR, 02-05 Jul 2022. URL https::/procee:: www.ooeeeeiine.......oo ml r. press www.//vruuee 12a html
Hongjian Wang. Mert Gurbuzbalaban, Lingjiong Zhu, Umut Simsekli, and Murat A Erdogdu. Convergence rates of stochastic gradient descent under infinite noise variance. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neu- ral Information Processing Systems, volume 34, pp- 18866-18877. Curran Associates, Inc., 2021. URL htttps:/pproceeddi.n. meeraeeddddenee..neeoo..e...... neur www.wpe.uccccccoooooo.o http://eeeeoooooo.oooooeeeeeeeee
File/ http////0006666666666663363633a3 Paper...pppppppppp..... wwteff/aappe//2222///
Manfred K Warmuth, Arun K Jagota, al. Continuous and discrete-time nonlinear gradient de- scent: Relative loss bounds and convergence. In Electronic proceedings of the 5th International Symposium on Artificial Intelligence and Mathematics, volume 326. Citeseer, 1997.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, San- jiv Kumar, and Suvrit Sra. Why adaptive methods good for attention models? In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 15383-15399 Curran Associates, Inc., cc cc/paper filess/pperr/20c//
2020. URL Fil maleebbobb77 FLL2:/00SSTTTead0000000000666660 Pap.red-ppppprpppppppp.
Juujaa Zhang and Ashok Cutkosky. Parameter-free regret in high probability with heavy tails. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 8000-8012. Curran Associates, Inc., 2022. URL httpps://proeedd.ngg neurips cc cc/paper.ppppceeceeece fi www.ff/pppeee////22./ Paper Cateer--cnneeeeeee.c
Pan Zhou, Jiashi Feng, Chao Ma, Caiming Xiong, Steven Chu Hong Hoi, and Weinan E. To- wards theoretically understanding why sgd generalizes better than adam in deep learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 21285-21296. Curran Associates, Inc., 2020. URL https://proceednngg neurips cc capppprr files/paper/202c/ pdf
File/ (0A.:///222227111000000000000000
Vladimir Zolotarev. One-dimensional stuble distributions, volume 65, American Mathematical
Soc., 1986.
15

---

Published as a conference paper at ICLR 2026
A LOWER BOUNDS ON deff
This section provides lower bounds on derr for the additive noise model, i.e., g(x,()xx))))))))))))))))) = V/(x)++ +
Given E [d], & denotes the i-th coordinate of ç, and or _ (E [I<: the p-th moment of
&. Additionally, L [d] - [d] the permutation that makes os nonincreasing order, i.e.,
On 2 0n 2 ca-1 2 Ous
A.1 INDEPENDENT COORDINATES
In this subsection, we assume that all & are mutually independent.
For any j E [d]. we can lower bound
|E =
where the last step is by the concavity of x², which implies of = E [[]]]|]] j - D of. Therefore, can find
z
of 2 max j jeld
(8)
For any E gd-1, we write e = Ei= d where Σ X = and e, denotes the all-zero vector except for the i-th coordinate, which is one. Therefore, have
(a)
E [[(e,))) = E
A
E
[ASS
1-4
22-p
o
22-p
0,
where (a) holds by la + b)P s la| + + |a |a|p-1 Vural et )2022) and the mutual independence of E., and (b) due
sa)b + 22-p |b| (see Proposition 18 of
$
1
d Σ
Pee PMPo
Σ
Σ
3p
Hence, we know
1-
d
o. = sup
E [) 2
22-p
Σ
T-P
(9)
1ml
As such, we can lower bound
max 5
1-
Σ/
oD
doff
(10)
2 -2
Ed
F-
Though I0p does not directly give a lower bound for dest expressed in terms of d, it has already provided some useful information. For example, when are all in the same order, (10) implies that
dut (2
A.2 I.I.D. COORDINATES
In this subsection, further assume that all & i...d. and then lower bound des by d. Since all coordinates are identically distributed now, we write o; = o, Vi [d] for some o 2 0 in the following.
16

---

Published as a conference paper at ICLR 2026
A.2.1 A GENERAL ((d2 BOUND
We invoke (TO) and plug in d; obtain
10
maXje d1) joz
df
deff
(1I)
2 2 1
2+ -2-
When = 2, the above bound recovers the fact that dett = for & with i.i.d. coordinates.
A.2.2 A SPECIAL (2(d) BOUND
Now we consider special kind of noise. Suppose p E (1,2) and & have the characteristic function
E (exp (its:) exp (-70 |010 (1 iß tan
sga(t)) vt E R.
where p for E (0, pl. B E [-1,1], 1], and
0. Such a distribution is known as
a-stable distribution satisfying that E [g] 0, oo, and
&, equals & in distribution This suggests that we can lower
Zolotarev 1986, Samorodnitsky & Taqqu 1994 Nolan
2020
bound of in another way.
E
d
Ei=
&
P
E
d &
+ op d
of = E [|K]]]] E
18ppp
18Ppp
p
18Pp
(p-1
p-1
(12)
where the inequality is due to Burkholderr
(973). Therefore, in this special case, we have
12 d:tr x² /18 pd (p 1)d FlDee
deff o²
(13)
2 2
-1
p3342$
In particular, for any 0 < trivial).
S min
2ind-1:
p
2 2-p] p}]
-pp
(assume d 2 2 here, since the case d = is
2e
S 1 deipte Seb + delf
(p 1)d
p3342 (dd).
(14)
p(p + E) Ind d
B REDUCTION FOR STRONGLY CONVEX PROBLEMS
We provide the reduction mentioned in Remark 5 strongly convex and G-Lipschitz with a minimizer x, on X. Now we consider the following problem instance to our problem structure
Recall that existing works assume f being p--
F(x) f(x)
" x
y112
||x - yl1 f(x);
fx)
Ax(
where y can be any known point in X. For example, one can set = X1 to be the initial point. Next, we show that fulfills all assumptions in Section 2
F on X has the same optimal solution x, as f and hence satisfies Assumption I
Note that f convex (since f is u-strongly convex) and r is p-strongly convex, which fits Assumption 2
Moreover, because f is p-strongly convex and G-Lipschitz with minimizer x, E X, well-know fact is that X has to be bounded, since for any x E X,
P x 11 < fxx) f(x.) - (V. x.) & f(x) - f(x.) - x S G||x - x,
2
$ <VV((x). x.)
2G
-1Ix-x+11
-xxl
(15)
17

---

Published as a conference paper at ICLR 2026
Then can calculate vf(xx) Vf(x) pxx y), VX E X and find f 1
||
[V](])] + - x.| + + lly x.I 5G, Vx X, meaning that Assumption holds under the parameter 5G.
In addition, suppose we have first-order oracle g(x, <) for f satistying Assumption Then g(x, E) g(x. {) pxx y) is a first-order oracle for f satisfying Assumption with same parameters p. 0 and dr-
Therefore, any instance in existing works can be transferred our problem structure. More- over, for such an instance, we have D
|| x.
2G implying that the first term J
which can be further bounded by the third term in Theorem can be omitted if compared with prior works. Remark 10. The above reduction does not hold in the reverse direction. This is because, one can see, the domain X in prior works has to be bounded (due to (15)). which is however not necessary under our problem structure. For example, X in our problem can take Rd which cannot be true for previous works in contrast. In other words, the problem studied in our paper is strictly more general.
nD2 T in Theorem 2 is at most O
G² uT
(af (aftaf a in
3)62 +0 O DD?
o
C STABILIZED CLIPPED STOCHASTIC GRADIENT DESCENT
Algorithm Stabilized Clipped Stochastic Gradient Descent (Stabilized Clipped SGD)
Input: initial point x E X, stepsize > O, clipping threshold Ti > 0
for T do gi = clip,, where g: = g(x,, Et) and & ~ D is sampled independently from the history
X1+1 = argmin (x) + (gf x) + [x xx1x. ? + (mn /on
27.
end for
In this section, we propose Stabilized Clipped Stochastic Gradient Descent (Stabilized Clipped SGD) in Algorithm 2 an algorithmic variant of Clipped SGD to deal with the undesired poly (In T') factor appearing in the anytime convergence rate of Clipped SGD for general convex functions.
Compared to Clipped SGD, the only difference is extra (ne/9te1-1)) 1)]xx-x term injected into the update rule, which is borrowed from the dual stabilization technique introduced by Fang et al. (2022). The stabilization trick was originally induced to make Online Mirror Descent (Nemirovski & Yudin 1983. Warmuth et al. 1997 Beck & Teboulle, 2003) achieve an anytime optimal (VTT) regret on unbounded domains without knowing T'. For how it works and the intuition behind this mechanism, we kindly refer the reader to Fang et al.] (2022) for details. Inspired by its anytime optimality, we incorporate it with Clipped SGD here and will show that this stabilized modification also works well under heavy-tailed noise. Precisely, assuming all problem-dee -ebeemddd parameters are known but not T, we prove in Theorem [T that Stabilized Clipped SGD converges at an anytime rate almost identical (though slightly different) to the bound for Clipped SGD given in Theorem that requires a known T in contrast.
2mp
Lastly, we remark that when the stepsize is constant, Stabilized Clipped SGD and Clipped SGD degenerate to the same algorithm. Therefore, Theorems and 3 can directly apply to Stabilized Clipped SGD as well. For the same reason and also to save space, we will only analyze Stabilized Clipped SGD when studying general convex functions.
D FINER BOUNDS FOR CLIPPING ERROR UNDER HEAVY-TAILED NOISE
In this section, we study the clipping error under heavy-tailed noise, whose finer bounds are critical in the analysis. Moreover, instead of limiting to clipped gradient methods, we will study a more general setting in the following Theorem 9 which may benefit broader research. In Appendix F. we apply this general result to prove clipping error bounds specialized for clipped gradient methods in Lemma which is the full statement of Lemma
18

---

Published as a conference paper at ICLR 2026
Theorem 9. Given o-algebra F and two random vectors g. f E R suppose they satisfy g F = and, for some p E (1,2] and two constants s, di 2 0.
E [llg fll' F of
E [ - f)| |
S of,
Ve edd1-
(16)
Moreover, we assume there exists another random vector g E IR4 that is independent from g con- ditioning on F and satisfies that g F equals
F in distribution. For any 0 < T E F,
let
g" - (g) = min 1, B
J
g. d g - Eg F}. db A HEL
E
F] - f, and
((a) - 1 [[1 a)r 2 [[f]]] Vo (0, 1), then there are:
1. d $ 2T.
2. E ||d'| | f 40p-2-p.
3. E d" (d") F 40p + 4||f]]²
4. E d" (d") T x(a) S 40.-2- + 4a Po ||r]]] P
Pop
5. |a v2 oo--1 |||||--1) O-T (of + ||el|*) [|
6. [[[[x(aa) S o
oo [f] T-
Before proving Theorem of a random vector g E Rd satisfying a certain condition. This technical assumption is mild as it hold automatically in many cases. For example, if F is the trivial sigma algebra, then can set g as an independent copy of g. For clipped gradient methods under Assumption 4 suppose F Fi-1, g g(x,,e)) { and
discuss one point here. As one can see, we require the existence
fxx)), then we can set g g(x;, fe+1). where we recall F afE,,'. ... 1 and &ı to ε++1 are sampled from ID independently.
Proof. Inspired by Das et al. (2044), we denote by h min 11 TET
[0, 1]. Under this notation,
we have
g clip, hgg.
(17)
We first give two useful properties of h.
For any 2 O, we have
g 9
|gl
[g 9
1 1- h <
gg
2
r|
79
7
which implies
h
inf
(18)
920
7-
We can also observe
[g]]
Igll
1- h
[|lg]]
2
Illll
5
2 7].
which implies
(1- (1-))x(a) < lgg - fll + [|f]| -T
[g] 2
7
1
1g fl|
||
lg fll
|g/|
>
inf
19-1-9 X(a),
(19)
T
221
19

---

Published as a conference paper at ICLR 2026
where the last step is by noticing that the event
{
|||||
2 T 2
[[]l]]
implies the event
I-a
|||l| { 2 1-aa llg - fl| 2 at
thereby leading to, for any
2 1,
1g - fll 1 |gl|| 2 1
[
I lg
fl
[
1
11g fl
2 oT
T
1
|1g
fl
1
T
2
llg
fl|
2 a7
09 79
|gg fll
a 179 x(a).
For g. we use ge to denote the clipped version of g under the same clipping threshold т, i.e., g. By our assumption on g. the following results hold
ge (g) = min
1, |ıा
E [g
F = Eg F = E B F,g),
(20)
E [[lg - fll
F = E [ll - fl F S oo.
(21)
We first prove inequalities for du.
Inequality
1 Note that ||g S r. implying |d"|= = =llg*= - R [g] | S 2T.
Inequality
We observe that
E |d'' 2
F
E
lg
[g] [F]
[ - g" | |1l |F]
||g
g0112 |F
S (2t)
llg - g | FE
(22)
IA3
(2r)
PE [|lg gll
4op
where (a) is by the convexity of 11.11 and the tower property, (b) holds because clip, is a nonexpansive mapping, and (c) follows by when p > 1
g g p S 2 (llg - fll + lg - fI') E g g
2P P
be a unit vector, we know The third and fourth inequalities are more technical. Let E gd-1
e E nd (d") T F e = E [e, a²) F = E (e.g Elg イM We will bound this term in two approaches. On the one hand, we have
(23)
E
(e, - E lg" 1 F
-E
(e.g" f) F|
[ec E [g FFM1 [F]
EE
(eeg g 1) F
E
(ee hg - ?) F
E
hh (c, g- f) (1 h) (c, 2 F
s E h ((c 1) + (1-1) Ke, F7]
<E
h bleee r) 2 (1 (1-h) h) ||r] [F]
(24)
where the last step by ( f) < ||||| [|[]| again,
[|f]]] and 1 h 2 By Cauchy- inequality
l(,
dle.--fo -
12fg-ff)--1 2- < 1gg - 2- < (1|g)) + 2
p>1 v
||l|| 2-p + ||
hgl<p 2
+ >h|(e, -
- 2 < h hgg
+ h || 2-p
| 2-p + ||f
2-p
| 1
||
2-p < 2-p + ||f]
20

---

Published as a conference paper at ICLR 2026
which implies
E
h (e..g-
F
(-2- + [| E [lke. f3/P F
2o, [||]2-P (25)
Combine
23
24 and (5 to obtain for any unit vector E gd-1
c E a (d")
F e ofrー~P + of || + ||E|| E [1 - h FF
E d" (d")
||]| s ooor + of ||| + ||||| B - h Fl.
(26)
On the other hand, we can follow a similar way of proving
to show
B KKee - [g FIN
デ] = (2 B (e g" g F
S 4 PB ||(e.g' - f)/² Fl.
(27)
Similar to 24 there is
E [[(ee,g' - 1))
S E h g r) + (1 11 ||||| |
< E - f) + (1 - h) ||F]| [F]
+ [ h Fl.
(28)
Combine 23
27
and 28
to obtain for any unit vector E gá-1
e
E
d
(d")
e S 40p
+ 472 P
|||| E [1 h [F]
E
(d")
+ - 40,
|||| E [] - h F].
(29)
Recall by our definition x(0) = 1 [T 2 Therefore,
f []. we then denote by x(0) - x(0) [T [|
B d"
(d")
F x(0)
0pr 0. [|A]] + ||E|| E [ h FT) X(O)
25
220p + || E
h F1) x(0),
and
29
E d (d") T
|F
X(0)
(40p + 47 2- || - h FI) x(O)
200772 2 + 4 | E h F x
which together imply
E d (d
T
F < P h 1
(30)
Now we are ready to prove inequalities 3 and 4
Inequality
We use
30
to know
E d (d")
F
< 4o 2 + 4 ||
2 1 h |F
S 40672-P + +1
Inequality 4 By 19 we have
(1 h)x(a) ||g fll
p--1y 7p x(a)
+ E h Fl x(a) x(a)EF B 1))(()) [ S
lg - fll
-p-1T8 x(o) |F
10 of 1-11
of <
21

---

Published as a conference paper at ICLR 2026
Now we use (30)
to know
E d" (d")
F [||((00)
S +4 E - h F) oo
S 500 4a Pop [|f]] [| T-P.
Finally, we prove the last two inequalities related to db Still let represent unit vector in R then by the definition of db,
(e, d
17
(e, E hg [ - f BB 1) (e. g) |
[F]
= ()
F
(e. E h F
(9
3 B[1 (1 (e, f)
F
| h FF]
( (B [B[(1- (1-1)== |
0, + || h F 0g + E | h 1F)
= | < E (1 - h) - F
(31)
where (d) is by h S 1 and (e, f) < |l|| ||||| = ||||] and (e) is by Hölder's inequality and (6)..
Inequality Noticing that -- 2 and
h S 1, we then have
(1- -) S 1
g
P
2
g flP
(E)())
7P
P
which implies
2P-1
(op P + [|E||P)
E (1 h) -) F < E
h
F
TP
Combine 31 and the above inequality to have
2P-1 (of + [1E]1*)
2P-1 (ap + [[E)]
||ab|| 5
0, + |||]|
TP
TP
ps2 I
v2 oo + ||E|| [[E||P-1) OCT 1-P P + +2 + [|E|[*) [|E]] -
Inequality 6 Recall that x(a) {0, 13 F, which implies
|bb (())
E ((1 ( h)x FF) o, + [( - (1)-(((aa)) | Fl
(E [(11 - h)x(a))) (F) [F)) 1- o. + ||| [[ [(1 - h)x(a) |
1-!
lg - fll
x(()) 5
lg fll
E
0. + ||||
ap-1マP x(a) F
TP
-100-111-0 + a 1 of [|[][-T] X(a)
<
00
p p-l 1- a p P..
E FULL THEOREMS FOR UPPER BOUNDS AND PROOFS
In this section, we provide the full description of each theorem given in the main paper with the proof. Besides, we also present new anytime convergence of Stabilized Clipped SGD. All interme- diate results used in the analysis are deferred to be proved in Appendix F
22

---

Published as a conference paper at ICLR 2026
Before starting, recall that D ||x, and the initial point.
x1|l denotes the distance between the optimal solution
For high-probability convergence, as proposed in (2) repeatedly used quantity in the clipping threshold is
0 P-1
In 3/ à 2- o
min
(32)
< 2]
where & E (0, 1] is the failure probability, p E (1,2)
and 0 S 0g S oi are introduced in Assumption
Another useful value mentioned before in (3 is
3 S max Vd in 8 d p 2
(33)
where dest = 07/0 is called generalized effective dimension defined in satisfying
deft E {0} U [1, xd/2),
(34)
in which dest = 0 if and only if 01 = 0a = O, i.e., the noiseless case. Lastly, it is noteworthy that the following equation always holds
9.
(35)
For in-expectation convergence, we will consider a larger quantity in the clipping threshold as men- tioned in Section
(36)
|p < 2]
We also recall
6. den 1 Ip < 2]
(37)
Note that there is
o
8. =
(38)
E.
GENERAL CONVEX CASE
We provide different convergence rates for general convex objectives. Recall that x stands for the average iterate after T steps, i.e.,
T Σ
X
(39)
Moreover, note that Clipped SGD and Stabilized Clipped SGD are the same when the stepsize Hence, everything in this subsection is proved based on the
constant, mentioned in Appendix C analysis for Stabilized Clipped SGD.
E.1.1 HIGH-PROOABILITT CONVERGENCE
Known T. We begin with the situation where the time horizon T is known in advance. Theorem 10 below shows the refined high- gighabbibbbiltyy rate for Clipped SGD.
Theorem 10 (Full statement of Theorem [. Under Assumptions T E N and 8 E (0, 11. setting Tソ 7), max G I-a T
(with μ 0).3 and for any
Vt E [T] where 1/2,
D/G +
D/G
D
7/ min
(40)
In g
(opP/CP +1)T
2- 2-1 0
2-2
+ 0 0
1
In
T
23

---

Published as a conference paper at ICLR 2026
and 4 S p, a constant defined in (46) and equals (p, when = (Algorithm 7V guarantees that with probability at least F F(XT-1 of
G² p.). then Clipped SGD
F, converges at the rate
( + In GD GD +
(o
( 2 2-
of
0 o
In Int-b 3 D
T
VT
T
Remark 11. There are two points we want to emphasize:
First, the choice a 1/2 not essential and can be changed to any a (0, 1), only resulting in different hidden constant in the O notation. In the proof, we try to keep until the very last step. Moreover, we would like mention that a small a may lead to better practical performance as suggested in Remark 2 of Parletta et al. (2025).
Second, these rates are presented while assuming the knowledge of all ters, as ubiquitously done in the optimization literature. However, not all problem beblem-deppedent param- eters are necessary if one only wants to ensure the convergence. For example. in the above Theorem
parame-
10 taking 7/2 min GVT Ti Ti max T Vt [T] where 7, O (like Theorem in Liu & Zhou (2023) is sufficient to prove that Clipped SGD converges. Therefore, when proving these theorems, we also try to keep a general version of the stepsize scheduling and the clipping threshold until the very last step.
Proof. First, a constant stepsize fulfills the requirement of Lemma 4 In addition, our choices of fj and also satisfy Conditions I and 2 (with a 1/2) in Lemma Therefore, given T E N and E (0, 1], Lemmas 4 and 6 together yield with probability at least 8,
|x, X1+1
D
F(x++1) P.
2AT
20
1/
1
2A
F(x741) -
S
(41)
1/++1 T
T
where AQ is a constant in the order of
o max 7h In? + Σ
of
2-P
0,0
p-1
GT
Σ
G
(42)
(E(T]
ap 17p
Our left task is to bound ACrx When T = T1 = 1A E [T] where 7) > 0 and G (as
2
I-a
required by Condition 2 in Lemma 6 we can simplify (42
into
3 8
0f
2p 2p-2
o 20 G²
T G2T) G2T))
x O
17
2 ln2
2
PT 2p2
T
a 2p 2720
(43)
One more step, under changing 7 to max
c
rT
(the second is only required to be nonneg-
I-a
ative) and using < 2, we can further write
43
into
AC -0 11
inf 1/()
(1 -1-a8 -20p 29 28p
2,2--221111 B)p
1
29
G2 In 2
0)
+
(1 (1-
ofG2-
+ G2 (+)r)
T
0.00 2p-2
+n
7 In2
+ + -
T
(44)
22p
where the first term appears due to for any B E 102).
0 2p G2
0 G²
T (1 288p 0 G2 G2-20p 23p
2
T28
a 2p 2p
28p
91p
ap 2-1-2 2(1
2p-2
G I-a
(Tb
24

---

Published as a conference paper at ICLR 2026
into (44) to have, under T, = max { : j. .t [T].
Now, we plug T = т. (see
32)
AT -0
G²
G2
of Gf
+ +0+) )
11
222-2
+
a) +
(1 a)2p
+1|
1 - 1-1
t of
2-3
In2
2 3
T
(45)
8
where the first term is obtained by noticing
(1 a) 2.9 0 G 2
T22
G
(1- a1-a)00) a) J (1-8)p
0 G
Ap
T
2
2p 2T 2(1B8)p B)p
T
[1
35
G
(1-a) 8 1-8
01
3p
T
2
Q2p-2 2
G
(1 - (000)0000000
G2-28p 20p
G²4²
inf 3c(0.1/2]
0
2
ax2p ax2p-27 2, 2(1-9)p
22--
in which
[1 9p
min S+, (1 -a)ppp
(2)²T)
inf (1 0p
1-
T
T
S Se. (46)
G
Note that we have yp = y. when T
6. (I-oPop
GP s
of p.)
By
45 and
1/2, we can find
D2
17
(1²²
+
In 2 3 G2
F( 1 F. 00
1/T'
T
4-2 4-4
2 2
In 2- = 3
T 1
03
01
+ o
01
Plug in 77 = 77 (see (40
to conclude that F F(x7x1)
Fx converges at the rate of
(o D
2 2-
0ē0 01
In -n | D
3/
(p In }
GD
0
o
+
T
VT
Recover the existing rate in Liu & Zhou 2023). Remarkably, our above analysis is essentially
tighter than Liu & Zhou| (2023) To see this claim, we bound Ag7x in the following way (take the same a 172 as Liu & Zhou (2023) for fair comparison):
1
13
7
2 in
3
8
+ +
2
PT
0300
72p-2
2p-2
T
o 29 02
72p
T
G2T
(0)
3
0.0
2p-2
2p
0
17
2 In2
+ of
2 PT +
22p-2
T
72p-2
T2 G2T
0 2p
1
2 In 2
+ +of
PT
2p-2
T2
+ GPT
where (a) is by T
2
G = 2G and (b) holds due to 0, S or.
Under the choice of
I-a
" min 1 A used in Theorem 3 of Liu & Zhou 2023).
GVT: :
have
x²
o T
x2
3
))
AgAx < 0
In2
2 + 1
0
In2
+
T
"
PP
2p
7
5
2p
25

---

Published as a conference paper at ICLR 2026
where the second step due to we replace 7 with max [2, T
2 I
+
T + 1 (by AM-GM inequality) and 1 S In2 g. Lastly,
FF
given in Theorem 3 of Liu & Zhou (003) to obtain
X2
o 2p In
))
AT
0
72p
Combine with (41 to finally have
D2 + X2
In 3
+
28 7T
F(XT+)) -F.5O
T/T
which is the same rate given in Liu & Zhou (023)
(see their equation (7)), implying that our
analysis is indeed more refined than
Liu & Zhou 2023
Unknown T. We move the case of unknown T. Theorem 11 in the following gives the anytime high-probability rate for Stabilized Clipped SGD.
Theorem 11. Under Assumptions
72 (with = 0), 3 and for any T E N and ò E (0, 1]. setting
"
min 7x:
T1 Vt
TE max a T VI VI [T]
where a = 1/2.
T,
D/G
D/G Vol
A
(47)
P.V. + In L
In2 +
3 8
2
and w. A 11+1o p., then Stabilized Clipped SGD (Algorithm
guarantees that with probability at
least 1 - 8, F(xx+1) F. converges at the rate of
(p.V, + In 3) GD
Go : SGG D
0
11
03
0 In 1n=-;
338 D
VT
T 5
Proof. By the same argument for (11 in the proof of Theorem 10 1 6,
we have with probability at least
D
2
F
F.
(48)
1T+17 T
T
where A is constant in the order of
max T LE(T)
In
3
+
T
2-P
+
T
0,0
T
o
GT
T
Gm
aP
[=1
(49)
When 7) = min
v
7
n
= max
T(t
} Vl E [T] for nonnegative 7. À and т,
we can bound the above five terms as follows.
Term I. We have
(1 a1 + (T()) (T(b)²) 2)
T/G²2
max rE[T]
T In
< max [T
In2
G2
ln2 3
= ( (2G² In3
3
< max rE[T]
+ Arti
+ Ar In2
T
(50)
(1
0)²
26

---

Published as a conference paper at ICLR 2026
Term II. For any t [T], we have
2-p PS2 1 (1 a1-a)2p + (T(E) (rlt) 2-p) ) 5
G²-p
G
A
T
(1 -1 a1)----P
(Tt
p-I.
which implies
nofG2-
dot T
of p p
(1 (1-a)z2 VT
(51)
TP-1
Term III. For any t [T], have
T
p21 v/(Tth)
VX
p-1
(
(
which implics
0
1-
v T
s 0
vā
T
(52)
7P-3
Term IV. For any 8 E [0, 1), we have
T
T
oG n
//oaG
Σ
(
?
(53)
aP-i
ap-1 1
aB-1-P
where
1 + In 1+ 3/
==0 BE (0,1)
(3,1))
(54)
Term V. We have
T
T
G2
Σ
G
S
Σ
0 (1TPVT)
(55)
Vi
1=1
We plug
50).
51.
52
53
and
55) back into
49 to know
A
<0
22p-272p a
(1/7) 2 (n))))))")(
GP
G2 In 3
+n
(1 a1- + +0²) VT
of
(1 - a)
of
0.020-1 2p-2
+\ Tln
+ -P-1
+
T
vB = [0.1]
-2p-1
Combine the above result with 7, = min {
7, t/.
d
and (48) to obtain
rt
D2
0 (m/")) (B.T)
G 1n (1-a)²
Da + n (1-ap--5 + 6
( ofG20
F F(x(x1) F. 50
7 +
n20 2720
9
VT
D²T
X + >
T In2 (3)
+
-
of
00 20-2
-1
vB E [0.
(56)
T1-3
27

---

Published as a conference paper at ICLR 2026
Finally, conclude after plugging in Tx, = 7, 1/., A X, (see (2) and 47 and the following fact:
1/2,
inf 7+ Ae(o.1]
1/4 7/+
13.
T
47
D/G
inf (p.0))) (3,
P+P' sElo.1]
D/G (1- )0 (3.. where B. max (In (bx
PAp
D/G e² max {Iu (...)))22))
Putlie
D/G
=0 (DIG
(
o
(1 1n² 4p- + In
w/s)) +nn12/)))
1/4
1att/
f++
where the last step is by In th. 2 1 1+ In ip, S v2 (since v. In (p, and pp, 2 1), and
s/. 2
As one can see, the only difference is the term versus the term p.th. the former of which satisfies & I 9.. This change should be expected as the precise value ip depends on T (see (46)). Moreover, recall that y y. once T exceeds
We first compare Theorem I with our Theorem 10
Ω G² of p.). Hence, roughly speaking, the only loss in Theorem 11 is an extra multiplicative term
th., which never grows with '' and is in the order of
maxx
{ (V In
den 1p <
p.
This positive result, i.e., extra poly poly(In?) (In Appendix C
term, is due to the stabilization technique, as discussed
Without considering the extra stabilized step, following a similar analysis given in Appendix F later, one can show that for any general stepsize d and any clipping threshold т. 2 I Clipped SGD guarantees with probability least (assuming that f)e nonincreasing for simplicity).
D2 + Agrx TTT
F(XTX)) F.
(57)
where Agrx is in the order of
T
T
T oeG
2
T
max 2_2 ln2 (E[T]
+
2 11
p
2-P
+
0
Σ
G2
(58)
a a1P1-7
As sanity check, when 7)t = T. V. [T), Aprx /n coincides with Apr given in (43) If T
unknown, even ignoring all other terms and only focusing on ΣT G in (58. the final of Clipped SGD by (57) will contain a term Σi= /2n (Tr which is however well-known to give an extra poly (In 7) factor for time-varying stepsize 1)--
Now let us compare Theorem I| to Theorem I in Liu & Zhou (023). The latter gives the current best anytime rate for Clipped SGD follows (actually, this can obtained by (57) and (58) above):
(n)++nrr) (
GD
o. -
F x
F. 0
VT
Similar to our comparison when T' is known in Section 4 one can see that our Theorem [1 is better (at least in the case of large 7))
1.2 IN-EXPECTATION CONVERGENCE
Known T. Now we consider the in-expectation convergence. Theorem gives the first rate
d off DT faster than the existing lower bound (T Nemirovski & Yudin 1983
Vural al. 2022
28

---

Published as a conference paper at ICLR 2026
Theorem 12 (Full statement of Theorem T E N, setting The = TI max
Jny Under Assumptions 7 (with μ == 0), Band 4 for any
7.T
v } vt E [2] where a 1/2.
D/G
D/G
D 3-1
7 = min
S
(59)
(oP/GP+
0
01
TTb
and G G. a constant defined in 60 and equals G.. when T a
p.)
then Clipped SGD
(Algorithm 7y guarantees that E
[ [F(x7+1) F.] converges the rate of
G
+G) D
2-3
@GD
O
+
T
VT
T
Proof. By Lemmas 5 and
6 we can follow a similar argument until (44) in the proof of Theorem 10
to have
D2
2
E
F
- F.| 1
+
T
TT
T
where, under 1/2 = 17, = max
I-a -T Vt = [T]
for 77, T
> 0.
(1- a) 28p 01
2p G 2pp
G2G2-
BT <0
17
8E(0.112)
inf
a22 2- 2- B)p
T
(1 (1- + G2) (2) T
0 2p-2 2
trj
of 2
+
T
22 2-
Now, we plug max
Fx (see
36
into the above inequality to have under the choice of
Vt
E [T].
B 0 " 2p--2 +
(1-0)-0 + +2²
GPGP
4-2 1- T [+o)
-
$1+))
$7:
01
where the first term obtained by noticing
(1 200p 01 -200
722_
G
(1-
-1-
(1-8)p
0 G
Sp
T
2
220-277- 21 91
2-
1(1-0)p 7x
G2
0 3p
2
(1-a)995
T1
2
(1 - -1)20 0:
G2-
G2
inf 8E[0,1/2]
23 <
272-27?(11 (1
(1pbppp
2-
in which
inf (1
8P
01 G
Sp
8
min
5 (1 app (g)
$ p.. (60)
Note that we have ; = S. when T 2
G
= s
of px
G
By above results and a 1/2, we find
D2
G²
(aPC2-P G2) + no? a, 4- + (7
E [F(XTX))
F.] <
+
TTT
T
Plug in 17 7,, (see 55 to conclude that E [[((xxx)) F.] converges the rate of
G + G) D
GGD
0
D
o
+
T
VT
T--1 1
29

---

Published as a conference paper at ICLR 2026
Unknown T. Next, we consider the in-expectation convergence for Stabilized Clipped SGD. This anytime rate is also faster than the lower bound (or -
Theorem 13. Under Assumptions
(with = 0). and for any T E N, setting =
min
V Ve F.00 f T Ft max 1 J. ,. E [T] where a = 1/2 7+:
D/G 74
G.
7/
Vop/GP+1
D/G
X.
o 22007 20
D
(61)
and v.. A 11 G.. then Stabilized Clipped SGD (Algorithm) converges at the rale of
guarantees that E [F(941) F.]
(o+
+G))
F.O.GI
GD
0
01 D
+
T
VT
T
Proof. By Lemmas 5 and
6
we can follow a similar argument until (56) in the proof of Theorem [1
{ (t e [T].
to have when min 7, -
To
max
rtF
D² +
o (1/77)
Da
of of +1 (1-0)2-p + G2
F(xT+1) - F. 50 50
a2p-1y2p
T
VT
D
+ X
TP-T
+
2022-22 ppp-T
BB E [0.1].
-111
1 + In
3=0
where (B,
is defined in (54).
B (0, 1]
Finally, we conclude after plugging in r F.. = "n. A x. (see 36 and 61), 1/2, and the following fact:
inf sE[o.1]
7/a
174
2
(B,T)
61
D/G
inf (2.0.)" (2(B,TT
G.U.
sElo,1)
D/G
(7.0.)) (3((..T) where B. =
2
2.
In (priis) .2
max
D/G
c²
(1+ max IIn (5.0%) :2))
2
G.v.
D/G
(1+ G. + In2 $.)) )) 0
D/G ~
0
6. v
G.0.
where the last step is by Ing. < 2/ Vnn 1 +
2
In2
J (since v. + In S. and S. > 1), and
V. 2 1.
Compared to Theorem 12 we only incur extra multiplicative term J. 1 + In 1 1+ In (dan Ip < 2)) in the higher-order (T--1) part.
E.2 STRONGLY CONVEX CASE
We turn attention to strongly convex objectives. In this setting, recall that x denotes the following weighted average iterate after T steps:
ΣT (t + 4)(t+ 5)xc+1
str X++1
(62)
Σ Eh (t+ 4)
30

---

Published as a conference paper at ICLR 2026
E.2.1 NIGH-PROBABILIT CONVERGENCE
Still, we first consider the high-probability convergence rate. Theorem 14 gives the anytime high- probability rate of Clipped SGD improving upon Liu & Zhou (003).
Theorem 14 (Full statement of Theorem
2 Under Assumptions
2 (with > and for any
T E N and (0, 1), setting 7)t
pat Te max
I-a: T,t fo 1,v [7] where a 1/2, then
Clipped SGD (Algorithm) ! guarantees that with probability at least 6, both F(x)4+) F. and |||x++1 x=2 converge at the rale of
DD
(00 +n
G2
(op
G2-D+ G2
+ 0b of
1 2-2 4
2 +
1
In
O
T
μT²
PT
pl
where :p S. sp, is constant defined in 46) and equals sp, when T = l
of p.)
G"
Proof. First, the choice of π7- = Vt E [T] satisfies 17 I 3 Vt E [T] for = 6. fulfilling the
requirement of Lemma 7 In addition, our choices of 77, and T also meet Conditions | and 2 (with
1/2) in Lemma Therefore, given T N and 5 E (0, 1]. Lemmas 7 and together yield that with probability at least --6 6,
T441 Xx XT
T
Σ
Pem (F(x(+1) F.) S 4D2 + 2AT
Tr+1 |X, x1+1l? El= Ton (F F.)
4D + 2.7 Σ I'm
(63)
T 2 "Σ Imm
Σ Pim
where I'
-IT [T
1+ is introduced in 955 and Art a constant in the order of T+,n./2
0
max
oi LE(T]
2 I
3 T3 In2
o
I
Ml
2 2-P
TTTun
2 2-p
GP
In
3
ap-17
8
0
2p
TTme
Me
22 G
1 +
Ge
(64)
2p
a 2
Tt
We use 17:
pet Vt E [T]
compute
pMs
8 8 5
4)(++))
r,
V T +1.
(65)
1 12
8 4
30
2=2
s=2
So for any t E [T].
(t+ (++4)(t++ +5)
6t
6(t + 4) + 5)
36t
T
S
and
To
S
(66)
54l
1
5/1²t
112
implying
T
T
4) +)
T(T + 157 + 74)
mmm =
(67)
5p
15p
Lastly, let bound (63)
For the L.H.S. of (63 we have
T241
65.67
65
67
(T + 1T (T + 6)
+ ()
3p
> min
2 2Σ Tm In addition, we observe that
4T + + 74)
TEN
4T +17 +7)
16
1= I lemp1
66
-1=1 (t 4)(t + 55xx++1
62
estr
Σr 1== l'm
Ele ++44) +)
XT+11
31

---

Published as a conference paper at ICLR 2026
The above two results and the convexity of F together lead us to
3/ X,
x 2|
F(x7+1) - F. S L.H.S. of (63)
(68)
16
For the R.H.S. of (63 we plug 67
back into (63 to have
nD + HAT
R.H.S. of (63)
S 0
(69)
7
One more step, we use 66 to upper bound (64) and obtain
T
ofGit
8
PAT S
max SE(T]
Te
In
+
Σ
o Tt
2-
+++)
Σ
o
2 2-Pt +t
ap-1T?
In
111
0.
2p-2
o
G2R
+G
(70)
2p
2
27
2p
IV
When 7, -max (1 Vt E [T], control the above four terms follows.
Term I. We have
max
(E[T]
3 g
T
In
3
g
1n 2
a)
T
+
In2
3 7
r
(71)
Term II. We have
T Σopt
p32
o'G2-p
222--T22
(1- a--a)--p T2 + of 7
(72)
Term III. We have
T
PS2 2
Pt
2-22
<
72 + o. 2
a)
and for any 8 E [0, 1/2]
r
(11-a)3pof G2-Bp
$
00
(1-1)p110)p T1+
3p
(1-8)p
t=1
aP-1
T(P
1-o
Thus, for any 3 E [0.1/2]
G:G G2t
3
Σ
T
2- 1/
j
a 7P
G²
(1- o - 3p
3 In 1n 5
<0
T + 2-
T1+8
(73)
(1--a)2-p
2-p
ap 1 B)p
Term IV. We have
T Σ
0
2p
2
p21
0:01 2p
1+2
2p-2
7 2p
Tt
32

---

Published as a conference paper at ICLR 2026
and for any 8 [0, 1/2].
T
28 t2
T
o G222
Σ
2p
rt
2p
1=1 a 2--
TTF
2(1-B)p
1-a
(1 - a)) 0.0000000 01 (2(1-pp)
0
T1+28
a2p 2220-22(11- 2 33p
Hence, for any 3 [0, 1/2].
Σ
r
0 0
2p 2p-212 22
0 Gat
2p-2
a2p-2 2p
Tt
0,00
(1 - a 2 2p (2(1 0p)
0
T +
+
0
1
(74)
-2p-2
2p 2 11-p1 3/p
Next, for any fixed 8 E [0, 1/2],
R.H.S. of
71 + R.H.S. of
G
1n2
T +
(1 a) 20 a (2(1-9p)
71+28 + + In2
3
T
0/00 2p-2
T 1+
(1 ))²
a (
2pp-2
(a)
(1 a) - In
3
3
22
T1+
20,00 - 11 In
T
(1 a)a 1-(1 B]p
(b) (1 a) o G2- In
T 8 + 5. -
a 1 B)p
of
In G
-R...S. of 73
2-p 87
where (a) by AM-GM incquality and (b) is due to < 1, 01
0, and p 2 Therefore, after 733. and (74) back into 770 we have for any 8 E 10,1
plugging 71.. (22)
a:) P
G2 In 2 8
(0f + of In 3 G2-D
MA S
8
T+
+ T2
4 aP (((-)
(1 )
(1-a) 2 2-p
7 In
3 8
+
-
0.000 2p-2
T T ?
22p
Combine the above bound on μA#
and 69
to have for any 3 E [0, 1/2],
G² In?
(1-a)) 1--1-11- 310 1
2
1D
(1-a)
+
R.H.S. of 63
00
T3
HI2
(of+o In c
G2
2 In2
-p-2-p p
-6020- 20-2--2
(1-o)=
(75)
2
We put (68) and 75 together, then use a = 1/2 and argument of (46) to finally obtain
(see
32 ) and follow the same
3/4 1x, Xr+Il 1
F(sttr - F.
16
nD²
(6² + In
G2 G² +
(of
+o In c++
G2
a 4-2
0 T
00
T3
nT
33

---

Published as a conference paper at ICLR 2026
E.2.2 IN-EXPECTATION CONVERGENCE
Next, we consider the in-expectation convergence. Note that Theorem is also the first result that breaks the existing lower bound (oFT -2
Zhang et al. 2020).
Theorem 15 (Full statement of Theorem 4p. Under Assumptions
2 /with μ > 0). 3 and 4 for
any T E N, setting 1 jut Tt max
I-a T VI. [T] where a = 1/2, then Clipped
SGD (Algorithm guarantees that both E the rate of
F(x7+1) F..
and μ.
||x+1 x. 11 converge at
$ 4-2 1-
nD²
G2
G
0s
01
+
PT
2
where $ S f is constant defined in 600
and equals G. when T
S2
of p.
Proof. By Lemmas X and 9 to have
we can follow a similar argument until (70) in the proof of Theorem 14
|x
x1+1
1uD²2 + +uB
[F(x++]]
E
F.] so
(76)
16
T3
where
1
o
o
2- Ptt
0
2 G2t
+G²13
11
Tt
2p
a 220
When 7. = max
G
T |
14 E (T], we know
I-ai
p GPG2-p
722 + -
o
(1-a)2-p
and for any B E (0,1/
T
0
2p 2p-222 22 2p
G2P
0.00 2-
(1 - 2000p0p 0² G2(1 (1p))
0
T
p
T
27
-2
2pp-2 2 ((-11)
1=1
Therefore, we can bound
1 n Betr s 0
2
GP
1
7
T
(1 a) + G2 7e
0/00
2222
2p-2
+ op-2-D
T
./ e [0.1/2].
(77)
-2p-2
76 and 777 together, then use a = 1/2 and argument of (60) finally obtain
We put
F. (see 36 ) and follow the same
3μE
||x.
X1+1/1
E
[xxetr - -F,]
16
PD²
G²
G2 G²
05 0
<0
+
7
n112
pT
2 2
34

---

Published as a conference paper at ICLR 2026
F THEORETICAL ANALYSIS
This section provides the missing analysis for every lemma used in the proof in Section As discussed in Section 5 our refined analysis has two core parts: better application of Freedman's inequality and finer bounds for clipping error.
Before starting, we summarize the frequently used notation in the proof:
X2 x, the optimal solution in the domain of the problem X.
.
D = ||, XiIl, distance between the optimal solution and the initial point.
F = (f1. ... Ex), the natural filtration induced by i.i.d. samples &1 to & from D.
B: g(x, E,), the stochastic gradient accessed at the t-th iteration for point x,, the clipping threshold used at the t-th iteration.
gi clip,, (gt) = min { 1, | gt. the clipped stochastic gradient.
d gi Vx((x,) difference between the clipped stochastic gradient and the true gradient.
dj' gi E lgg Fi-1], the unbiased part in dē.
d = E lgf F(-1] - [x{)), the biased part in dç-
F.1 GENERAL LEMMAS
We give two general lemmas in this subsection.
First, we apply Theorem 9 to obtain the following error bounds specialized for clipped gradient methods. As mentioned, the technical condition required in Theorem automatically holds for clipped gradient methods.
Lemma 2 (Full statement of Lemma T. Under Assumption 4 and assuming 0 < To
Fi-1. then for d. gi [gi Fi-1l. d, = E [gi Fi-1l
vf(x)), and Xc(a) =
[11 a) [F(x)) Va E (0, 1), there
| S 2T.
2. E || Fr-1 < 40/
3. E ay (dy) T F 40 +4 [f(x))]
4. E d (d:) T [ xe(a) - 40 2-p 40 of
5. |abll S V2 (0) - [V](x ||
T.T 1-p + 2 [V) T.
6. |ab (e) S -- 1-p a Vf(x))) T.
Proof. We invoke Theorem with Fi = gr. f vf(x)). g g(x, T T d" = d. d = d, and ((a) = X² (a) to conclude.
Compared to Lemma] [ the clipping threshold T. could be time-varying and random. Inequalities
and d provide further (though minor) generalization by a new parameter a, which might be useful in practice as mentioned in Remark 11 Especially, setting a = 1/2 will recover Lemma [ and 6 are all finer than existing bounds for
Moreover, as discussed in Section 5) Incqualities
clipping error under heavy-tailed noise.
We then discuss Inequalities 3 noot provided in Lemma 1. As far know, both of them new in the literature. As one can see, we do not require [|V((x,) (which turns out to be G under Assumption
up T, now, which we believe could be useful for future work.
Next, we give two one-step descent inequalities for our algorithms. The analysis is standard in the literature, which reproduce here for completeness.
35

---

Published as a conference paper at ICLR 2026
Lemma 3. Under Assumptions
2 and 3 for any
Jny y X and E N:
Clipped SGD (Algorithm guarantees
y
xell" (1 + pm)) ly x 11?
F(xx+1)-F(y) 2
+(d,,y - (oxyy-)))+in +4m
2fte
21
Stabilized Clipped SGD (Algorithm guarantees, if the is nonincreasing.
F(x++1) - Fly) y -xx: x11
(1 + pmn+11 lyy x++1ll
(
_ 7/.
lly x1l
21)
21/(+1
1/+1
2
+ -di, xxi) + + 1|d111 + 472
Proof. By the convexity of f.
f(xx+1) - f(xx) S (VI(((+1), X -Xt)
(VV((x++) (x(x),, X xx) + (V xx+1-xi) -xx)
Recall that dj = gi - v)((x),, we hence have for any y E X,
(V](x)), X1+1 - x1) (df, X X(+1) + (g): Xt-1 yy) + (di -x) + (V)(x)),) xx)
(dl, Xx xx+1) (g): Xt-1 -y) + y xx)) + y f(y) f(x)),
where the inequality is, again, due to the convexity of f. Combine the above two results to obtain
[(x++1) - f(y) S (VI(x(+1) - (x(), x - xx) + (d., X X
II
+ X1+, - y) + y
(78)
Next, we bound these three terms separately.
Term By Cauchy-Schwand inequality, G-Lipschitz property of f. and AM-GM inequal- ity, there is
(VS(x(+1) Vf(x.), Xx+11 xx) < [V[((++1) vf(x)))] ||xe+1 xxel
S 2G [x - xxIl S 4n + ||x+1 x=
(79)
417
Term II. By Cauchy-Schward inequality and AM-GM inequality, we know
||x++1 - x, 1|
(d), x x(+1)= & ||d Xx+1 - x, || S 7h ||d]]|
(80)
4n
Term III. For Clipped SGD, by the optimality condition of the update rule, there exists Vr(x++1) E Or(x(+1) such that
Vr(x++1) + +g.
Xt-1 - Xt Xx+1 - y 50,
T1
which implies
(g) X y)
Xx X Xx+1 y) + (Vr(x++1)s) xe+1)
ly -xel2 - Ily xs+1|1 ||x++| - xxIl
+ (Vr(x++1) x(+1)
27
ly
x
Il X 11
| x + r(y) r(x(+1) - 111 -x++1
2mp
(81)
36

---

Published as a conference paper at ICLR 2026
where the last step is due to the μu-strong convexity of (Assumption For Stabilized Clipped SGD, a similar argument yields that when 7) 2 7)++1
x1l1?
lly
x++1l1
Xx++1
ly
x1|l
(B), X y)
21
20++1
217c
9++1
T/
r(y) r(x(+1)
2 byy X
(82)
We plug 79
88 and (8)) (resp. 82 back into 788 and rearrange terms obtain the desired
result for Clipped SGD (resp. Stabilized Clipped SGD).
F.2 LEMMAS FOR GENERAL CONVEX FUNCTIONS
In this section, we focus on the general convex case, i.c., μ = 0 in Assumption 2 As mentioned before in Appendix C it is enough to only analyze the Stabilized Clipped SGD method since it is the same as the original Clipped SGD when the stepsize constant.
F.2.1 TWO CORE INEQUALITIES
Before moving to the formal proof, we first introduce two quantities that will used the analysis:
R₂ max SEId]
|X+
xx1l
Vt E [T], and N₂
&
X, Xx
vI E [T].
(83)
Te
Re
Note that Ri E F and No E Fi by their definitions. Importantly, No is a real-valued MDS due to
E[N Fi-1== ( M [d, Fe-1),
X X.
= 0, Vt [7].
(84)
RI Th
Now we are ready to dive into the analysis. We first introduce the following Lemma which characterizes the progress made by Stabilized Clipped SGD after T iterations.
Lemma 4. Under Assumptions 7 (with μ = and 3
if ne is nonincreasing, then for any T N,
Stabilized Clipped SGD (Algorithm) guarantees
x.
X1+1
D
F(x++1) - F. + 21
21/T+1
1/++1
1=1
where
2
TCVX 8 max
Σ N₂
2
Th
|
Σl
ElIvTodPl)
402 Σ n/-
(E(T)
Proof. We invoke Lemma 3 for Stabilized Clipped SGD with μ and y x.. then replace the subscript with and use x. - X1 = D to have
|x. xxll 12
||x, x++1l1
D
F(x++1)-P2
+ (d x. - +x) +4
211s
21/++1
7-+1
17s
sum up which over from to < T to obtain
xx. x
D2
F(x++1) - F, S
(d x. Xs) +
ns ||d|| 2 + 4G2 Σ 7/5-
21/+11
21/1+1
(85)
We recall the decomposition d; =d + dh to have
Σ (d X, - x.) = Σ x - x.)+
(bb b X,
83
R
N.
1/8
d
X. X
==1
8=1
37

---

Published as a conference paper at ICLR 2026
We can bound
Σ R.N, <
Σ N
Lemnna 13
S
2Rd max
N
SE(1)
In addition, Cauchy- Schwarz inequality gives us
VTd.
x, X,
7.d
|x. x
83
R
Te
T/
As such, we know
Σ
(d x, x2) 24 max
Σ N
+ Rs Σ
SE(A]
R²
$
8 max SE
N₂
+
Σ
(86)
4
where the second inequality is by R,X &
R
+ 2x
(due to AM-GM inequality) for
2 maxsel(] Eem N₂ and E |l TT respectively.
Plug 86 back into (85) get
X,
X++1
F(x++1)= F+
21/++1
2
R
D
max SE(A]
Σ
N₂
+ Σ
Σ
n
||d%||
4G2
Σ
f10
2/tt 1
2
2
R2
D2
8 max SEl
Σ
N
+
no
||d
+ 4
Σ
|v
4G2
17
4
21/-1
1
(87)
where the last step is by
Σ ||d
= Σ
d + dbb1 < 2 Σ
no ||d:112 + Σ no ||abb|
s=1
2
< 2
T/s 1 +2
Σ
|
s=1
Now we let a A |xx-xxl
Vt E [T + 1], b Ei= F(x++1) F., Vt E [7] and c2 - D2 + 0. Note that b, is nonnegative, is nondecreasing 7
1e2,, Vt [T + 1] where
1
nonincreasing, and
|x, - 11
D2
D
<
201.
2m/1
2m/1
171
Moreover, 887 is saying that
max as
a++1 + b
+ C1+1, VI E [7].
2
Thus, can invoke Lemma
14 to obtain
aT+1 + by < 2CT+1.
which means
x. - 1
T
D
+ Σ F(x++)) - F, <
+ 21
2
1/++1
t=1
38

---

Published as a conference paper at ICLR 2026
Equipped with Lemma 4
prove the following in-expectation convergence result for Stabilized
Clipped SGD.
Lemma 5.
Under the same setting Lemiaa
Stabilized Clipped SGD (Algorithm) 2
guarantees
B
XT+11
T
D
B (x++1) - P.]
+
2JT
+1
4/+1
where
27
34
||
4B
II |1
46
n|-
Proof. We invoke Lemma 4 and take expectations to obtain
|xx -x+111++112 11+
T E [F(x++1)
D 1T+1
- F.]
+ 23
[17
2
1=1
where, by the definition of 1770
27
I
27
T Σ
|
SE
max BETT
Σ
N₂
2
E
|
+
4IE
Σ
n
+
4G2
?/-
Recall that N₁, Vt E [2]] is a MDS (see
844
Therefore, by Lemma 12 there is
E
max LE|T]
Σ
No
E
N2
83
||ll 2
t=1
Finally, we have
T
(Σ
27
T
CvX
34
E
||411|
+ 4E
+
4G²
Σ
1/p = J
1=11
F.2.2 BOUNDING RESIDUAL. TERMS
With Lemmas 4 and 5 next goal is naturally to bound the residual terms IT and J Note that the G2 Ei Th part is standard in nonsmooth optimization. Hence, all important things are to control the other terms left.
now provide the bound in the following Lemma 6 a tighter estimation for the residual term compared to prior works (e.g., Liu & Zhou (2023)), which is achieved due to finer bounds for clipping error under heavy-tailed noise.
Lemma 6. Under Assumptions 3 4 and the following two conditions:
1. Mi and deterministic for all [T].
2. T I-a
G_ holds for some constant a E (0, 1) and all t E [T].
We have:
1. for any 8 (0, 1]. with probability at least
Ixvx < A where I defined in
Lemma 4 and A is constant in the order of
T
T
2
T
0
max T T
In
3
m
0e0
lt.
+ Σ
G2
6
a 1
T
1=1
t=1
39

---

Published as a conference paper at ICLR 2026
2. J S Bxx
where JT
is defined in Lemma 3 and Bi is constant in the order of
Th
p-1
G/G/ V
T
o
1
Σ
aP 17
Proof. We observe that for any / E [7] T 2
C
2
[[x)) holds almost surely due to Condition
I-a
1-a
2 and Assumption 3 implying that (a) in Lemma 2
equals for all t E [T]. Then Lemma 2
and
Assumption together yield the following inequalities holding for any E [T]:
Inequality
Ivndil
TETE S 2 max VIETE. 1E[2]
(88)
Fe-1 4of TC
Incquality
|V E
(89)
Inequality
4 ne
40 G2
E bd (d.")
Fi-11
(90)
ap p
|| |/
Inequality
0
v +
G
(91)
Tp-1
a
7p
We first bound 1ate in high prohability.
Recall that N₂ ( TT R. /
Vt [T] real-valued MDS (see (84 ) whose
absolute value can be bounded by Sauchy-Schwarrs inequality
N < | dill
X
max VET EE[T]
Re
Moreover, its conditional variance can be controlled by
N2 Fi-1] X, xx
Rs Te ndd (d.)
X, Xt Fi-1
ne
[ 4o -P--
40 G2:1:
E dh (dy) T
a aP-17P
Therefore, Freedman's 's inequality (Lemmal 10
gives that with probability at least 1 25/3.
3 +
o
o.G aP-173
3
N
S
max TeTe In [E
8
+
In
Ing.
vt
[T),
3
8
73
#=1
which implies
t
2
25
3
o ne
of G2 me
3
max (E(T)
Σ
N₂
S
max 7 In2 2
16
+
In
(92)
9
[E|T
oD
aP-1T?
Note that
Vt E [T] is a sequence of random variables satisfying
40 n
2 max Vie. and E [IVTT Fr-1 E
Then by Lemma 11
we have with probability at least 8/3.
T
Tc | 2|
<
14
max of
2 In
3
+ σ
>
T
ne
In 321
max
In2 3
+8
>
T
o n
3 [[[]]
p
3
[E[T]
7 p-2"
1=1
(93)
40

---

Published as a conference paper at ICLR 2026
Lastly, there is
91
T
ogo
v
ll
dil
(94)
r--
a aP-17?
Combine 92
93
and
(94)
to have with probability at least 1 - 8,
T
2
T Σ
1 8 max 11
Σ
N
+
||
+ 4
11 v )
+ 4G2
n1 S A7x
[=1
where
1
A
2
28
In
3
+ 16
oim
128 p-2
Σ
0 1]
o GP
In
3 6
3
(E(T]
8
ap -.
+4 4
05 p-1
V
o QG
4G2
T Σ 1/c
p
aP-1 1
1=1
3
T
ofG
3
max [E|T]
T In
+
in
P-2
p-2
aP-177
p-
Th
of G
2
Σ
T
GTT
aP-17!
Note that by AM-GM inequality
T
2
max T
2
3
+
Th
(E[T)
8
Tt
aP-17p
O5oP p-1
3
22
max VITE (E/2)
In
aP-1
8
(a) 2
nl
3 (
o T
Gf
of
3 In
In
2
P-2
(1 - a)-
p
ap-177
8'
I-a in Condition and (b) is due to σi 2 os. p and a E (0, 1). Hence, the order of Aq can be simplified into
where (a) is by Ti 2
2
3 J
T
T
p-1
Vit
GT
2
T
max MTT EE(T)
In2
+
+ + G
p-1
ap
aP-l7?
Now let us bound JøYX It can be done directly via 89 and claim J S Byxx where Bex is a constant in the order of
91
Hence, we omit the detail and
ooo p-1
/
o GG aP
2
T
o
dh
1=
t=l
F.3 LEMMAS FOR STRONGLY CONVEX FUNCTIONS
In this section, we move to the strongly convex case, i.e., μ > 0 in Assumption that we study is Clipped SGD.
2 The algorithm
41

---

Published as a conference paper at ICLR 2026
F.3.1 Two CORE INEQUALITIES
We begin by introducing some notations that will be used later:
r pTs-1 12 [T+1]
(95)
which satisfies the equation
T + pm)) = 11+1 -1 Vt E [T].
(96)
Equipped with r,. we redefine
A max R2
VT,(1 + pm,/2) ||x, xx,1, [T),
(97)
sE((]
1 1 ". VT(1 wiue (xx, xx)
Te
N₂ -
.t E [T].
(98)
Rs
By their definitions, R2 Fi-1 and N₂ E Ft. Moreover, N₂ is still MDS due
E Fi-1l= = (1 r.
1+ um/ m E (d Fi-)). VT + pm (x) xx)
0, -0, v4 E [T].
R₁
(99)
Again, we first show the progress made by Clipped SGD after T steps in the following Lemma
7
Lemma 7. Under Assumptions /with μ. 0) and if S 2 for some constant v) > O, then for any T E N, Clipped SGD (Algoritmm 7
guarantees
TT+1 ||x, - XT+1| 2
Tem (F(xx+1) - -4) s (1 + n/2)D² + 2
2
where
1
2
T Fom
2m T +
T
1st A 4 max
Σ
N₂
||d]||
Tem || + 4G2
AE(T)
1=1
Proof. We invoke Lemma 3 for Clipped SGD with μ and y = x., then replace the subscript
with s, and multiply both sides by T,7,, to have
Pan (F(x++1) - F.))
F xx,
x²1?
[o(1 (M7 1x, x9+1l1? + (T, - xx) ||]] + G
2
2
96 r. Ix, x,1
[1 + 11)) -x+t1ll
+ (Tsdd, xx) xx) 1d:l + 41 .2
2
2
sum up which over form 1 to < T to obtain
T241(1 + 212 ||x. - X1+1
Σ
r Te (F(xo+1) - F.)
==1
D1 |x,
111
".. ||x, 1
Σ
( To 1x,xx,xxxx -x,) + Σ r 1 |d]]|
46 Σ r r.m
2
8=2
s=1
D2
#1
Σ
P.ma ||x
x=
(I da x. -xa) + Σ
r n 2 | 462 Σ ma
(100)
where the last step holds by T, and ||x, X1|| = D.
42

---

Published as a conference paper at ICLR 2026
We recall the decomposition d. dp + d to have
To xx)) ( n. X. -x,) + Σ (T (Tnnd -x,)
Σ R,N, Σ
(T (T.. xx))
By Lemma 13 and AM-GM inequality, there is
R
8
2
Σ
R,N, S 2R, max
N
S
max Seld
Σ
No
SEl
4
In addition, we use Cauchy-Schwer inequality and AM-GM inequality to bound
||
uI M7s
||x
-x,1l"
(Tandd,, xx)
r.m || ||x,
xx
1
4
As such, we obtain
(Tn.d X. - xxa) S
R²
+ 4 max
Σ
N₂ +
r n
|
17
Xx.
Xx
4
sE((
4
==1
(101)
Plug 101) back into (100) to get
I 11 1 /2) |x. X
Tal (F(xs+1) - F.)
R2
(1 + um /2)
2
Po |dbl1
max SE(A)
Σ
N₂
+
r s ||d
2 4G2
2
R²
(1 + n222D22
4
+ 4 max
Σ N
+ 2
|
+
2n 1
Tome |dbl' 2 + -G
Σ
r n (102)
SE((
s=1
s=1
where the last step is by m S n//4 and
1 Σ T d + a
2 222n 23 |411 + Σ T .n ||abb12
2
Σ T 2 ||d%1| +
21
Σ
r non ||
11 s=1
#=1
Now we let
F.(1+ /2]] 2
Vt E [ + 11, by E._
1 P.m (F(xe+1) - Vt e [2]
2
and [1+m/2)D² + 1sts, Vt E [ 1]. where 1øtt = O. Note that b, is nonnegative, is nondecreasing, and
Q1 ri(1 + pm / ||x, - x1 (1+ n/2)
I (1+ n/2) 2c1-
2
2
Moreover, 102 is saying that
max,elt as
a++1 + b, <
+ C441. Vt E [T].
2
43

---

Published as a conference paper at ICLR 2026
Thus, can invoke Lemma 14 to obtain
ar+1 by S 201+1
which means
T1+1(1 + p1p+11122 122 ||x, XT+1 2
T
Tom (F(x(+1)-)) & (1+n/2)DD + 217
Finally, we conclude from pur++1 2 0.
Equipped with Lemma 7 we prove the following in-expectation convergence result for Clipped SGD under strong convexity.
Lemma 8. Under the same setting in Lemma
Clipped SGD (Algorithm) guarantees
T++1 EE
|x,
XT+1
T
B [F(x++1) - F.] < (1 + 2/2 + 2.17
2
where
T
T
J7
A
18
Ten
|||11]
+
2nj +
r T.m
[|bb1]]]
+ 4G2
> Tmm
Proof. Similar the proof of Lemma 5 we take expectations both sides of Lemma and then The calculations are omitted here to save space.
invoke Lemma 12
F.3.2 BOUNDING RESIDUAL TERMS
Like previously, we need to upper bound 1 and JT which done the following lemma.
Lemma 9, Under Assumptions f and the following two conditions:
1. Tte and Tt are deterministic for all E [T]]
2. T a holds for some constant a E (0, 1) and all E [T].
We have:
1. for any E (0, 1), with probability at least 8, 122 <
A&r where 1x is defined in
Lemma 7 Asti is constant in the order of
3
0 Th
G
3
max Pem [E(T]
2
2
In
+
In
5
ap aP-17p
Tt.
050
2p 2
22 G
2n +
2p
2pp-2
2. J < Betr where J is defined in Lemma and But is a constant in the order of
Σ
T
oT p-2
2p TTm
+ 0 GPG tT
2n +1
+ - GT
T
2p-2
2p 2720
Proof. We observe that for any [T], Tt
G
| [xx(( holds almost surely due Condition
1-a
1-a
2 and Assumption implying that (a) in Lemma equals for all E [7]. Then Lemma 2 and
44

---

Published as a conference paper at ICLR 2026
Assumption together yield the following inequalities holding for any t E [T]:
Inoquality 1
VT ||al]|
2 Te S max
Venae
(103)
CE|T
Fi-1] Inequality
2 40 TemE
E Foml
(104)
T
Inequality
[ 4ofremi mn
Ta (d;)*
Fi-1]
(105)
a IT.
Inoquality
F
VT
G.GTT
VTa
|
+ aP-171
(106)
Similar to
99
we can prove now with probability at least -26/3.
2
ToTTmm
G.GTT oz
3
maax (E(T]
Σ
N
max
Path T, In + 16 Σ
Tp-2
at aP-17?
In
5"
(107)
Similar to (93
we can prove now with probability at least 1 8/3,
T
T
Ton
|لا| <
14
3
EE[T]
max
r
1
2,2 7
In2
3
8
+
8
o
p-2
(108)
Lastly, there is
106
050 1-o0- Tim
o.GTTeM
Σ ce
|
a ap-17?
T
20 2 2p 1
Me
20 2P G 2p
(109)
a 2p--2, 27
We combine 1077
108) and 109 to have with probability at least 1 - 8,
2
T
T
T
1s = 4 max
No
+
r Ton
||
217
+
Dem ||d + 4G2
rim < ATT,,
BE[T]
1
8=1
where
A+
A
27
9
+
28
3
max [E(T]
2
In
3
8
+ 16 Σ
T
o mn
p-2
+ +64
Σ
T
o of'''
p-2
of oG
a 1
In
1=1
t=1
+
Σ
20 2p
01
2 Te7h
20 2p GT
2m + 1
+4 4
Σ
GTT
2p-2
a 22
Tt
1=1
(=1
3
T
T m
of G.G mh
In 3
=0
max
Pime
2-2
In
[E
aP aP-17p
0
i
2p
T
29 G
Me
27 1
Σ G
2p
a2 2
2p
Now let us bound J It can be done directly via 104 and 106). claim Jetr S Butr, where Bett is constant in the order of
Hence, we omit the detail and
T
Tom
0.00
2p-2pp TTm
29 G2 me
2n + 1
0
Σ 1=1
Σ
+ Σ t=1
2p
1.20-277 2p
1=1
Tt
45

---

Published as a conference paper at ICLR 2026
F.4 EXISTING TECHNICAL RESULTS
This section contains some technical results existing (or implicitly used) in prior works.
First, Lemma T0 is the famous Freedman's inequality, useful tool bound real-valued MDS.
Lemma 10 (Freedman's inequality (Freedman 1975)). Suppose X, E R, Vt E [T] is a real-
valued MDS adapted to the filtration F,, Vl. E {0) U [T] satisfying for any E [T), X S b and
[X] Fe-1] S of almost surely, where and of are both constant, then for any å (0, 1].
there is
26
Pr
2 of Σ
8 vt [T]
2 2.88.
Next, Lemma IT is another concentration incquality. This is not new result, and similar ideas were used before in, e.g.. Cutkosyy & Mehta (2021): :: Zhang Cutkosky (2022); Liu & Zhou (2023). We provide proof here to make the work self-contained.
Lemma 11. Suppose X, E RR,t vt E [T] is sequence of random variables adapted to the filtration
Fr, Vi E {0} U [T] satisfying for any E [T], [Xe] S b and E [X] Fi-1] S of almost surely,
where 2 and of are both constant, then for any 8 E (0, 11. there is
T
7b
T 2
Pr
X2
S
ln
+
+
o
21-6.
2
6
Proof. Note that bound
X
E
X2
Fi-1]
E Fi-1] $
Σ 1=1
Yı +
o
YY
Observe that Y,, Vt E [T' real-valued MDS adapted to the filtration F,, Vt E [T] satisfying
Y $ x b and [ F.-1] < | S o²
Then Lemma 10 yields that, for any 8 E (0, 1]. we have with probability at least
26
1
T
Σ Y, S
+
2
82 In 8
vt [T),
3
==1
==1
which implies
T ln
26
T
Σ
Y
<
2
bo
In
<
In
3
1=1
1=1
where the last step is by Hence, it follows that
V 2 2T t=1
boo In 1
< 2 In +
ΣT
of
due to AM-GM inequality.
T
762
T
Pr
Σ x² <
In
+2
o7 21
6
t=1
The following Lemma 12 is the famous Doob's L maximum inequality. For its proof, see, e.g., Theorem 4.4.4 in Durrett 2019).
Lemma 12 (Doob's 's 2 maximum inequality). Suppose X, E I, Vt E [T] real-valued MDS, then there is
27
T
E max [E
X.
<
4
E [x?]
e=1
1=1
46

---

Published as a conference paper at ICLR 2026
In addition, we need the following algebraic fact in analysis.
Lemma 13 (Lemma C.2 in lvgi et al. (2023), Let d1. ar and b1. by be two sequences in such that ae is nonnegative and nondecreusing, then there is
9
agba
S 2a, max SE
b
v [T]
Lastly, we introduce another algebraic inequality, the idea behind which can also be found in pre- vious works like Ivgi et al. (2023); Liu & Zhou (2023). For completeness, we produce proof here.
Lemma 14. Let a1. ar+1. b,.... by and C1 ...... cT+1 be three sequences in R such that b is nonnegative and Ct is nondecreasing, af I 2c1 and
maxsEl4 as
a++1 + b
+ C411, V [7],
2
then there is
aT+1 + by S 20T+1
Proof. We first use induction show
0 S 2c,, AA (T].
(110)
For the base case t = 1, we know 2c1 by the assumption. Suppose 110) holds for all time not greater than t for some E [T - 1]. Then for time + 1, we know
6,20
maxxel!| as
110
max.el1 2c,
0++1
a++1 + b -
C++1
C+11 S 20++1
2
2
where the last inequality holds because is nondecreasing. Therefore, Hence, we know
110 is true by induction.
4T by m ae
IIG
E 2c,
+ CT+1
CT+1 S 20T+11
2
where the last step is also because & nondecreasing.
G FULL THEOREMS FOR LOWER BOUNDS AND PROOFS
Please refer to Appendix the full version of this work.
H NUMERICAL SIMULATIONS
In this section, we provide some numerical simulations to support our theory. We limit our attention to the additive noise model, i.c., g(x, {) f + + where all coordinates & are assumed to be i..d. Moreover, denote by e [E [[])"]
Objective. We pick X Rd, fx) x yll, for some y E Rd, and r(x) Therefore, know = f, F = y and F. = Moreover, we have μ = 0 and = Vd.
Noise. We choose & eZ i.idd. for all E [d]. where and Z are independent and satisfy
that Pr [E = 2 = 3 and Pr -1] 2. and follows the Pareto distribution with the seale
parameter a-1 and the shape parameter a = 0.001, i.c., Pr 1Z > 2] = [==1
(==1""1 2 ا-حج +
p-1 Note that we have E.. [e E [|c|_] 2 and E [2 a-p (e-1) implying
that E [E]] 0 and a
[ [l)
22
a-1
a-p
Algorithms. We consider Liu & Zhou (2023) as the baseline, since it is closest to our setting, and choose the stepsize di and the clipping threshold 7, follows:
47

---

Published as a conference paper at ICLR 2026
Adopted from Theorem in Liu & Zhou 2023
octi/
7
and
71
max (2vd, od J. where
X1 y and x1 is the initial point.
Adopted from Theorem 7l
8//0 and To max 2Vd, t//
where = ||x1 yll and X1 is the initial point.
Remark 12. For both ?/. only keep the dominant term in the order of O(1/t//p) for simplicity. We pick 7) = X1 - yl to match the optimal choice in theory. Moreover, T) is set in an anytime
fashion, i.e., depending on instead of T. oं do and o, = 2 d fo are set based on their d established (11) 2 2
bounds given (8 and respectively. deff set as its lower bound
2i/d i i d/2 initialize x1 0, Parameter values. In experiments, we fix d = 50, set y, = 2 i d/2'
and let T = 10000. For two kinds of (Nls Te), we run 10 trials for each and plot the mean (# standard error) of the trajectory F(x --,, F. F(x++)) as used the convergence theory, where we recall
x = 1 Σ X We test (1.2, 1.4, 1.6, 1.8) and report the results in Figure
19K
20K
Figure I: Comparison between Liu & Zhou (2023) and this work when = 1.2 (top left), p = 1.4 (top right), p = 1.6 (bottom left), p 1.8 (bottom right).
Observation and Conclusion. In all cases, the (m.. Tτ) pair chosen based on our work is faster, matching the new theoretical finding when a, * ot. As p approaches 2, the difference becomes minor, which should be expected, since the improvement predicted by our theory is in the order of 2-2
(1/ /d
(see discussion under Theorem 3). which will vanish if p is close to 2.
48


Reviews:
[{"review_id": "MqE4Ij2deA", "reviewer": "Reviewer_j1s2", "summary": "This paper studies (strongly) convex non-smooth stochastic optimization under heavy-tailed gradient noise. Clipped-SGD is analyzed, and two refined rates are derived in both high-probability and in-expectation sense.", "questions": "1. The improvement depends on the magnitude of $d_{eff}$. It would help to discuss how the noise structure change $d_{eff}$. \n2. The breaking of lower bounds seem to be dependent on the restrictions on noise family. If that's the case, can you discuss more on this point why lower bounds can be improved? \n3. Can this refined analysis be applied on other nonlinearities such as normalization and sign?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This paper provides a careful analysis that better utilizes Freedman’s inequality that leads to refined high-probability and in-expectation bounds. \n2. This work generalizes the effective dimension into heavy-tailed robust optimization.", "weaknesses": "1. The boundedness of gradients is a strong assumption given that the motivation of heavy-tailed noise is typically training neural networks.\n2. The improvements of the bound is mostly in terms of constant, and it is not clear whether this is a significant improvement. \n3. No experiments provided. Some simple numerical examples to validate theory can also be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KHCRP63hkY", "reviewer": "Reviewer_BWN2", "summary": "The authors consider the problem of heavy-tailed composite optimization with a convex or strongly convex regularizer. They provide refined high-probability rates of convergence for proximal clipped stochastic gradient descent in both convex and strongly convex scenarios. The improvements are based on two main ingredients. The first one is a tighter bound on the variance term in Freedman's inequality. The second one is a better bound on clipping error following from Lemma 1 (in particular, from the refined bounds on $\\|\\| \\mathbb E_{t - 1} [d_t^u (d_t^u)^\\top]\\|\\|$ and $\\|\\|d_t^b\\|\\|$). The authors also prove in-expectation bounds (Theorems 3 and 4) with essentially the same rates of convergence.", "questions": "Is it possible to choose the clipping threshold independently of $\\delta$? If you could do so, then the results of Theorem 3 and Theorem 4 would easily follow from the high-probability upper bounds.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The rates of convergence in Theorems 1 and 2 are tighter compared to [Das et al., NeurIPS 2024], [Gorbunov et al., JOTA 2024], [Liu, Zhou, arXiv:2303.12277, 2023]. The present paper also removes some artefacts. For instance, in [Das et al., NeurIPS 2024] the upper bound blows up when $\\sigma_s$ tends to zero.", "weaknesses": "1. The upper bound on $\\mathbb E_{t - 1} X_t^2 = \\mathbb E_{t - 1} \\langle d_t^u, y_t\\rangle^2$ is quite standard. The fact that $\\mathbb E_{t - 1} X_t^2 \\leq \\|\\| \\mathbb E_{t - 1} [ d_t^u (d_t^u)^\\top ] \\|\\|$ has been used in statistics. I am a bit surprised that it was overlooked in optimization.\n\n2. According to Section 5, the main novelty of the paper is based on the refined bounds on $\\|\\| \\mathbb E_{t - 1} [d_t^u (d_t^u)^\\top]\\|\\|$ and $\\|\\|d_t^b\\|\\|$ stated in Lemma 1. Their proofs take a few lines each. For this reason, the contribution looks somewhat incremental.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9YBcpK9cQI", "reviewer": "Reviewer_WNtT", "summary": "The paper studies the clipped stochastic gradient descent under tighter assumptions on heavy-tailed noise (Assumption 4 in the manuscript). They analyze the proximal version, assuming that the objective function is convex and $G$-Lipschitz. By better utilizing the Freedman's inequality, they obtain better convergence rates for high-probability convergence, replacing the $\\log\\frac{\\log T}{\\delta}$ term with $\\log \\frac{1}{\\delta}$. For in-expectation convergence, utilizing Assumption 4 results in an improvement by a factor of $\\Theta\\left(d_{\\text{eff}}^\\frac{p-2}{2p}\\right)$.", "questions": "1)What were the main difficulties in adapting the previous analysis in [1]?\n\n2)How can the analysis be extended to more realistic assumptions -- $L$-smooth or $(L_0,L_1)$-smooth?\n\n3)Can the existing analysis be extended for nonconvex case? \n\n[1] Das, A., Nagaraj, D., Pal, S., Suggala, A., & Varshney, P. (2024). Near-optimal streaming heavy-tailed statistical estimation with clipped SGD. Advances in Neural Information Processing Systems, 37, 8834-8900.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1)Improving convergence rates in both high-probability and in-expectation analyses.\n\n2)Considering tighter assumption on heavy-tailed noise and introducing a generalized effective dimension $d_{\\text{eff}}$.\n\n3)Conducting a tighter analysis using martingale inequalities.", "weaknesses": "1)Bounded gradients are quite a restrictive assumption for Clipped SGD. \n\n2)Following the previous point, the lower bound on iteration depends on $G$. Therefore, with exploding gradients we have to perform significantly more iterations.\n\n3)The paper lacks a performance comparison of Clipped SGD with $\\sigma_s\\neq\\sigma_l$, as well as their evaluation on the different datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QAwyDsxPKn", "reviewer": "Reviewer_9vd3", "summary": "The paper presents a refined analysis of the Clipped SGD method under both convex and strongly convex regimes. Through a more careful application of Freedman’s inequality and an enhanced clipping lemma providing tighter bounds on bias and variance, the authors derive improved convergence rates compared to existing results.", "questions": "1. Can convergence in the strongly convex setting be proved for the last iterate (for the term $f(x) - f^*$)? What are the technical challenges involved in performing such an analysis (if I am not mistaken, the current results are derived for a specially weighted point)?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. **Extensive theoretical results.** The authors provide a fairly comprehensive analysis of various cases. They also emphasize that the discrepancy between the obtained upper bounds and the existing lower bounds is natural, since the classes of problems do not coincide in terms of the stochastic oracle model.\n\n2. **Improvement of the result in terms of $\\ln(T)$.** The authors applied the concentration inequality in a tighter form (to me more precise, Freedman's inequality), which allowed them to eliminate the arising factor $\\ln(T)$ compared to Das et al. (2024).\n\n3. **Great clipping lemma.** The authors propose a refined clipping lemma that yields improved bounds for bias and variance. Importantly, this lemma (see Theorem 5) does not rely on fact that the norm of the true gradient should be less than $\\frac{\\tau}{2}$ (this condition is required in many papers, e.g. [1], [2]), which marks a significant methodological advantage.\n\n---\n\n**References**\n\n[1] High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance. Sadiev et al. (2023)\n\n[2] High Probability Convergence of Clipped-SGD Under Heavy-tailed Noise. Nguyen et al. (2023)", "weaknesses": "### **Minor weaknesses**\n\n1. **Failure of SGD.** To be fair, the inability of SGD to cope with heavy-tailed noise deserves a clearer explanation. While it is true that, in the absence of a finite second moment for the stochastic gradient error norm, the classical analysis paradigm breaks down, there exists [3] showing that SGD still converges in expectation under condition $p \\in (1, 2]$. Nevertheless, it is provable that SGD, and even Adam, fail to adequately cope with this type of stochasticity when high-probability convergence is considered. These results were established in [4] and [5] for SGD and Adam, respectively. Accordingly, work [4] should be cited to substantiate this point.\n\n2. **Clipped SGD or Proximal Clipped SGD.** It would be more appropriate to refer to the method considered by the authors as Proximal Clipped SGD, since the notation introduced in the paper may confuse readers, and this terminology is formally more accurate.\n\n### **Major weaknesses**\n\n1. **Assumptions.** A key limitation concerns the assumptions adopted. In particular, the set $\\mathbb{X} \\subseteq \\mathbb{R}^d$ on which the optimization problem is defined is assumed to be nonempty, closed, and convex. Therefore, $\\mathbb{X} = \\mathbb{R}^d$ can be considered. At the same time, in the paper, the function $f$ is assumed to be both convex and Lipschitz with constant $G$. Regrettably, this assumption severely restricts the class of admissible functions, as it effectively admits **very limited** examples of $f$ -- linear functions or $|| \\cdot ||$ (or other examples of convex functions with unformly bounded subgradient). This automatically leads to the need to impose additional constraints on the set $\\mathbb{X}$.\n\n2. **Fighting for $\\ln(T)$ elimination.** In fact, one can consider an additional assumption of **boundedness** of the set, that is, taking its closedness into account, the optimization can be considered over a compact set. From the perspective of the class of functions considered, this class is quite broad. However, in this case, striving to eliminate $\\ln(T)$ becomes entirely meaningless. In existing analyses, such as in work [6], the factor $\\ln\\left(\\frac{T}{\\delta}\\right)$ arises from the problem formulation and the assumptions made. The analysis in this work, as well as in other similar studies, is constructed so that the optimization problem is solved over the entire $\\mathbb{R}^d$, while the assumptions are made on a compact subset $\\mathbb{X}$. Consequently, during the convergence analysis, it is necessary to use induction to ensure that points conducted by optimization method do not leave the domain where assumptions hold. Based on this type of analysis, the probability estimate deteriorates by $\\frac{\\delta}{T}$ at each step (which is precisely why  $\\ln\\left(\\frac{T}{\\delta}\\right)$ appears). However, if the problem is formulated on a compact set, no inductive steps are required, and thus the bound with factor $\\ln\\left(\\frac{1}{\\delta}\\right)$ instead of $\\ln\\left(\\frac{T}{\\delta}\\right)$ can be achieved.\n\nEmphasizing the above, the main issue lies in the assumptions made, since in the current formulation, without a bounded set, the class of considered functions $f$ is very limited. If boundedness of the set is added, $\\ln(T)$ can be eliminated based on existing analyses. Therefore, in my opinion, the main contribution of this work at present is a **more precise treatment of the heavy-tailed stochasticity via Assumption 4**.\n\nDespite the concerns mentioned, I am open to reassess the paper according to further explanations or revisions by authors.\n\n---\n\n**References**\n\n[3] Can SGD Handle Heavy-Tailed Noise? Fatkhullin et al. (2025)\n\n[4]  High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance. Sadiev et al. (2023)\n\n[5] Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailed. Chezhegov et al. (2024)\n\n[6] High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise. Gorbunov et al. (2024)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)