Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity
Authors: Eduard Gorbunov
Nazarii Tupitsa
Sayantan Choudhury
Alen Aliev
Peter Richtárik
Samuel Horváth
Martin Takáč
Venue: ICLR 2025 Poster (2025)
Keywords: generalized smoothness
first-order optimization
convex optimization
Polyak stepsizes
gradient clipping
adaptive optimization
acceleration
Primary area: optimization

Abstract: Due to the non-smoothness of optimization problems in Machine Learning, generalized smoothness assumptions have been gaining a lot of attention in recent years. One of the most popular assumptions of this type is $(L_0,L_1)$-smoothness (Zhang et al., 2020). In this paper, we focus on the class of (strongly) convex $(L_0,L_1)$-smooth functions and derive new convergence guarantees for several existing methods. In particular, we derive improved convergence rates for Gradient Descent with (Smoothed) Gradient Clipping and for Gradient Descent with Polyak Stepsizes. In contrast to the existing results, our rates do not rely on the standard smoothness assumption and do not suffer from the exponential dependency on the initial distance to the solution. We also extend these results to the stochastic case under the over-parameterization assumption, propose a new accelerated method for convex  $(L_0,L_1)$-smooth optimization, and derive new convergence rates for Adaptive Gradient Descent (Malitsky and Mishchenko, 2020).

Published as a conference paper at ICLR 2025
METHODS FOR CONVEX (Lo, LI)-SMOTTH OPTIMIZA- TION: CLIPPING, ACCELERATION, AND ADAPTIVITY
Eduard Gorbunov* MBZUAI
Nazarii Tupitsa' MBZUAI
Sayantan Choudhury Johns Hopkins University
Alen Aliev MBZUAI
Innopolis University
Peter Richtárik KAUST
Samuel Horváth MBZUAI
Martin Takáč
MBZUAI
ABSTRACT
Due to the non-smoothness of optimization problems in Machine Learning, gen- eralized smoothness assumptions have been gaining a lot of attention in recent years. One of the most popular assumptions of this type is (T.p T. -smoothhssss (Zhang et al., 2020b). this paper, we focus on the class (strongly) convex (Lo, L-s-moooth functions and derive new convergence guarantees for several ex- isting methods. In particular, we derive improved convergence rates for Gradient Descent with (Smoothed) Gradient Clipping and for Gradient Descent with Polyak Stepsizes. In contrast to the existing results, our rates do not rely on the standard smoothness assumption and do not suffer from the exponential dependency initial distance to the solution. We also extend these results to the stochastic case under the werrparaaeeterization assumption, propose new accelerated method for convex (Lo. -smoohh optimization, and derive new convergence rates for Adaptive Gradient Descent (Malitsky & Mishchenko, 2020).
the
INTRODUCTION
Modern optimization problems arising in Machine Learning (ML) and Deep Learning (DL) are typically non-smooth, i.e., the gradient of the objective function is not necessarily Lipschitz continu- ous. In particular, the gradient of the standard éz-regression loss computed for simple networks is not Lipschitz continuous (Zhang et al., 2020b). Moreover, the methods that are designed benefit from the smoothness of the objective often perform poorly in Deep Learning, where problems are non-smooth. For example, variance-reduced methods (Schmidt et al., 2017: Johnson & Zhang, 2013; Defazio et al., 2014; Nguyen et al., 2017; 2021; Beznosikov & Takáč, 2021; Shi et al., 2023) are known to be faster in theory (for finite sums of smooth functions) but are outperformed by slower theoretically non-variance non-variance-rrduced methods (Defazio & Bottou, 2019). All of these reasons motivate researchers to consider different assumptions replace the standard smoothness assumption.
One such assumption is (Lo, L1)-smoothness originally introduced by Zhang et al. (2020b) for twice differentiable functions. This assumption allows the norm of the Hessian of the objective to increase linearly with the growth of the norm of the gradient. In particular, (Lo, L1 }smooohhness can hold even for functions with polynomially growing gradients - a typical behavior for DL problems. Moreover, the notion of (Lo, L, smoothhness can also be extended to the class of differentiable but not necessarily twice differentiable functions (Zhang et al., 2020a; Chen al., 2023).
Although Zhang et al. (2020b) focus on the non-convex problems as well as more recent works such as (Zhang et al., 2020a; Zhao et al., 2021; Faw et al., 2023; Wang et al., 2023; Li et al., 2024b; Chen et al., 2023; Hübler et al., 2024), the class of (Lo. ) -smooth conver! function is much weaker explored. particular, the existing convergence results for the methods such as Gradient Descent with
Equul contribution. Corresponding author F. Gorbunov (eduard. www.bnowggmbuuai...o ac.. Research Center the Artificial Intelligence Institute of Innopolis University, Innopolis, Russia Although many existing problems not convex, it is useful to understand methods hehavior under the convexity assumption well due several reasons; see further details in Appendix A.

---

Published as a conference paper at ICLR 2025
Clipping (Pascanu al., 2013) and Gradient Descent with Polyak Stepsizes (Polyak, 1987) applied to (Lo, L1 -smooth convex problems either rely on additional smoothness assumption (Koloskova et al., 2023: Takezawa et al., 2024) require (potentially) small stepsizes to ensure that the method stays in the compact set where the gradient is bounded and, as a consequence of (T-o I >-mmoothness of the objective, Lipschitz continuous (Li al., 2024a). This leads us the following natural question:
How the convergence bounds for different versions of Gradient Descent depend on Lg and L when the objective function is convex, Lo, -smoooh but not necessarily L-smooth?
In this paper, we address the above question for Gradient Descent with Smoothed Gradient Clipping, Polyak Stepsizes, Similar Triangles Method (Gasnikov & Nesterov, 2016), and Adaptive Gradient Descent (Malitsky & Mishchenko, 2020): for each of the mentioned methods, we either improve the existing convergence results or derive the first convergence results under (Lo, L1) smmothhnnsss We also derive new results for the stochastic versions of Gradient Descent with Smoothed Gradient Clipping and Polyak Stepsizes.
1.1 PROBLEM SETUP
Before continue the discussion of the related work and our results, we need formalize the problem setup. That is, we consider the unconstrained minimization problem
min f(x), #ER
where Rd + R is a (strongly) convex differentiable function.
Assumption (Convexity). Function f IRd + R is p-strongly convex with p 3 O:
f(y) > f(z)+ (VF(z))) x) + fell-yll Va,ye Rd.
(2)
As we already mentioned earlier, in addition to convexity, we assume that the objective function is (oo, In J-smooth. Following" Chen et al. (2023), we consider two types of (I., I1)- smoothness.
Assumption 2 (Asymmetric (Lo, L1) smoothnsss.. Function I2dd + IR is asymmetrically (Lo, -mmoohh (f & Lasym (Lo, L1)), i.e., for all x, Rd we have
[Vf(()) v f())l < (Lo + V || yll-
(3)
Assumption 3 (Symmetric (Lo, I, smmothhtts)),s Function f : Rdd + R is symmetrically (Lo, LT)- smooth (f C.ymmmLLL L1)), i.e., for all x, y Rd we have
[V)(z) - ff(i)) < Lo L1 L1 sup [Vf(ui]] ||> vll-
u<(=:0)
Clearly, Assumption 3 more general than Assumtpion Due to this reason, we mostly focus on Assumption 3, and by (Lo. Lmmmmmothh functions, we mean functions satisfying Assumption 3 if the opposite is not specified. Nevertheless, it worth mentioning that asymmetric (Lo, Lmm-mmoothness (under some extra assumptions) is satisfied for certain problem formulation appearing in Distribu- tionally Robust Optimization (Jin et al., 2021). Chen et al. (2023) also show that exponential function satisfies (4), and, more generally, for twice differentiable functions Assumption 3 is equivalent to
V [<>)) & Lo + L [x))],, Vr Rdd
Moreover, below, we provide some examples of functions satisfying Assumption 3 but either not satisfying standard L-smoothness, i.e., (4) with L, O, or satisfying T-smoothness with larger constants than Lo and L, respectively. The detailed proofs are deferred to Appendix B.
Example 1.1 (Power of Norm). Let f=) ||>||2", where a positive integer. Then, f(x) convex and (2n, 2n -moshh.hh Moreover, f(x) is not L-smooth for n 2 2 and any L 2 0.
"In this paper, we consider standard fn-nrrm for vectors and spectral norm for matrices.
"The first version of Assumptions 2 and 3 proposed by Zhang al. (2020a).
2

---

Published as a conference paper at ICLR 2025
Example 1.2 (Exponent of the Inner Product). Function f(x) expp(Taa 2) for some E R is convex, (0, ||a]]) smoothh but not L-smooth for a # 0 and any L > 0.
These two examples illustrate that (Lo, ssmmoottssssss is quite a mild assumption, and it is strictly weaker than L-smoothness. However, the next example shows that even when L-smoothness holds, makes sense to consider (Lo, -mmoothhssssss as well.
Example 1.3 (Logistic Function). Consider logistic function: f(x) = log (1 + exp(-a (aaaaaaa))) x)). where a E IRd is some vector. It known thut this function is L-smooth and convex with I. = ||a|?? However, one can show that f is also (Lo, (oo,-11)smoool smooth with Lo = 0 and L1 = ||a|]. For ||a|| > 1, both Lo and L1 are much smaller than L.
1.2 RELATED WORKS
We overview closely related works below and defer the additional discussion to Appendix A.
Results in the non-convex case. Zhang et al. (2020b) introduce (To, [s)-smoothness in the form (5) and show that Clipped Gradient Descent (Clip-GD) has iteration complexity O (max (LoA/E2, (12))/// with A := f(x) - xnf f(z) for finding s-approximate first- order stationary point of (Lg, -mooohh function. The asymptotically dominant term in this complexity O (LoA/e²) is independent of L., and thus, this term can be much smaller than O (LD/2), where L is Lipschitz constant of the gradient (if finite). Under the assumption that M == sup[IVV[(x))
E IRd such that (xx & [(=))) < +0o Zhang et al. (2020b) also show that GD with stepsize θ (f/Lo++M..) has complexity ((LotMML))//2)) which is natural to expect since on {i E Ra f(x) & f(z")} the norm of the Hessian is bounded as La + ML1 (see (5)), ie., function is (Lo + -smoothhh Zhang et al. (2020a) generalize the results from (Zhang et al., 2020b) to the method with heavy-ball momentum (Polyak, 1964) and clipping of both momentum and gradient. Similar results are derived for Normalized GD (Zhao et al., 2021; Chen et al., 2023), SignGD (Crawshaw et al., 2022), AddGrad-Norm/AdacGe Adam (Wang et al., 2022; Li et al., 2024b), and Normalized GD with Momentum (Hübler et al., 2024). Notably, all papers in this paragraph also address stochastic method versions.
(Faw al., 2023; Wang et al., 2023),
Results in the convex case. To the best of our knowledge, convex (Lo. L1 )smoohh optimization studied in three papers* (Koloskova et al., 2023; Takezawa et al., 2024; Li al., 2024a). In particular, under convexity, L-smoothness, and (Lo. smoohhnosssssss Koloskova et al. (2023) show
complexity of finding g-solution, i.c. x such that f(x) - fx²) & E, where x" E arg min f(x) and Rg := ||200 2=I1. In particular, if e To/L1, then the asymptotically dominant term in the complexity is O (LoR)/E), i.e., it is independent of L1 and L. which can be significantly better than the complexity of GD of O (LR8/E) for convex I-smooth functions. In the same setting, Takezawa et al. (2024) prove O (max/ (LoRE/e, V / complexity bound for GD with Polyak Stepsizes (GD-PS). Finally, under convexity and (Lo- L Li et al. (2024a) show that for sufficiently small stepsizes standard GD and Nesterov's 's method (NAG) (Nesterov, 1983) have complexities O (eRe/s) and O (V (eRöfe) respectively, where E := Lo + L2G G and G is some constant
that Clip-GD with clipping level e has O (max/ (LoteL))Ak/,
/RbLiLotcti)/24 (
depending on Lo, In, Ro: [Vf(2")), and f(=")- - -(xx). ). In particular, constant G and stepsizes are chosen in such way that it is possible to show via induction that in all points generated by GD/NAG and where (Lo, Li)-smoothness is used the norm of the gradient is bounded by G. However, these results have common limitation: constants L (if finite) and & can be much larger than Lo and L1. Moreover, for Glip-GD and GD-PS, these results lead to a natural question of whether it is possible to achieve O (1.R8/)) complexity without L-smoothness non-asymptotically.
1.3 OUR CONTRIBUTION
Tighter rates for Gradient Descent with (Smoothed) Clipping. We prove that Gradient Descent with (Smoothed) Clipping, which we call (Lo, GDD. has O (max Ro. L R2)) worst-case
*After the first version of our paper appeared online, another highly-relevan paper appeared online (Vankov al., 2024). In particular, Vankov et al. (2024) independently derive similar results ours for (Lo, LD) and GD-PS, and also obtained new convergence bounds for Normalized GD and improved accelerated rates.
3

---

Published as a conference paper at ICLR 2025
complexity of finding e-solution for convex (Lg, L1)-smooth functions. In contrast to the previous results (Koloskova et al., 2023; et al., 2024a), our bound is derived without L-smoothness assumption and does not depend any bound for f
(z*))] [|. To achieve this, we prove that (To, I.)-GD has non-increasing gradient norm and show that the method's behavior consists of phases: initial (and finite) phase when [**()*) > La/t, (large gradient), and final phase when | f(**)]] < Lo/L, and the method behaves similarly to GD applied to Lso-smooth problem. We also extend the result the strongly/stochastic convex cases.
Tighter rates for Gradient Descent with Polyak Stepsizes. For GD-PS, also derive (max { To R8/e, L RR)) worst-case complexity of finding e-solution for convex (Lo, -sm-oho functions. In contrast to the existing result (Takezawa et al., 2024), our bound is derived without L-smoothness assumption. We also extend the result to the strongly/stochastic convex cases.
New accelerated method: (Lo, LI)-Smmilar Triangles Method. We propose a version of Similar Triangles Method (Gasnikov & Nesterov, 2016) for convex (Lo, Li)-mootth optimization, and prove O V Fo[I+TT, exp(1, Ro)) R5/e complexity of finding E-solution for convex (Lo, L1)- smooth functions. In contrast to the accelerated result from (Li et al., 2024a), our bound is derived without the usage of stepsizes depending on Ro and f(²") f(x").
New convergence results for Adaptive Gradient Descent. We also show new convergence result for Adaptive Gradient Descent (Malitsky & Mishchenko, 2020) for convex (Lo, Li -mmoohh problems: prove O mmax { (LoD*/s, m2 (I3 L}Df))) complexity of finding e-solution, where D is a constant depending on initial suboptimality of the starting point, and m is logarithmic factor depending on Lı and D. We also extend the result the strongly convex case.
New technical results for (Lo, Li >-smooth functions. We derive several useful inequalities for the class of (convex) (Lo: -smoohh functions.
TECHNICAL LEMMAS
In this section, we provide some useful facts about (Lo, -mooohh functions. We start with the following result from (Chen et al., 2023).
Lemma 2.1 (Proposition from (Chen et al., 2023)). Assumption: 3 holds if and only for
f ff(ill < (Lo + L [V)())) exp (L1||x vll) || - vll Vx, E Rd.
(6)
Moreover, Assumption 3 implies for all x, E Rd
f(v) & f(x) + (Vf(x), - 2) + Lo + La [[||I
exp(I1lxx- vlD | - vl1
(7)
2
Inequality (6) removes the supremum from (4), but the price for this a factor of exp(Lillz 1- l))
When 2 -ll 1/L,, this factor is upper-bounded as However, in general, it cannot be removed since (6) is equivalentt to (4). Inequality (7) can be seen as a generalization of standard quadratic upper- upper-bound bound for L-smooth functions (Nesterov, 2018) to the class of (Lo, L --smoohh functions. Note, that (Zhang et al., 2020a) provides a Hessian free assumption which is equivalent to (5), it can be seen as (6) and (7) with improved constants.
Using the above lemma, we derive several useful inequalities that we actively use throughout our proofs. Most of these inequalities can be further simplified in the case of Assumption 2.
Lemma 2.2. Let Assumption 3 hold and satisfyš e- Then, the following statements hold.
For fa == inf fxx and arbitrary x. E ERd, we have
v [Vf())]1
2(Lo + L, [V)())]] f(xx) ff.
(8)
If additionally Assumption I holds with μ = 0, then for any x, y E Rd such that
L vl exp (Liliz vll) < 1,
(9)
*One can check numerically that 0.56 v < 0.57.
4

---

Published as a conference paper at ICLR 2025
have
-
f(v)- - (Vf())))
(10)
2(Lo + +
and
- - 2 + (+(() 2(L 4 (
- (V)(2) -V)()))VV()))== v)-
(11)
This lemma provides with set of useful inequalities that be viewed generalizations of analogous inequalities that hold for smooth (convex) functions. We provide the complete proof in Appendix C. Moreover, when Assumption 2 holds, all inequalities from Lemma 2.2 hold with v and requirement (9) is not needed for (10) and (11) to hold. An analog of (8) for local version of (Lo, L1 ssmosoottsssss can be found in (Koloskova al., 2023). We also refer to (Li al., 2024a) for analog of inequality (11) for (r, sm-smh functions. However, in contrast to the bound from (Koloskova et al., 2023), bound (8) derived for a global version of Lo, L1) )smoothhness and thus differs in numerical constants, and, in contrast to the proof from (Li et al., 2024a), we do not use local Lipshitzness of the gradient.
3 SMOOTHED GRADIENT CLIPPING
The first method that we consider is closely related to Clip-GD and can be seen smoothed version of it - see Algorithm 1. Alternatively, this method can be seen as a version of Gradient Descent designed for (Lo, Ls)-mootth functions. Therefore, we call this algorithm (Lo, LD.
Algorithm (Lo, L1 L Gradient Descent (LL, L1)
Input: starting point æº, number of iterations N, stepsize parameter 0, Lo 0. L1 1: for k 0, I...., N- do
2:
xb+1 = x.
Lo LOT2I f((*)
end for Output: V
Similarly to standard GD, (Lo, LD) satisfies two useful properties, summarized below.
Lemma 3.1 (Monotonicity function value). Let Assumption 3 hold. Then, for all k 2 the iterates generated by (Lo, LDD with 7 & - satisfy
n (a
f(x"tl) < f(1²) 2(Lo + LI [ & f((²).
(12)
Proof sketch. The inequality follows from (7) applied to y = b+1 and x = 1² see the complete proof in Appendix D.
Lemma 3.2 (Monotonicity gradient norm). Let Assumptions with μ = 0 and hold. Then, for all k the iterates generated by (Lo, GD)-GD with n & v, - satisfy
[V ++) < [[]()*]]
(13)
Proof sketch. The inequality follows from (11) applied to kk+l and y x² see the complete proof Appendix
We notice that similar result to Lemma 3.2 is shown in (Li et al., 2024a) for GD with sufficiently small stepsize. With these lemmas in hand, we derive the convergence result for (Lo, L GDD.
'Indeed, when [V < Lo/2,, the denominator of the stepsize (Lo, Li)-GD lies [Lo. 2L)). and when | fzx))] > Lo/ f., this denominator lies in [T, [V= /Ta V fz=*))ll Il]. Such behavior is very similar the hchavior of Clip-GD with clipping level Lo/r., r. and stepsize 7/1...
5

---

Published as a conference paper at ICLR 2025
Theorem 3.1. Let Assumptionss with μ and hold. Then, the iterates generated by (Lu, L1)-GD = e satisfy the following implication:
with <
E v 2
V
|V
Lo
K
8L11|20 - x=' 12
and | -x'1' & 1| =x112
x²112
vn
(14)
L1
817
Moreover, the output after N -=
iterations satisfies
f f(x)) Lo | |x00 - =2"
VLoT
2 20 =x"11
(15)
n +1- T) 4L7(N + -)
(NN +
where T = 1 for the set T = {k (0,1....N- - 1} [[ > t.
Proof sketch. Similarly to the proofs from (Koloskova et al., 2023; Takezawa et al., 2024), our proof is based on careful consideration of two possible situations: either fx(*)) > Ta/L, or [V < La/L4- When the first situation happens, the squared distance to the solution decreases by n/8z7. Since the squared distance is non-negative and -on-incce,,,,, this cannot happen more
than "='ll="='11//a times, which gives the first part of the result. Next, when [+*(( < Lo/Li,
the method behaves GD on convex -smoohh problem and the analysis is also similar. Together with Lemmas 3.1 and 3.2, this gives the second part of the proof, see Appendix D for the details. O
Bound (15) implies that (Lo, L1 GDD with 1 4/2 satisfies f(xN) f(=²) < e after N O (max { La f [2 iterations. In contrast, Koloskova al. (2023); Takezawa al. (2024)
derive O maxx (LoRi/e, (RLLLS/)) complexity bound that depends on the smoothness constant L,
which can be much larger than Lo and L,. e.g., when ((x = || constant L depends on the starting point (since it defines a compact set, where the method stays) Lo + Ln [VV = O(1 - ||=0 (see Appendix B). while Lo = 4 and L1 = 3. That is, by moving xd away from the solution, one can make our bound arbitrarily better than the previous unlike the result from (Li et al., 2024a) for GD with small enough stepsize, our bound depends neither on
for this simple example. Morcover,
nor [ f=)")] that can be significantly larger than Rg (according Lemma 2.1 exponentially larger). Finally, we highlight that our analysis shows that (Lo, LDD exhibits two-stage behavior: during the first stage, the gradient is large (this stage be empty), and the squared distance to the solution decreases by a constant, and during the second stage, the method behaves as standard GD. This observation is novel on its own and gives better understanding of the method's behavior. We also provide the result for the strongly convex case in Appendix D.
4 GRADIENT DESCENT WITH POLYAK STEPSIZES
Next, we provide an improved analysis under (Lo, Ls)-mmtthness for celebrated Gradient Descent with Polyak Stepsizes (GD-PS, Algorithm 2).
Algorithm 2 Gradient Descent with Polyak Stepsizes (GD-PS)
Input: starting point _ number of iterations N, minimal value f(x*) mingerd f(x)
1: for k == 1, N do
2: x k+1 x
f(a -
|| (x*))
3: end for
Output: V.
Theorem 4.1. Let Assumptions I with μ 0 and 3 hold. Then, the iterates generated by GD-PS satisfy the following implication:
Lo
222
[[V
||aht1 2²113 < 11 =1=112--
(16)
L1
16L7
Moreover, the output after N steps the iterates satisfy
4Ln | No.
Σ (f(x*) - f(x²)) & 4ho 11.00
LL
x= 2²112 12+
x²112
(17)
4L2

---

Published as a conference paper at ICLR 2025
where T= = { (0,1,........................1 N) 1l
La 1. T TT, and if T - 1, it holds that
[(a - f(x)) 4Lol| - 1²
WLoT
(18)
v(N - +1 4T - -
where aN E {x= xt ................................ ......,]] is such that f(a²)) +'' x (xx). In particular, for inequality N T - 1 guaranteed and
N > 162, 1 =0'1
f(**) f(x²) ALol|= - 21
(19)
v(N 1
Proof sketch. The proof is similar to the one for (Lo, L1 GDD, see the details in Appendix E.
In other words, the above result shows that GD-PS has the same worst-case complexity as (Lo, LI)- GD, and the comparison with the results from (Koloskova et al., 2023; Takezawa et al., 2024; Li et al., 2024a) that we provided after Theorem 3.1 is valid for GD-PS as well. However, in contrast to (Lo, L GDGD, GD-PS requires to know f(x=)) only. In some cases, the optimal value is known in advance, e.g. for wer-pprameterized problems (Vaswani et al., 2019a) f(x = O. In such situations GD-PS can be called parameter-free. The price for this is the potential non-monotonic behavior of GD-PS, which we observed in our preliminary computer-aided analysis using PEPit (Goujaud et al., 2024) even the case of L-smooth functions. Therefore, unlike Theorem 3.1, Theorem 4.1 does not provide last-iterate convergence rates in the convex case and also does not imply that GD-PS has clear two-stage behavior (although the iterates can be split into two groups based on the norm of the gradient as well). We also provide the result for the strongly convex case in Appendix E.
5 ACCELERATION: (Lo: -1)-SMMILAR TRIANGLES METHOD
In this section, we present an accelerated version of (Lo. Li GDG called (Lo. L-S-miilla Triangles Method ((Ln, L1) J-STM, Algorithm 3). This method can be seen an adaptation of STM (Gasnikov & Nesterov, 2016) to the case of (Lo. )-mmooth functions. The main modification in comparison to the standard STM in Line 5: stepsize for GD-type step is now proportional to 1/G.... where Ga+1 is some upper bound on Lo + L V II. while in STM Gk+1 should be an upper bound for the smoothness constant.
Algorithm 3 (Lo, Limmmiil Triangles Method ((Lo, LIM-SMM)
Input: starting point.co x²., number of iterations N, stepsize parameter 7) 1: yd = 20 = x,, A = 0
2: for k 0, l...., N do
3: Set 0 = n(k+2)
and AR+1 = A + 0641
2
4: x k+l Auy 40211=
Ast1
5: gh+l 2² orti
Vf(x+!)), where GK+1 Lo + L1 [
Geil
6: g++ Aoy"+ag11a""
Axt1
7: end for
Output: y/
The next lemma is valid for any choice of GK+1 > Lo +
Lemma 5.1. Let If satisfy Assumptions I with μ = and 3.
Then, the iterates generated by
L2)-STM with 0 < 7) & 5. v - satisfy for all N 3/ 0
GN R2 v
G
G
G R
af
AN (f(D*) f(x)))
R +
|
[
2
2
4G&41
k=
R=
(20)
(21)
where Rs R=:= || x² for all k > 0.

---

Published as a conference paper at ICLR 2025
Since AN > 2N( (see Lemma F.1) and the term from (21) is non-positive the above lemma gives an accelerated convergence rate, if we manage to bound the sum from (20), Unfortunately. in the case of Gk+1 Lo + / [(**+]]]| it is unclear whether this sum bounded due to the well- known non-monotonic behavior (in particular, in terms of the gradient norm) of accelerated methods. Nevertheless, if we enforce G to be non-decreasing as function of k, then from the above lemma one can show that R& remains bounded by Ro and all iterates generated by (Lo. L1)-STM lie in the ball centered x² with radius Rg- This observation is formalized in the theorem below (see the complete proof in Appendix F).
Theorem 5.1. Let f satisfy Assumptions with Y 0 and 3. Then, the iterates generated by and
(To, LTM with 0 < 7 Σ 5. v v== = G1 = Lo + [x))) I],
GR+1 = [ Lo + /
111 kb 0,
(22)
satisfy
exp <xppL1ll='=- f(y f(x)) < 2L (1 L 11 x"
1D -
(23)
N +3)
In the special case of Lm-oth functions (Lj 0), the above result recovers the standard accelerated convergence rate (Gasnikov & Nesterov, 2016). In the general (Lo, L1 )sm-sohhh case, the rate is
also accelerated and implies an optimal O (V Lo exp(I, Roj in ε complexity. In the
case of (Lo, L )-smooth functions, the complexity O ( (ERi/e) from (Li et al., 2024a) derived for Nesterov's ' method applied to convex (r, f)-smooth problem coincides with our result in the worst- case. Indeed, in this special case, & Lo 2., where G ~ [= (Li et al., 2024a, Theorem 4.4). However, according to Lemma 2.1, [V ~ Rg exp( Ro) in the worst case, implying that l ~ [1 2T, Ro exp( (T, Ro)) in the worst case. Nevertheless, the derived complexity is clearly not optimal if L1 is large, Rg is large, and e not too small since /Lo(I+La Ro exp(L, Ri/e can be larger than max { [LoRi/e, L. i... (Lo, L1)-GD and GD-PS can be faster achieving e-solutiion for some values of L,, Ro, and e. Deriving tight lower bound and optimal method for convex (Lo, -mmoohotth optimization remains an open problem.
ADAPTIVE GRADIENT DESCENT
In this section, we consider Adaptive Gradient Descent (AdGD, Algorithm 4) proposed by Malitsky Mishchenko (2020). In the original paper, the method is analyzed under the assumption that the gradient of f is locally Lipschitz, i.e., for any compact set C. gradient of f is assumed to be bounded. Clearly, (Lo, Ls)-mmoothness of f implies that Vf is locally Lipschitz, e.g., this can be deduced from (6). In particular, Malitsky & Mishchenko (2020) prove O(I.D/NN) convergence rate for AdGD, where L is smoothness constant on the convex combination of fx", o x² ...): this set is bounded since the authors prove that AdGD does not leave ball centered at xx with radius D > 0 such that D2 := ||x: x= 1 + ||x 2012 (2x10((((=)) -(xx)))))))))) Moreover, they derive ||
2 < 2D for all A > 1. 1
Algorithm 4 Adaptive Gradient Descent (Malitsky & Mishchenko, 2020)
1: Input: x² E Rd Ao > 0, 0o +00, &
2: x² T0_ - Ao V f(x
3: for = 1,2,... do
- (((
4: Au min
0z- 12--
5:
x c++ t
d Vx(('')
6: Og Xx
Ak
7: end for
In the case of (Lo, Ly Jsmoothness, constant L. can be estimated explicitly: in view of the mentioned upper bounds on ||a- - 1= and ||a* - 11. we have
(6) [VS(t>))| & To exp(TT 1100* x² 1l1 xx1l "1 & To exp
(24)
8

---

Published as a conference paper at ICLR 2025
7/la** -,n
which allows us to lower-bound
V P)ll and X Lo(1+L, exp (L) exp (V2L,D) for
all > 1. Then, following the proof by Malitsky & Mishchenko (2020), we get the following rate (for the definition of g.v and the detailed statement of the result we refer Appendix G):
Lo(1 + La D exp (I, exp (v (V2LD
f(aN) f(x") <
(25)
N
Although this result shows that AdGD has the same rate 1/N of convergence for smooth and (Lo, L1)- smooth functions, constant (1 + D, exp (L) exp (V2L, D) appearing in the upper bound can be huge. To address this issue, derive refined convergence result for AdGD.
Theorem 6.1. Let Assumptions I with μ 0 and hold. For all N 1 we define point &. wxa²).
SN (AN(1 + 0N) + +W " where Wp := Au + 0v) - Ax+ 10+11 SN: == X1 + EK km Ak.
and {a" 1:30 are the iterates produced by AdGD with 7 = 1/4. Then, for N >> mK 12
iterate &º satisfies
2I
f(ēN) - f(x')= <
(26)
v(N mK) V2N 1)T,
where >> 0 and D2 = | x=
+ -11x² -
x2122 22 (f(x)) ffxx))))
m = + 1og
(1+ Doxp (21, m))
K = 2030" and v = e_ particular, for N >
2
(2mK + v
)(m+))); we have
4L vN
_(*N) -(x') &
(27)
The above states that AdGD converges at least ~ (1 + L, exp (L, ex) exp (V2L, D) faster (for sufficiently large N) than the upper bound from (25). This noticeable factor: if I, 1, 10, it is of the order 8 10 Moreover, in contrast to (25), Theorem 6.1 does not follow its counterpart from Malitsky & Mishchenko (2020). To achieve it, we use y = 1/1 to get a new potential function
2²112 + 1 -lla* - 11 2AA - ((x))) )) + Σ lattt x'I?? (28)
t :=:= 1===|>=-=*'0
and show that 0x+1 & t Vk In contrast, the potential function from (Malitsky Mishchenko,
2020) does not have term E || - x=1|3, which is the key for obtaining a better guarantee under (Tn, T. -smoohnttssss. Finally, we also note that up the numerical factors bound (27) coincides with the bound from (Malitsky & Mishchenko, 2020) derived for L-smooth problems. Moreover, up to the numerical factors and the replacement of ||I0 x 212 with 1)2 which might be
larger than ||""" - x² 112 our bound (27) for AdGD coincides with the ones derived for (Lo, GDD
and GD-PS. These facts highlight the adaptivity of AdGD in theory.
7 STOCHASTIC EXTENSIONS
In this section, we consider the finite-sum minimization problem, i.e., we assume that f(x:) == fxx).. f((). Problems of this type are typical for MI. application (Shalev-Shwartz & Ben-David, 2014), where fa( represents the loss function evaluated for i-th example in the dataset and are parameters of the model. Since the size of the dataset n is usually large, stochastic first-order methods such as Stochastic Gradient Descent (Robbins & Monro, 1951) are the methods of choice for this class of problems. However, to proceed, we need to impose some assumptions on functions {
Assumption 4. For all i = 1,..., function fo is convex and symmetrically (Lu, L.) Ln)-smooth, i.e inequalities (2) with μ 0 and for function fo well. Moreover, assume that there exists x² E Idd such that x= E arg min fi(z) for all = 1,..., n, i.e., functions (fa have a common minimizer.

---

Published as a conference paper at ICLR 2025
The first part of the assumption (convexity and (Lo, - -mmoothness of all {f))==) is natural generalization of convexity and (Lu, -mmsoohhhsssss of f to the finite-sum case. Next, the existence of common minimizer x" for all ) is a typical assumption for werrpaarameerrzee models (Belkin et al., 2019; Liang & Rakhlin, 2020; Zhang et al., 2021; Bartlett et al., 1998) and used in several recent works on the analysis of stochastic methods (Vaswani et al., 201 Loizou et al., 2021; Gower et al., 2021). Although Assumption 4 does not cover all possibly interesting stochastic scenarios, it does allow the variance of the stochastic gradients to depend on æ and grow with the growth of ||a - x" ||. which is typical for DL, unlike the standard bounded variance assumption.
For such problems, we consider direct extension of (Lo, L-D called (Lo. L1) Stochhssci Gradi- ent Descent (Lo. LGD, Algorithm 5 in Appendix H.1).
Theorem 7.1. Let Assumption 4 hold. Then, the iterates generated by (Lo, L1) with 0 < r & 5
= e after N iterations satisfy
vTo min
{ [4nL 5( -
2T 2T x= n(N
min k= D...
E
<
(29)
As in the deterministic case, the upper bound is proportional to Lo and 1/(N+1) and does not depend on smoothness constant on some ball around the solution. However, one can notice that the convergence criterion in the above result is quite non-standard: typically, the results are given in terms of [f(=*) f fx" ). This happens because although functions {fA) have a common minimizer, we cannot guarantec that for some ko and any &o > ko we have fz(xx)) < To/L, with probability 1 for all é (1.... n), i.e., the method does not have to converge uniformly for all samples. This implies that with some small probability f(**) f(=") can be larger than vLa/(4n(.)) for any = 0, 1, 1....,N
and any N > However, in view of (29), this probability has to be smaller than 8nLf (N+1) iie.
with probability at least 1- 8nL -="1"" for k(N) such that E min uLoo [4n2]"
f(x f [(x))]
(N+++1
mink=o...... N EE min vLa 4n1..
which is small f(x - f(x*) we have f(xh()) f(x)) < ant.
for large enough n.
Next, we consider SGD-PS proposed by Loizou et al. (2021) (Algorithm 6 in Appendix H.2). In contrast to the deterministic case, SGD-PS requires to know { in advance. Nevertheless, these values equal for some existing over parameterizee models, and thus, the method can be applied in such cases. Under the same assumptions, we also derive a similar result for SGD-PS.
Theorem 7.2. Let Assumption hold. Then, the iterates of SGD-PS after N iterations satisfy
vLa [4n.."
J -1(0))
| 12
min
E
min
<
(30)
k=O.....
v(N +1)
The result is very similar to the one we derive for (Lo, SGG. Therefore, the discussion provided after Theorem 7.1 (with 7) = -//2) is valid for the above result as well.
CONCLUSION AND FUTURE WORK
In this paper, we derive improved convergence rates for (Lo, L-G and GD-PS, derive convergence guarantees for the new accelcrated method called (Lo, D-SMM and also derive new result for AdGD in the case of (strongly) convex (Lo, In) -mmothh optimization. Our results for (Io, La GDD and GD-PS depend neither on [V nor on f(x9) f(x") nor on exponential functions of Rg. We also prove new results for the stochastic extensions of (Lo, GGD and GD-PS in the case of finite sums of functions having common minimizer. Nevertheless, several important questions remain open. One of these questions is the lower bounds for the class of (strongly) convex (Lo, L1)- smooth functions and optimal methods for this class. Moreover, it would be interesting to develop stochastic extensions of (Lo, L GDD and GD-PS with strong theoretical guarantees beyond the case of finite sums with shared minimizer.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
All authors affiliated with the Innopolis University were supported by the Research Center of the Artificial Intelligence Institute of Innopolis University. We thank Konstantin Mishchenko for his useful suggestions for improving the writing. We also thank the anonymous reviewers for their valuable feedback.
REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 508-318, 2016.
Farshed Abdukhakimov, Chulu Xiang, Dmitry Kamzolov, and Martin Takáč. Stochastic gradient descent with preconditioned polyak step-size. Computational Mathematics and Mathernatical Physics, (6(4))6211634 2024.
Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert E Schapire. Boosting the margin: A new explanation for the effectiveness of voting methods. The annals of statistics, 26(5):1651 1998.
Heinz H Bauschke, Jérôme Bolte, and Mare Teboulle. A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications. Mathematics of Operations Research, 42(2):330-348, 2017.
Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contradict statistical optimality? In The 22nd International Conference on on Artificial Intelligence and Statistics, pp. 1611-1619. PMLR, 2019.
Leonard Berrada, Andrew Zisserman, and M. Pawan Kumar. Training neural networks for and by interpolation. In International Conference on Machine Learning. 2020.
Aleksandr Beznosikov and Martin Takáč. Random-reshufiled sarah does not need full gradient computations. In Optimization for Machine Learning Workshop @ NeurIPS 2021, 2021.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points ii: first-order methods. Mathematical Programming, 185(1):315-355 355, 2021.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM
transactions on intelligent systems and technology (TIST), 1-2) 2011.
Xiangyi Chen, Steven 7. Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: geometric perspective. Advances in Neural Information Processing Systems, 33:13773-13782. 2020.
Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smen nonconvex optimization is as efficient smooth nonconvex optimization. In International Conference on Machine Learning. pp. 5396-5427. PMLR, 2023.
Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to unbounded smoothness of generalized signsgd. Advances in neural information processing systems, 35:9955-9968, 2022.
Ashok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails. Advances in Neural Information Processing Systems, 34:4883-4895, 2021.
Aaron Defazio and Léon Bottou. On the ineffectiveness variance reduced optimization for deep learning. Advances in Neural Information Processing Systems, 32, 2019.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27, 2014.
11

---

Published as a conference paper at ICLR 2025
Cong Fang, Chris Junchi Li. Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic rath-integrann differential estimator. Advances Neural Information Processing Systems, 31, 2018.
Hyas Fatkhullin, Niao He, and Yifan Hu. Stochastic optimization under hidden convexity, arXiv preprint 3XXv:24401000006 2023.
Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smooth- ness: A stopped analysis of adaptive sgd. In The Thirty Sixth Annual Conference on Learning Theory, pp. 89-160 PMLR, 2023.
Leonardo Galli, Holger Rauhut, and Mark Schmidt. Don't be so monotone: Relaxing stochastic line search in over-parameterized models. In Advances in Neural Information Processing Systems, 2023.
Alexander Gasnikov and Yurii Nesterov. Universal fast gradient method for stochastic composit optimization problems. arXiv preprint arXiv: 1604.00555 2016.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http:
//www. www.:/ddeeeeernnggooooooooo org.
Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy- tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Systems, 13:15042-15053 2020.
Eduard Gorbunov, Marina Danilova, Innokentiy Shibaev, Pavel Dvurechensky, and Alexander Gasnikov. Near-optimal high probability complexity bounds for non-smooth stochastic op- timization with heavy-tailed noise. arXiv preprint wrXiv:2006.05958, 2021. URL https:
//aaxiiv.rgg/ppe pdf////ff///// /2166. 05958.pdtt
Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient method: O(1/k) last-iterate convergence for monotone variational inequalities and connections with cocoercivity. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 366-402 PMLR, 2022.
Baptiste Goujaud, Céline Moucer, François Glineur, Julien M Hendrickx, Adrien B Taylor, and Aymeric Dieuleveut. PEPit: computer-assisted worst-case analyses of first-order optimization methods python. Mathematical Programming Computation, pp. 1-31, 2024.
Robert Gower, Othmane Sebbouh, and Nicolas Loizou. SGD for structured nonconvex functions: Learning rates, minibatching and interpolation. In International Conference on Artificial Intelli- gence and Statistics, pp. 1315-1323. PMLR, 2021.
Robert M Gower, Mathicu Blondel, Nidham Gazagnadou, and Fabian Pedregosa. Cutting some slack for sgd with adaptive polyak stepsizes. arXiv preprint arXiv:2202.12322 2022.
Elad Hazan and Sham M. Kakade. Revisiting the Polyak step size. In arXiv, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition. pp. 770-778, 2016.
Samuel Horváth, Konstantin Mishchenko, and Peter Richtárik. Adaptive learning rates for faster stochastic gradient methods. arXiv preprint arXiv:2208.08 05287, 2022.
Florian Hübler, Junchi Yang. Xiang Li, and Niao He. Parameter-agnostic optimization under relaxed smoothness, In International Conference on Artificial Intelligence and Statistics, pp. 4861-4866
PMLR, 2024.
Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. Advances in Neural Information Processing Systems, 34: 2771-2782 2021.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013.
12

---

Published as a conference paper at ICLR 2025
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In Interaational Conference on Machine Learning, pp. 5311-5319. PMLR, 2021.
Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning, 2023.
Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems, 36, 2024a.
Haochuan Li, Alexander Rakhlin, and Ali Jadbabaic. Convergence of adam under relaxed assumptions. Advances in Neural Information Processing Systems, 36, 2024b.
Shuang Li, William J Swartworth, Martin Takáč, Deanna Needell, and Robert M Gower. Sp2: second order stochastic polyak method. ICLR 2023, 2022.
Tengyuan Liang and Alexander Rakhlin. Just interpolate. The Annals of Statisties, 48(3):1329-1333 1347, 2020.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59: 85-116, 2022.
Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, and Simon Lacoste-Juliess Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. In International Conference Artificial Intelligence and Statistics, pp. 1306-1314. PMLR, 2021.
Vien V Mai and Mikael Johansson. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. In International Conference on Machine Learning. pp. 7325-7335. PMLR, 2021.
Grigory Malinovsky, Peter Richtárik, Samuel Horváth, and Eduard Gorbunov. Byzantine robustness and partial participation be achieved simultaneously: Just clip gradient differences. arXiv preprint arXiv:2311. 1.127,, 2023.
Yura Malitsky and Konstantin Mishchenko. Adaptive gradient descent without descent. In Interna- tional Conference on Machine Learning, pp. 6702-6712. PMLR, 2020.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing LSTM language models. In International Conference on Learning Representations, 2018.
Arkadi Semenovich Nemirovski and David Borisovich Yudin. Problem Complexity and Method Efficiency in Optimization. A Wiley-Ineerscience publication. Wiley, 1983.
Arkaddii S Nemirovskii and Yu E Nesterov. Optimal methods of smooth convex minimization. USSR
Computational Mathematics and Mathematical Physics, 25(2):21-30, 1985.
Yurii Nesterov. Lectures on Convex Optimization. Springer, 2018.
Yurii Eygenievich Nesterov. A method for solving the convex programming problem with convergence rate O(1/k²). In Dokl. akad. nauk Sssr, volume 269, pp. 543-547, 1983.
Lam Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: novel method for machine learning problems using stochastic recursive gradient. In In 34th International Conference Machine Learning, ICML 2017, 2017.
Lam M Nguyen, Katya Scheinberg, and Martin Takáč. Inexact sarah algorithm for stochastic optimization. Optimization Methods and Software, 36(1):237-2588 2021.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International Conference on Machine Learning, 2013.
Vivak Patel and Albert Berahas, Gradient descent in the absence of global lipschitz continuity of the gradients. arXiv preprint 1rX1v:2210002418. 2022.
13

---

Published as a conference paper at ICLR 2025
Vivak Patel, Shushu Zhang, and Bowen Tian. Global convergence and stability of stochastic gradient descent. Advances in Neural Information Processing Systems, 35:36014-36022 2022.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computa-
tional mathematics and mathematical physics, 4(5):1-17, 1964.
B.T. Polyak.
Introduction to Optimization. Optimization Software, 1987.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky. Alexander Gasnikov, and Peter Richtárik. High-probability bounds for stochastic optimization and variational inequalities: the case of unbounded variance. In International Conference on Machine Learning, 2023.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162:83-112, 2017.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Zheng Shi, Abdurakhmon Sadiev, Nicolas Loizou, Peter Richtárik, and Martin Takáč. Ai-sarah: Adaptive and implicit stochastic recursive gradient methods. 2023.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum deep learning. International conference on machine learning, pp. 1139-1147. PMLR. 2013.
Yuki Takezawa, Han Bao, Ryoma Sato, Kenta Niwa, and Makoto Yamada. Polyak meets parameter- free clipped gradient descent. arXiv preprint arXiv:2405. 15010, 2024.
Danil Vankov, Anton Rodomanov, Angelia Nedich, Lalitha Sankar, and Sebastian U Stich. Optimiz- ing (Lo, s-moohh functions by gradient methods. arXiv preprint arXiv:2410. 10800, 2024.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and an accelerated perceptron. In The 22nd international conference on artificial intelligence and statistics, pp. 1195- 1204. PMLR, 2019a.
Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste- Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. Advances in neural information processing systems, 32, 2019b.
Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Zhi-Ming Ma, Tie-Yan Liu, and Wei Chen. Provable adaptivity in adam. arXiv preprini arXiv: 2290009000 2022.
Bohan Wang, Huishuai Zhang, Zhiming Ma, and Wei Chen. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. In The Thirty Sixth Annual Conference on Learning Theory, pp. 161-190. PMLR, 2023.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. In Advances in Neural Information Processing Systems, 2020a.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020b.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? In Advances in Neural Information Processing Systems, 2020c.
Shen- Yi Zhao, Yin-Peng Xie, and Wu-Jun Li. On the convergence and improvement of stochastic normalized gradient descent. Science China Information Sciences, 64:1-13, 2021.
14

---

Published as a conference paper at ICLR 2025
CONTENTS
Introduction
1.1
Problem Setup
1.2
Related Works
1.3
Our Contribution
2
Technical Lemmas
3
Smoothed Gradient Clipping
Gradient Descent with Polyak Stepsizes
5
Acceleration: (Lo, L1) -Smmilrr Triangles Method
Adaptive Gradient Descent
7
Stochastic Extensions
8 Conclusion and Future Work
10
Extra Related Work
16
Examples of (Lo, L1) --moohhh Functions
18
C Proof of Lemma 2.2
20
Missing Proofs for (Lo, L.G
22
D.1 Comparison with the Proofs from (Koloskova al., 2023; Takezawa et al., 2024; Chen et al., 2023)
25
Missing Proofs for Gradient Descent with Polyak Stepsizes
27
F Missing Proofs for (Lo, -immiar Triangles Method
29
G Missing Proofs for Adaptive Gradient Descent
32
G.I Derivation (25)...
32
G.2 Proof of Theorem 6.1
33
G.3 Convergence in the Strongly Convex Case
36
H Stochastic Extensions: Missing Proofs and Details
39
H.1 (Iog, -tt-hhaatstii Gradient Descent
39
H.2 Stochastic Gradient Descent with Polyak Stepsizes
41
Numerical Experiments
43
15

---

Published as a conference paper at ICLR 2025
A EXTRA RELATED WORK
On the importance of convex analysis. Although many existing problems are not convex, it is useful to understand methods behavior under the convexity assumption as well due to several reasons. First of all, since the class of non-convex functions is too broad, the existing results for this class are quite pessimistic. In particular, among first-order methods, Gradient Descent the best (in theory) first-order method if only smoothness is assumed (Carmon et al., 2021). In contrast, while accelerated//oomnntum methods do not have theoretical advantages over Gradient Descent for non-convex problems and shine in theory only under convexity- assumptions, they work better in practice even when the problems are not convex (Sutskever et al., 2013). Last but not least, several recent works show that some problems appearing in Deep Learning, Optimal Control, and Reinforcement Learning have properties akin to (strongly) convex functions (Liu et al., 2022) and are even hiddenly convex (Fatkhullin al., 2023).
Results for stochastic methods. In the main part of the paper, we mainly discuss the existing convergence results under (Lo, Lsmmmmotts for deterministic methods. However, there ex- ist several stochastic extensions. For non-convex twice differentiable (Lo, Li)-moooth problems with o-bounded noise, Zhang al. (2020b) show O (max { ((Lo+L,0)//², (L.4/e, 5 52/6") com- plexity bound with Á := f(x)= inf f(z) + (5Lo + 2L20)o² + 90 for Clip-SGD with clipping level dependent on the noise level. Zhang al. (2020a) generalize the result from (Zhang et al., 2020b) to the case of (Lo, Li --mooohh functions that are not necessarily twice dif- ferentiable and derive improved O (Ateo"/e) complexity for sufficiently small E. Next, Zhao et al. (2021) derive O (max { 4/s, InA/t2 Le /= complexity bound for Normal- ized SGD with sufficiently large batchsize under o-bounded variance assumption. Under the additional assumption of expected (Lo, L.LLLLm)mooohesss Chen et al. (2023) improve the previ- ous results and derive O ((110-La)4/=-)) complexity for SPIDER (Fang et al., 2018). Craw- shaw et al. (2022) derive a similar bound to the one from (Zhang et al., 2020a) for a Generalized SignSGD under coordinate- wise (Lo, L1 L1)-smoothesss Next, Faw et al. (2023); Wang et al. (2023) derive (high-probability) complexity bounds for AdaGrad-Non sumption. Similar results are obtained for Adam by Wang et al. (2022), and Li et al. (2024b) analyze Adam for (Lo, Lsmmmooth problems under bounded noise assumption. Recently, Koloskova et al. (2023) derive O (max (A/ne", A/nee)) complexity bound of finding E-stationary point for Clip-SGD under o-bounded variance assumption, where is the clipping level, v 1/9(Lo-eLn) is the stepsize, and Ω (min (min(o², {o², / + ViíLo + cLi)a). Next, Li et al. (2024a) obtain O (max (Lā/e, (L, high-probability complexity bound? for SGD with sufficiently small stepsize, where Â == (A+o)/6, 5 is failure probability, and L := Lo (L, + VL Finally, Hübler et al. (2024) prove O (AaA
under the affine variance as-
total (An to)" and O ((1n+a+ -//+/-"
complex- ity bounds for parameter-agnostie and parameter-non-agnossi versions of Normalized SGD with momentum. To the best of our knowledge, there are no results in the literature for convex (Lo, Li)- smooth stochastic optimization.
Gradient clipping. As follows from the above discussion, gradient clipping is a useful tool for handling possible non-smoothness of the objective, which is also confirmed in practice (Goodfellow et al., 2016). However, it is worth mentioning that clipping has also other applications. In particular, gradient clipping is used to handle heavy-tailed noise (Zhang al., 2020c; Gorbunov al., 2020; Cutkosky & Mchta, 2021), to achieve differentiable privacy (Abadi et al., 2016; Chen et al.. 2020), and also to tolerate Byzantine attacks (Karimireddy et al., 2021; Malinovsky et al., 2023).
Polyak Stepsizes. GD with Polyak Stepsizes (GD-PS) is celebrated approach for making GD parameter-free (under the assumption that f(x") is known) (Polyak, 1987). In particular, Hazan & Kakade (2019) show that GD-PS achieves the same rate as GD with optimally chosen constant stepsize (up to a constant factor) for convex Lipschitz. functions, convex smooth functions, and strongly convex smooth functions. Moreover, some recent works (Loizou et al., 2021; Galli et al.,
"The complexity hound from (Iii et al., 2024a) for more general notion of smoothness. The complexity bound we provide in the text is the special case of the one from (Li al., 2024a).
16

---

Published as a conference paper at ICLR 2025
2023; Berrada et al., 2020; Horváth et al., 2022; Gower et al., 2022: Abdukhakimov al., 2024; Li et al., 2022) also consider different stochastic extensions of GD-PS.
Other Notions of Generalized Smoothness. (Lo, L1) smoothness belongs to the class of sumptions on so-called generalized smoothness. Classical assumptions of this type include Hölder continuity of the gradient (Nemirovski & Yudin, 1983; Nemirovskii & Nesterov, 1985), relative smoothness (Bauschke et al., 2017), and local smoothness, i.e., Lipschitzness of the gradient on any compact (Malitsky Mishchenko, 2020; Patel Berahas, 2022; Patel et al., 2022; Gorbunov et al., 2021; Sadiev et al., 2023). Although these assumptions are quite broad (e.g., for local smooth- ness, it is sufficient to assume just continuity of the gradient), they do not relate the growth of non-smoothness/oocal Lipschitz constant of the gradient with the growth of the gradient distance to the solution. From this perspective, assumptions such as polynomial growth the gradient norm (Mai & Johansson, 2021), a-symmetric (Lo, L1 >smoothnness (Chen al., 2023) which also introduces the key technical tools, and (r, e) -mmoothhessss (Li et al., 2024a) are closer to Assumption than local Lipschitz/Hölder continuity of the gradient and relative smoothness.
17

---

Published as a conference paper at ICLR 2025
B EXAMPLES OF (Lo, -SM-OHTTHH FUNCTIONS
Example B.1 (Power of Norm). Let [(x) ||a||2n, where is positive integer. Then, (xx is convex and (2n, 2n 1)-smooth. Moreover, J (xx is not L-smooth for n 2 2.
Proof. Convexity of follows from convexity and monotonicity of (p(t) = 2 for > and convexity of h(x) = | since f(z) = ((h(x))). To show (Lo. smmooththsssss, we compute gradient and Hessian of f(x)::
Vf(x) = 2n| 2n||=r|2(mn1))
V2f(x) = (2I,
if = 14n(n 1)11==111(0002)1110 2n||=||2<=111,
if 1.
Therefore.
[V)(2)] 2n||z|||n-1
[2.
if 1
[
12m(2n - 1)]1==
if 1
2n(2n
which implies
VV (2n - 1)]1v\ 2n(2n || 2n ||=11)
If ||>||| > 1, then we have /| < (2n - (>)] If ||=||| < 1, then
| f(x)ll (2n (=)) 2n(2n 1) max (t())
[E
where vi(t) = 2 t). For n 1 we have max (tt) = and [x)]l=) - (2n
2n
1)l < 2. For n > we have max vi(t) = 2n 1
2n-
2n < 2n-1 which gives
[[> - -2n 1)ll f=)]l < 2n. Putting two cases together, we get
| f(x)l2 < 2n + (2n f(x))
that is equivalent to (2n, 2n - 1) smoothnesss (Chen et al., 2023, Theorem 1). Non-smoothness of for n > 1 follows from the unboundedncss of 2 (x) in this case.
Example B.2 (Exponent of the Inner Product). Function (xx = exp(a Tx) for some a E Rd is convex, (0, -mmothh, but not T-smooth for any 2 O.
Proof. Let us compute the gradient and Hessian of f:
()(x) exp(a x), V²f(x) aa exp(a TT).. x:).
Clearly V f2)( > meaning that fxx is convex. Moreover,
f=) = ||a] exp(a" T x) |al]| IVf(')]
that is equivalent to (0, |aaaaallmooohhess (Chen et al., 2023, Theorem 1). When a o function f has unbounded Hessian, i.e., f is not I-smmooh for any T. > 0 in this case.
I
Example B.3 (Logistic Function). Consider logistic function: f(x) = log + exp(-a aaaa))))))))))))>))))) x)). where E [gd is some vector. Function f is (Lo, Li)-shoth with Lo = 0 and L ||a]].
Proof. The gradient and the Hessian of f(x) equal
aa T
Vf(x) = 1 exx((aaT
a
V f2)(x)= =
(oxp (- 3a Ta) + exp x)
18

---

Published as a conference paper at ICLR 2025
Moreover,
|all
||a12
[f(=)]
[<))2== =
1 exp(aTx))
(exp (- a- T x)) + exp (2xTx)) xx))
This leads to
[2 [()]] [V(i)||
1 exp(a x))
(exp (- 3 T x) + exp (Ha T x)) ||l||
+ exp(a x))
exp (-a x)) (1 exp x)) ? |al
1 exp( -a x) ||l| < |||||
implying that / [())]| ||a||-II//I [[]]] for all R. This condition is equivalent to (0, ||a]])-
smoothness (Chen et al., 2023, Theorem 1).
19

---

Published as a conference paper at ICLR 2025
C PROOF OF LEMMA 2.2
Lemma C.1 (Lemma 2.2). Let Assumption hold and u satisfy² V= E.V. Then, the following statements hold.
1. For f. == inf zeR f(x), arbitrary R., and such that v exp(u) we have
v Vf(x)]?
2(Lo + L1 Vf(+)]] f(x))- fx.
(31)
2. If additionally Assumption 1 with μ 0 holds, then for any x. y Rd such that
| l/l exp (Ta1l30 yll) < 1,
(32)
we have
[IVf(=)-Vf(()) { - x))
(33)
+ [[ll((()
and
/ - (VV
- v). (34)
2(L0 + 1 (( 2(4 + L, Vf(=)])
Proof. To prove (31), we apply (7) with y = x Lo+hi [[f( fx() for given x e Rd and v such that v vexp(u)= = 1:
2 =
Lo L1 Vf(x)]
f. f(y)
+(x)+ (Vf())) x)
exp(L1 ||2 =|)|[> y/1²
((1) Lo + L V[(II
o7 + 1, V
(Lo + (=)))
exp
2
Lo + 1 LIllf(())1)
f(x) Lo + L L f=))
2(Lo + L, [ (exp(1)
f(x) 2(Lo + (=)))
Rearranging the terms, get (31).
Next, we will prove (33) and (34) under Assumptions and The proof follows similar steps to the one that holds for standard L-smoothness (i.e., cocoercivity of the gradient) (Nesterov, 2018):
f=() ((i=)-ff((il ff < L(V)(x) vf(v), 9).
That is. for given consider function (v) f(y) fz), y). This function is differentiable and (ya(y) Vf(y) - Vf Moreover, for any u, E Rdd we have
- Vp)) = -V)))- < (Lo + L (v)(I)) -u-vll exp(Lillu =ll). (35)
Next, for given and for any y. u E Rd we define function V. (t) R + IR as v. pp (u + (yy u)). Then, by definition of thagga we have (u( = Vayaa (0), (p(()) (z.g,(())
*One check numerically that 0.56 < 0.57.
20

---

Published as a conference paper at ICLR 2025
and (t) (Vixx t(y -u)) y u). Therefore, using Newton-Leibniz formula, we derive (x)()) - (u(( = (1) - (0) = V Nu (t)dt
[ (Vpx(u f1y u)), y u)dt
= (Vpa(u), - u) + (V + t(y u)) Vpo(u).y -u)dt
u., < (Vpa(u),) - u) +
1Vpp t(y u)) - vp>(u)]l 1|u - ylldt
(3)
(Vpo()),y-u) y u) + / (Lo - V exp(tL w1l v v1l2tdt
Lo + In [/('I]
(V)r()), - u) +
exp(LIllu - y b|) - v/l
2
that implies Vu, y E IRd
Lo + 41 11 f(w)l exp(Li || =lDI|u (11ill/-// yll
(y) < p2())) + (Vx u) u)+
(36)
2
To proceed, we will need the following inequality:
L1 [
L V f - V
eexp Lo +Lo+L111 L[
vexp
Lo + [f]i
Ln Li u|l exp u + L(IV)(
ul]
vexp
40 41 V[(wai
vexp(uI1lle exp( L1 [x]
vexp(v) "==" 1.
(37)
Using the above bound and (36) with y = u LotLiiN/(O) Vpr(u). we derive
11 Lo + LI Ver(())
v
8x
(6)
(u))(())
v² V [1]
L1 V "To + In [
(w) "To Ln [/(")]
2(Lo + L, V [())l])
exp
(37)
VV (1)
v/ V pm. [1
Lo (u) LLo + L, [
2(Lo + 41 V f()))
(w)
(v) 2(Lo + L (/(IIl))
Taking into account that an optimum for (u) (Ve,, (x:) = 0) and the definition of yo (u), we get the following inequality from the above one:
f(x) - (Vf(z), & f(u) (VF(x),
Vx, Rd
2(Lo + [[))(())
which is equivalent
" / - 2
f(x) - (VS(,, x), Va, E Rd. 2(L + (()iI & f
Therefore, we established (33). Moreover, by swapping x and in the above inequality, we also get
f v f(y)l2
-V/w),,=---- v), Va, E Rd. 2(Ln + Li ( < <((x)
To get (34), it remains to sum the above two inequalities.
21

---

Published as a conference paper at ICLR 2025
D MISSING PROOFS FOR (Lo, LI)-GD
Lemma D.1 (Lemma 3.1: monotonicity of function value). Let Assumption 3 hold. Then, for all E the iterates generated by (Lo, GDD with 1) & v, V = satisfy
/| 2 L1 [[(+)]]] {(x)).
[x $ {(x))
(38)
Proof. Applying (7) with y = xh+ and x = x and using
L LI
exp(L1|1> 2²11) = exp 1 To + L V
< (ep(n)
(39)
we get
f(x*) + (Vf(2*)) k+1 =t) + O7 + L, V f(x*) ||| 7/
f(xht1)
<
|| - x
2
112
2 cxp(n) V fxx*)) )12
f(x²) Lo + L1 f((t))]]
2(Lo + TT V (xx+ II)
f(x²) ((=9)-1 -
mesplm
2
Lo + Li V
nsy
eexplv)
Vf(x")11
[(xt)
2
n| V fxx 1
"E f(at)
2(Lo Li | V/ < f(*)),
which finishes the proof.
Lemma D.2 (Lemma 3.2: monotonicity of gradient norm). Let Assumptions with μ and hold. Then, for all & > 0 the iterates generated by (Lo, GDD with n & v, v = e satisfy
[V *+])|||||| < [v)()')
(40)
Proof. For convenience, we introduce the following notation: wi = Lo + I, [xx))) for all k > 0. Since
nL [Vf
1L 7L !ل
L1l|zh+1 exxp (L1 b+1 - =*11) Lo + L | exp
Lo + Li V[(
nexp(1) pexp(v)
"=="" 1,
the assumptions for the second part of Lemma 2.2 are satisfied for = ++1 and = x², and inequality (11) implies
V
< (Vf(xtt)) vf(x*) (,tt),,,++))) _
+
2wik
2wk+
" (V
V)(+))).
where in the second line we use k++ rearranging the terms, get
x
Vf(tt). Multiplying both sides by 20//u and
wx
(1 (
Wik wK+1/
- ).f((()
2n (V/( v((})) + 2n / [|V[(>*)]
22

---

Published as a conference paper at ICLR 2025
which is equivalent to
(1+ Wk wk+1
[V
&
1
wik
11 (x*)))
wk+1
+2
+
/
?
(Vi(zht)) Vs((tt)) (
Wk+1
2) ||
-2
Wk+11
wik
|[V{(=*)11
wh+1
+
wk
2
-V(=)),)))())),,, Vs(x*))
V((a))
Wk+11
(1
wkk
[|Vf(=*)]1
(41)
Wk+1
2o0k
Wk
- 2) (Vf(x 7f(a*), x²).
1
7
Wk+1
We notice that 20h > 0 and + Wk
11
We
7 0 since ! < 1. Moreover, due to the xkt1 - xn) 0. Therefore, have
we+1
V
wh+1
convexity of f we also have (V (a((t))))
V
{((*))
2ook
[+
Wke
-
2
x²) $0.
"
WK+1
Together with (41), the above inequality implies
1
Wis
[V < (1+
Wk w Wh+T
||
4k 0,
Wk+1
which is equivalent to (40).
Theorem D.1 (Theorem 3.1). Let Assumptions with p= 0 and 3 hold. Then, the iterates generated by (Lo, LD) with n & 5. v e- satisfy the following implication:
[V)(=*)||
Lo
k <
8L71|00 - =11
and || - =²11 & 1| - -x"12
Vn
(42)
L
mM
8L7
81711=0=0111
Moreover, the output after N >
iterations satisfies
f(aN) f(x") 2L 20 - =2"112
LoT
2L 1/2 1=
(43)
(NN +1 -7)
4N + +1-T)
(N + +1)
where T = | the set T = (k E 1......N - ||[]((**]] > 2 ). In addition, if
and N: 81.71120 1, then
| x= 101 (1
pn
N-T
|1 -200=111'-
101
VnT
pml
N-T
(44)
4Lo
8L?
4Lo
Remark D.I. In the strongly convex case, our convergence bound implies that (I.g, I-)-
GD with πl u/2 satisfies || 112 & E after N O (max { Lo log() L3 R2)) 1 iterations, while the complexity of Glip-GD derived by Koloskova et al. (2023) is O (max/ { Io tort (ertt//=/// Ro min T/ LRO))) our bound due the dependence on T.
})). which again can be arbitrarity worse than
23

---

Published as a conference paper at ICLR 2025
Proof of Theorem D.I. We start by expanding the squared distance the solution:
| - x²12
x x²"
La + L1 V [(x)))]] vs(++))
7
2n
|a x² 1122
Lo + ي1 L (x -x" vf((z)))
n V fx**))) 112
(Lo + Li| V (x 1))
2n
x²11" 112 Lo + L V [(++|||| (f(x*) s(x)))
1 ff
(Lo L1l ff
11 x² x²112 1 2n (1 )
f(x²) - f(x²)
Lo + Ln [((*)))
f(x²) f(x*)
| 1 x²11 1 Lo L [+(*)|
(45)
To continue the derivation, we consider two possible cases:
[vf(=*] > LA or [Vf(2*)] < t.
Case 1: |V
this case, we have
Lo L, (V 22,,
(46)
[+(*))l (46)
& {(at) -(xx)
(47)
4ha
2(L + L [((*)|
Plugging the above incqualities in (45), we continue the derivation as follows:
11 x²1
(4))
|| x=112 11 2L, -11 [[[[(()
f(x²) f(x²)
1 x²112- vn
(48)
8L7
We notice that if [ [x+)
La then, view of Lemma 3.2, we also have |V/('')| b,
bn for all
t 0, 1, 1....,A, k. Therefore, (48) implies
|
1²1 1
1²11
[T] SL}
(k: + 1).
(49)
Since ||æ - 1² > 0, & should be bounded as k <
|1, -
1, which gives (14), We
vn
denote T' := [T] for the set T := {k E (0, L.... - 1} |V
)]|
>
Li Therefore, in view of
La
(49) and non-negativity of the squared distance, T' is bounded as T < Case 2: [V La. this case, we have
8L2 -
09
Lo + L. L+IV & 2Lo.
(50)
implying that
1+ 11
(45). <
I1a
- x x2
17
(f(**)- - f(x"))
(51)
2LD
Moreover, since the norm of the gradient is non-increasing along the trajectory of (Lo, LD) La (Lemma 3.2), [[V](=*)]| < ta implies that k T. Therefore, sum up inequalities (51) for
24

---

Published as a conference paper at ICLR 2025
k = T,T + 1, N, rearrange the terms, and get
N
1
20
Σ ( ((x)))
(1 -
1x11 =x
|1 x² x²))
N+ T
n(N +
T)
k=T
20 (11x7 ===11 k=T
-111: x² 112))
7TN +1-
2Lol1>" x²
7TN - -T)
Finally, we take into account that for k 0, 0,1...., T - 1, we have |[[{'*]] > t::
N Σ (((x)))((x))) K=
(49)
2Lo 2 - x1
LooT
-
(52)
N N+1-T
n(N +1- A +1-
remains to notice that Lemma 3.1 implies f(x²) - f(x*) & N Ex-++ (f(xt) f( ))
Together with the above inequality, it implies the first part (15). To derive the second part of (15),
remains to notice that for N > 8Li ="=1""--11 1 the right-hand side of (52) as a function of T attains
on its maximum at T = O. Indeed, the derivative of function
(T( = 20 - x=11
VLoT AN + 11-T) T)
(NN + 1 - T)
2Lal 2000 - 112
VLa
vLo(N +
(N + +1- -T)
4L3 -
equals
2Lo 20 - 10
(No + 1)
(((T)
(N TT + 1)2
4LŞ(N +
-1,11=0-2'1" 17
Since N
1, we have xp (T) 0, i.e. (T) is decreasing function of T, meaning
that
2L = 11 (N -1 AL +1-7)
vLoT
2L x x1
(N + +1)
which gives (43).
To prove (44), we notice that for μ > 0 we have f(x²t) - -((x*) ((x))) > 41 - xz implying
|| - -2112 < 1
(51)
lln)
100 - xx
(53)
4Lv
when [f(*')] <
La T.
Therefore, for N T we have
N-T
N 112
(53)
pm
11 -
4Lo
(49)
pm
N-T
11 -x012
VTI
4Lo
8L3
N-T
pm
1| -x"11" 11?
4Lo
which gives (44) and concludes the proof.
D. COMPARISON WITH THE PROOFS FROM (KOLOSKOVA ET AL., 2023; TAKEZAWA ET AL., 2024; CHEN ET AL., 2023)
Comparison with (Koluskova et al., 2023; Takezawa et al., 2024). In this paragraph, we further elaborate on the difference between our proof and the ones given by (Koloskova et al., 2023; Takezawa
25

---

Published as a conference paper at ICLR 2025
al., 2024). As explain in the main text, our proof follows the one from (Koloskova et al., 2023; Takezawa et al., 2024), which follows the analysis of standard GD. Then, similarly to (Koloskova et al., 2023), consider two possible situations: either V fx second case, the gradient is small, and -tteem in Lo. Ln ssmoothnssss is dominated by Ln-term, i.e., in inequality (8), the denominator of the left-hand side is (TTp). In this case, the method behaves as standard GD for L-smooth problems with L = (Lo). However, when [VV > Lo/Ln L,, the Li-term in (Lo, ssmoshhttsssss is the leading one and this is the crucial difference between our proof and the one obtained by Koloskova et al. (2023): to handle this case, use (8) and show that such situations lead the decrease of || 1²2 by some positive constant (T/(81]). In contrast, explained our first response. Moreover, Lemma 3.2 shows that the gradient norm is non-increasing along the trajectory of the method similar to standard GD (e.g., see Lemma C.3 from (Gorbunov et al., 2022)).
Lo/L, or [[*((*) < Lo/L, In the
Koloskova et al. (2023) use traditional smoothness, which leads to worse complexity,
Comparison with (Chen et al., 2023). Although Chen al. (2023) analyze 3-Normalized GD without assuming convexity, their results can be used to derive convergence bounds in the convex case as well. In particular, from convexity, have
-(**)-((** f(x*) < (Vf(z"), x²) IVf(**)
I|
1| x/
Although the proof from Chen et al. (2023) does give bound for ||ac x= ||, one assume for simplicity that it is bounded by D > (c.g.. we derive the boundedness of || xx || for (Lo, L1) in (45)). Then, using the bound for 2/4 Σ k= [V+((*)]|
from (Chen al., 2023, Theorem 2), we get
N-1 N
2T. 2L D(F(a) - f(x))) + 2
DE
- - f(x)))
Ne
k=0
where 0. In the original paper. E is the target accuracy. However, one can optimize in the above bound and get Eopt = 2
La(s(xo)- f(=))) and
N
- s(x)) & AD AD N
1
N
Lo(s(x)) ADVLo(J(>*) - ((*)))
k=
The above rate is v -wose than the leading term in the results we obtained for (Lo, I-)-GD This This fact illustrate non-triviality of the extension of the known results from non-convex case to the convex case with the right dependence on N.
26

---

Published as a conference paper at ICLR 2025
E MISSING PROOFS FOR GRADIENT DESCENT WITH POLYAK STEPSIZES
Theorem E.1 (Theorem 4.1), Let Assumptions with O and 3 hold. Then, the iterates generated by GD-PS satisfy the following implication:
Lo
2²
||
-x1112 & 11 - x²11²-
(54)
L1
1627
Moreover, the output after N steps the iterates satisfy
4La ||0 NoxN+11 x =1
Σ (f(x*) [(x))) & 4La |200 xx112
VLoT
(55)
41.3
NE(U.1....NAAT
where T = {1: E (0.
NY | IIV
>
L1 }. P == IT, and if N > T - 1, it holds that
La
5(*N) - f(x*)= & 4Tol| - x²11
vlnT
(56)
v(N T + +)
AN T 1)
where &N E {x0 ,0!, :.... .......,]]] is such that f(ØN) 1= N (xx). In particular, for N 164, =1'1?
inequality N T 1 guaranteed and
1(* - -(x)) < 4Lol|z - xx1
(57)
v(N 11
161.11=0-2"11 -1, then
In addition, if p > 0 and N
1| N x²112 < (1 (1- pvv
N-T
2T 1677
N-T
|1 -120-2011
x²11
<
1
- (58)
-
8Lo
SLo
Proof. As for (Lo, L1) GD, start by expanding the squared distance to the solution:
f(**) - f(x') Vf(at)
11a 2²11
x
[[+)(2))11
2 (f(xt) -(fa==)f((())) -x()))
(f(x*) )(x)))
1100
x² 11
fot -x", xx, (((x))))))
[x*)(
[V[[{
(J(xt) - f(x"))
||
1=1
[VV[(*+)]1
f(x²) f(x²)
110 x² 112 2 Lo + L. [
(59)
To continue the derivation, consider two possible cases: | f+ م [V}('*>|
+.
Case 1: [[V > La. In this case, inequalitics (46) and (47) hold and the derivation from (59)
can be continued as follows:
(49).44)
[(x²) f(x*)
k 11
|| 101
2L (f(()
(47)
v²
||* x²1
(60)
16T
which gives (54).
Case 2: [V)(z*)]
L. In this case, inequality (50) holds and we have
(59),500
v fx* f(x*)
| 1²1
||,
x0112-
(61)
2
2Lu
27

---

Published as a conference paper at ICLR 2025
Next, we introduce the set of indices T {k+ (0.1,...,NN f > Lo
L, of size T = T
In view of the above derivations, if k: T. inequality (60) holds, and if E 1., .N) T. inequality (61) is satisfied. Therefore, unrolling the pair of inequalities (60) and (61), we get
U²T
<
||000
x²1
V
Σ
(f(=*)- - f(x*))
16L7
4Lo
which is equivalent to (55). Therefore, N 1, set 10,1,..., NJ \ T is non-empty and the above inequality implies
1,t
{(a - f(x))
<
Σ
((a0))((00)
N - +1
kEf0.1.....J1
4L ALolI>0 - x1
VLoT
v(N - - + + ALŞ(N -T+
where a. {x",x²,,.. ΦN is such that f(*N) min att ...,,, f(x). 161 1| xx"=""==""""
Moreover, Therefore, for
since the left-hand side of (55) non-negative, we have T < N 1613
inequality N T 1 guaranteed as well (56). Finally, to derive (57), we consider the right-hand side of (56) function of T:
(T)) = 4Lo| 10 x² 1²2
VLoT
(N - T + 1)
4L7(N - T
4Lol|æ0 1=1
vLa
vLo(N +1) -T+1
"NV T + 1)
4L7
The derivative of this function equals
4Lo 11 - x1
vLo(N +
('TT)
v(N T + +1)²
ALŞ(N T 1)2
Since N 162i1l=--r II? 1, we have x ((()) < i.e. sp(T) is decreasing function of Therefore,
since T > 0, we have that
4Lal| - x11
vLoT
4L |Lol - x011 v(N +1)
((T) E ((0)
v(N - T - ALŞ(N +
Combining the above inequality with (56), we obtain (57).
To prove (58), we notice that for μ > 0 we have ((ak)-s((e)) ((+)² > $1 x² implying v.v
| - (61)
(1
10 - x11
(62)
8Ta
La when [V(('>)]| < L.
Unrolling the pair of inequalities (60) and (62), we get for N > T
|| - 1112 & (1
N-T
4
1
1=12-
8L
16L7
8Lo
KET
where tę is the cardinality of {k + 1,..., N] T. Since |T| = we have that t4 < N T for all k E T. Therefore, can continue the derivation follows:
N-T
2TT
|| N 2011
1100 - x11
8L0
1677
N-T
Wv
1
x²1
8Lo
which gives (58) and concludes the proof.
28

---

Published as a conference paper at ICLR 2025
F MISSING PROOFS FOR (Lo, - TRIANGLES METHOD
Lemma F.1 (Lemma E.1 from (Gorbunov et al., 2020)), Let sequences {ax k20 and {Ak) be defined as follows:
77(k +0++) 2)
ag A =
0k+1
AR+1 As agt1s
Vk 3 0.
2
Then, for all k 3 0
nk + 1) + 44)
Ak+1
(63)
4
a1+1
As+1
(64)
Lemma F.2 (Lemma 5.1). Let f satisfy Assumptions with μi = 0 and 3. Then, the iterates generated
by (Lo, LTM-STM with 0 n 2, e- satisfy for all N > 0
GN R
Gi 2
Gk+1
Gk R
- f(x*)) + AN )
R
+
(65)
2
k=1
N
V [
[z(x(+1)1
(66)
AG
where Rs = 1| - x² for all >
Proof. The proof follows the one of Lemma F.4 from (Gorbunov al., 2020). From the update rule, we have ck+1 zk
0641
V (1* and
TL+t
a++1 (V( 2t x²)
a++l f((x*=1),) 2,,2
2411 -
( 2k1 x²) akt1
[f((x- 1, 2 -2 Cxt1 (2++1 2/ x² 2 xt1
ak+1
ax+1 AA++(Vf((e ff( k- ), - 21 Gx+1 || - 1
2
Gk+1 b/ x²112
Gk-1
|| k-1 - x x111
2
2
The update rules for gh and k+1 imply
A )(t1) ax 1 - =
(67)
Moreover, to proceed, we will need the following upper-bound:
L Li0841
|| - 211
exp (Ta 11
exp
ARt1
ak+1 Li V V f(a
0 O
exp
A + L1 V (z(++1)]|
$
exp
A
(64)
va & exp(v) v=
exp(1)
(68)
29

---

Published as a conference paper at ICLR 2025
Using these formulas, continue the derivation follows:
1,, - Gk+1 - 1
01+1 (V -x²)
Ak+1 (V 2+1
2
Gk+1 || - -x"11- Gk+1
11 | - x²11
2
2
A&+1 (f(xht)) - -((
Ak+1GH+1 exp (In || - yl+
1 | 4 1p?
Gk+1 1| - +
Gk+1 1|
x=1 x2112
2
Gk+1 || - xx²11
2
(67)
Gk+1
vak+1
- Ak+1 (f(xht1)- -5(
11 11
2
A
Gk+1 || 1 +
Gk+1
|| - x=1
2
2
Gk+1 || - x1"
2
Ak+1 (f(x - -((1
Gk+1 /00 -1 11a4 - 2
2
Ak+1
Gk+1
11 - -x²112 ---12--0000 Gk+1 || - x²11
2
2
(6))
Ak+1 ( -((xht2)) Gx+1 || =
Gk+1
1| =x"112
Gk+1 ||
|| x²1
(69)
2
2
Next, using the definition of ++1 and A&+1 = Av + 01+11 we get
a - -x )+ = Auly² - x-11)
(70)
Combining the established inequalities, we obtain
ax++1 (V (Vx(x+))) 1 x²)
a4t1 (Vfatt)()t))) x - 2t)
st - x²))
(79)
A -ttt1)
+ (f(x -((x)t1)) Gk+1 11 1 22111
4
Gk+1 11 - =1 GG+t1 _G || - -x" x²1
2
2
A (s(1²) [(akt1] + Act1 (f(xht1) - ((1)t2))
Gk+1 1| 1 + Gk+1 || - x21
2
Gk+1 || 12 =11
2
30

---

Published as a conference paper at ICLR 2025
which can be rewritten
A&+ A
-b)(()) < ak+1 (f(x+t1) ((V -x(tl1)
Gk+1 1|2 x1²112
Gk+1
1| gbt x²112
[f(x
2
2
4Gx+1
(x+1)(x"))
Gk+1 11 x² x²112
Gk+1
||
1+1 - x²11
ax+l
[f
2
2
4G
Summing up the above inequality for k = 0, ,,...., Av, and new notation Rg
N - 1 and using Ag ag = 0, Σ
k==
N-1
0k++1
== 1|2 x= ||. we derive
N-1
AN f(x))) +
GN R
&
G
R 2
Gk+1
Gk R
Σ
a+tl
2
2
4Gk+1
which finishes the proof.
Theorem F.1 (Theorem 5.1). Let f satisfy Assumptions 1 with 0 and 3. Then, the iterates generated by (Lo, -TM with 0 < n & V v = e_ G1 Lo Lo + L fx(l)(())) and
G max (Gx. Lo + Ln / I]): k => 0,
(71)
satisfy
2Lo(1 + 11112 - x exp 11|1=
1)) ==
) - f(x")= <
(72)
(NN +3)
Proof. Let us prove by induction that Rs < Rg for all k > O. For k = 0, the statement is trivial. Next, assume that the statement holds for k = N and derive that it also holds for k = N 1. Indeed, from Lemma 5.1 we have
GN+1 RN41
GN+1 R2y11
<
AN+1 - +
2
(2))
G1
Gk+1
Gh
Rg
R
2
2
k=
G
N
Gk+1 - -Gk
GN+1
R
Ry
R
(73)
2
2
2
implying that RN+1 & Ro- That is, we proved that Rs < Ro for all k > 0, i.e. the sequence
J220 stays in BRo (x*) := fo E Fd |>=->"|| Ro}. Since xd = 8d 20 x++ is convex combination of y and zt, x²1 is a convex combination of y and *+1 we also have that sequences Ju20 and {v² Ja20 stay in Bx,)),), which can be formally shown using an induction argument.
Therefore, we can upper-bound Gş for all le > O as follows
(6) & Lo + LiLo max exp(Lilla' x" "DII'""' x"1l
G Lo + L1 max
[V
D....
< Lo (1 Ry exp( Ro)).
(74)
Moreover, from (73) we also have
G Rg (74)66) 2L + In Ro exp L1 Ro)
-
2AN
nN(N +3)
which finishes the proof.
31

---

Published as a conference paper at ICLR 2025
G MISSING PROOFS FOR ADAPTIVE GRADIENT DESCENT
G.1 DERIVATION OF (25)
The key lemma about the convergence of AdGD holds for any convex function regardless of the smoothness properties.
Lemma G.1 (Lemma from Malitsky & Mishchenko (2020)). Let Assumption with μ = 0 hold, and x be any minimizer of f. Then, the iterates generated by Algorithm 4 with satisfy
| - x² x²11²+ + | k+l - 20113
+ 21x(1+ -
1 x²112 + 2 || -
x1-1112 +2 f(x")). (75)
In particular, the above lemma implies boundedness of || - =2'l and 1| 1 which allows us get the upper bound on the gradient norm (24) and lower bound for 2 as stated in the paragraph before (25). For completeness, we provide a detailed statement of the result and its proof below.
Theorem G.1. Let Assumptions I with μ = and 3 hold. For all N 2 1 we define point &N ==
SN (AN(1 + ON) + Em=n wrat), where w2 =- A (1 0x) A SN x1 + Ek=1 Ak-
and {-th Juzo are the iterates produced by AdGD with 7 = 1/2. Then, aN satisfies
S(aN) f(x)) < Lo(1 + L, exp (I, D)) exp (V2L
(76)
N
where > 0 and D2 = || x= 1|? | (f))) f(x)))
Proof. The proof follows almost the same lines as the proof from (Malitsky & Mishchenko, 2020). Telescoping inequality (75). we get
1
|| x²1 + 11
11 + 27x +1)+())0((++)))))))) f(x)))
2
+2
[1 + 0.) - - (f(=)
| - -x012 2X00 (77)
Since X1(1 + 0:) - Ai+10 > 0 by definition of A; we conclude that the term in the second line of the above inequality neg-negative. Therefore, for any h: > we have
x0 112 k 1112
D2
(78)
||
2D2
(79)
Using Jensen's 's inequality in (77), we derive
D
S - f(xx)) &
2
where
*b AR + 0x.aa - wart
(80)
Sk
= A,11 a(1+0;) - 11t1,
(81)
k
Sk = 111y + Σ A
(82)
1=1
Thus, we have
2
5(8/) f. 25k
(83)
32

---

Published as a conference paper at ICLR 2025
Next, we notice that for any lo > 1
11 - x ---
[V](**) V V
(Lo L1 L1|V/[(++]]]]] exp(( 1 -1-
(24)
>
Lo(1 + L, L (xsp(22211)
Since 0o- +00, we have A1 1 -V
- [ Moreover, for k > 1 have either d 2 Ak-1
1 |
or A
Therefore, by induction we can prove that
1
X 2Lo(1 + D)Dex((L))) exp( 2)
(84)
that implies
Sk
11Yk Σ A
2Lo(1 + L, expp (22,
Therefore, we have
D2
Lo(1 + Dxp (x, (L) exp (V
-(tt) <
2 <
k
which is equivalent to (76) when k N.
G.2 PROOF OF THEOREM 6.1
To show an improved result, we consider Algorithm 4 with 7 ]/2 and refine Lemma G.1 as follows. Lemma G.2. Let Assumption with 0 hold, and x² be any minimizer of f. Then, the iterates generated by Algorithmm with y 1/ satisfy for all k >
|1 - -11112 + |1 - 111 21a(1 + -x) f(x²)) +
| lx - 1211
1 < 11 - x111 +
4 1 - 112 2Ne0x f(x)))
| r²112. (85)
Proof. The proof is almost identical to the one from (Malitsky & Mishchenko, 2020) and starts as the standard proof for GD:
++
1
1 x² #+ x x -x") + || 2/1
|| x² x²1 + 2 (Vf(x"), x- -x*) ) + ||a - 1111..
(2)
1100 - x x21 (x=(((=") - f(x*)) ))- + || 112
<
Introducing Σt+1 Ex=u
|| x11 rewrite the above inequality
| - 2²112 112++00 + Ma41
<
||o x (fx - -((((((()((())))))))))))())))))) + || k+1 - x1112
1 +E+ + マ Ila x* 112
(86)
Next, we transform ||, - x similarly to the original proof:
++ 2t112 2| 1011 ||, xx 112
-2ee(V x k+1 x0)) || x*112
2(c(V - Vs(x - xtt11
+2 (vx -x11) 1lobbt1 1..11
(87)
33

---

Published as a conference paper at ICLR 2025
Next, we apply Cauchy- -cchwarz inequality, the definition of d with y 3. and Young's ' inequality to estimate the first inner- mnner-prouuct in the right-hand side:
2 (V (s(x"=)),,>>) x t
< 2hx (x.IVV((**) ( x 1
< 1 - 3¹ 111e** - xktll1
1 - 112 + illattt 1x1/
(88)
Then, using the convexity of f. we handle the second inner product from the right-hand side (87):
2dx
2A (V
), x²
xb = Ak-1
(x
,²,x* xt sht1)
= =21x0h (a (a . V.((x'))
& 22 (f(xx - -((x*)).
(89)
Plugging (88) and (89) in (87), we get
1 | Id 112 $ || 1/11 + 2x (f(ht\))))))))))))()) s(x²)).
3
||r - 11
Finally, using the above upper bound for || - x* 112 in (86), we obtain
|| - 1=2 + Ex+1
$ 1|* - x0112 1 (fxx -((x))
1
3
1 11 -0"-11²
| 121 111++N0((((E+ -((*))
4
+Ex +
b110011 - 1²11
2
11 - x²11 + 7 g1a0 - 1² 111 - f(())) + Ex
1 | 2 22x -f0((()))((())))
Rearranging the terms, we derive (85).
The above lemma implies not only the boundedness of the iterates but also the boundedness of EtDo ||x't] - 122 for k > 1.
Corollary 1. Let Assumption 1 with p= 0 hold, and x² be any minimizer of f. Then, the iterates generated by Algorithm with 7 1 satisfy for all k >
11a - x11 & D)? |2 - -1²11 2 < 4D2
(90)
(91)
|| 1212 & 2D2
(92)
0=
where > 0 and D : ||,| x= 112 + 1| 02 + (2x)( - f(x)))
Using the above results, we derive the following theorem.
Theorem G.2 (Theorem 6.1). Let Assumptions with μ = and hold. For all N > we -
define point iN
(AN(1 0N) + waah). where we Xx(1 + 0k) > 0++10k+1 SN = A10, + En' AE, and {ar) Jazo are the iterates produced by AdGD with 7 = 1/4. Then, for N > mK- (2N(m-1))n) iterate &. satisfies
D2
f(aN) f(x')( <
(93)
v(N mK) V2N(m + D)L,D*
34

---

Published as a conference paper at ICLR 2025
where D > and D²
|xl x=1
1 2 =012 + 2>101(f(=)) - f(xx)),
1 1og.2 (1+1) D expp12L, (2L, D)!
K 22.00² and E.. In particular, for N >
(Zmk + ) we have
1(*N) f(x)) < 4LoD²
(94)
vN
Proof. Using Lemma 2.1, we obtain
|V \ < 1a - 111 (Lo + L1 [[((a)]]] exp (11 x4-111) (95)
Moreover, since" 0g- +o0, we have A1 4/I [1| V
11 -
Next, for h > we have either A = /1 1 or d ](v Viii +)]l For con- venience of the analysis of these options, let K. be the set of indices h 1 such that 11xh 1 1-
A = =V+++ 0 and AR-1 4]V \/ 2)
Option 1: 0 = V + 1 Then, by definition of K. there exists 7 > 1 and index such that I 1}. and - (|- i.e., & belongs some sub-sequence of indices such that Option 1 holds. Following exactly the same steps as in the derivation of (84), we conclude that
L A V1+ 01-1 for all / E (1,4+1,.... ++ 1). k E
AL+T 1 -n -
21g 2 exp D) + DL, exp exp DJ) Ami
for any le 3 1. Since 0/ > for all 1 E
t+r - 1), we get that A 3 22
2 -1 for E {t + l......t + + - 1), meaning that for - larger than + log ILodAni
1 log exp (L, D) exp (L, together, we conclude that
=: m we have X > Th where v = e Putting all
A-11,
for E {t, t + 1....................... t m]. for forlE E (t + m + 1,t + m + 2, - 1}.
A
>>
(96)
v T7m
|| |
Option 2: A
Then, using (95), we get exp (- L1 1 x -
(
11rk -
exp (-L2 1| x
A ([
vf(x+-1)]
Lo L vf(x*))
4(>xLo + Ln k.4 x 1)
implying that
d exp L1 - - 111
L1
| =
(97)
4ho
4ho
To continue the proof, we split the set of indices {,, . N3 into three disjoint I A - 1
sets Tı, T2, Ta defined as follows: To {K (KE (1,
Ti = {ke (1,2....,A (1,2,.... 22...,, NN (Ti T2). Then, taking into account the lower bounds (96) and (97), we have
d = VI+ and Et E such that & l < m) Ta ==
Ak E (1. N}
d exp
if k E Ti, where 1 E KC and 0 & k - L < m,
11 k-1
L1 Iho
|
11.
k E Tz.
1ha
if & Ta.
4he
exp
(- Li -1 21-211)
|| -²--111 ||:
if k E Tı, where i K. and 0 < k $ m,
(-1872.097) 2
16o
4ho
exp
1| x-
k+1
11
if k: E Tz,
4ha
aLn
P 1Lp
k E Ty.
1 1 -
In practice 0, it is sufficient to take 0g >
1.
16
35

---

Published as a conference paper at ICLR 2025
Also the number of steps when L1 L1|10* x > holds is bounded by
= D D2
N
since Σ ||abt| - r411 & 2D2. For convenience, we introduce new set of indices M
k=
[1e
L 1|
s - 11 E v)- Then, for & E M we have
exp (-L1||=* x k - > exp(-v) =v v.
(98)
Therefore, we can lower bound the sum of stepsizes as follows:
exp (1 ||
exp (- L1 || x x
A
Σ
4L0
4L0
k=1
kETi.EK K,ck
mm
kE
L
mL1
Σ kETs
|| --+1-=x+ -x0'l x''l
4Lo
4Lo
4Ta0
kETz
1ET2:+IEK
exp - 1i1 1|,0" - x²--11)
exp ( T1 11
x x-1-11))
Σ
4Lu
4Lu
KET METK,,,EER,
RETaNM
(m+ (m11)L1
Σ
Σ
1 x*1
4L0
4L0
KE
bETa
(9)
v(N mK)
(m + 1)L1
| - 211
4Le
4Lo
k==
v(N mK)
(m + 1)L1
N
W
N
| - 10
4L
4Lo
A=0
v(N - mK)
22N(m= + D)
(99)
4T.
4T.0
Since SN > Σm=1 A (see the definition (82)) we have from (83) and the above lower bound on
EN d that
1
(99)
D0
f(a~) - f(x*) <
(100)
2S
v(N mK) V2N (m + 1)LID
In particular, we derived (93) under Assumption 3 holds, and when N (2mK + 4(m + D
we have v(N -mm) /2N(mm + 1)L, >
nN 2 which in combination with (100) implies (94).
G.3 CONVERGENCE STRONGLY CONVEX CASE
To show an improved result in the strongly convex case (μ > 0 in Assumptions 1), we consider Algorithm with more more conservative stepsize selection rule:
30k-1
| k
A = min
(101)
4
[f(**) v vf(x+
For these stepsizes, Lemma G.2 holds as well. However, in contrast to the convex case, we will use Assumption 2 instead of Assumption 3. The key reason for this is that need to (10) for x² and = x that not necessarily satisfy (9). In contrast, inequality (10) holds for any x, y E Rd under the Assumption 2 and convexity.
36

---

Published as a conference paper at ICLR 2025
Theorem G.3. Let Assumptions I with μ >> 0 and 2 hold. For all N 2 1 we define the Lyapunov function
VE )1
AuH
841 1 - x011++ ( ++ -a)
Ta)
| - 11-
To
where {a*) Jaz0 are the iterutes produced by AdGD with 2 defined (101), and ex 0.98. Then, for N > V2N(m + 1)L1 D Lyapunov function V N++1 satisfies
1/2211
16
VN+1 < 1 a²
+ a² a² + 1)L,D
N
VI
(102)
8L.
4V/NLL
where D 0 and D == | - x=1 1
--1'
+ 2|12² 20112
2x 0 (f(x)) f(x))), and m
1 + log V 2
1,4, PT. In particular, for N z 8(m
1)21,
we have
L NN+1 1 (1- a²
N
(103)
16L0
Proof. The proof follows the one from (Malitsky & Mishchenko, 2020). First of all, we note that the
stricter inequality A & / 1 30-11 - 1 is not used in the derivation of Lemma G.2. Therefore, Lemma G.2 holds as well as Corollary 1. Next, we make certain steps in the analysis tighter to use the fact that js > O. Strong convexity implies
A (Vf(x*)) x xh, < (x(((=))
> - -
(104)
and Vf(x*) vf(z*~1)|| > 1|-0*==** ----|| ||. The latter implies that A & 1 for k > 1. Since Apc
Lemma 2.2 holds under Assumption 2 with v = and without condition (9), and bound X S holds, we have
(10)
A 2(Lo + L f()+)|)) [V
A (Vf (f (a*), -x/
>x(f(x") (e(f(x")=((a"))
Aa(f- -((x1)
21 || 111
>e(fa - f(x+))-
-1111 || 1i-tl-a"0 -1
2/1
(105)
Lo
Convex combination of (104) and (105) with a E (0, 1), which will be specified latter, gives
Aum 11
2p
A x==((=),==="'""""")"" < f(x*))
x 11 (1 -a)
-
Lo
Using the above inequality instead of convexity and keeping the rest of the proof of Lemma G.2 as is with omitted Σ; terms, get analog of (75):
1++ 11 + 1 4
1+ (1 -a)
81 Lo
1a
1
1²1
1 02
10++101+1(fe+)) f.)
1+30
1 - x11
1
1 1 11 at)
811
||akt| - -x0 =11 22e + (=*) f
Lo
1-a Aul
||00 |1a--x"1 11
1 ||
-2 11 22. ff),
1+0, where the first inequality follows from 1438 A4+10++1 & >x + 0x) provided by the new
condition on dg- Thus, we have contraction in every term: 1 - a Age in the first, 1+(1-a)
1 (1-a) S4
in the second and
1+30s/1 14%
1
in the last one. We bound the third term I(440)
0g
1+(1-a) kg
37

---

Published as a conference paper at ICLR 2025
8k
Ak
4p for both terms in the denominator. Taking 0.98, which is the root of a= 64(1-a²) 1+8(1-a")* we bound the second term
Rbs using d &
11+0g)
/3281
a*'
=
16
as
[+(1-a) 1.0
(1-a) b
3/.0
#
1+8(1-a)
32(1-a)
a" # 8L.
Therefore, for Vx (1 Aed | x 1
1 1+ (1 a²)
|
112 112 22x0u(f
x
fo) we have
k+1 $ (1- a" Ak 1 4Lo
1 Pk.
min
(106)
2
The final step of the proof unrolling the recursion for Lyapunov function V.. Following the proof of Theorem G.2, we have that
Le
100
x
||,
if k: E Ti, where & K and 0 & k--t- & m,
min
Ap 4Lo
xt ||,
l: E T2,
(107)
4La
4hn
1
if k E Ts.
1La
with m m= 1 + log
which differs from m defined in the convex case due to the new condition on Ak. Therefore, by repeating all the steps from the proof of (99), we obtain
/
[1+DL,)
2
N
N
V2N (m + 1)L,D
Σ
min
An
(108)
4T.0
4T.
4T.
Next, we bound the product that arises during recursion unrolling by using the relation between the geometric mean and the arithmetic mean:
N
a² 2
1
})
a" p 1
N
N
1
min
AEe
min
Ak:
4Lo
2
N
4Lo
k=1
(108)
a" +
a" plm + 1)L1D)
N
(109)
8T.0
4v Lo
Finally, we combine (106) and (109) and get
(106)
N
α
Au: 4T. 1) v
V N+1
1
min
2
k=1
(109) <
a x²m(mm + 1) D
V
8Lo
4/ Lo
Moreover, when N > 8(m + D) we have the above inequality implies (103).
a(m++1)L
a'P 164
which in combination with
4v2NLo
38

---

Published as a conference paper at ICLR 2025
H STOCHASTIC EXTENSIONS: MISSING PROOFS AND DETAILS
H.1 (Lo, (i..1i)-STOIII -.SOSCCATCCC GRADIENT DESCENT
Algorithm (Lv, Stochastic Gradient Descent ((Lo, 41)
Input: starting point æº. number of iterations N, stepsize parameter 0, Lo 0. L1 > 0
1: for == 0, ,...., N do
2: Sample gh {1, ..,..-- n uniformly random Lo+2. 1ot2I1V7 f(e+(a
3: a+++
4: end for
Output: z.V
Theorem H.1 (Theorem 7.1). Let Assumption hold. Then, the iterates generated by (Lo, L1) with < E 2. ===== e after N iterations satisfy
min
E
min
vLo 4nL2
f(x*)(()))))))))))))
-
f(00))
2L x2
(110)
nNN +
Proof. Similarly to the deterministic case, we start by expanding the squared distance x", which is common minimizer for all {fil=
1 x=1
x² x²"
Ve Vigx((t
To + [n V Set (3ct)]
2m
1| x x²112
(xt - Vfg (x*))))))
Lo + L1
fer (-+))|
172 V fet (x* |12
+ (To + Ln [5 (1)²
(2)
27
||/// - x²11 Lo + L1
V Sen (x+)]] (Fe) - fex (x*))
17 V Jet (x+
+ (Lo + L1 fe+ (x+
fex (x (x*)
1| z²112 - 2m (1 2)
Lo L1 V fot (I+\)]
fex (a**) fez (x*)
||
20112 11 Too + Tn Ve (2+
(111)
As before, we consider two possible eases:
> Lı
Lo or [V < h.
Case 1: [V
>
Lo L.
In this case, we have
Lo + L VeL((")) & 2 (e+
(112)
"|l Se (x+))) (112)
w Se
2(Lo + L1 Vee & (ex fex(
(113)
4L
Plugging the above inequalities in (111), continue the derivation follows:
(111)(111)
a| - x²12 foz (x*) fgz (x*)
1 h+1 - 1
22, fex
11 - x²12-
vT
(114)
8L?
Case 2: [V (1*)]] < Lg. In this case, have
Lo + L L fet (x < 2Lo,
(115)
39

---

Published as a conference paper at ICLR 2025
implying that
(15). || x²11 & 1| - x²113- -x-1- 111-
17
(fea(z")) fe (x))).
(116)
2Lo
To combine (114) and (116), we introduce event E(a*) ( (x+*) Eu x for given x²
and indicator of event E(x=*) as El(t)): i.e., for given =² we have 1 Ex(*)) and 1 E((*)) = 0f if fe= (x*)
if || fe= h.
<
La L1"
Then, inequalities (114) and (116) can be unified as follows:
$ | x. B(at) 1²1 x
(1 (-1()))))
" (Je= fex (x")))
SL}
2Lo
Let us denote the expectation conditioned on x as [x(.]] == E[: x*). Taking E& from the both sides of the above inequality, derive
E& |110 - x=11
x 11
x²112 Pk
-Ex (1-1a) [(())) )-
11
(fee (fe(((t))
2Lo
where Ps: == P ([ L 2²) 1 P[E({*)) Ex(LE(2t) Note that pk is a random
variable itself. Nevertheless, if pa > 0, it means that for at least one gk E (1....,n) n) we have fg (x*)]| 2 Le for given x² Therefore, either pk: > 1 n or ps: = 0. Moreover, when pv = 0, we have 1 1 1
Li
for given .² Putting all together, we continue as follows:
Ey [1 x² x²]
<
1|x² x²11² 1pu "P 8T7
- [p)=0) Bx (1- (1-1 (((N)) )
(Jea(a")- Sea(=t)) -(((=)))(((())
2T.0
= 1|
x 112 - (0x)00 Pr 8L7
VT
2Lo (f(xt) - -f(x))
(m==0)
1|
x²112 -1 (mn>0)
v1j
11 [m==0)
2hu (f(x*) - f(x)))
8nL}
|| x=1 min
in
11
(f(*²) - f(0')) ((x)))
8nL
2Lo
Taking full expectation from the above inequality and telescoping the result, we get
N+1
E
min
en
" (f(at) ( f(x'))
E
x= 1121 -|112
xx 111
8nL
2Lo
km
km
||
1=1
Since
+1++1)
min
E min
ula inl3
l(x*)
{(x*)}
is
not
greater
than
2Lg
N
(f(x*) - f(x")) }}. we also have
Σ
E
min
n
BnL
20.
k=0
(N + 1)
vLu [(x*) -(60)) -
2
Im O....
min
E min
Ant. AnI...1
< -| - 1²1
Dividing both sides by
+(N+1)
obtain (110).
2ho
40

---

Published as a conference paper at ICLR 2025
H.2 STOCHASTIC GRADIENT DESCENT WITH POLYAK STEPSIZES
Algorithm Stochastic Gradient Descent with Polyak Stepsizes (SGD-PS)
Input: starting point v", number of iterations N, minimal values fi(x*) = minlzedd fi(e) for all E (1,...,7)) n
1: for k = 0, .......,N. - do
2: Sample 5 ~ {I,...,,, na uniformly random
3: x++1 = x (((==")(+++)))
(x Vfe= (x*)
4: end for
Output: v.V
Theorem H.2 (Theorem 7.2). Let Assumption 4 hold. Then, the iterates generated by SGD-PS after N iterations satisfy
VLo
4L 10 - x²12
min
E
min
(117)
AmL]
v(N +1)
Proof. Similarly to the deterministic case, we start by expanding the squared distance x", which is common minimizer for all (fi)
xh x= fea(x*) fc)
|1 112
Vse (ctt)
(x
2 (see (x²) - Sex (x*))
= 1 z²112
(oo - -x¹, [f
(z*))
(x*)
- (x))))
+
V )1
(2) 110 =x1112 ( (x*)))
- Sea
(z*))²
(8) || - 2 Lo + L1 fg (x+))]
(x*) Sea (x*)
20112
(118)
As before, consider two possible cases: | fe- (++)| > La or Se (2*) ||| <
Case 1:
(x= Le In this case, inequalities (112) and (113) hold and the derivation from
L.
(118) can be continued as follows:
|| - x²1
(18)
| x=13
V
Sea (a*) fea(x*)
2
21 Veen
(113)
v²
1 ==112-
(119)
16I
which gives (54).
Case 2: fex < Lo. In this case, inequality (115) holds and we have Li
| - 12 (118)
| x01 fe*(x - [ex
(120)
2L.0
To combine (119) and (120), we introduce event E(x*) V (x+)1 Lu x for given *²
and indicator of event E(x*) as B(at)) i.e., for given wt we have I F():)) 1 // Se Lo and 1 E(=*) = 0 if V fee (x**
Il <
Lo
Then, inequalities (119) and (120) can be unified as follows:
T.
|| x²11 2 & ||,.* - 11 ((*)))
(1 - 1 B(()))) )
V. (fet (x+) - fet (x*))
161
4Lo
41

---

Published as a conference paper at ICLR 2025
Let us denote the expectation conditioned on x² as [&[] E[| |x*). Taking B&[-] from the both sides of the above inequality, we derive
D²
Ex |||a - x² x=]]
< 11a
-0111- =-112-pp Ps
16L7
-Ex (1- 1
(1-1 B(()))) 4Lo (Sea (1*)) - fer (x=)))
where Ps: :- P V (I L wt P{E(=*)}
[(()) Note that pa is random it means that for least one 5t E {l....,m) have
variable itself. Nevertheless, if pk [g (x*) > tu for given æ². Therefore, either Pa > 1 Pk = O. Moreover, when Ps 0, have 1 1 = for given x² Putting all together, we continue as follows:
D²
E& [| x=1
1 x²112 1l (pE20) Pk
1617
4Lg (fex - fc)(00))
1 (m==0) Ek (1 )(()))))
v²
1| 2²112 [mm20)] Pk
1 (m-
(f(x*) - -f(x²))
1677
4L0
2²
11 - z²112 [(p
1
1p==0)
4Lo (f(xh) f(x²))
16mL7
| x²112 min
v²
V
(f(x*)- -
[66LL
4Lo
Taking full expectation from the above inequality and telescoping the result, we get
N
22
N+1
min
16mL; 4Lo (f(x*) - (((+)))((=)))
v
E
201
El[a
x=1 1
1|
x 2²1
Since
v(N+1)
Alo
k=
min
E
min
uLa Imll. [(x*) S(x*)
is
not
greater
than
N
16nL aLo ( -(x) }} we also have
2
min
v(N + 1)
min
E min
4mI? AnIz: [(x*((()))))) -(0t)-((0))))
vLa
< - 1²12
4Lp
k=
Dividing both sides by
v(N+1)
we obtain (117).
4h.0
Remark H.1. Note that the LHS of equation (29) can be lower bounded as follows:
v(N + 1)
vLo
min E min k=O....N
f(x (a²)))((²))
1 ((xt))(((a)))) 1.
4Ta
Ant.
{
vLa
5(0")/ } ((0t)) (5 201
+ min
l(x
AmLZ
vLa
min E min
AmI? s(x s(x ((00)) ) -s(x0)
nLo P
(s(xt) f(x))
vLn
min k=
N 4nL
4nt?
Therefore, from equation equation (29) we have that mink=o,... NN P (f(x*)) - f(xx)====+)))) > #Tp <
8n1.112
"1
n0(++1]
42

---

Published as a conference paper at ICLR 2025
|x_ -x
=1
|x0
x
10
[x0 -x--x"
x
100
10
10a.
10
10a.
10f
10:5.
10a
10".
10.9.
10
10-
10-11
10-9.
10-9.
10-34.
10-12.
10-12.
10
Addo
10
10-19.
AddD
10
10
10
0
200
400
600
800
1000
400
600
800
1000
200
400
600
800
1000
Iteration
Iteration
Figure 1: The last iterate discrepancy of algorithms on the one- variable polynomial function f() =
I NUMERICAL EXPERIMENTS
Synthetic experiment. The existing numerical studies already illustrate the benefits of many methods considered in this paper in solving of numerical experiments with Clip-GD, which is closely related to (Lo, Li J-G., GD-PS, and AdGD on training LSTM (Merity et al., 2018) and/or ResNet (He et al., 2016) models are provided in (Zhang et al., 2020b; Loizou et al., 2021; Malitsky & Mishchenko, 2020). Therefore, in numerical experiments, we focus on a simple 1-dimensional problem that is convex, (Lo. L1)- smooth, and provides additional insights
problems. In particular, the results
the ones presented in the literature. In particular, consider function f(x = x², which is convex, (4, -ssmooth, but not L-smooth as illustrated in Example 1.1. We (i) GD with stepsize 1/z, L = 12 12 (which corresponds to the worst-case smoothness constant on the interval |æ|| < (z))), (ii) (Lo, L-G with Lo = 4, L1 = 3. = 8/2, (iii) (Lo, L -TM with G = Lo + +1 [v/ II (not supported by our theory) and (iv) with Gk+11 max Gk. Lo + L1 [
(called (Lo. LT)-STMMmax on the plots). (v) GD-PS, and (vi) AdGD for starting points x. E {1, 10, 100). The results are reported in Figure 1. In all tests, GD-PS and AdGD show the best results among other methods (which is expected since these methods are the only parameter-free methods). Next, standard GD is the slowest among other methods and slow-downs once we move the starting point further from the optimum, which is also expected since L increases and we have to use smaller stepsizes for GD. Finally, let us discuss the behavior of (Lo, LD) (Lo, 1.J-STM-max, and (Lo, L1) STSM.. Clearly, it depends the starting point to the solution. In particular, when _0 = we have Vv(x9)] = 4, meaning that == 16. In this case, GD and (Lo, L1) behave similarly to each other, and (Lo, L-)-STM-max significantly outperforms both of them, which is well-aligned with the derived bounds. However, for x = 10 and - = 100 we have [vx)) ]|
the distance from
10 leading to significant slow down in the convergence of GD and (Lo. L1) L-SM) maxx In particular, (Lo. L, GDD achieves a similar optimization error to (Lo. L -TMM-xxx for x 10 and much better optimization error for x = 100. This is also aligned with our theoretical results: when Ro is large and number of iterations not too large, bound (15) derived for (Lo, L1 G-D can be better than bound (23) derived for (Lo. L, JSTM-max. Moreover, for x 100, Figure illustrates well the two-stages convergence behavior of (Lo, Li GD described in Theorem 3. 1. Finally, although our theory does not provide any guarantees for (Lo, L1) STM with G+++1 Lo + L, [[VV(x+*+)] this method converges faster than (Lo, L1)-GD for the considered problem but exhibits highly non- monotone behavior.
4- 10 and [v=()))
Logistic regression. problem of the form
We also study the behavior of the algorithms on the Logistic Regression
f(x) =
T1 Σ f((x), where f(x)= = log (1 + exp( y.a x)), a, E R", y1 E (-1,1).
As Example 1.3 shows, each individual function fi is (Lo, In smooth. Moreover, function f is also L-smooth. This implies that f(x) is (Lo, smooooh,, but the derivation of the exact constants Lo and L1 for is problematic and highly depends on the relation between {a.)" Nevertheless, one can still compare the methods considered above on this problem and numerically estimate the dependency of the Hessian norm the norm of the gradient. In particular, gradient norm dependency on the hessian norm in the toy scenario, where all vectors a; are close to each other, i.e., we generated a; 5050 as 0; (1,2,...,50) 50) E, where & ~ ~N(0, I) are
observe linear- like
43

---

Published as a conference paper at ICLR 2025
LogReg Smoothness
22.5
90
20.0
Hessian Norm
17.5
80
15.0
70
12.5
60
10.0
50
7.5
40
5.0
30
50
60
90
100
Gradient Norm
Figure 2: Smoothness dependency on the gradient norm, toy scenario logistic regression.
Reg, a9a
LogReg, a9a
|x x 16
|
11000
L1-STTM
106
Re. 4:3-TTM
10
(,,.L))-TMM.m
(4g.4.)-TMMmaa
10a
10-3.
(D
10a
(G.L:))GD AdGO GD-PS
10-6
AdGD
10
GD-PS
10 6
10
10
10
10
10-15
10
200
400 Iteration
600
800
1000
200
400
600
800
1000
Iteration
LogReg, mushroom
LogReg, mushroom ||x
x x 5
28000
10
106
(c.44))STM
10
Lo.4M)-5MM-max GD
103
10
10
GD
10a
L:-.D
10-7
AdGD
GD-PS
10 -3
GD-PS
10-9
10
10-11
10
10-13
10-12
10-15
10-15
150 200 250 300 400
200
400
600
800
1000
Iteration
lteration
Figure 3: The last iterate discrepancy of algorithms on the logistic regression problem.
i..dd standard Gaussian vectors, and all y; = 1 except of one y, = -1 for randomly selected j from
(1...., 50) (Figure 1).
44

---

Published as a conference paper at ICLR 2025
We also the considered methods for real datasets from LIBSVM (Chang & Lin, 2011) a9a and mushrooms for different starting points. The results are presented in Figure 3. Despite the fact that for these datasets, does not have clear linear dependence of the norm of the Hessian w.r.t. the norm of the gradient, the methods that are hetter suited for (T-p L Ls)-soooth problems (like (To, In GDD GD-PS, and AdGD) converge significantly faster than other methods. Moreover, also emphasize that accelerated variants - (Lo, L1) and (Lo, - S-)M--aaxxx work not better than standard GD in this case.
45


Reviews:
[{"review_id": "e1i8sNQmeP", "reviewer": "Reviewer_RdU1", "summary": "This paper analyzes the iteration complexities of several algorithms targeted at convex $(L_0,L_1)$-smooth optimization. In comparison to previous works, the authors focus on a more refined analysis, including the elimination of dependence on the smoothness parameter $L$ (although it is not the dominant term) for variants of Gradient Descent, as well as improvements on the naive adaption of Adaptive Gradient Descent for generalized smoothness.", "questions": "**Typos and minor suggestions:**\n\nLine 203: Since you cite the conference version rather than the arXiv version of the paper, please refer to it as \"Proposition 1\".\n\nLine 383-387 / Inequality (20-21): I suggest that the authors avoid breaking the entire inequality into two labels, which can cause ambiguity as seen in the second step of (73). Using an underbrace might be a better option.\n\nLine 419: \"$\\varepsilon$-solution\".\n\nLine 1095: a multiplier of $\\exp(\\eta)$ is missing in the last term.\n\n**Questions:**\n\n* As I mentioned in the Weaknesses section, are there any practical examples (either theoretical or experimental) that can justify the importance of the *improved* complexities?\n* For Theorem 3.1, it appears that you integrate the analyses from Li et al. (2024) and Koloskova et al. (2023), substituting the normalization term $\\ell(G)$ in $\\eta$ into something related to $\\|\\nabla f(x^k)\\|$, so that the sequence enjoys the monotonic properties and can be analyzed in two cases. Could you elaborate on the intuition behind this approach?\n* You mention new technical results for $(L_0,L_1)$-smooth functions in Section 1.3. Could you specify these results for reference? \n\n\n\nHaochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex optimization under generalized smoothness. In Advances in Neural Information Processing Systems 36, 2024.\n\nAnastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In Proceedings of the 40th International Conference on Machine Learning, 2023.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "This paper covers existing methods for convex $(L_0,L_1)$-smooth optimization, specifically Gradient Descent with Smoothed Clipping and Polyak Stepsizes. It also provides analyses of Similar Triangles Methods and Adaptive Gradient Descent under the setting of generalized smoothness. The results give an overview of existing and adapted methods.", "weaknesses": "My major concern is about the significance of the results. To be specific, for the first two variants of Gradient Descent, this paper only improves the non-dominant $\\mathcal{O}(\\sqrt{1/\\varepsilon})$ term of iteration complexity, which is inconsequential for small $\\varepsilon$, i.e., when finding a solution with good quality. For the adapted versions of Similar Triangles Method and Adaptive Gradient Descent, the iteration complexity is in the form of $\\mathcal{O}(\\sqrt{L_0L_1A\\exp(L_1A)A^2/\\varepsilon^2})$, where $A$ equals either $R_0$ or $D$, which generally aligns with a specification of Li et al. (2024). Thus, the overall contribution in terms of novel theoretical guarantees appears quite limited to me at this stage.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jBw5ZQrgOd", "reviewer": "Reviewer_pFMj", "summary": "The paper focuses on convex $(L_0, L_1)$-smooth optimization and answers important open questions in this domain. In particular, new convergence rates are derived for the gradient method with smoothed clipping and Polyak stepsizes, improving existing results. The best-known convergence rate is derived for $(L_0, L_1)$-STM. Also, new results proved for AdGD and a stochastic case under the additional assumption on a shared minimizer. The statements in the paper are clear, and compared with existing results in the literature, the proofs are correct.", "questions": "- In the last part of the equation (15), should it be N+1 - T instead of N+1?\n- Why is it so crucial to choose $\\gamma= 1/4$? In Theorem 6.1, to achieve a rate better than in (25)? Can it be relaxed?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Paper improved existing convergence results for gradient methods with (smoothed) clipping and Polyak stepsizes.\n2. New convergence results for AdGD under $(L_0, L_1)$-smooth assumption.\n3. Proposed $(L_0, L_1)$-STM recovers the best-know convergence rate for accelerated methods without additional knowledge on $R_0$ and $f(x^0) - f^*$.", "weaknesses": "1. The paper is missing the conclusion and experiments sections. However, the experiments are provided in the appendix.\n2. The assumptions for stochastic problem is restrictive; however, the derived results are new and better than previous ones.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7M6eOzt6VY", "reviewer": "Reviewer_jtK8", "summary": "This paper takes a closer look at $(L_0,L_1)$-smoothness for the setting of convex optimization. There, it derives more fine-grained convergence rate guarantees than existing work, while discussing extensions to accelerated, stochastic, and certain adaptive settings.", "questions": "* Can a version of the method that is somewhat more agnostic of the knowledge of L0 and L1 be designed, since right now this knowledge is quite necessary for selecting the correct step sizes?\n\n* Ultimately, a high-level takeaway of the work (which is likely also a takeaway that follows from the Chen paper if one could quickly bridge their stationarity to function suboptimality here) seems to be that the results are ultimately of a *local nature*. What I mean by that is that due to the unavoidable dependence of the type $\\exp(\\|x-y\\|)$, the terms involving that in the bound will be large, unless $\\|x-y\\|$ is sufficiently small, and hence, in spirit the results can be viewed as showing that the GD methods studied in the paper are good but only locally. This aspect is not a criticism of the paper, but just a comment on how one can typically interpret bounds that involve exponentials.\n\n* Do the results really offer a significant improvement over Li et al. 2024a (_Convex and Non-convex Optimization Under Generalized Smoothness_). The results provided by Li et al. 2024a for GD and NAG also do not rely on the assumption of L-smoothness, and their acceleration results for NAG  **do not** have a dependence on exp(L1). The authors claim that the advantage of their results is that they do not require dependencies on $\\Vert \\nabla f(x_0) \\Vert$ and $f(x_0) - f^*$, as in Li et al. 2024a, and they argue that these quantities could potentially be exponentially large in the worst case (Line 408-420)---But in the reviewer's opinion, assuming these initial quantities to be constants is not a very strong assumption, whereas in comparison, the authors' acceleration result depends on exp(L1), which seems to be less favorable.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "**UPDATE:** Given the authors willingness (mentioned in their final comment) to make the paper's claims more transparent and to perform the pedagogic and scholarly improvements, I have raised my score.\n\n---\nThe paper makes a technical contribution to the convergence analysis of gradient descent(like) methods, under the general $(L_0,L_1)$ smoothness for differentiable functions. In the reviewer's opinion, the main contribution is a tighter bound on Clip-GD under the generalized smoothness assumption (e.g., The Polyak stepsize is chosen to minimize the upper bound in (59), so the result for GD-PS is not hard to get after having proved (45) for Clip-GD, while STM and AdGD have exponential terms in their upper bounds, and hence only of marginal interest).\n\nStrengths: This article fills a gap in the analysis of convex L0-L1 problems that are differentiable, and claims to do that without having to resort to small stepsizes as in the recent work of Li et al. The work is reasonably clearly written, and is easy to follow. Some aspects that could do with more discussion are the two-phase nature of GD (with the $>, < L_0/L_1$), and what that may mean when compared with other work (does the same happen in the nonconvex case for instance? how does it relate to bounds from the work of Li et al for instance?)", "weaknesses": "*  From a quick skim of the literature, it seems that Zhang et al noted in passing that twice differentiability could be dropped at the expense of some more analysis, but the full details of the differentiable case were worked out in subsequent work. This aspect is not clear from how the current work cites related work, and should be fixed.\n\n* While the related work section is overall fairly good, a more precise statement about the results of Chen et al is needed, especially because that work introduced some of the key technical tools too, and studied the nonconvex case; in particular, it would be worth noting what happens if one trivially takes their nonconvex results, and tries to adapt them to the convex case (by boosting stationarity to function suboptimality using the current assumptions). Also, their slightly more general $\\alpha$-version of Assumption 3 could be noted.\n\n* Section 5 on acceleration could be deferred to the appendix or noted in passing, and more discussion given to the exponential terms in the bound, which are tantamount to saying that essentially no practical acceleration happens, even though the technical result itself is interesting to note. Similarly, the bounds arising in Section 6 should be discussed a bit more, because due to the central assumption of the paper, ultimately the pessimistic exponential terms in D arise.\n\n* The authors's motivation for studying AdGD should be as a result further enhanced: it seems inherently unsuitable to use under the generalized smoothness assumptions since AdGD does not utilize clipping.  And the result for the stochastic case (Section 7) requires a common minimizer for all the stochastic components (Assumption 4). Although such an assumption is also used in some works, this assumption is not that weak, and renders the results less applicable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wQYEBjVuA2", "reviewer": "Reviewer_iTbo", "summary": "This paper focuses on analyzing optimization methods for convex problems under $(L_0,L_1)$-smoothness settings. It provides improved convergence rates for the Gradient Descent (GD) method with Gradient Clipping and the Gradient Descent method with Polyak Stepsizes. It introduces a new accelerated method based on the Similar Triangles Method and provides new convergence rates for the Adaptive Gradient Descent Method. Finally, it extends the analysis to the stochastic case in overparametrized settings.", "questions": "Please refer to the weakness.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The analysis in this work does not rely on the L-smooth assumption, which was required in previous works. In this way, the work proves a convergence rate for the Gradient Descent (GD) method with Gradient Clipping and the Gradient Descent method with Polyak Stepsizes, with the dominant part having a smaller constant depending on $L_0$.\n\n2. This work proposes a new variant of the Similar Triangles Method that accelerates GD.\n\n3. This work provides a faster convergence rate for the Adaptive Gradient Descent Method in $(L_0,L_1)$-smoothness settings compared to the locally L-smooth setting.", "weaknesses": "1. A new acceleration of GD is proposed. It would be supportive to add more remarks to highlight the theoretical merits of this acceleration compared with the STM in (Gasnikov & Nesterov, 2016). Additionally, it would be more supportive to numerically compare its performance with STM in (Gasnikov & Nesterov, 2016).\n\n2. Example 1.3 considers a logistic function with L2 regularization. However, $f(x)$ is not related to L2. It would be better to specify where the L2 regularization is.\n\n3. The discussion after Theorem 7.1 (line 521) claims that the probability must be smaller than $\\frac{8nL_1^2\\|x^0-x^*\\|^2}{\\eta\\nu(N+1)}$. It would be clearer to explain why the probability should be smaller than this value.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IrswG0mixZ", "reviewer": "Reviewer_4rMB", "summary": "The paper present a study for gradient method for solving optimization problems involving (L0,L1)-smooth objective function, which was first introduced in (Zhang et al, 2020b). The analysis in the current paper is devoted fully for the convex and strongly convex case, where the convergence analysis of several methods is proopsed, both in the deterministic and stochastic setting. However, there are some major issues needed to be addressed.", "questions": "See weakness", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper is well-writen, and thus easy to follow. The paper has some signification theoretical contributions for the existing algorithms. There are also new algorithms being adapated from the classical smoothness to the new (L0,L1)-smoothness.", "weaknesses": "1. The analysis of the current paper is mostly based on Assymetric and Symmetric (L0,L1) smoothness, which can be hold for functions that are not twice differentiable. This is good since this class cover the original class of function in (Zhang et al, 2020b), where twice differentiability is a must. However, which meaningful classes of functions satisfy Assymetric/Symmetric (L0,L1) smoothness while not C2? I found that all the examples presented are C2, and thus it seems that the use of  Assymetric and Symmetric (L0,L1) smoothness is not neccesary, which reduces the importance of the current paper much. Note that examples for L-smooth functions that are not C2 are diverse, so it is reasonable to use the gradient Lipschitz condition instead of the stronger one, bounded Hessian. I do not think it is the case for (L0,L1) smoothness.\n\n2. Now assume that the function is C2. Lemma 2.1 shows that (L0,L1) smoothness implies (not equivalent) equation (7). In comparison with Lemma 2.2 (Vankov et al., 2024) below, their equation (2.2) seems to be a shaper inequality and in fact is a equivalent condition. Based on this, I suspect that the results obtained by the paper under review is not as tight as claimed by the authors, especially when compared with (Vankov et al., 2024).  \n\n3. The convergence theory of algorithms for (L0,L1)-smooth function does not explain why they are better than standard gradient descent. For example, can the authors explain why standard GD performs worse than designated algorithms for (L0,L1)-smooth function in solving logistic regression?\n\nReference.\nD Vankov, A Rodomanov, A Nedich, L Sankar, SU Stich, Optimizing (L0,L1) - Smooth Functions by Gradient Methods, https://arxiv.org/abs/2410.10800", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)