High-Probability Bounds for the Last Iterate of Clipped SGD
Authors: Savelii Chezhegov
Daniela Angela Parletta
Andrea Paudice
Eduard Gorbunov
Venue: ICLR 2026 Poster (2026)
Keywords: Stochastic optimization
high-probability convergence
heavy-tailed noise
last-iterate convergence
gradient clipping
Primary area: optimization

Abstract: We study the problem of minimizing a convex objective when only noisy gradient estimates are available. Assuming that stochastic gradients have finite $\alpha$-th moments for some $\alpha \in (1,2]$, we establish - for the first time - a high-probability convergence guarantee for the last iterate of clipped stochastic gradient descent (Clipped-SGD) on smooth objectives. In particular, we prove a rate of $1/K^{(2\alpha-2)/(3\alpha)}$ with only polylogarithmic dependence on the confidence parameter. In addition, we introduce a new technique for deriving in-expectation convergence guarantees from high-probability bounds for methods with almost surely bounded updates, and apply it to obtain expectation guarantees for Clipped-SGD. Finally, we complement our theoretical analysis with empirical results that support and illustrate our findings.

Published as a conference paper at ICLR 2026
HIGH-PROBABILI BOUNDS FOR THE LAST ITERATE OF CLIPPED SGD
Savelii Chezhegov BRAIn Lab", MIRAII,
Daniela A. Parletta University of Genoa
Andrea Paudice
Eduard Gorbunov MBZUAI
Aarhus University
Sher Al Lab
ABSTRACT
We study the problem of minimizing convex objective when only noisy gra- dient estimates are available. Assuming that stochastic gradients have finite a- th moments for some probability convergence guarantee for the last iterate of clipped stochastic gradient descent (Clipped-SCG) SGDD on smooth objectives. In particular, we prove rate of 1/K(2a-2)/(sa) with only polylogarithmic dependence on the confidence param- eter. In addition, we introduce a new technique for deriving in-expectation con- vergence guarantees from high-prohd probabbbbbyiltty bounds for methods with almost surely bounded updates, and apply it to obtain expectation guarantees for Clipped-SGG -GG. Finally, we complement our theoretical analysis with empirical results that support and illustrate our findings.
(1, we establish for the first time a high-
INTRODUCTION
Stochastic first-order optimization methods such as SGD (Robbins & Monro, 1951), Adam (Kingma & Ba, 2014), and their numerous variants are central to the training of modern machine learning models. In practice, these algorithms almost always combined with additional tech- niques that enhance stability and performance. One such technique gradient clipping (Pascanu al., 2013) has become standard component in the training of large language models (LLMs) (Devlin et al., 2019; Brown et al., 2020; Fedus et al., 2022; Touvron et al., 2023).
Originally introduced to address exploding gradients in recurrent neural networks, gradient clipping has since proven valuable well beyond this motivation. It has been shown to improve convergence under generalized smoothness conditions (Zhang et al., 2020a), to provide robustness against heavy- tailed noise where gradient variance can be unbounded (Zhang et al., 2020b), and to enable strong high-probabbility convergence guarantees (Gorbunov al., 2020; Cutkosky Mehta, 2021: Parletta et al., 2024; Sadiev et al., 2023; Nguyen et al., 2023). Nevertheless, for convex problems, most existing theoretical results for clipped methods (including Clipped-SGD) analyze averaged iterates, while the practically more relevant last iterate remains largely unexplored.
Contributions. In this work, we close a long-standing gap in the theory of clipped stochastic gradient descent by analyzing the last iterate under heavy-tailed noise. Our main contributions are:
First phobabbrbbbillity last-iterate guarantees for CLipped-SGD. We establish the first high-probabilityy convergence rate for the last iterate of Clipped-SGD on convex smooth objectives. Assuming stochastic gradients have finite a-th moments with a E (1,2), we prove that after K iterations the method achieves an error of most
polylog(K/6)
O
1)/3-
with failure probability at most 8 (0, 1), Theorem and Corollary 1. In the special
case of a = 2, this results in a polynomial gap compared to the best-known in-expectation
* "Basic Research of Artificial Intelligence Laboratory
Moscow Independent Research Institute of Artificial Intelligence Mohhamdd bin Zayed University of Artificial Intelligence

---

Published as a conference paper at ICLR 2026
rate of 1/VK, where clipping is unnecessary. Crucially, result covers the full spectrum of heavy-tailed noise and provides High-probability guarantees for a single run signifi- cantly stronger than standard in-execctation bounds.
General analysis of step-size and clipping schedules. We develop a unified analysis for polynomially decaying step-sizes and varying clipping levels. bounding the optimization етror as a function of these schedules. This yields principled guidelines for tuning and identifies optimal exponents, while avoiding restrictive assumptions such as bounded optimization domain.
Any-time parameter choices. Our parameter selection horizon-free: it does not require prior knowledge of the number of iterations and remains valid in streaming or indefinite- training scenarios, where restarting schemes are impractical. Our results hold without re- liance on large minibatches, making them applicable in resource- resource-onntrraneed settings.
From high- probability to in-expectation convergence. We develop general technique for converting probbabrbbbb convergence guarantees into in-expectation convergence rates. The approach applies to any method for which the convergence criterion (e.g., the function sub-optimality of the last iterate) is almost surely polynomially bounded in terms of the total number of iterations K. In particular, our technique can be applied any high- probability result established for algorithms with almost surely bounded updates, including Clipped- -GDpe normalized SGD with momentum (Cutkosky & Mehta, 2020), SignSGD (Bernstein et al., 2018), Muon (Jordan et al., 2024), and many other related methods. In Section 4.2, we demonstrate this approach on the example of Clipped-SGD.
We complement result with empirical evidence supporting the advantage of the last iterate the average.
NOTATION AND PROBLEM SETUP
In this section, we introduce the main notation and discuss the assumptions used in the analysis.
Notation. The norm ||>|| = V (x.x) denotes the Euclidean norm in Rd. Eg] denotes the expectation w.r.t. the random variable E. We also denote the clipping operator clip(x, A) = min {1, A ||ل]||
The initial distance, i.e., the distance between the starting point and solution
x² we denote as Ro == ||-0 x²||-
Problem. We study the following problem:
mün ((x),
(I)
ZERE
under the following standard hypothesis. Assumption (Convexity). The differentiable function f is convex, i.e.,
f(v) 2 f(x) + (Vf(z). - z) Vx, y E Rd.
Moreover, we also assume that there exists optimal point x". Assumption 2. There exist an optimal point x² E Ré such that for x E Rd
f(x) 2 f(x*)= > -00
In addition to convexity, we assume that f is L-smooth. Assumption (Smoothness). The differentiable function f is T--moooth ie.. L x) lly x!1? Yx,yeR'
f(y) s +
Finally, although the optimizer does not have direct access to f. we assume access to a stochastic gradient oracle fx. satisfying the following condition.
Our results hold for any solution of the considered problem.
2

---

Published as a conference paper at ICLR 2026
Assumption 4 (Stochastic oracle). The stochastic oracle (z, is unbiased and has bounded a-th central moment with a E (1,2), i.e.
(V 4) fx));
This assumption was introduced by Nemirovskij & Yudin (1983) and later rediscovered by Zhang al. (2020b), after which it has become standard in the analysis of stochastic methods under heavy- tailed noise. For problem (1), we study Clipped-SGD with time-varying stepsize and clipping level Ag:
2k+1 = 2k 7 clip( V fę. (Ix).
where Vfce (2x) = ff(x Ex) is the stochastic gradient sampled independently the past.
Stochastic optimization. tic optimization problem:
The above problem encompasses, a special case, the classical stochas-
((x) == EgwD (e(x,
min aER
where l is the loss function, the model parameters and represents the randomness due to data
sampling from the unknown distribution 'D. In this setting, the stochastic gradient can be computed
from the sample also covers the statical supervised learning problem. Another important special case of Equation (2)
V)(x, = Vf(x, E)- Note that, when (Z, Y) Rd x R, Equation (2)
the sinite-sum setting f(x) = Σi= f(()), which underlies many training procedures in machine
learning.
High-probability convergence guarantees. For an iterative sequence {* (produced by some stochastic method) and target criterion C((=)) the standard goal ensure
E [C ((=x))==)) S S.
Such in-expectation bounds describe average behavior, but they do not capture the variability of the random process. hiobbbprobabilityy bounds, by contrast, guarantee that the performance criterion is met with confidence least 1 5, i.e.,
P (C ((==) < 2 -
thereby directly limiting the probability of unfavorable deviations.
Although one can obtain such bounds from expectation guarantees via Markov's inequality, this typically yields rates with an undesirable polynomial 1/8 dependence. Modern approaches instead achieve bounds with only polylogarithmic dependence on 1/5, which greatly improves reliability and reduces the number of iterations required to reach target confidence level. other words, the goal of high-probability convergence analysis is to establish convergence rates of the same order as the optimal in-expectation guarantees, with only minimal dependence on the confidence parameter ideally (Iooog(1/5))
RELATED WORKS
The literature on SGD and Clipped-SGD vast and multifaceted, and a comprehensive survey beyond the scope of this work. In what follows, we focus only on the closely related works.
In-expectation convergence bounds. Early studies on SGD for smooth and non-smooth (but Lip- noise (Nemirovskij
schitz) objectives investigated convergence in expectation under & Yudin, 1983; Nemirovski et al., 2009; Ghadimi & Lan, 2013a;b). In this setting, the average iterate of SGD achieves a rate of (I, which is known to be optimal (Agarwal et al., 2012). Similar established in (Shamir & Zhang, 2013; Jain al., 2021), while for smooth objectives the best known rate remained O(1/K1/3 (Moulines & Bach, 2011) for a long time, until (Liu & Zhou, 2024) - building on ideas from (Zamani & Glineur, 2023) proved the optimal rate (1/VK), thereby unifying the analysis of both smooth and non-smooth cases.
optimal rates for the last iterate in the non-smooth case

---

Published as a conference paper at ICLR 2026
Under the more general bounded (1,2) moments model considered in this work, Zhang et al. (2020b) show that plain SGD does not converge (in terms? of Ellæy - =²'] and prove in- expectation convergence bounds for Clipped-SGD for non-convex smooth and strongly convex problems with bounded gradients. Vural et al. (2022) derive average-iterate ((1/K(a11/aa bound for Stochastic Mirror Descent (SMD) over convex Lipschitz objectives and show that it is optimal. In the same non-smooth setting, Parletta et al. (2025) show that the last iterate of Clipped-SGD enjoys the same optimal rate. Moreover, for strongly convex objectives, Jakovetić et al. (2023) investigate the last-iterate convergence of a general class of robust SGD variants assuming only = 1. However, these results require additional assumptions, such as symmetry of the noise dis- tribution and constraints on its effective dimension. To the best of our knowledge, there exist no last-iterate in-expectation convergence bounds for Clipped-SSe in the case of convex L-smooth problems with the stochastic oracle satisfying Assumption
Hfigh-probbbility convergence bounds. The first high-probability results for SGD were estab- lished under sub-Gaussian noise assumptions (Nemirovski al., 2009; Harvey et al., 2019b), which are considerably stronger than those considered in this work. Moreover, these guarantees apply only to the average iterate. In this setting and for non-smooth objectives, Liu et al. (2023) showed that the average iterate of Stochastic Mirror Descent (and hence of SGD) converges at the optimal rate with only a modest confidence overhead of O (log()/))). Similar last-iterate guarantees (in- cluding for smooth objectives) were later obtained by Eldowa & Paudice (2024) and Liu & Zhou (2024). Both works also relaxed the sub-Gaussian assumption to the broader class of sub-Weibull tails (Vladimirova et al., 2020), which were further explored in non-convex settings by Madden et al. (2024). While more general, these tail models still imply the existence of moments of all orders.
In contrast, under the heavy-tailed noise model studied here, several works (Nazin et al., 2019; Gorbunov et al., 2020; Nguyen et al., 2023; Sadiev et al., 2023; Gorbunov al., 2024; Par- letta et al., 2024; 2025) have shown that clipping yield convergence of the average iterate at rate O(1/K(0-1//0) for convex L-smooth objectives. To the best of our knowledge, results for the last iterate in this regime require additional structural assumptions such as strong convexity or the PL condition (Sadiev et al., 2023). Our work closes this gap by establishing, for the first time, high- high-probability convergence rates for the last iterate of SGD on convex smooth objectives. Finally, refinements of the E (1, model have been proposed in Puchkin et al. (2024), who demonstrate that in certain cases is possible to surpass the Ō(1/K" (////(o-1)// ())))))) barrier.
MAIN RESULTS
In this section, we state our high-probability last-iterate guarantee for Clipped- and explain the ideas behind its proof.
Theorem 1. Suppose that Assumptions 1, 2, and hold. Then, if we choose
B
7/k min
(3)
320L In
6(k+1)] 8
80 (kk + 1)3 In
6(k+1)2
0
Ry min
{
|,,11
Vite
A
(4)
80yy In
1/2 0(K++112) 8
"In the case convex non-smooth problems, i.e.. assuming that [|[ (2, 1 S G"J.Fatkhullii Fatkhullin et al. (2025) prove ((1/k(a-1)44 average-iterate convergence rate of SGD. The same result was independently shown by Liu (2025) for the average and last iterates of SGD (a.k.a. Online Gradient Descent), Dual Averaging (Nesterov, 2009). and AdaGrad Streeter & McMahan (2010); Duchi et al. (2011). Moreover, Liu (2025) also derive similar results for the average iterates of SGD, Dual Averaging, and AdaGrad for convex smooth objectives. Importantly, both papers (Fatkhullin al., 2025; Liu, 2025) assume boundedness of the domain.
'The ④ hides poly- logaritgti factors. Nazin et al. (2019); Gorbunov et al. (2020: 2024); Parletta et al. (2024) consider the case of a 2, which is often considered as heavy-tailed noise in the literature since the majority of prior high-probability results relied on sub-Gaussian noise assumption.
4

---

Published as a conference paper at ICLR 2026
Table 1: Comparison of the state-of-the-art non-accelerated in-expectation and high-prohe ceah-prbbbbiityy
convergence results for SGD/Clipped-SGD-II methods applied to smooth corvex problems.
Reference
Convergence type
Iterate
Stochasticity
Rate
(Ghadimi & Lan, 2013b)
In-expectation
Average
As. 4, 4,0 ==
LRg
Rae
(Taylor & Bach, 2019)
In-expectation
Last
As. 4
LRg K K37
(Liu & Zhou, 2024)
In-expectation
Last
As. & (1,2)
1.Ng
Rug
(Ghadimi & Lan, 2013b)
High probability
Average
Sub-Gause Gaussian
Ligg
Rao
K
VK
(Liu & Zhou, 2024)
High probability
Last
Sub-Weibul
LRg
Rgo
(Nguyen al., 2023)
High probability
Average
As. 4, (1,2)
LNN
Rug
to 117
This work
High prohability
Last
As. E (1
LRG
+ Kalo- 13730
D
The rate from Nguyen et al. (2023) has better logarithmic factor than the one from Sadiev et al. (2023).
D = max Roo, (a-1))(aa-1))/pp (dta (2)(3111)))) 220/(30-1) 1 1,1/ / /2/3 )2/a].
where B chosen
Ro
Rg
R
B min
20c
σ L
and parameter 3 satisfies
2 + a
3a
then, after K iterations of Clipped- we have that f(xx) f"
max
ROoT L Na
R
3u
L.
LR
6(K + 1)2
In?
K
K1-8
K Σ
holds with probability at least
pz.
1=1
Corollary 1. Let the conditions Theorem hold. Then, we choose in the optimal way, ie.
== 2ta derive that
4n Bm
max Roo, -a R
1 R of
LR K
(αx) -
20-2 30
holds with probability at least - 28. Here (-) denotes polylogarithmic dependency.
Proof. It is enough to substitute the equation for 3 in the result of Theorem and clarify that
8T
Σ
=
> 1 28.
6
1=1
t=1
This finishes the proof.
4.1 PROOF SKETCH AND TECHNICAL NOVELTIES
We outline the analysis and highlight the three key innovations.

---

Published as a conference paper at ICLR 2026
Potential- high--robabilltty convergence proof. potential:
We analyze the method using the following
4x =
L| - x²1 de+1 = d2 + 27th L, do = 0.
This potential coincides with the one proposed by Bansal Gupta (2017) to study the convergence of Gradient Descent. Moreover, Taylor & Bach (2019) use 4 to derive last-iterate in-expectation convergence rates (see Table 1). Since we focus on high-probabilityy convergence, our descent lemma differs from that of Taylor & Bach (2019) and leads to
K Σ k
K Σ den (V](=)). O&) + R-O
K Σ (d++1 + 1)47211011 (5) R-O
SK S 40
2 (o* - -200a))
where O2 = the right-hand side are controlled via bernstein/Freedmaa inequalities using a time-varying failure budget 6g ~ 1/t², followed by a union bound over t.
(((xx) and ==
The three martingale-type sums on
Clipping level λ ~ 1/vdk. A key technical ingredient of our analysis is the choice
Ro
min
dd 1
80y In 6(k++)2
rather than scaling proportional to 1/7k, commonly used in existing vverage-iterate convergence results (e.g., (Sadiev et al., 2023; Nguyen et al., 2023)). The additional factor min (1/ l/. 1) is motivated by the following observation. Since we prove by induction that f(xx f decreases
as ((1/ds) with high probability, it follows that [ S /2L(f(z)) fr)
(l1/Vd)).
At the same time, the standard smoothness bound | fx=x) S L || remains valid. This refined scaling of ÅS therefore allows us to more effectively balance the bias and variance terms introduced by clipping under Assumption 4, leading to sharper high-probability bounds.
Horizon-agnosta schedules and log-factors. Both % and d are any-time, i.e., no prior knowl- edge of K is assumed. This influences two aspects of the proof:
Similarly to the prior uighprobbbiility analysis of Clipped-SGD (Gorbunov et al., 2020; Sadiev et al., 2023) for smooth convex objectives, we bound the sums from (5) for each K > 0 with high probability and then apply the union bound for estimating the probability of the "good" event Ex. However, since the horizon is unknown, we cannot select the failure probability at each step as 8/K for each k O..... probability for step & is upper bounded by 5/k² in our proof. The choice òg ~ 1/k² (and the resulting Σn d5 I 5) introduces at most polylogarithmic dependence on 1/8 in the final bound, while keeping the schedules horizon-free.
Instead, the failure
Moreover, due to the horizon independence of the parameters, the derived upper bound for & k contains logarithmic factor ~ (6(6( +)////). This leads the additional exponent in the final bound (for comparison, see Sadiev et al. (2023) or Nguyen et al. (2023)). We refer to Appendix B.3 for further details.
We also note that "/ and Å depend on the failure probability 8, which is a common practice in high-probability convergence results (Nazin et al., 2019; Gorbunov et al., 2020; Nguyen et al., 2023; Sadiev et al., 2023; Parletta al., 2025). To the best of our knowledge, almost! all existing either aab-Gaussian (Li & Orabona, 2020; Harvey et al., 2019a; Jain al., 2021; Liu al., 2023) or wei-Weibulll (Madden et al., 2024) noise assumption. In both of these cases, the analysis does not require proving by induction that the iterates remain bounded with high probability due to the strengths of the assumptions. In contrast, our analysis does rely on inductive argument, which is the key reason why 7/ and Å are dependent on in our
results with ö-independent parameters choice are derived under
'Hübler et al. (2025); Kornilov et al. (2025) derive brobbbrobbbylityy convergence results for normalized SGD and SignSGD respectively for non-convex (generally) smooth objectives. The results are shown for the 8-agnostic paraee-arameters' choices. However, both results rely the usage of large mini-batches, which is often prohibitively expensive.

---

Published as a conference paper at ICLR 2026
results. Nevertheless, note that the dependence of y and X does not artificially stabilize the dynamics of the method and our result does imply meaningful in in-expectation bound as explain in Section 4.2.
Remark 1. When + 1, then our result shows convergence to some (finite) neighborhood, which is well-aligned with existing average-itenn itegate results (see Table 1) and the lower bound for the Lipschitz convex case (Vural et al., 2022).
4.2 FROM PROB-PRRBABILITY IN-EXPECTATION CONVERGENCE
Since 7 and Å are 5-dependent, one cannot obtain an in-expectation guarantee from our high- probability result via integration of the tail bound. Nevertheless, one derive meaningful in- expectation convergence guarantee in another way. Indeed, for any fixed E (0, 1) we can choose sequences of parameters {7% ) and {Ax k== according the Theorem this case, the fol- lowing inequality holds with probability at least 1 20:
f(xx) -
max
Roo, L 50-1
R σ 33-
L. 13
6(K + 1)3
LR K
(6)
K1-5
where some numerical constant. What is more, for Clipped-SGD we can also bound f(rk) f" with probability 1. To show that, let us bound the distance to x² at iteration K:
a - x²1l
Vi clip(V Sea (Ix), An)
k=0
K
< 1 - x= I1 +
fex Ax)Il
k=
K
(4)
Ro
< In x"
Ro
+
Σ
K KR.-
k=
k=
Therefore, we can upper bound the function sub sub-optimality using Assumption 3:
L
|, x011² LRGK2
[(x) 8 S
2
Next, since the random variable f(*x) I is bounded as in (6) with probability at least 1 26, and is bounded in (7) with probability 1, the expectation of f(xx) f can be bounded follows:
[[f(xx) - l*]
Roo, L - Rg 30-1 Lb R 3
6(K 1)3 ()2)
LR K
max
$ (1 - (1-22))llo'
8
K1-5
+ KLRR
4a-2
6(K + 1)2 8
LR
max
Ryo
-
R
g 30-1
L
< (1 - 11-8))olog
K
K1-3
max
Roo L 10001
9-1
R
4a
L R
LR K
+ +.K3
K1-8
Choosing in appropriate way, we get the following result.

---

Published as a conference paper at ICLR 2026
Corollary 2. Let the conditions of Theorem hold and d 1 F[f(xx) - -f]
Then, we have
K3.
LR log" (6(K + 1)9) max Roo, L sm R sa
L Ry
log (6(K + 1)9) Roo
K
K K1-3
Remark 2. Clearly, we can substitute the best possible choice of 3 to obtain the same convergence rate in Corollary 1.
Remark 3. In-expectation convergence from Corollary 2 reproduces the result from Taylor & Bach (2019) for a = up logarithmic factors.
Remark 4. Since we take 8 xas the resulting choice of 7Kk and X in Corollary 2 is horizon- dependent. Achieving a similar in-expectation convergence rate for Clipped-SGI horizon-agnostic hyper-parameters is an interesting open question.
Remark 5. Interestingly, upper bounds analogous to (7), which constitute the key ingredient in deriving the in-expectation guarantee from the high-probability results, can be established for any method with bounded updales, such as normalized SGD and SignSGD, with without momentum. This demonstrates that the technique developed in this section extends well beyond Clipped-SGr and applies to a broad class of algorithms with bounded steps.
5 EXPERIMENTS
In this section, we present the results of numerical simulations showing the practical advantages of the last iterate over the average. We consider the problem of minimizing convex and smooth function f: Rd - IR from noisy estimates (zx) of its gradients. In all experiments, we run Clipped-SGD with the step-size and clipping level schedules suggested by the theory, optimizing the constants via a grid-search procedure. Finally we report the performance of both the average and the last iterate in terms of the 0.95-pereentile and, for completeness, also the sample mean + the standard deviation of the function values across 1000 repetitions.
Corrupted gradients. We set fz(x) f(x) N, where N is random vector with compo- nents sampled i.i.d. from Pareto distribution rescaled and reshaped so that satisfies E J (x)) fx))., f() [=)) < 1, and all moments order greater than 2.001 are infinite, which closely matches assumption with = 2. We set d 100 and consider two cases: first, for a fixed unit vector a we let fx) = In(1 + exp( (z, a})) + (A/2)|[=|1 (where À = 10-6 is only introduced to make the problem well defined); second,
also consider f(x) (1/2)[ Both objectives are smooth and strongly convex, although the first one is almost not strongly convex due to the very small value of X. The results are shown in the left and central plots of Figure 1, where it
is possible to see that the last iterate performs better than the average.
Statistical learning. to minimize
We also consider the following statistical learning problem, in which we aim
f(x) = E(Z,r)a [In + exp(-Y(p)))) Z))) + +
using only sampling access to = 112 Jyyz and X = 10-2 (again introduced only to make the problem well-defined). We set sampled from a Student-t distribution with 2.001 degrees of freedom, so that each component has variance 1/d but infinite moments of higher order. Moreover, we set 1Y| = Ber(p(2)) over
and take uzz to be an isotropic distribution with components
{+1} with p(z) sigmoid (w, 2)). We use fz(x) V a In(1 + exp(-Y (x, Z))) for (Z,Y) Y) and note that f[V] Vf.x) We estimate f(2) given point via the Median-of-Ne M
log(1/8) with confidence 1 'The use of Median-of-Mern ensures an estimation error of the order
over samples, which is exponentially better than the exhibited by the standard Monte-Carlo estimate (Lugosi& & Mendelson, 2019).
8

---

Published as a conference paper at ICLR 2026
101
Amnrage
10"
Ave-age
Revate
Ddpccre vale
2xx
10
100
I04
400 600
420
020
850
3000
200
400
600
800
1000
Figure 1: Experimental results: (left) f(x) In(1 + exp( a))), (center) f(æ) 2|2= and (right) f(x) = (bb exp(-Y((x: Z))][. The z-axis shows the iteration counter k, while the y-axis (in logarithmic scale) reports the objective value f(*x) at the iterate 2k- Note that in the left and center plots, the y-axis corresponds to the optimization error since infzer f(x) O. In all figures, the dotted line denotes the 0.95-percentile, while the solid line together with the shaded area denotes the sample mean + standard deviation. Note that, due to the log scale the y, the shaded area appears stretched whenever its magnitude differs by orders magnitude from the sample mean.
estimator with 10a samples from μr. The results are shown in the right plot of Figure 1, where it is possible to see that the last iterate performs better than the average.
Discussion. For fairness, both the average and the last iterate evaluated under the same step- size and clipping level schedules: namely, those which our theory guarantees convergence the last iterate. We emphasize that the optimal schedules for the average iterate differ from these ones. In additional experiments (see appendix), we observed that the last iterate actually performs even better when the average iterate is under its own optimal schedule. This suggests that current OL1/ bound for the last iterate may be an artifact of the analysis, and that there might exist schedule (possibly the one already known to be optimal for the average iterate) that makes the last iterate achieve the optimal rate as well. A rigorous proof of this conjecture is left future work.
CONCLUSION
We presented the first high-probability last-iterate guarantees for Clipped-SGD on convex L- smooth objectives under heavy-tailed noise with finite a-th moments, E (1, 2). Our analysis based on a potential function tailored to bigh-probability control, new clipping schedule that scales 1/(vbatk), and O(1 (1/33)) for the last iterate with only polylogarithmic dependence 1/.. Empirically, we observe clear advantage of the last iterate over the average under heavy-tailed perturbations.
parameter choices. These ingredients yield rate of
Limitations and future work. The rate at = 2 leaves a polynomial gap from the ((1/VK) expectation benchmark (Liuu & Zhou, 2024); tightening the last-iterate high-probability rate compelling direction. Extending the theory to (Lo, -mmommothh objectives, which is done for the average iterate by Gaash et al. (2025) under sub-Gaussian noise assumption and by Chezhegov al. (2025) under Assumption without losing Morizon-freeness. is another natural next step.
ACKNOW.EDGGENTS
The work of Savelii Chezhegov supported by the Ministry of Economic Development of the Russian Federation (agreement No. 139-15-2025-013, dated June 20, 2025, IGK 00000CC113995P44000)..
REFERENCES
Alekh 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 Information Theory, 58(5))3235-3244 2012. (Cited page 3)

---

Published as a conference paper at ICLR 2026
Nikhil Bansal and Anupam Gupta. iitential-fucction proofs for first-order methods. arXiv preprint arXiv:1712.04581, 2017. (Cited on page 6)
George Bennett. Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association, 57(297):33-45, 1962. (Cited on page 14)
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. In International conference on machine learning. pp. 560-569 (60-569. PMLR, 2018. (Cited on page 2)
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020. (Cited on page 1)
Savelii Chezhegov, Aleksandr Beznosikov, Samuel Horváth, and Eduard Gorbunov. Convergence of clipped-sgd for convex (To, L, -smooth optimization with heavy-tailed noise. arXiv preprint arXiv:2505.208177 2025, (Cited on page 9)
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. In International confer- ence on machine learning, pp. 2260-2268. PMLR, 2020. (Cited on page 2)
Ashok Cutkosky and Harsh Mehta. High-probabilltty bounds for non-convex stochastic optimization with heavy tails. Advances in Neural Information Processing Systems, 34:4883-4895, 2021. (Cited on page 1)
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume I (Long and Short Papers), pp. 4171-4186, 2019. (Cited on page 1)
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011. 1. (Cited on page 4)
Kacha Dzhaparidze and JH Van Zanten. On bernstein-type inequalities for martingales. Stochastic processes and their applications, 93(1):109-11) 2001. (Cited page 14)
Khaled Eldowa and Andrea Paudice. General tail bounds for non-smooth stochastic mirror descent. In Proceedings of the 27-th International Conference on Artificial Intelligence and Statistics, pp- 3205-3213, 2024. (Cited page 4)
llyas Fatkhullin, Florian Hübler, and Guanghui Lan. Can sgd handle heavy-tailed noise? arXiv preprint arXiv:2508. 048600 2025. (Cited on page 4)
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. Journal of Machine Learning Research, 23(120): 1-39, 2022. (Cited page !)
David A Freedman et al. On tail probabilities for martingales. the Annals of Probability, 3(1): 100-118, 1975. (Cited on page 14)
Ofir Gaash, Kfir Yehuda Levy, and Yair Carmon. Convergence of clipped sgd on convex (Lo, Lz)- smooth functions. arXiv preprint arXiv:2502.16492 2025. (Cited on page 9)
Saced Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly con- vex stochastic composite optimization, i:: shrinking procedures and optimal algorithms. SIAM Journal on Optimization, 23(4):2061-200 2089. 2013a. (Cited on page 3)
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal on Optimization, 23(4):2341-236 2013b. (Cited on pages 3 and 5)
Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy- tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Sys- fems, 15053, 2020. (Cited pages 1, 4, and 6)
10

---

Published as a conference paper at ICLR 2026
Eduard Gorbunov, Marina Danilova, Innokentiy Shibaev, Pavel E. Dvurechensky, and Alexander V. Gasnikov. High-probability complexity bounds for mon-sm stochastic convex optimization with heavy-tailed noise. J. Optim. Theory Appl., 203(3))2679-2733 2024. (Cited on page
Nicholas J.A. Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Proceedinds of the 32nd International Conference Computational Learning Theory, pp. 1579-1613, 2019a. (Cited on page 6)
Nicholas JA Harvey, Christopher Liaw, and Sikander Randhawa. Simple and optimal high-pres probbbbbiy bounds for strongly-convex stochastic gradient descent. arXiv preprint arXiv: /909. 00843, 2019b. (Cited on page 4)
Florian Hübler, Ilyas Fatkhullin, and Niao He. From gradient clipping to normalization for heavy tailed sgd. In International Conference Artificial Intelligence and Statistics, pp. 2413-2421.
PMLR, 2025. (Cited on page 6)
Prateek Jain, Dheeraj M. Nagaraj, and Praneeth Netrapalli, Making the last iterate of sgd information theoretically optimal. SIAM Journal on Optimization, (2): 108-1130, 2021. (Cited on pages 3 and 6)
Dusan Jakovetić, Dragana Bajović, Anit Kumar Sahu, Soummya Kar, Nemanja Milosević, and Du- Stamenković. Nonlinear gradient mappings and stochastic optimization: general framework with applications to heavy-tail noise. SIAM Journal on Optimization, 33(2):394 423, 2023. (Cited
on page
Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse, and Jeremy Bernstein. Muon: An optimizer for hidden layers in neural networks, 2024. URL https:
/ //kellerjordam..ii.. gaarrdanggithub. wit.ub...................g.....b io/ posts /muon/. (Cited on page 2)
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint
arXiv: 1412.6900 2014. (Cited on page 1)
Nikita Kornilov, Philip Zmushko, Andrei Semenov, Alexander Gasnikov, and Alexander Beznosikov. Sign operator for coping with heavy-tailed noise: High probability convergence bounds with extensions to distributed optimization and comparison oracle. arXiv e-prints, pp- arXiv-2502, 2025. (Cited on page 6)
Xiaoyu Li and Francesco Orabona. A high probability analysis of adaptive sgd with momentum. arXiv preprini arXiv:2007.14294 2020. (Cited on page 6)
Zijian Liu. Online convex optimization with heavy tails: Old algorithms, regrets, and applica- tions. arXiv preprint arXiv:2508.07473, 2025. (Cited on page 4)
Zijian Liu and Zhengyuan Zhou. Revisiting the last-iterate convergence of stochastic gradient meth- ods. In Proceedings of the 12-th International Conference on Learning Representations (to ap- pear), 2024. (Cited on pages
and
Zijian Liu, Ta Duy Nguyen, Thien Hang Nguyen, Alina Ene, and Huy Nguyen. High probability convergence of stochastic gradient methods. In Proceedings of the 40-th International Conference on Machine Learning, pp. 21884-21914, 2023. (Cited on pages 4 and 6)
Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailes distribu- tions: A survey. Foundations of Computational Mathematics, 19(5):1145-110 2019. (Cited on page 8)
Liam Madden, Emiliano Dall' Anese, and Stephen Becker. High probability convergence bounds for non-convex stochastic gradient descent with sub-weibull noise. Journal of Machine Learning Research, 25(241):1-36, 2024. (Cited on pages 4 and 6)
Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Proceedings of the 7th Annual Conference on Advances in Neural Infor- mation Processing Systems, 2011 1. (Cited on page

---

Published as a conference paper at ICLR 2026
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, 80(9):1607-1627, 2019. (Cited on pages 4 and 6)
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574-160) 2009. (Cited on pages and 4)
Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscienee 1983. (Cited page 3)
Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical programming, 120(1):221-259, 2009. (Cited on page 4)
Ta Duy Nguyen, Thien H Nguyen, Alina Enc, and Huy Nguyen. Improved con- vergence in high probability of clipped gradient methods with heavy tailed noise, 2023. URL https: file/
neurips ec wwtpppprreeaeeeeeeeeeeeee forer__flllee fiwee//paaaaeeee heaeleesppp/e222.33 hag.ra/eee..ataeeeeeeeee-------e pdf. (Cited on
pages I, 4, and 6)
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(4):953-977, 2024. (Cited on pages and 4)
Daniela Angela Parletta, Andrea Paudice, and Saverio Salzo. An improved analysis of the clipped stochastic subgradient method under heavy-tailed noise, 2025. URL https: /tt.aiiaxv..o///////........ abs/2410. 00573. (Cited on pages 4 and 6)
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pp. 1310-1318. Pmlr, 2013. (Cited on page 1)
Nikita Puchkin, Eduard Gorbunov, Nickolay Kutuzov, and Alexander Gasnikov. Breaking the heavy- tailed noise barrier in stochastic optimization problems. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, 2024. (Cited on page 4)
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951. (Cited on page
Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. High-probability bounds for stochas- tic optimization and variational inequalities: the case of unbounded variance. In International Conference on Machine Learning, pp. 29563-29648, PMLR, 2023, (Cited on pages 1, 4, 5, 6, 14, and 18)
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Conver- gence results and optimal averaging schemes. In Proceedings the 30th International Conference on Machine Learning, 2013. (Cited on page 3)
Matthew Streeter and H Brendan McMahan. Less regret via online conditioning. arXiv preprint 1002,44002.4883 2010. (Cited on page 4)
Adrien Taylor and Francis Bach. Stochastic first-order methods: non-asymptotic and computer- aided analyses via potential functions. In Conference on Learning Theory, pp. 2934-2992. PMLR, 2019. (Cited on pages 5, 6, and 8)
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302. /397/, 2023. (Cited page 1)
Mariia Vladimirova, Stéphane Girard, Hien Nguyen, and Julyan Arbel. Sub-weibull distributions: Generalizing sub-gaussian and sub-exponential properties to heavier tailed distributions. Stat, (1):e318, 2020. (Cited on page 4)
12

---

Published as a conference paper at ICLR 2026
Nuri Mert Vural, Lu Yu, Krishnakumar Balasubramanian, Stanislav Volgushev, and Murat A. Er- dogdu. Mirror descent strikes again: Optimal stochastic convex optimization under infinite noise variance. In Proceedings of the 35-th Conference Learning Theory, 2022. (Cited on pages
and 7)
Moslem Zamani and Francois Glineur. Exact convergence rate of the last iterate in subgradient methods, 2023. URL bttps://arxivv http:iiw..gg/../oooaaaoooboaaaet /tabbb/23301 2207 11134. (Cited on page
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Rep- resentations, 2020a. (Cited on page 1)
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why adaptive methods good for attention models? In Proceedings of the 34th Annual Conference on Neural Information Processing Systems, 2020b. (Cited on pages 1, and
13

---

Published as a conference paper at ICLR 2026
A APPENDIX
In this section, we provide additional known details intended to support our analysis.
A.1
TECHNICAL DETAILS
Additional notation.
We introduce the following notation:
gt clip (V S& (zre),
O, (((e),
Or gr E [gt],
of [g] vf(xz),
R. || - x= =='1, |l,
A, f(x)) - f-
Moreover, we provide the main notation that appears in the analysis to simplify the reading of the proof:
k the stepsize at iteration A;;
AR the clipping threshold iteration k;
dg the weight for the function distance between the current point 24 and the optimal one, which allows to construct the potential Øx;
2p 1--the the initial potential, which is equal to L|| - x=1|2
We also the following standard results.
Lemma 1 (Lemma 5.1 from (Sadiev al., 2023)). Let be random vector from Rd and X
clip(X, A). Then, X
E
x < 2x. Moreover, if for some 2 0 and E (1,2) we have
E[X] Rd. E
|||
x
91
< d², and ||||| S then
F X
x
S A
x 11]
1 18A 2-0 0²
E
x
x
S 18A 1
This lemma provides sufficient bounds for quantities such as the bias and variance of the clipped stochastic gradient, which satisfies Assumption 4. Next, we use one of the most popular concentration inequalities: Bernstein's inequality (Bennett, 1962: Dzhaparidze & Van Zanten, 2001; Freedman et al., 1975).
Lemma 2 (Bernstein's 's inequality). Let the sequence of random variables (X,h22 form a martin- gale difference sequence, i.e., [X; X,-1,..., X2] O for all i 2 1. Assume that conditional variances of = F XX3 X;-1...., Xi] exist and are bounded and also assume that there exists de- terministic constant > 0 such that [Xi I c almost surely for all 2 1. Then for all b > 0, G > 0
and n
62
X
b and Σ
of
G
2xxp
2G + 2cb
Additionally, we formulate Young's 's inequality.
Proposition 1 (Young's inequality.). For any x, y Rd and p >> 0 the following inequality holds:
(1
1
|| + 2/ <
+ p) |
|lv1
p
14

---

Published as a conference paper at ICLR 2026
In partieular, for p 1
| + yll - 2//2112 + 21ly1l?
15

---

Published as a conference paper at ICLR 2026
B MISSING PROOFS
This section is organized as follows. First, we introduce an auxiliary numerical lemma required for the main proof. Next, state the descent lemma, which serves the foundation for deriving the main result. Finally, we present the convergence rate theorem for Clipped-SCo -SD based on the last iterate.
B.1 AUXILIARY NUMERICAL LEMMA
Lemma 3 (Numerical lemma). Suppose that t 2 0, t. is integer, B E (0, 1), m 2 0 and n > 0. Then, have
(t + 1)11-)))--1 1 (t (++1)-
< (t 1)
1-
(t + 1) (1-8)a
Proof. Let consider
+ (1+1)1-9-3 - 1
(1 11+1)-T-.
1- 3
For the case = it is obvious: 0 S 0. For 1.rl 2 1. it can be rewritten as
(1+ 1++1)==8 1-8
(1- In(++++ -1 (t + 1)- )
1-B (++1)-
In(t 1) (1- B) In(t +
In (t + 1)
(el1-8)lu((t)) -1 "
(t + 1)T
(1- In(++()
What is more, is known that for all we have
x
is enough to apply Taylor series or compare the growth of both parts. Therefore, with B < 1 and In(t 1) since t. 2 1, we have
(t + 1 1) (t (1+1)----
(t" 11 (ell-9)in(e-1) - n
1-9 3
(t+ 1)th
(1 In
+
In" 11)
(c1=8))n(eet)))
(t 1)th
In" In"(t + 1)
+ 1)
(t 1)th
In"(t +1)
(++1) (1+1)mm(118)p)
This finishes the proof.
B.2 DESCENT LEMMA
Lemma 4 (Descent lemma). Suppose that Assumptions 1, 2 and hold. Then, if for all 2 0 we have 7 2r. after K iterations of Clipped-SGD, we have
K-1
K-1
K-1
Φ v U Σ L (ax - 0k)
Σ den (Vf(xx), 0k) + k=0
Σ (d++1 InZ + Ln
k=
k=
where dx+1 == dx + 2% du and t := dx(f(xk) fr) + L 12 1²1 -
Proof. We start with the definition of 2b:
Φx+1 D (f f+) + L| b4 x111 dx(f(x)) -f¹) -1| x=1
= df - f(xx)) + -d++1- - (FT)) - -
I[[ x² 2²12 - -1117 x= =²1)
16

---

Published as a conference paper at ICLR 2026
Decomposing the last term allows, obtain
$ k++1 4x =d++1(f - (xx+) + (de+1 df)(((ak)) fm
+ ((2 (ax+1 - Tk. 2g x²) + 12 - xx
Applying T-smoothness to the first term and using the convexity for the second one, we get
1x+1 - 2b S dk+1 (VVf(z), Ix+1 mx) - - 11 - x
+ (dx+1 dx) f T - x²))
L(2 (0L+1 Tk. Th > + || 11
(8)
Next, substitution of the update rule for 21++1 into (8) gives the following inequality;
gkk + L 11
2x+1 - 2x S dx+1 (<Tk
+ (dx+1 dx) (V (xx) -x") + L(-2((10) (gh, xx) + +1lllaa11"
Therefore, using the notation of 02 gb: ff(x), derive
(-76 (77 (Vx())), gk) + Li2 I1 11
2x+1 - 24 S dx+1
2
+ (de+1 dx) (V](zz), x²) L(-2 2 (ge, Th - x²) + >2l 11 1=10 112)
I dd+1 (-7x (Vf((=)) 0x) - 7 (x+))) (11 (
+ 110x 10x(11)
+ (dx+1 d2 - L) (V x²) - 2 (0x, 24 x²)
2 22 [L +
110x11
Combining terms, we have
2++1 42 < (-dx+1(74 - LT +
| [xx))| 27 L (0k: x²)
(dx+1 - 2Tmmk (V (x*), 0k) + (dx+1 I, I, 1 0x 11?
where use dx+1 d3 27x O. What is more, since 7/6 S Therefore, using the update of dx+11. we have (-d++1 (7k -n L result,
2ī have *k L 3.
1
S -dk Tkk and,
dx S daYk
2
2 [f(xx)]1
2n (0p, x x²) - du 7n (V 0k)
+ (dx+) L1t)110n11
< 2 (0x, I - x²) dR th (Vf(xx)) 0n) + (dx+1 + 11201
Summing up. we conclude the proof.
B.3 PROOF OF THEOREM
Theorem 2, Suppose that Assumptions 1, 2, 3 and hold. Then, if we choose
B
= min
(9)
3207.In
6(k 6((k-1)2
80 13%/-(k 1)81 In
6(k-1)
1)2
Ro min
1
Vole"
(10)
80% In
6(k+1)²
17

---

Published as a conference paper at ICLR 2026
where B is chosen
Ro
R
B min
(11)
0 L
parameter satisfies the following boundary:
2 + a
B 2 3a
then, after K iterations of Clipped-SGa -GD, we have that f(xx) f
LR
max
Rgo, La 0-1
R
2
L8
Ro
03
6(K + 1)3
=0
In²
K
K1-8
hold with probability least 6 Σ
Remark 6. During the proof, some constrains on 3 appear. This parameter obviously has a strong impact on a final convergence bound. This is why, in the course of the proof, parameter 3 must be chosen with greater care. These constraints are formulated as Conditions throughout the proof. In the end of the proof, we show that 3 2 2+a meets these conditions.
The proof constructed in the similar manner as in Sadiev et al. (2023). For each = 0, 0,1,... let consider probabilistic events Eg: inequalities
Proof.
I-1
6(t + 1)2
2 (x) x²,0)) Σ dra (Vf(z))
Σ (dde I
111)110111
s $
6(t + 1)2
i S 2 In
8
hold for all = O,...,k k simultaneously. We want to show via induction that P[E.} 2 1
For k = 0, it is obvious since the left- side of the first inequality is zero and the Σ 22
second inequality holds for 0 since the log-factor is larger than Now, let us assume that 8 T-1
P(Er-1}
Σ for some T 1. Then, applying Lemma 4, we have
④ < 20-
Σ
ML (z) x², 01) Σ
dra (Vf(z)) 01) +
Σ (d L 11)
(12)
1=0
1=0
1=
for all t = O,...,T. T. Moreover, for all t O...., T the event Ey- implies
Φ. < 80
Σ
mb (or -0--x0000 x0,0,)
Σ
dm (VI()), +
(de Lni + 1
1=0
1=0
1=0
6(t 1)
2 In
At the same time, the event Ey-1 implies
AL. In
(L( t> 0:
t> 0;
de
( || x-11,
t t2 0;
2.2 12 In
6((++)2
t2 0;
18

---

Published as a conference paper at ICLR 2026
((+++)2) where we use df(f(z)) - f*) = 2, 2LR
Moreover, the bound
8
2I.Ro [ N In (9)
vdo
also holds since do 0 and we define 1/0 +00. Therefore, we get
6(t + 1)2 5
min 1
(110 X
[V < 20 In
S
(13)
2
Simultaneously, we have that ET-1 implies
Φ. /2
6(L 6(1++1
+ 1)2
|00 x S L
S
(14)
5
Therefore, if we define random vectors 7) and 24
vf(e), [Vf( & 2o In 1)2
min Vdd 1
1,,11
0,
otherwise,
and
Tt x², | - x--1=11 v2 In 6(1+1)2
14 =
0,
otherwise,
then 7/ and Pe can be upper bounded with probability 1. What is more, using (13) and (14), we can rewrite (12) using the new notation for truncated vectors and decomposing O, into bias and unbiased terms: Er-1 implies
T-1
T < p
Σ
2 (ee, Bi)
Σ
den (n, 01) +
Σ
Lnd + 11
0=0
1=
1=
S t
Σ
2 (1, Σ 2 (me, 08)
Σ
den (ne, 071
Σ 1=
den (ne, 0%)
1=
1=
T
+
2(de+1ln Ii + int) (100812
IEc, [1081-]
Σ
2(d Int LTt)E [10811]]
1=
T-1 +
Σ
where we apply Young's 's inequality for ||0| + 06112
Next, we are going to derive a sufficient bound on each term: i...,, Ø However, before we start, let us provide additional upper bounds for the sequence {dz). For the case t 0 we have de 0. On the other hand, for > O we get
d; =
Σ k=0
2% L
<
2BL
2BL
1+ 1
dr
80 13 + 1)8 80
13//-
2
R=0
2BL
11 -
1
(15)
1
1 1- 8
19

---

Published as a conference paper at ICLR 2026
To reflect the correct behavior of convergence with 1, we need bound de as above.
Nevertheless, to obtain the correct bound for fixed a E (1, 2). it is enough to use
2BL
12-3
(16)
80
13%v 1- 3
The problem arises when we consider the limit - 1. In the next part of the proof will be shown that
1+1 3 +1
due to the constraints over B. Consequently, we could get
111
lim
instead of
el f1 -
lim B-+1
In(())
As a result, for more reasonable analysis, we must use (15) instead of (16).
Next, since the full gradients are upper-bounded by A (13), we can apply Lemma obtain that Er-1 implies
| $ 2)c;
2
|10.1| S 2,
E [10;1]]
< 18A
Now we are ready to bound terms ① W.
Bound for ① By definition 0%, we get
Eg. E (Me, 07)) 0.
Moreover, have that
((( + 1)2
(10) 6LR
$
1 (mn, 01) & 2% ||4|| ||r0| < Ro In
=
6
80
2
Next, define of:
6(t + 1)2
of Eg, 1s.1 (mc, 0,9 & 872 R In
Es. |1027
Therefore, we can apply Bernstein's 's inequality with b = 4
/2 and G = o3 In
0:21²
/20
6²
8
P and
Σ
o G
<
2exp
2G +
2cb
37
t=0
3
Consequently, we have
P
< b either
Σ
of
2
>
G
2
37
t=0
20

---

Published as a conference paper at ICLR 2026
What is more, have that Er-1 implies
6(t
1)2 8 00
6(t +
1)2
Σ
8 1. In
Eg, |101
- Σ
14 In
22-000
8
1=
T-1 1441 R
In %/2
0(
(10)
802-a
Using the upper bound on B: B
S
Re in the choice of 7/ (9), obtain that Ex implies
T
144L Ro-0 18 00 1/2
6((+1)²
T-I
144L2 13 80 + 1)80
802-a
t=
To obtain sufficient bound depending on In Thus, we obtain
6T
must have this term in the power of one.
Condition 1:
$a 3
(17)
Moreover, get
T-1 Σ 1=
T-1
$1
dr
(T)
1)
(t+ 1)
x
V6T
6T
3n
3/2 In
(18)
vō
since T' 2 1. Therefore, with (17) we have that ET implies
D In
67
1441² Rd 13- 80 + 1)8a
(17.18)
24
where we used that LR = 4o. Bound for @, The event ET- implies
6(( (6(L+ + 1)2 2000 8 1 6( (6(1+1)) 1)2
T-1 Σ
Σ mL (pe, 8+)
LL || | <
Ro in
T-1
2LR2-011 2/2
2--00= o max (dp, 1) =
8
6(t + 1)2
2LR 2 0/2
1/2
20 1 T=
8
6(t + 1)2
2LR
2-
In 0/2
80 20000~10000
(19)
1=1
21

---

Published as a conference paper at ICLR 2026
where we use max(a, b) - a" + 6" for p S 1 and do 0. To handle the first sum, apply (15) to obtain
6(( (((1+1)2)
2 2/2
1/2
20 00000~10077000 0
T-1 de d<-d--1
6(t 1)2
1)9
2L 1n
9/2
20 1 2-1
6(t + 1)2
2BL
1 (t 1
a-1
2 "/
20
0 1000000000
13%
1-3
T-1
6(t + 1)²
6BL
(t 18 1
2LR
2 In
a
2/2
2 80 00
5
80-137 13
1- 3
where in the last inequality we use
(2-9
(1 11+1)1-8- -1
(1+ 1)2-8
S
S
(20)
1-3 3
1 B
1 1 3
with 2 1. Thus, using (9) and B
R
we get
I. 3n-1
T-1
6(t + 1)²
2 a In 2/2
2a -1 000 a de 2
8
T-1
6 20 LR
(t+1)² -1
2-1
(++ -0a
(80 - 13%/ Bu In 4/2 0(1141)2)
1- 3
Consequently, applying Lemma 3, we derive
6(t + 1)3
2L
In 2/2
208000 " 2e a_
8
L 30 (80 13%/)
6 2020
(t 1++1)1----
(t (++1)-00 50
In 4/2 [((+1)/
1-3
6 2-2-00a-LLit
(80- 13t/a 3 + 1)8a-
where in the last incquality expand the sum limits and use that In " (t 1) S In (6((+1)))
For the second sum the right-hand side of (19), we substitute Yo with B Ro:
a
In 0/2 6(t (o(t+1))) 1)²)
2LR 80
Σ
2
20 0
(80 13 + 1)
Using the inequality on Σ from the previous bound with next conditions:
Condition 2:
Ba (- > 1 3
(21)
Ba > 3 //2
22

---

Published as a conference paper at ICLR 2026
conclude that Ey-1 implies
6 6-2"800-1RR, LR
2LR 20
Lp In
67
5
(80 13
2 (t+1)
(80 (tt+)
12
t=
where LRQ Dy due to the notation.
Bound for 3. Due to the definition f we get
Eg, -e (m,, 07)) 0.
Moreover, it is uniformly bounded:
In 6(++1)² 8 (10)
4LR
340
--der (n,, 077 & den 11 < 4den
c.
de
80
32
Moreover, there is no contradiction for the case t = O: the corresponding term is equal to 0 due to du = 0. Let us define of = =E.g. (der (ne, 0;)) Hence, we get
of Ee 1 [1 [10:13] di mell [Es, 1E,
[100811]
Consequently,
we can apply Bernstein's inequality with 1152:
ao
122 and
=
4 In
T-1 and
g2
8
P
3
Σ
of S
G
<
2xxp
2G +
2cb
37
automatically leads
T-1
S b either
Σ
o
2 0
2
372
What is more, we get that E implies
T-1
T-1
6(t 6(t + 1)2
d?? [| 1 Eg. [10:112] S
72d L
In
8
0=0
72d 1 R
R
In 4/2
(6(++))²
(10)
802-a
where in the first line we apply do = 0. Using the upper bound (15) on d, and (20), we obtain that Er-1 implies
L2 0a 2/2
(6(++))²
Σ t=
8
6BL
(L+
()+1)2-3
802-a
80 13%/
3
R
Therefore, substituting 7 with B <
allows to get that E implies
σ L3
T-1 72 - 000 In 2/2
6((+1)²
6BL
(t 1)' 1-8 18811
802-a
80 13%
1 -
1=0
432L²
(t 1)2-8
(1 + 1)-80 80.
802-a(80 13//) No In
0/2 (((++)))
1 1- 3
23

---

Published as a conference paper at ICLR 2026
Applying Lemma 3, we obtain that Er-1 implies
4321, Rg
Σ
802-a(80- 13 3 (t + 1) (1--))1)
Thus, conditions over / can be formulated as follows:
Condition 3:
2 + ox
3a - 330/2 1 8
(22)
3a
Consequently, with (22), we have
432L Rd
(18)
64843 In
67
$ In
67
802-a(80 134/) 2 (1 1
802-a (80 13
3m
1152
t=0
Bound for @ The event Er-1 implies
T-1
Σ
de (T. 87)
Σ dr |1 |
In 6(8+1)2
2
2d 2d %T.R
dg
x X
(10)
2 2.20 180-000-111
1//0
L.
6(l + (6(++))² 1)2
max max(dr, 1) =
7t
8
T-1
6(( (6 + 1)2
800 100-11,/2 2
R a I/
8
T-1
2.20. 80 100-1,0 2 0 4/2 6(( (b((+1)) 1)2
+
t=1
where we use dg = 0 and de max dr, "²
max dd. 1; if de S 1. we have
de max(de, 1] _ < 1; otherwise have d/² max 1) - < d²'2 Hence, bound the first term, we apply d, < de+1 and substitute the upper bound on de from (15):
<
T-1
2. 2a 80
2//2
LR oa In 2/2
"n
(ot
6(t + 1)2
(6 ( 1)2
2.2"
80
-0001100 LR
2-a a 4/2 4/2
8
1=1
T-1
2. 2.
80
11,
1 1.R- 0 o/2
6(1 (6(1+ 1)2
6BL
(1+ 1)1-8 -
80 13
1-
T-1
6(L + 1)2
+
a0a Σ 2.
1, L a In 0/2
8
[++1)] 9
where we bound
1-8 in the similar manner as for previous terms with / > 1. Now, we
can substitute the choice of 7 from (9) with the upper bound on B: B
R for the first term,
24

---

Published as a conference paper at ICLR 2026
and B v Ra for the second term, to derive
T-1
6(t 1)2
6BL
(t + 1-1
8
x
2.2". 80 100-12 LR 0 In 0/2
80 13
1- 3
6(t + 1)3
2. 2 80
7," Li
0 In 0/2
6
t=1
12. 2 80 LR
+ 1) 1
(++ 1) 8ax
(80 13%) % 6(e+1)²)
1
8
2.2". 80 LR
(t + 1) Ba_ 1a
(80 13/.)e )a
Applying Lemma 3, we get
12. 2 80 LR?
$ (t+ (6+1)1-9-1 - 1)
(t+ ()=a
(80 13)=)
2 In 4/2
[((++1)2
1-
8
2.2" 80 LR
(t + 1) Ba
(80 13
12. 2a 800-1L12
T
2. -800
(80 13 7 (t + 1) 1)80 (1- 0jo/2
(80- (3 1)
To derive a sufficient boundary, it is enough to apply next conditions over 3:
Condition 4:
( Sa 2 1 ( - 8/ 2
(23)
1 82
2+a 30
Hence, we have
-00-800-1L LR3
2. 80 LR3 (18)
Do In
6T
t= (80 1/4/
3 (L +
(80 13%a)a(1 +
12
t=1
where we expand the sum limits and abuse the notation of t
Bound for (,, At first, we have
Eg. 2(de+1 + LT7) (1107112- - Ec, [10:11]])
Moreover, we get that
2dde41 + Int) (10%111 Es. [1ee|19]]
Lus1 (8d.I + 24L77)
< 8(d441 Li
L S
(10) 324
40 c. s
6400 S
Let us define oā Iee. 4ež (1001122 IEe. [109111] Consequently, it can be bounded as fol-
lows:
of = Eel A(de+ibig + LxZ)² (100)) [Es, [100912]]* 2
< clss, 12(des1 + |nt (10%112- Le. [108 1²]
< 4c(de41L1g Ln? Eg. [16.11]]
25

---

Published as a conference paper at ICLR 2026
Therefore, apply Bernstein's 's inequality with b 4 (n)((=))) )/8 and G
03 1g]n(
)/388:
T-1 Σ
b²
8
P
b and
oo S
2
G
eexp
2G +
2ch
31
t=0
3
Hence, we derive
P
S b either
Σ
2 >
G
21
372
t=
What is more, we get
T-1
4.11d,+2In T-1 5
Σ oo S
+ &
[10291]]
72c(d,L1 + +3
T-1
2- 0a +
216cL1,
-,000
(24)
t=
where in the last equation we use do obtain
O. To deal with the first term of (24), we substitute (10) to
(10)
72cd? LR a "n00"a 802 a In 1-022 0(++1)2
72cd 1/2 LR "2600"
L
2-2-a 0
802-a In 1-02 [(++1)2
t=1
8
Next, we apply (15) to substitute the upper bound on de+1:
T-1
72ed 1/2 IRR- 0
72ed Lix 222- 00 <
802 In
1-122 6((+1))
RocT.Rg-a700 72cI. 2000
6BL (1+1)1-0 1
9/2
1-4/3 In 802-a
6(t+1))
80 13%
1- 3
where we also use the idea that 1 1 (9), one can derive
((+1)--8-)
< <3
for all I 2 1. Using the choice of ?
1-3
1-
T
72cd L 22 22-00000000 0
12cLRR-aad
10th
6BL
(t 1)2-8 9/2
802 In 1-0/2
6(++1))
80 - 13%
3
432cLR3
t=1 802-a(80 134/
2 In 14//2 6(141)²
(t + 1)1-8
4/2
(t ( 1) 18 Baa
1-3
where in the last inequality we apply B <
r. Thus, noting that the RHS can be bounded
according to Lemma 3, we get
432cLR2
72cd L 22 2- <
(25)
802-0 131/u) 2 1 6((+1)2
(++
1)1-3 ((+1)1--11)
-1) 1-B
%/2
(t + 1 3a
T-1
432cLR2
<
(26)
802-a(80- 13'/a²
80
(t + 81-)/18)
1=1
26

---

Published as a conference paper at ICLR 2026
To handle with the second term from (24), substitute the upper bound on d (10) and y with
B < Ro:
T-1
2-00 0a (10)
216cI
R8-00
(9)
T
216cLR
216cLn,,,
(27)
802-a In 1-/2
6[1+1)2
802
13(t + 1)
Thus, if we choose 3 as follows:
Condition
Ba 2 1 82 1
(28)
Ba (1 (1- 3)0/2 2 1 = 82
2ta 30
combining (25), (27) and (28), we derive
T
128) o S
432cI.R 802-a 13 30 (t (t+1) 1)
T-1
216cI.R 802. 13(t +1)
(18)
D7 In
6T
384
where we expand the sum limits for the first term, apply (18) to bound Σ 4 substitute the value e and abuse the notation of Po.
Bound for @, The event ET-1 implies
Σ 2(1++1 L2? + L7) Es, [10913
36 + Ln?)) 00
T-1
36d, L a 0" +
10 0",
(29)
t=1
t=0
where we use dr+1 = de + 1,,,, Ln S 1 and do O. Next, we bound the first term from (29) as follows:
T-1
36d 1/2 LR "If²
Lo 2-0 00h <
36d 1 2-a σa
802-a In 1-%/ (((+1)2
Subsequently, we can use (15) bound de41:
T-1
T-1
36d 0/2 Rg aaaaa
36dgL 122--000 0 <
802-0 In 1-///
6(++1)
a 36LR2
6BL
(L+ 1+1-1
%/2
802-a In 1-9/2
6(4+112
80 13
1- 9
6
Substitution of (9) with the boundary B < ...
R
allows derive
36LR, "2f0" 0
6BL
(++ 1) -1
%/2
802 a In 1-/2
6(L+1)²
80 13%₂a
1- -B
1=1
216LR
802-a 13//a² Ap In 1+0/2
6(f+1)2
(1+1)1-82 -1
4/2
(t 1) -a
1 1-
27

---

Published as a conference paper at ICLR 2026
Applying Lemma 3 to the RHS, we obtain
216LR1
36d, L 0
(30)
802-0 13 (t + 1) 1) 11- 11-1//
To deal with the second term from (29), enough to substitute upper bounds on X and 76 with
B S Ro.
(10)
10 a
(9)
T
108
108
000
(31)
802 a
In
1-9/2
6((+1)2
80
13(t + 1)50
t=
Therefore, if we choose 33 in the following way:
Condition
Ba 2 1= 82 1, Ba - (1 - 3)9/2 2 1 2
(32)
2+ 30
combining (30), (31) and (32), one can obtain
67
216LR 802-a 13 (++1)
108LR3
(18)
8
802
13(t +
16
where we also expand sum limits the first term and apply (18).
Bound for @, According to the event ET we have
2(d Li? + LTt) o2a
Σ 0=
2(d + L
2
t=
(10)
T
T-12
2-
20
(de Tr? 2a g In
a-1
6(++1)² max (d,, 11a-1
0
R2a0
where in the last inequality we also use that de+1 = d, + 2T. S d, - 2. Next, if d, < 1, we have that d, + E 4; otherwise, we get de + S 4d,. Thus, one can obtain (d, + 3) max (de, a S 4 max 1}, which allows to have
8 20 Ly2a - a-1 6((++)2
Σ 2(d++ Int + 10
R20-2
T- 8 10-80 2 in
2a
40
In a-1
6((+1)²
(33)
R2n
where we apply maxfa, 6)0-1 < 0-1 + 1- due to a S 1 and combine terms according to the power of d, with mentioning that du for the first term. The following idea is similar with previous bound- - for the first term we use the bound on d, (15) and apply Lemma 3; after this, we substitute the choice of y. with corresponding upper bound on B for each term. Consequently,
28

---

Published as a conference paper at ICLR 2026
have
T-18
80 2 di Ln 00 In a- [[(++])
8. 20
-40 2
In a-1
(((+1)²
Ro
22a-
R6 12a-2
IA W3
T-1 8 -00 2
1t
20
4 2a In-1
6((+1)
6BL
(1+ 1)2
IM
R
80 13%₂
1
IMi
I
288 802a-2110
LR 4a
(L (1+1))-9-
(1 + 1)
1) -28a
(80- 13%/ )30 In a+1 6(t+1)2
1 1-
288 202a-2LR? 1"
IA
(34)
80
(t (3 + 1)28a (1 (1-8)m)
R
where we use the upper bound on B: B <
For the second term from (33), we get
T-18 8-888822-222 20 Lnd
4 ln a-
6(++1))
8 80 4
(35)
R
Ran2
(80- 13 (2a 1)28a
L=
where we apply B <
Rt Hence, to obtain the sufficient bound, it is enough to choose B as follows:
Condition
2Ba 2 1 82 2a 2,a (1 3)a 2 11
(36)
1+ Sa
As result, combining (34), (35) and (36), we derive
67
288 802a LI
T-1
8 240
Py
(80 13 300 1)
(80
16
where we abuse the notation L = Lo.
Final bound. If we formulate events Ex,, Ex, Ex as follows:
2o 6(T)²
$ In 6(2)²
8
Fee
1 5
either
2
24
6(T)²
4 In 6[T))
4 In
8
Es
(
either
12
1152
$ In
((T)²
& In
(O(T)"
Eg
@ <
either
8
384
then the event Ey
n Ex
n
Eg n Ex implies
2o In
2o In
6T
2
6
4
6T
8
8
4r < 20 +
+3 3
+
2
12
8
16
6
2 In
8
Consequently, we have
2 Ea
-1- 1
n
Eg
=
E n Es}
T-1 Σ
35
1
2 1 -
1
6
12
3T
8
[
[=1
29

---

Published as a conference paper at ICLR 2026
This finishes the inductive step of the proof. Therefore, the event Ex implies
6(K + 1)2
Φ S 20p In
with probability at least 8 pz. Abusing the notation, with do have
[6(K 1)
dx([(xx)) - 1*) 2L In
5
Thus, the event Ex implies
LR In
(((++)2
Rg In
6(K++))
f(Ik)
(37)
K-1
K-
Σ
mL
Σ
7t
t=
t=0
Moreover, is known that
Σ
04
1
1=1
n
Σ
R1
for a; > 0, since it is AM-HM inequality, Thus, applying it with a;
1
(37) leads
76
Rg In
[6(+1))
Rg In
(6(++1)²
5
f(xx) - S
K
K2
t= Tt.
t=0
Substituting (9), we have
RB In
6(K
6(K+1)²
K 1
f(Ix) - ft <
K2
k=
R In
(((+1)2
[((k + 1)2
80 10 (K + 1)8 In
((k++))
max
32
K2
B
Before we provide final bound, let us emphasize an important point. Combining Conditions 1- It is easy to verify that & should be
we should choose 3 max { @ 3a-I+
a+1
2+a
a+1
3a
I0-I
3a
greater than 3a
2+a What is more, using that
6(k: + 1)2
6(K + 1)²
In
< In
8
and
K
(k + 1) = Σ
K
h < K3 + f
K
1o = K8 +
K1+B
< 1K1+8
1 3
k=
k=1
we conclude
[(xx) 8 8r
LR In? 66(K+)2
max
Roo I 3. 1 R
Sa
L
R
a3
ln2 [6(K+))2
=0
K
K1-3
30

---

Published as a conference paper at ICLR 2026
Noting that choose 3 as the best possible one, i.e. B we obtain
2+a
4n-2
max
ROo, L R
L Ro 0
LR
f(xx) -5=
K
Ra-2
30
where Õ()) denotes polylogarithmic dependency. This concludes the proof.
31


Reviews:
[{"review_id": "H8FgeL94ve", "reviewer": "Reviewer_Mpxc", "summary": "This paper studies **Clipped Stochastic Gradient Descent (Clipped-SGD)** under **heavy-tailed noise**—that is, when the stochastic gradient only has a finite α-th moment for α ∈ (1, 2]. The authors provide, for the **first time**, *high-probability* convergence guarantees for the **last iterate** (as opposed to the more typical average iterate) on convex, L-smooth objectives.\n\nTheir main result shows that the last iterate of Clipped-SGD achieves a convergence rate of\n[\nO!\\left(\\frac{\\mathrm{polylog}(K/\\delta)}{K^{2(\\alpha-1)/(3\\alpha)}}\\right)\n]\nwith failure probability ≤ δ.\n\nThey also propose *horizon-free* step-size (γₖ) and clipping-level (λₖ) schedules—meaning they do not require knowing the total number of iterations in advance—and verify their theory empirically.", "questions": "In your final convergence result, the learning rate $\\gamma$ explicitly depends on the confidence parameter $\\delta,$ i.e., $\\gamma_k \\propto 1 / \\ln^3(1/\\delta).$\nThis dependence between the step size and the high-probability confidence level is quite unusual in the stochastic optimization literature, where $\\gamma$ is typically independent of probabilistic guarantees.\nCould the authors clarify **why this dependence is necessary** in your analysis?\nIs it an intrinsic requirement of the heavy-tailed, high-probability setting, or merely a technical artifact introduced by the proof method (e.g., via union bounds or Freedman’s inequality)?\n\nIf this coupling is indeed required, the authors should provide a **rigorous necessity proof** to justify it, since this assumption significantly restricts the generality of the result.\n Moreover, **if such δ-dependent compression of the learning rate is generally allowed**, then even many divergent dynamical systems — for example,\n$$\nx_{n+1} = x_n - \\gamma_n x_n^2+\\gamma_n x_n^4 + \\gamma_n z_n, \\quad (z_n \\sim \\mathcal{N}(0,1))\n$$\n—could be made to appear *artificially stable* or “high-probability convergent” simply by shrinking $\\gamma_n$ according to a small δ.\nThis type of construction is **well known from standard graduate-level stochastic process exercises taught in mathematics departments**, and therefore **cannot be regarded as a publishable theoretical contribution** unless the authors rigorously prove that the δ-dependence is both mathematically necessary and not a by-product of overly conservative probabilistic bounding", "limitations": "", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **First High-Probability Last-Iterate Result under Heavy Tails**\n   Previous work established only *expected* convergence or *average-iterate* guarantees. This paper closes a notable theoretical gap by analyzing the **last iterate** under α-th moment assumptions, a more realistic model for gradient noise in large-scale ML.\n\n2. **Novel Potential-Based Proof**\n   The authors design a custom potential function Φₖ combining function suboptimality and distance to optimum. This enables applying **Freedman/Bernstein inequalities** for martingale control, producing high-probability results without strong boundedness assumptions.\n\n3. **Horizon-Free (Any-Time) Step-Size and Clipping**\n   The method adaptively scales γₖ and λₖ using logarithmic corrections in δ, ensuring convergence without pre-specifying total iterations. This is practical for streaming or online settings.\n\n4. **Solid Empirical Verification**\n   The authors validate theory with synthetic and logistic regression problems under heavy-tailed (Pareto, Student-t) noise, showing that the **last iterate consistently outperforms the average iterate**.", "weaknesses": "1. **Limited Empirical Scope**\n   Only simple convex problems (logistic, quadratic) are tested. Including real datasets or large-scale ML examples (e.g., transformer finetuning) would strengthen impact.\n\n2. **Complex Presentation**\n   The notation (γₖ, λₖ, dₖ, bₖ, Φ₀, C, p(Φ₀,L,σ)) is extremely dense. The exposition would benefit from a simplified summary table for parameters and clearer intuition for each scaling choice.\n\n3. **Lack of Sharpness at α=2**\n   When α = 2 (finite variance), the bound leaves a polynomial gap from the optimal O(1/√K) rate. The authors acknowledge this, but it remains an open issue.\n\n4. **δ-Dependence Obscures Practical Interpretation**\n   The interplay between the learning rate γ and the probability parameter δ—key to your question—is not explicitly analyzed beyond asymptotic scaling.", "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": "fs9LWQuf0O", "reviewer": "Reviewer_7EUw", "summary": "This paper presents an analysis of SGD for heavy-tailed gradients with bounded alpha-moment and convergence rate 1/T^{2(alpha-1)/(3alpha)} for smooth convex objectives.", "questions": "Please address the weakness above. Happy to revise my opinion.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "I am not aware of other results on this problem, and the execution seems good.", "weaknesses": "The convergence rate is not optimal. This makes the paper somewhat incremental because if you allow projection into a bounded diameter domain, you get the optimal rate (without clipping). This is a straightforward consequence of recent results connecting the last iterate of SGD with linear decay schedules and regret analysis, along with the same martingale/bias arguments used to bound error from clipping in this paper (see e.g. https://arxiv.org/abs/2310.07831 and the more general result in https://arxiv.org/abs/2405.15682). Essentially, one needs only show that the linearized regret of projected online gradient descent is bounded in high probability, which I think is not too hard using the standard concentration of clipped values arguments presented here if the gradients are clipped and the iterates are bounded by some projection.\n\nWithout the projection, there is some difficulty and so the present paper does have value. My concern is that this difference seems relatively small.\n\nIf it were possible to achieve the optimal rate without projection, or (even better) show that the optimal rate is NOT achievable without projections, that would be a much better result.", "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": "LuQoRBcPH9", "reviewer": "Reviewer_TuTb", "summary": "The paper provides the first high-probability last-iterate convergence rate of Clipped SGD. The authors also conducted numerical experiments demonstrating that the last iterate of Clipped SGD indeed converges.", "questions": "In addition to the weaknesses mentioned earlier, it seems the current proof cannot be directly extended to constrained optimization. Could the authors provide any discussion on this issue?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The result is meaningful, as it fills a gap in the literature.", "weaknesses": "1. Line 112, when talking about the heavy-tailed noise, the finite-sum problem is not a proper example. Note that for this kind of problem, a finite $\\alpha$-th central moment directly implies a finite $2$nd central moment.\n\n1. Line 116, missing $\\\\\\{\\\\\\}$ for ${x_k}_{k=0}^K$.\n\n1. Some statements in Section 3 are inaccurate.\n\n    1. Line 142, $\\widetilde{\\mathcal{O}}$ is not necessary and instead should be $\\mathcal{O}$ since the current description doesn't limit to the case of an unknown $K$.\n\n    1. Line 149, missing $)$ after $\\mathbb{E}[...]$. In addition, Fatkhullin et al. (2025) didn't consider exactly the same condition as in the current Assumption 3.\n    \n    1. For the in-expectation convergence under heavy-tailed noise, the authors missed a relevant work [1]. Note that for the non-smooth Lipschitz case, [1] showed both average-iterate and last-iterate convergence. For the smooth case, [1] also showed the average-iterate convergence.\n\n    1. Still in Table 1, if the results in (Nguyen et al., 2023) are better than (Sadiev et al., 2023) from every perspective, then I don't see the point of putting (Sadiev et al., 2023) in it.\n\n    1. Line 192,  none of these four works (Nazin et al., 2019; Gorbunov et al., 2020; Gorbunov et al., 2024; Parletta et al., 2024) consider heavy-tailed noise. (Liu & Zhou, 2024) didn't study clipping methods.\n\n    **Reference** \n\n    [1] Liu, Z. (2025). Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications. arXiv preprint arXiv:2508.07473.\n\n1. In the statement of Theorem 1: \n\n    1. No definition of $d_k$ is provided. \n\n    1. I don't see why $p$ is a function of $L$. Do the authors mean $C$?\n\n    1. The definition of $C$ is also not proper. It involves solving a fixed-point equation. However, the authors didn't discuss whether it is always solvable (or any other related discussion). In addition, since $\\Phi_0=C\\\\\\|x_0-x^\\*\\\\\\|^2/2$, which cannot be evaluated in general due to the unknown value $\\\\\\|x_0-x^*\\\\\\|$.\n\n1. The whole paper relies on the existence of $x^*$, which the authors should state clearly.\n\n1. About numerical experiments:\n\n    1. For all experiments, could the authors also provide the empirical mean and standard deviation for both the average iterate and the last iterate?\n\n    1. In Line 307, the authors said the step-size and clipping level schedules are selected based on the theory. Could the authors provide more details? Especially, for $f(x)=\\ln(1+\\exp(\\langle x,a\\rangle))$, this objective doesn't have an optimal solution on $\\mathbb{R}^d$ (also implying $\\\\\\|x_0-x^\\*\\\\\\|=+\\infty$), which clearly differs from the current theorem. Could the authors provide more details? \n\n1. I appreciate the authors' honesty about the limitations discussed in Section 6. However, I have to repeat that the current rate $\\tilde{O}(1/K^\\frac{2(\\alpha-1)}{3\\alpha})$ seems not optimal.\n\n1. The analysis is somewhat standard, without introducing any new techniques, as far as I can see.\n\n1. The proof is not written in a mathematically rigorous manner. For example, the two inequalities in Lines 893-897 only hold conditionally on the event $E_{T-1}$. This means that one cannot directly invoke Bernstein’s inequality in the following proof. Instead, one should do one more step to introduce some proxy variables, like many prior works (e.g., the indicator variable $\\mathbb{I}[\\Phi_t\\leq 2\\Phi_0\\log(6(t+1)^2/\\delta)]$). Therefore, I believe many parts of the proof should be carefully revised.", "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": "AflskNiWI0", "reviewer": "Reviewer_BKzV", "summary": "The paper studies high-probability last-iterate guarantees for Clipped-SGD on convex L-smooth objectives under heavy-tailed noise with finite \\alpha-th moments ($\\alpha \\in (1,2]$). It proposes a potential-based analysis with horizon-free step size and a clipping level scaling as $1/\\sqrt{b_k}$, and proves a last-iterate rate $O(K^{-2(\\alpha-1)/(3\\alpha)})$.", "questions": "The paper is short with limited empirical support; the theoretical advance, while neat, is incremental and currently rate-suboptimal at $\\alpha=2$; several claims read stronger than warranted. With strengthened results and a broader empirical study, it could be a good workshop paper.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "- Addresses a practically relevant “last-iterate” question for clipped methods under heavy-tailed noise; the setup (convex + L-smooth + $\\alpha$-moment) is standard and clearly stated.\n\n- Writing is generally clear; related-work table situates results among expectation and high-probability bounds (SGD / clipped-SGD, average vs last iterate).", "weaknesses": "- Short and narrow in scope. The paper reads like a concise note; the empirical section is minimal (toy problems, limited baselines).\n- Limited contribution vs. prior art. While the shift to high-probability \\emph{last-iterate} guarantees under heavy tails is interesting, the improvement over existing results is incremental and tightly scoped to convex $L$-smooth objectives.\n- Suboptimal rate at $\\alpha=2$. Instantiating the main bound with $\\alpha=2$ yields a last-iterate rate $\\tilde{\\mathcal{O}}(K^{-1/3})$, leaving a \\emph{polynomial gap} to the known $\\tilde{\\mathcal{O}}(K^{-1/2})$ benchmark in the finite-variance setting.\n- Overclaim / framing. Phrases such as “close a long-standing gap” and “first high-probability last-iterate guarantees” are stronger than warranted given the convex-only scope and the $\\alpha=2$ suboptimality; related work is not contrasted with sufficient precision to delimit novelty.", "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)