Toward a Unified Theory of Gradient Descent under Generalized Smoothness
Authors: Alexander Tyurin
Venue: ICML 2025 poster (2025)
Keywords: generalized smoothness
first-order optimization
nonconvex optimization
convex optimization
Primary area: optimization

Abstract: We study the classical optimization problem $\min_{x \in \mathbb{R}^d} f(x)$ and analyze the gradient descent (GD) method in both nonconvex and convex settings. It is well-known that, under the $L$–smoothness assumption ($\|\| \nabla^2 f(x) \|\| \leq L$), the optimal point minimizing the quadratic upper bound $f(x_k) + \langle \nabla f(x_k), x_{k+1} - x_k \rangle + \frac{L}{2} \|\| x_{k+1} - x_k \|\|^2$ is $x_{k+1} = x_k - \gamma_k \nabla f(x_k)$ with step size  $\gamma_k = \frac{1}{L}$. Surprisingly, a similar result can be derived under the $\ell$-generalized smoothness assumption ($\|\| \nabla^2 f(x) \|\| \leq \ell( \|\| \nabla f(x) \|\| )$). In this case, we derive the step size $$\gamma_k = \int_{0}^{1} \frac{d v}{\ell( \|\| \nabla f(x_k) \|\| + \|\| \nabla f(x_k) \|\| v)}.$$ Using this step size rule, we improve upon existing theoretical convergence rates and obtain new results in several previously unexplored setups.

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
Alexander Tyurin'
Abstract
most popular numerical first-order method, gradient descent (GD):
We study the classical optimization prob- lem min f(x) and analyze the gradi- ent descent (GD) method in both noncon- vex and convex settings. It is well-known that, under the L-smoothness assumption [[)]] I L). the optimal point min- imizing the quadratic upper bound f(xx) + (Vx( 2x+1 Ix) + 4/2||=2+1 2 is Tk+1 Fx - 7a (xxx with step size "Mk 1/z. Surprisingly, a similar result can be derived under the l-generalized smoothness assumption f(x)] < e(IlV (l). In this case, we de- rive the step size
Fk+1 24 (xxx),
(2)
where To is starting point, and {r are step sizes.
GD is pretty well understood under the traditional L-smoothness assumption, i.c., [[V - Vf S
L| y|l or || S L for æ, X. However, instead of smoothness, we investigate E E-smoothness, i.e.
[ > ((VV)())I
for all x E X (see Assumption 3.1), where E is any non- decreasing positive locally Lipchitz function. This is recent assumption that captures a much wider set of func- tions (Li et al., 2024a). In particular, if ((s) = L, then we get L-smoothness. If ((s) Lo + L15, then we get (Lo. L,) smoosooossssss (Zhang et al., 2019). I-smoothness can typically capture "quadratic like" functions and does not include even fxx x" for 2 f(x) e A similar problem arises with (Lo, smoootthhssss: it does not include f(z) = - -log a, for instance. The class of t- smooth functions can include all these examples and more (Li et al., 2024a).
7h L' [(IV)(=))I [[)()))
de
Using this step size rule, we improve upon exist- ing theoretical convergence rates and obtain new results in several previously unexplored setups.
1. Introduction
We consider optimization problems of the form
1.1. Related work
min f (I)) ZER2
(L)
Under L-smoothness, is well-known that GD converges to an E-stationary point after (LA/E), and to an s-solution after O (LR*/a) iterations (Nesterov, 2018), where A := f(xo) f R = | - x.Il. inf=ER* [(x), and v. E IRd is solution of (1). Interestingly, this result can be further improved by employing non-constant step sizes (Altschuler & Parrilo, 2024; Grimmer et al., 2024), although relying on the I-smoothness assumption.
I-smoothness:
where ʃ Rd - IR U {oo}. Our goal is to find an e- stationary point, I E Rd such that [+]( < E, in the nonconvex setting, and an e-solution, I Rd such that f(z) inf f(x) & E, in the convex setting. We define X' = {x E gd f(x) < 2o } and assume that X' is open convex, f is smooth on X, and continuous on the closure of X.
This is classical and well-studied problem in optimization (Nesterov, 2018; Lan, 2020). We investigate arguably the
(Lo. smooohhhhssss and nonconvex setup: In the nonconvex setting, Zhang et al. (2019) analyzed the (Lg, L1) smoohhhosssssss assumption, which is stated for twice differentiable functions as /22 [x)]] s To + L1 |V [x+)] for all x E X. Zhang et al. (2019) showed that a clipped version of GD, i.e., (2) with appropriately chosen step sizes, finds an E -ttttionary point after O (LoA/e 1fA/Lo) iterations. Subsequently, Crawshaw et al. (2022); Chen
'AIRI, Moscow, Russia "Skoltech, Moscow, Russia. Corre- spondence to: Alexander Tyurin <alexandertiurie gmail.com>>
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
Table I: Summary of convergence rates for various GD methods under generalized smoothness assumptions in the nonconvex setting. Abbreviations: R := 1000- - æ1|1: A = f(z)) - (Ix), E = error tolerance. With the green color we highlight our new results and improvements.
Setting
Rate
References
Smoothness
LA
v1 s(oill s <)
(Lo. L1 Smmoothnness
L
+
L,A V2
(Vankovv al., 2024)
(Iv" f(x)ll ss La + ((
8
L [
(Li al., 2024a) (no guarantees when p 2)
(p, Lo, [1) Smm-ohhossssss with 0 S S 2 (1N2) & Lo + 4 /(10)))))1*)
8
Sec. 5.3 (new)
LoA
+
L 2(8-1//3
(Lo4/S + L A when = 2)
(p, L Smoothness with p > 2
Sec. 6.2 (new)
LoA
+ L, 11(22))-2
(requires A.6.1)
Exponential growth of ! (1V²2 & Lo LIlV)( e(p()()(()1)))
Sec. 6.1 (new) (requires 1.
LAd L 6
al. (2023); Wang et al. (2023); Koloskova al. (2023); Li et al. (2024a;b); Hübler et al. (2024); Vankov et al. (2024) considered the same setup, where the state-of-the-ar art theoretical iteration complexity O (LoA/e+ L:4/vE is obtained by Vankov et al. (2024), without requiring a bounded gradient assumption, dependence on [Vof(z)) [|, or L-smoothness f.
accelerated version of GD. They obtained convergence rates of O (cUIV/((=)))))))) and O (V for GD and accelerated GD in the convex setting, and a rate of O (AUIV ((=)))))))))))) in the nonconvex setting for GD. In all cases, their results depend on f and require that the function {(s) grows more slowly than s² in the nonconvex setting. For instance, they cannot guarantee convergence when {(s) = Lo + L1s². The E-smoothness assumption was also consider in online learning (Xie et al., 2024).
(Lo, Lm)-mmoohhness and convex setup: Convex problems were investigated by Koloskova et al. (2023). They showed that (2) with normalized step sizes guarantees o Loott/= + R²) rate, which requires the L- smoothness of f. Li et al. (2024a), using GD and accelerated GD (Nesterov, 1983), obtained O ((oo+
1.2. Contributions
We take the next step in the theoretical understanding of op- timization for ê-smooth functions. Using new bounds, we discover a new step size rule Algorithm 1, which not only improves previous theoretical guarantees but also provides results in settings where GD's convergence was previously unknown (see Tables and 2). In particular,
and O norm of the initial gradient | Furthermore, Takezawa et al. (2024) get O [Latt//= R² rate using the Polyak step size (Polyak, 1987), which also re- quires Lmoohthesss.. Using adaptive step sizes, Gorbunov et al. (2024); Vankov et al. (2024) concurrently provided the convergence rate O (ToRt/E + LTRR).. Also, with fixed step size, (Li et al., 2024a) proved the convergence rate O (Loft/e fs L, ((ro) Vankov et al. (2024) also analyzed accelerated versions of GD, but Gorbunov et al. (2024) get an exponential dependence on L, and R, while Vankov et al. (2024) requires solving an auxiliary one-dimensional optimization problem in each iteration.
which depend on the
We prove new key auxiliary results, Lemmas 4.3 and 4.5, which generalize the classical results and allow us to derive the step size 7 = So IIV
du
Using this step size, we significantly improve the conver- gence rate established by Li et al. (2024a) in the nonconvex setting. For instance, under the (p, Lo. I.) smooth assump- tion with 0 < p < 2, we improve their convergence rate of GD from 4.4 L, [ to Lo g(2-p//2 over, Li et al. (2024a) do not guarantee the convergence of GD when = 2, while our theory, for the first time, estab- lishes the rate Lo + L,A, which we believe is important in view of the motivating examples from Section Despite the (p. Lo, smotshhhssss assumption, our theory remains
Gorbunov et al. (2024);
1 More-
(-smoothness: Li et al. (2024a) introduced the L smoothness assumption and analyzed GD as well as an
2

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
Table 2: Summary of convergence rates for various GD methods under generalized smoothness assumptions in the convex setting. Abbreviations: R == ||zo Iz || A = f(xo) - f(z,), Mo == [ E = error tolerance. With the green
color we highlight our new results and improvements.
Setting
Rate
References
Smavthness
LR²
(Li al., 2024a)
k
+ min (1. n?, L1 M1
(Gorhunav et al., 2024)
(Le, 11))-moothnes
(Vankov al., 2024)
4 4/41/2 12,1t. L. Mo
+ min
.//2
Sec. 7.2 and 8.1 (new)
R 4Ag R2
(Li al., 2024a)
(p, Lo, L1 J-moothhness with 0 S p S
12
4 4,40/2n2
L. Mg n²
min
cl-p/2
-01-0/0-11
Sec. 7.2 and 8.1 (new)
R 14
(Li ct al., 2024a)
(e, Lo. Li> )-Smoothnesss with < p <
2/40/222-
T LIMER
min
R
Scc. 7.2 and 8.1 (new)
L b MG R2
(Li ct al., 2024a)
(p, Lo, L1 >-Smoothness with p 2 2
kgR² + min
Li 11A(2M))0-
1 34F 1770 240
L Ling""
Sec. 8.2 (new)
22p
MMMiin2
(Li 2024a)
General Result (works any Z)
2(0) min T. ([M)]R2
where T does not depend on
Sec. 8.3 (new)
(convergence rate is f(oy/e /4 for e small cnough)
The canonical analysis can be found in (Nesterov, 2018; Lan, 2020). However, using non-constant step sizes, is possible to improve the complexity under L-smoothness (Altschuler & Parrilo, 2024; Grimmer et at. 2024).
applicable to virtually any l functions.
there are many examples when (Lo, assumpttonoo fails to hold. The simplest example is f(x) log which has the Hessian (second derivative) that depends quadrati- cally on the norm of gradient (first derivative). Moreover, we argue that (Lo, asssumpttno is not appropriate even for modern optimization problems with neural networks. Indeed, consider a toy example f I + E such that fxx y) = log(1 + exp(-ry))- A two-layers neural net- work with log loss, one feature, and one sample reduces to this function. Then Vf(I.v)) = Iteey (y. x)) E I22 and (²)(E,)) = ( ( 2² "T+e by ayy
In the convex setting, we also improve all known previous results (see Table 2). Specifically, we refine the dominat- ing term' from f(IV)(( )r² (Li et al., 2024a) to ((O) under the E-moothhesss assumptions, which is significant improvement because the initial norm | [<ro)] can be large. Additionally, we derive tighter non-dominating terms, further enhancing the current theoretical state-of-the-arr results (I.i et al., 2024a; Gorbunov et al., 2024; Vankov et al., 2024). Even under the well-explored (Lo, L1)- smoothness assumption, we discover a new convergence rate L, A/22
8 } where the first term in min is new and can be better in practical regimes (see Section 8).
Loft" min {
cl/a L,RR,, Ln Mofe"
I (I+E - I- (Ite=xyz 2)) E R222, In the regime xy = -1, when the sample is not correctly clas- sified, we get Vf(x, y) & -(y, and (2 v) v (v? 1:
8
We extend our theoretical results to stochastic optimization and verify the obtained results with numerical experiments.
E R2x2, Notice that f2) = y² and [V w)ll ~ y if y ~ oc and x 1/v; Thus, more appropriate assumption would be (p, Lo. Lsmmooothsssss, i.e., V f(x r)ll S Lo + L, [V x)1l for all æ E X with p 2 2. Furthermore, there exist examples of func- tions that satisfy (p. Lo, smootthhs with only p> 2. For instance, take f(x) = - VT x, which is (3, Lo, Li)- smooth. This is why exploring a more general assumption, f-smoothness, is important. Another example where the (Lo, L assumption is not satisfied in practice is given in (Cooper, 2024; Chen et al., 2023).
2. Motivating Examples
One notable reason for the popularity of the (Lo, L))- assumption, i.e., / < Lo+hi [+]( for all x E X, is the observation that, in modern neural networks, the spectral norms of the Hessians exhibit a linear dependence on the norm of the gradients (Zhang al., 2019). However,
terms that dominate when e small.
3

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
Algorithm 1 Gradient Descent (GD) with E-Smoothness
import scipy. integrate integrate
1: Input: starting point zo X, function e from Assump- tion 3.1
def find step step_sizeee__eeeeeeeeetttteeeett size (el1, norm grad):
h lambda v: / ell (norm_grad * (1 v) return integrate quad (h, O, 1) [0]
2: for k ===0 0, 1,.. do
3: Find the step size
Figure I: Python function to compute the step sizes {
using SciPy (Virtanen et al., 2020).
dv 7k L.' [(IVS(+>)]+++ |V] (
4. Preliminary Theoretical Properties
analytically or numerically (Simpson's rule or Fig. I)
4: Øk+1 = 2k 7% f2(z))
Before we state our main properties and theorems, we will introduce the q-function:
5: end for
Definition 4.1 (g-function). Let Assumption 3.1 hold. For all a 2 O, we define the function R4 + [0, 9max(() (a)) such that
3. Assumptions in Nonconvex World
Following (Li et al., 2024a), we consider the following assumption:
((5 10-
du
(5)
l(a +
Assumption 3.1. A function f R RU U (0o) is & smooth if f is twice differentiable X, is continuous the closure of X, and there exists non-decreasing positive locally Lipchitz function E 00) + (0, oo) such that
du where Imnx (a): = So E(atv) E (0, oo].
Jo
Proposition 4.2. The function q is invertible, differentiable, positive, and strongly increasing, and the inverse function q- [0, (m)x(a)) + R2 of q is also differentiable, posi- tive, and strongly increasing.
| f(x)] f
(4)
The function is primarily defined because its inverse, g= plays a key role in the main results, and q does not gener- ally have a (nice) closed-form explicit formula.
for all x E X.
This assumption generalizes L L-smoothness, (Lo, L1)- smoothness, and (p, Top smoosonthsss,,
i.e., [[*](()]] < Lo+ + L1 [+)(') for all E X. In order to introduce Assumption 3.1, we have to assume that is twice differentiable. Through this paper, do not calculate Hessians of f in methods, and we only use them in Assumption 3.1. Later, we will prove (6) (Lemma 4.3) that involves only gradients of f, and it can taken as an alternative to Assumption 3.1 if f' not twice differential. However, (6) is much less interpretable and intuitive.
Under L-smoothness, IVf(y) f(zil I L L - =Il for all z.y E X. In the first lemma of the proof, we will obtain generalized bound under Assumption 3.1:
is known that
Lemma 4.3. For all x,y E X such that lly æll [0, 9max), if f is E-smooth (Assumption 3.1), then
-V -
'(lv =Ill==
(6)
where q and Junx = Imax (I (I (x)))) are defined in Defini- tion 4.1.
We start out work with the nonconvex setting. Thus addi- tionally to Assumption 3.1, we only consider the standard assumption that the function is bounded:
Let us consider some examples.
L-smoothness: {(s) = L., then q(s;a) a) = f/1. and q (2; L2; thus V - f(x)] S L 11y - æl1, recovering the classical assumption. (Lo. L1) smoothness: if ((s) = Lo + Lis, 1)/L1, recov-
Assumption 3.2. There exists f E R such that f(x) 2 l for all x E X. We define A : f(z²) fr, where x is starting point of numerical methods.
(Lo + Lxa)(ex((L1)) ering the result from (Vankov et al., 2024). However, (6) works with virtually any other choice of f. Remarkably and unexpectedly, it is never necessary to explicitly compute q1 in theory. We will see later that the final results do not depend on q
then 9 (2;
Notations: R4 := 10, N = (1, |x||| is the
output of the standard Euclidean norm for all x E Rd;
(x, 3) = Ei 24y4 is the standard dot product; |||]] is
the standard spectral norm for all A E Rddd, g = O(f)= :
exist C > such that g(z) S C x f() for all 2 E Z;
g = 2(f)) exist C > such that g(2) 2 C x [()) for
Remark 4.4. An important note is that instead of Assump- tion 3.1, we can assume (6) for functions that are not twice differentiable. All the subsequent theory remains valid. However, (6) arguably less intuitive than (4).
2 E 2: g = +(f): 9 = O(f) and = l(f): g = θ(f) f(f()==ff)))))))))))))))))))))))
the same as = R)f) but up to logarithmic factors; g ~ h:
g and h are equal up to universal constant.

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
The next step is to generalize the inequality
Remark 4.7. Since é is non-decreasing, we can get the fol- lowing bounds on the optimal step size: x( S
f(v) [()) + (VI(x), x²) + Lila-al
du 7k = So [|]/// S (VV()=)))) One can take the step size rule 7 == M( instead of 7k and avoid the integration, though this approach may result in less tight final result. For a clean and rigorous theory, it is crucial to work with the optimal step size ya. Notably, in some parts of our proofs, we leverage elegant proper- ties such as " [V[(+))]l: [[ )l) = | [VI(x)))) IIl particularly in the arguments surrounding (34) and (24).
for all 2, y E X, which is true for L-smooth functions. Lemma 4.5. For all 2,y y E X' such that lly - xll E [0, Junax ( if f is E-smooth (Assumption 3.1), then
f(y) S f(z) + (Vf(x).
+ * 11v-
(8)
(+::
Let us take another example and consider (p, Lo, L1)- smoothness, {(s) = Lo + +1s for any p 2 O. Then, in view
where q and Qmax (I) [[V][())] are defined in Definition I.
of Remark 4.7, we obtain (Lo + 2 L1 |/ (xx) )(") S
Using the same reasoning as with the previous lemma, this bound generalizes the previous bounds for L-smoothness and (Lo. L1) smoothness.
K I (Lo + L1 || [=*(=)))"* thus, roughly, 7k x (To + L1 (xx )))=
min /L, 1/T1 [ ]
if p 1, which coincides with the famous clipping rule (Koloskova et al., 2023; Gorbunov et al., 2024; Vankov et al., 2024). However, one can take not only any P 2 0, but also any non-decreasing positive locally Lipchitz function f. The step size rule in Algorithm is universal.
4.1. Derivation of the optimal gradient descent rule
Under L-smoothness, it is well-known that y = x 1 fz)(z) is the optimal point that minimizes the upper bound in (7). We now aim to extend this reasoning to (8) and determine the "right" GD method under Assumption 3.1. At first glance, it may seem infeasible to find an explicit formula for the optimal step size using (8). However, sur- prisingly, we can derive it:
5. Convergence Theory in Nonconvex Setting
In the previous section, we derived the optimal step size rule for GD that minimizes the upper bound (8). We are now ready to present the convergence guarantees of this method in the nonconvex setting.
Corollary 4.6. For a fixed x E X, the upper bound
Theorem 5.1. Suppose that Assumptions 3.1 and 3.2 hold. Then Algorithm 1 guarantees that [(I=-1) S [(xx)
f(x) + (Vf()). +)+ Iv-=zl
q (V
L [[ for all k 2 0, and
from (8) is minimized with
I1 (xx)) 8(2 vf(zz)
4A T
min LO.......
(9)
du y' L.' E(I E(IV + Vf(x)= E X.
for all 2
With the optimal y", the upper bound equals
Theorem 5.1 is our main result for nonconvex functions.
Evidently, (9) does not provide the convergence rate of minke [(+/() However, if the function 2x(()) T(2z) is strictly increasing, we finally obtain the
1-v f(x) - (V)() L. [(IV + +
dc.
rate:
This corollary follows from Lemma D.I. By leveraging this result, immediately propose a new GD method, detailed in Algorithm 1. The algorithm is the standard GD method but with the step size Tik In some cases, such as L- smoothness and ( (Lo, Ln -mmoothness, one can easily calcu- late 7ss Indeed, if E(5) = L, then 7'%- = 1/ L. If ((s) = Lo +
Corollary 5.2. In view of Theorem 5.1 and assuming that the function (2(x)) = E(2z) is strictlyy increasing, we get
80 T
min KE (O(O....TT1))
[V S 22
(10)
for Algorithm and for all T 2 1 such that 8A/T im (2)))
[ log [1+ Lo+L1 V [(()]]]]]] getting the same rule as in (Vankov et al., 2024). Our rule of the step size in Algorithm 1 works with arbitrary E function. If it is not possible explicitly, numerical methods like Simp- son's rule can be applied instead or SciPy library (Virtanen et al., 2020) (see Figure l).
Lis, then 7%
L, |I [xx))l
If thy is invertible, there is a straightforward strategy to determine an explicit convergence rate: derive ,/5 and apply Corollary 5.2. Below are some illustrative examples:
2if (Do) = oo, then the corollary is true for all 2 1.
5

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
5.1. L-smoothness
In general, the can behave in highly non-trivial manner. Therefore, each possible e function needs be analyzed individually. If ((s) Lo + Lis" for > 2 or {(s) Lo + L1see", e", then function 4/ first increases and then starts decreasing, and we can apply the following analysis.
We start with the simplest and straightforward example: {(s = L, indicating that f is L-smooth. In this case, we
can use Corollary 5.2 with (2(x)) = E. and get
4LA
min keço
V vx(x)))
V
6.1. Exponential growth of &
T
Let us consider an example when & grows exponen- tially?:
which is classical and optimal result (Carmon et al., 2020)
((t) = Lo + LisSe Then 1/2(2)
(up to a constant factor).
2
1 min
4l,02= S Theorem 5.1 en- x2 Lo
Lo
2
5.2. (Lo, (1),L))-smin smoothness
sures that min
min
[[x)))))
1
S
Lo
1b Abbe>
For (Lo. L1) smsootthesss, we should take {(s) Lu+ Lis, use Corollary 5.2, and get
8A Thus, either
kE (O...... [+)())
min
[ 2 1 log M. Since the gradi-
84, A
max kg T-I. ents are bounded by M, we can conclude that the method finds e-stationary point after
min TE(0...TT-1)
[f[(=)]|
T +
T
Loz I 2L12 + Loz. since U5 (z) = L1z + 2
8L E
This rate coincides with the results from (Vankov et al., 2024).
T= max
=ax
A 2M
(13)
iterations.
5.3. (p. Lo, smoothhhsss with 0 S PS
Remark 6.2. One can notice that if the gradients are bounded, then Algorithm 1 is not necessary, since | [x)] I ((M). In this case, it is sufficient use the classical GD theory with the step size
As far as we know, this result is new. Applying Theorem 5.1 with ((s) ((s) Lo + LisP, we obtain
a(Mr Lo However, one would get the iteration com- 1
[V NE(0....TT-1 Lo L1 [
4A T
min
(11)
plexity O (max Ln == which is worse than (13) up to the constant factors, and depends on e in the sec- ond term. Thus, our new step size rule provably helps even if grows quickly.
Using the reasoning in the previous sec- tions (see details in Section G), one can show that (o...( [++) < after at most
A
A
max
(12)
6.2. (p. Lo, L smoothness with >> 2
Similarly, we can show that the method finds an e-stationary after
iterations. For (2, Lo. L1) -moosthessssss we get max { S A2L, In contrast, the previous work (Li al., 2024a) on essmoohhnsss does not guarantee any convergence if p 2 for their variant of GD. Unlike (Li et al., 2024a), we non-constant and adaptive step sizes, which enables us to get better convergence guarantees.
64L)A(2M)0-2)
max
steps with (p, Lo, L1) smoothness and p (see Sec. H).
7. Convergence Theory in Convex Setting
6. Superquadratic Growth of {-Function
We now analyze how Alg. I works with convex problems, and use the following standard assumption.
Corollary 5.2 works only if (2(x)) = _² is strictly increas- с(2m)
ing. If {(2x) grows too quickly, Corollary 5.2 cannot be applied. However, using Theorem 5.1, we can still get con- vergence guarantees, though with the additional assumption that the gradients are bounded:
Assumption 7.1. A function f _ + RU (oo) is convex and attains the minimum at (non-unique) x. E Rd We define R = || xall, where n0 is a starting point of numerical methods.
(we assume it only in this section with superquadratic growth of f-function and nonconvex setting). A function f : Rd + IR U {oo} has bounded gradients for some M 2 [=)]] < M for all E X.
Assumption 6.1
Under generalized e-smoothness, we can prove a conver- gence rate for convex functions:
We multiply the exponent by s² for convenience
6

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
Theorem 7.2. Suppose that Assumptions 3.1 and 7.1 hold. Additionally, the function (2( =
We complement this theorem with another important result:
x²² f(2x)
strictly increas-
ing and (00) cc. Then Algorithm guarantees that
Theorem 8.3. Suppose that Assumptions 3.1 and 7.1 hold.
Then the sequence V fax)]l is decreasing.
- f((x))
120 - x.Il
min RE( 22 (2/++1((())) ||00==01|
T+1
The idea behind this result is as follows: first, we wait for the moment when GD returns a point (f(())) such that )| S M, which takes T(M) iterations. After that, GD works in region where the norm of the Hessians is bounded by ((2M) ) allowing us to apply classical conver- gence reasoning. The key observation is that this reasoning remains valid for all M > O; therefore, we take the infimum over M > 0.
As with Theorem 5.1, this theorem provides an implicit convergence rate of f(TT) - fxx)). Moreover, the theorem offers guarantees only if (1)) -²
ø[2m] is strictly increasing and 4)2((0) co. We now consider some examples.
7.1. L-smoothness
While Theorem 8.1 does not provide the final convergence rate for ((xT) [xx,), now illustrate the steps that should be taken next. Due Theorem 8.3, the sequence {IV f (Irx)l is decreasing. Using Theorem 5.1, one should should find T(M) as a function of M, substitute (M)) into (15), and minimize the obtained formula over M > 0. Let us illustrate this on (p, Lo, -mmooth functions.
If E(s) = T., then [(T)) S (x..) v Lllan x. because (fx+) decreasing sequence (Theorem 5.1). This is the classical rate of GD (Nesterov, 2018).
T+1
7.2. (p, Lo, smoothhsesss with 0 < p <
In Section K, we show that the method finds e-solutoon after at most
8.1. (p. Lo, ) smoothnnss with 0 <<
2t
4L (12--))) R22
According to (12), T(M) = max { ( 32L, if M <
max
2011-)/12-p)
[ and T(M) = if M 2 [ I. Since ((s) Le + L1s", we should minimize (15) and consider
M -/--
iterations for p 1. And after most
R
161 R2 20-11
min inf M<IlVS(OO)I
T(M)
((2M)
22
max
(14)
inf M2IlV/(W)
[(M) + ((2M)R
2
iterations for 1 <.<2.
min inf M20
LoA L Mr
La
LIMeR
max
M
8. Alternative Convergence Theory in Convex Setting
Lg
max
The main disadvantage of Theorem 7.2 is that it works only _²
where, for simplicity, ignore all universal constants. The term with inf is minimized with M = VEA/R². Thus, we get
if v>2(x) 7(24] is strictly increasing and via (c0) = oo. To address this limitation, we introduce new proof technique for GD from Algorithm 1, which not only works in cases of superquadratic growth of l but also guarantees better convergence rates than Theorem 7.2 in certain practical regimes.
{ La e miin
min {
LA ( "n² 11 (16) el 272
max
Unlike (14), (16) is finite when p 2. For L,)- 1, this setting reduces to the smooth case with the complexity T = O (max {To min (12 R/e [11l This complexity
Theorem 8.1. Suppose that Assumptions 3.1 and 7.1 hold.
Then Algorithm I guarantees [(TT) - [xx.) < after
can be better than O (max { (LoR"/e /e, min In (e improve the results by Li et al. (2024a); Gorbunov al. (2024); Vankov et al. (2024). As example, consider the convex function ʃ R - R such that f(x) = - pae +eb which is (Lit,, smooohh (see Section Q). Taking To = O, we get (xo) f(x.) ) I 1. At the same time, letting μ - O, the distance R = 1/L, [log(H/L)] diverges to infinity, whaR2/o converges zero, and
+(M)+ ((2M) | 12.
inf MSO
(15)
and
2=
iterations, where T(M) is the number of iterations required to obtain V ((FF(M)) < M.
Remark 8.2. This convergence rate can be combined with Theorem 7.2. Thus, one can take the minimum of the results from Theorems 8.1 and 7.2.
7

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
Algorithm 2 Stochastic Gradient Descent (SGD) with &
iterations, where Ma == V| [[V (e, A, Mo) depends only on E, A, and Ma, and does not depend 8.
Smoothness
1: Input: starting point zo E X, function E from Assump- tion 3.1, batch size B
Thus, for small E, Algorithm I converges after at most θ (<())&%/) iterations. In other words, Algorithm I behaves like the classical GD method with the step size 1/2(0). In contrast, Li et al. (2024a) proved a significantly weaker convergence rate θ (EUIV (toII// for GD.
2: Find the ratio sup (2s)
#20
3: for k= 0,1,................ do
4: Calculate gb B 21=1 (a(x
([Exr) are i.i.d.)
dv
9. Stochastic Gradient Descent
5: 7k 5r Jo E(1gkll + 19 v)
6: #k+1 = Fh Yk.R
We can obtain similar results in stochastic setting, where we access to stochastic gradients V fz; {) characterized by the following "light-tail" assumption (Lan, 2020).
7: end for
mi (xo can become arbitrarily larger than 4/4// //20,, because the latter scales linearly with R.
Assumption 9.1. For all x E X, the stochastic gra- dients v.((=; satisfy Eg [=) = ff(x) and
Eg eep (IV] ((>)) / S exp(1) for some 0.
8.2. (p, Lo, L1) smoothness with p > 2
Theorem 8.1 works even if p > 2 in (p, Lo, 1,)- smoothness. In the convex setting, Assumption 6.1 is not required since [+x]] S
We can prove the following result that extend Theorem 5.1: Theorem 9.2, Suppose that Assumptions 3.1, 3.2, and 9. hold. Let T denote the number required to ensure that ti... [xx)] S based on
((o)]] for all k 2 0. Simi-
larly to Section 6.2, we can conclude that || ( S M for (MM) max { & M 64L, (2 V (zx) (0-0))))))))))))))))))))) }
M- < (2))]],, and T(M) = 0 if M 2 [[(())]]- Substituting (MM into (15), we obtain
C [VV SrX kE(O.....T -13 (3 ((x)
45A T
min
(20)
Lg R min L.
Then, with probubility
and batch size B 2 0² /e Algorithmm 2 32 (1 (1+v33 (3log((/8))
c
(17)
max
Lg
747 A 840
Li R
L, RR
finds an s-stationary point after T iterations, and the total number of computed stochastic gradients is B x T.
2==
e
up to universal constant factors, where Mo = [x())]
Let us explain how the theorem works. Notice that the convergence guarantee (20) coincides with (9), differing only in r and universal constants. To find T, one can use exactly the same reasoning as in Section 5. Specifically, T is shown to be the same in that section, multiplied by and a universal constant. The main difference lies in r. For instance, r = 2" for (p, Lo, L1) smooshhtssssss. If < 2, then r S 4, mcaning it is simply a constant factor. Overall, for any f, the total number computed stochastic gradients is O(B x T). For (p, Lo, L1) -moothhtssssss with 0 < p S 2,
8.3. Convergence guarantees for small E
In many practical problems, finding term in convergence rates that dominates when ě is small is sufficient. We notice that the term Loft/e dominates in all derived complexities. turns out we can generalize this observation:
Corollary 8.4 (Subquadratic and Quadratic Growth of E). Consider Theorem 1. Additionally, assume that the func-
tion (2(x)) = E(20) is strictly increasing. Then GD finds an e-solution after at most
=²
we get
o ( 22 (
A p(4-p)/2
LA Lo + c(2-0)/2
+
+
R(
+ min { T (L,
R2
(18)
ignoring the logarithmic factor. For s small enough, the dominating term is θ (~"1a//=)) that, up to logarithmic factors, recovers the optimal rate (Arjevani et al., 2022). Furthermore, unlike (Li et al., 2024a), we can extend these convergence guarantees to cases where p 2 2, and the dominating term does not depend on L1. Our approach assumes stochastic gradients with "light tails," which
iterations, where Mo := fzo)l T (e, A) depends only on and A, and does not depend on E.
Corollary 8.5 (Superquadratic Growth of E). Consider The- orem 8.1. Then GD finds an e-solution after at most
(()) + min ( (e, A, Mo),
8(2 25
(19)
8

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
necessary for handling the non-constant, gradient-dependen step sizes in Algorithm 2. Extending these results settings with "heavy tails" is an important and challenging research question.
condition in deep learning. In OPT 2024: Optimization for Machine Learming, 2024.
Crawshaw, M., Liu, M., Orabona, F., Zhang, W. and Zhuang, Z. Robustness to unbounded smoothness of generalized signsgd. Advances in Nearal Information Processing Systems, 35:9955-9968, 2022.
10. Conclusion and Future Work
This work offers new insights into modern optimization within the framework of the E-smoothness assumption. We present new lemmas, algorithms, and convergence rates. However, numerous other directions remain to be explored, including stochastic optimization with "heavy tails" (Rob- bins Monro, 1951; Lan, 2020), acceleration of Algo- rithm 1 (addressing the exponential dependence on L1 and R. or resolving the need to solve an auxiliary one- dimensional optimization problem in each iteration (Gor- bunov et al., 2024; Vankov et al., 2024)), variance reduction (Schmidt et al., 2017), federated learning, and distributed optimization (Konečný et al., 2016).
Gorbunov, E., Tupitsa, N., Choudhury, S., Aliev, A., Richtárik, P., Horváth, S., and Takáč, M. Methods for convex (L.O, -.I--mmothh optimization: Clipping. acceler- ation, and adaptivity. arXiv preprint arXiv:2409.14989, 2024.
Grimmer, B., Shu, K., and Wang, A. L. Accelerated ob- jective gap and gradient norm convergence for gradient descent via long steps. arXiv preprint 1XXi:24433114455 2024.
Gronwall, T. H. Note the derivatives with respect
parameter of the solutions of system of differential equations. Annals of Mathematics, 20(4):292-296, 1919.
Acknowledgements
The work was supported by the grant for research centers in the field of Al provided by the Ministry of Economic Development of the Russian Federation in accordance with the agreement 000000CC13925P4F0000 and the agreement with Skoltech N=139- 10-2055033..
Hübler, F., Yang. J., Li, X., and He, N. Parameter-agnosii optimization under relaxed smoothness. In International Conference on Artificial Intelligence and Statistics, pp.
4861-4866 PMLR, 2024.
Juditsky, A. and Nemirovski, A. S. Large deviations of vector-valued martingales in 2-smooth normed spaces. arXiv preprint arXiv:0809.0813 2008.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Koloskova, A., Hendrikx, H., and Stich, S. U. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning, pp. 17343-17363. PMLR, 2023.
References
Konečný, J., McMahan, H. B., Yu, X., Richtárik, P.,
Suresh, A. T., and Bacon, D. Federated learning: Strate- gies for improving communication efficiency. arXiv preprint 1r1.v:161 2016.
Altschuler, J. M. and Parrilo, P. A. Acceleration by stepsize hedging: Silver stepsize schedule for smooth convex op- timization. Mathematical Programming, pp. 1-14, 2024.
Lan, G. First-order and stochastic optimization methods for machine learning. Springer, 2020.
Arjevani, Y., Carmon, Y., Duchi, J. C., Foster, J., Srebro, N., and Woodworth, B. Lower bounds for non-convex stochastic optimization. Mathematical Programming, pp. 1-50, 2022.
Li, H., Qian, J., Tian, Y., Rakhlin, A., and Jadbabaie. A. Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems, 36, 2024a.
Carmon, Y., Duchi, J. C., Hinder, O., and Sidford, A. Lower bounds for finding stationary points i. Mathematical Programming. (84(())71-12))) 2020.
Li, H., Rakhlin, A., and Jadbabaie, A. Convergence of adam under relaxed assumptions. Advances in Neural Information Processing Systems, 36, 2024b.
Chen, Z., Zhou, Y., Liang. Y., and Lu, Z. Generalized- smooth nonconvex optimization as efficient as smooth nonconvex optimization. In International Conference on Machine Learning, pp.
Nesterov, method of solving a convex programming problem with convergence rate o (1/k** 2). Doklady
PMLR, 2023.
Cooper, Y. theoretical study of the (1 0, 1) smoothnesss
Akademii Nauk SSSR, 269(3):543, 1983.

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
Nesterov, Y. Lectures on convex optimization, volume 137.
Springer, 2018.
Polyak, B. T. Introduction to optimization. 1987.
Robbins, H. and Monro, S. A stochastic approximation method. The Annals of Mathematical Statistics, pp- 400- 407, 1951.
Schmidt, M., Le Roux, N., and Bach, F. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162:83-112, 2017.
Takezawa, Y., Bao, H.. Sato, R., Niwa, K., and Yamada, M. Polyak meets parameter-free clipped gradient descent. arXiv preprint arXiv:2405.15010, 2024.
Vankov, D., Rodomanov, A., Nedich, A., Sankar, L., and Stich, S. U. Optimizing (LO, Lmo-sho functions by gra- dient methods. arXiv preprint arXiv:2410. 10800, 2024.
Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., et SciPy 1.0: fundamental algorithms for scientific computing in python. Nature methods, 17(3):261-272) 2020.
Wang, B., Zhang, H., Ma, Z., and Chen, W. Convergence of adagrad for non-convex objectives: Simple proofs and relaxed assumptions. In The Thirty Sixth Annual Conference Learning Theory, pp. 161-190. PMLR, 2023.
Xie, Y.-F., Zhao, P., and Zhou, Z.-H. Gradient-variation online learning under generalized smoothness. arXiv preprint ar arXiv:2408.0000
2024.
Zhang, J., He, T., Sra, S., and Jadbabaie, A. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint arXiv:1905.1188 1881. 2019.
10

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
A. Experiments
We verify our theoretical results by asking whether it is necessary to use the step size rule from Algorithm 1, and maybe sufficient to use the step size rules by Li et al. (2024a); Vankov et al. (2024) instead. We first take the function log log(0.1 x) (see Figure 2), which has its minimum at z. 0.05. This function is (p, 800, 2) -mooohh with p 2; however, it not (Lo; Lm)-shooth for any Lo, L1 2 0. Consequently, run Algorithm 1 with {(s)
f [0, 0.1] R U {oo} defined as f(x)
800 + 28², starting at 20 10-7, and observe that it converges" after 75 iterations. Next, we take the step size ? = 1/ /8000 + (zo))) from (Li et al., 2024a) and observe that GD requires at least 20.000 iterations because (20) is huge. Finally, to verify whether the exponent 2 is necessary, we take {(s) 800 + 2s (Vankov et al., 2024). For this choice of E, GD diverges.
10"
10x
101
(ours)
10
(Vankov et al., 2024) (diverged)
(Li et al., 2024a)
10
20
40
63
70
iterations
Figure 2: Experiment with f(x) = log x log(0.1 r).
We repeat this experiment with the function / R + It defined as ((x) = e + +el (see Figure 3) which has its minimum at x, = 0.5. This function is (3.3, -mstth,,h meaning we can run Algorithm with {(s) = 3.3 + s. It converges after at most 20 iterations. At the same time, we choose ((s) = 3.3 + or 7 = (3.3 + 2 (f)()))) -1 (Li et al., 2024a), GD requires least 200 iterations to converge. These experiments underscore the importance of our step size rule and the right choice of step size and normalization.
161
f(x")
=33 5
f(s) -
+
(Li et al., 2024a)
12-1
iterations
Figure Experiment with f(x) 6" c22-
*finds ī such that f(ā) - f(x.) s 10-5

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
B. Proof of Lemma 4.3
The following proof is based on the techniques from (Li et al., 2024a; Vankov et al., 2024).
Proof.
is sufficient to prove that for all z, x x E X, t E [0, 9max) such that || = 1, if is e-smooth (Assumption 3.1),
then
V th) - vf(²) S <t
(21)
where q and Imax Imax t= lly z||.
(I)) defined in Definition 4.1. One can get (6) from (21) with y th and
Let us define c(t) = So ((IV (T) Using Taylor expansion, we get
VVf( + ht) -)(() --(+>||- - 116 v v2f(o hr) h S |1bll J ||v2((x f(x (
(22)
= -f V f(z + &
$ <(V dr) =
In the first inequality, we use the definition of the operator norm and the triangle inequality for the integral. The triangle inequality yields
ht)ll = [VV IV vf(=))] V
[V)] < v(t).
Note that v1) = f(< + ho)ll) and is non-decreasing. Thus v1(1 N {[]V\( + +()) for all / 2 0 and e(0) = 0.
Instead of this incquality, consider the differential equation
g'(t) v[IV s(t), g(0) = 0,
(23)
where g RR+ - R is solution, and [ a fixed quantity. Using the standard differential algebra, we can solve
[())))) di Le ([IV =1= = )(())
dg(L)
dg(v)
((L)) {(Vf(=))+ =t.
de
Recall the definition of the function g. which an increasing and differentiable function on R., with (s; for all 8 E R... Therefore, q -1 is strongly increasing and differentiable on [0, 4max) and we can take g(t) - q (1: [[V(()))) for
all t [0, (max). One can check that gtt) is a solution of (23). Let us define p(t) = v(t) g()). Then p(0) and
(t() = (u(t) - g()) < f(IV) + ott) - e(IV +
Let us fix any [0, (max). Since l is locally Lipchitz, there exists M 2 0 such that
(t) - M |il] (v(t) (()) = .M [()]
for all t E [0, b] because vt) and g(t) are bounded on [0, 6]. Using Grönwall's lemma (Gronwall, 1919), we can conclude
that p(t) < p(0) exp( (Mt) = 0. Thus v(t) I g(t) - (t: f=))l)) for all t E [o, b). The last inequality holds for all L E (0, 4max) because is an arbitrary value from [0, 4max)) Finally, using (22), we get (21).
C. Proof of Lemma 4.5
Proof. If y, then the lemma holds, since q is non-negative Otherwise, using Taylor expansion, we get
f(v)= = f(x) (Vf(x), L''' (V5(x x)) Vf(x). -(( x²) dr
$ f(()) (Vf(z) lly xll
fx) dr.
Due to Lemma 4.3:
f(0) < f() (Vf(x),v x) 11 æ11 [ "T 11y =|1: [=)()(]
12

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
f()) + (Vf(c),y 2) L/ |1v==
(r: (V.lVVVV)))
where we changed variables in the integral.
D. Auxiliary Lemmas
We need this auxiliary lemma to find the optimal choice of 7/k in Algorithm 1, and in Lemma I.1.
Lemma D.I. For all E I' and 2 0, the term
U U(t,)) = (2, + I (T;
under the constraints ||b]| = and E [0, qmax (8)) minimized with t" a([l=]]; = ||=|| So [[ and ht* = ل
if + 0, and with t' 0 and any h" E Red. such that ||h|| if 0. With the optimal t" and h², the term U equals
U² =-==-11>11 [/'
1 1 dv. [(s + ||
Proof. The term depends on only in (z, th). Since ||/||| = 1, the term is minimized with /t"
if z + 0, and with 2 [|T
any h" E Rd such that |h"||| 2 0. In both cases, we get
//" a (T:
U -
with optimal choice of h. Next, we can take the derivative w.r.t. and obtain
U ||ж|| + (t:
U is strongly increasing because q- is strongly increasing (see Definition 4.1). Moreover Ug < 0 when t = 0. Thus, there exists the optimal t" defined by the equation
(24)
If |||||| 0, then 0. Otherwise,
t" r-= |=|| du
dv
E(s + -111 E(s + [|=
For this choice of l" and h"," using the change of variables p= p= (T;8)) we get
roll= lt)
= - =-([==]]=s)) || + ((ai] pdq(p; s)
||
U = [[1[]||| + g =
||2|| J. ||=|| 1 dv + jo ((stv
|| v du - S/' e(s + || v)
( -1212
1 1 dv.
((s
We will require the following lemma to ensure that Algorithm is well-defined. This lemma says can safely do step in direction with step size t E [0, qmax fz))())
Lemma D.2. For fixed X, the point y th X for all & [0, (mmxx (I and h E RRd such that ||]||| 1.
The proof is bit technical and can be skipped by the reader if X R
13

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
Proof. Let define y(u) x+ +ttth for all j [0, 1]. Note that y(1) y and y(0) A.. Using proof by contradiction, assume that y(1) & A. Then
j = sup 2 0 ( E } E [0.
(()) & X, and v() belongs to the closure of A' because A' is open convex and f is continuous on the closure of X. Next, v()) E X' for all < j and
f(y(u)) S f(z) at (VS(2).)) + J q (T:
(25)
for all 1 < ji due to Lemma 4.5. Since the r.h.s. is continuous for all μ E [0, 1] because take sequence { such that un, ji and lim Un μ. Thus
[0, 9max (I [+))))),,, we can
lim f(x) put (Vf(x).)) + / un! n
9 (T: [V:
(26)
f(x) ju (VS()))))) J (r: (T: <0..
Since is continuous the closure of X, have
f(v(a)) lim [(((un) 25,200
co.
which contradicts y(ū) & X
E. Proof of Corollary 4.6
Proof: Corollary 4.6 follows from Lemma D.1 with s [V/(')) Vf(a), and y² = + thh". It is only left to show that 3² E X, which follows from Lemma D.2.
F. Proof of Theorem 5.1
Proof. Notice that Algorithm 1 uses the optimal gradient descent rule from Corollary 4.6. Thus, for Algorithm 1, we have
f(zx+1) S f(xx) -(ax)-1V L. f(I[v)(xx)] [V de.
1
(27)
Corollary 4.6 automatically ensures that 26+1 X if Ix E X. Thus Algorithm is well-defined because E X. Note that
J. f(IVf((x)) + [|V]==>))+++++[[aaa)))
1/2
du 2
f(x)) + [V(((x)] de 1 E(IVS(>))II + [VV[(x))] du 7k 6
00
1/2
du
V[(x))
4
where the last inequality because is non-decreasing. Substituting this (27), we get
f(*x+1) & f(x))
7A
4 [V+
Summing this inequality for t: =0 O,..., 1, dividing the result by T' taking the minimum over A E {O...., T - 1}, and using Assumption 3.2 and Remark 4.7, one can get (9).
G. Derivation of the Rate from Section 5.3
Let us now apply Theorem 5.1 with {(s) {(s) Lo + L1s" and 0 I p
25
[V
4A
min kE 1} Lo 2 L1 [f
(28)
T
14

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
Remark G.I. Due Theorem 5.1 and Remark 4.7, the term 2 is not tight and could potentially be improved. However, achieving this improvement would require calculating the integral in Y explicitly instead, which results in "lengthy trigonometric formulas."
We continue with (28) to get
[V
2-0 1
84
min WE (0....7-1))
min
(29)
Lo
L1
T
for all p because max y) 2 x for all v, 2 0. If S 2, then we can guarantee (o.... |I (xxx)) after at most
32LI
max
E
c(2-p1/2
iterations.
H. Derivation of the Rate from Section 6.2
Using (29), either
8 T
T
kE AE T-1
min
[V
<
or
max (E(O....TT-1)
2 41 A
We now require Assumption 6.1. Since the gradients are bounded by M, we can conclude that the method finds an e-stationary after
64T,
max
iterations because maxae(O....TTI)) [[x](=))) MP-2
I. Proof of Lemmas in the Convex World
The following proof technique is based on the classical approaches by Nesterov (2018). We start our proof by 1 V N f(x) f(y) (Vf(y),x y) and [V - fly)ll S
generalizing the inequalities 2T.
(vV - VV(y), x y), which are true under !-smoothness (Nesterov, 2018).
Lemma I.1. For all x, y E X, if f is smsoohh (Assumption 3.1) and convex. then
1- L. [(VS -
[V)(x)
VلWiI1 -
du fo) v)
(30)
and
(V/(x) - w)
1-c + [[( [V Vf - Vf(=)) - +
1-
(31)
- vf(
dv.
As in (Nesterov, 2018), we define the function Φ(v) := f(0) (Vf(z)), v) for fixed xo E X. For all X, have
Proof.
((m)) min d(y) min {s(y) (VI(20),)))
yEœ
vEd
Lemma
|1y-z|1
S
min
[(x) (VI(x). xx)
q- (T. ((Vpaa))))(V((((())))\>>)) (VS(20),))
yEX
15

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
1v-z/l
min y
f(x) + (Vf(x) - y x) + J q (T; (/t[VV/()))--/V///
(Vf(z) - vf((o)) y- =x)+ + flu-zll
= =((x)= + min
q (T: [T(x)]])
yE
||||=1,tE 00.0ma (()))) (V[(x) (s(zo), 1h) + S (T:
S ((x) +
min
Lemma D.1 with 2 v.(=)) fx0) and [[v](z)| ensures that
((x)) - Φ(x) VV) - V -V/wa\ L:
1- ((IV + +VV((z) vf(x))) dv.
Thus, get (30). One can get (31) interchanging and y in (30) and using (30) two times.
Lemma 1.2. Suppose that Assumptions 3.1 and 7.1 hold. Then Algorithm 1 guarantees that
1 2 | - x=11² S 2 || x_11²
f(xx) fxx))
E(2 (((x))l
for all k 2 O.
Proof. Due to the strategy from Alg. 1, we get
| - x..1l = ||0x x=112 27 (5x R4: Vf(xx)) + + [+)()))
(32)
We now consider the last two terms:
27k (0t - n., vf((z)) + + [V
2 (-f(xx)) + f(xx) + (Vf(=)) I- -xA) - f(xx) + f(x))()))))))))))))())))))))ff + + [
(3)) S 7h [[+)2=))1? (Tx -2 L [[V((())) du) 27 (f(zx) f(x)))
1-
Note that
7/k - 2 |. ((I](()))]
1-v
du = S'' <([[V[(**)] +
do [[(x)))) || - = E(IV (xx) du
(2u 1)dv 00
((I[[[(x))]) v)
because é is non-decreasing. Thus
2%k (x F., vf(xx)) + + (V - -27 (f(xx) - f(x)))
Substituting this inequality to (32), we get
|| 2=11² < || x=11² 1----2277 27 (f(x)) - fxx))
and
1
| -x,12
1 1110 1=
f(xx) - f(x.) E(2 (z>))l))>))))
2
due to Remark 4.7.
16

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
J. Proof of Theorem 7.2
The following proof is based on the techniques from (Vankov et al., 2024).
Proof. Using Lemma I.2, we obtain
2 | - 11011-xxa12- S 1|=x -x.11=
1
(xx.)
At the same time, using Theorem 5.1 and Remark 4.7, we obtain
[V S [V/((a))) 5 ((xx) ((r.)
4f (((x))
and
[xxx2]
S <4((x)) - -(xx)).
((2 [2
S 15 (4fx) Defining Su = [(xx) - f(x.) and v/2(x)) = [(20)' we get [VS(x)) $
x²²
and
SK.
|, - 2.112 2
1 - x..l' 1
1(265
(4fx))
(v2 (4fi)) 2 x fN
1
| - x2.12
2
(1/2 (4fx)) x ((20)) (4fx))
(05' (4fw))
where the first inequality because é is non-decreasing. The equality 8(20, (afz)) inequality to
22(22 (4fr))
4fx simplifies the last
4(fa)²
|k+1 v2.12 s 1 x.112
(v5 (15'(11))) (4fa))
Summing the inequality for {O....,. T - 13, we obtain
T
4(fa)²
- ro - 1I=11
( (4fh))
k=
(
|:00 1=1
min kETO....
(v55 (4fx)))
8T
and
fs
100 - xz ||
min
SE. T 11) 1/ (4
2VT
For all x, t. > O, notice that
2
T
+
D = (:5((4r) (4x) + 2/2 (2)
4x +
15
4x +
= t2.
(x)
6 ((4)
48 (4)
Thus
fp 2/
Io x=,1 1
min
kE (O.....- T-I.. 1) /
1 10-g-2_1
SThis the place we use that the function (x)
2
strictly increasing and 2/2(00) cc.
[(23)
17

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
K. Derivation of the Rate from Section 7.2
Let us define fN = f(xx) - f(x.). Then fT (i...e fu and fo. For (p, Lo. Lim-mmotthness,, we should take ((s) Lo + LisP, use Theorem 7.2, and get min kE(O....T) Lothi
R T+I
Using the inequality x + y S
297 +irk)
2 max wh: we obtain min kE
min
fu 2he 221
lf2 T+I.
For S 1, the method finds s-solution after at
11)
most
Ro 166, 2/12- 1622/12-1 p) R²a
T:
2( 211-p)/2-pp
iterations. One easily show this by swapping min min, noticing that the terms under the min operations keO....,
non-decreasing functions of and fr min
Sk, and considering three cases: (i) 21,54
fT
(ii)
k
2Lg
2UTHT
fr 2Lo
and 1, and (iii)
f
(2VT4T) and 1.
21,17-1
2Lg
21,57
(T+1)2-3 For < p 2, either fr S T+I or T.2011
LL
max fk_ Since fa is decreasing (see Theorem 5.1), the second ke (O.....))
R
option implies (I'+ + 1)²- < L,20t1 R2-P p60 f601
meaning the method finds solutiio after at most
R
16L 2- RR
M(p-11 2-p
max
iterations.
L. Proof of Theorem 8.1
Proof. Using Lemma I.2, we obtain
2 | - x..1² S 11 x..12- f(x)) (z.) [(2 (((x))
(33)
for all k 2 0. [+V](z))]] is decreasing due to Theorem 8.3, We fix any T 2 0. Thus, for all A: 2 T, we get
|| - xx,11 1 12.11-- f(zx) -(ox)=f(2z) f(z.)
[(
Summing the last inequality for k = T...., and dividing by T - T - 1, we obtain
S(IT) - f(x.) {(2 V (x ) ||- xx1l
[| xxll?
2(T - ++
2(T - (
where use the inequalities || - x2.111 1 ||5 - x..12 1xT - x. 2
due to (33). For any 2 0, taking T(M) such
that || f= M, we get
[WT)) [(xx) 5 {(2M) |100 1211
2(T - T(M) + 1)
Thus, after
T(M) + ((2M) |1:00 - vr,l1
2e
iterations the inequality f(TT) - fxx)) S holds. The final result holds since M > 0 is arbitrary.
18

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
M. Proof of Theorem 8.3
Proof. We have
+ Vo H1/00///222t/Y//a////////-/-/1/> V/((x))
= =|V/(<=)]]* (/ -
Lemma 4.3 guarantees that
- vx((=)]] S 9 ' ( (f(x)))
Notice that
Th [[ I."'
Det.5
V[ +
Thus y (7) [>>>>>
and
[V/( V/(xx) s [V/(xx)]l
(34)
Ignoring the first non-negative term in the integral of (31), we obtain
(Vf(I++1) - Vf(xx), mA) > [ff(x++1 ((((==++1-(((xx)))) f( L. [()))(
1- + | v) du
(34)
- L. + (V{aa)))) de.
1- v
Therefore
VV ( [
[++()=)]
2 (3) [[I[](()))
1
do 7/6 [1V 2
7k
+ |
1 1 2v
|[/((m))
du |V/(<c+1)
7k
+
Since l is increasing, obtain
L. I fxx)
1- 2v
du 2
and
[ 0)1 [+
N. Proof of Corollary 8.4
Proof. For all 8 > O, using Theorem 8.3, Corollary 5.2, and the fact that sup=20 r>2(x)) > 0, there exists (1, A, large enough, which depends only on E, A, and 6, such that ||V [ )|| < 6. Since is continuous, there exists 5()) > 0, which depends only on such that (()) < 28(0). Taking = (E, A) == (E A, 8())), we get [|v](x))] $ 5(8) and
(15) < 7 + {(2(()))
<T {(0)
2
Thus Algorithm converges after ( + T () iterations because it converges after (15) iterations (Theorem 8.1).
19

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
Additionally, we know that
{ (
f(2 (
(15) S ((IV)( +
2
2e
where T(IVV (z)))l) 0 because it is required zero iterations to find point such that the norm of a gradient is V (the starting point satisfies this criterion). In total, Algorithm converges after at most
Re (C, A(2 V (3o)
E(O)R2 min (t.A). ((2 (2 Rt
2s
8
25
iterations.
O. Proof of Corollary 8.5
Proof. Using Theorem 5.1 and Theorem 8.3, we get
[V((rr-ill& 4E(2 VV (fao)))
T
Thus, for all 8 > 0, one can take (e, A, (/(x))) 42/2 / A ensure that [[V )| < 6. Since is continuous, there exists 8(E) > 0, which depends only on l, such that ((20(()) 20(0). Taking = T (e. A, [ := (e, A, (x))[ 5())), we get [++]) < ((E) and
(15) < ((2 ST E(
28
Thus Algorithm converges after (19) iterations because it converges after (15) iterations (Theorem 8.1). One can get the second term in the min using the same reasoning at the end of the proof of Corollary 8.4.
P. Proof of Theorem 9.2
Let us recall the standard result regarding the large derivation of the sum of i.i.d. random vectors. Lemma P.1 (Simplified Version of Theorem 2.1 from (Juditsky Nemirovski, 2008)). Assume that (n. are i...d. random vectors such that 7). Rd. E [m,] and E exp [lmil /o²) s exp(1) for all e [n]. Then
m
P
Σ
-2(1+ N)
S <exp(->2/3)
for all A 2 0.
We now proof the main theorem:
Proof. Using Lemma P.I, we get
1
P
(z(zi -V((z))
V
2 2 N)o/VB
B
B
E
P
-
2 22 + \)oo / IT
< <xxp(_>2\3)
B
for & 2 0, where IP (-|ax) is the probability conditioned on Ty. Using the union bound, we obtain
V2(1+ 1a/oVBBBBBB \ 1)
P
V -
k=
20

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
B
-
v
V (((a))
2 V21 + Ajo/VBB
S Texpp->\/33
B
k=
32 1- (1ogg1/))/))
Taking À = (og(()))) and B = max
we can conclude that with probability 1-6, --
1
S VE
11 - v/(xx)]
vs(x))) -v(
Σ
(35)
B
j=1
and
v8 4
g S [f((z)]] + ve
(36)
for all & {O....,
T 1}, where we use the triangle inequality.
To simplify the notation, we assume that all subsequent derivations hold with probability 1 1- 8, omitting the explicit mention of it each time. Using proof by contradiction, we now prove that there exists k E (O...., T 1} such that [V < e. Assume that
(37)
for all & E to..... T 1). Then
[[((a)]
11 - vf(xx)]1
(38)
and
3 [f(xx)]
4
S |1 S I [V{(mi)]
(39)
from (35) and (36). Since l increasing, we obtain
= I'
1
| de
Thk |1
5r
8 { 11
(39)
[ du
Jo r rx ( V/((x)]] + ())())))
By the definition of the ratio r, we get r
{ [/(x)))]+ ( Therefore
V ((r MI
7k 11 S 4 1 E [[IVf(=>)] + + [f(x))
[f{x))] de
(40)
$ L.' ([Vvf(=))] + [z(())] 9//4 [144
[ du
where q is defined in Definition 4.1. Notice that F441 Fb TA9 2g 7h |1 | and n ||ax|l < 2 ( < 9max (IV fzx))l). Thus, IR+1 E X' due to Lemma D.2 and we can use Lemma 4.5 to obtain
malloall
f(xx-1) S f(xx) - Th (Vf(z)).9)) +
(r(
f((x) 7k - vf(xx)) + / Melloell (f(x)\\(()))))
21

---

Toward a Unified Theory of Gradient Descent under Generalized Smoothness
milllall
CS
S f(z)) 7 [ + yA [[+)] 1lax
v.((x))]++
+
q (T:1
(38)
3
[V+ 112 + (oalloul q (T:
S f(x))=
4
Since q-1 is increasing (Propostion 4.2), we have
3
[(*+11) S fxx)
[V(()))]|
+ TN 119
(7H 11ax [[V][(
(40)
$ f(z))
3
[v((*))]1
7k
4
37k
5
S [(xs)
[V[(x)
4
16
S f(x)) - 2kk
|V
4
It is left sum this inequality for k (0,... T 1} and use Assumption 6.1 to get
4A
Th [V/(2)]|
T
and
4A T
min kE aE(O..... -11
*k [fxx)]] $
Due to Remark 4.7 and (39),
7* 2 5rl (3(
and
V (x(x)))) Srx x
45A T
min
(41)
kE -1] (3 V (l)
Since (41) holds, we conclude that minke (o.....TT. [f(x)))] s due the choice of T specified in the theorem. This result contradicts (37).
Q. Function -p + -l is (Li L1) -mooth In this section, we prove that the convex function f R + R such that f(z) par + _ is (LiH, L1) smooth. Indeed,
[ 1.fe-1
Then
V v'f(z)] Liehi S Lip+ Ln Lietuz - 11| S Lift La IVf(())
because
[f((a)] 12 -p)²
Finally,
v f()) < Li + L1 ff(x)]l
At the same time, for any A 2 0, there exists such that 41 x > 24
2A
We get Le < Vf(x)]]
< Lie and
bi
L
2T, [>])] > ||>]]()]|| 1.7e 1=
|VS(,)]
Thus, the second constant in the assumption can be improved by at most of factor
22


Reviews:
[{"review_id": "VUSmrzZqgi", "reviewer": "Reviewer_eBsG", "summary": "This paper studies the performance of the Gradient Descent (GD) method under a generalized $\\ell$-smoothness condition. The authors propose a universal step size applicable across different parameter choices. Using this step size, they improve existing theoretical results and establish new convergence guarantees for previously unexplored settings.\n\n## update after rebuttal\nThanks the authors for answering my questions. I decide to keep my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive review!\n\nWe would like to clarify the weaknesses:\n\n> Can these results be extended to the constrained setting?\n\nThis is a good question. We have not yet explored this extension in depth; however, it appears that the constrained setting might be more challenging than in the $L$-smooth case. This is an important future work.\n\n> It would strengthen the paper to include experiments demonstrating the universal applicability of the proposed step sizes across different problem settings.\n\nOur main objective was to establish new theoretical results, supported by toy experiments. We acknowledge that there is significant potential for further research to explore the proposed approach in various practical and deep learning scenarios.\n\n> More details on the practical implementation of the step size computation would be beneficial.\n\n\nIn our implementation, we use the standard `scipy` library as follows:\n```python\nimport scipy.integrate as integrate\n\ndef find_step_size(ell, norm_grad):\n    return integrate.quad(lambda v: 1 / ell(norm_grad + norm_grad * v), 0, 1)[0]\n```\n\n> For experiments mentioned in Appendix A, it would be better to provide a figure to show the results.\n\nWe have prepared figures (see [figure](https://www.dropbox.com/scl/fi/xo2pr2cow8201ce4p75mj/fig.pdf?rlkey=cyhhm2wbvqrr2b21xqezzmjbi&e=1&st=7n46aqyx&dl=0)) that we will include in the camera-ready version of the paper.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. I think it is correct.", "experimental_designs_or_analyses": "Yes. In fact, there are no experiments in the main content.", "relation_to_broader_scientific_literature": "See below.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Weaknesses:\n* Can these results be extended to the constrained setting?\n* It would strengthen the paper to include experiments demonstrating the universal applicability of the proposed step sizes across different problem settings.\n* More details on the practical implementation of the step size computation would be beneficial.\n* For experiments mentioned in Appendix A, it would be better to provide a figure to show the results.\n\nStrengths:\n* The paper provides a unified analysis and a universal step size for problems satisfying the $\\ell$-smoothness condition, which encompasses many existing smoothness assumptions. Furthermore, the convergence results recover all known results as special cases.\n* By leveraging the new step size, the authors improve the convergence rate of GD for certain function classes.\n* The paper is well-written and easy to follow.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above.", "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": {"ethical_review_concerns": "N/A"}}, {"review_id": "8bhoLCMgih", "reviewer": "Reviewer_PL6G", "summary": "The paper discusses optimization under the generalized smoothness assumptions and show a choice of step size that improves the known convergence bounds in this setting. The paper also presents convergence rates in scenarios where previous work did not consider (e.g., $\\rho\\geq 2$).\n\n# Update after rebuttal\n\nIn the rebuttal, the authors addressed my concerns about the computational cost and the accuracy needed in calculating the new step sizes. The is a good paper and I support in acceptance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you!\n\nLet us respond to the weaknesses and questions:\n\n> The fact that the new step size does not always have a closed-form expression could pose challenges for its practical implementation in real-world applications.\n\nWe now show how we implement it in the experiments and how it can be done in Python:\n```python\nimport scipy.integrate as integrate\n\ndef find_step_size(ell, norm_grad):\n    return integrate.quad(lambda v: 1 / ell(norm_grad + norm_grad * v), 0, 1)[0]\n```\nWe believe that the implementation is straightforward and only requires the standard `scipy` library.\n\n> From a theoretical perspective, the additional computation required to determine the step size at each iteration may negatively impact the overall computational complexity compared to standard gradient descent.\n\n> For a general $\\ell$, what is the computational cost of computing the new step size with a precision of $\\delta$?\n\nWe agree that the function above requires an additional call to `integrate.quad`. However, compared to the complexity of gradient computations, this operation is negligible. Calculating a numerical integral of a bounded and well-behaved function is a very simple one-dimensional numerical task.\n\n> Is it necessary to compute the step size exactly in order to achieve the improved convergence rates? If not, how do the convergence bounds degrade when the step size is determined with an accuracy $\\delta$?\n\nThis is a good question. We have not investigated it in detail, but the rationale is similar: computing the numerical integral in one dimension with very good accuracy is a very inexpensive operation. This operation is almost as simple as calculating $e^x$, division, and so on, which are also not computed with perfect precision. However, the errors arising from summation, division, $e^x,$ $\\sin x,$ and other standard operations are typically ignored in practice due to the high level of accuracy.", "claims_and_evidence": "Yes, all of the theoretical claims in the paper are proved in the text or in the appendices.", "methods_and_evaluation_criteria": "Yes, the paper is mostly theoretical.", "theoretical_claims": "No. I focused on reading the main text of the paper.", "experimental_designs_or_analyses": "No. I focused on the theoretical part of the paper.", "relation_to_broader_scientific_literature": "The paper show convergence bounds that improve rates from previous work. Moreover, there are bounds for scenarios that was not studied in previous work. This improvements are achieved due to a different step size than considered in previous work.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n \n1.The paper is well-written and clearly presented.  \n2. It establishes improved convergence rates for gradient descent under the generalized smoothness assumption in both convex and non-convex settings, which has been a topic of growing interest in recent years.  \n3. The approach of utilizing the function $q$ to reformulate the generalized smoothness conditions and derive a new step size is both novel and insightful.  \n4. The proposed step size allows the authors to obtain new theoretical results, also in the case of $\\rho \\geq 2$.  \n\nWeaknesses:\n\n1.The fact that the new step size does not always have a closed-form expression could pose challenges for its practical implementation in real-world applications.  \n2. From a theoretical perspective, the additional computation required to determine the step size at each iteration may negatively impact the overall computational complexity compared to standard gradient descent.", "other_comments_or_suggestions": "N.A.", "questions_for_authors": "I have several questions regarding the computation of the new step size:  \n\n1. Is it necessary to compute the step size exactly in order to achieve the improved convergence rates? If not, how do the convergence bounds degrade when the step size is determined with an accuracy of $\\delta$?  \n\n2. For a general $\\ell$, what is the computational cost of computing the new step size with a precision of $\\delta$?", "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": "9Drmbb2WhL", "reviewer": "Reviewer_4Yov", "summary": "This work improves the convergence rates of gradient descent on the $\\ell$-generalized smooth problem for both nonconvex and convex settings by using a novel integral-based stepsize. Then it extends the results to stochastic gradient descent algorithm.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you! \n\n> Please plot the learning curves which makes this criterion more clear.\n\nWe've done this. We will add the following plots to the section with experiments: [figure](https://figicml.tiiny.site/)\n\n> Weakness mainly in presentation: (1) In ICML papers, usually Section 1 is introduction which introduces the studied problem, the drawback of existing works and the contribution of this work (move your Section 4 here) are missing in the Section 1.\n\nThank you for the suggestions. We tried to follow the standard pattern: 1. Problem -> 2. Related Work -> 4. Contributions.  (yet, we added motivating examples to give more motivation to our contributions). **We will align our structure with the reviewer's expectations: i) we will swap \"3. Motivating Examples\" and \"4. Contributions.\" Then, we will unify \"1. Problem,\" \"2. Related Work,\" and \"3. Contributions.\" into one section called \"1. Introduction.\" It can be easily done in the camera-ready version.**\n\n> The experimental results are usually shown by figure or table. In your case, it is strongly recommended to plot the learning curves\n\n**We will add the following plots to the section with experiments**: [figure](https://www.dropbox.com/scl/fi/xo2pr2cow8201ce4p75mj/fig.pdf?rlkey=cyhhm2wbvqrr2b21xqezzmjbi&e=1&st=7n46aqyx&dl=0)\n\n> The final paragraph of Section 2 \"Related Works\" could mention ... You could add them.\n\n> In Section 3, you could add machine learning application examples, for example, the examples in (Chen et. al. 2023). Also, are there any application examples t\n\nAgree. We will add these important papers to the overview.\n\n> The title of Section 5 could be \"Assumptions for Nonconvex Setting\". The title of Section 6 could be \"Preliminary Theoretical Properties\", since the main theoretical results are the convergence results in the consequent sections.\n\nAlso agree; this title makes more sense.\n\n> You could explain how to compute such stepsize  as an integral form in practice.\n\nIn our implementation, we use the standard `scipy` library as follows:\n```python\nimport scipy.integrate as integrate\n\ndef find_step_size(ell, norm_grad):\n    return integrate.quad(lambda v: 1 / ell(norm_grad + norm_grad * v), 0, 1)[0]\n```\n\n> In the equation right after (23), the middle step could use\n\n> Lemma D.1 could define \n\n> Right after Lemma P.1\n\nWe will fix these problems. \n\nThank you very much for the nice review, which helps to improve our work!", "claims_and_evidence": "The improved convergence rates claimed by this work are well supported by theoretical results.", "methods_and_evaluation_criteria": "The numerical examples fit the generalized smooth condition well. The evaluation criterion I guess is the objective function $f(x_k)$, which is standard and reasonable. Please plot the learning curves which makes this criterion more clear.", "theoretical_claims": "By checking some key proofs, I believe the proofs are correct and novel.", "experimental_designs_or_analyses": "The numerical examples and reproducibility (e.g. hyperparameter choices) look fine. It is strongly recommended to plot the learning curves $f(x_k)$.", "relation_to_broader_scientific_literature": "This work studies currently the most generalized smooth optimization problem ($\\ell$-generalized smooth problem), with better convergence rates than the state of the arts in the other works on the same or less generalized smooth optimization problem.", "essential_references_not_discussed": "There are other works on $\\ell$-smoothness, citing Li et al. (2024a). You could add them to the related works.", "other_strengths_and_weaknesses": "Strengths: The $\\ell$-generalized smoothness studied in this problem is so far the most generalized smooth, which covers a lot of examples and applications. The theoretical results and proof techniques are correct and very novel. For example, this work uses inverse of the integral operator $q^{-1}$ which yields an integral-based bound on function decrease $f(x_{k+1})-f(x_k)$ and thus an integral-based stepsize. These further yield convergence results that improve the state of the arts. \n\nWeakness mainly in presentation: (1) In ICML papers, usually Section 1 is introduction which introduces the studied problem, the drawback of existing works and the contribution of this work (move your Section 4 here) are missing in the Section 1. The final item of Section 4 could add \"see Section xx\". (2) The experimental results are usually shown by figure or table. In your case, it is strongly recommended to plot the learning curves $f(x_k)$. **I would like to raise my rating if you improve the presentation.**", "other_comments_or_suggestions": "(1) The suggestions about presentation above. \n\n(2) The final paragraph of Section 2 \"Related Works\" could mention that $\\ell$-smoothness generalizes $(L_0,L_1)$-smoothness. Also, there are other works on $\\ell$-smoothness, citing Li et al. (2024a). You could add them. \n\n(3) In Section 3, you could add machine learning application examples, for example, the examples in (Chen et. al. 2023). Also, are there any application examples that belong to $\\ell$-smoothness but not $(L_0,L_1)$-smoothness (i.e., when $\\ell(x)=\\mathcal{O}(||x||^p)$ with $p\\in(1,2)$ as $||x||\\to+\\infty$). \n\n(4) The exact expression of Eq. (17) could be written in Table 2 for convenient comparison. If there is not enough space, you may consider denoting constants like $c=L_0^{\\frac{\\rho}{2+\\rho}} \\Delta^{\\frac{\\rho}{2+\\rho}} L_1^{\\frac{2}{2+\\rho}} R^{\\frac{4}{2+\\rho}}$. \n\n(5) The title of Section 5 could be \"Assumptions for Nonconvex Setting\". The title of Section 6 could be \"Preliminary Theoretical Properties\", since the main theoretical results are the convergence results in the consequent sections. \n\n(6) You could explain how to compute such stepsize $\\gamma_k$ as an integral form in practice. \n\n(7) In Algorithm 2, you could explain that {$\\xi_{kj}$}$_{j=1}^B$ are i.i.d. samples. \n\n(8) In the equation right after (23), the middle step could use $g(v)$ instead of $g(t)$ to avoid confusing the two $t$. \n\n(9) Lemma D.1 could define $U$ as $U(t,h)$ to be more clear.\n\n(10) Right after Lemma P.1, \"We now prove the main theorem\".", "questions_for_authors": "No questions now.", "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": {"ethical_review_concerns": "N/A"}}, {"review_id": "xi16muIJ5N", "reviewer": "Reviewer_fNss", "summary": "--------- \n## Update after rebuttal\n\nThe authors showed that the issue in the proof can be fixed. I checked the corrected proof and it looks good to me, so I'm raising my score.\n\n-------------\n\n\nThis paper studies the convergence of gradients descent under a generalized assumption on the objective $L$-smoothness. Assuming that the Hessian of the objective $f$ satisfies $\\Vert \\nabla^2 f(x)\\Vert \\le \\ell (\\Vert \\nabla f(x)\\Vert)$, where $\\ell$ is a nondecreasing positive locally Lipchitz function, the authors show that with the stepsize $\\gamma_k = $. The authors give a few good motivating toy examples such as classification with a linear two-layer network with a single parameter in each layer. Even this extremely simplified  example is not covered by previous theory, while the new work gives result if we choose $\\ell(t) = L_0 + L_1t^\\rho$ with some $\\rho\\ge 2$ (previous work only covers $\\rho < 2$). And even in the case where the previous work does cover examples, the new stepsize rule leads to a superior  complexity.\n\nThe authors study nonconvex and convex problems. There are certain limitations to the results and one of the results is wrong (see the Theoretical Claims section of my review). The results for the case where $\\ell$ is sub-quadratic have been already covered by the previous work, even though with a worse complexity, while the super-quadratic $\\ell$ requires an assumption on bounded gradients. So while I found some of the small facts discovered in the paper to be elegant, the paper feels a bit inconclusive and doesn't seem to solve the problem of minimizing the functions advertised in the motivation. \n\nThe empirical results are very small and are only provided in Appendix A. \n\nTo conclude, the paper has very solid motivation, but the results are a bit underwhelming, especially taking into account one of them is wrong. I think removing the wrong part wouldn't be too difficult.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review!\n\nWe now start with \"Mistake in the proof.\" Thank you again for spotting a typo in the paper. **We will try to explain that this is a typo rather than a mistake because it is sufficient to fix \"max\" to \"min,\" and nothing else should be changed.** Let us clarify this part. Both we and the reviewer agree that the right inequality is\n\n$$\\min_{k \\in \\{0, \\dots, T\\}}  \\min\\left[\\frac{f_k}{2 L_0}, \\frac{1}{2 L_1 f_k^{\\rho - 1}\\left(\\frac{2 \\sqrt{T + 1}}{R}\\right)^{\\rho}}\\right]\n\\leq \\frac{R^2}{T + 1}.$$ Let us fix $T$ as in the paper\n$$T = \\max\\left[\\frac{2 L_0 R^2}{\\varepsilon}, \\frac{16 L_1^{2 / (2 - \\rho)} R^2}{\\varepsilon^{2 (1 - \\rho) / (2 - \\rho)}}\\right]$$\n(smallest integer larger than this. Also, we should take 16 instead of 4).\n\nNotice that \n\n$$\\min_{k \\in \\{0, \\dots, T\\}}  \\min\\left[\\frac{f_k}{2 L_0}, \\frac{1}{2 L_1 f_k^{\\rho - 1}\\left(\\frac{2 \\sqrt{T + 1}}{R}\\right)^{\\rho}}\\right] = \\min\\left[\\frac{f_T}{2 L_0}, \\frac{1}{2 L_1 (f_T)^{\\rho - 1}\\left(\\frac{2 \\sqrt{T + 1}}{R}\\right)^{\\rho}}\\right] \\leq \\frac{R^2}{T + 1} (**)$$\n\nbecause the terms in min are non-decreasing functions of $f_k$ for all $0 \\leq \\rho \\leq 1$ and $f_T = \\min_{ k \\in [ 0, \\dots, T ] } f_k$ (see Theorem 7.1). There are three options:\n\n1) $\\frac{f_T}{2 L_0} \\leq \\frac{1}{2 L_1 (f_T)^{\\rho - 1}\\left(\\frac{2 \\sqrt{T + 1}}{R}\\right)^{\\rho}}.$ Using (**), we get\n\n$$f_T \\leq \\frac{2 L_0 R^2}{T + 1} \\leq \\varepsilon,$$ where the last inequality due the choice of $T.$\n\n2) $\\frac{f_T}{2 L_0} > \\frac{1}{2 L_1 (f_T)^{\\rho - 1}\\left(\\frac{2 \\sqrt{T + 1}}{R}\\right)^{\\rho}}$ and $\\rho = 1.$ Using (**), we get\n\n$$(f_T)^{1 - \\rho } \\leq \\frac{2^{1 + \\rho} L_1 R^{2 - \\rho}}{(T + 1)^{1 - \\rho / 2}}$$\n\nand\n\n$$T + 1 \\leq 16 L_1^2 R^2$$ because $\\rho = 1,$ which can not be true due to the choice of $T.$ Thus, the second option is not possible after $T$ iterations.\n\n3) $\\frac{f_T}{2 L_0} > \\frac{1}{2 L_1 (f_T)^{\\rho - 1}\\left(\\frac{2 \\sqrt{T + 1}}{R}\\right)^{\\rho}}$ and $\\rho < 1.$ Using (**), we get\n\n$$(f_T)^{1 - \\rho } \\leq \\frac{2^{1 + \\rho} L_1 R^{2 - \\rho}}{(T + 1)^{1 - \\rho / 2}}.$$\n\nSince $T \\geq \\frac{16 L_1^{2 / (2 - \\rho)} R^2}{\\varepsilon^{2 (1 - \\rho) / (2 - \\rho)}},$ we get\n\n$$(f_T)^{1 - \\rho } \\leq \\frac{2^{1 + \\rho} L_1 R^{2 - \\rho}}{(T + 1)^{1 - \\rho / 2}} \\leq \\varepsilon^{1 - \\rho}$$\n\nand \n\n$$f_T \\leq \\varepsilon$$\n\nbecause $\\rho < 1.$\n\nIn total, $f_T \\leq \\varepsilon$ for both possible options! We agree that these derivations are important, and we will add them to Section K. **The reviewer can see that there are no mistakes in Section K and only a small typo with \"min\" and \"max\".**\n\nLet us respond to other concerns:\n\n> One key paper on the topic has been missed by the authors: Xie et al., \"Gradient-Variation Online Learning under Generalized Smoothness\". \n\nAgree; we will add this paper to the discussion.\n\n> I'd suggest making sections 2, 3, and 4 subsections of section 1. Section 5, 6 could be unified as sections on general theory, while the rest except for the conclusion could be combined into a section on convergence.\n\nAgree; we will do it this way. See our discussion with Reviewer fNss.\n\n> Typos ...\n\nThank you for spotting the typos!\n\n> The authors explain in Remark 6.7 that one can use the stepsize  but it would lead to \"a less tight final result\". Can the authors clarifiy how much worse it's gonna be? \n\nWe believe that it can be significantly worse, and the new iteration complexity with $\\ell(2 || \\nabla f(x_k)||)$ can become $\\sup_{s \\geq 0} \\ell(2 s) / \\ell(s)$ bigger. For the $(\\rho, L_0, L_1)$-smooth setup, the difference can be $2^{\\rho}$ times. If $\\rho$ is large, it is better to use our rule with the integral.\n\n> Can the authors provide an example of how Simpson's rule can be used on a specific example? Taking an example from Section 3 would be particularly illustrative.\n\nIn our implementation, we use the standard `scipy` library as follows:\n```python\nimport scipy.integrate as integrate\n\ndef find_step_size(ell, norm_grad):\n    return integrate.quad(lambda v: 1 / ell(norm_grad + norm_grad * v), 0, 1)[0]\n```\n\nIt is not necessary Simpson's rule, but some other numerical method from the Fortran library QUADPACK.\n\n> To conclude, the paper has very solid motivation, but the results are a bit underwhelming, especially taking into account one of them is wrong.\n\nWe hope that our clarification of the typo improves the perception of our work. Note that our work provides new state-of-the-art theoretical complexities in both convex and nonconvex settings, which we believe constitutes an important contribution to the ICML community given the current interest in generalized smoothness.\n\nThank you once again for spotting the typo!", "claims_and_evidence": "The claims are supported with evidence, I do not see any issue with that, and I'm pretty sure the authors willl be able to adjust them after removing the wrong part of the paper.", "methods_and_evaluation_criteria": "There is no issues with methods and evulations.", "theoretical_claims": "The guarantees in this paper can be split it into several categories:\n1. General **nonconvex** problems with $\\ell(x)$ being **sub**-quadratic. This part looks **correct**, although not very interesting due to prior work already covering it.\n2. General **nonconvex** problems with $\\ell(x)$ potentially being **super**-quadratic. This one looks **correct**, but it requires an extra assumption that the gradient is bounded.\n3. **Convex** problems with $\\ell(x)$ being **sub**-quadratic. There is a **mistake** in the proof (see below).\n4. **Convex** problems with $\\ell(x)$ potentially being **super**-quadratic. This alternative approach seems to be correct as it uses a different proof technique.\n5. **SGD** theory. I checked some steps in the proofs and they looked good to me, they follow the standard steps in high probability bounds. The convergence result requires large batch sizes, which is an issue present in a lot of previous papers on $(L_0, L_1)$-smoothness. It was shown in the work of Koloskova et al. that it's not surprising, clipping biases SGD and it doesn't converge in general. I see this as a small extension of the deterministic results.\n\n## Mistake in the proof \nIn Appendix K, the authors use $x+y\\le 2\\max(x, y)$ in the wrong way. They conclude from $\\min_k \\frac{f_k}{x+y}\\le \\frac{R^2}{T+1}$ that  $\\min_k \\max(\\frac{f_k}{2x}, \\frac{f_k}{2y})\\le \\frac{R^2}{T+1}$, whereas the correct bound would be $\\min_k \\min(\\frac{f_k}{2x}, \\frac{f_k}{2y})\\le \\frac{R^2}{T+1}$, i.e., with $\\min$ instead of $\\max$ since $\\frac{1}{\\max(x, y)} = \\min (\\frac{1}{x}, \\frac{1}{y})$. Unfortunately, I think it's a fundamental issue and can't be easily fixed.", "experimental_designs_or_analyses": "The experiments are only performed on simplified 1-dimensional functions and reported in the appendix providing the number of iterations needed to reach a target accuracy. I think it's fair to say they don't constitute a solid contribution and the paper should be viewed as purely theoretical.", "relation_to_broader_scientific_literature": "The paper extends the prior work on generalized $L$-smoothness assumptions and provides a new stepsize that, to the best of my knowledge, hasn't been considered before. I think the contributions are novel and will be of interest to the optimization community.", "essential_references_not_discussed": "One key paper on the topic has been missed by the authors: Xie et al., \"Gradient-Variation Online Learning under Generalized Smoothness\". The paper considers online learning under a time-varying function $\\ell_t$ in the generalized $\\ell$-smoothness assumption.\n\nOtherwise, the essential references seem to be already in the paper.", "other_strengths_and_weaknesses": "I found it very easy to go through the paper and I'd commend the authors for the presentation of their results.", "other_comments_or_suggestions": "When discussing related work and complexities, the proper definition of complexity is missing, which is especially important in the nonconvex case since some other papers discuss the complexity if getting $\\Vert \\nabla f(x) \\Vert \\le \\varepsilon$ rather than $\\Vert \\nabla f(x) \\Vert^2 \\le \\varepsilon$. Furthermore, the authors need to make it clear they discuss the best iterate rather than the last iterate or the average iterate.  \nI think the section structure is a bit sub-optimal. I'd suggest making sections 2, 3, and 4 subsections of section 1. Section 5, 6 could be unified as sections on general theory, while the rest except for the conclusion could be combined into a section on convergence.  \nTypo on page 4: \"it is know that\".  \nTypo on page 5: \"it seems that this infeasible because to find an explicit formula of the optimal step size using (8).\"  \nTypo on page 5: \"one easily calculate $\\gamma_k$\".  \nTypo in equation (11): the gradient norm power is $p$ instead of $\\rho$. Same typo is made in equation (28).   \nTypo on page 6: \"If $\\ell(s) = L_0 + L_1s^\\rho$ for $p > 2$\".  \nTypoe on page 6: \"finds an $\\varepsilon$–stationary after\"  \nThe way Assumption 9.1 is formulated is a bit weird as it seems to ask for non-uniqueness of $x_*$, which the authors don't need.", "questions_for_authors": "1. The authors explain in Remark 6.7 that one can use the stepsize $\\gamma_k = \\frac{1}{\\ell(2\\Vert \\nabla f(x_k)\\Vert)}$ but it would lead to \"a less tight final result\". Can the authors clarifiy how much worse it's gonna be? From the practical perspective, the rule without integration seems to be a lot more appealing and relying on it would make the paper even stronger. Since (33) alreasy uses $\\ell(2\\Vert \\nabla f(x_k)\\Vert)$, it appears that the simpler choice would work at least for convex problems. \n\n2. Can the authors provide an example of how Simpson's rule can be used on a specific example? Taking an example from Section 3 would be particularly illustrative.", "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:

Meta-review: The paper derives the optimal step size for gradient descent under generalized smoothness assumptions. These assumptions have attracted much attention in the machine learning community. While the reviewers agreed that the work is well motivated and the results are new, the contribution is mainly theoretical, and the numerical advantage of the derived step size rule is far from obvious. The author(s) should take the reviewers' comments into account when revising the paper.
Decision: Accept (poster)