Optimizing $(L_0, L_1)$-Smooth Functions by Gradient Methods
Authors: Daniil Vankov
Anton Rodomanov
Angelia Nedich
Lalitha Sankar
Sebastian U Stich
Venue: ICLR 2025 Poster (2025)
Keywords: $(L_0
L_1)$-smoothness
gradient methods
convex optimization
worst-case complexity bounds
acceleration
Polyak stepsizes
nonconvex optimization
Primary area: optimization

Abstract: We study gradient methods for optimizing $(L_0, L_1)$-smooth functions, a
class that generalizes Lipschitz-smooth functions and has gained attention for
its relevance in machine learning.
We provide new insights into the structure of this function class and develop
a principled framework for analyzing optimization methods in this setting.
While our convergence rate estimates recover existing results for minimizing
the gradient norm in nonconvex problems, our approach significantly improves
the best-known complexity bounds for convex objectives.
Moreover, we show that the gradient method with Polyak stepsizes and the
normalized gradient method achieve nearly the same complexity guarantees as
methods that rely on explicit knowledge of $(L_0, L_1)$.
Finally, we demonstrate that a carefully designed accelerated gradient
method can be applied to $(L_0, L_1)$-smooth functions, further improving all
previous results.

Published as a conference paper at ICLR 2025
OPTIMIZING (Lo, LI)-SMOOTH FUNCTIONS BY GRADI- ENT METHODS
Daniil Vankov' Arizona State University dvankov@asu.eda edu
Anton Rodomanov
CISPA
anton. htw.:cc.rrodmnnoccccisp..co
Angelia Nedić
Lalitha Sankar
Sebastian U. Stich
Arizona State University
Arizona State University
CISPA
www.:iiasndicccaass.e.. edu
ssankaz@asu.edtt
stichScispa.de
ABSTRACT
We study gradient methods for optimizing (Lo, --m-oohtth functions, a class that generalizes Lipschitz-smooth functions and has gained attention for its relevance in machine learning. We provide new insights into the structure of this function class and develop principled framework for analyzing optimization methods in this setting. While our convergence rate estimates recover existing results for minimizing the gradient norm nonconvex problems, our approach significantly improves the best-known complexity bounds for convex objectives. Moreover, we show that the gradient method with Polyak stepsizes and the normalized gradient method achieve nearly the same complexity guarantees as methods that rely on explicit knowledge of (Lo, L1). Finally, we demonstrate that carefully designed accelerated gradient method can be applied to (Lo, L1) -mmoohh functions, further improving all previous results.
INTRODUCTION
In this paper, we focus on the deterministic unconstrained optimization problem
min f(x), FER
(1)
an (Lo, Li -smooth function. With the rise of deep learning, ensuring effi- cient convergence has become increasingly critical. Traditional optimization methods, such as the gradient descent method and its variants, often rely on assumptions like Lipschitz-sman smoothhess to guarantee convergence rates. However, in modern machine learning problems, these assumptions might be too restrictive, especially when optimizing deep neural network models.
where f: Rd Rd
Experiments in (Zhang al. 2019) demonstrated that the Hessian ent norm of the loss when training neural networks. This observation led the authors to propose (Lo, -mmoooosttssssss,
correlates with the gradi-
realistic smoothness assumption that generalizes classical Lipschitz smoothness. They also analyzed the gradient method (GM) with fixed, normalized, and clipped stepsizes for nonconvex optimization, showing that normalized and clipped methods perform more favorably in the new setting. In recent years, numerous studies have investigated optimization meth- ods under (La, In smmoothnesss.. However, despite growing interest, existing convergence results remain suboptimal in key cases, and the theoretical analysis of these methods is still incomplete.
To address this gap. this work explores the properties of (Lo, L1) smooth functions and investigates gradient methods for their optimization.
Contributions. Our main contributions can be summarized as follows:
Part of the work was done while DV visited the CISPA Helmholtz Center for Information Security. CISPA Helmholtz Center for Information Security.

---

Published as a conference paper at ICLR 2025
In Section we provide novel results and insights into the (Lo, L1 -smoohh class by (i) presenting new examples and operations preserving (Lo, smmoshheesssss, and (ii) deriving new properties of this function class, leading to tighter bounds on the function value and its gradient. In Section 3 we propose new, intuitive step sizes that directly follow from minimizing our tighter upper bound the function growth. We also discuss the relation between these stepsizes and those used in the normalized and clipped gradient methods.
For nonconvex functions, our gradient methods achieve the best-known O (Lffe + _ com- plexity bound for finding an e-stationary point, where Fo- == f(zo) f is the function residual at the initial point (Theorem 3.T). For convex problems, we significantly improve existing results by showing that an e-approximate solution in terms of the function value can be found in at most
0 [Lalt" + L Rn Fb) gradient queries, where = ||00 - x" is the initial distance to solution
(Theorem 3.2).
We also study two other methods: normalized gradient method (NGM) and gradient method with Polyak stepsizes (PS-GM), neither of which requires the knowledge of (To, [1). For both meth-
ods, we show that they enjoy the O Loft" 2 + [}] complexity (see Theorems 4.1 and 5.1
complexity bound for the Accelerated Gradient Method with Small-Dimensione Relaxation (AGMsDR), where 2 denotes the number of oracle queries required for one-dimensional minimization of the objective over an interval (see Theorem 6.2
Finally, in Section we prove the (V(v L + [(L; E
In contrast other results in the literature, all our complexity bounds neither depend the initial gradient norm nor have an exponential dependency on Lo or L1-
Following the introduction of the (Lo, L.)-slass by Zhang et al. (0119) subsequent works have explored other smoothness generalizations and analyzed gradient methods under these new assumptions. Chen et al. (2033) introduced the a-asymmetric class, relaxing the assumption on twice differentiability and allowing a sublinear growth on the norm of a gradient. In (Li et al.) 2023), authors went further and proposed the weakest (r, 1) 1)-smooth class, which allows even quadratic growth of the norm of the Hessian with respect to the norm of the gradient. Despite the generality of this assumption, there are still some issues and open questions regarding the existing results even for the basic (To, L1) -smooth class.
Related work.
In (Zhang et al.] (202)) the authors analyzed the clipped GM with momentum and improved the com- plexity bound with respect to (Lo, L.). Using the right choice of clipping parameters, Koloskova et al. (2023) proved, for nonconvex and convex problems respectively, the O La Li and
0 L + V L. R2) complexity bounds, where L. is the standard Lipschitz-
constant.
For convex problems, Li et al. (2023) proposed an (asymptotically) faster accelerated gradient L3
method whose complexity is O + Lo + 1// Lo+ Several works have studied
adaptive optimization methods that do not require the (Lo, Li) parameters to be known. Faw et al. 2023); Wang et al. (2023) studied convergence rates for AdaGrad for stochastic nonconvex prob-
lems. Hübler et al. (2024) proposed a gradient method with the backtracking line search and showed
the O
Fa
2
complexity bound for nonconvex problems, For convex problems, Takezawa RTT.
et al.
(224)) proved that the PS-GM method enjoys the complexity of O Lo.
A closely related paper that appeared online independently during the finalization of our manuscript is (Gorbunov et al. 20244.. The authors introduce a new stepsize selection strategy for gradient meth- ods on convex (Lo, L1 -mmooth functions, called "smooth clipping." which, up to absolute constants, coincides with one of our formulas. Their proof techniques differ from ours, resulting in a slightly
worse complexity bound of O L [L, (2)²) compared to our O RR + L, R In Fie), particularly when the initial function value is reasonably bounded (see Section 3 They also show that PS-GM achieves the same efficiency bound as in our work. Additionally, the authors present accelerated
method with complexity ((1) exp(O(1)L, R La and extend their analysis strongly con- vex, stochastic and adaptive methods. In contrast, our work has a slightly different focus, offering
c
See Scction
2

---

Published as a conference paper at ICLR 2025
deeper insights by deriving principled stepsize formulas, analyzing nonconvex functions, studying nornlizedd gradient methods, and developing a superior acceleration scheme with significantly better
complexity. Moreover, proof techniques differ from those in (Gorbunov et al. 2024)
DEFINITION AND PROPERTIES OF (Lo, L1)-SMOTHH FUNCTIONS
In this section, we state assumptions and discuss important properties of generalized smooth functions. We start with defining our main assumption on (Lo, L1 -smooth functions.
Throughout this paper, unless specified otherwise, we use the standard inner product (5 and the standard Euclidean norm for vectors, and the standard spectral norm || assume that problem (T) admits solution.
for matrices. We also
Definition 2.1. twice continuously differentiable function f: Rd - TR called (To, In) -mooth (for some Lo. L1 0) it holds that
f(x)l & Lo + [x)])
Va E E
The class of (Lu, L-)-smooth functions a wide family which includes the class of Lipschitz- smooth functions, and was introduced in (Zhang al.) (019). For twice differentiable functions, this definition is equivalent to that of a-symmetric functions with a = proposed in (Chen et al.) 2.23). Since any a-symmetric twice differentiable function is also (Lo, I -mmoth with different choice of parameters, all our subsequent results hold for a-symmetric functions as well.
For the purpose of analysis of the methods, we provide an alternative and more useful first-order characterization of the class of (Lo, Lsmomhhtth functions.
Lemma 2.2. Let f be twice continuously differentiable function, Then, f is (Lo, L, -mooohh if and only if any of the following inequalities holds for any x. y E IR
te A1llv-=1-1
[V V < (Lo + L [[(x))
(3)
L1
(TTilly xxll)
1f(v) - f(x) - (Vf(z).v - 2) s (Lo + L ([((()I
(4)
L
where ((t) = e¹ - 1 0)
The proof of Lemma 2.2 be found in Section A.1 is worth noting that inequality (3 is stronger
than that from (Zhang et al., 2020) Corollary A.4). The bound in inequality 44) is tighter than those presented previous works (see, for example, Lemma A.3 in (Zhang et 2020). Lemma
in (Hübler et al., 2024)). These tighter estimates allow us to construct gradient methods in the sequel.
In analysis, often certain properties of the function Φ and its conjugate d.. which summarize in the following lemma (see Section A.7 for the proof).
Lemma 2.3. The following statements for the function ((t) e - --11 hold true:
1. d(t) s x1-5) for all E (0,3) and ((t) < Se' for all 0.
12
2. o. (,) = max frt o(t)} = (1 + + 7) for any 7 2 0.
3. 24y < (1) & for all 7 2 0.
72
When f is also convex, we have the following useful incqualities (see Section A.2 for the proof).
Hereinafter, for L, 0 and any 2 O, we assume that f limits of these expressions when Ln + 0; Lı > 0.
t, ((4r))
2 etc.,
etc., which are the
7.1
2
"The conjugate function is defined in the standard way: (T)) maxezolt ( ((t))-
3

---

Published as a conference paper at ICLR 2025
Lemma 2.4. Let f be convex (Lu, (al_L11ssoooo smoooth nonlinea function. Then, for any 2, y E R.
f(v) f(x) + (Vf(x), 2) + Lo + ZallVf()))
ITlV -
Lo + [[(VV( | V)(D)))).
(5)
Li
(V)(z) - vf(v).x- Lo + L1 V /
4 L - -
Li
Lo L1
(6)
Lo + L1 [[](]
( V
Lo L1 [/((]]
where th is the function from Lemma 2.3
Lemma 2.4 is generalization of Nesterov
2018
Theorem 2.1.5) to (Lo. L1) L-)oshooth functions. 2 as L1 0). Moreover, using Lemma 2.3
and matches it when L1 (since 0
we can simplify the lower bound in
Corollary 2.5. Let f be a convex (Lo, L1) smooth nonlinear function. Then, for any 2. y Rd
f(v) f(x) + (V z) + 2(Lo + L ( [f(a]l
(7)
GRADIENT METHOD
Having established a few important properties of an (Lo, Li --momhoth function f. we now turn our attention to the gradient method (GM) for minimizing such function:
F&+1 = The fxxx),
k 1,0,
(8)
where E Rd is starting point and пą 2 O are certain stepsizes.
We start with showing that the gradient update rule ( and the "right" formula for the stepsize me
both naturally arise from the classical idea in optimization theory-choosing the next iterate 1 by minimizing the global upper bound on the objective constructed around the current iterate z& (see (Nesterov 2). Indeed, let z E Rd be the current point, and let == Lo + L1 [[[v)( > 0.
According to (4), for any y E Rd.
fly) S (Vf(2), x) + 6L1 x()).
Our goal minimize the right-hand of the above inequality in y. Since the last term in this bound depends only on the norm of x, the optimal point y" = T(x) is the result of the gradient step T(x) r* (x))) for some r* > 0 ensuring the following progress in decreasing the function value:
[V/(]]]
(
(x)))(((x)) max r20
(V)(()))
(Lr)))
a I,
L
where d. is the conjugate function to & (see Lemma 2.3 the above optimization problem, satisfying T. V
Furthermore, r* is exactly the solution of
(Tar"" Solving this equation, using (6')-1(2) = (.))) = In(1 + 7). we obtain p" I, 0'(( L
[V((a)) = L In(1 + L L[V((1I]
The above considerations lead us to the following optimal choice of stepsizes in
[
11 = La [ In
To + Ln V[(xa)
A O,
(9)
resulting in the following progress in decreasing the objective:
f(x)) - [(x++1) Lo L, L [
L (IlV
= A
(10)
T
To + LA V[
According Lemma 2.2 this means that Lo L [1([(( for any x Rd.
4

---

Published as a conference paper at ICLR 2025
The above expression for A& is quite cumbersome but, in fact, it behaves as the simple fraction [[ Lo+Li (V(()) More precisely, from Lemma 3), we see that
[V((x)]1
A
20 - 34, [(x)]
2(Lo + L1 ((xx)l
Thus, there not much point in keeping the complicated expression it follows:
10 and we can safely simplify
[[
f(zx) f(x++1) 2L0 + 3L, V[
(11)
Interestingly, we can also arrive at exactly the bound sizes. Specifically, replacing In(1 + 7) with its lower bound inequality in Lemma 33 that we used to simplify (TO) into fied stepsizes:
11
by using a simpler choice of step-
27 (which is responsible for the
we obtain the following simpli-
1/K
k 0.
(12)
Lo
With this choice, the iterates of method (8) still satisfy
(see Lemma B.I
Further, note that, up to absolute constants, stepsize
12
acts
max Lo V [Ix)
min Ln L, M J. which is the so-called clipping stepsize used in many previous works (hang al. 2019 2020 Koloskova et al. (023). Thus, with the right choice of absolute constants, we can expect the corresponding clipping stepsizes, to satisfy a similar inequality (11). This indeed the case, and we can show, in particular, that the clipping stepsizes
m min 2L [
(13)
do satisfy although with slightly worse absolute constants (see Lemmal B.I.
We have thus demonstrated in this section that clipping stepsizes (13) simply convenient ap- proximation of the optimal stepsizes (9) ensuring a similar bound on the objective progress. This
observation seems to be a new insight into clipping stepsizes which has not been previously explored
in the literature.
It is not difficult see that the three stepsizes we introduced in this section satisfy
Th
1 < mi
(14)
3.1 NONCONVEX FUNCTIONS
We are now ready to present convergence rate result for nonconvex functions. Theorem 3.1. Let f be an (Lo, Li )-smooth function, and let {Ix} be iterate sequence of GM (8) with one of the stepsize choices given by (22 or (3) Then, minogask [[v]l S e for any
given e > 0 whenever
FL FL,Fo ac²
K
ac
where a = 1 for stepsizes and 12 and = 2 for stepsize
13
The proof of Theorem 3.1 can be found in Section B.2
The rate in Theorem 3.1 matches, up to absolute constants, the rate in (Koloskova et al. 2023 for clipped GM with 1 (oo + +cL, for c =
4,, or equivalently the GM with stepsize 7)s = 18L. min [1, L, V }. Furthermore, our rate is
obtained in Zhang et al. 2019) for the clipped + 2L." and the latter expression can be arbitrarily far away from the former whenever Lp is sufficiently small and L, is distinct from zero. In addition to that, our convergence rate result does not depend on the gradient norm at the initial point, contrast to [L al. (2023) who consider a wider class of generalized-smooth functions but whose rate (polynomially) depends
significantly better than the rate O Lofe + L. GM since L.fe < L. Fa 2c
T.o
on V ffx))) [|- Also, our rate from Theorem 3.1 is better than O Lafa + 12 al. 2024 for the GM equipped with cerfain backtracking line search.
provided in HHübler
5

---

Published as a conference paper at ICLR 2025
3.2 CONVEX FUNCTIONS
Let us now provide the convergence rate for convex functions.
Theorem 3.2. Let { be the iterates of GM (8) with one of the stepsize choices given in 9
12
or (13), applied to problem (1) with (Lu, L -smooth convex function f. Let x² be arbitrary
solution to the problem and let Fo == f(x0) - s Then, the sequence Ra == 10 - x= k 2 0, is
nonincreasing, and [xx)
5 S 6 for any given 0 < 5 Fo whenever
2 L
3
Fu
2+ LoR
3(1
K 2
LI
11
where = Ro, and for stepsizes (9). and 2 for stepsize
The proof of Theorem 3.2 be found in Section B.3 Notice that the second estimate O (Laltt c + [[, in Theorem 3.2 comes from a very pessimistic bound on Fo with the exponen- tially large quantity exp(I,, R) fa coming from Lemmas 2.2 and 2.3 However, in the case when Fo is reasonably bounded (e.g., we apply "hot-start" or f IS a well-behaved function such as the logistic one), the OLn ( term from the main estimate can be much smaller than ([L2 R)?) from the pessimistic estimate. It is worth mentioning the work of Lobanov et al. (2024), posted online after the ICLR rebuttal, where the same bound as in Theorem 3.2 was independently derived.
In Theorem 3.2 do not make assumption L-smoothness of the objective, in contrast
Koloskova al. 2023). Moreover, the rate in the theorem is better than O Le
- L R2)
provided in (Koloskova et al. 2023) for the clipped GM. Also, in contrast to (Li et al. 2023 our result does not include the gradient norm the initial point which could be quite large (consider, e.g.. (x) = = ||==|| from Example A.1 for p > 2 and To sufficiently far from the origin).
4 NORMALIZED GRADIENT METHOD
To run GM from Section 3 it is necessary to know the parameters (To, I1) in advance. In many real-life examples, those parameters are unknown, and it might be computationally expensive to estimate them. Furthermore, for any given function f. the pair (Lo, L2) is generally not unique (see Examples A. and [..)). and
not clear in advance which pair would result the best possible convergence rate of our optimization method. To address this issue, in this section, we present another version of the gradient method that does not require knowing (Lo, L1). This is the normalized gradient method (NGM):
3E [ff(2))]
F&+1
I.
vf(xx),
A 0,
(15)
where No IR is certain starting point, and 3x are positive coefficients. The following result describes the efficiency of NGM (see Section C for the proof).
Theorem 4.1. Let { be the iterates of NGM 15 as applied to problem with an (Lo, L1)- smooth convex function f- Consider the constant coefficients Bx. 'K+I' 0 I k K where R > 0 is parameter and K > 1 is the total number of iterations of the method (fixed in advance). Then, minosksK f(x+) f < for any given > 0 whenever
ft
R2 L -
K + 12 max
where R = 1( R
R2), R
x² ||. and x" is an arbitrary solution of the problem.
The parameter Ř in the formula for coefficients B& is an estimation of the initial distance R to solution, and the best complexity bound of K* O La RJ²) is achieved whenever ft - R. Note that, even if R + R, the method still converges but with a slightly worse total complexity of K p², where p max / R
R R

---

Published as a conference paper at ICLR 2025
The proof of Theorem 4.1 is based on the following two important facts (Nesterov 2018 Section 3). First, under the proper choice of coefficients Bk. NGM ensures that the minimal value Ux among
2g = (V [[x]( 7 k I K, converges to zero at the rate of R These quantities ty have vk
geometrical meaning- each of them is exactly the distance from the point x² to the supporting hyperplane to the sublevel set of f at the point 2g.- Second, whenever uik converges to zero, so does minosksK - f*. Moreover, we can relate the two quantities whenever we can bound, for any given v 2 0, the function residual f(x)) - f over the ball || x²1 v:
Lemma 4.2 (Nesterov 2018 Lemma 3.2.1)). Let f: IRd + R be differentiable convex function.
Then, for any y Rd and ( = (V/())) wll+, it holds that
[[
((x f(v) max f(y) ||= vll - (y(;,)))-
(16)
=ER
In case when the function f is (To; T1)-smooth the corresponding bound can be obtained from Lemma 2.2
In Theorem 4.1, we fix the number of iterations K before running the method, which is standard approach for the moormalized)-(subgraadde doing so may be undesirable in practice since it becomes difficult continue running the method if the time budget was suddenly increased and also prevents the method from using larger stepsizes at the initial iterations. To overcome these drawbacks, one can use time-varying coefficients by setting A 0
methods (Section 3.2 in Nesterov] (2018)) ). However,
S k < K - 1. This results in the same worst-case theoretical complexity as in 4. but with extra logarithmic factor (see Theorem C.2) Moreover, one can completely eliminate this extra logarithmic factor by switching to an appropriate modification of the standard (sub)gradient method such as Dual Averaging (Nesterov) 2005).
Theorem
For R R. the complexity of NGM is O Lo + [T, RJ2) which is generally worse than that of the previously considered GM (see Theorem and that GM requires knowing (Lo, L1), and its rate depends on the particular choice of these constants. In contrast, NGM does not require the knowledge of these parameters, and its "real" complexity is
and the corresponding discussion). However, recall
O(1) min { Lo,L2
R2 +[L,R]; f is (Lu, L Ln)-moothh]
where O(1) is an absolute constant.
5 GRADIENT METHOD WITH POLYAK STEPSIZES
In the previous sections, the parameters required to run the methods were (Lo, L1) for GM, and the estimation R. of the initial distance to solution R for NGM. To achieve good complexity for NGM, the estimate it should be close the real R. otherwise the algorithm will be inefficient. Sometimes. (Lo, L1), or a good estimate R are unknown, while the optimal value of the objective is available. One such example is overparametrized models in machine learning where f = 0.
In this section, we focus on the case when f is known and analyze the gradient method g with the Polyak stepsizes (PS-GM):
Th [(xx) -
k 220 0.
(17)
[+
Theorem 5.1. Let { be the iterates of PS-GM 8 17 as applied to problem ! with an (Lo, -mooohh convex function f. Then, it holds that minogksk f(xx) - f* S for any given
>> O whenever
K + 12 max RL
(L [6],
where == 1|:00 - x²'| and x² is an arbitrary solution of the problem.
'Here [t]+ == max(t, 0} is the nonnegative part of t E R.
7

---

Published as a conference paper at ICLR 2025
Algorithm AGMsDR
1: Input: Initial point E R update rule T()).
2: uo zo. Ao Co(z) = | voll".
for 1,....
4: yA arg m (f()):
vs + Baxx - 1x), 3 []]
5: 3*+1 T(yk): M& )) f( (> 0)
6: Find 0x+1 > from the equation MA A + 0.+1. Set Ak+1 As aa+11-
7: ex+1 arg ged (Sx+1 = (x) (f(h) (V/(,), wx)]}.
We prove the theorem by using standard inequality for the gradient method with Polyak stepsizes (PS-GM) for convex functions,
R R 2 fb
gh
where Rg || 11 fx f(xx) f", and gk
[[x((] We then leverage the lower
bound (7). and bound the gradient norm gk by 1/ (fa,. where (g))) = IL. obtaining
18 [JW)]
Summing these relations, passing to the minimal value of fe. and rearranging the resulting in- equality, we obtain the desired bound. The complete proof of Theorem 5.1 can be found Section D.I
Notice that the rate O Lo +Th Ri22 in Theorem 5.1 is the same as that of NGM from Theorem
Further, rate is better than O R + L provided in (Takezawa et al. 2024), and does not require any extra assumptions such as the L-Lipschitz smoothness of the objective. Finally, as for NGM, the rate for PS-GM holds for any choice of (Lo, L1), including the best possible one.
ACCELERATED GRADIENT METHOD
This section develops an accelerated method for minimizing an (Lg, L1) -moothh convex function f- The key ingredient of our analysis is monotone variant of the accelerated gradient scheme known as Accelerated Gradient Method with mmall-Dimmensionl Relaxation (AGMsDR) (Nestervv al.) 2021I. We present this method in Algorithm in slightly more general form than the original work. Specifically, instead computing Ik+1 via a standard gradient step from yk. we allow any update rule T(-): Rd Ied that ensures a strictly positive decrease in the function value:
f(x) - f(T(=)) > 00
Vx e Rd {z:
(18)
Theorem 6.1. Let AGMsDR (Algorithm 7 be applied to problem ( with a differentiable comvex objective f, and any update rule T()) satisfying the strictly positive decrease property (18). Let x² be an arbitrary solution of the problem, and let R = -|z0 - x²1.. Then, for all k 2 0, we have
2R
f(*x+1) - f
f(zx+1) +
|f( f(yx) $ f(xx). (19)
E
Ei=0
2M
VM,
The proof of Theorem 6.1 is given in Section E.1 Interestingly, neither the result nor the algorithm assumes any specific smoothness properties of the objective function. However, the convergence rate depends on the magnitude of the quantities M, -[/( which quantifies the progress made by each step T(-). For standard L-Lipschitz smooth functions, natural choice of T(.) is gradient step with stepsize 1. yielding M4 < L and the well-known rate O LR
[V
for f(xx) f* 1
'For the sake of simplicity. in what follows, we always assume that, at each iteration, Vf(yx) * 0. Oth- erwise, Yt is optimal point, and we can stop the method. Note that, in view of (88) the denominator in the definition of Mg strictly positive.
8

---

Published as a conference paper at ICLR 2025
For (Lu, L1)-LLssiin smoothh functions, define 2/++1 T(k)) gradient step with any of the stepsize rules discussed in Section B (applied to yb rather than 2x), ensuring the following progress per step:
g
f(x) - ((x++1)) 2 T/g + 1499*
(20)
where S = [V](())] 14- _ Lo. and L 2 L1. with a being an absolute constant depending on the specific stepsize rule. This implies Mr S ( leading to the following convergence rate estimate:
(2R)²
f(x++1)-
(21)
(i ViG+119
To obtain an explicit complexity bound from 21 we must show that the gradient norms Ji do not grow too quickly on average. This follows from (20p and the algorithm's construction ensuring that
(Vk) < f(x)). Ultimately, this yields the following complexity result whose proof is given in Section
Theorem 6.2. Let AGMsDR (Algorithm 7 be applied to solving problem ① with an (Lo, L1)- smooth convex objective, and T() being the gradient update T(x) 2 1he fz))), where is any of the stepsizes 9. (12), or (13 (with Vs replaced byx, x, rexpectively). Further, let x² be an arbitrury
solution to the problem, and define Fo = =(xx)) -5* and R == 120 xx Then, [(xx) - S for a given O < S Fo whenever
48L
log2 2Fo
kN
k
+ (3)2
ac
where 1 for stepsize rules (9. 12 and first-order oracle queries required to construct æ4 is at most (v + 1)k, where v is the number of oracle queries needed to compute yv at each iteration.
for stepsize rule 13) The total number of
Compared to existing complexity results for accelerated gradient methods on (Lo, L smooth F.
functions- -uchh as the R
1)
Fot Lose) bound for NAG (Li al. 2023 (see
Lo
Section and the ex)))xp((()))))) R), our complexity estimate in Theorem 6.2 is significantly better.
La bound for STM-Max (Gorbunov al. 2024
At each step, AGMsDR requires solving a certain one-dimensional subproblem compute yk. which we assume requires at most oracle queries. For many practical problems, this subproblem computationally efficient, making the extra factor v in the complexity estimate negligible. Nev- ertheless, from a theoretical perspective, eliminating this one-dimensional search (as in the standard FGM for Lipschitz- smooth functions) remains an important open question for future research.
CONCLUSION
This work investigates gradient methods for (Lo, Li >-moooth optimization problems. We have pro- vided new insights into this function class, presented examples, and identified operations preserving (Lo, -msooootnssss. Additionally, we have established refined properties of these functions, lead- ing to tighter approximations of the objective and its gradient. Building these improved proper- ties, we have derived new stepsizes for the gradient method and connected them to normalized and clipped stepsizes. For these stepsizes, we have achieved the best-known complexity O LoFa + L for finding e-stationary point in nonconvex problems. In the convex setting, our analysis signifi- cantly strengthens existing results, yielding the improved complexity O Latt" I. Rn Fs for the gradient method with our stepsizes. We have further analyzed the GM-PS and NGM methods, both of which achieve the complexity O Lo + R]3. significant improvement over previously known bounds. Notably, these methods automatically adapt to the best possible values of (Lo, L1).
Finally, we have obtained fast complexity bound of DO(V L.." + [), | 1) for AGMsDR, which provides the best efficiency estimate currently available for minimizing L,)- smooth convex functions. An interesting open question is whether line search be eliminated in

---

Published as a conference paper at ICLR 2025
the accelerated method, potentially replacing in the complexity bound with absolute constant. Additionally, it remains to be seen whether the second term in the complexity bound can be further improved or if it is indeed optimal.
REFERENCES
Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smooth nonconvex, optimiza- tion is as efficient as smooth nonconvex optimization. In International Conference on Machine Learning, 2023.
Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smooth- ness: A stopped analysis of adaptive sgd. The Thirty Sixth Annual Conference on Learning Theory, pp. 89-160. PMLR, 2023.
Eduard Gorbunov, Nazarii Tupitsa, Sayantan Choudhury, Alen Aliev, Peter Richtárik, Samuel Horváth, and Martin Takáč. Methods for convex (lo, (1) >mmoohh optimization: Clipping, ac- celeration, and adaptivity. arXiv preprint arXiv:2409. 14999999..499, 2024.
Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal. Convex Analysis and Minimization Algo- rithms II: Advanced Theory and Bundle Methods. Springer Berlin Heidelberg. 1993. ISBN 9783662064092. doi: (00007978-33662-06440000 978 3- 662 000-6662204999 06409-2
URLhttp::/dkx do wor.ioorg/110.
Florian Hübler, Junchi Yang. Xiang Li, and Niao He. Parameter- optimization under relaxed smoothness. In International Conference on Artificial Intelligence and Statistics, pp. 4861-4869. PMLR, 2024.
Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U Stich. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees, In International Conference on Machine Learn- ing. pp. 17343-1783 PMLR, 2023.
Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex optimization under generalized smoothness. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
Aleksandr Lobanov, Alexander Gasnikov, Eduard Gorbunov, and Martin Takác. Linear convergence rate in convex setup is possible! gradient descent method variants under (lo, 11) (o.o)))mmmohhness arXiv preprint arXi::2412.
2024.
Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical Program- ming, 120:221-259, 2005. URL httpp:://appp www.ppsssttscccooaaoaaooo... wtt.://cccooaaaoooooroosssssss/s
14935076
Yurii Nesterov. Lectures on Convex Optimization, volume 137, Springer Optimization and Its Applications Series, 2nd edition, 2018.
Yurii Nesterov, Alexander Gasnikov, Sergey Guminov, and Pavel Dvurechensky. Primal-dual ac- celerated gradient methods with small-dimensional relaxation oracle. Optimization Methods and Software, 36(():773-811 2021.
R Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
Anton Rodomanov. Mhasi-Newton Methods with Provable Efficiency Guarantees. PhD thesis, PhD thesis, Université Catholique de Louvain, 2022.
Yuki Takezawa, Han Bao, Ryoma Sato, Kenta Niwa, and Makoto Yamada. Polyak meets parameter- free clipped gradient descent. arXiv preprint arXiv:2405.150/1 2024.
Bohan Wang, Huishuai Zhang, Zhiming Ma, and Wei Chen. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. The Thirty Sixth Annual Conference on Learning Theory, pp. 161-190. PMLR, 2023.
10

---

Published as a conference paper at ICLR 2025
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Advances in Neural Information Processing Systems, 15:15511-155211 2020.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint arviv: arXiv: 1905. 2019.

---

Published as a conference paper at ICLR 2025
A MISSING PROOFS IN SECTION 2
A.1 1 PROOF OF LEMMA 2.2
Let x, y Rd be arbitrary and let : # (otherwise the claim is trivial). Then, for any E [0, 11, using ( we can estimate
(VV/(=th)-v//00) - ||b]| / [IV f(++hi)l S |1b|1| J. (Lo+LilV//(++>>)))) x(1).
Our goal is to upper bound x(1). We may assume that L1 > 0 since otherwise x(1) = Lo LoIl and the proof is finished. Differentiating, obtain, for any E [0,1].
x() Lo ||]||| + L [[]I|| + th)ll S (To + L, V ( + L,]lb|x(()),
where the final bound is due to the triangle inequality and the previous display. Hence, for any t [0, 1]. have
d + 2z
+ [111|x((0] L1
dt
where >> O is arbitrary
Integrating this inequality in / E [0. 1] and noting that x()) 0. we get
In Lu + [ + L1((1) S Li |/b]].
To [/
or, equivalently,
ebillAll= -1
x(1) S (To + [[V](()]] +c)
L1
Passing now to the limit as + 0, we obtain B
Let Rd be arbitrary points and let h == -. Then, using 3
we can estimate
(f(w) - f(x) - (V (V))())))))))))))))))) x>) / [V + th) - vf(x),
(To + La | /
c Illl - dl (To + T [
L1 hh| -
L1
L
which is exactly
Let us fix an arbitrary point x e Rdd and an arbitrary unit vector h E RRd. Then, for any O. follows from 44 that
cht Lit -1
[s + th) (x)) (VS(()) < (Lo La [V((((
I2
Dividing both sides by f2 and passing to the limit as - we get
(2) < Lo + L, [V/x)]]
This proves since the unit vector was allowed to be arbitrary.
A.2 PROOF OF LEMMA
Proof of (5). Let x, Rdd be arbitrary points and let us assume w.L.ogg that L1 0. In view of the convexity of of and (4), for any h E IRd we can write the following two inequalities:
0 < f(y ( (x) (VI(x),
x) S By(x, + (VS Vs()). Lo + (
T & ((LI)))))
This additional term is needed handle the possibility of To T.IlV((a)) being zero
12

---

Published as a conference paper at ICLR 2025
where By v) f(y) f(z) - - z). Denoting a Lo + Lillff(y)
0 and
8 = Vf(y) - Vz(x), we therefore obtain
8y(x, max hER
(s, h)
(LI
[|s||r | r20
T [Lir)
a
(
T
a
[Proof of 6 Summing up 5 with the same inequality but and y interchanged, obtain 6
[Proof of
By using lower bound (~(7) 2
277 in and denoting = =VV[(a) v
and
[w))), we obtain
f(v) 2 f(x) (Vf()) Lo + Lig
L7u²
Le + Lıg 2(L L1g) +
Li
(Lo L1g)
a²
= f + (VI()), - x) 2(Lo Lıg) +
A.3 EXAMPLES AND PROPERTIES OF (Lo, L1) SMOOTH FUNCTIONS
Let us present a few simple examples of (To, I1I- -mmoshh functions.
Example A.I. The function fz) = || where p 2, is (Lo, Li)-moooth with arbitrary 1 >> 0
and Lo (
Example A.2. The function f(x) = In(1 + e*) is (Lo, L.) smooth with arbitrary L E [0, 1] and Lo [1 2
The preceding examples also show that the choice of To, La parameters is generally not unique. While we cannot guarantee that the class is closed under all standard operations, such as the sum- mation, affine substitution of the argument, we can still show that some operations do preserve (Lo. -mmoothhssssss under certain additional assumptions.
Proposition A.3. Let f: Rd + be a twice continuously differentiable (Lo, Lı)-smooth funcetioo Then, the following statements hold:
1. Let g: Rd + R be an L-smooth and M M-Lipschitz twice continuously differentiable functioo Then, the sum f g is (Ig, -mooohh with Li Lo + ML + and Li Li.
2. Let fc: Rdd - R be (To, -smmooht function for each i = 1...., Then, the function ., x d + R given by h(xx) = -i=r fi(x;), where = . In). is (Lo, L1)- smooth with Lo = maxisign Lo,i and L1- = maxigisn L1,5.
h: Rdd X x...
3. If f is univariate (d = 1) and hxxx) = (((,z)) + b). x E Rd, where a E IRd, b E R. then is (Ly, -.)-mmothh with parameters L - ||a| and Lí = [|ll
4. Let additionally 4 f(x) for all x R2d and f be 1-coercivd Then, f is (Lo, -mo-sh iff its conjugate fo (which is, under our assumptions, defined on the entire space and also twice continuously differentiable) satisfies 2 f.)) = Totta [a]| T for all E Rdd. where I is the identity matrix.
One simple example of the additive term y satisfying the assumptions in the first item of Propo- sition A.3 is an affine function (for which L = 0); another interesting example the soft-max function g(x) = plnn m alta..))+bll/ where a; Rd. b, E R. μ > 0. Based on the second i-1
statement of Proposition A.3 and Example A.1 the function f(x) 1 ||=1|p = Ed |a, with
p > 2 is (Lo, L1 -smomhotth with arbitrary Li
0 and Lo = (2 p-2 Using the third statement, can generalize Example A.2 and conclude that f(x) In(1 + ((a.))) is also (La, -mooshh with arbitrary L E [0. ||a]]] and Lo = [1aal] - L2)2. Also, we can use the last statement of the proposition to show that (a:) 2 og (TT[[
Lg [للا| || 1) is (Lo, Ia -m)-shooth since
the Hessian of its conjugate (s) L7 (
Lallell = L [11 Lellll| In(1 + Lille
Lo )
L, [|ell] has the
Lo
Top
L.g
*hhis means that
f(x) |
+00 as || co.
13

---

Published as a conference paper at ICLR 2025
form f4)ss Lu+ I. In particular, we can construct an (Lo, Lss-sootth function by taking any convex function h.s adding o, and taking the conjugate (this corresponds to the infimal convolution of h with Φ).
A.4 PROOF OF A.J
Proof. Differentiating, we obtain, for any x: E Rdd
vf(x) | -1=1)_1 f'a()= [ 1|=1|0-~ 1 (+ (p- 2)
(1+
Z.F'
|
where is the identity matrix. Hence, for any I, > 0, the minimal value of Lo satisfying the inequality from Definition 2.T]is given by
Lg max SE
zERd max { (p 1)||=|11-2 -1||=||-11}
-mx (p 1)7 (p-1)7= L17}.
720
The solution of the latter problem
7" = (P-2)p0 p-1 Substituting this value, we obtain
Lo = (p- p- 2 p-2
2 p-1
(P-2) P-p-2 p-2
11
L1
11
11
A.5 PROOF OF EXAMPLE
Proof. Differentiating, we obtain, for any x E R,
e
f((x) 1t (0,1), f"(x) (I+e f0)
Thus, for any L1 E [0, 1]. the minimal value of Lo satisfying the inequality from Definition 2.1
Lo = ZER (z)) L (x)]=))]
max {r(1 7) L
rE(0,1)
max ((1-L1))) - -2}= = 71 L1)2. rE(0,1)
A.6 PROOF OF PROPOSITION A.3
Proof. [Claim 1] Since, g and Vg are M and L Lipschitz continuous, ||Vg(>)|| g, then, for any Rd we can estimate
< M and
[V*g())) < L for all R. Let F
|[ < (() [<> - Lo + L [=(
L +
(Ln + L, M + 4
[Claim 2] Notice, that the gradient of / is V f(xx) (V/((z)) ..... ()n(Zn) and the Hessian of f is (²((x) is block-diagonal matrix, with (1.) blocks. Thus,
| [(x)]] = max
\ < max LL. + LI (((())) Isišn
max (Lo L Vf))| < Isis
max Lo,5 + max ())=)(
1si5n
[Claim 3) Observe that the gradient of function is Vf(x) g'(la, x)) + b)a, and the Hessian is V² = g" (((aa 2) + b)aa Hence,
2 f(x())] (g"((a, x) + b)]l|||2 < (Lo + ( + +a
Lolla|| - |||||| [+]]]]]
14

---

Published as a conference paper at ICLR 2025
[Claim 4] Under assumptions, fx)) is one-to-one transformation from R to R (whose inverse transformation is x = V.. f. (s)); moreover, the Hessians at such pair of points are inverse to each other: V f. (s) [V2 fz)] (see, e.g.. Corollaries 4.1.4 and 4.2. in (Hiriart- Urruty
& Lemaréchal 1993 as well as Example 11.9 from (Rockafellar & Wets. 2009)). Thus, for any pair of points I, IR such that
Vf(x), assumption [v=] S Lo L1 [())
which, due to the convexity of f, can be equivalently rewritten as f() = (Lo + L ( equivalent
s+)) (v<))
Lo + La [Vfail
Lo + L1|ss
This proves the claim since the transformation
fx(x one-to-one.
A.7 PROOF OF LEMMA 2.3
Proof. [Claim 1] Indeed, for any t E [0,3), we have
2
1
12
1
<(t) = - -t-1=
i!
2
+ i)!
2
2
3
2(1
9
1=
1=0
1=0
1=3
==
Similarly, for any t 220,
20
12
1
(1) = 2 i=0
j=3 5
2
i!
2
1=
[Claim 2] By the definition, for any 7 2 0, we have
(.)7) = max(nt <(t) = m
+
120
120
Differentiating, we that the solution of this optimization problem is to In(1 + 7). Hence, (.(7) = (1 7) In + 7) + +1= In + 7.
[Claim 3] We first show that, for any 7 2 0,
27
In(1 + 7) 2
2 2+
Since both functions coincide at 7 it suffices to verify the corresponding inequality for the derivatives:
1
1
1+7 (2+7)² 4+ 4+ + 1 1+7+7 x2
But this is obviously true. Applying the derived inequality, we get, for any 7 0,
(.) = 71 + 2 27(1 +2) 7/2(1 + +2) - (2+
722
+
2+7
2 +
which proves the first part of the claim.
z coincide at 7 = 0. Hence, it suffices to check the For the second part, we note that (7) and 2 corresponding inequality for the derivatives, i.e., to verify that, for all 2 0,
d.(r) In(1 + +7) S.y
But this follows from the concavity of the logarithm.
B MISSING PROOFS IN SECTION 3
B. ONE-STEP PROGRESS
Lemma B.I. Let ʃ Rd + R be an (Lo, Li)-smooth function, let E Rdd, and let T(x)
I V fx),, where n is given by one of the following formulas:
L.lVf(x)) ((0)l
(1) 17.
In 1+
(2) Tsi Lo +
Lo
(3) na min
2L 2
15

---

Published as a conference paper at ICLR 2025
Then,
a [[f])))
f(z) - ((T))) 2Lo + 3L, Vf(=))l
where a = 1 in cases (1) and (2), and = in case (3).
Proof. [Case (I)) The proof of this case was already presented in Section
For the other two cases, we start by applying Lemma 2.2 to get
Lo + L1 [x())
A f(x) f(T(z)) 2 (Vf(x), - -T(x))
o (LL))T(()) ==l)
Lo + L1g ((nLL19),
=
1,
where g = [V(( and ((1) = c² -t 11
[Case (2) Estimating ((1) I
3/a
I
1
(Lemma 2.3 and substituting the definition of 7/si we
6-21
2-1
can continue as follows:
Lo Lig T L2g
(Lo Lig)mal
2 17619"
16619"
1 2 - Biiig
2 7si Lig
(Lo + (11 (2
1
Lo - Lig
g²
g²
Lig Lot $419
Lo + Lig
2L0 + 3L19
[Case (3)] Observe that
1
S 1el
2 3L.g
max (2 3Lig}
Lo + Lng
Combining these bounds with d(t)
31a (Lemma
2.3
(1)), get
Lo + Lig
3L
3 (Lo + Lig)
A 7e19²
"ag
1,3
Maann
6-21 L.g
3(In + Lig)
g2
(Lo + b1))
2h19
2Lo + 3L1g
Lo+
3(o + L19)
g²
1
g²
6Lo + 7Lig 2Lo 3L1g
2L + 3L19
Lemma B.2. Let f: Rdd + R be a convex (To, I-)-smooth function, let E Ted, and let T()) be any of the update rules from Lemma B.1 Further, let x" be a minimizer of f. Then,
((()) x11 S 1 xx
Proof. Denote 3 (V](r)) x and g = (x)]] According to the update rule T(.), we have
[[T(z) x = || x 2n + n1²9²
Therefore, to prove that [[7(x) - x²| < | xx 1|2 we need to show that
ng² 23.
Applying bound 77 twice, we see that
f(x) - -()) (Vf(x) - =x]
Br = (1)x)-f11
9²
9²
g²
2 2Lo 3L19
>
2Lo + Lig
Lo + Lig
where the final inequality follows from the fact that 1 need check if
+> + atb (convexity of i> 1). Thus, we
a
2
1) 5
(22)
Lo + Lig
16

---

Published as a conference paper at ICLR 2025
Furthermore, it suffices check this inequality only for the largest among the three stepsizes consider. This is the stepsize 1f (see (44). Applying In(1 + 7) $ y (which holds for any y 2 0), see that
In ( In(1
Lo + 2I9)
Lig
1
Lig
Lo + L1g
so indeed satisfied.
B.2 PROOF THEOREM 3.1
Proof.
According to Lemma
B. for any & 2 O, we have
(xx)1 f(xx) - f(*++1) 2Lo + 3L, V f(xx)ll
where a is absolute constant defined in the statement depending on the stepsize choice. Denote
fu = f(xx)= - f (2 0) and Oh = [[V this notation, the above inequality reads
72
f 2 ap()))
(())
2Lo +L117
Summing up these inequalities for all S k S K and denoting gK = minosAsK ge, we get
Fo 2o - fK 2 a (Gg)) 2 a(K 1)k()))
where the final inequality holds since & is increasing function. Denoting the corresponding inverse function by 1 we come to the conclusion that
Fo aa(++1) + Sc
9K S -
whenever
Fo a(H K +1)
S (b(()),
or, equivalently,
Fo axp(c)
= 2o.Fo
3L1Fo
K +
ac
B.3 PROOF OF THEOREM 3.2
Proof of Theorem 3.2
Let 2 be arbitrary and denote far = f(zx) f and gs = |f(x))]]
According to Lemma B.1 we have
72
fa - fet1 2 ab(gk),
((>) = 2 + 3
where a is an absolute constant defined in the statement depending the stepsize choice. Further, according to Lemma B.2 the distances R& == || I=1| are nonincreasing. In particular, R& S estimate
Ro R. Henee, in view of the convexity of f.
f S (Vf(=x), 2x - x²) I Ry S R.
Combining the above two displays and using the fact that the function vp is increasing, we obtain
fx
Sk Sk+1 and
R
Consequently,
a < fx. fk+1
9hh f1x
fn n
22
+ 3L1R
()(
fen
(1))
fu
12
1
1)
fR
2T R?
+
3L,
Rln
fr+l
Fx
Fr+n
17

---

Published as a conference paper at ICLR 2025
Summing up these inequalities for all 0 S k S K - 1 and dropping the negative Jo term, get
ak v RL
+ 3L2 Rin fo fK
fK
Hence, fx S E whenever
2o
3 RIn +L,,,
fo K(e).
K>
ac
To upper bound (e),, first estimate fo using Lemmas 2.2 and 2.3
Lo
Lo 4.
fo S
(L)
1
2
This gives us
(<(() - RL + 3., Ln R + R
RL
+ +3 R222 + 6L, Rln (v LoR
Estimating Int S (holding for any t > 0) and applying the AM-GM inequality, we get
aK(c) S LL
RoRe
(2 + LoR + (3+ - [L,
3[, eV
R|,
C MISSING PROOFS SECTION
4
C.I GENERAL RESULT
Lemma C.1. Let { ) be the iterates of NGM (5) with arbitrary coefficients 3x > 0, as applied
problem with an (Lo, L1) Li)-smothh convex function f. Then, minoskeK f(xx) f S for
any given K 2 0 and > whenever
Rº O
O
3 < 5(e)
= min
3
2 2 3x
2TA
T
where = Iz x² is the distance from the initial point to solution x² of the problem.
Proof.
According to 11). for any A O, we have
|| 1|2 | 211 21/ (V 2* x²) n (xx))
. - x 1| 2B 3
where Uy (V((z))mz [V](x)]
0). Summing up these relations over O,...
, K and rearranging
the terms, obtain
K
K
3 <
R
+ 32
k=0
k=0
Denoting uk minogkgK Uk. we get
R K
32
k=
= 8k.
(23)
K
3k
==
Let f% = minogesk fxx) Then, by Lemma 4.2
fk max(f(z)
f" 112--0" x²1l S vk}.
Applying Lemma 2.2 and the fact that d(t) <
31a
for any (0,3) (Lemma 2.3 we obtain
6-27
La
3Lo )2
S 8 <
o
(Lak)) <
I
6 - 2
18

---

Published as a conference paper at ICLR 2025
whenever Lun < 3. To achieve the desired accuracy it thus suffices to ensure that the following two inequalities are satisfied:
2L1uk S 3,
Lo(uk) Se.
This is equivalent to
3
c
u/2 S min
= ō(e).
-2L1
Lo
and follows from 8 S 8(c) in view of (33
C.2 PROOF OF THEOREM 4.1
Proof. According to Lemma
we need to ensure that
R
Σ
K
3
k=0
S
5(c)
min
2
k= 3k
21, V
Lo
In our case,
R R
R
6k 2R K +1 VK+I
Therefore, óσ S 8(e) iff
R2 (2(()
(4
Lofe
K 11
= max
C.3 ANALYSIS FOR TIME- VARYING STEP SIZE
Theorem C.2. Let { be the iterates of NGM (15), as applied to problem smooth nonlinear
( with an L1)-
o convex function f. Consider decreasing coefficients 3x VK+T
R k 2 0, where
R >> 0 is parameter. Then, minogksk (xx 1 for any given e whenever
K + max ANR(E), (=-T) - (N
where R R= 1( RR), == 1120 x² (x* is an arbitrary solution of the problem), and
No(c) max [L, D2
Proof. According to Lemma C.1
we need to ensure that
R²
K
< 8(e) = min
2
K 2Σ
3k
22,
Lo
For our choice of 3e. obtain, by standard results (e.g., Lemma 2.6.3 in Rodomanov (0022 ) that
Σ
1
fe In(K 1)],
Σ
BN
N
Σ
PVK+1 +1.
Vk
k=0
Hence,
R² + R + In(K + +1]
R
Rln(K)) +1)
ōk <
2R
VK+1
2VK
To ensure that 8x 6(e), suffices to ensure that the following inequalities are satisfied:
8(c)
Rln(K +
< 5(e).
K
VK +1
2.2 This means that Ta + [()) 0 for any E Rd Lemma
19

---

Published as a conference paper at ICLR 2025
The first inequality is equivalent to K+1 to Lemma
4R-
To get the second one, it suffices to take, according
C.3 (with p and 8'
[[el] PR_
)
c 2R 8(e)
2R
2
R2
4
K+1
In
In
8(e)
c
(2(()
(²(c)
Putting these two inequalities together and substituting our formula for 8(c), we come to the require- ment that
4R
2
R
4
12)
K + 1 max
In
1 e (2(c)'
(2)
82(c)
max (oox(410) (/N((e), (e-
(t(e)) In)NN)
where
D²
4 {
L
ND(e) = (c)
Lemma C.3. For any real p. we have the following implication
In
i 1
S
pd
1
Proof. W.l.o.g,, we can assume that p and our goal to prove the implication
[n 3
<(t) = Int
t(6)
6.
5
f
The general case then follows by the change of variables f = (t')² and 8 = po'.
Further, we can assume that 8 < since otherwise (tt) < / S for any 2 0 (since the maximum of & is achieved at 4, = e). Under this additional assumption, [In } In
since ó ). Since the function is decreasing Let us now assume that t(0) 2 ب the interval +00), we have
In (()) In 1 ((t) S o(t()))
8.
t(8)
- In
To finish the proof, it remains to show that the final fraction the above display is S 1, or, equiva- lently, that
t(0) = e In 8
Rearranging and denoting := (t) o-1,, see that the above inequality is equivalent to
In u
suu)
But this is indeed true since o attains its maximum value at
D MISSING PROOFS IN SECTION
D. PROOF OF THEBREM 5.I
Proof. Let x" be an arbitrary solution. By the method's update rule and convexity of f()), we get, for all k 2 0,
| 2=1 = || - 2²1 - 2mk (V f((x).)).))). 24 x²) + m [f(2))1
< | x x01 [f(xx) fop
[
Foror & we define by continuity
OC.
20

---

Published as a conference paper at ICLR 2025
Denote Rg: | x=11, 9s
and fo f(xx) - f" According to Lemma 2.4 for [[vf(=))]
each A 2 0, holds that
g²
Ju 2 (gt);
where ((g) 20 + 3Lg 2 0.
Observe that the function v is increasing, so its inverse e 1 is well-defined and is increasing as well. In terms of this function, Ok I Φ (fk) and hence
R R
9k
Summing up these inequalities over 0 S k v K and rearranging, we get
K
2 I R
Σ
R
R
Note that (0) is increasing in t (as the composition of increasing in y function M(*) 33 with increasing in t function y = (t). Thus, by taking a minimum over the terms on the left-hand side of the above display and denoting fk minosksK fae we get
?
fk
(K 1)
S SR²²
Rearranging, we obtain
((k) VK+ Kf
or, equivalently,
VK + 1fk
(K + 1)
(fk)²
fk 2 16
R
R2 (2Lo 3L, vK+15j
2L
VK+I $1
K+1
Hence,
2 KK (K+1)(1 3L, BL,KKK1]
fK S
whenever 3L, RV K + < 1. Thus, to achieve desired accuracy > O, the number K of iterations should satisfy the following conditions:
RL
3L, RLIRVK+SS 2'
K +1 S
Thus, the final iteration complexity is K +1> max
R2a
[6L 1133].
E MISSING PROOFS IN SECTION 6
The proof of Theorem 6.1 is similar to the original proof Theorem in (Nesterov al. 202I). but, instead of the Lipschitz-smoothness of f, we use the definition of M..
E.1 PROOF OF THEOREM 6.1
Proof. Let us prove by induction that, for any & 2 0, we have
Axf( S c == {x(w)).
(24)
This trivially holds for i 0 since Ao and C 0. Now assume that (24) is satisfied for some k 2 0 and let us prove that it is also satisfied for the next index k'' = k + 1. We start by noting that
Sh+ (v+1(1 = (c(Ux+1) + (f + (V u - yk>!
2 G$ | -vll 2 + a 1 [ (vx) (V f U vk
2 (xx(xx) + - |11011 val 2 au | (ww) (VI(v)), vn+1 -Ma>),
(25)
21

---

Published as a conference paper at ICLR 2025
where the first inequality holds due the strong convexity of Çk. and the second one is due to the induction hypothesis. Further, note that, by construction, yk E [Uk, øx]. Considering separately any of the three possible situations, yk Uk. Us 2g and yk (t),
that, in all cases,
(v)())) yb? 0. Substituting this estimate into 25 and using the fact that f(()k) f((ak)) (by construction), we obtain
C 2 Axf( + ax+If(U)) + ||0k+1 uxl1 + ax+1 (V (2):); Uk+1 - uk)
+ Aut1((yk) + ||o0+11 uk ax+1 aaxti (V])( uk+1 vk)
2 A ax+1 2
V [ Aut1 [(v=) 2M
[V
where the final identity is due to the definition of Mr. while the preceeding one follows from the definition of ax+1, which ensures that
Mc0 = Ak+1-
(26)
The induction is now complete.
Let & be arbitrary. By the convexity of f and the definition of Ak, have
k-1
C s (x((")= = R²
Σ a aatilf(())
(V(()), -vill s R² + A&t"
where = ||:0- - x²||. Combining this with 24 we conclude that
R²
f(xx) f S
(27)
2A₁
remains to estimate the rate of growth of the coefficients Ag. From 26 and the definition of Agt1, it follows, for any k 2 0, that
A M
ax++ AR+1
A = (VA + VAa)( A+T1 VAu)
<2/ARt1 Akt1 - VAt).
Cancelling / AA+1 on both sides and telescoping the resulting inequalities, get, for any 1.
A
Σ M,
Substituting this estimate into (77.. we obtain the first relation in 19 The second one follows trivially from the definition of M, and the fact that f(y)) fxx).
E.2 PROOF THEOREM
Proof. Let & > 0 be arbitrary, and denote fa = [(x) f and ga = |V/(})]] According to
Theorem 6. we have
2R22
g
fe+1 S c
fx fk+1 2
A
2
2M
where M₁ that
[Vf(ve)) | 31f1v))f((ee))
Further, from the fact that Ft+1 Ty(x)) and Lemma B.1 B.1
we know
2Lo + +L1gg
Mj <
=
(Lo + +L/g);
2a
2
22

---

Published as a conference paper at ICLR 2025
where L/ == Lo. L1
L1, and is defined in the statement. Thus,
(R))
SN fu+1 2 g
fk+1
1/ + 1498
where R² = 2R. Applying Lemma k (()), where
E.1 we conclude that S S e for a given 0 < e S fo whenever
K(6)= = (R)
2/0
(T)
log2
6(2 Ta) (2R)2
13/33 (13 (2R)
2//9
logg
2fo
48 R2
250
(1 2/3
log2
ac
To estimate the oracle complexity, it remains to note that each iteration of the algorithm requires exactly one computation of the gradient plus most oracle queries for the line search. Hence, the overall oracle complexity to compute is most (v 1)k.
Lemma E.1. Let (fu) (gk) be nonnegative real sequences such that, for any &s 2 0, the
following inequalities hold:
R
2
fk+1
fu fu+1 2
Ei= VLo
Lo + Ligk
where R. Lo, L1 2 are certain constants, and Lo + Ligk > for all & 2 0. Then, for any integer k 2 0 and N 2 1, it holds that
RL
3(,
fu+N S 2N
2N3 fk.
Consequently, fu S for a given << fo whenever
R2
2fo loga
k
[3//3 (L,
Proof. Let k 2 0 and N 2 1 be arbitrary. Denote JN.N = A Σ
NNN
Dt. Then, dropping part of
the nonnegative terms and applying Jensen's 's inequality to the convex function 7 + /F> we see that
k+N-1 1
k+N-1
N
VTo T1g:
Vla Toih
VLo LIēK,N
kmk
Hence,
futN (To + L
N
Our goal now is to estimate how fast HN,N grow.
According to our assumptions, for any 2 we have Si - Set1 2 (gg)), where vh: [0, +ox) IR.
52
is an increasing convex function (gg) LotL.g' Jensen's 's inequality, we obtain
Summing up these inequalities and applying
k+N-1
fn SKAN
Σ
((a:) 2 No (2 0).
i=k
Hence, JK.N S 4-1
se- (I--(eNN, where 1h is the inverse function of vh. Consequently,
[To + I
feAN R
futN x
N
23

---

Published as a conference paper at ICLR 2025
Note that, for any 2 O, we have 20 (7) = Lor + + + 2017 S vLo7 + LIY, whenee
3
La + Lib (7) S La Li Lo7 L17) = Lo Li7 + LoLir
z( + Li7).
2
Thus,
3(Lo + [3 fa- - RR
3l R2
3(L
fR+N I
+
(fx fk+N),
2N2
2N2
2N3
which proves the first part of the claim. Applying now Lemma
E.2
conclude that fx S for given 0 c S fo whenever
4 LoR
2
+ - (L)
log2
R2
2fo
(3)
logg
Lemma E.2. Let (fw)k be nonnegative sequence of reals such that, for any integer k 2 0 and N 2 1, it holds that
fu+N S N2 No. Sk.
where B 2 0 are certain constants. Then, fo S cfor a given O < <c fo whenever
4a + (233) logg 2fo
k
Proof. We assume that B > 0 (otherwise the claim is trivial). Let N₁ = ((23)1/8 ( 1). Then, for any t 2 0, we have
B
1
fR+N.
S
fa -
2 fm.
N
N
where A = <
Applying now Lemma
E.3 to the subsequence (JN,)) obtain, for
N?
(28)273
any 2 that
JNL 2A
2 fo-
Hence, for any 1 2 and any N 2 1, it holds that
fNINN < Therefore, to ensure that fNA+NN it suffices to satisfy the following three inequalities:
3
JNN. <
23
+
f
a
+
f
N2
N3
N2
N3
N32
N2
N
N32
2a
Bfo
N
2 N1,
N2
2
N32
Note that, for each 2 Ni. we have it suffices to ensure that
8 N
<
Hence, to satisfy the above three inequalities,
N
N 2 max / 4a
Aer Ni] N2,
7 loga fo
We have thus proved that fx < whenever k 2 N.T + N₂. It remains to note that
NT + No < NI +1)++
4a
1/3
1/3
[oog
2fu
4a
where we have first estimated the maximum by the sum and then used the fact that [log, 7 + 1 [loga 7 1] = [log2(27) (2r)] for any 2
24

---

Published as a conference paper at ICLR 2025
Lemma E.3. Let (mk))= be nonnegative real sequence such that, for any k 0.
7i++1 S A + 9ik,
where 2 and q [0, 1) are certain constants. Then, for any k 2 1, holds that
9th 7k -
A
+ 70-
Proof. We can assume that q > 0 since otherwise the claim is trivial. Dividing both sides of the inequality from the statement by gh+1, we obtain, for any & 2 0,
Yk+1 ++I
g+1
9*
Summing up these inequalities, we get, for any 2 1,
Σ
1
4
g
-1 A 70.
9
70
70
1
1
and the claim follows.
F COMPLEXITY OF NAG
Unfortunately, the NAG algorithm presented in (Li et al.
2023) not scale-invariant and its com- plexity reported in (Li et al. 2023] Theorem 4.4) is not written explicitly. To streamline the com- parison of the complexity bound for NAG with those for other methods for minimizing an (Lo, 41)- smooth function, we provide a simple fix making the algorithm scale-invarial and also rewrite the result of (Li et al. 2023 Theorem 4.4) (assuming it true) an explicit form.
Theorem F.1. Consider problem ① with (Lo, Ia -mooohh convex function assuming Lo 0. Let NAG (L 2023 be applied to solving the rescaled version of this problem:
1 Tn -00)
i = min =ER
-
[(x)
starting from a certain point Zo E Rd. Then, for an appropriate choice of parameters, NAG finds a point Rd such that f(i) - f I E for a given iterations / grudient-oracle queries:
after at most the following number of
128L3
Fo LoR?
16 128L +
+ +1)
Lo
where Fb = f(xo) fr, R 100 x²1l and x² is arbitrary solution of our problem.
Proof. By construction, f is an (Lo, Ln -mmoth with i. = and i. = I1- In the terminology of al. 2023), this means that is f-smooth w.r.t. the function
(G) = Lo L= L.G.
Theorem 4.4 from Li al. 2023 then tells that the sequence of the iterates {a,) constructed by
NAG satisfies
4(8, + 12.) 1yt2 +
- -(
(28)
where Fo = f(x0) - fra ||10 x²1l and 1 > is the stepsize parameter required to satisfy
1
n ~ min 16[((2G))²* 2((2)) 16[((2G)]
(29)
16(1 + 2L,
where an arbitrary constant such that
G > max(8y (F + R²),0o}
max(8y (F. R22,
(30)
25

---

Published as a conference paper at ICLR 2025
where [
In terms of our original function f. the guarantee 28 reads
4(Fo + Lo1l²)
St = f(x))
-
1/22 +
To achieve the fastest possible convergence, select the largest possible stepsize v which is, cording to (29
1
16(1 + 2L G)²²
Substituting this formula into the previous display and dropping the (useless for improving the con- vergence rate) constant 4 from the denominator, obtain
fe 3 64(1 + (Fo LoR
SE
12
whenever
Fu + L
1 12 8(1 2L,
t(c).
(31)
The obtained t(c) is exactly the iteration complexity of the algorithm for obtaining e-approximate solution for the original problem, and is also its gradient oracle complexity since the method makes precisely gradient-oracle query at each iteration.
remains to choose the smallest possible parameter G satisfying 30 inequality in terms of the original function:
We start with rewriting this
G 2 max f /v (1+ (1+
Fo Ln
9o Lo
9o max V(++2(GG)
+ R2
L
where go = Vf(xo)) and 64( Fa + R This inequality is equivalent to the system two inequalities:
G (1)
90 G2
Lo
Rearranging, we see that the first inequality is equivalent to
G A 2 + LA=
Further, it turns out that G. 2 Lg Indeed, according to p7) we have Fo 2
2Lo+3L1g0 meaning that
of
9o $ 2L + F + 3 F. S Fu + 3L2 Fu; on the other hand, estimating
64F%
Lo
we see that Lo(VA+, > 8 + Thus, the smallest possible value of G satisfying the original requirement (30) in fact G G..
Choosing now G G. and substituting the definition of A, we obtain
G2 2(A + L3A3) + 21 2(1 + 217A) =2(1+ + 128L + 128L3R2)
1+ 2L, G
A
A
Lo
Substituting this bound into we obtain the claimed bound t(c).
G NUMERICAL RESULTS
In Fig. compare the performance of the analyzed methods for solving optimization prob- lem with function f(x)) p
|| We fix T, 1 and choose Tap (2-2)p-2 according
Example For GM, choose stepsizes according D 12 and 13 For NGM, we use time-varying coefficients 3x = Æ-I with different values of E { 2R, 10R), which allows us to study the robustness of this method to our initial guess of the unknown initial distance to the solution. Note that, for this particular problem, the choice of R R is rather special and allows the not considering it. We observe that,
method to find the exact solution after one iteration,
26

---

Published as a conference paper at ICLR 2025
Convergencee
Convergence
Convergence
(140
Jance
Number Raratiena
atons
(a)
(b) 6
(c)
Figure Comparison gradient methods for f(z) p | 3-NGD stands for Normalized Gradient
Method, where is an estimation of the true initial distance to a solution R. TD- rf* of stand for gradient method with stepsizes method, and AGMsDR stands for Algorithm
and 13
respectively, PS-GD stands for Polyak stepsizes gradient
Convergence
Convergence
Convergence
3.0
4.=10
4 1.5
2,0
2.=20
4.2
6-40
--00
1y 36.0
16.
304
16
Koratonss
(a) p 4
(b) 6
(c) p
Figure 2: Convergence of the gradient method on the same function but with different choices of (Lo, L1).
NGM and PS-GM outperform GM with stepsizes from (9 and 13 This can be explained by
the fact that the complexity of GM depends on the particular choice of (Lo, L1). while complexity of NGM and PS-GM involves the optimal parameters La, L discussed in Section f Moreover, closer initial distance estimation N to a true value leads faster convergence of NGM solution.
In Fig. 2 present experiment studying the performance of the GM with the stepsize rule ( based the choice of (Lg, L1). For each choice of L1 {1, 16) we set I. (%r jo- according Example A.I As expected from the theory (see the corresponding discussion at the end of Section 4. the choice of (Lo, L1) pair is crucial in practice for the performance GM and depends target accuracy
In Fig. 3 we conduct an experiment for accelerated methods and consider GM with stepsize P Algorithm 1 with T(-) being the gradient update with stepsize (9). and two variants of normal- ized Similar Triangles Methods (STM, and STM-Max) from Gorbunov et al. (2024). STM uses normalization by the norm of the gradient the current point in gradient step, while STM-Max normalizes by the largest norm of the gradient over the optimization trajectory. It is worth noticing that only STM-Max has theoretical convergence guarantees. We set Ln = 1, Tug (2-2) (see Example A.I with various p. We observe that for smaller values of p. Algorithm outperforms STM and STM-max.
Convergencee
Convergence
Convergence
STM
5TM
01:03
Number Berstiane
Nammer ctftendiore
Nurterr becations
p 4.0
(b) 6.0
(c)
8.0
Figure 3: Comparison of Algorithm| [ denoted by AGMsDR with Similar Triangles Method (SMT) and Similar Triangles Method Max (STM max) for f(x) = =| with different values p.
27


Reviews:
[{"review_id": "arkYVX48mO", "reviewer": "Reviewer_qpgv", "summary": "This paper provides a general understanding of the $(L_0, L_1)$-smooth function class, which has recently gained increasing interest due to its empirically observed connections to deep learning applications. They authors establish a parallelism between the classical optimization theory for $L_0$-smooth functions, and show how analogous inequalities and algorithm design strategies should be carried out with $(L_0, L_1)$-smooth functions. This includes the derivation of $(L_0, L_1)$-smooth version of the cocoercivity inequality, analysis of fixed-stepsize gradient descent method for convex and nonconvex cases, and analysis of gradient methods using normalized stepsizes, Polyak stepsizes, and Nesterov-type acceleration for convex functions.", "questions": "Writing issues (in the order of appearance)\n- In pg. 3, lines 108-109, it will be illustrative to explain in more detail in which aspects the authors' proof techniques differ from that of the work [1], cited as Gorbunov et al. (2024) in the manuscript. Also I think the authors should be more cautious about claiming that the proof is more \"elegant\" than something else. One possible suggestion is to emphasize their clearer parallelism with the classical theory, rather than to describe the value of this paper's framework with a subjective expression like \"elegant\".\n- The statement of Lemma 2.2 involves the notation $\\phi(t) = e^t - t - 1$, while its proof in the Appendix uses the symbol $\\phi$ to denote something else. Please change it.\n- The bound $\\phi_* (\\gamma) \\ge \\frac{\\gamma^2}{2+\\gamma}$ appears suddenly in the statement of Lemma 2.3, while the relevant discussion appears later in Section 3. I think this should be relocated to somewhere near Lemma 2.3.\n- In pg. 4, lines 164-165, the meaning of the sentence \"we present some examples to support the choice of generalized smooth assumption\" is unclear.\n- Proposition 2.6 and the subsequent discussion doesn't seem very relevant to the rest of the paper. To some readers this information could be valuable, but generally speaking, I even think the whole part can be moved to the Appendix without altering the flow of the paper. Also, please clearly define the expressions like \"$M$-Lipschitz twice continuously differentiable\" before using it.\n- In line 183-184, there is dangling \"for some\" after the period.\n- In Theorem 3.1, it should have been assumed/defined that $f^* := \\inf f > - \\infty$. In general, the authors did not properly state that they assume the existence of a minimizer $x^*$, etc. (in subsequent theorems regarding convex cases). Please be precise about these points.\n- In the statement of Theorem 3.2, is $||x_0 - x^*||$ intended to be denoted as $R_0$?\n- In pg. 6, in lines 297-298, it is not clear what the authors mean with \"by using the preceding estimate and the update rule of the method\". Only after reading the proof in the Appendix I could understand the technique deriving equation (20), and I still do not feel that the text surrounding the equation is successfully conveying the idea. If you intend to provide a high-level intuition, please be more precise and detailed. Also, note that the exponent 2 is missing in $R_{k+1}^2$ within (20), and in equation (43), the $g_k^2$ factors seem to be missing.\n- Lines 304-310 provide an interesting insight on the complexity $\\mathcal{O}(L_0 R_0^2 / \\epsilon + L_1^2 R_0^2)$, but I think the complexity analysis does not clearly show that the constant $\\mathcal{O}(L_1^2 R_0^2)$ complexity corresponds to the phase where the algorithm reaches the regime where $f$ behaves like a smooth function. (Which is in contrast with Section 6, where the algorithm is deliberately designed in this way.) Can this discussion somehow be made more precise?\n- In Theorem 4.2, $R$ is used without being defined.\n- I do not see any reason why Lemma 4.1 is introduced in pg. 7. I think a discussion on how (22) is utilized in the analysis is missing.\n- In lines 349-350, the authors say \"time-varying stepsizes can be eliminated\", but this seems to be a conjecture (or at least, something that the authors do not formally prove) and I think it should be reworded. Please be careful about making such statement.\n- In pg. 8, lines 378-380, the authors emphasize that their rate does not have an exponential dependency on $L_0, L_1$, but why does this worth emphasis? Are there prior work which analyzed gradient method with Polyak stepsizes in the same setup and obtained rate that involves $\\exp (L_0), \\exp (L_1)$? If so, please specify.\n- In lines 400-401, the authors mention that \"Our rate is better than $\\mathcal{O}(L_0 R^2 / \\epsilon + \\sqrt{L / \\epsilon} L_1 R^2)$\", but where does this rate come from?\n- In the beginning of Section 6 (and also the same for Sections 4, 5) please clearly specify in the first sentence introducing the setup that you are dealing with convex functions.\n- It is weird that Algorithm 1 (which is not the algorithm that the authors develop) is packaged using the Algorithm environment, while the authors' algorithm (lines 427-431) isn't. \n- The Step 1 of the authors' algorithm in Section 6 requires to find a point $\\bar{x}$ satisfying $f(\\bar{x}) - f(x^*) \\le \\frac{L_0}{8 L_1^2}$. I think this requires either the knowledge of $f(x^*)$ or $R=||x_0 - x^*||$ (in order to determine when to stop). Is this understanding correct? If so, this is a limitation that should be clearly explained.\n- Theorem 6.1 misses the convexity assumption in the statement. Also, it analyzes the AGMsDR algorithm with initial point satisfying  $f(x_0) - f(x^*) \\le \\frac{L_0}{8 L_1^2}$, but this is inconsistent with the $\\bar{x}$ notation used in lines 427-431. I think this also comes from the problem of not highlighting their \"procedure\" as a separate algorithm with a proper name.\n- In lines 477-478, should the two occurrences of $R$ be the same values? It seems like one is $||x_0 - x^*||$ and one is $||\\bar{x} - x^*||$.\n- In line 483, the authors again mention \"not have an exponential dependency\". Please cite a relevant prior work explaining why this is worth emphasis.\n- It is not clearly defined what the figure labels like NGD, GD1, GD2, etc. precisely means. Even though it could be speculated if one reads through Section 7, this should be done somewhere, for example, within the figure caption.\n- In Figure 2, please specify that you are using $L_0 = (\\frac{p-2}{L_1})^{p-2}$ according to Example 2.4 (if this understanding is correct).\n\n[1] Gorbunov et al., Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "As mentioned in the Summary section, this paper nicely demonstrates the parallelism of how the traditional techniques from smooth (convex) minimization should be properly interpreted and applied to the class of $(L_0, L_1)$-smooth functions. As a reader who is much more familiar with the classical optimization theory but not as much with the recent theory of $(L_0, L_1)$-smooth optimization, the paper was interesting, easily readable, and informative. It seems such viewpoint has not been provided previously with this level of clarity, and I think this work could serve as a solid reference for those future readers who are interested in this area. The algorithms and their convergence results the paper provides within various setups seem correct and competitive.", "weaknesses": "The primary weakness of the current version of the paper is the writing. While I think the technical contents are good, the writing does not seem to be polished carefully enough and should be managed before the publication. The general flow is okay, but there are many detailed points which I would recommend the authors to address; please refer to the Questions section. I would recommend acceptance of the paper provided that the writing issues get resolved.", "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": "pKxoEvDQPl", "reviewer": "Reviewer_gEoz", "summary": "The paper studies gradient methods for solving problems with (L0, L1)-smoothness, a recent class of functions developed by Zhang et al. (2019). Novel convergence results are established in this paper, including tighter bounds on function growth and the complexity bound for finding near stationary points in both nonconvex and convex cases. Some new methods with different step sizes are also examined.", "questions": "See weakness", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and easy to follow. The analysis is thorough and offers many insights for research in optimization.\n\n2. I appreciate the comparison between this paper and Gorbunov et al. (2024), which is comprehensive and particularly crucial for readers.\n\n3. I have attempted to implement some of the suggested algorithms and found that the analysis presented here is essential for practical use, especially when the optimal step size in equation (11) is given explicitly.", "weaknesses": "The following are some major concerns about the paper.\n\n1. The numerical experiments are conducted only on simple functions. I suggest that the authors significantly improve this section by employing more diverse examples, particularly in nonconvex cases. For examples, could the authors consider loss functions from deep learning models or other challenging nonconvex optimization problems from applications?\n\n2. If I have not overlooked anything, the current paper does not discuss the difficulties of deriving the convergence properties for (L0, L1)-smooth functions compared to L-smooth functions, nor how the authors overcome these challenges. Can the author discuss key challenges in analyzing (L0,L1)-smooth functions compared to L-smooth functions, and to highlight any novel theoretical tools or techniques they developed to overcome these challenges.\n\n3. I do not find Proposition 2.6 impressive, as the results are rather predictable, and the proofs seem straighforward. \n\n4. The authors mention that \"we cannot guarantee that the class is closed under all standard operations, such as the summation\". Can you provide a concrete counterexample showing that the sum of two (L0,L1)-smooth functions is not necessarily (L0,L1)-smooth? If so, are there any additional conditions that could guarantee the sum remains in this function class?\n\n5. The authors claim that the estimate in (4) is tighter than those presented in previous works. Can you provide a numerical example or theoretical argument demonstrating how your estimate in (4) is tighter than previous bounds? Is it possible to prove that this bound is optimal, or are there cases where it could potentially be improved further?", "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": "uqJCUWdpR7", "reviewer": "Reviewer_KuU4", "summary": "The author(s) present non-asymptotic convergent analyses of various types of gradient methods on convex and non-convex functions satisfying $(L_0, L_1)$-smoothness, which is a type of generalized smoothness assumption that has gained some interests recently in machine learning community.\n\nThey derive a series of first-order upper bounds, implied by the generalized smoothness assumption, which are tigher bounds than previous works. Furthermore, they derive similar lower bounds when the functions are convex.\n\nUsing these newly derived bounds, they present a convergent analysis on non-convex functions, which matches the current best-known rate of this function class up to absolute constants.\n\nFor convex functions, however, they derive better-than-existing convergent rates for different gradient methods of this particular function class.\n\nFinally, they experiment with a simple $||\\mathbf{x}||^p / p$ function, where the constants $L_0$ and $L_1$ can be known in advance.", "questions": "1. Another way to dispense of the dependency of the constants $L_0$ and $L_1$ in the step-size is to perform backtracking line-search, which also guarantees descents in the objective function value. Can the given new bounds (Lemma 2.2, 2.3) improve the rate derived by Hubler et al 2024?\n\n2. For Theorem 6.1, empirically, is there any way to tell when to switch to AGMsDR? That is, can we tell that we are in a local region?\n\n3. Have you tried experimenting with a softmax function, which I believe the constants $L_0$ and $L_1$ can be analytically evaluated? This example will provide more insights than the simple function $||\\mathbf{x}||^p$.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "To me, one of this paper's main strengths/contributions is the derivation of tighter first-order upper and lower bounds. The bounds will undoubtedly help any further work on analyzing this particular function class.\n\nIn Theorems 3.2 and 5.1, the author(s) is able to dispense $L$-gradient Lipschitz, which was additionally assumed in the previous works Koloskova et al 2023, while improving the current existing rate.\n\nThe overall flow of the paper is well-presented.", "weaknesses": "1. Numerical results can be strengthened by providing more experiments.\n\n2. For Theorem 3.1, even though your rate is better than the rate provided in Hubler et al 2024, they do not have the dependency on $L_0$ and $L_1$ (See section Questions, 1.).\n\n3. (line 269) I believe \"By Theorem 3.1, the smallest number K of iterations required to achieve ...\" is incorrect, as one can happen to choose an initial point such that $\\|\\| \\nabla f(x_{0}) || < \\epsilon_{\\mathbf{g}}$. In this case, $K = 0$, which violates your claim here. The correct wording should be \"By Theorem 3.1, obtaining the stationary point requires at most ... \".\n\n4. (Theorem 5.1) The presentation of your theorems should be consistent. It is recommended to present in the form of \"$K \\geq $\", like in your other theorems. \n\n5. $||\\mathbf{x}_0 - \\mathbf{x}^*||$ is denoted to be both $R_0$ and $R$, e.g., Theorem 3.2. Notations should be consistent.\n\n6. (line 257) \"absolte\" -> \"absolute\"\n\n7. (eq. 14) I think the inequality should be $... \\geq \\frac{||\\nabla f(x)||^2}{2L_0 + 3L_1||\\nabla f(x)||}$, i.e., there is no 2 in the numerator (c.f. Lemma B.1)\n\n8. (line 641) I think $s$ should be $s := \\nabla f(x) - \\nabla f(y)$. Otherwise, the sign in the inequality at line 643 is incorrect.\n\n9. (line 648) Change $\\phi^*(\\gamma)$ to $\\phi_*(\\gamma)$ to maintain consistency.\n\n10. (line 651) Some of the gradients should be of variable $y$, not just $x$, i.e., $\\nabla f(y)$.", "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": "7mGTODDshP", "reviewer": "Reviewer_R7w6", "summary": "The paper examines the extension of a certain optimization method to a broader smoothness assumption, specifically $L_0,L_1$-smoothness. While it broadens the class of functions to be minimized, the authors manage to recover convergence rates comparable to those of the standard $L$-smooth case, albeit with an additional term that does not depend on the final accuracy.", "questions": "- As a contribution authors listed in line 54 \"tighter bounds on descent inequalities\". But in line 58 authors \"achieve the best-known\" rate for non convex functions. I am curious if the tighter bounds actually helps to improve convergence. I would expect improving the rate, if they actually help. As far as I understand, the tighter bounds are supposed to help for the non-simplified stepsize version and some logarithmic improving factor should appear. Am I right? Could the authors answer this question by providing rates with their tighter bounds and with non-tight bounds?\n- Acceleration does not seems fair. By initially running non-accelerated method authors enter the area where $\\|\\|\\nabla f(x) \\|\\|\\leq \\frac{L_0}{L_1}$, making the right hand side of the generalized smoothness condition (line 121) $L_0 + L_1|\\|\\nabla f(x) \\|\\| \\leq 2L_0$, that corresponds to the standard smoothness assumption. \n   - In the standard $L$-smooth case there exist accelerated methods without line search (e.g. Similar Triangles Method), that keep iteration bounded ($\\|\\|x^k - x^* \\|\\|  \\leq R \\cdot const$), so I am expecting such methods stay in the area. Can the line search be avoided in your analysis? Or what is it crucial role? \n\n  - The term  $L^2_1 R^2$ corresponds to the number of iteration to enter the area with bounded gradient. Then the authors in fact deal with the standard $2L$-smooth case, while obtaining the other term. This observation is consistent with non-accelerated methods, considered in the paper. I would like to note, that acceleration in fact is used only in the area where the standard $2L$-smooth case takes place, and does not help to enter the area faster. In other words I would say that the contribution in fact is -- a bound on the number of oracle calls to enter this area. And I am expecting this bound to be improved in the accelerated case. Don't get me wrong, but I could not consider the convergence of AGMSDR in the standard $2L$-smooth case as a contribution. I would like authors to address my concerns, and clarify about their contribution to this part. Is it an application of the authors result of non-accelerated method to bound the number to enter the area with bounded gradient? \n\nI would like to comment on the scores. Taking the above questions into account, I currently accept the contributions related to first-order methods. The results are new and significantly improve previous rates. But they rely on the only basic result -- descent inequalities. The rest is an application of the new inequalities to the well-known methods. That is why I consider the contribution as limited. I open for a discussion and the authors are likely to expect higher scores if my concerns are convincingly addressed, especially about the area with bounded gradient.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- For convex problems, authors improves existing results by achieving $O( L_0R^2 / \\varepsilon + L^2_1 R^2)$\n- Normalized gradient method and gradient method with Polyak stepsizes, which do not require the knowledge of the parameters $L_0$, $L_1$ and have the same rate as above\n- Accelerated method with $O( \\sqrt{L_0R^2 / \\varepsilon} + L^2_1 R^2)$", "weaknesses": "- Lack of analysis  for stochastic case is significantly limiting practical value of the work\n- Accelerated method requires a line search (minor)\n- The second part of the second question from below", "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)