Convex and Non-convex Optimization Under Generalized Smoothness
Authors: Haochuan Li
Jian Qian
Yi Tian
Alexander Rakhlin
Ali Jadbabaie
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Optimization
Convergence
Generalized smoothness
TL;DR: We generalize the classical smoothness condition in optimization, and develop a new analysis approach, which gives much better results for convergence of GD, SGD, and NAG in the convex and/or non-convex setting.

Abstract: Classical analysis of convex and non-convex optimization methods often requires the Lipschitz continuity of the gradient, which limits the analysis to functions bounded by quadratics. Recent work relaxed this requirement to a non-uniform smoothness condition with the Hessian norm  bounded by an affine function of the gradient norm, and proved convergence in the non-convex setting via gradient clipping, assuming bounded noise. In this paper, we further generalize this non-uniform smoothness condition and develop a simple, yet powerful analysis technique that bounds the gradients along the trajectory, thereby leading to  stronger results for both convex and non-convex optimization problems. In particular, we obtain the classical convergence rates for (stochastic) gradient descent and Nesterov's accelerated gradient method in the convex and/or non-convex setting under this general smoothness condition. The new analysis approach does not require gradient clipping and allows heavy-tailed noise with bounded variance in the stochastic setting.

Convex and Non-convex Optimization Under Generalized Smoothness
Haochuan Li" MIT
Jian Qian" MIT jianqian@mit.cm edu
Yi Tian MIT yitian@mit. edu
haochuan@mit.. edu
Alexander Rakhlin
Ali Jadbabaie MIT Tadbabai@mit... edu
MIT rakhlin@mit.edn
Abstract
Classical analysis of convex and non-convex optimization methods often requires the Lipschitz continuity of the gradient, which limits the analysis to functions bounded by quadratics. Recent work relaxed this requirement smoothness condition with the Hessian norm bounded by an affine function of the gradient norm, and proved convergence the non-convex setting via gradient clipping, assuming bounded noise. In this paper, we further generalize this non-uniform smoothness condition and develop simple, yet powerful analysis technique that bounds the gradients along the trajectory, thereby leading stronger results for both convex and non-convex optimization problems. In particular, obtain the classical convergence rates for (stochastic) gradient descent and Nesterov's accelerated gradient method in the convex and/or non-convex setting under this general smoothness condition. The new analysis approach does not require gradient clipping and allows heavy-tailed noise with bounded variance the stochastic setting.
non-uniform
Introduction
In this paper, we study the following unconstrained optimization problem
min
where X' C pd is the domain of f. Classical textbook analyses [Nemirovskij and Yudin 1983
Nesterov 2003 (T) often require the Lipschitz smoothness condition, which assumes [z
almost everywhere for some L > 0 called the smoothness constant. This condition, however, is rather restrictive and only satisfied by functions that are both upper and lower bounded by quadratic
functions.
proposed the more general (Lo, Jsmommothsessss condition, which Lo [=) for some constants Lo, L1 2 0, motivated by their extensive language model experiments. This notion generalizes the standard Lipschitz smoothness condition and also contains e.g. univariate polynomial and exponential functions. For non-comvex and (Lo, L2 -smoohh functions, they prove convergence of gradient descent (GD) and stochastic gradient descent (SGD) with gradient clipping and also provide a complexity lower bound for constant- contanntsteesize GD/SGD without clipping. Based on these results, they claim gradient clipping or other forms of adaptivity provably accelerate the convergence for (Tgg -smoohhh functions. Perhaps due to the
Recently. Zhang et al. 2019 assumes V²
Equul contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

lower bound, all the follow-up works under this condition that we are aware of limit their analyses to adaptive methods. Most of these focus on non-convex functions. See Section for more discussions of related works.
In this paper, we significantly generalize the (To; [ condition the f-smoothness condition which assumes || [(=)( I f())]( for some non-decreasing continuous function We develop simple, yet powerful approach, which allows us to obtain stronger results for both convex and non-convex optimization problems when & is sub-quadratic (i.e., 1im f(u)/u² 0) or even more general. The E-smooth function class with a sub- sub-quadratic l also contains e.g. univariate rational and double exponential functions. In particular, we prove the convergence of constant-stepsize GD/SGD and Nesterov's 's accelerated gradient method (NAG) in the convex or non-convex settings. For each method and setting, we obtain the classical convergence rate, under a certain requirement of f. In addition, we relax the assumption of bounded noise to the weaker one of bounded variance with the simple SGD method. See Table for a summary of our results and assumptions for each method and setting. At first glance, our resul(s "contradict" the lower bounds on constant-stepsize GD/SGD in [Zhang et al., 2019 Wang et al. 2022]: this will be reconciled in Section 5.3
Our approach analyzes boundedness of gradients along the optimization trajectory. The idea behind it can be informally illustrated by the following "circular" reasoning. On the one hand, if gradients along the trajectory are bounded by constant G, then the Hessian norms are bounded by the constant ((G) Informally speaking, we essentially have the standard Lipschitz smoothness condition and can apply classical textbook analyses to prove convergence, which implies that gradients converge to zero. On the other hand, if gradients converge, they must be bounded, since any convergent sequence is bounded. In other words, the bounded gradient condition implies convergence, and convergence also implies the condition back, which forms a circular argument. If can break this circularity of reasoning in a rigorous way, both the bounded gradient condition and convergence are proved. In this paper, we will show how to break the circularity using induction or contradiction arguments for different methods and settings in Sections 4 [] We note that the idea of bounding gradients can be applied the analysis of other optimization methods, e.g., the concurrent work [Li et al. 2023] by subset of the authors, which uses similar idea to obtain a rigorous and improved analysis of the Adam method [Kingma and Ba 2014).
Contributions. In light of the above discussions, we summarize our main contributions as follows.
We generalize the standard Lipschitz smoothness and also the (Io, L1 smoothness condition to the E-smoothness condition, and develop new approach for analyzing convergence under this condition by bounding the gradients along the optimization trajectory.
We prove the convergence of ponstant-stepsize GD/SGD/NAG in the convex and non-convex settings, and obtain the classical rates for all of them, as summarized in Table
Besides the generalized smoothness condition and the new approach, our results are also novel in the following aspects.
The convergence results of constant-stepsize methods challenge the folklore belief on the necessity of adaptive stepsize for generalized smooth functions.
We obtain new convergence results for GD and NAG in the convex setting under the generalized smoothness condition.
We relax the assumption of bounded noise to the weaker one of bounded variance of noise in the stochastic setting with the simple SGD method.
2
Related work
Gradient- optimizaiton. The classical gradient-based optimization problems for the standard Lipschitz smooth functions have been well studied for both convex [Nemirovskij and Yudin 1983
"This statement is informal because we can only bound Hessian norms along the trajectory, rather than almost everywhere within a convex set as in the standard Lipschitz smoothness condition. For example, even the Hessian norm is bounded at both H, and 2. it does not directly mean the Hessian norm is also bounded over the line segment between them, which is required in classical analysis. A more formal statement will need Lemma 3.3 presented later in the paper.

---

Table I: Summary of the results. e denotes the sub- cub-optimality gap of the function value in convex settings, and the gradient norm in non-convex settings. "*" denotes optimal rates.
Method
Convexity
Essmoothness
Gradient complexity
Strongly convex
(log(11 (1/e)) (Theorem 4.3
No requirement
Convex
((1/e) (Theorem 4.2
GD
Sub-quadratic f
(1fe²)* (Theorem 5.2
Non-convex
Quadratic &
Sieep. in cond #) (Theorem 5.4
NAG
Convex
Sub-quadratic ! (11/Ve) (Theorem 4.4
SGD
Non-convex
Sub-quadratic f
(1/cc)) (Theorem 5.3
Nesterov 2003 d' Aspremont al. 202 and non-convex functions. In the convex setting, the goal is to reach an c-sub-optimal point x satisfying f(x) - inf, f(x) I c. It is well known that GD achieves the (1/cc) gradient complexity and NAG achieves the accelerated O(1/Vē /c) complexity which is optimal among all gradient- based methods. For strongly convex functions, GD and NAG achieve the (1x log(1/e) and O (VV log(1/4 fe) complexity respectively, where is the condition number and the latter is again optimal. In the non-convex setting, the goal is to find an estaationary point x e, since finding global minimum is NP-hard in general. It is well known that GD achieves the optimal (11/²²) complexity which matches the lower bound in [Carmon et al. 2017]. In the stochastic setting for unbiased stochastic gradient with bounded variance, SGD achieves the optimal O(1fE*) complexity [Ghadimi and Lan 2013]. matching the lower bound in [Arjevani ct al. 2019 In this paper, we obtain the classical rates in terms of for all the above-mentiones methods and settings, under a far more general smoothness condition.
satisfying [x)]]
Generalized smoothness. The (Lo, L1) smoothhess condition proposed by Zhang et al. 2019 was studied by many follow-up works. Under the same condition, (Zhang et al. 2020 considers momentum in the updates and improves the constant dependency of the convergence rate for SGD with clipping derived (Zhang et al. 2019). [Qian et al., 2021] studies gradient clipping in incremental
gradient methods, [Zhao al.] [021] studies stochastic normalized gradient descent, and (Crawshaw)
ct al.) 2022) studies a generalized SignSGD method, under the (Lo, L1 -smmmottsssss condition. Reeisizadeh et al., 2023) studies variance reduction for (Lo, Lsm-mmooth functions. [Chen al. 2023] proposes a new notion of a-symmetric generalized smoothness, which is roughly as general as (Lg, L1 )mmoothnnsss. [Wang et al. 2022] analyzes convergence of Adam and provides lower bound which shows -ddaaive SGD may diverge. In the stochastic setting, the above- mentioned works either consider the strong assumption of bounded gradient noise or require very large batch size that depends on e, which essentially reduces the analysis to the deterministic setting. [Faw et al., 2023) proposes an AdaGrad-type algorithm in order to relax the bounded noise assumption. Perhaps due to the lower bounds in (Zhang et al.] [019 Wang et al., 2022). J. all the above works study methods with an adaptive stepsize. In this and our concurrent work [Li et al. 2023], we further generalize the smoothness condition and analyze various methods under this condition through bounding the gradients along the trajectory.
3 Function class
In this section, we discuss the function class of interest where the objective function f lies. We start with the following two standard assumptions in the literature of unconstrained optimization, which will be assumed throughout Sections 4 and 5 Jnnees explicitly stated.
Assumption 1. The objective function f is differentiable and closed within its open domain X. Assumption 2. The objective function is bounded from below, i.e., 1 == infzex f(x) > -00.
A function f is said to be closed if its sub-level set for E dom(f) | f(x)= S a} is closed for each a E IR. A continuous function I with an open domain is closed if and only ((x) tends to positive infinity when æ approaches the boundary of its domain (Boyd and Vandenberghe 2004). Assumption I is necessary for our analysis to ensure that the iterates of a method with a reasonably small stepsize stays within the domain X. Note that for X' = Rd considered in most unconstrained
3

---

optimization papers, the assumption is trivially satisfied as all continuous functions over I= are closed. We consider more general domain which may not be the whole space because that the case for some interesting examples in our function class of interest (see Section 3.1.3). However, it actually brings us some additional technical difficulties especially the stochastic setting, as we need to make sure the iterates do not go outside of the domain.
3.1 Generalized smoothness
In this section, we formally define the generalized smoothness condition, and present its properties and examples.
3.1.1 Definitions
Definitions I and 2 below are two equivalent ways of stating the definition, where we use (ix, R) to denote the Euclidean ball with radius R. centered at a.
Definition (f-smoothness), A real-valued differentiable function f: X + IR is E-smooth for some non-decreasing continuous function é [0, +00) (0. +00) if f(x) ((IV) almost everywhere (with respect to the Lehesgue measure) in X.
Remark 3.1. Definition PefinitionDreduceee. to the classical L-smoothness when / L is constant function. reduces the (Lo, -moothness proposed in Zhang et al. 2019 when ((u) Lo + Liu is an affine function.
Definition ((r, -)sooothnesss). A real-valued differentiable function f for continuous functions l: [0. +00) + (0, +o0) where É is non- non-decreasing and r is non- non-increasing. if it satisfies 1) for any x E X, B(x, (())) S X' and 2) for any 21, 22 E ((x))()V(())))) f()) (x(2)) & (())) [||] -x2
IR is (r, f)-smooth
The requirements that non-decreasing and r is non-increasing do not cause much loss in generality, If these conditions are not satisfied, one can replace é and with the non-increasing function F(u) == infos usu r(v) s r(u) and non-decreasing function E(u) == suPoguga ((v) 2 E(u) in Definitions D and
Then the only requirement is > and < co.
Next, we prove that the above two definitions are equivalent in the following proposition, whose proof is involved and deferred to Appendix [A.2
Proposition 3.2. An (r: -m-mmotth function is E-smooth; and t-smooth function satisfying Assump- tion is (r, m))mmooth where mmu)= = E(u + a) and r(u) == s/mm(u) for any a >> O.
The condition in Definition iss simple and one can easily check whether it is satisfied for given example function. On the other hand, Definition 2lis a local Lipschitz condition on the gradient that harder verify. However, it useful for deriving several useful properties in the next section.
3.1.2 Properties
First, we provide the following lemma which is very useful in our analyses of all the methods considered in this paper. Its proof deferred to Appendix A.3
Lemma 3.3. If f is (r, E)-smotth, for any X satisfying [V(()) S G, we have 1) ((xxr((()) C
X, and for any I1, B(xxr(()))
((x1)S((a2)) (VS(22), ( 1020 + L || - x221 (2)
where L = {(G) is the effective smoothness constant.
Remark 3.4. Since we have shown the equivalence between î-smoothness and (r, -mmoothessssss,
Lemma 3.3 also applies to f-smooth functions, for which we have I. - E(2G) and r()) = G/L.
choosing G Proposition 3.2
Lemma 3.3 states that, if the gradient at x is bounded by some constant G, then within its
neighborhood with a constant radius, we can obtain (2), the same inequalities that were derived in the textbook analysis [Nesterov] (2003) under the standard Lipschitz smoothness condition. With (2), the analysis for generalized smoothness is not much harder than that for standard smoothness. Since

---

Table 2: Examples of univariate (p, Lo. Lp) smooth functions for different ps. The parameters a, 6, are real numbers (not necessarily integers) satisfying a, b > 1 and p < or 2 2. We use 1 to denote any real number slightly larger than
P Example Functions
1
1.5
2
Quadratic
Polynomial
a² (b²))
Rational
Logarithmic
x
mostly choose x 222 2e and x1 = z(+1 in the analysis, in order to apply Lemma 3.3 we need
two conditions: V (x+))) I G and | xzll S r(G') for some constant G. The latter is usually directly implied by the former for most deterministic methods with a small enough stepsize, and the former can be obtained with our new approach that bounds the gradients along the trajectory.
With Lemma 3.3
we can derive the following useful lemma which is the reverse direction of generalized Polyak-Lojasiewiic. (PL) inequality, whose proof is deferred to Appendix A.3
Lemma 3.5. If f is E-smooth, then [+) S 2((2 ( forany any x E X.
Lemma 3.5 provides an inequality involving the gradient norm and the sub-optimality gap. For example, when f(u) = u² for some S p < 2, this lemma suggests [[V[(>)] S O ((f(z) - f+))1(2-0)), which means the gradient norm is bounded whenever the function value bounded. The following corollary provides more formal statement for general sub-quadratic l (i.e., oo f(u)/u² = =0), and we defer its proof to Appendix A.3
Corollary 3.6. Suppose f is E-smooth where E sub-quadratic. If fz) ff for some x E X and F > 0, denoting G == sup 2 0 u² < 2f(2u) F}, then they satisfy G² 2E((G) F and we have [<x)]] S. co.
Therefore, in order to bound the gradients along the trajectory as we discussed below Lemma 3.3 suffices to bound the function values, which is usually easier.
3.1.3 Examples
The most important subset Ê-smooth (or (r, sm-sthhth) functions are those with a polynomial f, and can be characterized by the (p, Lo, -mm-shhth function class defined below.
Definition 3 ((p, La. smmoohhses)ss A real-valued differentiable function f is (p, Lo. -mooth for constants p. Lo. Lp 2 O is Ê-smooth with E(u) = Lo + Lpw..
Definition 3 reduces the standard Lipschitz smoothness condition when p 0 Lp and to the (Zo, -smooohhtsssssss proposed in [Zhang et al. 2019] when P = 1. We list several univariate examples of (p, Lo. L, )-moothh functions for different ps in Table 2 with their rigorous justifications in Appendix A Note that when æ goes to infinity, polynomial and exponential functions corresponding to p grow much faster than quadratic functions corresponding to p 0. Rational and logarithmic functions for
grow even faster as they can blow up to infinity near finite points. Note that the domains of such functions are not Rd which is why we consider the more general Assumption ! iisteedd of simply assuming X' Idd.
Aside from logarithmic functions, the (2, Lo, -mmosh function class also includes other univariate self-concordant functions. This is an important function class in the analysis of Interior Point Methods and coordinate-free analysis of the Newton method [Nesterov] 2003 More specifically, convex function h R + F. is self-concordant if (x)) 22)(2)3//² for all R. Formally, we have the following proposition whose proof is deferred to Appendix A..
Proposition 3.7. If IR + a self-concorlani function satisfying li(()) > over the interval (a, b), then h restricted on (a, b) is (2, Lo. (..2)))smmoee smooth for some Lo 0.
4 Convex setting
In this section, we present the convergence results of gradient descent (GD) and Nesterov's accelerated gradient method (NAG) in the convex setting. Formally, we define convexity as follows.
5

---

Definition 4. A real-valued differentiable function f X + RR is p-strongly- for μ 2 0 X is convex set and f(v) - (() 2 (v)(z) - x) Eu2 lly x²| for any x, X. A function is convex if it is u-Strongly-convex with = 0.
We assume the existence of global optimal point x throughout this section, as in the following assumption. However, we want to note that, for gradient descent, this assumption is just for simplicity rather than necessary.
Assumption 3.
There exists point x² E X' such that f(x") = == =inf=ex ((x).
4.1 Gradient descent
The gradient descent method with constant stepsize is defined via the following update rule
Et+1 Zz V f=z).
As discussed below Lemma 3.3 the key in the convergence analysis is to show [ < G for all t 2 and some constant G. We will prove by induction relying on the following lemma whose proof is deferred to Appendix
Lemma 4.1. For any x E X satisfying
[VV[( & G, define xt = x - v V.()). I is convex
and (r, E)-smooth, and 1j S min EGG) 26 p we have xt E X and [V(+))]]| s [[][()) G.
Lemma suggests that for gradient descent with small enough stepsize, if the gradient norm f+=)) I G. i.e., the gradient norm is also
at 24 is bounded by G, then we have (x < bounded by G t 1. In other words, the gradient norm is indeed non-increasing potential function for gradient descent in the convex setting. With a standard induction argument, we can show that [[V[(ar < (xr)] for all 0. As discussed below Lemma 3.3 then we can basically apply the classical analysis to obtain the convergence guarantee the convex setting as in the following theorem, whose proof deferred to Appendix B
Theorem 4.2. Suppose f is convex and (r, E) -moothh. Denote G == [[ and : E(G), then x() satisfy [ S for all t 2 0 and
the iterates generated by with 1 I min
I
20
100 x x²1
f(xr) - f"
2n
Since 1) constant independent or T, Theorem achieves the classical O11/T) rate, or O(1/c) gradient complexity to achieve an c-sub-optimal point, under the generalized smoothness condition. Since strongly convex functions are subset of convex functions, Lemma[4.l]sii holds for them. Then we immediately obtain the following result in the strongly convex setting, whose proof deferred to Appendix
Theorem 4.3. Suppose J is y-strongly-comvex and (r, E)-smooth. Denote G r(G) 1 L. 26 satissy fxx)) < for
[V)(z)) and
L = (G), then the iterates generated by (3) with n S min all 2 0 and
f(IT) - = 111 n/)
2(1 m,)T" ||:0 - 1=1
Theorem 4.3
gives a linear convergence rate and the ((()))
(Le) (ogg))-logg(eee) gradient complexity to r(C) 1 (see Remark 3.4
achieve an --subopttmall point. Note that for f-smooth functions, we have _ which means the local condition number around the initial point zp. For standard Lipschitz smooth functions, reduces to the classical rate of gradient descent.
choose 27. Then obtain the O( log(1/e)) rate, where := L/
4.2 Nesterov's accelerated gradient method
In the case of convex and standard Lipschitz smooth functions, it is well known that Nesterov's accelerated gradient method (NAG) achieves the optimal (11/T²) rate. In this section, show that

---

Algorithm 1: Nesterov's s Accelerated Gradient Method (NAG)
input convex and E-smooth function f. stepsize 77, initial point 20
1: Initialize = 20. Bg = 0, and Ao = 1/ 1/n-
2: for == O.... do
3: Bi+1 = B, + 1 1 + vAB, +1)
2
4: A++1 = B1+1 + 1/11
5:
Yi = zt + -At/AA (2/A411)(2 z1)
6:
F(+1 y1 (V)
7: 2++1 = 2t - 77 m7(++11 (()))
8: end for
under the E-smoothness condition with a sub- sub-quadratic L, the optimal O(1/T²) rate can be achieved by slightly modified version of NAG shown in Algorithm [ the only difference between which
and the classical NAG is that the latter directly sets A++1 Bet1 in Line 4. Formally, we have the
following theorem, whose proof is deferred to Appendix C
Theorem 4.4. Suppose f is convex and E-smooth where is sub-quadratic. Then there always exists
a constant G satisfying G 2 max
8V ((2)) - f*) + I1:0 x [VV
Denote
L = E(2G) and choose 1 S min 167.2 2T. }
The iterates generated by Algorithm satisfy
[(TT) 1 4(f(ro) fr) + || 1
T/ +4
It is easy to note that Theorem 4.4 achieves the accelerated O(1/T2) convergence rate, or cquivalently the OL1/ Vt) gradient complexity to find an e-sub-optimal point, which is optimal among gradient-based methods (Nesterov] 2003].
In order to prove Theorem 4.4 we also use induction to show the gradients along the trajectory of Algorithm| 1 are bounded by G. However, unlike gradient descent, the gradient norm is no longer a potential function or monotonically non-increasing, which makes the induction analysis more challenging. Suppose that we have shown [v.]l I G for
< t. To complete the induction, suffices to prove [ [wx)l] G. Since x; = y/-11 [(yt-) is a gradient descent step by Line 6 of Algorithm Lemma 4.1 directly shows [[>((=))] S G. In order to also bound || [ Il. we try to control ||va =zll. which the most challenging part of our proof. Since y/ 2g can be expressed as linear combination of past gradients (V (yve ( Ject. it might grow linearly with if simply apply f[.)ll I for s < f. Fortunately, Lemma 3.5 allows us to control the gradient norm with the function value. Thus if the function value is decreasing sufficiently fast, which can be shown by following the standard Lyapunov analysis NAG, we are able to obtain a good enough bound on [f(y))] for < which allows to control Appendix(C C
[y: zzll- We defer the detailed proof to
Note that Theorem 4.4 requires smaller stepsize 7 O compared to the classical (1)/)) stepsize for standard Lipschitz smooth functions. The reason is we require a small enough stepsize to get a good enough bound on ||y. xzll. However, if the function is further assumed to be f-smooth with a sub-linear f. the requirement stepsize can be relaxed to 77 = (() similar to the classical requirement. See Appendix for the details.
In the strongly convex setting, we can also prove convergence of NAG with different {Atr22 parameters when f is E-smooth with sub-quadrati f, or (p. Lu, -mmooho with p < 2. The rate can be further improved when p becomes smaller. However, since the constants G and L are different for GD and NAG, it is not clear whether the rate of NAG is faster than that of GD in the strongly convex setting. We will present the detailed result and analysis in Appendix D
Non-convex setting
In this section, we present convergence results of gradient descent (GD) and stochastic gradient descent (SGD) in the non-convex setting.
7

---

5.1 Gradient descent
Similar to the convex setting, we still want to bound the gradients along the trajectory. However, in the non-convex setting, the gradient norm is not necessarily -on-increasing. Fortunately, similar to the classical analyses, the function value is still non-increasing and thus a potential function, as formally shown in the following lemma, whose proof is deferred to Appendix E
Lemma 5.1. Suppose f is E-smooth where l is sub-quadratic. For any given F 0, let G sup u 2 0 u² < 2((2)) }} and : ((2G). For any E X satisfying f(x) - f S. F, define
xx == 7V f(z) where S 2/ L, we have x E X and f(x*) S f(x).
Then using a standard induction argument, we can show f(xx)) < f(00) for all / 2 0. According to show convergence
Corollary 3.6 it implies bounded gradients along the trajectory. Therefore, of gradient descent as in the following theorem, whose proof is deferred to Appendix
Theorem 5.2, Suppose f. is E-smooth where L is sub-quadratic.
Let G
sup {u uu I <2l(2u)- (f())) and L. == E(2G). If S 1/L, the iterates gener-
ated by satisfy [V)(()) S G for all 2 0 and
|f(==)| 2(f(zo) - f*) n/T
T KT
It is clear that Theorem 5.2 gives the classical (1//²²) gradient complexity to achieve an e-stationary point, which optimal as matches the lower bound in [Carmon al. 2017).
5.2 Stochastic gradient descent
In this part, we present the convergence result for stochastic gradient descent defined as follows.
T++1 21 779t.
where ge an estimate the gradient V V (xxe). We consider the following standard assumption on the gradient noise Ur (zxz).
Assumption 4. [c-] 0 and E,-1 ||a.1P]] S o² for some o 2 0, where E,- denotes the
expectation conditioned {ga
Under Assumption 4 we obtain the following theorem.
Theorem 5.3. Suppose I is t-smooth where is sub-quadratic. For any 0 8 < we denote
F = 8(f(x)) - f // and G := sup(u 2 0 u² < 28(2u) F} < cc. Denote L = {(2G) }
and choose S min 2L 4GVT } and 2 ne for any e > 0. Then with probability at least the iterates generated by satisfy [ S for all l T and
T [(((a)) S
As we choose 1/ = (1/vT). Theorem 5.3 gives the classical O(1/e²) gradient complexity, where we ignore non-leading terms. This rate is optimal as it matches the lower bound in [Arjevani et al. 2019]. The key to its proof is again to bound the gradients along the trajectory. However, bounding gradients in the stochastic setting is much more challenging than the deterministic setting, especially with the heavy-tailed noise in Assumption E We brietly discuss some of the challenges well as our approach below and defer the detailed proof of Theorem 5.3 to Appendix F
First, due to the existence of heavy-tailed gradient noise as considered in Assumption neither the gradient nor the function values non-increasing. The induction analyses we have used the deterministic setting hardly work. In addition, to apply Lemma 3.3 we need to control the update at each step and make sure || - x;, || 7 ||9.l| S G/T. However, 9: might be unbounded due the potentially unbounded gradient noise.

---

To overcome these challenges, we define the following random variable T.
== min(! (
[(x+1) -
-f > F} AT,
T2 == min
|leall
AT:
(S)
5
T T :: T2),
where we use A b to denote min(a, b} for any a, E E. Then at least before time т, we know that the function value and gradient noise are bounded, where the former also implies bounded gradients according to Corollary (3.6] Therefore, suffices to show the probability of T < T is small, which means with a high probability, v = T and thus gradients are always bounded before T.
Since both the gradient and noise are bounded for < T, is straightforward bound the update || - Izll. which allows us to use Lemma 3.3 and other useful properties. However, it is still [*]
random variable instead of fixed time step. Fortunately, T is stopping time with nice properties. That is because both f(*++1) and e 9t 1 (x+) only depend on {ge i... the stochastic gradients up to t. Therefore, for any fixed t. the events {T >> t only depend on {gs which show T is stopping time. Then with a careful analysis, we are still able to obtain an upper bound on [[](r>)) l O(1).
non-trivial upper bound (x²)
On the other hand, r < T means either r = 71 < T or 7 12 < T. If T=ff=m < by its definition, we know +1)++1) - f F. Roughly speaking, it also suggests -( F/2. If we choose F' such that it is much larger than the upper bound on (z f we just obtained, by Markov's s inequality, we can show the probability of T TI < T is small. In addition, by union bound and Chebyshev's 's inequality, the probability T2 < T can also be bounded by small constant. Therefore, we have shown T < T. Then the rest of the analysis is not too hard following the classical analysis.
5.3 Reconciliation with existing lower bounds
In this section, we reconcile our convergence results for constant-stepsize GD/SGD in the non-convex setting with existing lower bounds in [Zhang et al. 2019] and (Wang et al. 2022 based on which the authors claim that adaptive methods such as GD/SGD with clipping and Adam are provably faster than non-adaptive GD/SGD. This may seem to contradict that any gain in adaptive methods is at most by constant factors, as GD and SGD already achieve the optimal rates in the non-convex setting.
convergence results. In fact, we show
Zhang et al. 2019) provides both upper and lower complexity bounds for constant-stepsize GD for (To, La J-soooth functions, and shows that its complexity is ((M=-). where
M := sup II V f())l fz) S f(xo)}
is the supremum gradient norm below the level set of the initial function value. If M is very large, then the O(Me-3) complexity can be viewed as a negative result, and evidence that constant-stepsize GD can be slower than GD with gradient clipping, since in the latter case, they obtain the ((=²²) complexity without M. However, based on our Corollary [36] their M can be actually bounded by our G. which is a constant. Therefore, the gain in adaptive methods is at most by constant factors.
(Wan et al. 2022 further provides lower bound which shows non-adaptive GD may diverge for some examples. However, their counter-example does not allow the stepsize to depend on the initial sub-optimality gap. In contrast, our stepsize 7) depends on the effective smoothness constant L, which depends on the initial sub-optimality gap through G. Therefore, there is no contradiction here either. We should point out that in the practice of training neural networks, the stepsize is usually tuned after fixing the loss function and initialization, so it does depend on the problem instance and initialization.
5.4 Lower bound
For (p, Lo, L,)-ssmm -smooth functions with p < 2, it is easy to verify that the constant G in both Theorem 5.2 and Theorem [5.3 is a polynomial function of problem-dependen parameters like Lo. Lp. ) fr .a, etc. In other words, GD and SGD are provably efficient methods in the non-convex setting for p < 2. In this section, we show that the requirement of p < 2 is necessary in the non-convex setting with the lower bound for GD in the following Theorem 5.4 whose proof is deferred in Appendix G Since SGD reduces to GD when there no gradient noise, it also a lower bound for SGD.

---

Theorem 5.4. Given Lo. L2. Go. Ao > O satisfying Lzão 2 10, for any 1j 2 O. there exists (2, Lo. - smooth function f that satisfies Assumptions a and initial point 2g that satisfies [V)()))) I Go and [zx) f v Do, such that gradient descent with stepsize (3) either cannot reach a -stationary point or takes at least exp( Sop (a)o/88// 8)/6 steps to reach a -stationnary point.
Conclusion
In this paper, we generalize the standard Lipschitz smoothness as well as the (Lo, Lsmootthhsssss iZhag al. 2020] conditions to the E-smoothness condition, and develop new approach for analyzing the convergence under this condition. The approach uses different techniques for several methods and settings bound the gradient along the optimization trajectory, which allows us to obtain stronger results for both convex and non-convex problems. We obtain the classical rates for GD/SGD/NAG methods in the convex and/or non-convex setting. Our results challenge the folklore belief on the necessity of adaptive methods for generalized smooth functions.
There are several interesting future directions following this work. First, the Ł-smoothness can perhaps be further generalized by allowing to also depend on potential functions in each setting, besides the gradient norm. addition, would also be interesting to see if the techniques of bounding gradients along the trajectory that we have developed in this and the concurrent work [Li et al. 22233 can be further generalized to other methods and problems and to see whether more efficient algorithms can be obtained. Finally, although we justified the necessity of the requirement of f-smoothness with sub-que rub--uudratic É in the non-convex setting, it is not clear whether it is also necessary for NAG in the convex setting, another interesting open problem.
Acknowledgments
This work supported, in part, by the MIT-IBM Watson AI Lab and ONR Grants 100014-20-1-2399 and N00011-23-1-2299 We also acknowledge support from DOE under grant DE-SC0022199, and NSF through awards DMS-2031883, 1953195, and RMS-2022448 (TRIPODS program).
References
Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake E. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199:165 214. 2019.
Stephen Boyd and Lieven Vandenberghe. Convex optimization, Cambridge university press, 2004.
Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, pages 1-50, 2017.
Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smoolf nonconvex optimization is as efficient as smooth nonconvex optimization. arXiv preprint arXiv:2303.0285. 2023.
Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to unbounded smoothness of generalized signsgd. Advances in Neural Information Processing Systems, 35:9955-9964 2022.
Alexandre d' Aspremont, Damien Scieur, and Adrien Taylor. Acceleration methods. Foundations and Trends@ Optimization, 5(1-2):1245, 2021. ISSN 2167-3888. doi: 10.1561/2400000036. URL http: / /x doi. org/ 10.
Matthew Faw, Litu Rout, Constantine Caramanis, and Sanjay Shakkottai. Beyond uniform smoothness: A stopped analysis of adaptive sgd. ArXiv, abs/2302.06670,, 2023.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal Optimization, 23(4):2341-234 2013.
10

---

Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. abs/1412.6980, 2014.
CoRR,
Haochuan Li, Ali Jadbabaie, and Alexander Rakhlin. Convergence adam under relaxed assumptions. arXiv preprint arXiv:2304. / 13972, 2023.
Arkadij Semenović Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. Wilee-nnterscience, 1983.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer
Science & Business Media, 2003.
Jiang Qian, Yuren Wu, Bojin Zhuang, Shaojun Wang, and Jing Xiao. Understanding gradient clipping in incremental gradient methods. In International Conference on Artificial Intelligence and Statistics, 2021.
Amirhossein Reisizadeh, Haochuan Li, Subhro Das, and Ali Jadbabaie. Variance-reduced clipping for non-convex optimization. ArXiv, abs/2303.00883 2023.
Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Zhi-Ming Ma, Tie- Yan Liu, and Wei Chen. Provable adaptivity adam. arXiv preprint arXiv:2208. 2,0900208..0900,, 2022.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. ArXiv, abs/2010.02519, 2020.
Jingzhao Zhang. Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. arXiv preprint arXiv: 1905. 1881, 2019.
Shen- Yi Zhao, Yin-Peng Xie, and Wu-Jun Li. On the convergence and improvement of stochastic normalized gradient descent. Science China Information Sciences, 64, 2021.

---

A Proofs related to generalized smoothness
In this section, we provide the proofs of propositions and lemmas related to the generalized
smoothness condition in Definition | or 2
First, in Appendix AA.1 we justify the examples we
discussed in Section 3 Next, we provide the detailed proof of Proposition [3.2 in Appendix A.2
Finally, we provide the proofs of the useful properties of generalized smoothness in Appendix A.3
including Lemma 3.3 Lemma 3.5 and Corollary 3.6 stated in Section 3.1.2
A.1 Justification of examples in Section 3
In this section, we justify the univariate examples of (p, Lo. -smothh functions listed in Table 2 and also provide the proof of Propositions 3.7
First, it is well-known that all quadratic functions have bounded Hessian and are Lipschitz smooth, corresponding to p O. Next, (Zhang al. 2019 Lemma 2] shows that any univariate polynomial is (Lo. L1 >-smoohh, corresponding to p Then, regarding the exponential function f(x) = a where 1, have f'(x)) log(a)a* and (')(x) log(a)Ra²
['(x), which implies f is (1, log(() logoo))ssmooth Similarly, by standard calculations, it is straight forward to verify that logarithmic functions and x², + 1 are also (p, Lo. Lp) -mooth with p 2 and hー respectively,
log(a) (rg((a)((x)
So far we have justified all the examples in Table 2 except double exponential functions (b and rational functions, which will be justified rigorously by the two propositions below.
First, for double exponential functions in the form of [(x) = (b") where a, b > 1, we have the following proposition, which shows is (p, Lo, Lp)-smooth for any p 1.
Proposition A.1. For any > 1, the double exponential function f(x) = (b"), where a, b > 1, is (p, La, I.p) -smoohh for some Lo, T.p 0. However, it is not necessarily (Io, L1) In)-smooth for any Lo, L1 2
Proof of Proposition A.1
By standard calculations, we can obtain
f((x) = log(a) log(b) ba (b") f"(x) = (log((a))))))) +1) ((x).
(6)
Note that if p>
lim ['(x))* lim [f"(x)]
15(x))
(ogb))) (0-01((0-11 (pp-1)v
lim 8-+00
00;
++++ log())(lg(a)b++]
log(b)(log(a))) + +1
where the first equality is a direct calculation based on (6; the second equality uses change of variable y 12;; and the last equality is because exponential functions grow faster than affine functions. Therefore, for any I,p > 0, there exists To E I such that [f"(x) < L, [f'))) if To. Next, note that -im fxxx) O. Then for any λι > there exists I1 IR such that [f"(z)] < λ if x < I1, Also, since f" is continuous, by Weierstrass's Theorem, we have [f"()) A i S x Fo for some A2 0. Then denoting Lp max(A1, A2), we know is (p, Lu. Lp) smooth.
Next, to show is not necessarily (Lu, -moothhhhh,, consider the specific double exponential function f(x) e(e"), Then have
f((x) = ce f'(x) = (e" + (1)
For any x 2 max flog(Lo Lo + lo, + 1)}, we can show that
|F"()) (L1 (x) In In (f)())),
which shows f is not (Lo, L,) smooth for any Lo. L 2 0.
In the next proposition, we show that any univariate rational function f(x) = P(x)/Q(z), where P and Q are two polynomials, is (p, Lo, -ym-shooth with p 1.5.
Proposition A.2. The rational function f(x) P(x)/(xx) where P and Q are two polynomiuls, (1.5, Lo. (r.s)-smooth for some Lo, L 2 0. However, is not necessarily (p, Lop, I.p) -mmooth for any p 1.5 and Lo, Lp 2 0.
12

---

Proof of Proposition A.2 Let f(x) = ((x)/Q(z) where P and Q are two polynomials. Then the partial fractional decomposition of f(x) is given by
m
Air
12
B Cir (x
f(x) - =
x az)""
+ b + q))
where ==(::) is a polynomial, Air, Bar, Cir, Ui bj, C2 all real constants satisfying 83 - 4c; 0 for each 1 < S n which implies x² + bb, + > 0 for all x E R. Assume j; 2 1 and Ai, * 0 without loss of generality. Then know f has only finite singular points {si)ssssm and has continuous first and second order derivatives at all other points. To simplify notation, denote
Air
B + Cir
(x) =
(xr(
(I (r-aj) a.)"
(x² + 6 + +c))"
Then have ((x) w(x)) E Σ Per (x) Ex= Σ Uir (1) We know that
r+2 r+1 S 1.5
for any 2 Then we can show that
[f())) [x)(
Mig (x))
1.5
lim
lim
Pij (z)
J++1
where the first equality is because one can easily verify that the first and second order derivatives
of Pij; dominate those of other terms when x goes to as and the second equality by standard
calculations noting that je22
J+1 < 1.5. Note that 7 implies that, for any Lp > js + 1, there exists
5, > 0 such that
[f"())] & Lp (f
[x- a,l < 8,.
(8)
|( 1 (x" co, which implies there exists xp > 0 such that
Similarly, one show limz-100
1s"(x) S (p)) if | > xo.
Define
B (-=
and |r a. 8,, Vij.
We know B is compact set and therefore the continuous function f" bounded within B, i.c. there exists some constant Lo > 0 such that
If"(z)) S Lo, if
(10)
Combining and 10 we have shown
[f"()) S Lo + Lp (1())) (x)
Var E dom(f),
which completes the proof of the first part.
For the second part, consider the ration function f(x) 1/x. Then know that f'(x) -1/2²
and f (xx( 2/23. Note that for any p 1.5 and 0 S min + 1) 1/3 (Lp + 1)-11((- (312))
we have
1 1
(f"())
zz-2p (z) Lo + L, (=))
which shows f is not (p, Lu, Lp) smooth for any < 1.5 and Ly, 2.
Finally, we complete this section with the proof of Proposition 3.7 which shows self-concordant functions are (2, Lo, smoooh for some Lo, L, 2 0.
Proof of Proposition 3.7 Let h R - R be self-concordant function. We have h²)x)) s 2h" (x)3/2 Then, for (a. we obtain
A² [' 1/2 (x)
Integrating both sides from zo for 2o. E E (a, b). have
h" hn(y) h" hxoz) 1/2 < h'(y) - hl(xo).
Therefore,
1²(y) (v) S
11 (mo) + 11' (v))² < 21 (ær) 1/2 - 1/ (zo))² + 2y)
Since 1²(r) > 0, we have [z)( 11" (u). Therefore, the above inequality shows that h is
(2, Lo, L2) -mooth with Lo 2(h (20))2 h' ) and L2 2.
13

---

A.2 Proof of Proposition 3.2
In order to prove Proposition 3.2 we need the following several lemmas. First, the lemma below partially generalizes Grönwall's s inequality.
Lemma A.3. Let o: [a, bj + [0, xc) and 3 [0, (0) + (0, x0) be two continuous functions. Suppose
at(t) S B(a(t)) almost everywhere over (a, Denote function o(u) == 200 du. We have for all t E [a, bj.
B(u)
p(a(t)) S ((a(a)) - a 1a+b t.
Proof of Lemma A.3
First, by definition, know that d is increasing since o' 3 > 0. Let function y [a, R the solution of the following differential equation
(1) = (()))) E (a, r(a) a(a)-
(11)
Then we have
dń()(1)) = dr(11)
B(>(t)) = dt.
Integrating both sides, noting that 7()) = a(a) by (TT), we obtain
((7(1)) - o(a(a)) = a. Then it suffices to show o(a(t)) s ((+(1), At E [a, bj. Note that the following inequality holds
almost everywhere.
( ((T(()())))) ='(o)))) (() (()))) a'(1) 7((1
B(a(t)) B(x(t)) 20,
where the inequality because a (t) < ((a(t)) by the assumption this lemma and 7'()) (() by (II). Since o(a(a)) - <(<(a)) = O, we know for all t E [a. ((a(t)) I (t),,),, which
completes the proof.
With Lemma A.3 one can bound the gradient norm within small enough neighborhood of a given point as in the following lemma.
Lemma A.4. If the objective function f is E-mooohh, for any two points y E Rd such that the closed line segment between and y is contained in X, if ly Ill S x[Vl[a]] for any a >> we have
|| < [V](())]
Proof of Lemma A.4 Denote =(t) = (1 f)x by for < S Then we know =(t) E X for all
A I < 1 by the assumption made in this lemma. Then we can also define a(l) == [[([((()) for
IA
t 1. Note that for any 0 S t s S 1, by triangle inequality,
ass) - at)) [V)(s)))) - ff((()))
(12)
We know that (1)) [=)((( is differentiable almost everywhere since f is second order differentiable almost everywhere (Here we assume (t)) * 0 for 0 < 1. < without loss of generality. Otherwise, one define f. s0 < 1 1 a(t) 0} and consider the interval [lm, 1] instead). Then the following equality holds almost everywhere
a' (t) = lim (ss) - a(t)
[Vf(2(s)) - vf(((t)) lim vf(c(s)) v)(((t))
< lim
s-t
5-t
=||v2 x) || < (=f((())]] Iy xll s E(a(t)) 11y æl1.
where the first inequality is due ((u) lly xII and Φ(u)= := f" गंप) dv. By Lemma A.3 we know that
and the last inequality is by Definition 1
Let 3(u)
* ( ((((1)) s s(u(0)) +1 o (I fx))) +
14

---

Denote v(() Jo So [., =d()= 1(1)- 2||. We have
+ ((V < (1] [()))) 1ll -
+ ( +a)
|V
/V
du
do
{(+)
|V(001
{(v)
Since &b is increasing, we have [V & [f +a.
With Lemma A.4 we are ready to prove Proposition 3.2
Proof of Proposition 3.2
We prove the two directions in this proposition separately.
1. An (r, -)-smooth function is E-smooth.
For each fixed E X where V fzx(x) exists and any unit-norm vector w, by Definition 2 that for any S r((ll.
we know
VV + tw) - f((ii) S <(IVV((()
Then we know that
f())wl
lim (V tw) {((>)
140
lim fI (x= + tw) Vf(+)II S ((IV)
140
which implies [> f())l for any point if V2 exists.
Then it suffices to show that f(x( exists almost everywhere. Note that for each x E X. Definition 2 states that the gradient function is f())l) Lipschitz within the ball B(xr, (<)]V( Then by Rademacher's Theorem, f is twice differentiable almost everywhere within this ball. Then we can show it is also twice differentiable almost everywhere within the entire domain X' as long as we can cover X' with countably many such balls. Define S, {i E X n < [V](()] < n nn+1) for integer n 2 O. We have = Un20Sn. One can easily find an internal covering of S,, with balls of size r(n + 1 i.e., there exist (Im,:)/20 where In, E Sn, such that Sn C (5 r(n + 1)) S UizoB(an,. r(] ((),f((...))))) Therefore we have X' C Un,520B(m r(] ( I)) which
completes the proof.
2. An E-smooth function satisfying Assumption is (r, m)-moooth where m(u) = f(u + a) and r(u) :- a/m(u) for any O.
For any y E RRd satisfying ly x:I| S <<IIV](<)II) 8 +o] denote =() = (1 l)a ty
for 0 < 1. We first show y X by contradiction. Suppose y É X, let us define t, := inf <
t t 1 2t) & X) and = (tp).. Then we know 2/ is a boundary point of X. Since f is closed
function with an open domain, we have
lim f(2(t)) co. rtt
(13)
the other hand, by the definition of ln we know 2(1) E X' for every S 1. < lp. Then by Lemma A.4 for all 0 S < ln. we have [VS(((())] [x)( + a. Therefore for all 0 < t < lb.
f(x(1)) Sf(x)+ / (V](=(+)), y - 2) ds
<ʃ(x) (I[V/(=)I + a) x|1|
<X0,
'We can find internal covering in the following way. We first cover S., with countably many hyper-cubes of length r(n + 1)/vd, which is obviously doable. Then for each hyper-cube that intersects with S.. we pick one point from the intersection. Then the ball centered at the picked point with radius r(n + 1) covers this hyper-cube. Therefore, the union of all such balls cover S...
15

---

which contradicts 13). Therefore we have shown y E X. Since is chosen arbitrarily with the ball (()))((((( we have ((x, ((Ilf(())I) X. Then for any 21, 21,42 E B(x, ( we
denote (()) == (x + (1 - 1).2. Then we know w(t) E B(x, r(1 (f()))) for all 0 S / S and
can obtain
% v2 f(w(tt) (x1 - (62))))0 dt
[Vf(z1) ( fx(2))
||| - 221l J. [[IV](()]] + dt
=m ||1 x211,
where the last inequality is due to Lemma
A.4
A.3 Proofs of lemmas implied by generalized smoothness
In this part, we provide the proofs of the useful properties stated in Section including Lemma 3.3 Lemma B.5 and Corollary 3.6
Proof of Lemma 3.3
First, note that since & non-decreasing and r non-increasing, we have
(()))())))) < G = and r(G) S rr[lV// [z))))) Then by Definition 2 we directly have that B(x, r(G)) S (xx, (II S X, and that for any I1, 22 E ( (())), we have
[V - (x2))) < A (x))l) || - x2 - L |0 x2l1-
Next, for the second inequality in 2 define =(1) == (1 - f)x2 + tr for 0 S l S 1. We know z(1) ((x, r()). Note that have shown
VV(((()) v ff (x2)) s L ( x21l = 1 | - x211
(14)
Then we have
f(x1) - f(x2) = (vf(2(t), x1 -1)))) dt
1.' (Vf(x2), x2)) (Vf(=(t)) Vf(x2), x2) dt
<VV(22)). 21 x2) + L | x2l1 //' t
<Vf(xz) 22) + 2
|| x2l
where the inequality due to 14
Proof of Lemma
3.5
If f-smooth, by Proposition
3.2 f is also (r. m) -moothh where m(u)
((2u) and ruu) u/ ((2)). Then by Lemma 3.3 where we choose G [VV(()]]. we have that
|
C X, and that for any IT, 22 E
B (r. 2(2
[
((=II)) ) we have
[(2 [(]
f(x1) S Sxx2) (VI(2)),
#1
x2)
| - well
2
Choosing #2 x and 01 x.
[|)| easy to verify that æ1, 82 E (z,
vf(2)
((()
Therefore, we have
Vf(z)
f S x
$ f())
4(2
20(2
which completes the proof.
16

---

Proof of Corollary 3.6 We first show G < 00. Note that since is sub-quadratic, we know -im 2f(2u)/ u²" O. Therefore, for any F 0, there exists some M 0 such that 20(2u)/ u² < 1/F for every > M. In other words, for any satisfying u² S 2f(2)) F, we must have u S M. Therefore, by definition of G. we have E M oo if F > I we trivially get G = 0 < co. Also, since the set (u 2 0 u² S 2f())) F} is closed and bounded, we
know its supremum G is in this set and it is also straightforward to show G 21(2G) F.
Next, by Lemma 3.5 we know
V f=)]l ((2 (f(x) 5*) (=2 Then based the definition of G, we have |[](()) s G.
B Analysis of GD for convex functions
In this section, we provide the detailed convergence analysis of gradient descent in the convex setting, including the proofs of Lemma 4.1 and Theorem 4.2 for which the following lemma will be helpful. Lemma B.1 (Co-coercivity). If f is convex and (r, E-smoothh, for any x X and y B(x, ((z))(())(()))))) we have X and
1 T. (V/(x) x 2
-
where L = (()))
Proof of Lemma B.I] Define the Bregman divergences 6z(w) == f(w) - (V w) and o, (w) =
f(w) fV) w). which are both convex functions. Since (w) = Vf(w) ff(x),
have V (z)
0 which implies min, (x(w) = (x)x) as dn is convex. Similarly we have
min,. (w)) = (v).
Denote r2 == f()]V) Since o (r, f)-smooth, we know its gradient V is I.-Lipschitz locally in B(x, T.). Since (w)(w) ff(w)= f(x) is a constant, we know V is also L-Lipschitz locally in B(x, rg). Then similar to the proof of Lemma 3.3 one can easily show that for any T1,22 B(x, Tz), we have
L || x211?
(x(r)) S (x2) + (V).(22). x2) + 2
(15)
Note that for any y E B(x, (f in the lemma statement,
1 (o)
lyy -|| || + VV(() - vf(2)) = x|| S ras
where the first inequality uses triangle inequality and (yr vf(y) fx)); and the second inequality uses Definition 2 It implies that y - Von (v) E B(x, r.). Then we can obtain
dx (x) min (z S oz (y Vel(w) s (x(1)
1
2L
where the last inequality uses 15 where we choose definition of dr, the above inequality is equivalent
1, (v) and x2 y. By the
1
2L VVly)
f()) f(v) - - (Vf(x), v).
Similar argument can be made for (-)()) to obtain
1
v f( < f(x) - f(v) (VI(). x))
2L
Summing up the two inequalities, obtain the desired result.
With Lemma B.I we prove Lemma follows.
17

---

Proof of Lemma 4.1 Let L = EG)). We first verify that x+= B(zz Note that
| =1 |vV S 5
where we choose 17 S (2G) Thus by Lemma B.1 we have
|| I|² = [V](2)] 2(Vf(2**)
Vf(=t) vf(=)||
[V 2 (V/(x=))
| [
"
< [Vf(2)]] + 11
nL -Vf(==t)V[(il]]
2
- [Vf(')]''
where the first inequality uses Lemma
B.1 and the last inequality chooses s 2/
With Lemma 4.1
we are ready to prove both Theorem 4.2 and Theorem
4.3
Proof of Theorem 4.2
Denote := [ Then we trivially have ( < G. Lemma 4.1
states that if [++) II < G for any t 2 0, then we also have [ < [V)(() < G. By
induction, we can show that [xx)]] I| S G for all 2 O. Then the of the proof basically follows the standard textbook analysis. We still provide the detailed proof below for completeness.
Note that |
[ $ n/ r(G), where choose 1) S r(G)/(2G). Thus
can apply Lemma 3.3 to obtain
0 f(z(1) f(x)) - (v.())), 24+1 - -x1) - || - xell
1
2 f(z41) f(x)) (V.((z)), -x1)-
| xz
(16)
27
where the last inequality chooses 1 L/L. Meanwhile, by convexity between 24 and x², we have
0 f(:) + (Vf(Ie), - xz).
(17)
Note that + 1)x 16
gives
> (xx) - f (Vf(xt), xz))
+ (1 +11+)) ((02+))) f(x)) - (VS(I)), Je41 - vz) I - 2zell
2n
Then reorganizing the terms of the above inequality, noting that
|| x²1 1| 2²1 || xx.l1 + 2(x T4, xx*)
|| -zell 2ny ff x31
we can obtain
1
(1+ (1+1)(((++1)) + 21
||,2 ==11== (((((:) - - (*)+ 2n ||,r, 2²112
I x*1 is non-increasing potential function, The above inequality implies ((f(xx) - 1*) 2n
which directly implies the desired result.
Proof of Theorem 4.3 Since strongly convex functions are also convex, by the same argument as in the proof of Theorem 4.2 have f(x)ll G == [ for all f > 0. Moreover, (16) still holds. For p-strooggyy-oonvex function, we can obtain a tighter version of (17) as follows.
0 2 f(x)) f + (z)) x" xx) + 2 || 22 11
(18)
18

---

Let A 0 and A4+1 (1 A.)(L1 -p) mp) for all 2 0. Combining (6] and 18 we have
0 02 (A++1 - A.)(((z)) - + (V]()),, mx))
+ Ac+1 (((1-11)-f(a00) -( (V) xi))
1 2n
1| mell?)
Then reorganizing the terms of the above inequality, noting that
| - x²1 a| z²1 11 = || xzel² 2(2 I2, xx")
|| -rell² rell2+ 2n f 1z)
we can obtain
A (f1((((t))) - muAA++1 |100+1 =x11| A((((x)) - f²) + queA
|| - ==111
21)
27
The above inequality means (f(((z)) - f²) + Itnudi || x² 11 is non-increasing potential
function. Thus by telescoping we have
f(IT) - f s 111 - -1/)²
2(1 - (1 m1)²") 11:0 =
C Analysis of NAG for convex functions
In this section, we provide the detailed analysis of Nesterov's accelerated gradient method in the convex setting. As we discussed in Section 4.2, the stepsize size choice in Theorem i.4]s smaller than the classical one. Therefore, we provide more fine-grained version of the theorem, which allows the stepsize to depend on the degree of f.
Theorem C.1. Suppose is convex and E-smooth. For (0,2), if E(u) o(u)), ie. lim (u))uu = 0, then there must exist a constant G such that for I, = ((2G), we have
2 max {
8 max Va- 1/2 1/,,-1111,,1,11/,, 111111 f+) + 1| - x² (V))11 (19)
Choose S min 1811-2111 2 Then the iterates of Algoritthm satisfy
[(TT) 5 4(f(2o - f³) + 1100 x*1 T/T2 +
Note that when a = 2, i.e., l is sub-quadratic, Theorem reduces to Theorem 4.4 i.e., e sub-linear, the above theorem chooses 1) S 16Z as in the classical textbook analysis up to numerical constant factor.
which chooses
17 minf = şτ J. When
Throughout this section, will assume is convex and f-smooth, and consider the parameter choices in Theorem C.I unless explicitly stated. Note that since f is E-smooth, it is also m) (r,m))smaan smooth with muu) E(u + G)) and r(u) = πu+oo by Proposition 3.2 Note that m(G) = ((2G) T. and
r(G) = G/L. Then the stepsize satisfies S 1/L))) S min m[G]
2 n()
2G }.
Before proving Theorem C.I we first present several additional useful lemmas. To start with, we provide two lemmas regarding the weights (Ar)220 and (B.120 used in Algorithm below states that B, = ((2).
[ The lemma
Lemma C.2. The weights (Brrzoo Algorithml satisfy 1 S B. S 12 for
Proof of Lemma C.2 We prove this lemma by induction. First note that the inequality obviously holds for Bo = O. Suppose its holds up to t. Then we have
B41 B, +
1 (1+ 4B,
1 e
1
1
V
(t 1++1) 1). +
+1
2
4
4
19

---

Similarly, we have
Br-1 Br (1+ 4B, +))
S x +
Lemma C.2
implies the following useful lemma.
Lemma C.3. The weights {At)120 in Algorithm satisff that
A A4+1 A
(1
Σ
VAsti(Ast) A, S 4.
First, note that it is easy verify that A,+1 A, Bst1 Bg 2 which implies each term in the LHS of the above inequality is non-negative. Then we have
Proof of Lemma C.3
A:
V Au41 (Ast1 Aa-11)
A441 At
1-1
$
(At+1 At)
Σ
(As+1 A, 1)
(Ae 2 Ast1)
A,
[-1
(Be+1 - B₂)
Σ
(Be+1 - Bg 11
(A, = Bg +
A4IVA,
==0
1-1
(1 v 4BB,
Σ
-1 -1 -1
v /B. 11)
(by definition of B.)
A 2
==0
(++1) 8²
8
(by A, 2 B, and Lemma C.2
(t + 1)2t
< 4.
The following lemma summarizes the results the classical potential function analysis of NAG in (d d'Aspremont et al. 2021]. In order to not deal with the generalized smoothness condition for now, we directly assume the incquality (20) holds the lemma, which will be proved later under the generalized smoothness condition.
Lemma C.4. For any 2 0, the following inequality holds,
1 f(x) + (VI(w)), Fe+1 110 || vil1 2 f(x+1)),
(20)
2n
then we can obtain
1 2m
A (f - f*) +
||+1 20122= A(((()) f*)
1
1=1
(21)
2m
Proof of Lemma C.4 These derivations below can be found in d A'spremont et al. present them here for completeness.
2021
We
First, since f is convex, the convexity between x" and ye gives
f 2 fvx) + (VI())), - ye).
Similarly the convexity between I' and gives
f(x)) 2 f(:) + (V vc)-
20

---

Combining the above two inequalities as well as 20
assumed in this lemma, we have
M (At+1 ())(f(()) f + (Vf x= ye))
+ -
- -y))
+ Ac+1 (((((1)- - f(ve)
- -v0)
|| - vell))
(22)
2n
Furthermore, note that
1
[141 - x² -x112 -112 10x==x11'" x²(1²)
21
- (12011 - z=11² + +2(2++1 =z,, -x0)
21j
(1²(At+1 -,,² [ 217(A+11 A) -x"))
21
! (Ar+1 - A.)3 / 2 - A 2 -x)).
(23)
2
Meanwhile, we have
Ar-17e+1 = Act13/+ A (((ee)) = A4+10t + (Ac+1 - Az) xx) -A (Vv)).
Thus we have
(At+1 Ao)a = A4t13441 - ALTa nA++1 Vf(w)).
Plugging back in
23
we obtain
[|e41 - =x1112 117--12a -112 11=1-1"1133
x²((²)
2n
7 (Ar+1 A.)² f +(A+1 A,)V)(()),'))
2
(-Ac+13e+1 Act. -1A4)V/(()) VS(W)))
Thus
(A+41
(ArT ACt13O+1 vf(1)))
2n (1 - x=1 ||ا - =01)²) + 7(A++1 (Att1 -A.))) // f20))1
So reorganize
(2 to obtain
2 A4t - f*) -((()()) f*)
(A1+1 A.)(V x²) + (ArT) A4113141 (4411)),VV(u))
2m Act1 ||02+11 - 22112
A (f(++11) - -³) (x:) 1r)
- x1112 112441-1*112
-1 x= (p) + "
2m
2
Then complete the proof noting that it is easy verify
A411 - (At+1 - 2,)2= B41 + (B441 B₂)² 2 0.
In the next lemma, show that if [ < G, then the condition 20 assumed in Lemma C.4 is satisfied at time t. Lemma C.5. For any 2 0, V [w))) S G, then we have [ \l s G. and furthermore,
f(y)) + (V)())) Æ(+1 Mt)
||
-x > f((+1).
2n
21

---

Proof of Lemma C.5 As disccued below Theorem
C.1 the stepsize satisfies - 1/(2L) -
min m(G))
2
r(G)
2G J. Therefore can apply Lemma
4.1 show [ & f
G. For apply Lemma 3.3 to
the second part, note that | vell 1) V f (1))
G
I r(G),
2T.
show
f(x++1) S ((m) + (V)())), Tz41 - y1) + |z+1 - yell
2
1
f()) (v)) xx+1
y10 + 2n
| Mel1
With Lemma C.4 and Lemma C.5 we can show that [[V S for all 2 O, as the lemma below.
Lemma C.6. For all t 2 0. V (v)) < G.
Proof of Lemma C.6 We will prove this lemma by induction. First, by Lemma 3.5
3.5
and and the choice of
G, it is easy to verify that V [(r))] S G. Then for any fixed 2 0, suppose that || [IV[(a, [xx,)) S G
for all s Then by Lemma C.4 and Lemma C.5 and that for all s < t,
we know that [[=)(=)) - for all 0 S s s
1
1 2n
As+1 (f(I++1) f) + ||,211 - x²12 s Ao(((E,) f*) +
2 x²12
(24)
2n
By telescoping 24 we have for all 0 S 8 t,
f(x+11) f n
((f(ro) f*) 1|:0 x²11 121
(25)
For S s S f, since |V*]( S G, then Lemma 3.5 implies
[V s 21( 1*).
(26)
Note that by Algorithm
I we have
Ap-1
21 Ft
(2t-1 Tt-1) - ((A, A
A
Thus we can obtain
t-1
2 F2
Σ
n A A,- 1)V
A,
Therefore
A
1 f-1
- (1
Σ
A - As 1)Vf(v)).
Ar+1
A
Thus have
A
t-1
11 - xell S (1
Ar41 )
} A (As+1 - A. - -) [))() =:
A.
Since [v=)()))] < G and |00+1 - yell = V & (G) for < t, by Lemma 3.3 we have
A
1-1
I (1
A (A.+1 - A, ( + /
(v.)))
A
A
#=1
A
1
$ SILI + (1
Σ
A - A. - 1) (2
A
A,
sml
22

---

Thus
1
A
<I < 1 - 11 (1
A - A, 11)
A++1
A ==1
A
(1
(Ast1A - -, 21
(by (26)
1- LL
A++1
A
A
2L 1 ((f(z)) fo) + 1| x+1; 2²1]²)
n (Ast1 -Ag - - As+1
1 1
A4+1
A
(by 25
2
A
v AAs1((As4) A. 1) (f(zo) - + 11:0 x0
1 7L
As+1
A
8/
1 7L /((((zz) f)) + |120 z+11
(by Lemma C.3
$ 2L3/2-1/a L 1/2 1122-1/o 2L S rG)).
(by the choices of 1) and G)
Since
[V[((=)) < G and we just showed || Vi S r()), by Lemma 3.3 we have
[V = [x()))] + 11 xz1|
2L
G
$ 1 14:
((((r)) - p²) + 1| x011+ L-
(by 26 and 25
2T.
1 + S.
$ 6
(by A, 2 1/1 and choice of G)
Then we complete the induction as well as the proof.
With the three lemmas above, is straight forward to prove Theorem C.T
Proof of Theorem C.I Combining Lemmas C.4
C.5
and
C.6
we know the following inequality
holds for 2
A (f(e1)))))) f*) + |z
- x x²1² A.(((x)) - f*) + 2n)
1| x= =1
21
Then by telescoping, we directly complete the proof.
D Analysis of NAG for strongly convex functions
In this section, we provide the convergence analysis of the modified version of Nesterov's 's accelerated gradient method for y-strongly-come functions defined in Algorithm
The convergence results is formally presented in the following theorem.
Theorem D.I. Suppose f is j-strongly-come and f-smooth. For E 20, if(()) olu iee. lim ((u) uu 0, then there must exist a constant G such that for L. = E(2G), we have
G z max Va--1/ ,11y (((((=)) - f*) + u 1|=00 - x= /13)/ min(u,1) 1}.
(27)
If we choose
< min
(28)
1441,32/00 2/c log
14/1
2L
23

---

Algorithm NAG for p-strongly-convex functions
input j-stronggyy-oonvxx and e-smooth function f. stepsize 7, initial point 20
1: Initialize = Po. Bg = 0, and Ag = 1/(j)).
2: for i O.... do
3: Bi+1 2B.+1+ IB, +
41-MA)
4: A1+1 B1+1 +
Te = (A++1 Ae m1+m
Ac --n and 6, = As
5:
6:
yt St + (1 lic)
7: Ft+1 Yt fV.)(())
9: end for m)dd)) 2z + mpddye n², V f(())
8: 2++1
The iterates generated by Algorithm S satisfy
f(XT) f s (1 /(n)) T -1 (1(0 (3) + 10 x²11
Ti + (1 (1-v111)²--
The above theorem gives gradient complexity of O (v log(1/e)) Note that Theorem 4.2 shows
the complexity of GD is O TH log(1/c)) It seems NAG gives better rate at first glance. However, note that the choices of G, L, 17 in these two theorems are different, is less clear whether NAG accelerates the optimization in this setting. Below, informally show that, if (()) = 5o))=o((oe o(Vu), the rate we obtain for NAG is faster than that for GD.
For simplicity, we informally assume f(u) = xf with p E (0, 1). Let Go |/ ((x))) Then for GD, by Theorem 4.2 we have 7gap x p/ x u/G6- For NAG, since is sub-linear we can choose 1 in the theorem statement. Since f is ju-strongly-conee
by standard results, n. Go. Thus the requirement G (27) can
can show that f(xo) - f I G. and ||o0 - x=Il I
be simplified as G 2 (GG) - Go/H, which is satisfied if choosing G (Go/k) Then also have Unag πO] (u/Go)p/(LLP)) Thus Vhnagti X (u/G))//(2-22) This means whenever 1/(2 2p) < i.e. 0 < p < 1/2, we have /haggl Z Agd/s, which implies the rate we obtain for NAG is faster than that for GD.
In what follows, we will provide the proof Theorem D.I We will always use the parameter choices in the theorem throughout this section.
D.1 Useful lemmas
In this part, we provide several useful lemmas for proving Theorem D.I To start with, the following two lemmas provide two useful inequalities.
Lemma D.2. For any 0 1, have log(1 + u) 2 j.
Lemma D.3. For all 0 < p Σ 1 and 2 O, we have
log(e + 1 1)(0(1++ (v)) +1).
t < vp
Proof of Lemma D.3 Let
1 10(1 + vD)²+ + +1) -
((1) = vp
log(e +
p
24

---

It is obvious that f(t) 2 0 fort v
2 vp
log(e + )) Fort 2 log(e + 1),, we have
vp
1 ) log(1 + vP)(1 + vD) -1 (t) 2/D log(( +
p
2 p(1 + vD) -1
(by Lemma D.2
pexp(tlog(( vP)) -
2 pexp(LvD/2)-1 -1
(by Lemma D.2
2 ple + 1/p) - 2 0.
(since 1 >
2 vp
log(e + )
Thus f is non-decreasing and
f()) 2 1( 2 log(e + ) 2 0. vp
2
In the next four lemmas, we provide several useful inequalities regarding the weights (Ac and {Br)e20 used in Algorithm 2
Lemma D.4. For all s S t, we have
B1I B.
B,+1 B,
$ 1, 1+ mpBB+1
But1
which implies T2 8, S 1.
Proof of Lemma
D.4 By Algorithm
2 is easy verify
(Bs+1 B.)² B.+1 npBB+1).
This implies
B. BB+1 v BBt1 + nuBB+1).
Thus
B: =
1
B₁
B mh
21
B
B
B
where in the inequality, we use the fact that B, is non-decreasing with 8. Therefore
B B.
B.+1 - B.
B B,
B.t1 - B.
1.
B1+1
1 MuBB+1
Bot1
1 nMBB+1
Thus we have
(Ar+1 A1)(1 + muA)))
As+1 As
Te 8,
A4t1 + A, - Au
1 muAst1
A411 A,
A,+1 Ag
(by Ac+1 2 As)
A++1
1 1744411
B141 B.
Ba+1 - B.
(by Ast1 - A, = BB+1 - Ba)
A+t1
1 + A11A411
Bri B.
Bs+1 Bs < 1.
<
(by Ast1 2 Bs41)
B+4
+ +tnB+t+1
Lemma D.5. 1f0 < np < 1, then for any t 2 1, we have
B,
3B,
B S
1 VI
1- mp
Thus
1
1-1 (1
(1 v mnl
25

---

Proof of Lemma D.5 For t 2 I, we have B, 2 1 thus
2B: + 1 + 4B, + B +1
2Br +
3B,
Bi+1
V
2(1 (11-)4) m1))
1 mp
1 pd
On the other hand, we have
2Bg 1 /4B, + 4npBi +1
B41
2(1 - (1/4)))
2B: + /(2B./Tju)
2(1 n/1)
B,
Thus
t-1
t-
B, 2
B z
2 (1 + vIJ1)
mp
1 Tp
Lemma D.6. For 0 < mp < 1 and 2 we have
Σ
BB B, S (1 - 1241 S 3B,
0=0
Proof of Lemma D.6
2B: 1 + V /B, + 4np
B
2(1 - 71)
VB,
2 B₁ +
mp
BB
sm0 Tp
Combined with Lemma D.5 we have the desired result.
Lemma D.7. For 1, we have
As+1
33+ 4log(e + - T/p1"
A
Proof of Lemma D.7
By Lemma
D.5
we have
1
A =
B,
+
2
(1+
Vnu) 1-1 +
(29)
m/
Thus, we have
Ast1
Bs+1 1/(1))
At
A
t-1
V Bs$1
b
A
VqHA
==0
2
1
< 3
log(e
(np(1 + vnp)i* + 1)
VTL.A
np
(by Lemma andland Lemma D.3
< 3 + 4 log(e + -)
)
(by Inequality 29
26

---

D.2 Proof of Theorem D.1
With all the useful lemmas in the previous section, we proceed to prove Theorem D.I. for which we need several additional lemmas. First, similar to Lemma C.4 the following lemma summarizes the results the classical potential function analysis of NAG for strongly convex functions in d' Aspremont et al., 2021].
Lemma D.8. For any 2 0, if the following inequality holds
1
f(y)) + (VI(v)) Fe+1 ya)
|| y1112 ((x++1),
2n
then we can obtain
1 + muA++1 ||2+11 - x01 (r(s(z)) 1*) +
1 + muAe
(f+((((ett) (*)
||
x²1
2nj
2nj
Proof of Lemma D.8 These derivations can be found in d' d'Aspremont et al. here for completeness.
[22]]
We present
The strong convexity between x² and Ye gives
vo) + 11 1| yo f' f(v)) (V)())), -3))
The convexity between and gives
f(z,) f() + (Vf())), 2z y1)-
Combining the above two inequalities and the one assumed in this lemma, we have
1 ||00 - y y1)1
ž (AL-1 - A0) - f(v)) - (V)())) x= yn)
2
A(((()) f(x,) - (V - 11))
1 ||,2 3ell
(44 f(ye) (V f xe+1 =1))
2n
Reorganizing can obtain
(f f²) 1 + muA++1
|| 1x"1
2n
< Ar(((z)) - -f')+ 1 1 Mua
11 - x²11
2m
(Ai - A4+1) Ac+1 - m...A....
V (vx)))
1 11+11111
2
A3 (Ar41 - A1) + m)) + m1AA4+1
11 - 2z
(Ar+1 + 22u A7)2
Then complete the proof noting that
(A, A )
11 = -B, 2
Ar-1
1
B1+1 +
Du((B4+ + 1/(1)))²
nH
1 -1uBB++ -2B
1
=mnBBt
7/
= -22 5.
Next, note that Lemma C.5 still holds in the strongly convex setting. We repeat it below for completeness. Lemma D.9. For any 1 2 0, if V (y()) s G, then we have ([ I)l S G. and furthermore,
f(y)) + (V)(),) L(+1 yt)
|| -1112 2 f((+1).
2n
27

---

With Lemma D.8 and Lemma D.9. we will show that [V - G for all f 2 0 by induction in the following lemma.
Lemma D.10. For all 2 we have |/ (V())l S.G. G.
Proof of Lemma D.10 We will prove this lemma by induction. First, by Lemma 3.5 and the choice
of G, it easy to verify that | (xx)]] - G. Then for any fixed 2 suppose that V (1 > S G for all < L. Then by Lemma D.8 and Lemma D.9 we know that [[V]((>)]| < G for all 0 S S L, and that for all 8 < 6
Ast1 (J(x+1)) - + + muAs+1
||0041 - x²1 - Ac(s(v)) - (²) 1 + muA,
| x² 1
2n
21
(30)
By telescoping 30 we have for all 0 < t,
f(r++1) - f" 1 As+17H (f(zo) f 1 + - x² 11))
(31)
For S I, since [V](())) G, then Lemma 3.5 implies
|V (210))l=2220000 ( (T 1*).
(32)
Note that by Algorithm
we have
2x (1 mus, (2-1)- - 2x-1) + 7(1 - 6,-1 v. Vf((e-1)
Thus
t-1
21 Jt
Σ
11 8.) ().))
II (1 mpdd)(1 Ti).
Therefore
V1 1t TIT
[1 (.
II (1 n1:: T.).
==0
#=$+1
Moreover
(1(11+1 - A.)
1 muA,
- npo; = =
+ muA++1 quAt+1
and
(A++1 A1 +MAA)))
A, + muA,+1)
Aa + 77A(41))
1 T4 =1
A.11 + 21/4A, Aada
A An yuun
A (1 muA,))
Thus we have
t-1
Ast1
As+1 [f =:
llve xell S 177s
Σ (5. 1)
[Vf().)
En A
Σ
A
8=0
2=0
where the second inequality follows from Lemma
D.4
We further control term I by
1-1 Ast1 (IV
I < 1
)l + 7 (v()))
A₂
==0
[-1
Ast1
$ 1LI + 1
V [1]]
A
e=0
28

---

Thus we have
ye x
-
77
[-1
A,+1
[f((zt1)
1 7L
A,
5
11
As+1
/2L(f(10=))
(by 32
1
A,
[-1
As+1
1 (f(xo) - f + to 1| - x² 2²1²²)
$ 1
22 V
(by 31
At
A0+17H4
8=0
8 + 11 1110=00000 2²1
Ag+1
A
V 2nL(S(20) f 1|:0 x*113)
3 + 13+41og 4log(e + m12 :
(by Lemma D.7
(1-1L)
/ (3
11)
G 11/2-1/a
3 4 4log(e + np
(by (27
nT.
4log(e + )
G
(by (28
log" 2
c+ 1441,32/0
24L
G
$ S r(G)
2L
Since [[+() < G and we just showed ||x, - y.ll S r(G), by Lemma 3.3 we have
[ s [V)()))) 1/5, xx:l
2h.
G
s <V nuu,
((f(x)) f*) 41 11 x+1 + L
(by (31
2L
s 1 + S.
(by A. 2 1/(1)) and 27
Then we complete the induction as well as the proof.
Proof of Theorem D.I Combining Lemmas D.8 D.9 and D.10 we know the following inequality
holds for 2
A+ ( 1*) + 1 nuA441
1+ quA
| - x²11 s Ac([(z)) 1*)
|| x:
2m
21
Then by telescoping, we get
Ae(f(z)) - f*) + mua,
|| x0112 S Ao(f(ro) - f()++ 1 + muAo
1|20 x²1
21
21j
Finally, applying Lemma D.5 we have At B, 1/(11)/) (qp) 2 1/(1 -pp 1 + 1/(pp). Thus completes the proof.
E Analysis of GD for non-convex functions
In this section, we provide the proofs related to analysis of gradient descent for non-convex function, including those of Lemma 5.1 and Theorem 5.2
Proof of Lemma 5.1 First, based on Corollary 3.6 we know [[V[(x]] S < co. Also note that
||a- 2|| = |lv] < G G/L.
29

---

Then by Lemma 3.3 and Remark 3.4 we have x E X and
f(xt) Sf(x) + (Vf(2)), - 2) + / || z012
2 =f(x) - [ <f(x).
Proof of Theorem 5.2
By Lemma 5.1 using induction, we directly obtain f(x,) < f(ro) for all
t 0. Then by Corollary 3.6 have [[V](*))] G for all 2 O. Following the proof of Lemma 5.1 we can similarly show
((4+1) ((m)) S (11 (n11~ - |V(E)) [V(())))
Taking summation over < T and rearanging terms, we have
[V(x))] 2(f(2o)) [(TT)) 2(1(z)) (*)
T KT
1/T
1/T
Analysis of SGD for non-convex functions
In this section, provide the detailed convergence analysis of stochastic gradient descent for f-smooth and non-convex functions where is sub-quadratic.
We first present some useful inequalities related to the parameter choices in Theorem 5.3
Lemma F.1. Under the parameters choices in Theorem 5.3 the following inequalities hold.
2T 2T 1/2,
nLoLT s 1/2,
100n2To²L' S 5G
Proof of Lemma F.I First note that by Corollary 3.6 we know
=2= 16L(f(xx) fr + +0//22 16Lo/8.
ie., aL < G86/1. Then since we choose 1 4GVT" we have
1G SV2/4 S 1/2, n'OLT TG < 6/256 < 1/2, 100 <100, 6² /2/6 < SG
Next, show the useful lemma which bounds E[f(x+) fr] and Eier (Vf simultancously. Lemma F2. Under the parameters choices in Theorem 5.3 the following inequality holds
E
f(zx) f + 7 Σ [V
< f(zo) 1 t
Proof of Lemmal F22
t < т, by the definition of r, we know f(x:) - f < and
||ce| S k
and the former also implies |/ (zx))
< G by Corollary 3,6 Then we can bound
| x, || = 7 ||
< (llV [lel)) S S +
5L L
30

---

where we use the choice of S 2L' Then based on Lemma 3.3 and Remark 3.4 for any < we have
L
-( (( 2z)
| xell
L
= (Vf(z)))9) +
2 l1
s (V((())))) + L|
+ |
(33)
where the equality due to (4): the second inequality uses 9t ct V (axe)) and Young's 's inequality lly + =11² |lyl + || any vectors y, 2; and the last inequality chooses 1) S 12L)) Taking a summation over t < and rearanging terms, we have
f(x+) - f
[V(+=)] & f(x)) - f E(Vi(a).a) + n² Σ 1al1
Now we bound the last two terms on RHS. First, for the last term, we have
E
Σ <<
|ell
S E
Σ |eell
S ouT,
DCT
where the first inequality s T by its defnition; and in the last inequality
Assumption 4
For the cross term, note that E,-1 (f()))) by Assumption 4 So this term is sum of martingale difference sequence. Since 7 is stopping time, we can apply the optional stopping theorem to obtain
E
=
(34)
Then have
V (Z)))
=E (Vf(=t),, $ SGE||
G &
G
E
||ll|
S
where the equality due to (34); the first inequality uses V ff S G by the definition of 7 in (5)
and Corollary 3.6 the fourth inequality uses E[X]² s x for any random variable X; and the last inequality uses Assumption 4
Combining all the bounds above, we get
E
[(x)) -
<1(x0) 1 +oo + LT 7 Σ [V+(()))
<f(x0) 1 to,
where the last inequality is due to Lemma F.
With Lemma
F2 we are ready to prove Theorem 5.3
Proof of Theorem 5.3
We want show the probability of {T T} is small, its complement 8 < F for all < which implies [V+() & G for all T. Note
{T = T} means (xt)
that
<<< = (T2 UUU < T
31

---

Therefore we only need to bound the probability of each of these two events on the RHS. We first bound P( T). Note that
P(r2 < <T) =P
U
|Ieell
>
G
5nL
K<
G
P
||eell
5m
K<
25n
To²
G
26/4,
where the first inequality uses union bound; the second inequality applies Chebyshev's inequality
and E E []] E[Ex_i[llee]]]]] S o² for each fixed by Assumption 4 the last inequality uses Lemma
Next, we will bound P(n <T = T). Note that under the event {11 < <T, T), we know that T TI < T which implies f(x++1) - > F; and 2) < T 72 which implies ||e~|| S 5n
G by
the definition in (5). Also note that we always have fxx+) - f s F which implies [/ ) S G
by Corollary 3.6 Then we can show
G
G T,
| xz || = 119111 S [[[[[(=))]] |c, S G
5T.
where we choose 17 S 27. Then based on Lemma 3.3 and Remark
3.4
we have
f(x++1) - f(x+) - " [ (V)(<)),
+ 172 ||c
Sn
||<||| r7²L ||-1|
G²
F
2
where the first inequality is obtained following the same derivation in 33 the last equality is due
to Corollary 3.6 Therefore we can show that under the event {7) T, 72 T),
[(x) - = f(xx) - (XT+11 + [(x++1)) - 8" F/2.
Hence,
B[f fr F/2
2(f(xo) - f +
P(Ti <
8/4,
F
where the second inequality uses Markov's inequality: the third inequality uses Lemma F22 and in the last inequality we choose F = 8(f(2o) f + 08/8.
Therefore we can show
P(r < - P( < T) + P(n < <T.7 5
Then we also know P(7 = T) 2 6-2 2 1/2. Therefore, by Lemma
2(f( - ff*
>E
[+))))))
1
2P(T= T)E
Vf((;)) T
.KT
V
[xxx))) T=
32

---

Then we have
|| T = T| -
4(f(20)
8 + 0)
6F
6
Vf (x++))]
V c
T K<
n/I
2n
2
where the last inequality uses the choice of T. Let E == + EeT [f(=)))] > e²} denote the
event of not converging to an e-stationary point. By Markov's inequality, we have P(E) z 6/2. Therefore we have P([T TT U S 6, which completes the proof.
0
G
Lower bound
In this section, we provide the proof of Theorem 5.4
Proof of Theorem 5.4 Let e, No > satisfy no S 2/22. Consider
log([z) c),
[x| 2 y
[(x)
2log(1 c) - loggoyy - |z|| c);
e/2 S |x| < ạ
kx² +b,
|x| < c/2,
where is constant and y (c+ + c2 + 2n/) /2 0 is the fixed point of the iteration
170
11+1
It
and are chosen in such way that f(x) and f'(x) are continuous. Specifically, choose A e fc(c/2) and b = fcc/2) ef (c/2/44. Since f(-x) fz). fxx is symmetric about the line == In a small neighborhood, f (z) is symmetric about (y. fz)), so f'(x) continuous at y.
Let us first consider the smoothness of f. By symmetry, it suffices to consider x > 0. Then,
x x29 y c/2 x < (2y x c)-
(x c) -1
f((x) =
2kr,
0 < c/2
Its Hessian given by
-(x c)-
I H> y c/2 < x <g
(*(x)
(2y x c)
2k:
0 < x < c/2.
Hence, f(x)) 2k, 1)-smohth
Note that f(x) has a stationary point O. For stepsize "y satisfying v/o S 7) S 2/4 there exists
== (c+ /e² + 2ny) 2 such that -2 = z- (y cy and by symmetry, once 2, = 2, = +æ for all 2 T, making the GD iterations stuck. Now we choose a proper uo such that f f'(rr) and f(0o) - f(0) are bounded.
We consider arriving at y from above. That is, xo 2 x 2 ... Fy = = c 0. Since in each update where 1z+1 It my (x; - c) >c G,
Zt It+1 = It- - (zt - ( -
-) ())
= my (xt - c) & VTF.
Hence, we can choose in such a way that 3c/2 & < 3c/2 + /nl- Then,
log(c/2) < ((x) S logle/2+ + / 2/(c + 2 < f'(xx) < 2/c. By definition, c= mu(c + vc² + 2np) 0m -1 Hence,
f(c/2) 2 log(y c) log 2y c/2 c)
= log(())) - log(c + v + 2mp) log( V 2 27o0 c/2),
1
f(c/2)) / 2 2no0 c/2
33

---

Then.
f(xo) - f(0) = -((o)) - f(c/2) + of (c/2)/4
I log(c/2 + vTF + 2og 1o 1) + log(c + v + 2110)
+ +oog( V 2 + 2njo c/2) + c
4 /² c² + 2170 - c/2
(2v 26 + log( v2c2) + 1
I log(c) + 20go + 2 log
2
= 4 log(c) + 2 log(
log(2) + 2
For stepsize ff < foo, reaching below 4c/3 takes at least
- ///3)/////// / 2 c/ c/6 > cq 1/2
steps to reach 4c/3, where f'(4c/3) = log(c/3).
Now we set and and scale function f(x)) to satisfy the parameter specifications Lu, L2. Go. Aq. Define (zz) L fzr) Then, (xx) is (2, 2 L2)-smooth. Since the gradient of g(x) is L times fxx), the above analysis for (xx applies to g(x) by replacing yo with ? = [22 and ff with
L2 To ensure that
1
4
2h = -2(cI2)- = cL2 2 2m12
S
I Lo:
c/2 c2
suffices to take c c² Lol2. To ensure that
2 < Go. Tzc
(((0)) s
it suffices to take 2 2/)2Gu) To ensure that
g(xa)= g(0) < (4 log(e) (lg((n 3.5 + 0.5) s Do:
it suffices to take
log(1/ L2 3.5 2 - 0.5
2 log(c).
2
Since we require 771 S c2/ parameters Le and Ao need to satisfy
log 2 - 2log(c) L2D0 3.5 3.5 2 0.5
2 log(c).
2
that is, TzAn 5.5 log + 0.5, which holds because T₂ 10. Take
max(2//LLa (/LgG), /8/Lo). Then, long 7 S L/Lu, the requirement that n S c² 22/4 is satisfied. Therefore, on g(z) with initial point Ho, gradient descent with a constant stepsize either gets stuck, or takes at least
L24n
3.5 - 0.5
CT) 1/2/6-
log(c)
exp
6
4
Lo
3.5 log 2 - 0.5
exp(
6
4
L2
exp(
6
8
steps to reach 1-stationary point.
On the other hand, if 2/ Lop consider the function f(x) to For any x4 * 0, always have |0++||/ / |æz| = |1 ryLol > 1, which means the iterates diverge to infinity.
34


Reviews:
[{"review_id": "o5Rd0ztOsP", "reviewer": "Reviewer_MmTX", "summary": "This paper generalizes the classic Lipschtiz smooth gradient condition, as well as a recent improvement. The proposed condition is essentially saying the Hessian norm is bounded by a non-decreasing function of the norm of gradient. Using such conditions, the authors proved convergence rates of gradient descent under various settings (convex, strongly convex, non-convex, stochastic). Classic optimal rates are recovered.", "questions": "See above", "limitations": "Yes", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is well presented. The technical contribution looks original and significant, as it is a generalization of the classic smoothness. Intuitions are shared for proving the convergence.", "weaknesses": "Overall, I do not have major concerns. \n\n1. The proof of Theorem 5.1, in particular the split of two time steps in (4) seems delicate and interesting, but also a bit out of blue to me. Is this splitting novel, or did part of it show up in the literature? What motivates such a splitting? \n2. Do you have examples of objective functions that show up in machine learning or other applications, such that they satisfy the generalized smoothness, but not the conventional smoothness? This would add much significance to the paper.\n3. It was not clear to me when we assume the function to be C^2 and when not. In the introduction, It appears at first sight that only twice differentiable functions are considered. Then I saw definition 2, so it is not true. Then I got confused again at Proposition 3.3: it seems that for l-smooth to hold you need f to be C^2. Did you assume it somewhere?\n4. Line 27: “provide a lower bound”. Do you mean on the number of iterations or on the error, or both?\n5. Table 1: Why is it called gradient complexity? Is it the number of times the gradient oracle needs to be queried? I thought a more common name is iteration complexity, but maybe I am wrong. \n6. Lines 46-48: “if gradients along the trajectory are bounded by a constant G, then the Hessian norms are bounded by the constant ℓ(G).” Why is this “if-then” true? Say we look at a univariate objective function f: R -> R. Its gradient g is also univariate. Are you saying that if g is bounded by a constant G, then |nabla g| is also bounded? This can not be true, since nabla g can be arbitrarily large.\n7. Line 77: “condition number” of what? \n8. Proposition 3.6: “If” -> “Suppose”\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments! Below we will try to address the questions of the reviewer.\n\n1. Regarding the proof of Theorem 5.1, this splitting is indeed novel and we are not aware of any previous optimization analysis using similar techniques. Let us briefly talk about the motivation for this approach below. First, it should be natural to consider $\\tau$ since our contradiction hypothesis is equivalent to $\\tau<\\infty$. Then we know that before $\\tau$, everything is well bounded, e.g., gradients and Hessian. Then informally speaking, classical analysis directly gives an upper bound of $S_{\\text{uc}}$, the area under the curve in Figure 1. However, since the gradient norm at $\\tau$ is very large by definition, if we assume there are no abrupt changes in the curve (which is true for a small enough step size), then in some neighborhood around and before $\\tau$, the gradient should stay large. Then a lower bound on the size of such a neighborhood essentially gives you a lower bound on $S_{\\text{uc}}$, and potentially leads to a contradiction. So we introduce $\\tau_{1/2}$ just to rigorously define the neighborhood.\n2. Regarding examples in machine learning applications, we think the empirical findings in the papers that study $(L_0,L_1)$-smooth functions (e.g. [Zhange et al., 2019] and [Wang et al., 2022]) can also be used to motivate our more general $\\ell$-smooth functions. They observe that when you train a language model, along the trajectory of certain optimizers, log(Hessian norm) is roughly a linear function of log(gradient norm), (i.e., Hessian norm is roughly a polynomial function of gradient norm). So we think our $\\ell$-smooth function class can better capture this property.\n3. This is a good question. We NEVER assume twice differentiability in this paper. Definition 1 only assumes twice differentiability **almost everywhere**, which means there may be a measure-zero set where Hessian does not exist. Our Proposition 3.3 is rigorous. When proving the direction from Definition 2 to Definition 1, we rigorously show that any $(r,\\ell)$-smooth function defined in Definition 2 is twice differentiable almost everywhere. This uses the Radermacher Theorem (which states that any Lipschitz function is differentiable almost everywhere) and a covering argument (see Lines 509-517 in the appendix).\n4. Here we mean a lower bound on the iteration or gradient complexity. We will make it clear in the revision.\n5. Yes, gradient complexity is exactly the number of times the gradient oracle needs to be queried, i.e., the oracle complexity when the oracle is a gradient oracle. For our theorems, it is equivalent to iteration complexity because each time we exactly query the oracle once. We think it is as common as iteration complexity, we use it because existing lower bounds are usually presented in terms of oracle complexities [Carmon et al., 2017, Arjevani et al., 2019].\n6. This argument is a direct consequence of Definition 1, which bounds Hessian using gradient norm.\n7. Here we mean the condition number of the objective function. It is defined as $L/\\mu$ for $L$-smooth and $\\mu$-strongly-convex functions.\n8. Thank you for pointing out the typo. We will fix it in the revision."}, {"review_id": "RJ3saJotbP", "reviewer": "Reviewer_cK5L", "summary": "This paper introduces a new assumption generalizing classical smoothness, and named $\\ell$-smoothness, motivates it by giving providing examples of non-smooth functions belonging to this class, and studies classical algorithms under this assumption.", "questions": "Can authors discuss my first point?\n\nAlso, can they try to study SGD under expected smoothness assumption?", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper is clear and fairly compared to related work.\n- The new class is well defined and motivated, and authors show that we can obtain results under it.", "weaknesses": "$\\underline{\\text{General remarks}}$:\n\n- First, I would like to make a somewhat subjective statement about the class: in my humble opinion, it seems a bit flawed as it does not respect fundamental homogeneity properties. Let me explain:\n\nLet $f\\in\\mathcal{F}_{\\ell}$ the class of $\\ell$-smooth functions. For $\\alpha, \\lambda > 0$, define $g$ as $g(x)=\\frac{\\alpha}{\\lambda^2}f(\\lambda x)$ (assume wlog that their minimum is in 0, otherwise translate $f$, then create $g$).\nWe verify $\\nabla g(x)=\\frac{\\alpha}{\\lambda}\\nabla f(\\lambda x)$ and $\\nabla^2 g(x)=\\alpha\\nabla^2 f(\\lambda x)$,\nhence $\\|\\nabla^2 g(x)\\| = \\|\\alpha\\nabla^2 f(\\lambda x)\\| \\leq \\alpha \\ell( \\|\\nabla f(\\lambda x)\\|) = \\alpha \\ell( \\frac{\\lambda}{\\alpha}\\|\\nabla g(x)\\|)$.\n\nFinally, $g\\in\\mathcal{F}_{\\alpha \\ell(\\frac{\\lambda}{\\alpha} .)}$.\n\nLet us assume that after some analysis of an algorithm like GD (this reasoning also applies to momentum), we find out that the step-size that achieves the best worst-case guarantee on the class $\\mathcal{F}_{\\ell}$ is $\\gamma_{\\ell}$.\n\nThen, if I need to optimize $f$, I will use $x_{t+1} = x_t - \\gamma_{\\ell} \\nabla f (x_t)$.\n\nNow, instead I minimize $g$, I will use $x_{t+1} = x_t - \\gamma_{\\alpha \\ell(\\frac{\\lambda}{\\alpha} .)} \\nabla g (x_t) = x_t - \\gamma_{\\alpha \\ell(\\frac{\\lambda}{\\alpha} .)} \\frac{\\alpha}{\\lambda}\\nabla f(\\lambda x_t)$.\n\nNote that $f$ and $g$ have the same minimum and if we introduce the iterates $y_t = \\lambda x_t$, we have\n\n$x_{t+1} = x_t - \\gamma_{\\ell} \\nabla f (x_t)$ when minimizing $f$,\n\nand\n\n$y_{t+1} = y_t - \\gamma_{\\alpha \\ell(\\frac{\\lambda}{\\alpha} .)} \\alpha\\nabla f(y_t)$ when minimizing $g$.\n\nIn short, we need to have $\\gamma_{\\ell} = \\alpha \\gamma_{\\alpha \\ell(\\frac{\\lambda}{\\alpha} .)}$, or again $ \\gamma_{\\alpha \\ell(\\frac{\\lambda}{\\alpha} .)} = \\frac{\\gamma_{\\ell}}{\\alpha}$.\nIndeed, they both optimize their dynamics.\n\nThis shows that $\\lambda$ has no impact on the optimal way to tune an algorithm. And we can stretch the function $\\ell$ as much as we want and notice that probably only $\\ell(0)$ matters, i.e. the smoothness constant in the optimum.\nIn particular, applied to the case where $\\ell(x) = L_0 + L_1x$, it is clear that the optimal parameter cannot depends on $L_1$.\n\nThis observation is explained by the lack of homogeneity in the formula: when scaling a function, only $L_0$ is scaled, not $L_1.$\nIn $L$-smooth class, the worst-case function generally do not belong to the $L-\\varepsilon$-smooth class. Hence there is a hierarchy of the classes, but here, it seems that by scaling a function, the worst-case dynamics does not depend on some part of the class definition, leading to useless specification.\n\nThis point can be further discussed. This is just some thoughts I had based on the class definition which I never used and I am aware from the related works section that some people are working with it. Thus I would be happy if authors could discuss this point.\n\nHowever, based on this remark, my first guess was that the analysis would basically lead as the same analysis as when $\\ell$ is constant, or $L_1=0$, which leads to my next point.\n\n- Second, we indeed recover classical analyses everywhere in this paper. There indeed is an additional argument, that is the sequence of iterate stays in a compact and by regularity of $f$, we can bound the gradients, hence the hessians and conclude with all the classical analyses.\nIndeed:\n    - Th4.2 and 4.3 use classical Lyap analyses.\n    - Lemma 4.1: Using cocoercivity, authors prove $\\|\\nabla f(x_t)\\|$ is decreasing.  Using the same proof, one could have that $\\|x_t-x_\\star\\|$ is decreasing as well. And using descent lemma, we have that $f(x_t)$ is also decreasing.\nFinally, we can prove the descent lemma without assumption of $\\ell$-smoothness by just assuming the continuity of the hessian, and taking G as upper bound of $\\lbrace \\|\\nabla^2 f(x)\\| | x\\in\\mathcal{X} \\text{ and } f(x)\\leq f(x_0) \\rbrace$ which is assumed to be a compact since authors assume that the function tends to infinity on the border of $\\mathcal{X}$. We have the revisited descent lemma: $f(x_{t+1}) \\leq f(x_t) - \\eta\\|\\nabla f(x_t)\\|^2 + \\frac{1}{2}\\eta^2 G \\|\\nabla f(x_t)\\|^2$, and by taking $\\eta$ sufficiently small, we insure in 1 calculus that\n    - 1) $f(x_t)$ is decreasing and that all the hessians keep being smaller than $G$.\n    - 2) the squared gradients are sommable, hence the classical complexity $O(1/\\varepsilon^2)$ that is as in thm5.1, obtained in a much simpler way.  Of course, here we only assumed the hessian to be bounded, so $\\ell$-smoothness + bounded gradients do the job.\n\nIn conclusion, in my opinion, most of the results are almost straightforward from what is known in the literature.\n\n- Third, in my opinion, the stochastic assumption A4 is too strong. I am aware authors claim that some works in the literature assume even stronger assumption, but A4 is way too strong: no multiplicative noise, only additive. This paper claims generalizing smoothness, but linear regressions with MSE losses are not even covered by the section 5.2.  Plus, bounded variance are too easy to handle in general and leads to an analysis close the deterministic case.  Instead, authors should consider expected smoothness (or its equivalent in $\\ell$-smoothness). Actually, under the assumption that there is a finite number of functions under consideration, I would guess we could generalize the same arguments as in the deterministic case to ensure all the hessians to be bounded on the optimization iterates and basically use classical SGD proof in the smooth case.\n\n$~$\n\n$\\underline{\\text{Minor}}$:\n\n- Clarity:\n\n    - Assumption 1: First recall definition of « closed function »\n    - Also define « sub-quadratic »\n    - l.468: It took me a while to find where this proof was. Please do as for other propositions: state it right before the proof. In a general way, please state all theorems right before their proofs if reported in appendix. Use the « restatable » latex package too avoid renumbering.\n    - Proof of lemma B1: From convexity and local smoothness, authors apply the $\\underline{\\text{descent lemma}}$ on the $\\underline{\\text{Bregman divergence}}$ of the objective function to obtain local $\\underline{\\text{cocoercivity}}$. The proof is the same as for global smoothness. Yet, for completness and care of the neighborhood needed to obtain the cocoercivity, I understand that the proof is provided. However, It needs a reference to this classical result in the global smooth case and mention of the 3 underlined terms when used.\n        - l.550: Cocoercivity\n        - l.553: Bregman divergences\n        - l.562: Descent Lemma\n    - l.560: please introduce y: « let y [as in the lemma statement] »\n    - l.248: « Theorem 5.1 gives the classical $O(1/T)$ rate, or $O(1/\\varepsilon^2)$ gradient complexity » -> $O(1/\\sqrt{T})$. Authors do not clearly state if they are talking here about gradient norm or its square, but they need to be consistent when talking about rate and complexity.\n\n- Typos:\n    - l.2: \"Lipshitzness\" -> Lipschitz continuity.\n    - l.76: \"strong convex\" -> strongly convex\n    - l.79: $\\nabla$ is missing\n    - l.144: « $x = x_2 = x_t$ » ? I guess \"$x$\" needs to be removed\n    - l.169: « accelearted » -> accelerated\n    - l.570: 1/L -> 2/L\n\n\n- Misc:\n    - Table 1: missing hline + be precise on the meaning of « - ».\n    - Table 1: for GD non convex: « Inf or $\\Omega$ … » could be summed up as «  $\\Omega$ … ».\n    - l.121-122: Put 2) under 1). It should not exceed the current number of lines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would to thank the reviewer for the insightful thoughts and comments! Below we will clarify the three points in the review.\n\n**1. Regarding the first point**, the reviewer made a very interesting reasoning regarding the optimal worse-case step-size $\\gamma_{\\ell}$, as defined in the comment. However, we want to point out that, for our $\\ell$-smooth functions, **the stepsize has to depend on the initialization point**, in addition to $\\ell$. Otherwise, let us consider the simple convex function $1/x+1/(1-x)$ with domain $(0,1)$. For any positive stepsize independent of the initial point, we can always find some initialization point $x_0$ close enough to $0$, whose gradient is large enough so that after one step of gradient descent, $x_1>1$ goes outside of the domain.\n\nLet the optimal worse-case stepsize be $\\gamma_{\\ell, \\\\|\\nabla f(x_0)\\\\|}$ which depends on both $\\ell$ and $\\\\|\\nabla f(x_0)\\\\|$, as in all our theorems. Following your reasoning, we can obtain something like $\\gamma_{\\ell, \\\\|\\nabla f(x_0)\\\\|}=\\alpha \\gamma_{\\alpha \\ell(\\frac{\\lambda}{\\alpha}\\cdot), \\\\|\\nabla g(x_0/\\lambda)\\\\|}=\\alpha \\gamma_{\\alpha \\ell(\\frac{\\lambda}{\\alpha}\\cdot), \\frac{\\alpha}{\\lambda}\\\\|\\nabla f(x_0)\\\\|}$ (Note that the initial point for minimizing $g$ is re-scaled to $x_0/\\lambda$). From this equation, we can see that $\\lambda$ indeed matters. In fact, this equation is very consistent with our step-size choice in Theorem 4.2: $\\gamma_{\\ell, \\\\|\\nabla f(x_0)\\\\|}\\approx \\frac{1}{\\ell(\\\\|\\nabla f(x_0)\\\\|)}$ (which we believe is also worse-case optimal). With this choice, both sides of the equation are the same.\n\nFor the case where $\\ell(x)=L_0+L_1x$, the step-size is $\\frac{1}{L_0+L_1\\\\|\\nabla f(x_0)\\\\|}$, which does depend on $L_1$. Therefore, the worse-case dynamics do depend on $L_1$ and there is indeed a hierarchy in our function classes. Regarding your point about lack of homogeneity, it is true that when you scale $f$ to $g=\\alpha f$, the constant $L_1$ does not change much. However, that only applies to the specific setting where $\\ell$ is linear. For example, consider the function $f(x)=1/x$ which is $(3/2, 0, 2)$-smooth per Definition 3 in our paper. After scaling it to $\\alpha/x$, it becomes $(3/2, 0, 2/\\sqrt{\\alpha})$-smooth, which means the constant $L_{3/2}$ changes from $2$ to $2/\\sqrt{\\alpha}$.\n\n**2. Regarding the second point**, we want to clarify the following several points in your argument\n- (1) The set $\\mathcal{S}:=\\\\{x\\in\\mathcal{X}, f(x)\\le f(x_0)\\\\}$ is NOT compact. We only assume $f$ is closed (the definition of a closed function is that all of its sub-level sets are closed). So $\\mathcal{S}$ is not necessarily bounded (thus not necessarily compact as well). Consider the closed function $f(x)=\\exp(-x)$ with domain $\\mathbb{R}$ which satisfies all our assumptions. Clearly $\\mathcal{S}$ is not compact for this example and the iterates also go to infinity. Since $\\mathcal{S}$ is not compact, it is not so straight-forward to bound gradient norm or Hessian within it.\n- (2) The assumption of continuity of Hessian is not necessarily weaker than $\\ell$-smoothness, for the latter Hessian may not exist over some points (with zero measure). For example, our example function used to show the lower bound in Theorem 5.3 has some points where Hessian does not exist.\n- (3) However, if assuming $\\ell$-smoothness with a sub-quadratic $\\ell$, we can indeed bound gradient norm (and thus also Hessian) within it using our Lemma 4.5. However, we want to point out that, Lemma 4.5 is derived based on Proposition 3.3 (the equivalence between $\\ell$-smoothness and $(r,\\ell)$-smoothness), which is indeed nontrivial and one of our novel contributions. This approach does offer a different way to proving convergence of GD. We were actually aware of this alternative approach and already mentioned it briefly in Section 5.3 (Lines 326--333)\n- (4) However, this approach only works easily for the simple algorithm GD, not for NAG or SGD. Because for NAG, SGD, and potentially other more complicated algorithms, the function values are not really decreasing. For SGD, iterates can easily escape from $\\mathcal{S}$ due to its heavy-tailed noise. For NAG, although we can easily bound $f(x_t)$, what we really need is a bound on $f(y_t)$, which turns out to be quite challenging.\n\n**3. Regarding the third point**, although our bounded noise assumption does not apply to linear regression with MSE loss, we think it is the most standard assumption in the optimization literature and is interesting and challenging enough. Noise with bounded variance is actually heavy-tailed and SGD with such noise is much more challenging than deterministic GD. For example, consider the function $f(x)=1/x+1/(1-x)$ with a bounded domain $(0,1)$. With noise, the iterates may easily go outside of the domain. Indeed, if you keep running, it will go outside with probability $1$. So the key is to show that with high probability, it converges before going outside. Also, since it is heavy-tailed, applying a naive union bound does not work and we feel it is necessary to use a stopping time analysis (and optional stopping theorem) which is novel compared with classical one-step analysis.\n\nWe thank the reviewer for pointing out the expected smoothness condition. We feel it should be doable and there are actually recent papers studying this condition for $(L_0,L_1)$-smooth function and variance reduction methods (see [Reisizadeh et al., 2023] cited in our paper). However, it is not necessarily weaker than our bounded variance assumption, and we have reservations about whether the former is more interesting or challenging than the latter.\n\nFinally, we thank the reviewer for suggestions regarding the writing, typos, etc., and will update them accordingly in the revision.\n"}, {"review_id": "KH2ZoAqc0M", "reviewer": "Reviewer_GKNp", "summary": "This paper generalizes the recently introduced (L0,L1)-smoothness which itself extends the L-smoothness which is key in analyzing rates of convergence of optimization algorithms. The authors introduce the concept of $\\ell$-smoothness where $\\ell$ is a function of the gradient of the function to minimize (e.g.: a polynomial).\nThe key idea is to show that under the $\\ell$-smoothness assumption, the gradient remains bounded along the iterates of a given algorithm.\nThe authors focus on smooth optimization and tackle both convex and non-convex settings, in which they (roughly) recover the bounds already known for L-smooth functions and show whether they hold or not with generalized smoothness depending on the function $\\ell$.", "questions": "1) Line 106 on the fact that f has to tend to infinity. First it might be good to specify +infinity (instead of infinity) to remove any ambiguity. Then I think that the statement is not true in its current form since R^d is an open set, yet there, the epigraph of f is closed without coercivity assumptions (as the authors discuss after). I think that the discussion is valid for *bounded* open domains. Could you clarify/correct this?\n\n2) Line 157. Following my previous question, the authors motivate the use of a domain X so as to include functions like logarithms and rational functions. However it seems that these functions are not closed (eg: log(x) when x -> 0), so Assumption 2 does not hold. Could you comment on that?\n\n3) Line 76-78. In the paper, and notably at these lines, there is a confusion between NAG which is indeed optimal for convex functions, and Heavy Ball with Friction (HBF). Indeed, NAG while being similar to HBF is not optimal in the strongly convex setting but HBF is. This should be clarified. (l76-78)\n\n4) On Assumption 3 (existence of a minimizer). While being reasonable this makes the studied framework more restrictive than the classical one (where the optimal rate is also valid for functions whose minimizer is at infinity). Therefore the results are not valid for the whole class of convex functions (but a very large subset of it), this should be a little more emphasized while discussing the contributions so as not to mislead the reader in the introduction. \n\n5) It would be better to define rigorously \"sub-quadratic\", in particular, does it include quadratic functions or is it strictly sub-quadratic? \n\n6) Do the authors have any idea on whether their modified NAG (Alg. 1) might improve NAG even when used on L-smooth functions? (even though NAG is already theoretically optimal). If not, is it worse than the vanilla version or does it behave similarly? Numerical experiments would be insightful here too.\n\n7) Typos: l76: strong convex -> strongly convex\nl207: line 6 of the algorithm -> Is it not rather line 4 of the algorithm? ", "limitations": "Some limitations are discussed, in particular those related to NAG in the non-convex setting. The limitations about existence of a minimizer might be further discussed (see questions). \nSocietal impact is not really applicable here.\n", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is well written, and the presentation is clear. The mathematical statements are rigorous and I did not spot mistakes. The paper builds on existing works on (L0-L1)-smoothness but significantly extends them and covers many important settings (convex/non-convex, etc.). Additionally, I found the reasoning interesting and the proof techniques used depart from the classical ones (especially in the non-convex setting). \nOverall, I think that this paper brings a significant contribution to the important question of the convergence of optimization algorithms. My general feeling is very positive.", "weaknesses": "On the theoretical side I think that there are some minor bugs (see questions below), but nothing really problematic.\nHowever, while the paper has extensive theoretical results, it does not provide any numerical experiments, which is important for machine learning and optimization papers. It would have been, for example, very informative to see how the theory allows making GD and NAG converging beyond Lipschitz assumption by using the author's step-sizes conditions.\nThe related work section seems too short to me given that gradient-based optimization is a very active topic of research. For example the authors call many results as \"well known\" where instead credit could have been given.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback! We will add some experimental results to support our theories in the revision. We will also consider adding more related works. Below we try to address your questions.\n\n1. First, we do mean positive infinity in Line 106, and thank you for pointing it out. We do not quite understand why the argument \"since $\\mathbb{R}^d$ is an open set, yet there, the epigraph of f is closed without coercivity assumptions\" suggests our statement is not true. We believe it is consistent with our statement. Note that $\\mathbb{R}^d$ does not have boundary, and thus in this case, we do NOT require $f$ to go to infinity when $x$ goes to infinity. Please let us know if we misunderstood your question.\n\n2. We want to clarify that, although Assumptions 1 and 2 are necessary for our convergence analysis,  the definitions of $\\ell$-smooth or $(r,\\ell)$-smooth functions themselves are independent of these two assumptions. So the examples in this section do not need to satisfy these two assumptions. Of course, we are more interested in examples satisfying them. So the logarithmic function here refers to $-\\log(x)$ and rational functions refer mostly to those satisfying these two assumptions.\n\n3. Thank you for the suggestion! Could you elaborate on why NAG is not optimal for strongly convex functions, given that its complexity is $\\sqrt{\\kappa}\\log(1/\\epsilon)$? \n\n4. Our analysis does directly apply to the case where the optimal point does not exist. We make this assumption just to present the convergence result in terms of the distance between the iterate and the optimal point, so that it looks similar to the most classical textbook ones. We will make it clear in the revision.\n\n5. We mean strictly sub-quadratic functions, which means $\\lim_{u\\to\\infty}\\ell(u)/u^2=0$, and will make it clear in the revision.\n\n6. Our modified version of NAG has the same rate as the classical one for $L$-smooth functions. The modification is minor and for technical convenience. We are not sure whether the modification is necessary for generalized smooth functions. We will add some empirical results based on the suggestions.\n\n7. Thank you for pointing out the typos, and we will fix them in the revision.\n"}, {"review_id": "QAAUkdTJwA", "reviewer": "Reviewer_QDyc", "summary": "Relaxed smoothness conditions have been introduced to study the gradient clipping algorithm, and show that clipping in particular allows fixed step-size convergence without smoothness under this relaxed assumption. This paper further generalizes the relaxed smoothness notion used for clipping by bounding the Hessian by any non-decreasing function of the gradient norm. \n\nThen, fixed step-size convergence is shown under the relaxed smoothness assumption in a variety of settings. The key technical part is to show that assuming a large enough initial bound on the gradients and relaxed smoothness, the gradients remain bounded throughout the trajectory regardless of the setting (convex, strongly convex, non-convex, and even stochastic with some necessary caveats). Then, boundedness of the gradients along the trajectory implies the regular smoothness condition, and thus standard analyses can be used to show convergence of gradient descent. ", "questions": "1) The main argument is that global bounds hold on the gradients. Although it is good to have, this potentially leads to very small step-sizes even in regions for which gradients are small. \nWould it be possible to improve those bounds, and show that the gradients actually decrease along the trajectories (e.g., in the strongly convex setting), in order to allow for increasingly large step-sizes? If so, what would the decrease rate be?\n\n2) How do results in the paper compare with simple clipped (S)GD with clipping threshold set to the gradient norm at $x_0$ (basically, enforce boundedness instead of showing it) ? Convergence rates seem equivalent but additional terms seem different in each case. Could you clarify that?  \n\n\n", "limitations": "The authors have addressed the limitations of their work adequately. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Shows convergence of GD, NAG and SGD for relaxed smoothness conditions, which were not known without gradient clipping. This allows to prove convergence of GD for general classes of functions. \n- Show boundedness of the gradients along trajectories under relaxed smoothness conditions. This is a nice-to-have technical result, especially for NAG. ", "weaknesses": "- Fixed step-size rates seem quite pessimistic in this case, since step-sizes all along the trajectory depend on the initial bound on smoothness, which might be very large.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments! We will try to address the concerns and questions below.\n\n1. Regarding the stepsize, we agree that using an adaptive stepsize (e.g. gradient clipping technique, which essentially uses a larger step size when gradients are small) may accelerate convergence. However, only constant-factor acceleration is possible because the convergence rates in our paper are already optimal up to constant factors. This may matter in practice but is not important for theoretical analysis. Actually, our analysis should directly apply to most methods with an adaptive stepsize, at least in the deterministic setting. We consider using a constant stepsize for the following reasons:\n- There are already a lot of papers studying methods with an adaptive stepsize for $(L_0,L_1)$-smooth functions. We are the first to study the classical methods with a constant stepsize and our results show that adaptivity is not necessary for generalized smooth functions.\n- In the stochastic setting, using a constant step size allows the relaxation of the noise assumption from the assumption of bounded noise in existing papers to that of bounded variance in our paper.\n- For NAG, using adaptive stepsize may lead to a very sophisticated algorithm, which is hard to implement.\n\n2. We believe that the simple clipped (S)GD with clipping threshold set to the gradient norm at $x_0$ should also converge with the same rate to constant-stepsize (S)GD, up to constant factors. We believe the convergence can be shown using our analysis. In the convex setting, they are actually equivalent since the gradient norm is non-increasing by Lemma 4.1. In the non-convex setting, it is hard and not very important to theoretically compare different constant factors in their convergence speeds, since we have to also obtain very precise complexity lower bounds for them. \n"}, {"review_id": "Fb0jpQx2y4", "reviewer": "Reviewer_YkEg", "summary": "This submission claims to relax the Lipschitz assumption on the gradient of the objective function in nonconvex optimisation, and obtains convergence bounds similar to textbook convergence results.", "questions": "In equation (5), why is there a $-1$ in the definition of $S_{\\textrm{rect}}$?", "limitations": "As there is no novel discovery in this submission, the limitation discussion is not applicable.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The presentation of the material is clear and the narrative flows well.", "weaknesses": "The result presented in this manuscript is not of importance. When we take the gradient information about the initialisation point into consideration, we can correspondingly restrict the feasibility set to the neighbourhood around the initialisation point, and then the $(r,l)$-smoothness defined in this paper can be replaced by the classical Lipschitz condition.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for the comments. However, we do NOT think there is any simple way to restrict the feasibility set to the neighborhood around the initialization point based on gradient information around the initialization, as claimed by the reviewer. \n\nIn particular, we want to clarify the following points regarding the challenges of restricting the feasibility set to some neighobood:\n- First, stationary points may be very far away from the initialization. For example, consider the function $f=\\exp(-x)$ with domain $\\mathbb{R}$, whose stationary point is at infinity. If you restrict the feasible set within a neighborhood of initialization, you will only converge to a sub-optimal point, which makes no sense. \n- For another example, consider the function $f(x)=1/x+1/(1-x)$ with domain $(0,1)$. Suppose the initialization is close to $0$, it is hard to make sure the neighborhood contains the optimal point at $1/2$ and does not go outside of the domain, given that the initialization point is closer to the boundary than the optimal point. Although it might be possible to find such a neighborhood for this simple convex and one-dimensional example (e.g. by cheating), we believe it is hard for a non-convex and high-dimensional function. \n- We also want to point out that the boundary of the domain could be non-convex and not known to the algorithm, which makes things even harder. So you may end up getting a non-convex neighborhood in order to contain stationary points, which does not really reduce the problem to the classical smoothness condition, since classical analysis requires a convex feasible set.\n\nBased on the discussions above, we respectfully disagree with the reviewers' suggestion that our results are not novel or important.  \n\nRegarding the question on equation (5), the $-1$ is there because we do not include the two end points $\\tau$ and $\\tau_{1/2}$ when defining $S_{\\text{rect}}$, in other words, $S_{\\text{rect}}:=\\sum_{\\tau_{1/2}<t<\\tau} (G/2)^2=(G/2)^2(\\tau-\\tau_{1/2}-1)$\n"}]

Author rebuttal:

Meta-review: Overview: Relaxed smoothness conditions have been introduced to study the gradient clipping algorithm, and show that clipping in particular allows fixed step-size convergence without smoothness under this relaxed assumption. This paper further generalizes the relaxed smoothness notion used for clipping by bounding the Hessian by any non-decreasing function of the gradient norm.

Then, fixed step-size convergence is shown under the relaxed smoothness assumption in a variety of settings. The key technical part is to show that assuming a large enough initial bound on the gradients and relaxed smoothness, the gradients remain bounded throughout the trajectory regardless of the setting (convex, strongly convex, non-convex, and even stochastic with some necessary caveats). Then, boundedness of the gradients along the trajectory implies the regular smoothness condition, and thus standard analyses can be used to show convergence of gradient descent.

Pros:

- Instead of listing, the positive points are mostly within all the reviews included in the reviewing process. Interesting Problem Setting, Theoretical results, Thorough literature review, Interesting results.

Cons: 

- Not many to be honest. 

Overall: Based on the initial reviews + discussion with the authors, the paper has only positive comments, and all the comments raised by the reviewers were adequately tackled by the authors.

The only requirement for the authors is to include (if possible and if space allows) any additional discussion that is useful during the rebuttal phase, in order to improve the paper. Please do not include material that is not presented during the rebuttal and material that cannot be checked, unless another round of review is required.
Decision: Accept (spotlight)