Convergence of Clipped SGD on Convex $(L_0,L_1)$-Smooth Functions
Authors: Ofir Gaash
Kfir Yehuda Levy
Yair Carmon
Venue: NeurIPS 2025 poster ()
Keywords: convex optimization
stochastic optimization
smooth optimization
generalized smoothness
Primary area: optimization
TL;DR: We show that clipped SGD converges with high probability on convex $(L_0,L_1)$-smooth functions.

Abstract: We study stochastic gradient descent (SGD) with gradient clipping on convex functions under a generalized smoothness assumption called $(L_0,L_1)$-smoothness. Using gradient clipping, we establish a high probability convergence rate that matches the SGD rate in the $L$ smooth case up to polylogarithmic factors and additive terms. We also propose a variation of adaptive SGD with gradient clipping, which achieves the same guarantee. We perform empirical experiments to examine our theory and algorithmic choices.

Convergence of Clipped SGD on Convex (Lo, Li)Soooth Functions
Ofir Gaash"
Kfir Yehuda Levy?
Yair Carmon"
Abstract
We study stochastic gradient descent (SGD) with gradient clipping on convex functions under generalized smoothness assumption called (To, I4 -mmoohnnsssss.. Using gradient clipping, we establish a high probability convergence rate that matches the SGD rate in the L smooth case up to polylogarithmic factors and additive terms. We also propose a variation of adaptive SGD with gradient clipping, which achieves the same guarantee. We perform empirical experiments to examine our theory and algorithmic choices.
Introduction
Gradient clipping is a common method for stabilizing neural network training. Despite its wide use, little thought is given to the choice of the clipping threshold, with many works fixing at I without attempting to tune it [3, 5, 34, 35, 2, 20, 21J. In pursuit of a theory-driven threshold choice, recent research tries better understand the benefits of gradient clipping.
Experiments suggest that clipping is effective situations where small changes input can lead to significant variations in gradient norms [44, 43]. This observation has led Zhang et al. [44] to formally define this behavior as the following "relaxed" smoothness property.
Definition 1. A twice-differentiable function f RRd R is (Tn, [-)-mmothh if for every x E Rd it holds that f(x)) < Lo + fxx)-
In words, (To; L1) smmoohhnssss allows the Hessian norm increase linearly in the gradient norm. This is opposed to the traditional smoothness property, which says that the Hessian norm bounded by constant, coinciding with the new definition for L1
Building on this definition, Zhang et al. [44] show instances where clipped SGD outperforms standard SGD. Specifically, they denote M = sup / (=)]l f(x) < f (2 and show that the complexity of SGD with a fixed stepsize is larger than the complexity of SGD with gradient clipping by a factor of L (assuming both algorithms are initialized at 2n). This factor can be very large: in particular, may be exponential in L1 Ro. where Ro is the initial distance from the optimum (see Appendix G).
The connection between (Lo, In --mooothness and gradient clipping has led researchers attempt characterize the complexity of (To. In )smoohhh optimization, mainly in terms the dependence on T1 The non-convex setting is well understood: the state-of-the-art rate of gradient norm convergence comprises of the rate for Lo-shh functions and additional low-order terms that depend on L1. This holds for both clipped GD [38] and clipped SGD [37] (see Section 2 for details).
Motivation for studying the convex setting. Despite being originally motivated by the behavior of (non-convex) neural networks, generalized smoothness is also compelling study in the convex setting. There are several instances where convex analysis closely aligns with empirical behavior; among them are AdaGrad- Caadd algorithms and the momentum technique, in which theory preceded
"Tel Aviv University, of irgaashemaal.. acu.ac. 11 and ycarmon@@mail.com
Technion, bryaedd@gmalll. com.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

practice [29, 3.. Furthermore, a body of work show that neural networks have convex-lik behavior [14, 46, 22]. From a theoretical perspective, allows to examine whether the pattern observed for gradient norm convergence an Le-smooth rate with low-order T. T.-ddpeedent terms also holds for optimality gap convergence.
These considerations have motivated recent work to study the convex, (Lo, Li -smmohhhh setting [15, 18, 11. 38. 37, 24]. For clipped GD, [11, 38, 37, 24J prove an optimality gap convergence rate following the aforementioned pattern. However, prior work does not provide a corresponding result in the stochastic setting (we discuss concurrent work by Lobanov and Gasnikov [23] in Section 2). The difficulty of the stochastic, convex regime stems from the fact that clipping biases stochastic gradients. Bias is arguably more challenging in the convex setting than in the non-convex setting: the former intimately relies on stochastic gradients being unbiased. while for the latter it suffices to average enough stochastic gradient such that the noise drops below the required degree of stationarity [15]. This is potentially the reason previous studies of the convex setting (18, 15] proved convergence only in the deterministic regime.
Our contribution. In this work, we analyze gradient clipping in the convex, stochastic, (Lo, L1)- smooth setting with light-tailed noise. Our contributions are as follows.
We show that the pattern of an Lo-smooth convergence rate with L Le-deeendent low-order terms extends to the stochastic convex setting. For clipped SGD with o-sub-Gaussian gradient noise, we prove a sub-optimality bound of O Log(T//)Looi,,
log" (TT that holds with probability at vT
T
least 1 8 for T = 2(log ( ())) That is, we bound the stochastic gradient query complexity
of achieving optimality gap with probability least 1 - by Ö Ō(Ln "BR 2
(L)
where Ō(.) hides factors poly-logarithmic in dz- This matches the best known bounds for (fixed step-size) SGD in the Lo-smooth case, which are 9 Lo =²m [16]. Our bound depends on
Lj only through an additive term, with no implicit dependence on exp(L,
We show the same complexity bound for two variations of SGD: adaptive SGD [25] with clipping. and SGD with a variable stepsize which we refer to as "implicit clipping."
We show that, to achieve the bounds above, precise knowledge of the parameter T, is not required: simply replacing L1 by the conservative choice ( Ru) suffices. This result does not appear in papers studying the deterministic regime.
We perform numerical experiments test the impact of gradient clipping for SGD on convex, (Io, -mmosh functions, and assess the empirical effect of some of our algorithmic choices.
To address the bias of stochastic gradients that is introduced by clipping, we employ a double sampling technique that uses two independent stochastic gradient samples in each update: one to estimate the direction of the update, and another to estimate its magnitude. This technique is necessary in order to apply some of the probabilistic tools we use, which assume sequences of unbiased random variables. but our empirical analysis suggests it might not be helpful in practice. We elaborate on this technique in the analysis as well as in the experiments.
The paper organization is as follows. In Section 2 we survey related work. In Section 3 we outline algorithmic framework and prove our theoretic results. In Section 4 we deseribe our experiments and discuss their results. In Section 5 we provide a short conclusion.
2 Related work
Generalized smoothness definitions. Zhang et al. [44] first introduced the concept of (Lo, Lz)- smoothness as in Definition 1. Zhang et al. [43], Gorbunov et al. [11], Vankov et al. [38] provide useful equivalent definitions. et al. [18] introduce an even more general notion of smoothness: given a non- decreasing continuous function f, they define f-smoothness as the property [ < {([][(())] l))
Yu et al. [42] extend E-smoothness to Ea sm-ooootssss by allowing the choice of non-euclidean norm. In this work, we focus on (Lo, L1) smoothhsss..
2

---

Algorithms for (Lo, L1 s-mohhhthh optimization. Most prior work [44, 43, 30, 15, 11, 38, 24. 37] consider GD/SGD with gradient clipping, where the stepsize is of the form vf' min 1, Toī or ' Tollte where g is (possibly stochastic) gradient. Zhang et al. [44], Vankov et al. [38] show that these two forms are closely related. While we focus on clipping methods, other methods are also analyzed under (Tog [1] ssmoothssss such normalized stepsizes [45, 4, 41], Polyak stepsizes [33, 11, 38], coordinate descent methods [24], adaptive SGD [8, 39, 13] and Adam [17, 12, 40].
Gradient clipping for (Lo, -smoohh functions. The non-convex regime was the first to be explored. Zhang et al. [44] provide the first theoretical demonstration of the advantage of clipped GD. and Koloskova et al. [15], Vankov et al. [38]. Tyurin [37] subsequently improve the bounds to O v L +
L Clipped SGD is considered under several noise assumptions. Zhang et al. [44, 43] consider a o-bounded gradient noise with probability 1. Zhang et al. [44] prove a rate of (((())()/)))))))))))))))))) / (Lo + L1o)
/T) where A = A (Lo + + L1- Zhang et al. [43] prove a rate of O( (LTT//)/T//1) for T = ( While the former has no conditions on T, the latter has better dependeney on the problem parameters. Li et al. [18], Koloskova et al. [15] consider o-bounded gradient noise variance. Li et al. [18] prove a rate that has a dependency on the initial gradient norm, and Koloskova et al. [15] show an unavoidable bias term when considering all clipping thresholds at once. Tyurin [37] consider light-tailed noise, and using a batch size of O(o2T), obtain a rate of O
The convex regime recently received much attention. Koloskova et al. [15], Li et al. [18] prove convergence rate for clipped GD where the dominating term is O(L + Ri/ where M is the maximal gradient norm among the iterates. Yu et al. [42] extend the result of Li et al. [18] to Mirror Descent. As discussed in the introduction, the term M may be exponential in L, Rg Gorbunov et al. [11], Vankov et al. [38] independently prove a convergence rate of O LLoR3 R5/T) /) with additive factors of L3 Ry and min L3 L1 Ro log log(AZ)), respectively. Lobanov et al. [24] show that in some initial phase of the algorithm, clipped GD enjoys linear convergence. Gorbunov et al. [11], Vankov et al. [38] both propose acceleration methods; The former has exponential dependency on Ru, and the latter requires to solve a meeddimenioonll optimization problem in each iteration.
In the stochastic convex case, Gorbunov et al. [11] consider finite-sum functions, with an additional assumption that all the functions share a common minimizer. They show convergence rate of OLL,RR/T) in expectation for T = ( where n is the number of functions. In concurrent and independent work, Lobanov and Gasnikov [23] present general framework and study both first- and zero-order methods. Assuming bounded noise variance, they obtain bounds for arbitrary clipping thresholds, and prove linear convergence in some special cases. However, their rate of convergence depends on M and A, both of which may be exponential in L, Rg- Another concurrent and independent work [42] studies Stochastic Mirror Descent Emoohh functions. Under noise variance assumpptin that generalizes over affine noise, they prove a high- gigh-probbbility, anytime convergence bound. Their rate, too, has an implicit exponential dependence on I, Ro-
To the best of our knowledge, our work provides the first rate of convergence for stochastic, convex, (To, I, -smooth optimization without exponential dependence on T,, Ro. and with a leading-orde order term independent of L1. For the case of a 0, our results match the state-of-the-a rate from the deterministic regime up to logarithmic factor:3 Our results hold with high probability, and the dependence on 1/5 is poly-logarithmic.
Adaptive SGD for (Lo. L1 -mmoohh functions. Faw et al. [8], Wang et al. [39] consider adaptive SGD for non-convex functions with an affine variance assumption. In the context of bounded variance, their rates translate to (I, (1a++)//887 + (LI A+t)///// VT. In similar setting, Hong and Lin [12] prove a rate that is logarithmic in 1/5, but polynomial in the dimension.
Our work on adaptive methods has several differences from the above. First, we analyze a clipped variation of adaptive SGD. Second, we consider convex functions and assume a stronger noise assumption. Third, our rate simultaneously has a poly-logarithmic dependence on 1/6, is not
'Note that the work of Lobanov et al. [24] is not directly comparable to ours: in the regime Lo > 0, their linear convergence does not hold asymptotically, but rather for some initial phase of the run.
3

---

dimension-depedn dependent, and has a weaker dependence on L1. Lastly, as for clipped SGD, we match the Sate-of-thhe-ars result from the deterministic setting up logarithmic factor.
3 Analysis
Notation.
Throughout the paper, ||-Il the Euclidean norm, (: the Euclidean dot product, P-)jx(()) is the Euclidean projection onto the set A' and (a r) is the Euclidean ball of radius centered We denote log+() 2 + log(-), R2 == | x=I and A, = f(xx)) f(x*).
Problem setting.
We consider the optimization problem
minimize (x) =E
where the function f satisfies the following.
Assumption The function f RR + R is convex, and attains a minimum some x² Rd with
distance at most R from the initialization.
Assumption 2. The function f is wwice-differemtiable and (Lo, ) smooth (see Definition 1).
We remark that the distance bound R is only required for our analysis of Clipped Adaptive SGD. Specifically, Theorem does not require (and does not require the corresponding projection operator present in Algorithm 1).
We assume access to a stochastic first-order oracle g that satisfies Blg(x)
fz) for any
Rd. We consider two different noise assumptions. Assumption 3 (Bounded noise). The oracle 9 satisfies
(()l((z) / S =
Assumption 4 (Sub-Gaussian noise). The oracle G satisfies
E [[exp([(((x) V [z)) /o)] s exp(1).
Notes on our assumptions. In Assumption 1, the existence of a minimum is required for a technical step our main high-probability argument (Lemma 8). The bound R allows us analyze AdaGrad- like algorithms without explicitly constraining the objective's domain, thereby letting us use fundamental lemma on (1 -mmooothesssss (Lemma 1). Assumption is a standard light-tail noise enabling high-probabilite bounds [44, 43, 37]. We conduct most of our analysis under a stronger bounded noise assumption (Assumption 3) and then use reduction [1] to lift our result to hold under the weaker Assumption 4. It is sometimes possible to prove high probability bounds under even more relaxed moment-bout bound assumptions [6, 9, 10, 26, 27, 31]; doing so our setting an interesting topic for future work.
Algorithms.
Our proposed methods are applications of Algorithm 1, which has three parameters:
1. Clipping rule oz in most settings, oz min 1, Tefl] for some stochastic gradient of and threshold c.
"Unclipped" step size ne the product of т) and a, constitutes the SGD step size.
3. Threshold c: say that clipping occurs whenever lIsf > We intentionally define this separately from ar to allow applications of the algorithm to set o₁ = 1.
A key aspect of Algorithm is that it uses "double sampling." querying the oracle twice in each iteration. The two queries are on the same point but are independent from each other. One sample is used to compute the "unclipped" step size πe and the clipping rule 04, and the other sample determines the direction of the gradient step. This enables analyzing E [ by conditioning on the clipping result without incurring a bias St. We remark that this method is also used Yang et al. [41], who analyze normalized SGD for non-convex functions.
'The twice- differentiability assumption can be relaxed by using smoothness definition such as in Koloskova al. [15]. for which the smoothness lemmas rely on still apply.

---

Algorithm 1: Clipped SGD With Double Sampling
Input: Initialization Tg E Rd gradient oracle 9 and bound R on || x²
Parameters: Clipping rule a₁, "unclipped" step size 7) and threshold c. Ti T2 6
for 0.1,2....
si + G(xx))
compute ag and dp using of
c S | then Ti = Ti U {t) else T2 T2 U {t)
+ (
1++1 Proj (Et T((gg))))
projection only required for variants of Adaptive SGD
if [22 * 9 then I [72 ELET, It else 3i
return œ
Another non-standard aspect of Algorithm is the way it chooses which iterates to average for the final result. The algorithm tracks the sets Ti and T2, which correspond to iterations where clipping occurs/does not occur, respectively. These sets considered when deciding the return value: if To * 9 then we return Σ [Ta] ΣXeT. Tt, and otherwise we return the initial point z Zg: our proof' show that [T2] 2 I with high probability.
Table 1: Definition of our methods as applications of Algorithm 1. Under Assumption (bounded
noise) we set o' == a. Under Assumption 4 (light tails) we set set = 3 log )))o
step size T)
clipping rule az
threshold c
standard
I6 min
min
+, max 10Lo,
o
vI Ho
IIL.' Lot -
To
implicit
D'vT" 1/ LLo + |198 L1 +
-1
1
t, max 10Lo,
YI Ro
0')
Ro
conservative
Is min
min
Ao 64v log (z)
max vT
II 10LO;
I1b
Lot
Ro
adaptive
R E' af 11911112)
min
max 10LO, o b
Tocell
adaptive
R a3
min 1, Tof
15 log, (3)
R /T
max 10L0. II
conservative
Table 1 presents our different methods, that is, the different applications of Algorithm 1. We provide short description each method:
1. "Standard clipping" is an extension of the common clipping stepsizes from the deterministic (Lo, In -smoohhh setting [44, 43, 38). Indeed, for 0, when ignoring constants, have
M, min { t. -
2. "Implicit clipping" is the method that prior work refers to as a "normalized step size" or "smoothed clipping" [44, 11]. this method, a, and 77 a function of of.
3. "Conservative clipping" is method that is independent of L1. This method stems from the proof of Theorem 1, which requires T' Z log_ (2) (64L, thereby limiting L1. We use this to modify standard clipping by replacing L1 with its limit.
4. "Adaptive clipping" is a version of adaptive SGD with two changes: clipping is applied according a, and the gradient norms in the denominator are also clipped using a1, a1....,t at,
5. "Adaptive conservative clipping" is similar method that is independent of L1-
5

---

3.1 Clipped SGD
Theorem 1. Let f Rd - R. and suppose Assumptions 1, 2 and 4 hold. Let 8 (0, 1/,1 and let be the output of Algorithm I when run for T 2 log, ( (64L, Ro)2 steps under of the first 3 rows of Table 1. Then with probability at least 26, the optimality gap f() f(x") is
of log, (0) (LoR) + (oo(())
T
We remark that Theorem 1 also holds when R = 0o. That is, the projection is not required for the first 3 methods from Table
Proof sketch. In the sketch, we first prove the desired rate under Assumption and with probability least - 5. To obtain the desired rate under Assumption 4 with probability at least 1 26, apply a reduction from Attia and Koren [1], which we elaborate on at the end of the sketch.
We begin by presenting the main outline of the proof, in which state two claims that will be proven immediately following the outline. To maintain conciseness, we defer the full details to Appendices and D. We start with the first claim.
Claim 1. With probability least 1- 6,
Σ
ma,Ai S 2log, (g) Rg)
L=
Separating the clipped and unclipped iterations, we get
Σ
na.A, S log
Rg Σ mar,
LET
LET
We now observe that clipped iterations make large progress, stated in the following claim. Claim 2. Ift Ti then A, 2 4og (
Therefore, with probability at least 5,
Tr T
Σ
n. < 2 log R3) 4log (l0g+()))) R3)
TE
This implies [Ti < and therefore T2 2' In particular, this shows that the output of the algorithm is = [7a1 Eier, Zt-
2
In unclipped iterations we have | < c. The norm [ appears only in the denominator of
Me we can bound O4, from below by substituting [IgEll with Thus, show that 1),0,, 2
16
1 11 +
o/T Ro
=
(see details Lemma 7). By this we have
Σ S Σ
M, s 2og RZ)
TE
TET
Dividing by 7/ and using the bound on (22), we have
64
11
+ ovT Ru
log ( R2
1
Σ
A
T
T
TET.
Using Jensen's 's inequality completes the proof.

---

Proof sketch of Claim 2 (full proof is in Lemmas 6 and 7). Consider iterations where t E Ti, that is, iterations where ll || > c: By our choice of threshold we have 2 60. Therefore, for the sample to be above the threshold, the gradient norm must dominate over the noise, implying l|aEll ~ ([))() A known property of (Lo, -smoohh functions is that for any I E IR
[V]())] = 2 + IV - f(x))).
Substituting x = Zy,, using our choice of az and T/. and substituting |I9f|| [ we get | S 2 + [ S (21paxe) D.
Multiplying by 2( we get
n, 2 2(1.ollo8
Clipping implies
merelloll R mhe 2 2 log (7)
(1)
(#i)
Ro /T
where (i) is an equality in the case a min 1, 10 and (ii) is due to the choice of and c.
R
Combining the last two inequalities, we get the bound m,, 8 llgg
Proof sketch of Claim 1 (full proof is in Lemma 8). We split the signal from the noise by expressing
sum - T, V (xx), 3t x²) as
naa (gt, Te x²)
Tha ( (Vf(z)) 9b, x*).
To bound S2, we use techniques from Attia and Koren [1]. The random variables Tд and ge are independent conditionally on due to the double sampling, and therefore the elements of S2 form martingale difference sequence w.r.t. & (z+.gf). This allows to bound S₂ using a martingale concentration bound and standard analysis. We get that with probability at least - 8,
)
S <
log
R
Σ ビ=
16
To bound S1, we use standard analysis and show that
R
T-1
S S
+ Σ 2
By the convexity of and the above displays we find that, with probability least 1 5,
T-1
Σ
M
mai V V
21-10 x*)
T-1
SS + S2 S 2
log (F) Rg +
v a 11 Σ t=-
To bound n 1 we consider the cases of high noise and low noise: when |Iael| 2 6σ, like in clipped iterations, we have llgell [v:f( and therefore af < ma when
l|g:1l S 6a, we use n,a; S BoyT and get n S
R
Plugging everything and rearranging, we have that with probability at least
T-1
n. S 221og (2) R3)
7

---

Obtaining the result for light-tailed noise. Let G be an unbiased gradient oracle with o-sub- Gaussian noise. Attia and Koren [1, Appendix A] show that there exists an unbiased gradient oracle I with 3/ log o--bounded noise that, with probability at least 8, has the exact same output as G throughout the entire algorithm. Therefore, with probability at least - 6, we have the same guarantee as when assuming 3/ ( o-bounded noise. By using a union bound, we get that the desired guarantee holds under
//
noise with probability at least 26.
3.2 Clipped Adaptive SGD
Theorem 2. Assume the setting of Theorem under one of the last 2 rows of Table 1. Then with probability at least - 26, the optimality gap f(Ø) f(xx'(=)x))))))))r)))) ) is
( log+ (t) (ooft +v (lott++ (log(F)oRVT
T
The proof shares the main ideas of the proof of Theorem 1. The main difference is that analyses of AdaGrad-like stepsizes handle the stepsize in very specific manner. In our case, it show that
at ar x²) S 2R
Σ a2
Therefore, for the rest of the proof, we analyze Et=o a,d instead of Σtso n,,
4 Experiments
Our work introduces several non-standard algorithmic choices that facilitate our theoretical analysis. We conduct experiments order assess the empirical effect of those choices. Specifically, we aim to shed some light on the following questions:
Does gradient clipping help in stochastic, convex, (Lo, L1) -mooth optimization?
2. Is doublc-sampling better than single sampling?
3. Does the average of iterates from To perform better than the average of all iterates?
How does "adaptive clipping" compare to "standard clipping"? How does it compare to adaptive SGD with no clipping?
We perform linear regression on the California Housing dataset [28] and the Parkinsons Telemon- itoring dataset [36] (the latter is in Appendix H) using the loss function fw) = || w yll For algorithms with a fixed stepsize, we set 7) to a variable which we tune. For algorithms with a time-dependent stepsize, we express π function of the clipping threshold and multiply the result by a factor of Ir which we tune. For each tested method, we tune both Ir and (when applicable) using two-level, two-dimensional grid search. We defer to Appendix H for additional details the definitions of 77, and the tuning process. We also perform similar synthetic experiments on a function of the form (ww |w (Appendix H). The code for reproducing the experiments is available hewpiiippdd-gg--dd----eeeeeeeeee
Comparison of clipping methods. Figure Ia compares the output of Algorithm I for the methods of standard, implicit and adaptive clipping (rows 1, 2 and 4 in Table 1). The three methods show similar dynamics and converge to nearly identical optimality gap.
Figures 1b and Ic compare SGD, adaptive SGD, Algorithm with standard clipping (clipped SGD) and Algorithm with adaptive clipping (clipped adaptive SGD), For SGD and adaptive SGD, we plot the sub-optimality of the average all iterates, set de = and set fı as their clipped counterparts. The figure shows overall similar performance. In SGD the clipped method performs bit worse. In Adaptive SGD the difference between clipping and no clipping is more substantial, in favor of clipping.

---

stenderd <loping
disped SGD SG0
diopes vedico tive
Imsleit clisping
adapotre dioppnn
18
19.
(b)
Figure 1: Sub-optimaligg of SGD variants as function of the number of stochastic gradients used, when training a quartic-loss linear regression model on the California Housing dataset. We plot the median across 10 runs, with a shaded region showing the inter-quartile range.
dleped 5G3 (dounle) dloppo S2D (singl))
cliped SCD (double) clppedd SGD (áinte)
disped 5GD, avg dioped 500,
#f Aandors
# slaishake gratarss
(b)
Figure 2: Ablations of Algorithm 1. Figures 2a and 2b compares single and double sampling by plotting sub-optimality as a function of gradient and iteration budget, respectively. Figure 2c compares different averaging methods. We plot the median across 10 runs and shade the inter-quartile range.
Comparison of theory with empirical results. We test the effect of our souble-sampling approach, it originated from analytical considerations and not from practice. Figure 2a plots the sub- optimality of standard clipping in two versions: one as presented in the paper, and another that uses single sample in each iteration. Note that the x-axis is the number of stochastic gradients, so the latter version ran for twice as many iterations. There seem to be no advantage to double-sampling, suggesting it might not be necessary in order prove convergence in the stochastic convex regime. Figure 2b plots comparison in terms of iteration complexity, where single sampling still achieves better sub-optimality.
We move on to investigate our algorithmic choice of defining the output as ã Figure 2c compares the sub-optimality of ē to the sub-optimality of the average across all iterates (both are with standard clipping). We see that achieves slightly better sub-optimality, supporting our choice.
[Tal ELeTs Ti.
1
5 Conclusion
In this paper, we analyze stochastic gradient descent with gradient clipping on convex, (Lo, L1)- smooth functions. We prove high-probability convergence rate for clipped SGD, and introduce clipped variation of adaptive SGD that has a similar rate.
There are various possible directions for future work. First, since the double-sampling approach is not supported by empirical data, it interesting to study convergence without it. Another direction is extending our analysis to more generalized smoothness assumption such as Ê-smoothness [18]. Lastly, exploring tuning-free methods that require no knowledge on problem parameters could of both theoretical and practical interest.

---

Acknowledgments
This research was partially supported by the Israeli Science Foundation (ISF) grant no. 2486/21 and the Adelis Foundation. It was also partially supported by Israel PBC-VATAT, by the Technion Artificial Intelligence Hub AT), and by the Israel Science Foundation (grant No. 3109/24).
References
[1] A. Attia and T. Koren. SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance. In International Conference on Machine Learning (ICML). 2023.
[2] X. Bi, D. Chen, G. Chen, S. Chen, D. Dai, C. Deng, H. Ding, K. Dong, Q. Du, and Z. Fu. DeepSeek LLM: Scaling Open-Source Language Models with Longtermism. arXiv:2401.000 0229444 2024.
[3] Brown, B. Mann, Ryder, M. Subbiah, J. D. Kaplan, Dhariwal, A. Neelakantan, Shyam, G. Sastry, and A. e. a. Askell. Language Models are Few-Shot Learners. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[4] 7. Chen, Y. Zhou, Liang, and 7., Lu. Generalized-Smoon Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization. In International Conference Machine Learning (ICML), 2023.
[5] A. Chowdhery, S. Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, Barham, H. W. Chung, C. Sutton, and S. Gehrmann. PaLM: Scaling Language Modeling with Pathways. Journal of Machine Learning Research, 24(240):1-113, 2023.
[6] D. Davis, D. Drusvyatskiy, L. Xiao, and J. Zhang. From low probability to high confidence in stochastic convex optimization. Journal of Machine Learning Research, 22(49):1-38 2021.
[7] J. Duchi, E. Hazan, and Y. Singer. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 12(7), 2011.
[8] M. Faw, L. Rout, C. Caramanis, and S. Shakkottai. Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD. In Conference Learning Theory (COLT), 2023.
[9] E. Gorbumov, M. Danilova, and A. Gasnikov. Stochastic optimization with heavy- noise via accelerated gradient clipping. In Advances in Neural Information Processing Systems (NeurlPS), 2020.
[10] E. Gorbunov, M. Danilova, I. Shibaev, P. Dvurechensky, and A. Gasnikov. High proba- bility complexity bounds for non-smooth stochastic optimization with heavy-tailed noise. 11X55:2106.05958, 2021.
[11] E. Gorbunov, N. Tupitsa, Choudhury, A. Aliev, P. Richtárik, Horváth, and M. Takáč. Methods for Convex (Lo, Li)-Smooth Optimization: Clipping, Acceleration, and Adaptivity. arXiv:2409. 14989, 2024.
[12] Y. Hong and J. Lin. On Convergence of Adam for Stochastic Optimization under Relaxed Assumptions. arXiv:2402.03982, 2024.
[13] Y. Hong and J. Lin. Revisiting Convergence of AdaGrad with Relaxed Assumptions. arXiv:2402. 13794, 2024.
[14] B. Kleinberg, Y. Li, and Y. Yuan. An Alternative View: In International Conference on Machine Learning (ICML), 2018.
When Does SGD Escape Local Minima?
[15] A. Koloskova, H. Hendrikx, and S. U. Stich. Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees. International Conference on Machine Learning (ICML), 2023.
[16] G. Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 2012.
10

---

[17] H. Li, A. Rakhlin, and A. Jadbabaie. Convergence of Adam Under Relaxed Assumptions. In Advances Neural Information Processing Systems (NeurIPS). 2023.
[18] H. Li, Qian, Y. Tian, A. Rakhlin, and A. Jadbabaie. Convex and Non-convex Optimization Under Generalized Smoothness. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
[19] X. Li and F. Orabona. A High Probability Analysis of Adaptive SGD with Momentum. WYXV:2007714224. 2020.
[20] A. Liu, B. Feng, B. Wang, B. Wang, B. Liu, C. Zhao, C. Dengr, C. Ruan, D. Dai, and D. Guo. DeepSeek- V2: Strong, Economical, and Efficient Mixture-of-Experts Language Model. arXiv:2405.00 04434, 2024.
[21] A. Liu, B. Feng, B. Xue, B. Wang, B. Wu, C. Lu, C. Zhao, C. Deng, C. Zhang, and C. Ruan. DeepSeek-V V3 Technical Report. arXiv:2412.19437, 2024.
[22] C. Liu, D. Drusvyatskiy, M. Belkin, D. Davis, and Y. Ma. Aiming Towards the Minimizers: Fast Convergence of SGD for Overparametrized Problems. In Advances Neural Information Processing Systems (NeurIPS), 2023.
[23] A. Lobanov and A. Gasnikov. Power of (lo, ( Smooothessss in Stochastic Convex Optimization: First- and Zero-Order Algorithms, 2025.
[24] A. Lobanov, Gasnikov, E. Gorbunov, and M. Takác. Linear Convergence Rate in Con- vex Setup is Possible! Gradient Descent Method Variants under (L_0, Lmmoohhhmmsssssss arXiv:2412.170500 2024.
[25] H. B. McMahan. A survey of algorithms and analysis for adaptive online learning. Journal of Machine Learning Research (JMLR), 2017.
[26] A. V. Nazin, A. Nemirovsky, A. B. Tsybakov, and A. B. Juditsky. Algorithms of robust stochastic optimization based mirror descent method. Automation and Remote Control, 80: 1607-1627, 2019.
[27] T. D. Nguyen, A. Ene, and H. L.. Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tails. arXiv:2304.01119, 2023.
[28] R. K. Pace and R. Barry. Sparse Spatial Autoregressions. Statistics & Probability Letters, 33 (3):291-297, 1997.
[29] B. T. Polyak. Some Methods of Speeding up the Convergence of Iteration Methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
[30] A. Reisizadeh, H. Li, Das, and A. Jadbabaie. Variance-reduced Clipping for Non-convex Optimization. arXiv:23033 arXin::303..0088; 2023.
[31] A. Sadiev, M. Danilova, E. Gorbunov, S. Horváth, G. Gidel, P. Dvurechensky, A. Gasnikov. and P. Richtárik. brohhbprbbbbility bounds for stochastic optimization and variational inequalities: the case of unbounded variance. In International Conference on Machine Learning (ICML), 2023.
[32] Schaipp, A. Hägele, A. Taylor, U. Simsekli, and F. Bach. The Surprising Agreement Between Convex Optimization Theory and Learning- Rate Scheduling for Large Model Training. arXiv:2501.18965 2025.
[33] Y. Takezawa, Bao, R. Sato, K. Niwa, and M. Yamada. Parameter-free Clipped Gradient Descent Meets Polyak. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
[34] H. Touvron, T. Lavril, G. Izacard, X. Martinet, M.-A. Lachaux, T. Lacroix, B. Rozière, N. Goyal, E. Hambro, and e. a. Azhar. LLaMA: Open and Efficient Foundation Language Models. 2023. 2023.
17X1v.2302.13971,

---

[35] H. Touvron, L. Martin, K. Stone, P. Albert, A. Almahairi, Y. Babaei, N. Bashlykov, S. Batra, Bhargava, and S. e. a. Bhosale. LLaMA Open Foundation and Fine- Chat Models. arXiv:3307009888, 2023.
[36] A. Tsanas, M. Little, P. McSharry, and L. Ramig. Accurate Telemonitoring of Parkinson's Disease Progression by Non-invasive Speech Tests. Nature Precedings, pages 1-1, 2009.
[37] A. Tyurin. Toward a Unified Theory of Gradient Descent under Generalized Smoothness. arXiv:2412.11773 2024.
[38] D. Vankov, Rodomanov, A. Nedich, L. Sankar, and S. U. Stich. Optimizing (Lo, -mmoth Functions by Gradient Methods, arXiv:2410. 2024.
[39] B. Wang, H. Zhang, Z. Ma, and W. Chen. Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions. In The Thirty Sixth Annual Conference on Learning Theory, 2023.
[40] B. Wang, H. Zhang, Q. Meng, R. Sun, Z.-M. Ma, and W. Chen. On the Convergence of Adam under Non-uniform Smoothness: Separability from SGDM and Beyond. 1511: 2024.
[41] Y. Yang, E. Tripp. Sun, S. Zou, and Y. Zhou. Independennty-Normaliiee SGD for Generalized- Smooth Nonconvex Optimization. urXiv:2410.14005: 2024.
[42] D. Yu, W. Jiang, Y. Wan, and L. Zhang. Mirror Descent Under Generalized Smoothness. arXiv:2502.00753, 2025.
[43] B. Zhang, J. Jin, C. Fang, and Wang. Improved Analysis of Clipping Algorithms for Non-convex Optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[44] J. Zhang. Т. Hc, S. Sra, and A. Jadbabaie. Why Gradient Clipping Accelerates Training: A The- oretical Justification for Adaptivity. In International Conference Learning Representations (ICLR), 2019.
[45] S.-Y. Zhao, Y.-P. Xie, and W.-. Li. On the convergence and improvement of stochastic normalized gradient descent, Science China Information Sciences, 64:1-13, 2021.
[46] Y. Zhou, Yang, H. Zhang, Y. Liang, and V. Tarokh. SGD Converges to Global Minimum in Deep Learning via Star-convex Path. In International Conference on Learning Representations (ICLR), 2019.
12

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The claims and contributions are stated in the abstract and are detailed in introduction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss limitations of our assumptions Section and the relation between theory and empirical observations in Section 4.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-texx system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification:
Our paper details all our assumption and provides detailed proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide the code necessary for reproducing our experiments, and provide details on data preparation and parameter tuning in Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
14

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide the code, which automatically downloads the data and runs the experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
Serriides/CodeSummiisse
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / ctttpp..cc/ubbicee gww.//////////eee/// CooeeSubmis ssi aesionPolicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Details the data and parameter tuning is in Appendix H. There is test since measuring generalization is irrelevant in this paper.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: The plots accompanied by intervals outlining the 25 and 75 percentile.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The requirements are listed in Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:///eeipppeeeeeeeeee httppubicc/ttiicauaaieiieeiaeiee
Answer: [Yes]
Justification: The paper follows the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
There ar eno societal impacts of the work in this paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The algorithms and code we provide pose no risk of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The relevant information is in Appendix H.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com con/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The code is the only asset provide, and it documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs were used only for writing. editing or formatting purposes.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https /ttpss:///ee.p..eeeeee /ttp:////e//oeeeeeeee////////// for what should or should not be described.
19

---

A Lemmas for (Lo, Lim-Smooth Functions
Lemma 1. Let f Rd R and suppose Assumption 2 holds. Then for any R
[V]()]] - 2(L + -
Koloskova et [15, Lemma A.2] prove this by simply using Zhang al. [43, Lemma A.3], which
assumes the (Lu, Lm)-sooohsnssss definition we use.
Lemma 2. Let f Rd + R and suppose Assumption 2 holds. Then for any E R4,
Lo
[V(x))] & max (LI(f(x)- - f(x)))
Proof. Denote = f(x) - f(x=). Lemma shows that
|V/(2)] -1ne--//A/////))) - 2 < 0.
This is quadratic inequality in [[]](= Since Lu, L1, A and [[v(())] are non-negative, the solution is less than the parabola's 's largest root. Therefore,
221 + AL772 )LOA) = LIA+ 17A2 + 24 2L, + 2L
[>))( -
2 2 2 then get
[V/(')
V 13 A 3L,
If 13 2LoA: Without loss of generality, we assume A 0 (since for A 0 the result is immediate from Lemma 1), and therefore A 2L LLo/L, L7 Consequently,
[f(()] s 22/21
2L 3 2 s 3v 4LL/ 6La/L1.
Overall, we have
[V S max 3L1 A, 6 L0
B Lemmas on Probability
To achieve high probability bounds, we use the following concentration inequality, which is corollary of Li and Orabona [19, Lemma 1].
Lemma 3. Assume that Z1, L2, ZT is martingale difference sequence with respect to E1, Er, ET (i.e., E. Ei,..., [t-1] = 0) and that [Z,] S a, for all 1 S t S T, where ae a sequence of random variables such that a measurable with respect E1, , Then, for any fixed À > 0 and E (0, 1). with probability at least 1 - 8, we have
Σ t=1
Z
3
1
1=1
To handle the light tails assumption, we use reduction from sub-Gaussian noise to bounded noise presented by Attia and Koren [1, Appendix A]. The reduction can be formally stated follows.
Lemma 4. Let G be an unbiased oracle satisfying Assumption 4. Then for any Zo. .o..... FT-1 and any 5 E (0, 1), there exists unbiased oracle 9 such that
(i) ğ satisfies Assumption 3 for 5 = 30 / log(
(ii) With probability at least for all O,.... T it holds that ((xx) = G(zz).
20

---

C Lemmas for proving Theorem
Lemma 5. The value of a4 is always smaller under "standard clipping" than under "implicit clipping." " Additionally, 2 log+ (7 (641, Ro)² $ T. then it always smaller under "conservative
clipping" than under "standard clipping."
Proof. First, let us compare conservative clipping and standard clipping: The definition of π is equivalent in both methods. Due to the assumption on T, the threshold smaller in conservative clipping than in standard clipping. This immediately leads to the stated relationship regarding 0z.
Now let us compare standard clipping and implicit clipping: For the rest of the proof, let The Or and be defined as in standard clipping. Observe that
1
1
n min
1ILO
oVT Lo + no
Lo + max 10T,,
TVT Ro
Lo chi
and
1
1
Ro T
1h min
min
min
T/t
11 Lo +
ovT
11
Lo +
gyT
gvT Ro
Rd
Ro
Together we get
Ro
T/ min
Lo + chi ovT
Consider the case of unclipped iterations, which satisfy ar
and <> || In this case,
Ro
Ro
a = 1/ 16 min
min
Lo + cL1 ovT)
16
Lo + |lgil| oVT
Now consider the case of clipped iterations, which satisfy a للाl and S l| In this case.
Ro
7h4
16 at min
Lo + cLL ovTT
Ro
04 min
16
(c/ll9f/)) cch "oTT
Ry
min
16
(c/ll9Ell) Lo 11 L1
ovTT)
1
1
Ro
min
16
(c/ ([l Too 11
T1
ovT)
1
Ro
min
16
Lo + 1198| [T "oVT)
Therefore, both cases satisfy
1
1
m,0r 16
min
Lo +
evT No
16 max Lu + (99 L1,
avT
Rg
TvT 16 Lo |198|141
Lo + |1 + ovT
Ho
Lemma Let f R2d + R and suppose Assumptions to 3 hold. Additionally, assume that
m, I }1 LL + 1196 [1 +
o/T and bo < |l Then for any g(x.),
Ro
n < n,
21

---

Proof. By our assumptions, we have 60 - 1l This implies o - as otherwise
|I ll vf(2)]]
+ [[[ a 50 60.
Therefore, every oracle query satisfies
(V)(=)) 9(x))1
By the triangle inequalities, we obtain
(4/5)IVV((<.II [[(x)))] (()))
(1)
Therefore,
(na)) 2 (n.a))=288660 11af |1
TVT
8(Lo (99
(2)
M 8(L (=))) (445)((o++
+V
By applying the smoothness property stated in Lemma 1, we obtain
|9((1x))11
8(4/5) T,at
To + [[
(6/5)
[V((2)]]] s mor...
8(4/5)
naat
Lo + [
Lemma 7. Assume that the expression 14 is between its value under "conservative clipping" and its value under "implicit clipping". Additionally, assume that the threshold is no less than its value under "conservative clipping". Then
1 [1Lo + ovT (i) |ل implies naa 2 16
(ii) c c |I implies n N 8 8log
(T') Ro T
Proof.
Consider iterations where ||9||] I|- In this case, under the choice of 1) and a2 in "conserva- tive clipping", we have
1
04 = 1)t 16 min
2
11L0'
Lo
ovT
16 11 +
TVT Rg
Ro
Due to Lemma 5, this lower bound applies any choice of vi and o, that matches our setting.
Consider iterations where c < | In this case we have o & V otherwise,
ا ol V f fzx))l + [[v)()))) < + 50 60 S S |IgE|l|
where the last two inequalities are by our assumptions on c. Therefore Lemma applies, and therefore
1
2 S,
o 2 2
2
(1)
min
min
16
11 Lo +
evT
|995
1io
2
(182)
1
1
min
16
11Lo Lo +
ovT
Ro
max 10L., Ro })²
oVT 2
(io)
1
64 Aogglog+000 (?) Ro
16 min
11 Lo
ovT
VT
Ro
where (1) uses Lemma 6, (ii) uses the assumption on 1):04, (iii) uses S || and (iv) uses the value of c under "conservative clipping".
22

---

From this point we are done with our assumptions and only use pure algebra:
2
1
ovT
2
min
64 log
())
max
10Lo:
16
11
avT Lo
+
Ro
Ro
R
oVT
})
2
16 logg
8
T
min
11L0 Lo + ovT
max
10L
Ro
Ro
(10Lo +
avT Ro
Rn
10L
16 16logg10 (3)
min
T
11
Lo ovT
no
RD
10 1
11
2 16 16 (3)
min
T
11'2]
R2
=4log_ (z)
T
Lemma 8. Let f IRd + TR. and suppose Assumptions 1 to 3 hold. Assume Algorithm I is run with
parameters satissyyng 0tt Lo + | [ at least - 5,
+
TVT Then for any ö (0, 1), with probability
No
T
ma
S 2lgg (Z)
t=
Proof. We remark that the first section of the proof follows techniques used in Attia and Koren [1, Lemma 2].
Define Ze := mrac (VF gr, Tt x²). Recall from Algorithm that ne and a are deterministic
given gf. Then the sequence Zo ... ZT-1 is martingale difference sequence with respect to E-- = (f):
Z Ne: Dol mi ( (V)(x)) Elg. st, gi,, xe - x²)
Define Rmaxxt
max {Ra). Each Ze satisfies US$5t
((VTT)
1
-1 Romux,t
Ro Rmxxxt 8VT
Z Vf(x)) - gell|lae x11 S maruo Rs
8
Ro
Therefore, by Lemma 3, for any E [T], 0 and 5 E (0, 1), with probability at least 1 holds that
T
Σ
1-1
n. (Vf((V - Is. - -x)) S
R2 R2
max.
log
64T
1
T
< 64
XR 2
max,t-1
X
log
5
By applying union bound and choosing À 4R get that with probability at least - 8,
Vt = I,.... T
Σ
1 na / (x(x))) - -9. xo - -x¹) <
16 R2
max.t-1 +
-log
RB.
(3)
log F) R + ET- naa I We show by induction on é that, when (3) holds, R I C for all 0 < T. For t = O we have Ra = R < C. Let us assume correctness for 0, O - 1. This implies R22 R I C, so to prove the induction step, it suffices to
Define C = 2(
23

---

show
R S C. By unfolding the definitions of Ro..... Re and using common projection algebra, we
have
t-1
R S RO -2 2
>
a 0g -x")+ +
a 2 1
==0
(
2 R2 2
Σ
7 10: - -x") +
a |1 112 + 2 Σ n,a (VS(a,),, 2, -x"
==0
==0
[-1
Ri + Σ
n, V (xx))
92, - x²) + Σ
11 1/
0
1+ 1
T
1-1
R2
max,t +
log
Rg
+
Σ
1 a 2
|9 2
2
8
$=0
1
C
R
Rmmxxtt- 1-
8
CC
where (1) holds since, by convexity and the optimality of a*,
S (f(xx) - f(x,)) - -a -V)=((((t),
- =x,)=
By applying the bound on Re to Equation (3) we obtain that
T 1
(
Ma (Z)( 9t, x*) - 8
1
+
log
+
1/ 0 l1ge 112
2 2
+ 4
log
R2
2
t=
1
5
T
+
log
n of |1
2
16
Moving on, a standard analysis shows that
T-1
R2
T-1
Σ
nar x x²) S
Σ
n a |1
2
By summing the two inequalities and using convexity, we get
T-1
T-1
A
S
mha
(Vf(z)) 20 - -xx)
1=0
1=0
3 T-1
5
+
5
log
RS
+
Σ
a 12
8
16
0
4 t=0
3 T-1
< log Rg) +
Σ
1/2 a 12
2 2
4 t=0
When 2 ((z)) we have
|1a.l| < 119e
V < 50 = 60
and therefore
22 < (60m:or)
<
66
(oVT
-1
R2
8
Ry
T
When a < (l)5) ||. Lemma 6 shows that
1 n/ af - ma.
2
24

---

Using these two inequalities, we get
1 na A S log-(2) R))
3 T-1
maaa + Rg
4
T-1
- log
Rg
+
7, + RD
2
1=0
T-1
1
$ log+
(f) +
Σ
ma,Se.
2
t=0
By rearranging the terms and multiplying by 2, we get
T-1 Σ
n,, S 210 (2) Rg.
t=
D Proof of Theorem 1
Theorem 1. Let f: R.d -> TR and suppose Assumptions 1, and 4 hold. Let 8 E (0, 1/2) and let be the output of Algorithm I when run for T z log rows of Table 1. Then with probability at least 25, the optimality gap f(3) {x*) is
steps under one of the first
LoRg log (2) (LoRg + (o
T
Proof. We begin with comment about the light tail assumption, and then continue with the proof.
Light-tailed noise vs. bounded noise. The rest of the proof is written under a modified setting: uses Assumption (bounded noise) instead of Assumption 4 (light-tailed noise), and it adjusts тh and c by replacing instances 3/ /og { o with a. The proof obtains bound that holds with probability at least 6. By Lemma 4, with probability at least - ó, using an oracle that satisfies Assumption results in the same output as using an oracle that satisfies Assumption 3 with o' = 3 logg( f o. By using union bound, we get that the desired bound holds under Assumption 4 with probability least 1 - 26.
Proof under Assumption By Lemma 8 we have
T-1
Σ n, S
Σ
marAi S 2log (T) R2.
BE
1=
The criteria for belonging Ti, together with Lemma 7, show that this implies
R2 T
8 log
(5)
T
S 2 2og Rg)
From this, it follows that |Ti < _. and therefore T2 2
T 2
Similarly, by Lemma 8 we have
T-1
Σ 1E
M, <
Σ
na S 2log (7)
25

---

The criteria for belonging to T2, together with Lemma 7, show that this implies
OVT Ro
11Lm
Σ rE
A S log (3)
16
From this, it follows that
1
32 log
(7)
11L0
+
TVT
Ro
64 log (T) 11 oRoVT
To
[72
T
1E72
where the last inequality uses the lower limit on (T2)- From the definition of Dc, and by Jensen's inequality, we obtain
64 log (7) R1 + o RoVVT)
Tt - [(x)) 5
To
T
LET
Recall from Algorithm that [T2l 2 T 2
implies ã = [Tal EIET, 24. Therefore the proof is complete.
E
Lemmas for proving Theorem 2
Lemma 9. Let f : Rd + and suppose Assumptions to 3 hold. Assume Algorithm I run with
step size 1/- VEi-o afllo:
R and clipping rule On min 1. To
Then for any threshold c,
T oi (gt, - x²) S 2R
a
11.
Proof. Since 1/n, is non-decreasing in t, a standard analysis shows that "
T-1
a4
(gc Dt x²)=
T
R
R
1
T-1
Σ
na 11
217
2
R3
T-1
1
1
T-1
R2
|1
21jo
1/t-1
2
t=
R
R²
T-1
11gel1
12
21j0
2
T/t
2
t=0
R²
a
2
|9 12
2TT-11
2
1=0
Define S, = Ei a?!1g:112 and S_1 = 0. Observe that 1/t
R
Then we have
JS.
T-1
R
S
S
2 a 1| 12
Σ
ns S(-1)
V5,
R T-1
VS, V S
VSi - -VS
2 i=
/Sr
R T-1
Σ
2(
(VS, VSS..)) = RR S1-1-
i=0
26

---

Therefore,
ai Ie S 2R
a 11
Lemma 10. Let : - R and suppose Assumptions to 3 hold. Additionally, assume 60 S c and |l Then for any g ((xe). a 19 - 4(Lo cL1)a,
Proof. Our assumptions imply 60 Σ lg which in turn implies a S (1/5) Vf(+))]]: Vf())) otherwise,
|ل |19 v (v:) || [V/()) + 5o 60 < |1g
(x,))
Therefore, every oracle query to 24 satisfies
- [xx
((x) (o0
(4)
By the triangle inequalities, we obtain
(4/5)ll & |((+)))| (6/5)
(5)
Therefore,
(5) $ (0/5)9
0f 11 1|
(6)
(6/5) 2(Lo + +V[[(E)))LLL)
@ (6/5)²
ai 2(T |1g
(4/5)
(i) A S 4(Lo cLI)a,A..
S 4(a, +
where (i) uses Lemma 1 and (ii) uses the definition of
Lemma 11. Assume the setting of Lemma 10, and assume that the threshold c is no less than its value under "conservative + adaptive clipping". Additionally, assume that log,, (1) R)2 < T. Then
1 C
80 T
(15LOR + log (t)oRTT)
A
4
T
Proof. By Lemma 10 we have that Equation (5) applies. Therefore,
|sg 2 2
8Lo
[V[(())] 2
6/5
6/5
L
and together with Lemma 2 we get f
< A This leads to
1
A 2 c 41
a,A, l A 2
A 6/5
6/5
[x))))]
By our assumptions on c, we have
c > 15 log. (1)
R
L
VT
R
R
VT R
2 / log+ (t)
/ (t)
15
1og,
max
10Lo,
VT
VT
R²
VT
256 25, (2)
max 10Lo,
T
R
2 125 log (+) - (100 +oRR2ooRV +ORVT)
80
R R + log (H) T
where the last two incqualities purposefully loose for later convenience.
27

---

Lemma 12. Assume the setting of Lemmaa 9. Then for any E (0. 1), with probability at least 1 - 8.
T-1
Σ
+ CL + +9log+ (2) (H)
If we also assume the setting of Lemma 10, then
T-1 Σ a.. s 25 15 + log (2)oRT))
Proof. The proof first uses martingale concentration inequality and Lemma 9 to obtain high- probability bound, and then continues to bound the stochastic gradient norms.
Define Ze = ar ( (fx) the sequence Zo: .... Zr-1 a martingale difference sequence with respect to fi (Z).9))
Lt x²). Recall from Table I that or is deterministic given of. Then
E Z Fe = (V)()())))) Elge xe. 84 x²) = 0.
Each Zz satisfies
7 at (xx) ge 11ll|1= x011 S RooRe S aR. S aR.
Therefore, by applying Lemma with X' (LoRVT) -1 probability least 1- 6,
we have that for any (0. 1), with
T-1 1
T-1
Σ
as (V((x) - go. 2s - x²) -
X
R²R² + x log(?)
3 $ 2
1
+ x
log(t)
3
s RRVT + 4log oo)
16
Recall that Lemma 9 bounds Ets at 0e x²). By summing that bound with our inequality, and by applying the gradient inequality, we get
Σ E.
Σ a. (V((((z)) x²)
T
a RVT + 4 log Ro) +R,
16
On iterations where 2 (/ we have
1ل < 1 < (1lg: - V((a)l + [+)((=)) (a + 50) (6o)².
On iterations where < VL/5)IIV (It))l, we can repeat the arguments from Equations (4) to (6) (note that they do not require the additional assumptions present in Lemma 10), and thus obtain
af l < 4(Lo + cL))a,
The two cases imply that every iteration satisfies of 19.11 < 4(To + cl,),, + (6o)² Therefore,
T-1
3 RRT
T-1
Σ
A <
4log RRRT + 2R,
Σ
+ 4(Lo + + (6o)2)
16
0=
T-1 Σ a. + (6
3
o RvTT + 4 + 2R,
4(Lo + cli)
16
im0
The rest of the proof is pure algebra, which we show separately in the subsequent lemma (Leemaa 13).
D
28

---

Lemma 13. If
T-1
3 3 oRRTT+ + + + 4(L0 + cli)
T-1
Σ
a+ S
Σ
a, + (,
16
t=
i=0
then
Σ 1=0
a, S 25 15bolt + log (t)oRVT)
Proof. Denote = Ei=0 a, Then we have
3
A
oRv T + 4oog (f) 2RV 4(Lo + + (60)
16
3
<
V
0 RV R + (08TT+400(3))R1111
+ +2RV + + (
16
2 RVT)
cZ)) + +2RV +2(4))
$ V
16
Squaring both sides leads
2
A3 5
2
+2 (1) +2Ry + (6o)
3 RVT) +2 (4logg())
+ 4R2 (a((((((<oo)) +[1)A (6o)²T)
2
- 64
(RRVT)
+ 4 1og
( ( RV + 32R + cl, + 8-33R
32R2 (Lo + cL1)A + (289- + 64 (t) (ORVT)
This is a quadratic inequality (in A) of the form 2 < bd (b, e 2 0). In such cases, every solution is less than or equal to the largest root of A2 - bA - c. Therefore,
A 1 b + V2 46) b+ V /4e) <b+ Vc.
In our context, this leads to
T-1
Σ an S 32 + R2 + 288 + 64 (?) RRVT
32(Lo + cI1) + (17 (17+ 8log()) .RVT .RRVT
< 332(Lo + e22 + 9 log (H)RRVT
From the assumption on we have
VT 10Lo, R o L < 10 FORTT.
RL < max
Therefore,
T
Σ a, I 32 LoR² + 10L + -ORVT) + 9log,, (H)
< <352Lo1² - 25 log (f)
< 25 15 + log (1))
29

---

Proof of Theorem 2
Theorem 2. Assume the setting of Theorem under one of the last 2 rows of Table 1. Then with probability at least 1 - 26, the optimality gup [(z) f(x*) is
log+ (2) (ToRe
+ (118
o
T
Proof. We begin with comment about the light tail assumption, and then continue with the proof.
Light-tailed noise vs. bounded noise. The rest of the proof is written under modified setting: It uses Assumption (bounded noise) instead Assumption (light-tailed noise), and it adjusts and b replacing instances 3 /ogg( (T) with o. The proof obtains bound that holds with probability at least 1 1- 6. By Lemma 4, with probability at least - ó, using oracle that satisfies Assumption results in the same output using oracle that satisfies Assumption 3 with o' 3 log { 0. By using a union bound, we get that the desired bound holds under Assumption with probability at least 1 - 20.
Proof under Assumption 3. Consider iterations that satisfy E Ti, that is, iterations where S [ By Lemma 11 we have
80 T
[5LLRR +og (f)oRVT).
A,
Therefore, together with Lemma 12, we get that with probability least 1 5,
80 [15LoR2 + log, (2) (2)
T S Σ a.
T
IE T-1 $
a,
1=
$ 25
15L + log (H)
From this follows that [7| T. and therefore T2 2 Similarly, by Lemma 12 we have,
T-1 -
a, 25 + log, (t)oRTT)
RETa
t=0
Dividing by [Tl, using the bound we obtained on T2l and using Jensen's 's inequality, we get
1
)
25 R5 + log (1g+(1)) (+)RRTT)
Zt
-10(0))
A
T2
T2
[22
BET2
LET2
50 15L R2 + +lo (f))RVT)
T
Recall from Algorithm 1 that [T2] 2 implies E =: = [7al ELeT, Tz. Therefore the proof is complete.
30

---

G The potentially exponential dependence of [V]( and f(x) - f(x*) on L x=1l
Let Lo, L1 E R2 and let f(x) La cosh(L)x). We will show that f is (Lo, -smothhh The first and second derivatives
Lo Li
(((x)
sinh(L (x) Lo coshoooshhi
For any x E R, by basic properties of cosh and sinh, it holds that
[x)( Lo cos)(L Lo(e -12 sinh(L1a)) Loe Lis + (z))
L1æ I and ('(x) (x)). Therefore, When x 2 we have e --
|/"()) - L.g [, (x)))
When < O we have fa(=a) < 1 and (-x) = [z) Therefore,
|f" - Lo - [=))(
and since 1" an even function, the same holds for (x)(.)). In both cases we end up with the inequality that defines (Lo, L1) -smoothhssss..
Let us discuss, in the context of the above f. quantities that appear in bounds of related work. Let To E R. The minimizer of f is x* = 0. therefore |20 - x=1| = |0ol. The gradient norm at æ = zo satisfies
To L1
Lo
Lo
Vff(z))l
sinh(L
sinh(L1 xol) 2 (exp(Ly|<ol) -1)
L1
2L1
Lo
(exp(L1l1zg x²1)) 1).
2L
Additionally, the sub-optimality 36 satisfies
f(zo) - f(x)) = Lo
Lo
(cosh(L - (osh([I/xoo))
I
L
2 (xxp(L)(zoo)) - -2) = Lo
Lo
(exp(L1l1z0 - x²1)) 2).
2L
L3
Both quantities demonstrate an exponential dependence on L, 11|1000 x=1|-
H Experiments
We present additional implementation details, results of the experiments on second dataset, and results obtained with synthetic data (not modeled as regression task).
H.1 Implementation details of real-data experiments
Data and computational resources. Our experiments use the California Housing dataset [28] and the Parkinsons Telemonitoring dataset [36], which are published under "CCO" and "CC-BY 4.0" licenses, respectively. All experiments provided in this paper were run on Google Colab (with a free account) using NVIDIA T4 GPU.
Data preprocessing. The data preparation begins by obtaining the dataset (X, y). where E Raa represents samples with features per sample, and E IR" represents the targets. Missing data in numerical features replaced with the mean value, and missing data in categorical features is replaced with the most frequent value. Numeric features, as well as the targets, are standardized to have zero mean and unit variance, and categorical features are encoded as one-hot vectors. The samples are then shuffled. Finally, column I E Rax1 is prepended to X in order have bias term in the regression task.
31

---

stenderd <loping
disped SGD SG0
diopes Aveiciive
Imsleit clisping
Aga
adapotre dioppnn
Uhe
(b)
Figure 3: Sub-optimality of SGD variants as a function of the number of stochastic gradients used, when training a quartic loss linear regression model on the Parkinsons Telemonitoring dataset. We plot the median across 10 runs, with shaded region showing the inter-quartile range.
disped SGD Idouphel dleped SGD
clpped SGD (double) clpped SCD (single)
disped 5GD,
disped
67
of Wi-oorass" gasieerr
of Beendoss
(a)
(b)
Figure 4: Ablations of Algorithm 1. Figures 4a and 4b compares single and double sampling by plotting sub-optimality as a function of gradient and iteration budget, respectively. Figure 4c compares different averaging methods. We plot the median across 10 runs, with shaded region showing the inter-quartile range.
Stepsize and clipping threshold tuning. We determine the clipping threshold of each method by tuning it, avoiding reliance on theoretical quantities from the definitions in Table 1. Similarly, we modify the parameter 17, by replacing theoretical quantities with some tunable variable, which we denote as Ir. For methods with fixed stepsize, we simply set Ir. For methods based on Adaptive
SGD we set i7 = Ir (Ei af 2 (see Section 3.1 on Zhang et al. [44] for intuition).
and for "implicit clipping" we set 17: = lr c/ (c + lI
We tune Ir and e by performing a two-level, two-dimensional grid search. In the first-level grid, the values geometrically spaced by factor of 10: The values for e are (102 (102,..., ...; 107). The values for ir are (10-10 ..... 10 10-5) for SGD, (10-7 ..... 10-2) for clipped SGD, and (10 ..... 1 for both Adaptive SGD and clipped Adaptive SGD, We verify that the best candidate is never at the edge of the grid. Denoting the best candidate as
the second-level grid is defined as ,,,,,,,,,, (c,))
[(r, c) Ir E (frr', fir', .rr 21r 4,r'), c E (fc', fcc,,
H.2 Additional experiments
Parkinsons Telemonitoring dataset. We repeat the experiments presented in Section 4 on the Parkinsons Telemonitoring dataset [36]. The results are displayed in Figures 3 and 4 There are two notable distinctions between the results here and the results in Section 4: In Figure 3c, clipped Adaptive SGD performs worse than the others, which show similar performance. In Figure 4c, the two averaging methods seem identical.
Synthetic data. We perform the same experiments, but instead of a regression-like objective, diag( 1/19, 1). We use the stochastic gradient oracle ((x) = ff(z) + E. where & has iid Gaussian entries and x² | = 4 . 103, We set T 1000 and xm = 1.75 T, where i is a vector of all ones. For each tested method, we plot the median across 100 runs, with a shaded region showing the inter-quartile range. We define the stepsize of each method as knay; The values of a and n,, unless
we use the function f 20 E given by f(x) | where
32

---

siandand clipping impiiit cápping
dipped SGD
dipped dabp odaptive SCD
10
adspthve dlpping
00 Kxr13
137
10-
of alcchsst greckota
st secrosss gaadent
Mbcrerlk grad
Figure 5: Sub-optimality of SGD variants as function of the number of stochastic gradients used, on the loss f(x) = |Ax| with synthetic noise. We plot the median across 100 runs, with a shaded region showing the inter-quartile range.
double sam plingin single campling
double sampling single sampling
average average over 8
10
301
y>*
enwttaii grsteeer
1300
250
ed of
PD
105
(a)
(b)
(c)
Figure 6: Ablations of Algorithm 1. Figures 6a and 6b compares single and double sampling by plotting sub-optimality as a function of gradient and iteration budget, respectively. Figure 6e compares different averaging methods. We plot the median across 100 runs, with a shaded region showing the inter-quartile range.
stated otherwise, are set according to Table 1, leveraging our knowledge the function f. the time T and the noise norm variance σ². The value l is scalar parameter that we tune: We first perform an initial grid search over (0.01, 0.1, 1, 10, 100). Denoting the best value as æ. we then perform a second grid search over f.. 22, xr, 2xr, 4v. In both searches, verify that the optimal value is never at the edge of the grid. The results are displayed in Figures and 6. Here, too, there are only a few distinctions compared to the results in Section In Figure 6b, using single sampling results in the same iteration complexity as using double sampling. In Figure 6c, the difference between the two averaging methods substantial in favor of the method from Algorithm 1.
33


Reviews:
[{"review_id": "siNITetymy", "reviewer": "Reviewer_cvF4", "summary": "The authors propose a Clipped SGD with double sampling. They consider different step selection strategies and also propose an analysis of an adaptive variant of the algorithm.", "questions": "- On line 115, the authors claim to provide the first convergence results for stochastic convex optimization with generalized smoothness, but this is not correct. There are a number of papers considering a stochastic formulation of the problem.\n\n- It follows from the problem statement that the authors consider a deterministic optimization problem (see line 133). Can the authors explain where the stochasticity comes from?\n\n- Line 141 suggests that the oracle is stochastic, but due to the lack of a definition of the oracle, it is not obvious that the oracle is stochastic. The presence of stochasticity should be explicitly stated, e.g., $\\mathcal{G}(x,\\xi)$ or otherwise.\n\n- Assumption 2 contains a very restricted assumption of double differentiability. Is it possible to use a relaxation of the assumption, e.g., see https://proceedings.mlr.press/v202/koloskova23a/koloskova23a.pdf? Assumption 1.2 of https://proceedings.mlr.press/v202/koloskova23a/koloskova23a.pdf?\n\n- The motivation for the light noise is not clear as is the nature of the noise itself from Section 3. It seems to be of more interest to the ML community if the authors consider the heavy tails assumption. Will there be a difference with work https://arxiv.org/pdf/2505.20817?\n\n- Could the authors please clarify in what sense the method can be considered adaptive, given that the threshold parameter $c$ still appears to depend on the constants $L_0$ and $R$? Additionally, could you elaborate on why the constant $L_1$ disappears from the final bounds? A more detailed explanation would be greatly appreciated.", "limitations": "N/A", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 1, "originality": 1, "strengths_and_weaknesses": "Among the strengths of the paper, I would like to highlight that the authors provide high-probability convergence guarantees (with probability at least $1 - \\delta$) for ClipSGD under $\\sigma$-sub-Gaussian gradient noise. The paper also considers varying step sizes (and consequently, varying clipping rules), which adds flexibility to the analysis. Furthermore, the authors claim to establish high-probability convergence results for an adaptive version of ClipSGD. These contributions are valuable and demonstrate a serious effort on the part of the authors.\n\nThat said, I believe that in its current form, the paper is not ready for acceptance at the conference. Below I explain my point of view; if the authors believe I am mistaken, I would be glad to discuss and reconsider.\n\n1) **Motivation of the work**: The introduction is, unfortunately, very poorly structured. In particular, the entire section preceding the statement of contributions reads more like an extended related work discussion on generalized smoothness. As a result, the paper fails to provide sufficient motivation for the problem it addresses. For instance, what is the practical or theoretical motivation for focusing on light-tailed noise and high-probability convergence? Why is double sampling used, and what is the intuition behind this choice? These and other important aspects remain unclear. I am concerned that for readers unfamiliar with the relatively recent field of generalized smoothness (and I believe there are many such readers), the paper may come across as overly theoretical and disconnected from practical relevance.\n\n2) **Clarity of Claims**: While the technical tools employed in the paper are solid, most of the results appear to follow from previously known techniques. As such, the contributions may be viewed as incremental, and it is important that the authors carefully position their results in relation to existing literature. On this note, I would like to respectfully raise a concern regarding the accuracy of certain claims. In particular, the authors state (lines 117–118) that their results in the case $\\sigma = 0$ are consistent with state-of-the-art results for the deterministic regime. However, this statement is inaccurate. For instance, the recent work https://arxiv.org/pdf/2412.17050 offers significantly stronger guarantees in the convex setting. This is especially evident in the regime where $L_0 = 0$: while the current paper suggests convergence only to a limiting neighborhood (an asymptote), the aforementioned work shows linear convergence to the exact solution. Moreover, at the end of page 3, the authors claim that linear convergence is not observed asymptotically. This statement, in the context of $L_0 = 0$, is misleading. The authors of https://arxiv.org/pdf/2412.17050 clearly highlight that when $L_0 = 0$, convergence to arbitrary precision is not only achievable but linear—a significantly stronger result than what is presented here. Additionally, Assumption 2 (as well as Definition 1) in the current paper explicitly allows for the regime $L_0 = 0$ or $L_0 \\to 0$, yet this important setting is not adequately discussed. It would greatly strengthen the paper if the authors acknowledged the existing literature, accurately compared the results, and clarified their contributions in relation to prior work—particularly the work cited above, which appears to provide stronger guarantees under similar assumptions in the case $\\sigma = 0$.\n\n3) **Comparison with Relevant Prior Work**: While the paper provides a fairly detailed overview of existing work in the area of generalized smoothness, it unfortunately lacks direct comparisons between the results obtained in this paper and those in prior literature. This absence significantly weakens the clarity and contextual positioning of the contributions. To improve this, I strongly encourage the authors to include explicit comparisons with relevant previous results throughout the paper. For example, after each main theorem or corollary, it would be helpful to add a short paragraph-discussion. Such discussion would not only help clarify the novelty of the work but also make it more accessible and informative for readers less familiar with the recent literature on this topic. In addition, I strongly recommend citing and discussing the following recent papers, which are highly relevant to the topic:\nhttps://arxiv.org/pdf/2502.00753 and https://arxiv.org/pdf/2505.20817.\n\n4) **Experiments**: The current experimental section does not meet the expectations for a machine learning conference. The empirical results are limited to a synthetic example, with no experiments on real-world datasets or practical tasks where the proposed methods could demonstrate their relevance. Moreover, there are no comparisons with prior or related work, which makes it difficult to assess the empirical advantages or limitations of the proposed approach. In addition, the design and clarity of the figures could be substantially improved. At present, the visualizations do not effectively communicate the key insights or support the theoretical claims made in the paper. To enhance the impact of the work, I would strongly encourage the authors to: Include comparisons with at least a few baselines or state-of-the-art methods, Consider evaluating on real datasets or realistic scenarios, and Improve the figure quality (e.g., readability, overall visual design). A more thorough and polished experimental section would significantly strengthen the paper and help readers better understand the practical value of the proposed contributions.", "was_revised": true, "final_justification": "I still have some concerns regarding the current version of the manuscript, which I outline below with the aim of providing constructive feedback.\n\nMotivation of the work. While the authors provided brief responses to each of the points raised, I believe that incorporating these statements into the introduction, as currently formulated, may not significantly improve the clarity or strength of the motivation. In fact, it may risk confusing readers rather than helping them.\n\nClarity of Claims. I remain concerned about the claim that the desired accuracy levels of $\\varepsilon_1 = 10^{-5}$ and $\\varepsilon = 10^{-5555}$ can be achieved in a constant number of iterations, independent of the accuracy. This assertion appears overly strong and may require further justification or clarification.\n\nComparison with Relevant Prior Work. The absence of a clear discussion and comparison with related work makes it difficult to fully appreciate the contributions and significance of the results. In my view, engaging with relevant literature is essential to properly situate the work within the broader research context.\n\nExperiments. While I appreciate the authors' perspective, I feel that the concerns raised regarding the experimental section have not been fully addressed. In particular, a comparison with related methods would significantly strengthen the empirical part of the paper.", "rebuttal": "**Motivation of the work**:\n> The introduction is, unfortunately, very poorly structured... As a result, the paper fails to provide sufficient motivation for the problem it addresses.\n\nWe respectfully disagree with this assessment, and it seems that no other reviewer shares this opinion.\n- We begin by providing motivation for studying gradient clipping, introducing the concept of $(L_0,L_1)$-smoothness, and highlighting its significance in the context of gradient clipping. \n- We then briefly mention an interesting pattern observed in non-convex analyses (the low-order dependence on $L_1$). \n- We move on to discuss the motivation and challenge of analysing the stochastic convex setting.\n- Then we list our contribution and briefly describe the double-sampling technique.\n\n> For instance, what is the practical or theoretical motivation for focusing on light-tailed noise and high-probability convergence? Why is double sampling used, and what is the intuition behind this choice? These and other important aspects remain unclear. \n\nThe choices you mention are not rooted in an underlying motivation, but rather as a means to realize our goal, which is understanding the theoretical complexity of $(L_0,L_1)$-smooth optimization. As such, we believe that it is more appropriate to discuss them in section 3 (lines 145-153, 160-165). \n\nHaving said that, we can revise the introduction to note the following:\n- High-probability guarantees are generally favorable compared to in-expectation guarantees.\n- The choice of double-sampling is motivated by the challenge of bias in gradient clipping. \n- Assuming light tails follows published work such as [37], [42] and [43] which, even under this assumption, contribute insightful ideas and are considered valuable.\n\n**Clarity of Claims**:\n> ... most of the results appear to follow from previously known techniques. As such, the contributions may be viewed as incremental...\n\nWhile the general outline of the proof may appear familiar, our argument relies on a novel choice of clipping threshold that allows us to decouple the effects of gradient clipping and gradient noise (Lemma 6), as well as careful use of concentration inequalities (Lemma 8) that are essential for enabling the case-splitting argument at the core of our proof.\n\nTo evaluate the novelty of these techniques we note that:\n- These techniques do not appear in analyses of clipped-SGD under generalized smoothness in the non-convex case.\n- Prior published work have already studied the convex generalized smooth setting, yet they do not manage to remove the exponential dependence on $L_1 R_0$.\n\n> ... the authors state (lines 117–118) that their results in the case $\\sigma = 0$ are consistent with state-of-the-art results for the deterministic regime. However, this statement is inaccurate. For instance, the recent work [link] offers significantly stronger guarantees in the convex setting. This is especially evident in the regime where $L_0=0$: while the current paper suggests convergence only to a limiting neighborhood (an asymptote), the aforementioned work shows linear convergence to the exact solution.\n\nCould you please explain why, in the case $L_0 = \\sigma = 0$, you think our paper suggests convergence only to a limiting neighborhood? When plugging these values to theorem 3, it shows the sub-optimality gap is 0. That is, we show convergence to the exact solution in a constant number of iterations, where the constant is any solution to the inequality $T \\geq \\log(T) (L_1 R_0)^2$.\n\n> Moreover, at the end of page 3, the authors claim that linear convergence is not observed asymptotically. This statement, in the context of $L_0 = 0$, is misleading.\n\nIndeed, that claim is stated for the general $(L_0,L_1)$-smooth case. We can alter it in our next revision to highlight the difference between the general case and $L_0=0$.\n\n**Comparison with Relevant Prior Work:**\n> ... lacks direct comparisons between the results obtained in this paper and those in prior literature...\n\nWe compare our work to existing literature in lines 108-119. Let us reiterate the key point from that part: a crucial factor that affects all known bounds in the stochastic setting is the dependence on either $\\Delta$ or $M$, both of which may be exponential in $L_1 R_0$. One of the main novelties in our work is surpassing this exponential dependence.\n\n> In addition, I strongly recommend citing and discussing the following recent papers, which are highly relevant to the topic: [link] and [link].\n\nWe would be happy to discuss the first paper in our next revision. The second paper was released after the neurips deadline, so we think it is fair to view it as subsequent to our work.\n\nLet us elaborate on the first paper: it studies stochastic mirror descent under $\\ell$-smoothness (a generalization beyond $(L_0,L_1)$-smoothness), and shows a convergence rate with an implicit exponential dependence on $L_1 R_0$. This dependency can be deduced by looking at their proof: eqn. 202 (page 62) relies on $L_{t-1}$, a function of the initial gradient norm. The authors claim that this quantity is $O(1)$, but it is only because they treat the initial gradient norm as $O(1)$.\n\n**Experiments:**\n> The current experimental section does not meet the expectations for a machine learning conference. The empirical results are limited to a synthetic example, with no experiments on real-world datasets or practical tasks where the proposed methods could demonstrate their relevance. \n\nOur main experiments are **not** synthetic; they use two real-world datasets and test the (practical) task of linear regression.\n\n> Moreover, there are no comparisons with prior or related work, which makes it difficult to assess the empirical advantages or limitations of the proposed approach. \n\nSince we tune $\\eta$, prior clipping methods are essentially equivalent to single-sampling clipping, which we do test. We also compare our methods to SGD/Adaptive SGD without clipping.\n\n**Questions:**\n> - On line 115, the authors claim to provide the first convergence results for stochastic convex optimization with generalized smoothness, but this is not correct. There are a number of papers considering a stochastic formulation of the problem.\n\nOur exact claim is that we provide “the first rate… **without exponential dependence on $L_1 R_0$**”. If you believe this is incorrect, please show an example and we will make sure to correct this in our next revision.\n\n> - It follows from the problem statement that the authors consider a deterministic optimization problem (see line 133). Can the authors explain where the stochasticity comes from?\n> - Line 141 suggests that the oracle is stochastic, but due to the lack of a definition of the oracle, it is not obvious that the oracle is stochastic. The presence of stochasticity should be explicitly stated, e.g., $\\mathcal{G}(x,\\xi)$ or otherwise.\n\nStochasticity comes from the gradient oracle (as explicitly stated). Our notation is consistent with work such as Zhang et al. (2019).\n\n> - Assumption 2 contains a very restricted assumption of double differentiability. Is it possible to use a relaxation of the assumption, e.g., see [link]? Assumption 1.2 of [link]?\n\nIt is probably possible to relax this, as it only affects basic smoothness lemmas.\n\n> - The motivation for the light noise is not clear as is the nature of the noise itself from Section 3. It seems to be of more interest to the ML community if the authors consider the heavy tails assumption. Will there be a difference with work [link]?\n\nWe leave heavy tails for future work.\n\n> - Could the authors please clarify in what sense the method can be considered adaptive, given that the threshold parameter $c$ still appears to depend on the constants $L_0$ and $R$? \n\nThe use of the word “adaptive” comes from $\\eta_t$ resembling Adaptive SGD (aka AdaGrad-Norm).\n\n> Additionally, could you elaborate on why the constant $L_1$ disappears from the final bounds? A more detailed explanation would be greatly appreciated.\n\nThe intuition is that, roughly speaking, every time clipping occurs we decrease the distance to the minimum by $\\Omega(1/L_1^2)$ (see Claim 2 in the proof sketch and think of $T$ as a fraction of $(L_1 R_0)^2$). Therefore, there can be at most $(L_1 R_0)^2$ such iterations. The rest of the trajectory behaves as though the function was $L_0$-smooth."}, {"review_id": "8dsOM61El7", "reviewer": "Reviewer_2xE3", "summary": "This paper investigates stochastic gradient descent (SGD) with gradient clipping on convex functions, assuming (L0, L1)-smoothness. The authors provide theoretical results demonstrating that clipped SGD achieves a convergence rate comparable to that of standard SGD under the L-smoothness assumption, albeit with additional terms and polylogarithmic factors. The analysis is extended to adaptive versions of SGD with gradient clipping, and empirical results are presented to showcase the effectiveness of clipping.", "questions": "1. The paper discusses gradient clipping but does not offer detailed guidance on how to select the clipping threshold, particularly in real-world settings where data and gradients may vary. Could the authors provide more practical advice on how to tune the threshold in practice?\n\n2. Are the assumptions (particularly the distance bound R and the Sub-Gaussian noise assumption) used in this paper standard and commonly accepted in the literature on related topics?", "limitations": "N/A", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The paper makes a good theoretical contribution, providing clear convergence bounds for clipped SGD in the context of convex, stochastic (L0, L1)-smooth functions.\n2. The theoretical presentation is both clear and well-organized. Key ideas are succinctly explained, and the overall structure of the paper is logical and easy to follow.\n3. The authors back up their theoretical claims with empirical experiments, lending credibility to their findings and demonstrating the practical relevance of their proposed methods.\n\n**Weaknesses:**\n\n1. While the empirical results illustrate the method's effectiveness, additional experiments on more complex tasks and larger datasets would improve the generalizability of the conclusions.\n2. The double-sampling technique, while theoretically sound, seems to provide limited practical benefits. Additionally, the paper introduces several variations of SGD with clipping (standard, implicit, and adaptive), but it is not immediately clear which method performs best under different real-world conditions or how to select the most efficient one in practice.\n\n**Typo:** Line 152 contains two semicolons.", "was_revised": true, "final_justification": "I have carefully read the author's rebuttal and the other reviewers' reviews, including the responses from other reviewers. As other reviewers have also mentioned, the experiments in this paper could be further refined to highlight the effectiveness and advantages of the proposed method. Although the author responded that this is a theoretical paper, I still believe that more solid experimental results would make the paper more convincing", "rebuttal": "**Strengths:**\n> 1. The paper makes a good theoretical contribution, providing clear convergence bounds for clipped SGD in the context of convex, stochastic (L0, L1)-smooth functions.\n> 2. The theoretical presentation is both clear and well-organized. Key ideas are succinctly explained, and the overall structure of the paper is logical and easy to follow.\n\nWe thank the reviewer for their thoughtful and encouraging review. We are glad that the contributions, proofs, and presentation were found to be clear and compelling.\n\n**Weaknesses:**\n> 1. ... additional experiments on more complex tasks and larger datasets would improve the generalizability of the conclusions.\n> 2. The double-sampling technique, while theoretically sound, seems to provide limited practical benefits. Additionally, the paper introduces several variations of SGD with clipping (standard, implicit, and adaptive), but it is not immediately clear which method performs best under different real-world conditions or how to select the most efficient one in practice.\n\nWe indeed aim to position this paper as theoretical, focusing on the complexity of $(L_0,L_1)$-smooth optimization and how proper clipping helps to achieve it. \n\nOn the matter of the several variations, please note the following.\n- In analyzing an AdaGrad-like stepsize, we provide support for the common practice of using Adam with clipping. \n- Our experiments show that all variations have similar performance, which is a useful observation in itself.\n\n> **Typo:** Line 152 contains two semicolons.\n\nThank you for the careful reading! We will fix this typo in the next revision.\n\n**Questions:**\n> 1. The paper discusses gradient clipping but does not offer detailed guidance on how to select the clipping threshold, particularly in real-world settings where data and gradients may vary. Could the authors provide more practical advice on how to tune the threshold in practice?\n\nThe most straightforward approach is to employ standard hyperparameter tuning (grid search) to tune the threshold, which for some reason is rarely performed. An observation which might prove useful is that our thresholds either scale like $\\sqrt{T}$ (“standard” clipping) or remain constant (“conservative” clipping for sufficiently large $T$).\n\n> 2. Are the assumptions (particularly the distance bound R and the Sub-Gaussian noise assumption) used in this paper standard and commonly accepted in the literature on related topics?\n\nThe distance bound $R$ is standard in analyses of AdaGrad and its variants. The noise assumption is also standard when proving high-probability bounds and appears in published work. In the context of $(L_0,L_1)$-smooth optimization, see [37], [42] and [43]; the last two the even stronger bounded noise assumption."}, {"review_id": "Q4LlWIo48s", "reviewer": "Reviewer_kUhz", "summary": "This work analyzes the stochastic gradient descent algorithm for solving minimization problems under the $(L_0, L_1)$ smoothness condition. They provide a high probability convergence rate that matches the rate under the $L$-smoothness assumption up to poly-logarithmic terms.", "questions": "1. Why do you need $\\mathcal{T}_1$ in the algorithm. I couldn't find where you used it.\n2. Where do you use assumption 3? This appears to be a very strong assumption.", "limitations": "Yes", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strength:\n\n1. Analysis of stochastic gradient descent under $(L_0, L_1)$-smoothness assumption. \n2. Convergence rate of SGD under $(L_0, L_1)$-smoothness assumption matches that of $L$-smoothness assumption upto a polylogarithmic factor. \n\nWeakness:\n1. In line 7 of the algorithm, the authors use projection onto the Ball of radius $R$ for adaptive methods. The value of $R$ depends on $\\|x_0 - x_*\\|$, which basically means you need the knowledge of $x_*$. This makes the algorithm impractical as the knowledge of $x_*$ is not known a priori.  \n2. All the algorithms require the knowledge of the total number of iterations $T$ to set the step sizes. This is not ideal in practice.\n3.  The algorithms also need the knowledge of $\\sigma$ or the variance of the gradient estimator to set the step size. This won't be available in practice. \n4. In contribution point 4, the author mentions the advantage of clipped SGD over SGD in numerical experiments. However, I do not observe any advantage of clipping in the experiments. \n5. The experiments are very basic. There is no proper evidence to show the advantage of gradient clipping or average over only $\\mathcal{T}_2$.", "was_revised": true, "final_justification": "Based on the experimental results, the advantages of using clipped SGD are not clear to me, and the algorithm requires the knowledge of quantities that are known a priori. Moreover, I believe that, given the existence of similar results in the deterministic setting, deriving the results in the paper under the assumptions on the stochastic gradients is not particularly challenging.", "rebuttal": "**Weaknesses:**\n> 1. In line 7 of the algorithm, the authors use projection onto the Ball of radius $R$ for adaptive methods. The value of $R$ depends on $|x_0 - x_*|$, which basically means you need the knowledge of $x_*$. This makes the algorithm impractical as the knowledge of $x_*$ is not known a priori.\n\nWe do not need to know the optimum itself, but rather a bound on the initial distance from it.\n\n> 2. All the algorithms require the knowledge of the total number of iterations $T$ to set the step sizes. This is not ideal in practice.\n> 3. The algorithms also need the knowledge of $\\sigma$ or the variance of the gradient estimator to set the step size. This won't be available in practice.\n\nWe indeed aim to position this paper as theoretical, focusing on the complexity of $(L_0,L_1)$-smooth optimization and how proper clipping helps to achieve it. Our main contribution is obtaining an additive dependence on $L_1$ and a non-exponential dependence on $L_1 R_0$, for both Clipped SGD and Clipped Adaptive SGD.\n\nIn general, it is very standard in optimization research to set the stepsize using $R_0$, $T$ and $\\sigma$, and results of this sort are considered of value. Avoiding them is usually tackled in dedicated future work. We consider our “conservative” variations, which are independent of $L_1$, as a stepping stone towards this.\n\n> 4. In contribution point 4, the author mentions the advantage of clipped SGD over SGD in numerical experiments. However, I do not observe any advantage of clipping in the experiments.\n\nThe synthetic experiments in the appendix show an advantage, but we agree that it is not clear how much the advantage persists in real-world losses. Thank you for noticing this. We will correct this point in our next revision.\n\n**Questions:**\n> 1. Why do you need $\\mathcal{T}_1$ in the algorithm. I couldn't find where you used it.\n\nYou are right in your observation that it is not necessary to maintain it. The reason we denote it explicitly in the algorithm is to make the later analysis easier to follow.\n\n> 2. Where do you use assumption 3? This appears to be a very strong assumption.\n\nWe conduct most of the analysis itself under assumption 3, and then use a reduction to lift our results to hold under (the weaker) assumption 4. See lines 149-153, 229-237."}, {"review_id": "yP43dtjPUe", "reviewer": "Reviewer_6Ygu", "summary": "This paper studies the high-probability convergence of a double-sampling variant of clipped SGD with five different configurations of stepsize/clipping rule/threshold under convexity and the $(L_0, L_1)$-smoothness. For this algorithm, the authors exploit a reduction from Attia and Koren to avoid some issues in previous works on the stochastic convex setting, such as the reliance on the interpolation condition or the exponential dependence of convergence rates on problem parameters. The result also recovers the best-known rate in the deterministic setting when gradient noise is zero.", "questions": "- How does $R$ (\"$x^\\*$ with distance at most $R$ from initialization $x_0$\") in Assumption 1 differ from $R_0 := \\\\|x_0 - x^*\\\\|$? The authors claim that $R$ is only needed for the analysis of adaptive variants. However, the non-adaptive options in the first three lines of Table 1 still depend on $R_0$?\n\n- Why are stepsize $\\eta_t$ and threshold $c$ tuned independently in the experiments (by two-dimensional grid search), considering that they depend on the same set of problem constants? For example, when $L_0 = 0$ and $L_1=1$, $\\eta_t$ in the \"standard\" clipped SGD should be $1/(16 c)$. \n\n- Some previous work under convexity and the $(L_0, L_1)$-smoothness use a weaker definition of $(L_0, L_1)$-smoothness from Zhang et al. (2020a) that does not require $f$ to be twice-differentiable. Can the result in this paper be established under this weaker assumption?\n\nZhang, Bohang, Jikai Jin, Cong Fang, and Liwei Wang. \"Improved analysis of clipping algorithms for non-convex optimization.\" Advances in Neural Information Processing Systems 33 (2020): 15511-15521.\n\n- In Lemma 12, the authors first provide a bound for $\\sum_t \\alpha_t \\Delta_t$  and then state, \"If we also assume the setting of Lemma 10, then\" and provide a different bound. But its proof proceeds by using results from Lemma 10 (in line 871).\n\n- Theorem 1: $\\delta\\in(0,1)$ $\\rightarrow$ $\\delta\\in(0,1/2)$?\n\n- Lemma 13: Some of the $\\sum_{t=0}^T$ should be $\\sum_{t=0}^{T-1}$?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The proposed algorithm and its analysis seem to be novel and interesting, especially from the theoretical perspective. \n- Some design choices (such as double sampling and the conservative configuration) are motivated by the theoretical analysis. \n\nWeaknesses:\n- The theoretical analysis offers limited insight into the practical effectiveness of clipped SGD, as certain components (such as double sampling) are introduced primarily for analytical convenience.\n- The empirical performance of the proposed algorithm might be sensitive to the choices of stepsize and threshold, which depend on unknown problem-specific constants. In the experiments, both parameters are tuned using a fine-grained two-level grid search.", "was_revised": true, "final_justification": "This paper does address certain theoretical issues in prior work on convex (L_0, L_1)-smooth optimization (such as the exponential dependence on smoothness parameters). Although they use a technique from a previous paper (not directly focused on the same problem), other parts of the proof remain non-trivial to me.\n\nThe experimental results of this paper are not extensive or large-scale, but they do not fall below the standard set by prior work on this topic.\n\nThe authors resolved most of my concerns. Although they claimed the theory can also be established under a weaker version of $(L_0,L_1)$-smoothness, they did not provide the details.", "rebuttal": "**Strengths:**\n> - The proposed algorithm and its analysis seem to be novel and interesting, especially from the theoretical perspective.\n> - Some design choices (such as double sampling and the conservative configuration) are motivated by the theoretical analysis.\n\nWe thank the reviewer for their thoughtful and encouraging review. We are glad that the novelty of our ideas, as well as the theory-driven design choices, were found to be interesting.\n\n**Weaknesses:**\n> - The theoretical analysis offers limited insight into the practical effectiveness of clipped SGD...\n> - The empirical performance of the proposed algorithm might be sensitive to the choices of stepsize and threshold, which depend on unknown problem-specific constants...\n\nWe indeed aim to position this paper as theoretical, focusing on the complexity of $(L_0,L_1)$-smooth optimization and how proper clipping helps to achieve it. Our main contribution is obtaining an additive dependence on $L_1$ and a non-exponential dependence on $L_1 R_0$, for both Clipped SGD and Clipped Adaptive SGD.\n\n**Questions:**\n> How does $R$ (\"$x^\\star$ with distance at most $R$ from initialization $x_0$\") in Assumption 1 differ from $R_0 ≔ \\lVert x_0 − x^\\star \\rVert$?\n\nThe difference lies in what each symbol represents:\n- $R$ is used as part of our formal setup to describe a constrained optimization setting; together with the algorithm’s projection, it is an effective bound on the problem domain. AdaGrad-like algorithms require such settings.\n- $R_0$ represents the initial distance to the optimum. Note that $R_0$ may be smaller than $R$, so it is preferable for the bounds to depend on $R_0$ rather than $R$.\n\n> Why are stepsize $\\eta_t$ and threshold $c$ tuned independently in the experiments (by two-dimensional grid search), considering that they depend on the same set of problem constants? \n\nWe chose our tuning approach with standard practices in mind. Note that the approach is sufficient in order to answer the questions we introduce in section 4. Tuning $\\eta_t$ and $c$ by tuning $L_0$, $L_1$, etc. is an interesting idea that we can consider for our next revision. However, note that directly using our formulation of $\\eta_t$ and $c$ is still not trivial, as it depends on other theoretical quantities.\n\n> Some previous work under convexity and the $(L_0,L_1)$-smoothness use a weaker definition of $(L_0,L_1)$-smoothness from Zhang et al. (2020a) that does not require $f$ to be twice-differentiable. Can the result in this paper be established under this weaker assumption?\n\nWe believe they can: the $(L_0,L_1)$-smoothness definition is used only in lemmas 1 & 2, which were proven in prior work without assuming twice-differentiability (see footnote on page 4).\n\n> In Lemma 12, the authors first provide a bound for $\\Sigma_t \\alpha_t \\Delta_t$ and then state, \"If we also assume the setting of Lemma 10, then\" and provide a different bound. But its proof proceeds by using results from Lemma 10 (in line 871).\n\nThe reference to lemma 10 in line 871 is an inexact justification on our side, and can be easily fixed (we can provide further explanation if you wish). In our next revision we will make this clearer.\n\n> - Theorem 1: $\\delta \\in (0,1) \\to \\delta \\in (0,1/2)$?\n> - Lemma 13: Some of the $\\Sigma_{t=0}^T$ should be $\\Sigma_{t=0}^{T-1}$?\n\nYou are correct, thank you for your careful reading! We will fix these in our next revision."}]

Author rebuttal:

Meta-review: # Reiew by AC

This paper addresses the stochastic minimization problem under convexity, $(L_0, L_1)$-smoothness, and a light-tailed noise assumption. The authors derive new convergence results for Clip-SGD (and its AdaGrad-type variant) applied to this setting. Their rates achieve logarithmic dependence on the failure probability and avoid exponentially large factors in $L_1 R_0$, where $R_0$ bounds $||x_0 - x_\ast||$. To the best of my knowledge, these are the first convergence guarantees - among both in-expectation and high-probability results - without exponential dependence on $L_1 R_0$, while also attaining the correct (non-accelerated) dependence on the number of iterations $T$ in the convex $(L_0, L_1)$-smooth case without requiring large batch sizes. Prior work either focused on non-convex problems or relied on large-batch regimes. Overall, I view this as a strong theoretical contribution, as deriving high-probability bounds in the $(L_0, L_1)$-smooth setting is highly non-trivial.

Weaknesses include:
- Reliance on the light-tailed noise assumption,
- Inferior empirical performance of clipping with double sampling compared to standard clipping.

However, I believe these weaknesses are outweighed by the theoretical strengths.

I would also like to emphasize the theoretical elegance of double sampling: under light-tailed noise, there is no need to use the same sample for both the update direction and the clipping coefficient (a necessity under heavy-tailed noise). Here, clipping serves primarily to handle $(L_0, L_1)$-smoothness and eliminate exponentially large dependencies on $L_1 R_0$.

# Reviewers' opinions

Three reviewers recommended rejection, while only Reviewer 6Ygu supported acceptance. Below, I explain why I believe the criticisms raised do not justify rejection.

## Reviewer cvF4

Concerns: motivation, clarity of claims, comparison with related work, and limited experiments.

- Motivation: Motivation: I find the motivation sufficient. Light-tailed noise is a standard assumption in stochastic optimization and does arise in practice (e.g., ResNet50 on ImageNet, see [Zhang, Jingzhao, et al. "Why are adaptive methods good for attention models?" Advances in Neural Information Processing Systems 33 (2020): 15383-15393]).

- Clarity of claims: This is a minor issue, easily addressed with an additional remark clarifying the better initial-stage rate.

- Comparison with related work: The comparisons are clear to experts. While they could be made more explicit, I do not see this as essential. Moreover, asking for comparisons with a paper posted on arXiv after the submission deadline is not appropriate.

- Experiments: The experiments are indeed limited, but this alone does not justify rejection given the theoretical contribution.

## Reviewer 2xE3

Concerns: experiments and double sampling - largely the same weaknesses I acknowledged. As argued above, I believe the theoretical contributions outweigh these limitations.

## Reviewer kUhz

Concerns: limited experiments, projection onto a ball of radius $R$, and the need to know $\sigma$ and $T$ for stepsize selection.

- Projection: This is required only for the adaptive method and is a standard assumption in AdaGrad-type analyses (bounded gradients or bounded domain).
- Stepsize dependence on $\sigma$ and $T$: While a limitation, it is common across many works in stochastic optimization. Even with these assumptions, the results are non-trivial and advance the theoretical understanding of stochastic methods.

## Reviewer 6Ygu

This reviewer found the proposed algorithm and results novel and theoretically interesting. Their listed weaknesses overlap with those I already noted.

# Final recommendation

This paper makes a meaningful contribution to the theory of stochastic optimization. The results are novel, the double-sampling idea is theoretically elegant, and the main technical achievement - removing exponential dependence on $L_1 R_0$ in the convex $(L_0, L_1)$-smooth setting - addresses an important gap. While experiments are limited and some assumptions could be stronger, the paper’s theoretical contributions are substantial and clearly outweigh the weaknesses.

**Therefore, despite three negative reviews, I recommend that this paper be accepted to NeurIPS.**
Decision: Accept (poster)