On the Lower Bound of Minimizing Polyak-Łojasiewicz functions
Authors: Pengyun Yue
Cong Fang
Zhouchen Lin
Venue: Submitted to ICLR 2023 (2023)
Keywords: Polyak-Łojasiewicz Condition
First-order Algorithms
Lower Bound
Complexity

Abstract: Polyak-Łojasiewicz (PL) [Polyak, 1963] condition is a weaker condition than the strong convexity but suffices to ensure a global convergence for the Gradient Descent algorithm. In this paper, we study the lower bound of algorithms using first-order oracles to find an approximate optimal solution. We show that any first-order algorithm requires at least $\Omega\left((L/\mu)^{1-\alpha} \right)$ gradient costs to find an $\epsilon$-approximate optimal solution for a general $L$-smooth function that has an $\mu$-PL constant for any $\alpha>0$. This result demonstrates the near optimality of the Gradient Descent algorithm to minimize smooth PL functions in the sense that there exists a ``hard'' PL function such that no first-order algorithm can be faster by a polynomial order. In contrast, it is well-known that the momentum technique, e.g. [Nesterov, 2003, chap. 2] can provably accelerate Gradient Descent to $O\left(\sqrt{L/\hat{\mu}}\log\frac{1}{\epsilon}\right)$ gradient costs for functions that are $L$-smooth and $\hat{\mu}$-strongly convex. Therefore, our result distinguishes the hardness of minimizing a smooth PL function and a smooth strongly convex function as the complexity of the former cannot be improved by any polynomial order in general. 

Under review as a conference paper at ICLR 2023
ON THE LOWER BOUND OF MINIMIZING POLYAK- LOJASIEWICZ FUNCTIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Polyak-Lojasiewicz (PL) (Polyak) 1963) condition is a weaker condition than the strong convexity but suffices to ensure global convergence for the Gradient De- scent algorithm. In this paper, we study the lower bound of algorithms using first-order oracles find an approximate optimal solution. We show that any first-order algorithm requires at least Ω (+ log ? gradient costs to find an e- approximate optimal solution for a general L-smooth function that has an μ-PL constant. This result demonstrates the optimality of the Gradient Descent algo- rithm to minimize smooth PL functions in the sense that there exists a "hard" PL function such that first-order algorithm when ignoring a numerical constant. In contrast, it is well-known that the mo- mentum technique, e.g. (Nesterov 2003 chap. 2) can provably accelerate Gradi-
be faster than Gradient Descent
ent Descent O (v log /ogg gradient costs for functions that T-smooth and ji-strongly convex. Therefore, our result distinguishes the hardness of minimizing smooth PL function and smooth strongly convex function as the complexity of the former cannot be improved by any polynomial order in general.
INTRODUCTION
We consider the problem
min f(x), XER
(1)
where the function f is T-smooth and satisfies the Polyak--.ojasewviez condition. function f said to satisfy the Polyak-Lojasiewiez condition if (2 holds for some μ >> O:
|V 2μ (f(x)
inf S(x)) Vx E Rd. YERd
We refer to ( as the p-PL condition and simply denote inf f(y) by f³. The PL condition may be originally introduced by Polyak (Polyak) 1963) and łojasiewicz (Lojasiewicz) 1963) in- dependently. The condition strictly weaker than strong convexity as one can show that any ji-ttrongly convex function which by definition satisfies:
P ||x - y11²
f(x) 2 f(y) + (Vf(y), x - y)
also p-PL by minimizing both sides with respect to x (Karimi al. 2016). However, the PL condition does not even imply convexity. From geometric view, the PI. condition suggests that the sum of the squares the gradient dominates the optimal function value gap, which implies that any local stationary point is global minimizer. Because it is relatively casy to obtain approximate local stationary point by first-order algorithms, the PL condition serves as an ideal and weaker alternative to strong convexity.
In machine learning. the PL condition has received wide attention recently. Lots of models are found to satisfy this condition under different regimes. Examples include, but not limited to, matrix decomposition and linear neural networks under specific initialization (Hardt & Ma 2016 Li et al. 2018), nonlinear neural networks in the so-called neural tangent kernel regime (Liu al.

---

Under review as a conference paper at ICLR 2023
2022).
reinforcement learning with linear quadratic regulator (Fazel et al. 2018). Compared with strong convexity, the PL condition much easier to hold since the reference point in the latter only is minimum point such that x" argminy f(y), instead of any y in the domain.
Turiing to the theoretic side, it is known (Karimi et al. 2016) that the standard Gradient Descent algorithm admits linear converge to minimize L-smooth and μ-PL function. To be specific, in order to find an e-approximate optimal solution & such that f(x) f I c, Gradient Decent needs O 4 log 2) gradient computations. However, it is still not clear whether there exist algo- rithms that can achieve a provably faster convergence rate. In the optimization community, it is perhaps well-known that the momentum technique, e.g. Nesterov (2003) chap. 2), can provably ac- celerate Gradient Descent from 0 log !) to O / log for functions that are L-smooth and ji-strongly convex. Even though some works (J Reddi et al. 2016 Lei et al. 2017) have considered accelerations under different settings, probably faster convergence of first-order algorithms for PL functions is still not obtained up to now.
In this paper, we study the first-order complexities minimize generic smooth PL function and ask the question:
"Is the Gradient Decent algorithum (nearly) optimal or can we design a much faster algorithm?"
We answer the question in the language of min-max lower bound complexity for minimizing the L- smooth and μtPL function class. We analyze the worst complexity of minimizing any function that belongs to the class using first-order algorithms. Excitingly, we construct a hard instance function showing that any first-order algorithm requires at least + log gradient costs to find an s- approximate optimal solution. This answers the aforementioned question in explicit way: the Gradient Descent algorithm is already optimal in the sense that no first-order algorithm can achieve a provably faster convergence rate in general ignoring numerical constant. For the first time, we distinguish the hardness of minimizing a PL function and strongly convex function in terms of first- order complexities, as the momentum technique for smooth and strongly convex functions provably accelerates Gradient Descent by certain polynomial order.
It worth mentioning that the optimization problem under our consideration is high-dimensie and the goal is to obtain the complexity bounds that do not have an explicit dependency on the dimension.
Our technique to establish the lower bound follows from the previous lower bounds in convex Nes- terov 2003) and non-convex optimization (Carmon et al.) (02T). The main idea to construct so-called "zero-chain" function ensuring that any first-order algorithm per-iteratively can only solve one coordinate of the optimization variable. Then for "zero-chain" function that has sufficiently high dimension, some number of entries will never reach their optimal values after the exccution of
any first-order algorithm in certain iterations. To obtain the desired 52 L log )) lower bound, we propose a "zero-chain" function similar Carmon al. (2020), which is composed of the worst con- vex function designed by Nesterov (2003) and a separable function in the form as a Σ.= (x,) or Ein Uy, (x;) to destroy the convexity. Different from their separable function, the one that we introduce has a large Lipshictz constant. This property helps us to estimate the PL constant in a convenient way. This new idea gives new insights into the constructions and analyses of instance functions, which might be potentially generalized to establish the lower bounds for other non-convex problems.
NOTATION
We use bold letters, such as x, to denote vectors in the Euclidean space Rd, and bold capital letters, such A, to denote matrices. L, denotes the identity matrix of size d x d. We omit the subscript and simply denote I as the identity matrix when the dimension is clear from context. For x E Rd, we use x, to denote its ith coordinate. We use supp(x) to denote the subscripts of non-zero entries
of x, i.c. supp(x) = {i: X, * 0}. We use span (x(1) ..... .x(")) to denote the linear subspace spanned by x(")... x((), i.. {y y = (9) a, E RJ. We call a function f L-smooth Vf is T.-Lipschitz continuous, i.e. [V((x) V S L|Ix yll- We denote f inf infx fxx..
2

---

Under review as a conference paper at ICLR 2023
We let x" be any minimizer of f, i.e.. x" argmin f. We always assume the existence x'. We say that x is an E-approximate optimal point of f when f(x) f S..
RELATED WORK
Lower Bounds There has been a line of research concerning the lower bounds of algorithms on cer- tain function classes. To the best of our knowledge, (Nemirovskij & Yudin (983) defines the oracle model measure the complexity of algorithms, and most existing research lower bounds follow this formulation of complexity. For convex functions and first-order oracles, the lower bound is studied in Nesterov 2003), where well-known optimal lower bound (s= $) and ((x !) are ob- tained. For convex functions and nth-order oracles, lower bounds f (a BHTT have been proposed in Arjevani et al. (2019b). When the function is non-convex, it is generally NP-hard to find its global minima, to test whether point is a local minimum or saddle point (Murty & Kabadi 1985). Instead of finding e-approximate optimal points, an alternative measure is finding E-stationary points where [x)]l I E. Sometimes, additional constraints on the Hessian matrices of second-order stationary points are needed. Results this kind include Carmon et al. (2020) 202T); Fang et al. 2018); Zhou & Gu (20T9); [Arjevani al. (2019a] 2020 Thougg PI. function may be convex, it is tractable to find an e-approximate optimal point, as local minima of a PI. function must be global minima. In this paper, we give the lower complexity bound for finding e-approximate
optimal points.
PL Condition The PL condition was introduced by Polyak (Polyak) 1963) and Lojasiewicz (Lo- jasiewicz, 1963) independently. Besides the PL condition, there are other relaxations of the strong convexity, including error bounds (Luo & Tseng/ 1993), essential strong convexity (Liu al. 2014)). weak strong convexity (Necoara et al. 2019). restricted secant inequality (Zhang & Yin 2013). and quadratic growth (Anitescul 2000). Karimi al. (016)) discussed the relationships between these conditions. All these relaxations implies the PI. condition except for the quadratic growth, which implies that the PL condition is quite general. There are many other papers that study designing prac- tical algorithms to optimize PL objective function under different scenarios, for example, [Bssily et al. (2018); Nouiched et al. 2019); Hardt & Ma 2016);
Fazel et al. (2018) Reddi et al. (2016);
Lei et al. (2017).
3
PRELIMINARIES
3.1 UPPER BOUND ON PL FUNCTIONS
Although the PL condition is a weaker condition than strong convexity, it guarantees linear conver- gence for Gradient Descent. The result be found in PPlyyk (1963) and Karimi et al. (2016). We present here for completeness.
Theorem 1. If f is L-smooth and satisfies p-PL condition, then the Gradient Descent algorithm with constant step-size
(k+1) x - ((x(1))
1
has linear convergence rate. We huve:
f(x(*)) - (1- (1 (f(x!0) ))).
(4)
Theorem shows that the Gradient Descent algorithm finds the e-approximate optimal point of f O 4 log log gradient computations. This gives an upper complexity bound for first-order algo- rithms. However, it remains open whether there are faster algorithms for smooth PL functions. We will establish a lower complexity bound on first-order algorithms, which nearly matches the upper bound.
3

---

Under review as a conference paper at ICLR 2023
3.2 DEFINITIONS OF ALGORITHM CLASSES AND FUNCTION CLASSES
An algorithm is a mapping from real-valued functions to sequences. For algorithm and f Rd RR, we define A[ = FeN to be the sequence of algorithm acting on f, where x(0) E RRd
Note here, the algorithm under consideration works function defined any Euclidean space. We call it the dimension-fred property of the algorithm.
The definition of algorithms abstracts away from the the optimization process of function. We consider algorithms which only make use of the first-order information of the iteration sequence. We call them first-order algorithms. If an algorithm is first-order algorithm, then
(
Vf(x
(1-11, Vf(x((-1))
(5)
where A is function depending A. Perhaps the simplest example of first-order algorithms is Gradient Descent.
We interested in finding e-approximate point of function f. Given function f Rd IR and an algorithm A, the complexity A on f is the number of queries to the first-order oracle needed find an e-approximate point. We denote (A, f) be the gradient complexity of A on f. then
To Te f) min t: f(x()))- se
(6)
t
In practice, we do not have the full information of the function f. We only know that f is particular function class F, such as L-smooth functions. Given an algorithm A. We denote Tg (A, F) to be the complexity of A on F, and define T TA JF as follows:
TA = sup (A,
FEF
Thus, FA, is the worst-case complexity of functions f F.
For searching an E-approximate optimal point of function in F, we need to find an algorithm which have a low complexity F. Denote an algorithm class by A. The lower bound of algorithm class on F describes the efficiency of algorithm class A on function class F, which is defined to be
(e) = inf Te(A,F) = inf sup Te (e, AEA JEF
(8)
AEA
3.3 ZERO-RESPECTING ALGORITIM
Among all the algorithms, special algorithm class is called zero-respecting algorithms. If A is zero-respecting algorithm and A[S] (x(1) >res then the following condition holds for all f
Rd + R:
(u)) - xx (0) U supp fx)
(9)
That is say, (n) ()) lies in the linear subspace spanned by ()) (((((n))) We
denote the collection of first-order zero-respecting algorithms with x (0) by Az.. It is shown by Nemirovskij & Yudin (1983) that a lower complexity bound on first-order zero-respecting algorithms
also a lower complexity bound on all the first-order algorithm when the function class satisfies the orthogonal invariance property.
3.4 ZERO-CHAIN
zero-chain ff is a function that safisfies the following condition:
supp(x) S (1,2, ... .., .))
= supp(Vf(x)) S 11, Vx.
(10)
In other words, the support of fx() lies in a restricted linear subspace depending on the support
of x.
4

---

Under review as a conference paper at ICLR 2023
1.0
1.75
0.5
1 0.5
37
0.5
1.50
0.2
0.2
0.8
022
1.25
=01
=01
0.6
0.1
1.00
0.75
0.4
0.50
0.2
0.25
0.00
-1.0
-0.5
0.0
0.5
1.0
1.5
2.0
-1.0 -0.5 0.0 0.5
1.0 1.5 2.0
-1.0
0.5
0.0
0.5
1.0
15
2.0
(a) VTec
(b) r/T,
(c) by.c
Figure 1: Illustration of vr,e, 7T, and by.e-
The "worst function in the (convex) world" in Nesterov (2003) defined as 1 fx(x)) 2x1 1)² + (x+1 x,)
(11)
a zero-chain, because if x; 0 for i n, then (x)) for i > A zero-chain is dif- ficult to optimize for zero-respecting algorithms, because zero-respecting algorithms only discover one coordinate by one gradient computation.
MAIN RESULTS
According to Theorem we already have an upper complexity bound O (#1 log by applying Gradient Descent all the PL functions. In this section, we establish the lower complexity bound of first-order algorithms on PL functions. Let P(A, μt, L) be the collection of all L-smooth and Ju-PI. functions f with f(x(()) - f < A. We establish a lower bound of Ts (Aze, P(A, μt, L)) by constructing a function which is hard optimize for zero-respecting algorithms, and extend the result to first-order algorithms. We first propose a relatively simple hard instance which leads to Q (k²199 lower bound in Section 4.1 where can be any real number that belongs (0, 1). This helps in understanding our intuitions. Then we present a more complicated hard instance that can achieve the desired Ω (ı log 2)
lower bound Section 4.2
4.1
Ω (k=10) LOWER BOUND
We introduce hard function fr, RT. + 18 for first-order algorithms:
T
fT.Co (x) = +(x) + a
UT.o(
(12)
where
1
((x)
(x++1 x;)²
(13)
2
i=1
a quadratic function, and we define YT,c as follows:
xx
r F51 30 LT
x
167
(I 1
1 17- <1
UT (T,)(x)
32
(14)
12
32 - ++ 167
1 T-92
1< T-
xx2
T
x x>1+1 17
32
where T is a positive integer, and are positive real numbers.
The function can be rewritten as
q(x) 2 x Ax,
(15)
5

---

Under review as a conference paper at ICLR 2023
where
2 -1
-1
2 -1
=
(16)
-1 2
-1
-1
is a desiiie-deffnite symmetric matrix.
From the definition of VTe in (4p. we obtain the derivative of UT, which is:
-
327 (x 11-1+ 32 _T
-
(x)
(17)
x + 327
(x (x-1-1 1-1-22- T
1 x x>1+ 32
TT
As we can see in (17). V/ is piecewise linear function. To further simplify notations, we define (x)) in (8):
[1 327 1/. 1 1 T- 1 T-c
(T((())=
32
(18)
00
otherwise.
Then (x) - (r,( Figure provides geometric view uree and by,e-
The quadratic part q is translation "the worst function in the (convex) world" in Nesterov (2003), and the definition of or, is inspired by the hard instance in Carmon et al. (202T). Our hard instance differs from previous ones mainly in the large Lipschitz constant of gradient. We note that the controlled degree of nonsmoothness is crucial for our estimate PI. constant. Lemma [ we list some important properties of fT.c,o, which we prove in Section ??.
Lemma 1, a < and T 2 20-1, then fr,c satisfies the following.
1. gT, = fT, x) is a zero-chain.
2. x' = fi.co 0, fr.c,o (x) 1 (A oT)x.
3. fr.co is (4+ 320T -
4. ST., satisfies - PL condition, where C₁ a universal constant.
Now study the lower bound of zero-respecting algorithms first. Let f denote the following function:
f(x) 42oTc ST.C,O (1 (1-71/2D-1x)
-2-112
(19)
where is the distance between and x*, and T, are parameters be specified later. A change in D affects f(0)- f(x*) and ||x* 0|, but does not affect the condition number of f.
In Lemma [ we show that is difficult to optimize for all first-order zero-respecting algorithms.
Lemma 2. Ifo < 1 and T fo- a first-order zero-respecting algorithm with x (0) = 0 needs least T gradient computations to find point satisfying f(x) - f 16 (x(x f*).
We give the full proof of Lemma 2 in Appendix B.I. The key point is that each gradient access of a rero-respecting algorithm only reveals one coordinate of zero-chain. For T. x remains unchanged when lo < 2- which gives a lower bound of the function value after the first gradient computations.
With Lemma T and Lemma 2 in hand, we are ready to give our lower complexity bound for zero- respecting first-order algorithms.

---

Under review as a conference paper at ICLR 2023
Theorem 2. Given L p 0 and 0.01. When K > C2 where C2 is universal constant,
let
100 C2
1/(2+6c)
200
1/(1+5e)
TE
K
C2 Ki
nz
(20)
and
100
xT (1+66)
xT
(21)
C2
Then, f is L-smooth and μ-PL. Moreover, any first-order zero-respecting algorithm with x
O needs at least Q (x1/(1)))) gradient computations to find point satisfying f(x) f S 1. ( f*)
The proof of Theorem 2 provided in Section ??. For a satisfying 6(1a] 0.01, l क(ーー)}
then by Theorem 2 any zero-respecting algorithm needs at least ((xt=a) gradient computations to find e-approximate optimal point of the function f.
Using the technique of Nemirovskij & Yudin (1983), for specific function classes such as PL func- tions, a lower complexity bound on first-order zero-respecting algorithms is also lower complexity bound all the first-order algorithms. Denoting the set of all first-order algorithms by A have the following lemma:
Lemma 3.
Te (1t) (1A,,) 2 Te (Arr, P(A,
(22)
Note that given L and μe, the value f(0) can controlled by choosing an appropriate D. Lemma leads to the main result of the paper:
Theorem 3. For any 0 < < 1, when
1 L.
To ( P(A, 2 12(x''1)
(23)
Discussion about parameter setting In the definition of J. has hyper-parameters T, a, c. From our construction, achieve lower bound ((x1=a) when a tends to zero, c also tends to zero. Parameters T and a are chosen according to (20) and (21). When tends to zero, T = (xx) and a tends
4.2 Ω (Is log !) LOWER BOUND
We show that the ((x) lower bound can be further improved (s 1) with a new hard instance based on fr.e. and similar technique to estimate the PL constant. Detailed proof of Lemmas and Theorems this subsection is provided in Appendix C.
We first introduce several components of the new hard instance. We define
x
x y. y < x y,
2x²
16
(x-
31
35
By (x)
(24)
xx
n² + 16
32
33
33 32
1 y
3y /,
32
where y > 0 is constant. By the definition of By. we have
x 31
x,
32
31
3 81
(((x))
(25)
32
y ツ<スー 39
x> 3

---

Under review as a conference paper at ICLR 2023
For the non-convex part, define
(x( = [1/ 32 y/.
32 otherwise.
31
32
(26)
0,
Then we have (x) by(())
For the convex part, we define ( as follows (for the convenience of notation, we define Xo 0):
2 T-1 +
Σ (5XT (
qI,((x)
(xT+++1 (x++)+1-xx+++) xxT+y)²
(27)
where E T Qr. is quadratic function of thus can be written as
qT, B',, Bx,
(28)
where a positive semi-definite symmetric matrix. Like A, B also satisfies N B < 4I, because the sum of absolute value of non-zero entries of each row of B is smaller equal to 4.
Let E R be vector satisfying M,7+h = (3)% % where E N, be , We define the
hard instance gr, T + R as follows:
Tt Σ 1=1
(T.x(x) (x. +
Uy (xi).
(29)
Now we list some properties of Ir. in Lemma Lemma 4. free satisfies the following.
1. gT.ely x) is zero-chain.
2. 0, .T. O. gxx f (B+I)x
3. 9r.t is 37-smooth.
4. 91. satisfies the PL condition, where C33 is universal constant.
Define ÿ to be the following function, which hard for first-order algorithms:
D2
37 9r (y - (1-
O(x)
(30)
Similar to Lemma we show that is hard for first-order zero-respecting algorithms:
Lemma 5. Assume that < 0.01 and let = log 2 A firstorder zero-respecting algorithm
with (0) 0 needs least T gradient computations to find point x satisfying g(x) " S
=(ğ(x (0) g²).
With Lemma 4 and we obtain lower bound for zero-respeting algorithms:
Theorem 4. Given 2 μ >>0 O. When
L > C4 where C4 is a universal constant, there exists
and such that ğ is L-smooth and p-PL. Moreover, any first-order zero-respecting algorithu with
(0) 0 needs least Z (ss log 2) gradient compulations to find point satisfying g(x) - ="" S
-g²").
Finally, we arrive at lower bound for first-order algorithms using Lemma Theorem 5. For any < a < when E E 16 A,
Te P(A, Ω k log !)
(31)
This bound matches the convergence rate of Gradient Descent up constant.
8

---

Under review as a conference paper at ICLR 2023
Lower bound
2.5
0.0-
-2
AGD, p=
AGD, p=
fxx*) -4
Foc-)
log30
Rx**)
-6
Heavy-ball, ů
log10 Fix9)
5.0-
Lower bound
Heavy-ball, o
GD
8-
AGD, ů g-M
10
AGD, ů
12.5-
-12
Heavy-ball, A=
Heavy-ball, f =
-14
-17.5
200
400
800
1000
1200
2000
4000
6000
8000
Gradient queries
Gradient queries
(a) K. = 4.8384 x 10
(b) K = 4.8384 x 10
Figure 2: Convergence rate under Gradient Descent, Nesterov's Accelerated Gradient Descent and Polyak's Heavy-ball Method
NUMERICAL EXPERIMENTS
We conduct numerical experiments our hard instance. We consider the x relatively large, which can reduce the factors from the numerical constants. We 4.8384 x 10a c 0.001 in Figure 2a and K 4. 4.8384 x 10 0.001 in Figure 2b then compute corresponding T and a according to 20 and (21) We use Gradient Descent, Nesterov's Accelerated Gradient Descent (AGD) and Polyak's Heavy-bal Method optimize the hard instance. As AGD and the Heavy-ball Method are designed for convex functions, we need to choose appropriate parameter ji in both algorithms, because our hard instance non-convex. The first choice is μr, which the PL constant of our hard instance. The second choice is because when x; is far from 1, our hard instance can be treated as a o-strongly convex quadratic function.
From Figure we observe that the convergence can be roughly divided into two phases. In phase one, the optimization methods tries to pull every coordinate x away from 1, and the function value does not decrease much. In phase two they converge linearly. This may be due to the fact that when each x; is far from 1, our hard instance exactly strongly convex quadratic function. The observation is consistent with theoretical results.
CONCLUSION
We construct lower complexity bound on optimizing smooth PI. functions with first-order methods. A first-order algorithm needs at least Ω log gradient access to find an s-approximate optimal point an L-smooth p-PL function. Our lower bound matches the convergence rate of Gradient Descent up to constants.
We only focus on deterministic algorithms in this paper. We conjecture that our results can be extended to randomized algorithms, using the same technique in Nemirovskij & Yudim (9883 and explicit construction in Woodworth & Srebro (2016) and Woodworth & (201)) We leave its formal derivation to the future work.
REFERENCES
Mihai Aniteseu. Degenerate nonlinear programming with a quadratic growth condition. SIAM
Journal on Optimization, 10(4):1116-1)) 16-4111166 2000.
Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint 1912.02., 2019a.
Yossi Arjevani, Ohad Shamir, and Ron Shiff. Oracle complexity of second-ore order methods for smooth convex optimization. Mathematical Programming, 178(1-2):3773360 November 2019b. ISSN

---

Under review as a conference paper at ICLR 2023
0025-5610, 1436-4646. doi: 10.10077/11107--11-122999 URL URL.ttD://in...pp-.... 0000:000000001111100011-12222221
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridha- ran. Second-order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pp. 242-299. PMLR, 2020.
Raef Bassily, Mikhail Belkin, and Siyuan Ma. On exponential convergence of SGD in non-convex over-parametrized learning. arXiv preprint 181.05664 2018.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points I. Mathematical Programming. 184(1):71-120, 2020.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points II: first-order methods. Mathematical Programming, 185(1):315-355 2021.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non-convex
optimization via stochastic path- inteegrttteed differential estimator. Advances Neural Information Processing Systems, 31, 2018.
Maryam Fazel, Rong Ge. Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradi- ent methods for the linear quadratic regulator. In International Conference on Machine Learning, pp. 1467-1476. PMLR, 2018.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. arXiv preprint urXiv:1611.04233 2016.
Sashank Reddi, Suvrit Sra, Barnabas Poczos, and Alexander J Smola. Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. Advances in neural information processing systems, 29, 2016
Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- condition. In Joint European Conference on Ma- chine Learning and Knowledge Discovery in Databases, pp. 795- 811. Springer, 2016.
gradient methods under the
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum optimization via sesg methods. Advances in Neural Information Processing Systems, 30, 2017.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in wee-pparameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning The- ory, pp. 2-47. PMLR, 2018
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over- parameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 2022.
Liu, Steve Wright, Christopher Ré, Victor Bittorf, and Srikrishna Sridhar. An asynchronous par- allel stochastic coordinate descent algorithm. In International Conference Machine Learning, pp. 469-477. PMLR, 2014.
Stanislaw Lojasiewicz. A topological property of real analytic subsets. Coll. du CNRS, Les équations aux dérivées partiellex, 117(87-89)22 1963.
Zhi-Que filnQuan Luo and Paul Tseng. Error bounds and convergence analysis of feasible descent methods: general approach. Annals of Operations Research, 46(1):157-178, 1993.
Katta G Murty and Santosh N Kabadi. Some NP-complete problems in quadratic and nonlinear programming. Technical report, 1985.
Ion Necoara, Yu Nesterov, and Francois Glineur. Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming, 175(1)69--077, 2019.
Arkadij Semenović Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
10

---

Under review as a conference paper at ICLR 2023
Yurii Nesterov. Introductory lectures convex optimization: A basic course, volume 87, Springer Science & Business Media, 2003.
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
B.T. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathe- matics and Mathematical Physics, 3(4):864 8788 1963.
Blake Woodworth and Nathan Srebro. Lower bound for randomized first order convex optimization. arXiv preprint arXiv: / 7709003599 2017.
Blake E Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. Advances in neural information processing systems, 29, 2016.
Hui Zhang and Wotao Yin. Gradient methods for convex minimization: better rates under weaker conditions. arXiv preprint arXiv: 1303.4645, 2013.
Dongruo Zhou and Quanquan Gu. Lower bounds for smooth nonconvex finite-sum optimization. In International Conference Machine Learning, pp. 7574-7583, PMLR, 2019.


Reviews:
[{"review_id": "WXOCKmrNQw", "reviewer": "Reviewer_sXZK", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "The paper presents a lower bound on gradient oracle complexity for optimizing smooth PL functions. Their result establishes that gradient descent method is worst-case optimal for this class of functions. ", "summary_of_the_review": "I think the studies a very natural problem and provides an interesting result. The only downside is its limited scope.\n\nEdit: Post author response, I have increased my score from 6 to 8.", "strength_and_weaknesses": "Strengths:\n\n- I think the problem is very natural and it was surprising (to me) that a result of this sort was not known. Also, the finding that gradient descent is optimal is interesting as well. This is because in (some parts) of the literature, PL functions are basically used as a class of non-convex functions in which typical analysis with strong convexity applies. However, this paper shows that unlike smooth strongly convex functions, it is not possible to accelerate gradient descent for this class. This establishes an interesting separation between the two classes.\n\n- I think the paper is written well; it presents a good overview of the existing tools in lower bound constructions and gradually builds up towards the main result. Also, the main text contains sufficient details of the proof.\n\nWeaknesses: \nI think the main weakness is that the scope of the paper is rather limited. Moreover, I think that there are still some loose \nends which would have been good to resolve (or comment on its difficulties) given the limited scope. One such aspect is that the lower bound is only established for constant error -- while this is sufficient to argue that no acceleration is possible in this class; it would be good to show that the oracle complexity of gradient descent is tight even with regard to its dependence on $\\epsilon$. Another aspect, unclear to me, is whether these lower bounds extend to randomized methods? If yes, the authors should comment on that; if not, it would be good to incorporate it (perhaps using techniques of [WS17]) or discuss challenges towards it.\n\n[WS17]:  Lower bound for randomized first order convex optimization\n\nI read parts of the proofs and have corrections and questions about how some of the steps follow. It would be helfpul if the authors response help address these.\n\n- Don't understand why the inequality before Eqn. 53 holds. If the lower bound on $m$ in the statement is used, then there should be no $m$ in the right hand side.\n\n- Proof of Lemma 5: I am little confused about the first few lines in the proof of this lemma. What if all coordinates of $\\tilde x$ except the first (which is 0) are negative. Then the assertion that there exists $k,l$ such that $\\tilde x_i>0.5$ for $i=k..l$ is not true. It seems that the proof should thus use the absolute values of these.\n\n- I am not sure about what happened in inequality in Eqn. 59.\n\n- Statement of Lemma 6: It seems that the assumptions stated in the lemma statement is not sufficient to get the final result -- say $x_l$ is $-\\infty$, $x_{l+1} = 1- \\frac{1}{32}T^{-c}$ and $x_{l+2} = 1+\\frac{1}{32}T^{-c}$, then $(\\nabla f_{T,c,\\sigma} (x)){(l+1)} = -\\infty$ The premise thus needs to be strengthened. Also, I dont understand some parts of the proof here:\n(a). Third inequality -- how? what if $\\tilde x_{l+1}$ is negative?\n(b). What happened in the fourth inequality; the statement has no lower bound on $\\tilde x_l$ in terms of $\\tilde x_{l+1}$, right?\n\n- Typo: It seems $1/32$ missing from definition $v_{T,c}$?\n\n- Typo: $\\sigma$ missing in front of $b_{T,c}(x)$ in inequality after Eqn. 66 and henceforth.\n\n- Typo: after Eqn 70, inequality should be outside the norm.\n\n- Typo: should be $1+\\frac{T^{-c}}{32}$ in the rhs in the first sentence of part 4(c) of proof of Lemma 1.\n\n- Typo: Should be $\\tilde x_k$ (as opposed to $\\tilde x_m$) at the end of base case in proof of Lemma 5\n\n- Typo: In the proof of Lemma 2, the last inequality should be $\\geq$.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Svu2tDBbeM", "reviewer": "Reviewer_dAiB", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "This paper studied the lower bound of minimizing PL functions. It provided an $\\Omega((L/\\mu)^{1-a})$ (arbitrary small $a>0$) lower bound for finding the optimal solution. It reveals a fundamental difference between PL functions and strongly convex minimization, also it shows that GD is already nearly optimal for solving PL functions.", "summary_of_the_review": "To be honest, I am in a dilemma on evaluating the significance of the result. I am excited on the result concerning it is the first result for PL functions. But the lower bound here is just $\\Omega((L/\\mu)^{1-a})$, which is kind of \"constant\" level, rather than the $\\Omega(\\sqrt{\\kappa}\\log(1/\\epsilon))$ in the strongly convex case, or maybe the lower bound here can be further rewritten as ($\\kappa=L/\\mu$):\n\n$\\Omega(\\max(\\sqrt{\\kappa}\\log(1/\\epsilon), \\kappa^{1-a}))$\n\nSo I believe that the result in the submission should not be tight enough (maybe the final tight lower bound should be $\\Omega(\\kappa\\log(1/\\epsilon))$?), which makes me skeptical on the significance of the result. So I hope to learn more from authors on the insight of the result, also the difference on the technical part compared to the lower bound of strongly convex minimization. Thank you for the effort.\n\n---------Update---------\n\nI appreciate authors' effort for revising the result, and there is a significant change in the new version, which took me a long time to read it beyond the regular review time frame. I think it is a pretty nice result revealing high importance, but I would say it is almost another new paper and I agree with Reviewer a1uz that it may require another full round of serious review, so I will keep my score here. Thank you very much.", "strength_and_weaknesses": "Strength:\n1. First specific lower bound result for PL functions\n2. Reveals the fundamental difference between PL function and strongly convex functions\n3. The paper is well-written.\n\nWeakness:\n1. The lower bound comes without the dependence on $\\epsilon$, which is different from the strongly convex counterpart.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "PFeIAqezY8O", "reviewer": "Reviewer_a1uz", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "This work derives a new lower bound for the class of first-order methods applied to minimize $L$-smooth functions satisfying the Polyak-Łojasiewicz condition with parameter $\\mu$. In particular, the authors derive $\\Omega\\left(\\left(\\frac{L}{\\mu}\\right)^{1 - \\alpha}\\right)$ lower bound for finding $\\varepsilon$-solution (for small enough $\\varepsilon$ and large enough dimension of the problem that depends on $\\alpha$). This closes a long-standing open question about the optimality of Gradient Descent for this class of problem.", "summary_of_the_review": "Overall, the main result of the paper is very good and significant, if the mentioned inaccuracies are not fatal mistakes. I will increase the score if the authors fix at least the issues with the proofs (otherwise, I will have to decrease the score and recommend rejection). Moreover, the paper will benefit, if the authors provide the results of the numerical experiments requested in my review.\n\n\n\n**UPDATE after rebuttal:**\n\nI thank the authors for their effort and improvement of the lower bound. However, a lot of new content was added: original submission was 15 pages (with appendix), not it has 26 pages. These extra pages are quite technical and I can say that the changes are too significant. Therefore, the paper needs another full round of review. Unfortunately, I have to take this into account, that is why I am changing my score to 3.", "strength_and_weaknesses": "## Strengths\n\n1. **Long-standing open question is resolved.** The contribution of the paper is fundamental: the question about the lower bounds for smooth PL functions has been open for a long time. PL condition gained a lot of interest in the optimization and ML communities during the recent few years, but the question remained open. This indicates the non-triviality of the derived result. \n\n2. **Elegant worst-case example.** I find the constructed \"worst-case\" function quite elegant: it is a sum of Nesterov's \"worst function in the world\" function and piece-wise quadratic function (along each component). The first part is standard and provides nice properties such as zero-chain property, which is the key property of literally all existing lower bounds. The second part is non-standard and makes the problem non-convex but not too much, i.e., PL-condition holds. Therefore, the proposed worst-case function is very intuitive and quite simple. I believe that providing simple solutions (especially for old problems like the one that this work addresses) is highly valuable for the community.\n\n## Weaknesses\n\n1. **Inaccuracies and gaps in the proofs.** Unfortunately, the proofs are hard to read due to multiple inaccuracies and gaps. Most of these issues can be fixed (I have double-checked), but a few of them are not obvious to me (though I did not try to think about them too long -- this is the authors' responsibility to make the proofs as clear as possible). See them in the list of comments.\n\n2. **Issues with English.** Some sentences end abruptly and some parts of the text are not polished well (especially in the proofs; because of that some parts are hard to comprehend). I provide some comments related to this issue. I suggest the authors make a thorough pass through the paper and correct all issues with English.\n\n## Detailed comments\n\n1. **Numerical experiment request.** The main result of this work is more than sufficient for publishing at top optimization/ML conference/journal (if the inaccuracies mentioned below are not fatal mistakes). However, I am curious to see how accelerated methods like Nesterov's one or momentum methods like the Heavy-ball method of Polyak behave on the constructed worst-case smooth PL function. It would be great to see the comparison of these methods with GD and with the theoretical lower bound for different dimensionalities of the problem.\n\n2. \"The PL condition may be originally introduced by Polyak\": if I am not mistaken it was introduced by Polyak and Łojasiewicz independently.\n\n3. \"any $\\hat \\mu$-strongly convex function that admits\": this sentence is a bit confusing because during the first reading one can think that the authors mean a particular subset of strongly convex functions. However, after this sentence, they provide a definition of differentiable strongly convex function. To prevent confusion, I suggest removing \"that admits\" (or replacing it by \", which by definition satisfies\").\n\n4. **Discussion about $\\alpha, T, c$.** I believe that this discussion should be added somewhere in the text. In particular, $\\alpha$ can be chosen arbitrarily small. However, in this case, $c$ has to be also small. This implies that $T$ should be large enough (according to (31) and (32)). In particular, $T \\to \\infty$ when $\\alpha \\to 0$. Therefore, the dimensionality of the worst-case example depends on $\\alpha$. I believe, the paper will benefit from such kind of discussion.\n\n5. Section 2 requires proofreading in terms of English: some sentences end abruptly.\n\n6. The fonts in Figure 1 are too small. The authors should increase the fonts and also add markers to the curves (to make the plots easier to comprehend).\n\n7. Formula (14) appears between two sentences. It should be a part of a sentence, e.g., \"Next, we define $v_{T,c}$ as follows:\"\n\n8. Formula (14), the first row (condition on $x$), the second row (last term), the third row (the last term): one should add $\\frac{1}{32}$ in front of $T^{-c}$.\n\n9. Formula (19): what is the role of $D$? This parameter is never introduced.\n\n10. Page 7, \"for any $0 < a < 1$\": one should also add that $\\frac{a}{6(a-1)} < 0.01$ (otherwise the the condition on $c$ from Theorem 2 does not hold).\n\n11. Proof sketch of Lemma 1: I think, this proof sketch does not improve the understanding of the proof. I believe it would be better to provide just the full proof of Lemma 1: for me it was easier to check the full proof than to parse the sketch.\n\n12. Pages 8-9: \"the smooth constant\" --> \"the smoothness constant\"\n\n13. Lemma 2, page 11: it is worth saying in the statement of the lemma that $T^{c} \\geq \\frac{1}{2}\\sigma^{-1}$ and $\\sigma < 1$.\n\n14. Formula (43): the union is over $k$, not over $i$\n\n15. Page 12, \"Lemma 3 then follows from Proposition 2 in Carmon et al. (2020)\": I guess one needs Proposition 1 to get the result. Moreover, it is formally about the slightly larger class of methods (so-called zero-respecting algorithms). As Carmon et al. (2020) write, this class is strictly larger than the class of the linear-span methods. However, the proof of Lemma 2 is valid even for zero-respecting algorithms, so, one can replace everywhere in the text \"linear-span methods\" by \"zero-respecting methods\" (and introduce zero-respecting methods instead of the linear-span ones).\n\n16. Formula (48): $E_{T,T}$ is not defined. I guess it is $T\\times T$ matrix having zero elements everywhere except the element $(T,T)$ that is equal to $1$.\n\n17. After (49): I guess $e^{(i)}$ is a column of $I$, not a row (to have the right size).\n\n18. After (50): one should exclude $k = 0$.\n\n19. After (52), \"From $x_k = \\max |x_i|$\": this sound a bit informal. Better to change to: \"For $k$ such that $x_k = \\max |x_i|$...\"\n\n20. Formula (53): in the fourth step one can get $\\frac{1}{32}$ instead of $\\frac{1}{64}$. Also the constant in the end should be different since $A + \\sigma I \\preceq (4+\\sigma) I$ (see my comment 31).\n\n21. Above (57): why $x_1$ cannot be larger than $1 - \\frac{1}{32}T^{-c}$? It seems that the current proof requires $x_1$ to be smaller than $1 - \\frac{1}{32}T^{-c}$.\n\n22. Formula (57), the last step: if my calculations are correct, one can get $\\sigma^2$ in the end (which is slightly better).\n\n23. \"The last inequality above holds because $||(A + \\sigma I)x|| \\leq 6\\sqrt{T}$\": my derivations give slightly better bound ($4$ instead of $6$). Moreover, the authors should provide the full derivation since it is not the readers' responsibility to fill the gaps in the proofs.\n\n24. Formula (58): the authors should provide the complete derivation. I have double-checked this part myself, everything seems to be correct. However, as I already mentioned, this is the authors' responsibility to provide complete and clear proof.\n\n25. Above (59), \"If (56) holds for $i = n$\": this is not a sentence. The authors should reformulate this part.\n\n26. The last step of (59): I do not understand the last step. In particular, it is equivalent to $- \\frac{1}{1 + \\sigma/2}\\tilde{x}_n \\geq 0$. But this is not true. **I think this is an important gap in the proof.**\n\n27. Formula (61): I do not understand how the fourth and sixth inequalities were obtained. Complete derivations are required. **I think this is an important gap in the proof.** Also I guess $\\theta$ should be replaced by $\\sigma$. Next, the final step also requires the full derivation (though this particular step is correct). \n\n28. Formular (63): $b_{T,c} \\to b_{T,c}(x)$.\n\n29. The sentence after (63): I think it is better to add some details, e.g., $b_{T,c}(1) = 1$, which implies that $(\\nabla g_{T,c,\\sigma}(x))_j = (A(1-x))_j$ for $j \\geq i$.\n\n30. Formula (65): one should have factor $1 + 32T^c$, since $b_{T,c}$ does not depend on $\\sigma$.\n\n31. \"Consequently, $f_{T,c,\\sigma}$ is $(3 + 32\\sigma T c)$-Lipschitz because $A \\preceq 2I$\": in fact, $A$ has eigenvalues larger than $3$, so, $A \\preceq 2I$ does not hold. Instead, one can get $A \\preceq 4I$ implying that $f_{T,c,\\sigma}$ is $(4 + \\sigma + 32\\sigma T c)$-smooth (not Lipschitz)\n\n32. Formula (66), the last step: one should add $\\inf_{x\\in \\mathbb{R}^T}$ in front of the expression and also multiply $b_{T,c}(x)$ by $\\sigma$.\n\n33. Formula (68): I have double-checked this part, but the authors should provide a complete derivation. Also above (68) and everywhere in this proof one should replace $\\max_{i=0,\\ldots,T+1}\\tilde{x}_i$ with $\\max_{i=0,\\ldots,T+1}|\\tilde{x}_i|$.\n\n34. Formula (69): I have double-checked this part, but the authors should provide a complete derivation.\n\n35. After (69), (c): one should have $1 - \\frac{1}{32} T^{-c} \\leq \\max_{i=0,\\ldots,T+1}|\\tilde{x}_i| \\leq 1 + \\frac{1}{32} T^{-c}$.\n\n36. After (70), \"consequently ...\": the norm sign is in the wrong place.\n\n37. Formula (71), the second step: according to my derivations, one should have $5$ instead of $3$ in the denominator of the second term. The authors should provide the complete derivation.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject