Sharp Analysis of Stochastic Optimization under Global Kurdyka-Lojasiewicz Inequality
Authors: Ilyas Fatkhullin
Jalal Etesami
Niao He
Negar Kiyavash
Venue: NeurIPS 2022 Accept (2022)
Keywords: stochastic optimization
nonconvex optimization
first order method
Kurdyka-Lojasiewicz condition
variance reduction

Abstract: We study the complexity of finding the global solution to stochastic nonconvex optimization when the objective function satisfies global Kurdyka-{\L}ojasiewicz (KL) inequality and the queries from stochastic gradient oracles satisfy mild expected smoothness assumption.  We first introduce a general framework to analyze Stochastic Gradient Descent (SGD) and its associated nonlinear dynamics under the setting.  As a byproduct of our analysis, we obtain a sample complexity of  $\mathcal{O}(\epsilon^{-(4-\alpha)/\alpha})$ for SGD when the objective satisfies the so called $\alpha$-P{\L} condition, where $\alpha$ is the degree of gradient domination. Furthermore, we show that a modified SGD with variance reduction and restarting (PAGER) achieves an improved sample complexity of $\mathcal{O}(\epsilon^{-2/\alpha})$ when the objective satisfies the average smoothness assumption. This leads to the first optimal algorithm for the important case of $\alpha=1$ which appears in applications such as policy optimization in reinforcement learning. 

Sharp Analysis of Stochastic Optimization under Global Kurdyka-Lojasiewicz Inequality
Ilyas Fatkhullin' ETH Al Center & ETH Zurich
Jalal Etesami" EPFL*
Niao He ETH Zurich
Negar Kiyavash EPFL
Abstract
We study the complexity of finding the global solution stochastic nonconvex optimization when the objective function satisfies global Gurdyka-Lojasieve (KL) inequality and the queries from stochastic gradient oracles satisfy mild ex- pected smoothness assumption. We first introduce a general framework to analyze Stochastic Gradient Descent (SGD) and its associated nonlinear dynamics under the setting. As a byproduct of our analysis, we obtain a sample complexity O(E-(4-a)/o for SGD when the objective satisfies the so called a-PL condition, where is the degree of gradient domination. Furthermore, fied SGD with variance reduction and restarting (PAGER) achieves an improved sample complexity of O -2/o) when objective satisfies the average smooth- ness assumption. This leads the first optimal algorithm for the important case of a = which appears in applications such as policy optimization in reinforcement learning.
show that a modi-
Introduction
Nonconvex optimization problems are ubiquitous in machine learning domains such training deep neural networks [22] policy optimization in reinforcement learning [52]. Stochastic Gradient Descent (SGD) and its variants are driving the practical success of machine learning approaches. Naturally, understanding the limits of performance of SGD in the nonconvex setting has become an important avenue of research in recent years [2
59
We are interested in solving the unconstrained stochastic, nonconvex optimization problem of the form
min f(x) = Ee-D [=)( #ERd
(1)
where f()) is smooth and possibly nonconvex, and & is random vector drawn from a distribution D. Moreover, we are interested in an important special case of (T), when the expectation can be written as the average of n smooth functions:
min FER
[(x))
Σ M
For general nonconvex differentiable objective f Rd finding a global minimum of is in general intractable [2 54]. There are two common strategies to analyze optimization methods for nonconvex functions. The first one is scale down the requirements on the solution of interest from global optimality to some relaxed version, e.g., first-order stationary point. However, such solutions do not exclude the possibility of approaching suboptimal local minima or a saddle point. Another approach is to study nonconvex problems with additional structural assumption in the hope of
First two authors have equal contribution. I École polytechnique fédérale de Lausanne
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

convergence to global solutions. In this direction, several relaxations of convexity have been proposed and analyzed, for instance, star convexity, quasar-convexity, error bounds condition, restricted secant inequality, and quadratic growth [26] 24 23 Many of the aforementioned relaxations have limited application in real-world problems.
Recently, there has been a surge of interest in the analysis of functions satisfying the so-called Lojaseewiz (KL) inequality 2 I0]. Of partieular interest is the family of functions that satisfy global KE inequality. Specifically, we say that f(-) satisfies (global) KL inequality if there exists some continuous function ((.) such that || [x)ll 2 ó (f(x)- inf, f(z)) for all x E R If this inequality is satisfied for ((t) = 22 tl/a, then we say that (global) a-Pt. condition is satisfied for f(.). The special case of Kt. condition, 2-PE., often referred as Polyak-L.ojasiewice or PL condition, was originally discovered independently in the seminal works of B. Polyak, T. Ležanski and S. Lojasiewicz [48 33 38 39). Notably, this class of problems has found many interesting emerging applications in machine learning, for instance, policy gradient (PG) methods in reinforcement learning 41 1I [56. generalized linear models [4], wver-parameterize neural
networks (7).. linear quadratic regulator in optimal control 13 19 and low-rank matrix recovery
Despite increased popularity of KE and a-PL assumptions, the analysis of stochastic optimization under it remains limited and the majority of works focus deterministic gradient methods. Indeed until recently. only the special case of a-PE with a = 2 was mainly addressed in the literature 49]. In this paper, we study the sample complexities of stochastic optimization for the broader class of nonconvex functions with global Kł property.
26
23 30 53
1.1 Related Works and Open Questions
Stochastic gradient descent. A plethora of existing works has studied the sample complexity of SGD and its variants for finding an e-stationary point of general nonconvex function f, that is,
point x E Rd for which E[| [f S e. For instance, [21] showed that for a smooth objective (one with Lipschitz gradients) under bounded variance (BV) assumption, SGD with properly chosen stepsizes reaches an e-stationary point with the sample complexity of Oe) Recently, [30, [66] further extended the result under a much milder expected smoothness (ES) assumption on stochastic gradient. While this sample complexity is known to be optimal for general nonconvex functions, a naive application of this result the function value using a-PL condition would lead to a suboptimal Ole (
sample complexity for finding an o-potimal solution, i.e., E (xxx) - [*] S ey. Recently, 20 studied SGD and established convergence rates for a-Pt. functions under BV assumption. Their sample complexity result is Ole, 0(e"(--/// in our notation. Later 35 considered SGD scheme with random reshuffling under local and global KF. conditions and provided convergence in the iterates for E (1, 2). We note that our proof techniques are different from 20 and (355 and are not limited merely to the case of BV assumption. In this work, we will answer the following open question:
What is the exact performance limit of SGD under global Kt. condition and a more practical model of stochastic oracle?
Variance reduction. There has been extensive research on development of algorithms which improve the dependence on n. and/or for both problems [T) and (2) (over simple methods such as SGD and Gradient Descent (GD) ). One important family of techniques" is variance reduction, which has emerged from the seminal works of Blatt et. al [8]. The main idea of variance reduction is make use of the stochastic gradients computed at previous itcrations to construct a better gradient estimator relatively small computational cost. Various modifications, generalizations, and improvements of the variance reduction technique appeared in subsequent work, for instance, [50] 28 [6]
to name a
few.
number of recently proposed algorithms such as SNVRG (58). SARAH 45). v when minimizing a general nonconvex function with finite sum structure (2) This result is also known to be optimal in this setting [36]. 27 studies SARAH in finite sum case under local Kt. assumption and
Finite-sum case.
STORM 15), SPIDER [17], and PAGE (36] achieve the sample complexity On + +
proves convergence in the iterates. The study in 27 is only asymptotic analysis and the dependence
Another independent direction is make use of higher order information 43 18 3

---

on the parameters & and n. which are important in practice for quantifying the improvement over GD and SGD are ignored. [4 proposes an SVRG-based based algorithm for Kł functions and [55] 45 46
study other variance reduction techniques, but they only analyze the special case a = 2. Under
2-PF. condition, these methods further improve to O (n + kynn) log( 2,)), sample complexity for
finding an é o-optimal solution. However, it is not clear it is possible to provide any non-asympiotic
guaranties for variance reduced methods under a-Pt. condition for any a E [1. In our work, we will answer the following open question:
What is the extent of improvement any variance reduction scheme can provide under global a-PL condition for finite-sum objectives of the form 2
Online/streaming case. While variance reduction methods have been initially designed for prob-
lems of the form (2) it was later discovered that they also improve over SGD when solving (I [32 1. The analysis of these methods was obtained for general noncorvex functions (for minimiz-
ing the norm of the gradient, E [I] V [a)]]] S e) and later extended to 2-PL objectives for minimizing
the function value, E [fx) - f I ey. For example, the methods in 558 45 17 36) achieve O(c ))
complexity improving over ( 4) complexity of SGD for finding an e-stationary point. Under the 2-PE. condition, these results can be extended to global convergence with (e7))) ) sample complexity
36). However, in contrast does not show any improvement over SGD in terms of cj. We highlight that all existing analysis of variance reduction under a-PE condition is restricted only to a special case a 2. We refer the reader to Appendix C where we elaborate on the key difficulties in the analysis for the cases E [1, 2). Since the direct analysis for a E (1,2) is challenging, in order obtain the global convergence in this setting, one could naively translate the complexity for finding a stationary point of general nonconvex function (which is ())=)) convergence in function value by using a-Pt.
general nonconvex case, variance reduction under 2-PL assumption
S [VV(())] This would result in O(e,""n) sample complexity. However, there are two serious issues with this approach. First, this complexity does not provide any improvement over SGD in the most interesting practical case a 1 and gives strictly worse result for all a > 1. Second, the guarantees for general nonconvex optimization hold on average, in the sense that the point à is sampled uniformly from all the iterates of the algorithm. It would be more desirable to instead derive last iterate convergence guarantees under KE (a-PL) condition. In this work, will address the following open question:
condition: 22 (f(#)
Is possible to accelerate the O ((e)"t- sample complexity of SGD under global o-PI. condition for stochastic objectives of the form
1.2 Contributions
In this work, we provide an extensive analysis of stochastic optimization under global Kt. condition and answer all the above questions. More precisely, our contributions are as follows
We provide a new framework for the analysis of the dynamics of SGD under global KL condition (see Section 3. It is based on the analysis of SGD dynamic which is governed by a recursive inequality (see Equation (6)). As a result of this analysis, we introduce a set of conditions (see Theorem D for designing proper stepsizes to guarantee convergence.
Using this framework, we provide sharp analysis of SGD under general ES assumption (Assumption 4h and demonstrate that the sample complexity O(, -4t=)//a is tight for the dynamical system deseribing SGD.
Next, propose PAGER, new variance reduction scheme with parameter restart. A carefully chosen sequence of parameters of PAGER allows the algorithm to adapt to the nonconvex geometry of the problem and establish state-of-the-arr convergence guarantees for minimizing a-PE functions. In online setting we obtain O E sample complexity
of PAGER, which beats O (e) (1-00)) complexity of SGD for the whole spectrum of
'x 4/μ is the analogue condition number, is defined in Assumption
Under additional assumptions such as smoothness of individual functions fe(.) or even milder condition such average L-smoothness (Assumption
3

---

parameters a E [1. In particular, for the important special case of 1-PL, this leads to the first optimal algorithm with O sample complexity, which already matches with the lower bound known for stochastic convex optimization [42].
Furthermore, we obtain faster rates with PAGER in finite sum case 22, providing the first acceleration over GD and SGD under a-PL condition.
In Table[] we summarize the sample complexity results for stochastic optimization under a-PL and BV assumptions. We also establish sharp convergence results for convergence in the iterates to the set X* optimal points and provide summary in Table 2 in the Appendix.
Table 1: Summary of sample complexity results for a-PE. functions (Assumption 3 under average [-smoothness (Assumptions ④ and bounded variance (Assumptions 5). Quantities: Pf. power; = PE constant; x 4/2s o² = variance. The entries of the table show the expected number of
stochastic gradient calls achieve E [f(x)) f*) Ef
Method
Finite sum case
Online case
GD
nk
4-a
SGD
No
No
PAGER
①
+
Vnx
a
(new)
o
g²
(new)
2 Assumptions and Discussion
In this section, we introduce the assumptions we make throughout the paper.
Assumption The gradient of f()) is Lipschitz continuous, that is, for all and y. [[V[(z) - ff(i) & L || - yll. L > 0 is referred to as the Lipschitz constant.
Furthermore, we assume that the objective function f lower bounded, i.e., f inf f(x) > OC. and it satisfies the following inequality
Assumption 2 (global Kt. or global Kurdyya--Lojasiewiiz)) Let Ø R+ IR+ be a continuous function such that ((0) 0 and o²² is convex. The function f()) is said to satisfy global Kurdyka- Lojasiewicz inequality if
[V 2 (f(x)) - for all x E R.a.
(3)
Assumption 3 (a-PL Polyak- There exists E [1,2] and μ >> 0 such that
[+)('))l 2 (2 (f(z) - f³) for all Rd.
(4)
We refer to a as the Pt. power and as the Pt. constant.
It is straightforward to see that the a-PL is special case of KL with @(t) 22 t//0
Connections with other assumptions. Another commonly adopted way to define the global Kł
property is to assume that // (f(x) - [|V](=)]| > 1 for all æ Rd, where p(t) is called
disingularizing function and p'(-) denotes its derivative. Moreover, disingularizing function satisfies the following conditions, it is continuous, concave, p(0) 0, and p'(t) > 0 (35].
the above assumption holds for p(t) = 1 and > 0, then Assumption is satisfied with Pt. power a 1 1- However, a-PE condition is more general since it allows to consider the case a 1.
For example, consider the function of one variable f(x) (e + x=²) 1, then [f'(x:) f(x) for all æ. Thus f(x) satisfies Assumption with a and μ = 1/2. Moreover, this function is
convex, but it does not satisfy inequality of (x) f*) [ 2 1 for any choice of p(t).
We also provide several non-convex problems for which a-PL holds with a E [1, in the Appendix A Other forms of (() also appear in practice, e.g., squared cross entropy loss function satisfies the KL condition with @(t) min(t, vt), (51].

---

The intuition behind the special case a is that the function is allowed to be flat near the set of optimal points X arg min, fz).
Assumption 4 (k-ES, Expected Smoothness of order k). The stochastic gradient estimator gk (z. E) is an unbiased estimate of the gradient V fxx at any given point x and its second moment satisfies
C bk
(199((2, < 2A h([()) - + [VV(())]
for all x E ER"
(5)
where A, B, C are non-negative constants. h: AR=R++ - RR is a concave continuously differentiable function with (t) 2 0, h()) 0. The expectation taken over random vector D. We call by the cost of such estimator.
This assumption encompasses previous assumptions the literature. For instance, it is straightforward to see that estimator satisfies the standard bounded variance assumption [21] when h()) 0, B and by
(5). Gradient estimators with relaxed growth assumption [6 are also special
cases of (5) for h((() O and by = 1. A closely related assumption to the relaxed growth was introduced in [33 which holds when (tt) = O and C in (5) Expected smoothness assumption 33 24 (56] is the closest assumption to k-ES and it holds when h(()) t and by = 1. Notably, ES assumption is satisfied in practical scenarios such as mini-batching, importance sampling and compressed communication [30). More recently, it has been shown that PG method with softmax policies and log barrier regularization can be modeled using ES assumption [56]. Note that due to the first term in (5). i.e., 2.A h(f(z) f*), the second moment can be large when the objective gap at x is large. Such property is not captured by standard bounded variance (Assumption (5). The flexibility and advantages of introducing such additional term are elaborated in detail in the literature
24 30 25 56].
We highlight two special cases for the sequence by: by = ((kT) with 2 0 and 6y O(g") with q > 1. For example, Monte Carlo sampling and mini-batching allow us to design estimators with such {bx J220 sequences. When gradient estimator satisfies Assumption 4 unless by is bounded for all k. it essentially means that we have mechanism to reduce its variance. More precisely, the variance decreases according to the sequence 1/bg- As we show Section if such estimator exists, it results in better convergence rate compared to vanilla SGD and the improvement is captured by sequence bg. On the other hand, usually the access to such estimator comes with a cost proportional to by. e.g., mini-bated setting described in Section 4 Thus refer to 6y the cost of the estimator go {).
3 Stochastic Gradient Method
Algorithm [ summarizzes the steps of a slightly modified SGD which we analyze in this work. We call this algorithm SGD with restarts{] This algorithm updates the point for number iterations within an inner-loop. Note that, in the inner-loop, the step-size remains unchanged and the iterates are updated via Iz+1 I2 (x,, Ex), where 77 is the step-size and (&h120 are independent random vectors. The cost by of the gradient estimator Algorithm [
remain the same within the inner loop of
Algorithm 1: SGD with restarts
1: Initialization: x, T, K, {m k O,..., K -11 1}
2: for k 0, ..... K do
3: 17 - 176
4: for O.....T do
5: x t r (1,
6: return Φ
3.1 Dynamies of SGD
Let (zr heo be the sequence of points generated by the inner loop of Algorithm I and Assumptions 2 are satisfied. Then the dynamics of SGD in the inner-loop of Algorithm is characterized by
Note that if we set K then Algorithm reduces
SGD with constant step-size.
5

---

Lemma 1. Under Assumptions
7 and with constant cost, i.e., b == bb, we obtain
dnp
6e+1 S 6 + an? h(6.)
! 200 (8,)) +
(6)
b
where 6, : -B)(( a LA, d LC :=
Understanding the dynamics of this recursion, allows us to establish the global convergence of SGD. Our approach consists of two main steps: i) Finding the stationary_ point of (6) when the inequality replaced by equality and for a fixed step-size, Tis = 7, which we denote by r(n). ii) Selecting the step-sizes } and sequence {bx F220, such that the corresponding stationary points {r(m) (defined below) converge to zero as k increases.
The stationary point of (6) after replacing inequality with equality must satisfy the equation:
dup 17
anj h(())(
2 (1).
Let us call this stationary point r(n). To complete the first step. we approximate r(1) by polynomial function of 17. In other words, we find y E Rt such that r(7) = (77)).
For the second step of our framework, we should design the stepsizes. Next result introduces set of conditions that allow us to design the stepsizes, which will guarantee convergence. The detailed derivations are presented in the Appendix.
Theorem 1. Suppose there exist O(k-(y), |1 wal < 1. and
0, (22 and & such that T
r(n))
+ anch' (r(m)) na
= wkk
(8)
Then, 6x=0(k (V) and the iteration complexity of Algorithmm with T-M2(1--11mmm) w/) ) is Oley 1/(59)).
As a consequence of Theorem !
we present the iteration complexity of SGD for a-PL functions.
Corollary Consider a special case of Assumption 4 with l(t)) = 1 and by k², where B E (0. 1] and r 2 0. Suppose the objective function f satisfies Assumptions and Let == aB. Then, for any E > 0, Algorithm 7 returns a point x with E [f(x) - -*] S E, after N = K T iterations.
i) 7 = 2 (a- = 2 and 3 = 1), we have
N - T with 7n Okk
ii) 7 < 2, we have
N = O(e, a(r+3) with T/2 O 2-0
r+1 +T) is
7
and
4 4-a
N = Olej 4-am
with mp @kk if 4 1-a-9
To verify the above result empirically, we simulated 8, in 66 throughout all iterations of Algorithms | for different sets of parameters and presented the results in Figure allong with their corresponding convergence rates given in Corollary [ As it is shown in these figure, the above convergence rates correctly capture the behaviour of the dynamics in (6). As an example, in Figure [b), the red solid curve shows the rate of og, i.e., log(5,) as a function of log(k) for y = 1.1, a 1.4, and r = 0.9. Based on Corollary the convergence rate of Algorithm I for this setting is (E, 0.9% or equivalently
log(óz, 6x) = (- 1) log(k) ~ - -1.02 -ogkklog(k) which is shown by red dashed line. Next, we discuss how the results in Corollary generalizes the existing work in the literature.
Comparison to related works. Authors (30 studied the convergence of SGD for 2-PE objectives, under stronger assumption than Assumption 4 More precisely, they assumed an estimator that satisfies Assumption 4 with 0 and h(()) and obtained the convergence rate of O(e This
Stationary point of dynamic is its convergence point.

---

43
6.0
55
58
kopp0
log00
(a) 7
(b) T 0.9.
(c) r = 2.
22 tl/a, T {0, 0.9, 2}, and function of log(k), for given set of parameters and each dashed line shows the corresponding theoretical convergence rate of óR presented in Corollary The numbers assigned to dashed lines indicate the slope of those lines. (a) and (b) verify the case
Figure 1: Behavior of the dynamics in (6) for = (()
different a, 3. Each solid line shows log(Og,
corresponding to S 7/(4- (4- a 7) and (c) verifies the case T > 7/(4 a - 7). Note that the distance between the dashed and solid lines is due to constant factors.
consistent with our rate presented the Corollary optimal 30
worth noting that in this setting, (ee
studied the performance of SGD for 1-Pt. objectives. Assuming that the gradient estimator satisfies Assumption with v and (tt) = they obtain (e, sample complexity. This result can be recovered from Corollary | by setting T 0, y 1. and a 1. Note that in this case, the cost of each iteration is 4 1, which means that the iteration complexity coincides with the sample complexity. We note that our proof technique is different than in [56) and allows to consider more general assumptions. Finally, (20) studied SGD with a-PF. objectives for a E [1,2] under bounded variance 3 W 6y = 1 and obtained similar convergence rate to ours. We recover their result as special case by setting A and
The authors 56
in Corollary if we set T 1 we
θ (k __ However, we highlight that our proof technique different from 200 and more generic since it holds for general Assumption
also recover the same (up to constant) step-sizes
3.2 Sample complexity of SGD
The result of Corollary D suggests that by increasing the cost of the gradient estimator by over the iterations, one achieve better iteration complexity of Algortihm [ In particular, improves with J until it reaches the minimum N -
7 1- and does not change for larger values of T. However, we are merely interested in the iteration complexity in practice, since the computational cost at each iteration can be prohibitively large. A more adequate measure the total computational cost (sample complexity) of the method. It is interesting whether increasing by over the iterations may also result in a better sample complexity for finding an e ooptimal solution, than for the constant choice, e.g., by = 1. The following lemma shows the contrary.
Proposition 1. Let the assumptions of Corollary Thold, by total computational cost (sample complexity) of Algorithm
θ (K*T), T (1). Then the expected is
K-1
for ST -
cost = T
bE
(4 (4-0-1((-1)
for I-0-7
The above result implies that increasing the cost of the gradient estimator with iterations does not Therefore, one can simply select by = 1 (r = 0)
improve the total sample complexity of Algorithm [
and obtain O
sample complexity.
3.3 Tightness of rates in Corollary I
In this section, we show that when - = O, the convergence rates presented in Corollary are tight for the dynamic (6) describing the progress of SGD. More precisely, if there exists function and
7

---

gradient estimator satisfying the assumptions in Corollary such that its corresponding recursive inequality (6) an equality, then its convergence rate, presented in Corollary [ cannot be improved by any choices of stepsizes (Th (1)))220 &20- Next proposition summarizes our results about the tightness of
our convergence rates in Corollary LT
Proposition Consider the following recursion
dnk by
ō6+1 82 aank h((z)) ) +
for all k 2 0,
where a 2 0, d> 0, h(t) 18 with 3 E (0, 11, x(1) = 22aa/ with a E [1, 2]. and by = ((1).
Then 0₁- = ) for any sequence of {mm Moreover, this rate is achieved by the choice
7h O(k 2-0/2
4 Faster Rates with Variance Reduction
Algorithm 2: PAGER (PAGE with restarts)
1: Initialization: To. To. K, {Ax = (m7, Tk. Phs by. b))) & = 0, ...,, K - 1}
2: for == 0..... K 1 do
3: (Io: 5- (3x, gk)
4: (n.p.b, b. b¹) (m], Pk, by (k)
5: fort = 0,...,Tk
do
6: 21+1 2t 179t
7:
Sample X ~ Bernoullip))
8:
if x then
9:
gt+1 1/ Ei= VfEt (I1+1)
10:
else
9c+1 9t 3 Ede Vfe (2e+1)
En Viec (Iz)
11:
12:
Dh+1) + (#++1.9041)
13:
Return: FK
To simplify the exposition of the results in this section, let assume that gl (22,, {t) is constructed explicitly via mini- hini-bbtching 9l (Ie, Ex) by E Vfg; where
[cl...., bb is random vector of independent entries, & are independent for all iterations, [V (vx)) bc are queries provided by oracle such that E[V (æ+)] (xx)) and E[[| Sell (2:z) (xx)) < o² for all / 2 0. The variance of this estimator diminishes linearly in the size of the mini-batch by. i.e., go (2 (x) satisfies
Assumption (k-BV, bounded variance). Let Assumption 4 hold with A 0, B 1 and C 02.
i.e. E
[19 (z. {) {=))
<
bk
Additionally, we assume that we have access to a gradient estimator 9 (x. E). which satisfies the following
Assumption 6 (Average L-smoothness (of order k)). Let g (x. E. I% (gg((a)) and
(y:( be unbiased mini-batch estimators of the gradient of f(-) at points and respectively for shared stochasticity ş² ~ D for each = 1,...,bl, and & = (5) (E)....,"") S")). Define Á(x, y) (x, (v. The average L-smoothness (of order k) holds if there
(v, = T. E I%
exists L > 0 such that IE [xx - A(z, <
vll for all a,y E Idd, where b
A y) = v -f(y)
Remark The Assumption 6 holds several standard settings. For instance, if each Vgg. (x) Lipschitz with constant T. (almost surely or on average), then Assumption holds with L T. Another example is when f()) is of the form (2) and b/g n, then C 0.

---

4.1 PAGER new variance reduction for a-PL objectives
We remark from the analysis of Algorithm T in Section that merely playing with choice of 7 and by (chosen as polynomial functions of k) is not sufficient to improve the convergence, hence, we need to construct more sophisticated gradient estimator and reduce the variance using control variate. Now, we highlight the main algorithmic ingredients of our construction. First, let us describe the variance reduced estimator named PAGE, which will be the main building block for our Algorithm 2 PAGE was introduced and analyzed in [36] and is known to be optimal for finding first order stationary point. Moreover, it is easy to implement and designed via a small modification to mini-batch SGD
1 Ei= Vigt (IL+1);
w.p. P, w.p. 1
91+1 =
gr + Ei= (Veeie) V (I++1) - Veet. (1+)):
where p is a small probability and mini-batch sizes satisfy >> b'.
However, while the method looks simple, the extension of its analysis to a-PL functions faces several difficulties. Therefore, we introduce a new method, which we call PAGER (Algorithm 2) Probabilistic Average Gradient Estimator with parameter Restart. It takes as input the sequence of parameters (AR := (M,- Tx. Ps.- bk. (%) : k 0, ..., K 1), where T3 the length of stage Th Pk, ba, 1/4 step-size, probability, and batch-sizes at stage k. PAGER updates this sequence of and applies PAGE estimator with fixed set of parameters in the inner loop = 0, ..... Ta 1. We will select (A* k20 depending on the PE. power to capture the dependence on the geometry of the problem and establish fast rates for each a in
parameters in the outer loop = 0..... : K
settings I and (2).
4.2 Online case
We present convergence guarantees for Algorithm in the setting ① and defer its formal proof to Appendix C
Theorem 2. Lei f() have the form 1 and satisfy Assumptions
3 (with E [1,
5 and
6 let the sequence.
9 in Algorithm 2 be chosen as b/2 = =0(2- w
Pk O
(2 (2-0 a
by =
(2 22 ). T3 = (2 wit ). 7k = (1). Then, for any Eg > 0 Algorithm
2 returns a point x with
K- Ta = O(Ke, 220 )) iterations, where C/v. The expected
[f 1*] S ef after N = >
total computational cost (sample complexity) O (( + x²2) Es" 2)
Improvement over SGD. Theorem iiplies that PAGER improves the sample complexity of SGD
to Oee )) under a-PL condition for the whole spectrum of parameters a E [1, 2). In the case a = 1, which holds in many interesting applications (see Appendix A for examples), this leads to (e, ?) sample complexity compared to the best known (E, for SGD.
from OEE 4-a
Relation to convex optimization and last iterate convergence. As a consequence of our analysis obtain the optimal sample complexity for convex stochastic optimization under the additional assumption that the iterates of the method remain bounded, i.e., || < D for all 2 O, where 10 For 1-PE objectives, PAGER has O sample complexity. Since the iterates of the algorithm are bounded, convexity (V)(),, x²) 2 f(x) f(x*) implies 1-PE. with = 2D This observation implies convergence of PAGER for convex objectives with O sample complexity, which is known be non- non-improvable for convex stochastic optimization 42
xx E arg ming fz)
*e refer the reader to Appendix C where we explain challenges in the analysis of variance reduction under a-PL condition and show how we overcome these difficulties using the restart strategy.
FFor brevity. in Theorem 2 we define the input sequences up constants hidden in e (-) notation. In fact, our analysis allows to specify these constants and we present detailed derivations in Appendix
Note that this assumption is mild since it holds for the iterates of PAGER, for example, if we additionally assume that f(-) is coercive, i... (x) co for

---

Moreover, we highlight that this result holds for the last iterate of PAGER, while the standard analysis of first order methods for convex functions guarantees convergence for the average iterate [3T]. The last iterate convergence for convex objectives was only recently established for SGD by following an
involved analysis with a careful control of iterates via suffix-averaging scheme (20
4.3 Finite sum case
Let f()) have the finite sum form 2 Then obtain the following result.
Theorem 3. Let S(-) have the form 2 and satisfy Assumptions 3 (with E [1, 2)) and 0 let
the sequences be chosen as pą m+1 b/2 = 1, by = n, Tx = e 12 aik
me ( Then,
for any e, > O, Algorithm 2 returns a point with E [ff()) - eg after -k-110
Ön + VnKee --
iterations, where K = c/P The expected total computational cost (sample
complexity) is Ön + VTKce
The proof is deferred to Appendix C Theorem 3 quaantifies the improvement of PAGER over GD in the finite sum setting in terms of n and over SGD in terms of e,, see Table for comparison. Recall
that GD has sample complexity O -(2-o),
When n is large, we get the improvement order n.. Notice that in the limit a + 2, it matches the best known result for 2-PE objectives [36].
5 Conclusion
We analyzed the complexity of SGD when the objective satisfies global KE inequality and the queries from stochastic gradient oracle satisfy weak expected smoothness. We introduced general framework for this analysis which resulted in sample complexity of O(c-(4-a)//n for SGD with objectives satisfying a-PL condition. We also demonstrated the tightness of this rate under the specific choice of stepsizes. Last but not least, developed modified SGD with variance reduction and restarting (PAGER), which improves the sample complexity of SGD for the whole spectrum of parameters [1,2] 2) and achieves the optimal rate for the important case of 1-PE. objectives.
Acknowledgements
We would like thank Anas Barakat and Anastasia Kireeva for valuable discussions. This work was supported by ETH AI Center doctoral fellowship, ETH Research Grant funded through the ETH Zurich Foundation, and NCCR Automation funded through the Swiss National Science Foundation.
References
[1] Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift. arXiv preprint arXiv:/908.0 00261, 2020.
[2] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A Convergence Theory for Deep Learning via aveerParameterization. Proceedings of International Conference on Muchine Learning, 2019.
[3] Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Ayush Sekhari, and Karthik Srid- haran. Second-order information in non-convex stochastic optimization: Power and limitations. Proceedings of Thirty Third Conference on Learning Theory, 2020.
[4] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Wood- worth. Lower bounds for non-convex stochastic optimization. arXiv preprint 1911v:1912.02336 2019.
[5] Jonathan Baxter and Peter I., Bartlett. Infinite-horizon aaiicy-gradient estimation. Journal of Artificial Intelligence Research, 2001.
10

---

[6] Dimitri P Bertsekas and John N Tsitsiklis. Gradient convergence in gradient methods with errors. SIAM Journal on Optimization, 2000.
[7] Yingjie Bi, Haixiang Zhang, and Javad Lavaei. Local and Global Linear Convergence General Low-rank Matrix Recovery Problems. arXiv preprint arXiv:2104.33344 2021.
[8] Doron Blatt, Alfred O. Hero, and Hillel Gauchman. A convergent incremental gradient method with constant step size. SIAM Journal on Optimization, 2007.
[9] Jérôme Bolte, Aris Daniilidis, and Adrian Lewis. The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM Journal on Optimization, 2007.
[10] Jérôme Bolte. Shoham Sabach, and Mare Teboulle. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, 2014.
[11] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 2018.
[12] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint arXiv:1606.000 540, 2016.
[13] Jingjing Bu, Afshin Mesbahi, Maryam Fazel, and Mehran Mesbahi. LQR through the lens of first order methods: Discrete-time case. arXiv preprint
2019.
[14] Xin Chen, Niao He, Yifan Hu, and Zikun Ye. Efficient Algorithms for Minimizing Composi- tions of Convex Functions and Random Functions and Its Applications in Network Revenue Management. arXiv preprint arXiv:2205.01774, 2022.
[15] Ashok Cutkosky and Francesco Orabona. Momentum- variance reduction non-convex SGD. In Advances in Neural Information Processing Systems, 2019.
[16] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives. In Advances in Neural Information Processing Systems, 2014.
[17] Cong Fang. Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Ncar-Optimal Non- Convex Optimization via Stochastic Path-Integre Integrated Differential Estimator. In Advances in Neural Information Processing Systems, 2018.
[18] Cong Fang, Zhouchen Lin, and Tong Zhang. Sharp analysis for nonconvex sgd escaping from saddle points. In Proceedings of the Thirty-Second Conference on Learning Theory, 2019.
[19] Ilyas Fatkhullin and Boris Polyak. Optimizing static linear feedback: Gradient method. SIAM Journal Control and Optimization, 2021.
[20] Xavier Fontaine, Valentin De Bortoli, and Alain Durmus. Convergence rates and approximation results for SGD and its continuous time counterpart. In Conference on Learning Theory, 2021.
[21] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 2013.
[22] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. The MIT Press, 2016.
[23] Robert Gower, Othmane Sebbouh, and Nicolas Loizou. SGD for structured nonconvex functions: Learning rates, minibatching and interpolation. In Proceedings of International Conference on Machine Learning, 2021.
[24] Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. Proceedings of International Conference on Machine Learning, 2019.
[25] Benjamin Grimmer. Convergence rates for deterministic and stochastic subgradient methods without lipschitz continuity. SIAM Journal on Optimization, 2019,
11

---

[26] Mark Schmidt Hamed Karimi, Julie Nutini. Linear convergence of gradient and proximal- gradient methods under the 2016.
condition. arXiv preprint arXiv:1608. 04636v4,
[27] Jia Hu, Congying Han, Tiande Guo, and Tong Zhao. On the Convergence of Stochastic Splitting Methods for Nonsmooth Nonconvex Optimization. arXiv: Optimization and Control, 2021.
[28] Rie Johnson and Tong Zhang. Accelerating Stochastic Gradient Descent using Predictive Variance Reduction. In Advances in Neural Information Processing Systems, 2013.
(29) Hamed Karimi, Julie Nutini, and Mark Schmidt. Linear convergence of gradient and proximal- gradient methods under the Salyak--.jjasewwiez condition. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2016.
[30] Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. arXiv preprint arXiv:2002.03322, 2020.
[31] Guanghui Lan. First-Order and Stochastic Optimization Methods for Machine Learning. Springer Series in the Data Sciences. Springer International Publishing, 2020.
[32] Lihua Lei, Cheng Ju, Jianbo Chen, and Michael I Jordan. Non-convex Finite-Sum Optimization Via SCSG Methods. In Advances in Neural Information Processing Systems, 2017.
[33] Tadeusz Ležanski. Gradient methods for minimizing functionals. Mathematische Annalen, 1963.
[34] Qunwei Li, Yi Zhou, Yingbin Liang, and Pramod K. Varshney. Convergence analysis of proximal gradient with momentum for nonconvex optimization. In Proceedings of International Conference on Machine Learning, 2017.
[35] Xiao Li, Andre Milzarek, and Junwen Qiu. Convergence of random reshuffling under the Kurdyka-E.ojasieviin inequality. arXiv preprint arXiv:2110.04926, 2021.
[36] Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: simple and optimal probabilistic gradient estimator for nonconvex optimization. arXiv preprint arXiv:2008. 10088/0088 10898, 2021.
[37] Zhize Li and and Jian Li. A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization. In Advances in Neural Information Processing Systems, 2018
[38] Stanistaw Lojasiewicz. Sur le probleme de la division. Studia Mathematica, 1959.
[39] Stanislaw Lojasiewicz. A topological property real analytic subsets. Coll. du CNRS, Les équations aux dérivées partielles, 1963.
[40] Jincheng Mei, Yue Gao, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. Leveraging non- uniformity in first-order non-convex optimization. In Proceedings of International Conference on Machine Learning. 2021.
[41] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the Global Conver- gence Rates of Softmax Policy Gradient Methods. In Proceedings of International Conference on Machine Learning, 2020.
[42] Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. SIAM Review, 1983.
[43] Yurii Nesterov and B.T. Polyak. Cubic regularization of newton method and its global perfor- mance. Mathematical Programming. 2006.
[44] Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. Sarah: A novel method for machine learning problems using stochastic recursive gradient. In Proceedings of International Conference Machine Learning, 2017.
12

---

[45] Lam M. Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient. arXiv preprint arXiv: 770300002, 2017.
[46] Lam M. Nguyen, Marten van Dijk, Dzung T. Phan, Phuong Ha Nguyen, Tsui- Wei Weng, and Jayant R. Kalagnanam. Finite-Sum Smooth Optimization with SARAH. arXiv preprint 1901009900.0744 2019.
[47] Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reduced policy gradient. In Proceedings of International Conference on Machine Learning, 2018.
[48] Boris Teodorovich Polyak. Gradient methods for minimizing functionals. Zhurnal vychislitel noi matematiki i matematicheskoi fiziki, 1963.
[49] Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In Proceedings of International Conference on Machine Learning, 2016.
[50] Nicolas Roux, Mark Schmidt, and Francis Bach. A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets. In Advances in Neural Information Processing Systems, 2012.
[51] Kevin Scaman, Cedric Malherbe, and Ludovic Dos Santos. Convergence rates of non-convex stochastic gradient descent under a generic lojasiewicz condition and local smoothness. In Proceedings of International Conference on Machine Learning. 2022.
[52] David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic Policy Gradient Algorithms. In Proceedings of International Conference Machine Learning, 2014.
[53] Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for weerpparameterize models and accelerated perceptron. In International Conference Artificial Intelligence and Statistics, 2019.
[54] Stephen A Vavasis. Complexity issues in global optimization: a survey. In Handbook of global optimization. Springer, 1995.
[55] Zhe Wang, Kaiyi Yi Zhou, Yingbin Liang, and Vahid Tarokh. SpiderBoost and Momentum: Faster Variance Reduction Algorithms. In Advances in Neural Information Processing Systems, 2019.
[56] Rui Yuan, Robert M Gower, and Alessandro Lazaric. general sample complexity analysis of vanilla policy gradient. arXiv preprint arXiv:2 1433, 2021.
[57] Jinshan Zeng, Shikang Ouyang, Tim Tsz-Kit Lau, Shaobo Lin, and Y. Yao. Global conver- gence in deep learning with variable splitting via the Lojjykaa-ojasiewicz property. arXiv: Optimization and Control, 2018
[58] Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. In Advances in Neural Information Processing Systems, 2018.
[59] Yi Zhou, Yingbin Liang, and Huishuai Zhang. Understanding generalization error of SGD in nonconvex optimization. Machine Learning. 2021.
13


Reviews:
[{"review_id": "pvuYudOuKsT", "reviewer": "Reviewer_ekoT", "summary": "The paper considers the stochastic optimization problem under the $\\alpha$-PL condition and the order k expected smoothness condition. The paper establishes the finite-time convergence for the SGD with a restart algorithm. The result generalizes the previous analysis to a wider range of \\alpha, and the sample complexity is later proven to be tight for restarting SGD. The paper then further improves the sample complexity by incorporating the variance reduction method PAGE into the restarting SGD algorithm.", "questions": "1. How generalized is Assumption 4 compared to the expected smoothness assumption [23,18,47]? Specifically, are there any applications with a concave h(t) other than $h(t)=t$? In addition, are there any applications where $\\alpha \\in (1,2)$?\n\n2. The restart process in Algorithm 1 is important for establishing the sample complexity. Yet it seems there is only one condition on $N=KT$, while the explicit conditions on T and K, which captures the impact of the restarting process, cannot be found in the analysis of section 3.1. It would be great if the authors can explicitly discuss the choice of $T, K$.\n\n3. The main results (Corollary 1, Proposition 1, and Theorem 2-3) hold for \\alpha-PL functions. Why do the authors claim results hold under the more general KL-condition (e.g., in the title, in section 1.1)?\n\n4. What are the theoretical challenges arising from incorporating PAGE into the stage-wise SGD? What is the techniques used to overcome the challenge? What is the reason for using PAGE instead of other variance-reduction methods?\n\nMinor questions:\n\n There are typos in the paper:  ‘Assumption 7’ should be changed to ‘Assumption 6’, and there are question marks in line 620.\n", "limitations": "Yes.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strengths:\n\nThe paper is well-structured and easy to understand. Section 3 offers an interesting analysis of the dynamics of stage-wise SGD under \\alpha-PL condition. The work is sound and thorough—it contains a tight analysis of stage-wise SGD, and in addition, it also provides an analysis of the variance reduced variant and establishes an improved sample complexity for different \\alpha.\n\n* Weaknesses:\n\nThe theoretical generalization claimed by this paper lacks applications, e.g., the generalization of $\\alpha=1 or 2$ to $\\alpha \\in [1,2]$ and the generalization of $h(t)=t$ to a concave $h(t)$ do not include more real-world applications. The extension of stage-wise SGD to PAGER lacks unique challenges therefore the improvement of sample complexity seems expected. \n", "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": "m7pMNdjWT9t", "reviewer": "Reviewer_ws9Y", "summary": "This paper studies the convergence of SGD and PAGE under smoothness, the Kurdyka-Lojasiewicz inequality, and the expected smoothness assumption. The authors show that the iterates generated by SGD follow a dynamic (Lemma 1) that can be tuned to ensure the optimal convergence rate using a certain step size scheme (Theorem 1 and Corollary 1). The authors show that using (with-replacement) mini-batching in the online setting can not improve the convergence rate of SGD further, and that their solution of the SGD dynamic they start with is optimal, although whether the dynamic they start with is optimal is not known. By extending the variance-reduced PAGE algorithm to the KL setting, the authors obtain improved convergence rates for online as well as finite-sum problems.\n", "questions": "- Can your result be used to handle other forms of minibatching as in [1]?\n- What about the dependence on the condition number? It is hard to parse and compare how your condition number dependence differs from prior work.\n- Lemma 4 seems to use a similar step size scheme to [2], can you discuss the similarities/differences?\n\n\n\nPost-rebuttal:\nI thank the authors for their clarifying remarks, I have raised my score as the response is satisfactory.\n\n[1] Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, Peter Richtárik. SGD: General Analysis and Improved Rates, PMLR 97 (2019).\n[2] Sebastian U. Stich Unified Optimal Analysis of the (Stochastic) Gradient Method, arXiv:1907.04232 (2019).\n", "limitations": "See the previous sections for limitations. Potential negative societal impacts are not applicable here.\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Main points:\n- (Strength) The setting studied (convergence under KL and Assumption 4) is very general, it covers several interesting applications that are not covered by existing analysis, and extends the applicability of results on the convergence of SGD and PAGE to several new applications (e.g. those mentioned in lines 44-46).\n- (Strength) The rates provided by the paper (in Corr. 1 and Thm. 3) recover the best prior rates when specialized to the setting of \\(\\alpha = 2\\), and extend these settings for general \\(\\alpha\\) and for SGD, under assumption 4 specifically. This means we gain more generality at no additional cost. Furthermore, generalizing the proofs is not straightforward from the prior work.\n- (Weakness) Sec. 3.3 talks about tightness, but in my opinion it is very misleading. The notion of tightness used here is the tightness of solving the particular recurrence the authors get in (eq. 7); But the result of Lemma 1 may not itself be tight at all.\n- (Weakness) While Sec 3.2 shows that minibatching cannot improve the convergence of SGD, this is only for minibatching with-replacement in the online setting. There are other forms of minibatching that can potentially improve the convergence rate of SGD, see e.g. [1].\n\nOverall: I think that while the paper has some drawbacks, it presents a nice contribution to the literature on SGD and PL. Therefore, I recommend acceptance.\n\n[1] Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, Peter Richtárik. SGD: General Analysis and Improved Rates, PMLR 97 (2019).\n\n", "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": "gvuRcFktbZT", "reviewer": "Reviewer_FAsV", "summary": "This paper studies the complexity of the first-order algorithms with being able to find the global optimal solution of nonconvex objective functions which satisfy the KL condition. This work uses a dynamic system to characterize the evolution of the iterates generated by the proposed algorithms. It is shown in this paper that the derived convergence rate of the variants of SGD is tight and further a variance reduced algorithm is also proposed with a convergence rate of matching the lower bound.", "questions": "1, it is quite confusing that why $g_k$ needs to be dependent on $k$? how does $K$ take the role in the convergence rate?\n\n2, in theorem 1, how many $\\omega_j$s? it seems that there is only one $\\omega_k$ show in eq. 9. How about others?\n\n3, in theorem 1, whether $\\nu$ is also nonnegative?\n\n4, in theorem 1, when $\\zeta$ is large, then $\\delta_k$ shrinks fast but $\\eta_k$ is small, which contradicts the intuition that a large step size gives a fast convergence rate.\n\n5, line 230, when $\\beta=0$, [14] gives the result but corollary 1 requests $\\beta\\in(0,1]$ which means that $\\beta$ cannot be 0 or corollary does not cover the existing results. \n\n6, I agree that the convergence result built upon the last iterate makes more sense, but how does the stochasticity of the gradient estimate take place in the final convergence result?\n\n7, what is the main reason of using the restart strategy? how to compare the step size $\\eta$ with the classic one in SGD? is this choice of the learning rate critical to show the convergence? \n\n8, line 297, how is $D$ obtained in the analysis? is it dependent on $\\mu$ or $L$?\n\n9, in theorem 3, why is the step size $\\eta_t$ dependent on $n$? when $n$ is large, the learning rate will be extremely small, right?\n\n10, why did not include some numerical results?\n\n", "limitations": "The limitations of this work are not mentioned, but I think it is fine as it is a truly theoretical one of discussing some math properties.\n", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThis paper studies a recent popularized question of showing the convergence rate of the first-order algorithms to the global optimal solutions of the nonconvex objective functions under the KL condition. This class of problems indeed covers a wide range of problems in machine learning. Especially, it is good to see that this work has already listed several motivating examples whose objective functions satisfy the KL condition. \n\nMore importantly, this paper provides the convergence rate of a variant of the SGD algorithm in this setting and proposes a new algorithm that can achieve the improved rate to find the global optimal solution. Theorem 1. is general, which gives the iteration complexity of the SGD with restarts under the KL condition.\n\nWeaknesses:\nEven though I believe that this is a truly interesting work and studying a worth well optimization problem, the main concerns are the quality of the presentation, significance of the theoretical results, and numerical justification of the algorithms. To be more specific, please see below.\n\n1, The presentation of this work needs more attention. A thorough comparison between this work and existing ones should be addressed in multiple dimensions, e.g., learning rates, hyper-parameters if any, complexity of the algorithm. Also there are other issues. See the next session.\n\n2,  Although the convergence rate achieved by the SGD with restarts is applicable for general case (KL), the rate matches the existing ones for the PL case which is the most practical setting for applications. How this extension is important to the machine learning problems is not clearly discussed or what are the challenges of showing the convergence beyond PL are not particularly discussed. Note that some discussion included in page 6 mainly focuses on the generality of the assumption 4 rather than KL. So, which assumption or condition is the truly restrict/general one that needs to be conveyed in this work is not clear. \n\n3, it is not surprising that PAGER can achieve a better convergence as the variance reduction has been applied. In practice, VR based algorithm would not perform well in terms of the generalization error. Also, the theoretical results are only applicable to the PL case rather than the KL case, but I presumably the main topic of this work is about showing the iteration complexity of the algorithms under the KL condition. \n\n4, Both alg.1 and alg.2 are variants of the existing ones. It is necessary to showcase the numerical performance of these algorithms with a comparison with the baselines.\n\n\n============================= After rebuttal ====================\n\nThanks for the authors' detailed response. I have increased the score. The concern regarding the small step size remains, which is not about the correctness of the proof but a concern about the dependence of the step size on the hyper-parameters, e.g., $n$.\n", "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": "EBD57DQqbdF", "reviewer": "Reviewer_cXuP", "summary": "The paper provides rates of convergence under various assumptions for global KL functions - which is rich enough to include many popular loss functions in practice. The authors provide rates for SGD algorithm, and then provide a new algorithm called PAGER which enjoys improved rates due to variance reduction. They then show how to apply this algorithm for finite sum optimization problems. \n", "questions": "Please refer to other sections! ", "limitations": "No foreseeable negative societal impacts. ", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The class of global KL is fairly rich and stochastic optimization is not well understood in this class. \n\nWeaknesses: I found the contributions of the paper to be a bit underwhelming and lacking novelty. Let me explain: \n\n1. The upper bound provided in Corollary 1 and the lower bound in Proposition 1 do not fit well with each other. The lower bound only holds for a particular step-size sequence and does not say much about the minimax rates for SGD for this class. \n\n2. Given the above, I am not sure how valuable is the contribution of improved rates under variance reduction. \n\n3. Lemma 2 is vacuous as it seems to be based on just comparing upper bounds which may not be tight. \n\n\n4. The theoretical ideas used in the SGD analysis, variance reduction, etc are not novel. In the end, the paper seems to be combining various previously known technical ideas, without any new high-level algorithmic insights. The paper seems to be missing an important reference: Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations, Arjevani et. al. 2020. \n\n5. There are still many gaps in the corresponding rates for KL functions. \n\n", "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