Gradient Descent Is Optimal Under Lower Restricted Secant Inequality And Upper Error Bound
Authors: Charles Guille-Escuret
Adam Ibrahim
Baptiste Goujaud
Ioannis Mitliagkas
Venue: NeurIPS 2022 Accept (2022)
Keywords: First-Order Optimization
Non-Convex
Deterministic
Gradient Descent
Restricted Secant Inequality
Error Bounds

Abstract: The study of first-order optimization is sensitive to the assumptions made on the objective functions.
These assumptions induce complexity classes which play a key role in worst-case analysis, including
the fundamental concept of algorithm optimality. Recent work argues that strong convexity and
smoothness—popular assumptions in literature—lead to a pathological definition of the condition
number. Motivated by this result, we focus on the class of functions
satisfying a lower restricted secant inequality and an upper error bound. On top of being robust to
the aforementioned pathological behavior and including some non-convex functions, this pair of
conditions displays interesting geometrical properties. In particular, the necessary and sufficient
conditions to interpolate a set of points and their gradients within the class can be separated into
simple conditions on each sampled gradient. This allows the performance estimation problem (PEP)
 to be solved analytically, leading to a lower bound
on the convergence rate that proves gradient descent to be exactly optimal on this class of functions
among all first-order algorithms.

Gradient Descent Is Optimal Under Lower Restricted Secant Inequality And Upper Error Bound
Charles Guille-Escuret Mila, Université de Montréal guillech@mila. quebec
Adam Ibrahim
Mila, Université de Montréal adam. ibrahimemi quebec
Baptiste Goujaud
Ioannis Mitliagkas
Ecole Polytechnique
Mila, Université de Montréal,
wrw.:isse..oujuuddegneo com com
Canada CIFAR Al chair ioannis @mi quebec
Abstract
The study of first-order optimization is sensitive to the assumptions made on the objective functions. These assumptions induce complexity classes which play a key role in worst-case analysis, including the fundamental concept of algorithm optimality. Recent work argues that strong convexity and smoothness- assumptions in literature- to a pathological definition of the condition number Motivated by this result, we focus on the class of functions satisfying a lower restricted secant inequality and an upper eгror bound. On top of being robust to the aforementioned pathological behavior and including some non-convex functions, this pair of conditions displays interesting geometrical properties. In particular, the necessary and sufficient conditions to interpolate their gradients within the class can be separated into simple conditions on each sampled gradient. This allows the performance estimation problem (PEP, [3] to be solved analytically, leading to lower bound on the convergence rate that proves gradient descent to be exactly optimal on this class of functions among all first-order algorithms.
[12]
points and
Introduction
The typical framework to study convergence properties of first-order algorithms in the context of machine learning is to first establish class of objective functions optimize through assumptions usually bound to a constant, such as T-ssmoothness and ju-strong convexity. tuning prescription of an algorithm then made based on the constants, (e.g. step size μ+ descent method on smooth and strongly convex functions), and finally a worst-case convergence rate can be derived for this algorithm when using this tuning prescription. In some cases, lower bound on the achievable worst-case convergence rate can also be derived, leading to the theoretical optimality of an algorithm on the considered class of function, for instance the Nesterov accelerated gradient method is known to be optimal up constant on strongly convex and smooth functions.
2
in the case of the gradient
However in 12. the authors establish that such framework and its derived results are very sensitive the choice of assumptions, and that strong convexity and smoothness can exhibit pathological behaviors leading to conservative tuning and arbitrarily sub-optimal convergence rates, even when the resulting algorithm achieves theoretical worst-case optimality on this class of functions. Furthermore, they propose a set of more robust alternative conditions. In this work, we focus on specific pair of such alternative conditions lower restricted secant inequality (RSI") and upper error bounds (EB (EB+). Our main contribution is to show that the gradient descent (GD) method with certain tuning
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

is exactly optimal on the classes of objective functions induced by these conditions, confirming that optimality results are highly sensitive the choice of conditions. Another consequence that no algorithm can accelerate on this class of functions, implying that additional assumptions are required to explain the practical efficiency of accelerated methods.
Notation Let F the set of differentiable functions from R to R that admit a convex set of global minima x. We focus on the problem optimizing a function f E F, i.e. finding x E j,. For any E RR we denote z² the orthogonal projection of x on Xy- By abuse of notation, when the context is not ambiguous, we will simply denote z'} as z².
We call gradient descent (GD) the standard optimization algorithm based on the following update, where a is the step size:
I++1 = x - fV.))
We call first-order algorithm all A that consider past iterates, function values and gradients and output a next iterate. Formally, A can be seen as sequence of functions {AA,. n E Nj such that for any 12d"=t with values in Idd. Under that formalism,
N. An is function defined on (IZd x R n+1 applying A to optimize an objective function f starting in zgg E I generates sequence of iterates (xn);; such that vi, 11+1 A (z), fazy) fz2))) get) Note that do not require the iterates of A to lic within the span of observed gradients as it is often the case in the literature.
Outline Section introduces RSI and EB+ and provides some basic properties and motivation. Section 3 discusses related works in the literature. Section defines and establishes the necessary and suffccintt interpolation conditions for RSI and EB+, which is key element of our analysis. Section proves the lower bound on the convergence rate of first-order algorithms under RST and EB + and finally Section concludes our work. Detailed proofs are provided in the appendix.
2 Lower restricted secant inequality and upper error bounds
We now define RSI and EB+ and discuss some basic properties.
Definition 2.1 (Lower restricted secant inequality) Let f E F and p >
f e RSI (w) + Va Rd, (Vf(z) x- x-- x²) > 2 μ -
Intuitively. RST (14) enforces that the further x is from Xý. the stronger the gradient of f in x must be the opposite direction of Xy.
Remark 2.2 RSI (μ) includes non-conved cun-coooxuuunciooss However, it prevents flat landscapes outside of X; and requires f to increase least quadratically with the distance to Xÿ, as established in 12
f e RSI (x) Vr TR.d f(x) - 5
p 11 x²112
Definition 2.3 (Upper Error Bounds) Let f E F and L >0
E (B) + Vo E Rd || (x)(())) ll < L | - x x=112
EB+(L) thus enforces that the gradient of f is controlled by the distance Xj.
Remark 2.4 L-smoothness implies EB+ + (L) and p-strong convexity implies RSI (p). However, one must be careful before claiming that RSI and EB are respectively weaker than strong convexity and smoothness: ffor μo > PA,, RSI (No) is neither stronger or weaker than pi-strong convexity, for Lo L1. EB (Lo) is neither stronger or weaker than Li-smoothness.
RSI
Therefore, even when the objective function is smooth and strongly convex, considering convergence results under RSI and EB+ is relevant, we might obtain better constants and L. Many

---

convergence results depend of the condition number k = L. Better constants leads to a better condition number, and thus a potentially better convergence rate (including when the dependence in the condition number и: is the same or worse). As consequence, machine learning problems with strongly convex and smooth objective functions are all potential applications of results under RSI and EB* provided we can obtain better constants under these conditions.
Prop 1 (convergence rate of GD under RST and EB+) Let f E (1) (L). Then gradient descent with learning rate E f will guarantee the following convergence rate:
12)) L2
11., 11 -
|00
2il12
(1)
Moreover, when the learning rate is set to Org = 1. on the first step, and a = L on every other step, gradient descent guarantees the following convergence rate:
24
[V[(z))]
122 i-1
||.; x1112 5
(2)
4112
T,2
Proof.
When a = 23. we have
[1411 - 2 1/ < |, 27,12
|| av [x(()))) - =1:12 1
| xłl1:- 2a (Vf(z;)
-;11 + |
(3)
(1 20p LLaa2) ||
2
T,2 ||=; 211122-
which proves
[ To prove
simply note that when using 1
2n we have:
|||
x 112
xū
2a (V)
20 - 2g) a +
<
1 -
1 (VI(z0) x
4n2
(4)
"
[V)(2))
4μ²
Interestingly, RSI and EB+ are direct bounds on the additional terms obtained by developing ||z; - fz,) - 2 1| leading to an extremely simple proof. On the intuitive level, RSI lower bounds the gain from stepping in the direction of Xj, while EB+ upper bounds the error coming from the component of the gradient orthogonal to that direction.
Remark 2.5
The literature gives a worst case convergence rate of gradient descent on j-sttroggyy zillz using the step size 128 30/. While this rate is better for fixed μ and L, we again emphasize that the #tL
convex and L-smooth functions of ||,,- - 112 < (1-
L+L) (1)
2q I|ze
constants p. and may be very different depending on the chosen conditions, and thus these two rates can not directly be compared.
we empirically verify in Appendix A that the optimization path of ResNet18 [T6 trained for classification on CIFAR10 10 (20] verifies the interpolation conditions of RSI 0 EB+ which are introduced in Section 4 This result guarantees the existence of a function in RSI 0 EB which exactly interpolates the observed gradients, and thus all convergence guarantees of RSI n EB+ naturally apply this practical deep learning setting. RST- n EB+ therefore provides linear convergence guarantees while being empirically applicable to neural networks (although with respects to local minima), an impressive feat given the highly non-convex nature neural networks loss functions.
Motivation:
3

---

3 Related Work
Throughout the literature, many choices assumptions have been used to study first-order optimiza- tion. Most assumptions fall into one of two categories: lower conditions and upper conditions that respectively take the form a lower and an upper bound on properties of the objective function. For instance, strong convexity lower bounds the curvature of the objective function and is thus lower condition. Similarly, smoothness is an upper condition.
Lower conditions have been the most extensively studied assumptions, such as Polyak-E.ojasiees
29.. -oca--iuuss-ccoveeitt [T5], weak quasi-convexity 14], quadratic growth 22
18 Kurdyka-
Lojasiewicz [21 3) optimal strong convexity [22] 25 weak strong convexity [9
26 error bounds
[24]. Some recent works have explored the relations between these lower conditions [19 38 this work we focus on the restricted secant inequality (RSI)) (which we denote lower restricted secant
inequality to differentiate it from its upper bound equivalent) which was introduced in [3], and has been used (along with its convex extension restricted strong convexity) in many recent theoretical derivations of linear convergence rates [6 31 37].
On the contrary, because most machine learning objective functions are naturally smooth, fewer works have explored alternatives to smoothness. However as discussed in Remark 2.4 is still relevant to study these alternatives on smooth objectives due to potentially better conditioning. The most notable ones in the literature are local smoothness [15] restricted smoothness M. relative smoothness 23 13 40]. weak-smoothunsss [14], expected smoothness (11). In 11), the authors argue that lower conditions can be naturally translated into equivalent upper conditions by changing the lower bound into upper bound, and vice-versa. Subsequently, they introduce set of upper equivalent existing lower conditions, such as upper error bounds EB* + the natural upper equivalent to error bounds from [24) Throughout this work, we focus EB* an upper condition.
Finally, key to our analysis are the necessary and sufficient interpolation conditions RST (n) n EB+ (L) (Section 4 The search of these conditions has been largely motivated by Performance
Estimation Problems (PEP), introduced in 333 and with many recent successful applications 17 6
33 34.
PEP is a framework for computer-assee assisted worst-case convergence analysis, that only requires necessary and sufficient interpolation conditions for the considered class of objective functions. In the case of RSI EB+ however, we found the interpolation conditions to be independent (see Section which made the worst-case analysis directly valle analytically.
Interpolation conditions
In this section we provide and discuss the necessary and sufficient interpolation conditions for RSI EBT. Their importance stems from the framework used in PEP and in this work to analyze worst-case convergence. Given a first-order optimization algorithm A we want to find the slowest convergence rate of A among all f within a class of objective functions C and starting point xo E Rd Xj. That is equivalent solving the following optimization problem any step number n
Ix0 2;1
min ((
| x
(5)
s.t. Vi < n 1, = A ((20, f(zo), ff(x)) ..., (I. f(())))
Directly searching for f in the functional space is generally intractable, however if we can explicitly find the set of all families (æ4, ft.9,); such that 3f C, vi, f gi and f(x) = f. (we say that f interpolates (2,, fi, 9;);), then problem (5) can be reduced to:
|100 Tūlls 211
min (a.d x
I x;,12
(6)
s.t. and
Vi 5 n 10-1,,, 1,4111 A ((os 9o) ,..., (zt, ( fi.
(x,, fr, filgiis GG
In many cases (see Section 3) problem 6 is tractable and becomes a very powerful analysis tool providing lower bounds, upper bounds, and optimal tuning for different types of algorithms and assumptions used. A crucial and difficult component of this analysis is to formulate the interpolation

---

conditions, that is the necessary and sufficient conditions for family (24, fi. 9:); to belong in G. Driven by these motivations, we now establish the interpolation conditions for RSI n NEB"
In Theorem introduce the necessary and sufficient conditions to interpolate family (
without considering the function values (fe);- This theorem could used to find the worst case convergence rate all first-order algorithms that ignore function values. However, in Corollary [ we deduce from Theorem I sufficient (but not necessary) conditions to interpolate a family (æ4, fi 9: These conditions allow in Section 15 find lower bound the worst-case convergence rate for all first-order algorithms (including algorithms that have access to function values information), which we know is tight thanks Prop
Theorem 1 (Interpolation conditions) Let (Ii.9:)isn (R" R separate points.
n+1 such that the I; are
Then, vp, L > 0: Aʃ E RST (14) n (L), s.l. Vi, V/(r;) gi
E C Rd convex, s.t. Vi,
1191l12 S I. 1| - 2ill2 and (gi 1 - 2;) 2 14 11|2; x/112
where x, is the orthogonal projection of x onto X*.
Proof. In order to preserve concision and clarity, we will only present the broad outline of the proof here. For a complete technical proof, see Appendix B
The direct implication is trivial as it is a direct application of RSI (4) and EB* (L) definitions to f in (æ:); For the reverse implication, we will construct function fe,s that interpolates (æi, )- The function fe.8 is a quadratic everywhere except in the spheres of radius e around each e being small enough for these spheres never intersect. Inside the sphere of radius around given x;, fe,9 will be perturbed by adding term X(I x xzllg)h(()) where h is affine in æ, and X is scaling term so that X(e) at the border of the sphere, and X(0)
its center dt.
The key is to find function À that preserves the properties of RSI (μ) and EB+(L), We use
+ cos
π
)e,
(8)
And our construction fe,9 given by:
H+L 4
|| x= x=1
if Vi, || - x xil12 2 6
[2,
L+L
||
x= 11
+ Ne. (1xxr - (1:11);11>) (0r ( u+ (xx 1n--tblo
x;) x x.)
if Bi, || xx 212 < 6
4
(9)
The rest of the proof is to use the Taylor expansions fe,a to show that for sufficiently small and 9, Je, will belong in RSI
RSI((u) (u)) and EB+ (L.) (see Appendix Bh.
5

---

Corollary Let (o,, fi, filgisenn E (Rd R x Rd."" n+1 Then, Vp, L > 0: EX* Rd convex, 8.1. Vi,
such that the 2; are separate points.
110:l12 S L [|= 27ll2
(9: 5i x;) 2 μ || x
(10)
L
fi 4
||,; 25
ff E RSI (M) MO)EE EB (L), s.t. Vi, Vf(x.) = and f(x.) fir
where of is the orthogonal projection of x; onto X
Proof. We simply use the function Se,a from the proof Theorem 1 and note that Vi, (3:a)
L x
x; 11
Theorem and Corollary I are the key elements prove the optimality of gradient descent on RSI and EB among all first-order algorithms (see Section
Remark 4.1 The interpolation conditions in Theorem 7 are independent, in the sense that a family (I (g)) admits an interpolation in RS) EB+ (T.) if and only if each {(x4, 9 admits interpolation in RSI (n4) EB+ (L). Similarly, the sufficient interpolation conditions in Corollary ] are also independent.
This property of independent interpolation conditions drastically simplifies convergence analysis and is the main reason are able to analytically derive lower bound in Section 5 Indeed, given interpolable family (I,, f.: gs ken for given set X it is sufficient to show that (#n+11 fn+1. 9n+11 is interpolable with X prove that the entire family (I,, f 9i)isn+11 can be interpolated. It thus simple to find the set interpolable (fn+1. given X", Iat1, and an interpolable (wi, fes se)
Lower bound on the convergence rate
In this Section we derive lower bound on the convergence rate of first-order algorithms on RSI and EB+ This lower bounds applies under the assumption that the number of steps taken is smaller than the number of dimension d. This assumption is frequent in the literature (c.g. [5] and not constraining for high-dimg high-dimensional optimization. The observed gradients of the worst-case functions for optimal algorithms are typically orthogonal to one another (see (6]) which is not possible when the number of steps becomes larger than the dimension We conjecture that when not bounding the number of steps, it is possible to achieve an asymptotic rate in O (2-å) 3) which would be better than the usual rates obtained for very ill-conditioned functions, while having little to no practical uses due to the bad convergence properties on lower number of steps.
We now introduce Lemma I which is the cornerstone of the proof of Theorem

---

Lemma 1 Let O and I, > Let E tx max (tx, 2u For any first-order optimization algorithm A and starting point E IR, there exists (9t)ssd-2 RR (fi)isd22 IR and Sa-2 Sa-1 S So S R& such that:
Vi S 2, there exists a (d - 1)-dimensional affine space Hi containing S and in which S; is a (d-i- sp-see of radius T4 = V nm aB 11o0ll2 (1 and
center C₁ H4s
Let (xi);; be the iterates generated by A starting from zo and reading gradients (gi); and function values (f()), thenfoor any i S. d-2 2 and any x E S,, there exists a function f in RSI (a) n EB*(L) minimized by {x} that interpolates
Proof. In order to preserve concision and clarity, we will only present the broad outline the proof here. For complete technical proof, see Appendix C
We construct the sequence iteratively. For initialisation, we take any non-zero Io- set fo #+L oo l1g0ll2- Co = Ho aego. and finally
So = (a Rd
(e co go) 0} n (n x
Rd | x
coll2
ag |
Then assuming we have sequence My , Sj)ssi<(-22) respecting the conditions of the Lemma, noting H, the d - ----- dimensional affine space in which S; is (d i 2) dimensional sphere, and 0++1 the (i + 1) iterate returned by A. Let h,41 the orthogonal projection of 2,+1 into H4.
((++1-4) If h4+1 = C. let s E S and v If h4+1 # cr let 1141-011
(8-6r)
We then construct:
C+11 C - riu
L
f411 p+L L
4²
(1 11+1112+
1 )r?
9+41 L | - 2²112 (x1+1 c441)
| c141l12
Hit1 = { x Hi (x c: 11) -
11 r
S = n H441
We verify in Appendix tht this construction respects the properties of Lemma
We can now introduce Theorem 2 which gives us a lower bound on the worst-case convergence rate of any first-order algorithm RSI (n) and EBT (L).

---

Theorem 2 (Lower bound RSI n NEB+) Let A be any first-order algorithm Rd, 0 and L μ. For any To E Rd, there exists Ied and a function f in RSI (1) n EB (B)( minimized by X fx*) such that
11²
Vi S d - 1, 12 - 22,12
11:0
=oll2
(11)
I
Furthermore, 4 2 V2, there exists h in RST (1)
(BB(T))
minimized by X {x*) such
that
[Vh(2e)12
112
i-1
vi -
(12)
4p²
L
where (xi) (resp. (z+)) is the trajectory obtained by applying A (resp. h) starting ro- Note that since X is singleton, Vi, =
Proof. L = μa, then the inequalities are trivial from the positivity of the norm. If L μu, let Let us
(gt, fú, (d) be the sequence introduced in Lemma for og E #. max
f 2n
note that for any x E So. ||z0 - ==I2 collgali 2 (see initialisation in Appendix
i E (1....,d- d 1). S has radius r4-1, thus there exists x² E S such that ||,; x²112 1l 2 Ti-1, and thus:
u² i-1
| x² r²-1
00 ag
1190112 1
(13)
L
When setting (g) # and observing that x² S S So and thus ||x0 xx x=1
aollsol
we obtain If L v2. we set an 2p
1 and
13 immediately yields
12
Remark 5.1 Since the lower bounds established Theorem are exactly matched by the conver- gence guarantees of gradient descent (see Prop these bounds are tight and gradient descent is exactly optimal on RSI (14) n EB* (L). This a concrete example of the sensitivity of theoretical optimality the choice of complexity classes.
5.1 Discussion
The first bound presented in Theorem gives the optimal solution when trying solve
|| 12122
min max A f.m0
(14)
[rg 26112
While the second bound gives the optimal solution when trying to solve
I x 12
min max f.m0
(15)
[V
For general smooth and convex functions, (15) will not have solution (for any A, the quantity will not have worst case upper bound), which is why (14) has historically been the focus of optimization literature. However in practice, when (15) admits a solution, as the case for RSI (f1) n EB (L),
fits practical motivations better than (4) when starting from Zo and observing
initial gradient go. the solution to (15) is the one that will minimize || x;, ll, in the worst case. In comparison, for
fixed [ the solution (1 will be faster when I xill2 small, and slower when -all =oll2 is large, leading to a slower worst-case convergence.
When > V2, using a tuning of og = 2μ convergence of |I x;il22 better by constant 2(12-p2)- While such small constant factor is often considered not impactful, the number of steps required to make up for this constant factor
1 on the first step instead of 12 leads to a worst-case 1a

---

Ceb
CсB
CRSI
CRSI
C AsI
go
(a)
& x
v2
(b) ト =
(c) 4.4 < v2
Figure 1: 2D representations of the possible positions of xx given zp and go. for three possible values of R xx must be in CnsI (red) but not in CEB (green). When f > v2 (left), doing larger step reach the center of CRST will minimize worst-case sub-optimality.
(2) 1, which yields 68 for & 10 and 6930 for & 100, and can thus become substantial ill-conditioned functions.
log 1og
Finally, we propose a geometric interpretation of the threshold /2. Given To and go. RSI (n) requires x" to within the circle of center zu
90 and radius Igoll2
while EB (L) requires x" to
2y
2μ
not be within the circle of center and radius values of L When L > 22 (Figure (a)), 21 to #:00 minimizes x
[gel22 In Figure we show these circles for different
||1-=0|| 1=0--'12 over all possible
x², while 21 =
gu minimizes [1 x= 112. As becomes smaller than v (Figure 1(b) and 2p
I(c)
the same point #1 TD 1. 90 minimizes both quantities.
5.2
PEP experiment
Since we have found necessary and sufficient interpolation conditions in Theorem can use the PEP framework on RSI n EB+ confirm our results and derive the worst-case convergence rate of first-order algorithms. In Figure
2 we show the worst-case linear rate of convergence of Heavy Ball (HB) 22 on RSI (0.1) EB (I.0) for regularly sampled learning rate a and momentum 3 (bright yellow means linear convergence), generated with PEPit [9]. We remind the update rule of HB
Tx+1 In a fz (xx, In-1)
Since gradient descent is special case of HB where 3 0, observe expected that the optimal rate of convergence is achieved for 3 and a = 0.1 = #.. Moreover, Figure 2 shows that momentum does not do well on RSI n EB + but gradient decent benefits from relative robustness the tuning of a we get similar convergence rates for any [0.05, 0.15].
6 Conclusion
Our main result is to prove that for any > O and L 2 gradient descent is exactly optimal on the class of functions RSI ()4) n EB (L. (by exact optimality, mean that the convergence guarantees of GD match the lower bound of worst-case performances exactly, without a constant factor of differencee). This result confirms the observation in [12] that optimality overly sensitive the choice of assumptions, and should thus be considered with a lot of caution.
Interestingly, our analysis also identifies two similar notions of optimality, one of which suggests using a larger step size on the first iteration when the function is not particularly well-conditioned to improve worst-case convergence speed (see section 5.I.
verified empirically that RSTT EB+, with respect to last iterate, are verified on optimization paths of simple deep neural networks (c.f. Appendix A). This suggests that unlike usual alternatives which are known not be verified on the highly non-convex loss landscapes of neural networks, convergence guarantees on RSI- n EB+ realistically apply to deep learning. On the

---

Worst-case convergence rate of Heavy-Ball on RSI(.1) EB(1)
1.00
Linear rate of convergence (smaller is better)
0.8
0.6
0.98
beta
0.96
0.0
0.05
0.10
0.15
0.20
alpha
Figure Worst-case linear convergence rate of heavy ball on RST (S1 EB+ (1) depending of its hyperparameters and B, as calculated by PEP. The best rate is achieved for a = 0.1 and / = 0.
other hand, the impossibility to accelerate the convergence rate on RSI n EB+ implies that these assumptions are insufficient to explain the empirical successes of accelerated methods.
For the scope of this work have focused worst-case convergence analysis. While in practice average-case convergence rates are more insightful than their worst-case counterparts, such results due the necessity of defining reasonable distribution the considered class of functions, which is generally unfeasible. While such distribution on RSI n EEB is equally difficult to define, should be feasible define instead reasonable distribution of the observed gradient for given sampling point x and nearest minima x², c.g. an uniform distribution over the (simple) set of possible gradients. Such approach is conceivable with RSI n EB- only because the interpolation conditions are independent (see remark 4. and thus we can easily make sure that any set of gradients sampled from this distribution can be interpolated within the class. While the distribution will necessarily be arbitrary, we believe such analysis could yield very useful insights and RSI n is rare opportunity follow this approach.
Finally, many alternative conditions have been introduced in the literature (see Section 3p. for which
optimality results are still unknown. The PEP framework a powerful tool study conditions for which we can determine sufficient and necessary interpolation conditions, which would improve our understanding of first-order algorithm properties and tuning on wide variety of objective function classes.
Acknowledgments and Disclosure of Funding
The authors would like thank Leonard Boussioux, for useful discussions and feedback. Ioannis Mitliagkas acknowledges support by an NSERC Discovery grant (RGPIN-2019-06512) Samsung grant and a Canada CIFAR AI chair.
References
[1] A. Agarwal, S. N. Negahban, and M. J. Wainwright. Fast global convergence of gradient methods for high-dimensional statistical recovery. Ann. Statist,, 40(5):2452-244 2482, 2012.
[2] M. Anitescu. Degenerate nonlinear programming with quadratic growth condition. SIAM Journal on Optimization, 10(4):1116-1133 2000.
[3] Bolte, Daniilidis, Ley, and L. Mazet. Characterizations of lojasiewicz inequalities and applications. arXiv:0802.0822 2008.
10

---

[4] J. F. Bonnans and A. D. loffe. Second-order sufficiency and quadratic growth for non isolated minima. PhD thesis, INRIA, 1993.
[5] Bubeck. Convex optimization: Algorithms and complexity, 2015.
[6] Y. Drori and A. B. Taylor. Efficient first-order methods for convex minimization: a con- structive approach. Mathematical Programuming, 133-220, Jun 2019. ISSN 1436-4646. doi: 10. 001000//1100020011911110-22
www.xxooo.ooooo URL ht.ptttp://da.dol..og/0000000000
s10107-01 901-010----11-
[7] Y. Drori and M. Tehoulle. Performance of first-order methods for smooth convex minimization: a novel approach, 2012.
[8] P. Gong and J. Ye. Linear convergence of variance-reduced stochastic gradient without strong convexity. arXiv: 1000 2014.
[9] B. Goujaud, C. Moucer, Glineur, J. Hendrickx, A. Taylor, and A. Dieuleveut. Pepit: computer- assisted worst-case analyses of first-order optimization methods in python, 2022.
[10] R. M. Gower. Convergence theorems for gradient descent. Lecture notes for Statistical Optimization, 2018
[11] R. M. Gower, O. Sebbouh, and N. Loizou. Sgd for structured nonconvex functions: Learning rates, minibatching and interpolation. arXiv:2006. 1031, 2020.
[12] C. Guille-Escuret, M. Girotti, B. Goujand, and Mitliagkas. A study of condition numbers for first-order optimization. In International Conference on Artificial Intelligence and Statistics, pages 1261-1269. PMLR, 2021.
[13] Hanzely, P. Richtarik, and Xiao. Accelerated Bregman proximal gradient methods for relatively smooth convex optimization. Technical Report MSR-TR-2018 1-22, Microsoft, 2018.
[14] M. Hardt, T. Ma, and B. Recht. Gradient descent learns linear dynamical systems. Journal of Machine Learning Research, 19, 2018.
[15] E. Hazan, K. Levy, and S. Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex optimization. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 1594-1602. Curran Associates, Inc., 2015.
[16] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition, 2015. URL https://arxiv. wtt.voorggaabb/.... 03385)
[17] B. Hu and L. Lessard. Dissipativity theory for nesterov's accelerated method, 2017.
[18] A. Ioffe. On sensitivity analysis of nonlinear programs in banach spaces: the approach via composite unconstrained optimization. SIAM Journal on Optimization, 4(1):1-43 1994.
[19] H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal graddennt methods under the polyak--ojasiewiez condition. CoRR, Abs/1608.046666 2016. URLhttp!
//arxiv. wwaxxiv.or//bb... /10.//608.000 04636
[20] A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[21] K. Kurdyka. On gradients of functions definable in o-minimal structures. Annales de I' l'institul Fourier, 48:769-783, 1998.
[22] Liu and Wright, Asynchronous stochastic coordinate descent: Parallelism and conver- gence properties. SIAM J. Optim., 25(1):351-376, 2015.
[23] H. Lu, R. M. Freund, and Y. Nesterov. Relatively-smooth convex optimization by first-order methods, and applications. SIAM J. Optim., (8(1):333-354, 2018
[24] Z.-Q. Luo and Tseng. Error bounds and convergence analysis of feasible descent methods: general approach. Annals of Operations Research, 46(1):157-178, 1993.

---

[25] C. Ma, R. Tappenden, and M. Takâč. Linear convergence of the randomized feasible descent method under the weak strong convexity assumption. Journal of Machine Learning Research, 17(228):1-24 2016.
[26] I. Necoara, Y. Nesterov, and F. Glineur. Linear convergence of first order methods for non- strongly convex optimization, 2016.
[27] Y. Nesterov. A method of solving a convex programming problem with convergence rate O (.a. Soviet Mathematics Doklady, 27:372-376, 1983.
[28] Y. Nesterov. Introductory lectures on convex optimization: A basic course, volume 87, Springer Science & Business Media, 2003.
[29] B. T. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics, 3(4):864 878, -778, 1963.
[30] B. Polyak. Introduction to optimization. optimization software. Inc., Publications Division, New York, 1:32, 1987.
[31] F. Schöpfer. Linear convergence of descent methods for the unconstrained minimization of restricted strongly convex functions. SIAM J. Optim., 26:1883-1911, 2016.
[32] A. B. Taylor. Convex interpolation and performance estimation of first-order methods for convex optimization, 2017.
[33] A. B. Taylor, M. Hendrickx, and F. Glineur. Smooth strongly convex interpolation and exact worst-case performance of first-order methods, 2016.
[34] A. B. Taylor, J. M. Hendrickx, and F. Glineur. Exact worst-case performance of first-order methods for composite convex optimization. SIAM Journal on Optimization, 231111333-111, Jan 2017. ISSN 1095-7189.
doi: 00.137/16m1081000 URL httpt://ax.x.oo//////
1137/16M108100
[35] A. B. Taylor, J. M. Hendrickx, and F. Glineur. Exact worst-case convergence rates of the proximal gradient method for composite convex minimization, 2020.
[36] X. Yi, S. Zhang, T. Yang. K. H. Johansson, and T. Chai. Exponential convergence for distributed smooth optimization under the restricted secant inequality condition, 2019.
[37] K. Yuan, Q. Ling, and W. Yin. On the convergence of decentralized gradient descent. SIAM J. Optim., 26:1835-1854 2016.
[38] H. Zhang. The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth. Optimization Letters, 11(4):817-33, 2017.
[39] H. Zhang and W. Yin. Gradient methods for convex minimization: better rates under weaker conditions. Cam report, UCLA, 2013.
[40] Y. Zhou, Y. Liang, and L. Shen. A simple convergence analysis of bregman proximal gradient algorithm. Computational Optimization and Applications, 73(3):903 912, 2019.
12


Reviews:
[{"review_id": "pLK0SJoZXmk", "reviewer": "Reviewer_tgSv", "summary": "Building on a series of work that explored alternative assumptions to smoothness and strong-convexity, that still lead to linear convergence of gradient descent but hold more generally, the submission presents an analysis of first order methods on a pair of such conditions; the restricted secant inequality lower bound and smoothness towards the optimum as the upper error bound. The results show that the worst-case convergence of gradient descent on the class of functions satisfying those assumptions is optimal, by providing a matching lower bound for first-order methods. The construction of the lower-bound deviates from the typical construction of quadratic functions using in smooth, convex optimization and uses that the restrictions imposed by the conditions are weaker than smoothness and strong-convexity to hide local deviations.", "questions": "The introduction relies heavily on the work of Guille-Escuret et al. ([12] in the manuscript) for the motivation of the investigation of the limits of the conditions studied. Motivations specific to the current submission are somewhat missing, and the conclusions are somewhat at odd with the motivations of Guille-Escuret et al., leaving me with some unaddressed questions. Those are not points against the results of the paper, and I believe it is a matter of editing to make the motivations clearer and can be addressed during a discussion period.\n\n- Why focus on the specific conditions in this paper, among the many possible combinations of conditions, even if restricted only to the ones discussed by Guille-Escuret et al.? Have other stronger (in the sense that they would imply the studied condition, up to a change of constants) conditions already been studied?\n- One of the motivations of Guille-Escuret et al. for the study of those conditions was to address the current limitations of the theory for accelerated methods, as in Polyak's Heavy Ball, where the parameter setting used for quadratics does not extend to smooth, strongly-convex functions. The result that Gradient Descent is optimal for this class of problem would suggest that the class considered is too large to be useful for the design of new methods, or contains pathological functions. For example, the construction given for the interpolation, while interesting, indicates that the function has arbitrary many local deviations that are unrelated to each other, leading to the question of whether this relaxation of smoothness/strong-convexity is a valid model to pursue?\n\n**Applicability of the assumptions**\n\nSome of the limitations of the work are in regard with the level of applicability of the results. The submission makes the point multiple time that, although the assumptions considered are implied by standard smoothness and strong-convexity assumptions, they are not strictly weaker as their condition number can improve.\nThus the improvement in the rates might be worth the degradation in the dependence on the new condition number, \"provided we can obtain better constants under these conditions\" (L65). This is reiterated in Remark 2.5. While I am sympathetic to this argument---for example, for least-squares, it is known that the strong-convexity constant can be 0 the Polyak-Lojasiewicz condition is always non-zero---the arguments of the paper would be strengthened by a simple, provable example of the gap between pairs of conditions on a problem of interest. Using the notation of Guille-Escuret et al. ([12]), on what problem do we see a benefit from using `(RSI-, EB+)` instead of smoothness/strong-convexity, that is not already captured by `(PL+, *SC-)`?\n\nI acknowledge that the submission also discuss the applicability of the conditions to fitting neural networks (L80-82). However, I would recommend adding a qualifier after \"an impressive feat given the highly non-convex nature of neural networks loss function\" (L82) to avoid overstating their applicability, similar to the qualifying paragraph found in Appendix A after L420.\n", "limitations": "No concern beyond the lack of a clear-cut use-case for the applicability of the assumptions used here noted above.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "To my knowledge, the results presented are new and the proof technique used to obtain the lower bound is technically interesting. The overall presentation of the technical results are reasonably clear. My main concern is on the clarity of the motivations, which I expand on in the next section. Regarding significance, althought not explicitly connected to this line of research in the submission, the results are interesting for the study of the possibility of acceleration under looser conditions than smooth/strong-convex which have attracted attention for applications in ML and explaining the effectiveness of momentum-based methods. This study shows the limitations of some relaxations of smoothness and strong-convexity, showing that acceleration beyond gradient descent is not provable without additional structure.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "gaoiJDhiueY", "reviewer": "Reviewer_nnuj", "summary": "This paper is a theoretical paper that studies the performance guarantees for gradient descent where the objective satisfies lower restricted secant inequality (weaker than the strong-convexity condition) and an upper error bound (weaker than the smoothness condition) so that this includes some non-convex objectives. The paper also proves that the gradient descent is optimal on this class of functions among all first-order algorithms.", "questions": "(1) In addition to the questions I mentioned above, one interesting thing I find is that the author(s) show that the gradient descent is optimal on this class of functions among all first-order algorithms. For $\\mu$-strongly convex and $L$-smooth objectives, it is known that Nesterov's accelerated gradient descent and heavy ball method can accelerate. So for your class of functions, the gradient descent is already optimal? What is the intuition behind this? Since your class of functions also include non-convex functions, does this indicate that when you have non-convex objectives, gradient descent might outperform Nesterov's accelerated gradient descent or other momentum-based methods?\n\n(2) In equation (9), write ''if'' in the text environment.\n\n(3) In Corollary 1, in the last line, write ''where'' instead of ''Where'' and add a '','' in the equation before the last sentence. Same can be said about Theorem 1.\n\n(4) In the first line in Theorem 2, it should be ''Let $\\mathcal{A}$ be''.\n\n(5) In the second line in the proof of Theorem 2, write ''be the sequence introduced in Lemma 1''.\n\n(6) In reference [17], nesterov should be Nesterov and please check the other references as well. ", "limitations": "It does not seem to me that the author(s) stated the limitations and potential negative societal impacts of their work. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and is a solid theoretical paper. It is remarkable that the authors can show rigorously that the gradient descent is optimal on the class of functions that satisfy a lower restricted secant inequality and among an upper error bound all first-order algorithms.\n\nThe weakness of the paper is that even though the paper has a nice theoretical contribution, its practical importance and relevance is less clear to me. The class of objective functions that the author(s) study includes some non-convex functions, but when you have gradient descent, depending on the initialization, the algorithm can easily get stuck at a bad local minimum. Then the optimality discussed in the paper might be restrictive. Also for example, in practice, how do you measure your $\\mu$ and $L$? In addition, the optimal stepsize for this class of objective functions is $\\alpha=\\mu/L^{2}$, which is smaller than the standard choice $\\alpha=2/(\\mu+L)$ for the $\\mu$-strongly convex and $L$-smooth objective. I am wondering what is the intuition behind this because $\\mu$-strong convexity and $L$-smoothness can be viewed as a special case under your assumption. What is the intuition that you need to choose smaller stepsize in your setup?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OsbAuxxUli", "reviewer": "Reviewer_Z4HC", "summary": "This paper studied the complexity of gradient descent (GD) in RSI- and EB+ settings, which is more general than the common smooth and strongly convex case. The paper provided linear convergence results of GD in this case, and further derived the interpolation conditions and showed the optimality results of GD under this case based on the PEP framework.", "questions": "Basically I only have some minor questions:\n\n1. You mentioned the optimal set $X^*$ should be convex, which means that the set $X^*$ is connected, right? I have the question because in Appendix A you tried to empirically shows that NN enjoys RSI- & EB+ style trajectory. But the landscape of NN may be complicated, and possibly attains disjoint (or nonconvex) optimal set. So I am confused on the statement \"and therefore, the convergence guarantees of RSI− & EB+ naturally apply to the optimization of neural networks in this setting.\"\n\n2. The independence of interpolation conditions look interesting. Following A. B. Taylor's thesis [32], it seems that the interpolation conditions for both strongly-convex smooth and nonconvex smooth are not independent (am I correct?). As a (kind of) \"intermediate\" setting, the RSI- & EB+ settings will enjoy the independence, which is a little counterintuitive to me. Is there any possible illustration, e.g., analysis technique? It may be better if authors can provide some discussion on the analysis compared to existing literature.\n\nSome minor points:\n\n1. Sec 5.2, I may suggest that authors should present the formal definition of HB algorithm, here the $\\beta$ should distinguish with that of $f_{\\epsilon, \\beta}$\n2. Corllary 1, change $\\wedge$ to $\\cap$?\n3. Appendix A, why do you use \"extrapolate\" here, any difference compared to \"interpolate\"?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The conciseness of the results, also the analysis covers both upper and lower bound, which is a complete story.\n2. The paper is well organized and easy to read.\n3. The independence of the interpolation conditions is interesting.\n\nWeakness:\n1. The assumptions may be still a little restrictive (to be a little picky)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "K0fzof4xB8O", "reviewer": "Reviewer_gSLD", "summary": "In this work, the authors considered applying the gradient descent algorithm to functions in the intersection of RSI- and EB+. The intersection set is a generalization of the set of strongly convex and differentiable functions. A matching lower/upper bounds on the convergence rate is derived.", "questions": "Major:\n(1) Line 78: since the stochastic gradient descent (SGD) method is considered for the optimization of neural networks, I wonder if the probability of escaping the attraction basin of local minima is sufficiently small. If the escaping probability is non-neglectable, the linear convergence may fail with certain probability and it is unsuitable to claim that RSI- and EB+ provide a guarantee on the linear convergence of SGD.\n\n(2) In Thm.1 and Thm.2, the optimality gap is characterized by x_i - x_i^* and x_i - x^*. It would be better if the authors can provide a comparison between these two metrics, which is important to the tightness of lower/upper bounds.\n\n(3) In the proof of Thm.2, it would be better to explicitly show why {x_i} are different points.\n\n(3) Maybe I missed something, but I think functions in the intersection of RSI- and EB+ also satisfy the Polyak-Łojasiewicz (PL) condition. Under the PL condition, it is already known that descent algorithms with a (small) constant \"step size\" are optimal and converge linearly. Hence, the advantage of the bounds in this work lie in a matching lower/upper bound without a constant factor of difference, which seems marginal. I would suggest the authors provide a more detailed comparison with existing results on PL functions.\n\n(4) In this experiments, the authors showed that the gradient descent method is better than the heavy-ball method. I wonder if this phenomenon is also observed on other functions in RSI- and EB+, or only appears on this special example. It would be better if more details of this experiments can be provided (e.g., which objective function is constructed).\n\n\nMinor: \n(1) Ln.20: it would be better to mention that alpha is the step size.\n\n(2) Remark 2.2: I wonder if the authors can provide an example of non-convex functions that satisfy RSI-.\n\n(3) Remark 2.4: the discussion after the first sentence seems unnecessary to me. When comparing RSI- and EB+ to other conditions, people usually assume that the same parameters (mu and L) are used. But I am okay if the authors want to keep this discussion.\n\n(4) Ln.86: I think the Kurdyka-Łojasiewicz and the Polyak-Łojasiewicz conditions do not \"take the form of a lower and an upper bound on properties of the objective function\", since the gradient and the optimality gap appear on both sides of the inequality. If I am correct, it would be better to revise the statement on Ln.86.\n\n(5) Ln.224: should \"learning rates\" be \"convergence rates\"?", "limitations": "See my comments in the \"questions\" section.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In this work, the authors extended the results of classical convex optimization and showed that the gradient descent algorithm is optimal for functions in RSI- and EB+. I think the results are interesting to audiences in optimization and machine learning. Furthermore, the presentation of this paper is clear and easy to follow.\n\nMy major concern is on the importance of the contribution in this work. As the authors mentioned, there are lots of existing literature studying lower/upper conditions. Many of those conditions can also guarantee the linear convergence of gradient-based algorithms; also see my comments in the \"questions\" section. Hence, I am not sure if the contributions in this work are significant and would suggest the authors provide more discussions on the importance of the results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept