Escape saddle points by a simple gradient-descent based algorithm
Authors: Chenyi Zhang
Tongyang Li
Venue: NeurIPS 2021 Poster (2021)
Keywords: saddle points
gradient descent
stochastic optimization
nonconvex optimization
negative curvature finding

Abstract: Escaping saddle points is a central research topic in nonconvex optimization. In this paper, we propose a simple gradient-based algorithm such that for a smooth function $f\colon\mathbb{R}^n\to\mathbb{R}$, it outputs an $\epsilon$-approximate second-order stationary point in $\tilde{O}(\log n/\epsilon^{1.75})$ iterations. Compared to the previous state-of-the-art algorithms by Jin et al. with $\tilde{O}(\log^4 n/\epsilon^{2})$ or $\tilde{O}(\log^6 n/\epsilon^{1.75})$ iterations, our algorithm is polynomially better in terms of $\log n$ and matches their complexities in terms of $1/\epsilon$. For the stochastic setting, our algorithm outputs an $\epsilon$-approximate second-order stationary point in $\tilde{O}(\log^{2} n/\epsilon^{4})$ iterations. Technically, our main contribution is an idea of implementing a robust Hessian power method using only gradients, which can find negative curvature near saddle points and achieve the polynomial speedup in $\log n$ compared to the perturbed gradient descent methods. Finally, we also perform numerical experiments that support our results.


Escape saddle points by a simple gradient-descent based algorithm
Chenyi Zhang'
Tongyang Lia3,4
Institute for Interdisciplinary Information Sciences, Tsinghua University, China
Center Frontiers of Computing Studies, Peking University, China
School of Computer Science, Peking University, China Center for Theoretical Physics, Massachusetts Institute of Technology, USA
Abstract
Escaping saddle points is central research topic in nonconvex optimization. In this paper, we propose simple gradient- based algorithm such that for smooth function f: R" + R, it outputs an e-approximate second-orde orddrr stationary point Ölog 175 itcrations. Compared the previous statc-of-the-an algorithms by Jin al. with Ö(log* n/e²) Ólogg n2/e1.75) iterations, our algorithm poly- nomially better terms log ni and matches their complexitics terms I/e.. For the stochastic setting, our algorithm outputs an e-approximate second-order stationary point in Ólog" n//"* iterations. Technically, our main contribution is an idea of implementing robust Hessian power method using only gradients, which find negative curvature near saddle points and achieve the polynomial speedup in log n compared the perturbed gradient descent methods. Finally, we also perform numerical experiments that support our results.
1 Introduction
Nonconvex optimization is central research area in optimization theory, since lots of modern ma- chine learning problems can be formulatedd in models with nonconvex loss functions, including deep neural networks, principal component analysis, tensor decomposition, elc. In general, finding global minimum of nonconvex function NP-hard the worst case. Instead, many theoretical works focus on finding a local minimum instead of a global one, because recent works (both empiri- cal and theoretical) suggested that local minima are nearly as good as global minima for significant amount well-studied machine learning problems; see c.g. [4, 12, 14, 15, 17, 18]. On the other hand, saddle points are major obstacles for solving these problems, not only because they are ubiqui- tous in -igh-dimensooall settings where the directions for escaping may be few (see e.g. [5, 8, 11]), but also saddle points can correspond highly suboptimal solutions (sec c.g. [19, 281).
Hence, one of the most important topies in nonconvex optimization is escape saddle points. Specifically, we consider a twice-dificrentiaall function f R" + R such that
f is f-smooth:
[x1) ( < f||i Xell
Vx1, X2 E
f is H-Hssia Lipschitz: [x(x)) - H(xx))l S p|x Xall
Vx,, E R":
here the Hessian f. The goal is to find an e-approximate second-order stationary point x,: [V)(x))] S
Amia (M(,))((x))) 2 Vpc.
(1)
"orresponniig author: Email: tongyangli @ pku.edu.cn
We can ask for (c1, -approx. recond-orded stationary point || fx)]] and Amiia (V fx))) -c general. The scaling was adopted standard in literature [1. 6, 10, 20, 21, 22, 26, 29, 30, 31].
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

In other words, at any e-approx, second-order stationary point x,, the gradient small with norm being at most and the Hessian is close to be positive semi-definite with all its eigenvalues 2 -yPe.
Algorithms for escaping saddle points are mainly evaluated from two aspects. On the one hand, considering the enormous dimensions of machine learning models in practice, dimension-free or almost dimension-free (i.e., having poly(log n) dependence) algorithms are highly preferred. On the other hand, recent empirical discoveries in machine learning suggests that it is often feasible to tackle difficult real-world problems using simple algorithms,, which can be implemented and maintained more easily in practice. On the contrary, algorithms with nested loops often suffer from significant overheads in large scales, or introduce concerns with the setting of hyperparameters and numerical stability (see e.g. [1, 7J., making them relatively hard to find practical implementations.
It is then natural to explore simple gradient- based algorithmss for escaping from saddle points. The reason we do not assume access to Hessians is because its construction takes Q(x²²) cost in general, which computationally infeasible when the dimension is large. A seminal work along this line was by Ge et al. [12], which found an e-approximate second-order stationary point satisfying (1) us- ing only gradients in (poly(n,, (n. 1/e)) iterations. This is later improved to be almost cimenssion-free Ö(log" 4 n//²) in the follow-up work [20],2 and the perturbed accelerated gradient descent algo- rithm [22] based on Nesterov's 's accelerated gradient descent [27] takes Ö(log" n/ee n//e1-75) iterations. However, these results still suffer from a significant overhead in terms of log n. On the other di- rection, Refs. [3, 25, 30] demonstrate that an c-approximate second-order stationary point can be find using gradients in Óllog (/llgn//c..00 12/c1.79) iterations. Their results are based on previous works [1, 6] using Hessian-vectto products and the observation that the Hessian-vector product can be upproxi- mated via the difference of two gradient queries. Hence, their implementations contain nested-loop structures with relatively large numbers of hyperparameters. It has been open question whether it is possible to keep both the merits of using only first-order information as well as being close to dimension- free using simple, muddiett-bsscd algorithm without nested-loop structure [23]. This paper answers this question in the affirmative.
Contributions. Our main contribution is simple, single-loop; and robust gradient-based algo- rithm that can find an e-approximate second-order stationary point of a smooth, Hessian Lipschitz function f: I + R. Compared to previous works [3, 25, 30] exploiting the idea of gradient-base Hessian power method, our algorithm has single-loope,, simpler structure and better numerical stability. Compared to the previous state-of-lhe-art results with single-kooped structures by [22] and [20, 21] using Öllg" n/55-75 or Ö(log* n/ee2) iterations, our algorithm achieves polynomial speedup in log n:
Theorem (informal). Our single-looped algorithm finds an e-approximate second-order station- ary point in Õ(log 7/95 iterations.
Technically, our work is inspired by the perturbed gradient descent (PGD) algorithm in [20, 21] and the perturbed accelerated gradient descent (PAGD) algorithm in [22]. Specifically, PGD applies gradient descents iteratively until il reaches point with small gradient, which can be a potential saddle point. Then PGD generates a uniform perturbation in small ball centered that point demonstrated that, with an appropriate choice of the
and then continues the GD procedure. perturbation radius, PGD can shake the point off from the neighborhood of the saddle point and converge to second-order stationary point with high probability. The PAGD in [22] adopts a similar perturbation idea, but the GD replaced by Nesterov's AGD [27].
Our algorithm built upon PGD and PAGD but with one main modification regarding the pertur- bation idea: it is more efficient to add a perturbation in the negative curvature direction nearby the saddle point, rather than the uniform perturbation in PGD and PAGD, which is compromise since we generally cannot access the Hessian at the saddle due to its high computational cost. Our key observation lies in the fact that we do not have to compute the entire Hessian to detect the negative curvature. Instead, in a small neighborhood of saddle point, gradients can be viewed as Hessian- vector products plus some bounded deviation. In particular, GD near the saddle with learning rate 1/L is approximately the same as the power method of the matrix (I - H/E). As a result, the most negative eigenvalues stand out in GD because they have leading exponents in the power method, and thus it approximately moves along the direction of the most negative curvature nearby the sad-
The Ô notation omits pogy-logari terms, i... Ö(g) O(g poly(log g)).

---

dle point. Following this approach, we can escape the saddle points more rapidly than previous algorithms: for a constant c, PGD and PAGD take (loog n) iterations to decrease the function value by ( log" n) and ( log" n) with high probability, respectively: on the contrary, we can first take (log n) iterations to specify a negative curvature direction, and then add a larger perturbation in this direction to decrease the function value by O(1). See Proposition 3 and Proposition 5. After escaping the saddle point, similar PGD and PAGD, we switch back to GD and AGD iterations, which are efficient to decrease the function value when the gradient is large [20, 21, 22].
Our algorithm is also applicable to the stochastic setting where we can only access stochastic gra- dients, and the stochasticity is not under the control of our algorithm. We further assume that the stochastic gradients are Lipschitz (or equivalently, the underlying functions are gradient-Lipshiit. see Assumption 2), which is also adopted in most of the cxisting works; see e.g. [9, 20, 21, 35]. We demonstrate that a simple extended version of our algorithm takes (logg n) iterations to detect a negative curvature direction using only stochastic gradients, and then obtain an 92(1) function value decrease with high probability. On the contrary, the perturbed stochastic gradient descent (PSGD) algorithm in [20, 21], the stochastic version of PGD, takes O(log" " n) iterations to decrease the function value by (11 log" n) with high probability.
Theorem 2 (informal). In the stochastic setting, our algorithm finds an c-approximate second-order stationary point using Ö(ogg n/(²)) iterations via stochastic gradients.
Our results are summarized Table 1. Although the underlying dynamics in [3, 25, 30] and our al- gorithm have similarity, the main focus of our work is different. Specifically, Refs. [3, 25, 30] mainly aim at using novel techniques to reduce the iteration complexity for finding second-order stationary point, whereas our work mainly focuses negative curvature finding methods while preserving their advantage in iteration complexity, since a much simpler structure accords with empirical observations and enables wider applications. More- over, the choice of perturhation in [3] based the Chebyshev approximation theory, which may require additional nested-looped structures to boost the success probability. In the stochastic set- ting, there are also other results studying nonconvex optimization [16, 24, 32, 37, 13, 33, 36] from different perspectives than escaping saddle points, which are incomparable to results.
reducing the number of loops and hyper- paraamerrresters of
Setting
Reference
Oracle
Iterations
Simplicity
Non-stochastic
[1. 6]
Hessian- -eeston product
Ologn/ee2.
Nested-loop
Non-stochastic
[20, 21]
Gradient
Ö(log" n/(2)
Single-loop
Non-stochastic
[22]
Gradient
Ollog" 2 n//2..5)
Single-loop
Non-stochastic
[3, 25, 30]
Gradient
O(log e
Nested-loop
Non-stochastic
this work
Gradient
Olog 1.75
Single-loop
Stochastic
[20, 21]
Gradient
O(log 15 n/e²)
Singlc-loop
Stochastic
[10]
Gradient
Olog n/5
Single-loop
Stochastic
[3]
Gradient
Ö(lg" n/e3.0
Nested-loop
Stochastic
[9]
Gradient
Ollog n/e²)
Nested-loop
Stochastic
this work
Gradient
Ö(log" n/e*)
Single-loop
Table 1: A summary of the state-of-the-ar results on finding approximate second-order stationary points by the first-order (gradient) orucle. Iteration numbers are highlighted in terms of the dimension n and the precision
is worth highlighting that our desceett-deseent based algorithm enjoys the following nice features:
Simpliciry: Some of the previous algorithms have nested-loop structures with the concern of practical impact when setting the hyperparameters. In contrast, our algorithm based on negative curvature finding only contains a single loop with two components: gradient descent (includ- ing AGD or SGD) and perturbation. As mentioned above, such simple structure is preferred in machine learning, which inereases the possibility of our algorithm to find real-world applications.
Numerical stability: Our algorithm contains an additional renormalization step at each iteration when escaping from saddle points. Although in theoretical aspect renormalization step does not affect the output and the complexity of our algorithm, when finding negative curvature near

---

saddle points enables us to sample gradients in a larger region, which makes our algorithm more numerically stable against floating point error and other errors. The introduction of renormaliza- tion step is enabled by the simple structure of our algorithm, which may not be feasible for more complicated algorithms [3, 25, 30].
Robustness: Our algorithm is robust against adversarial attacks when evaluating the value of the gradient. Specifically, when analyzing the performance of our algorithm near saddle points, we essentially view the deflation from pure quadratic geometry external noise. Hence, the effectiveness of our algorithm unaffected under external attacks as long the adversary bounded by deflations from quadratie landscape.
Finally, we perform numerical experiments that support polynomial speedup in log We per- form our negative curvature finding algorithms using GD or SGD in various landscapes and general classes of nonconvex functions, and use comparative studies to show that our Algorithm and Algo- rithm 3 achieve a higher probability of escaping saddle points using much fewer iterations than PGD and PSGD (typically less than 1/3 times of the iteration number of PGD and 1/2 times of the iter- ation number of PSGD, respectively). Moreover, we perform numerical experiments benchmarking the solution quality and iteration complexity of algorithm against accelerated methods. Com- pared to PAGD [22] and even advanced optimization algorithms such as NEON+ [30], Algorithm possesses better solution quality and iteration complexity in various landscapes given by more gen- eral nonconvex functions. With fewer iterations compared to PAGD and NEON+ (lypically less than 1/3 times of the iteration number of PAGD and 1/2 times of the iteration number of NEON+, respectively), our Algorithm 2 achieves higher probability of escaping from saddle points.
Open questions. This work leaves a couple of natural open questions for future investigation:
Can we achieve the polynomial speedup in log n for more advanced stochastic optimization algo- rithms with complexity (ppoyy(og n)/e* (..)) [2, 3, 10, 29, 31] or O(poly(logn)/e [9, 34]?
How is the performance of our algorithms for escaping saddle points in real-world applications, such as tensor decomposition [12, 17], matrix completion [14], etc.?
Broader impact. This work focuses on the theory of nonconvex optimization, and as far as we see, do not anticipate its potential negative societal impact. Nevertheless, it might have pos- itive impact for researchers who are interested understanding the theoretical underpinnings of (stochastic) gradient descent methods for machine learning applications.
Organization. Section 2, we introduce our gradient- based Hessian power method algorithm for negative curvature finding, and present how our algorithms provide polynomial speedup in log n for both PGD and PAGD. In Section 3, present the stochastic version of our negative curvature finding algorithm using stochastic gradients and demonstrate its polynomial speedup log n for PSGD. Numerical experiments are presented in Section 4. We provide detailed proofs and additional numerical experiments in the supplementary material.
2 A simple algorithm for negative curvature finding
We show how to find negative curvature near a saddle point using gradient- basedd Hessian power method algorithm, and extend it to a version with faster convergence rate by replacing gradient de- scents by accelcrated gradient descents. The intuition works as follows: in a small enough region nearby a saddle point, the gradient can be approximately expressed as a Hessian-vector product for- mula. and the approximation error can be efficiently upper bounded, see Eq. (6). Hence, using only gradients information, we can implement an accurale enough Hessian power method find negative cigenvectors of the Hessian matrix, and further find the negative curvature nearby the saddle.
2.1 Negative curvature finding based on gradient descents
We first present an algorithm for negative curvature finding based on gradient descents. Specifically, for any R with Ania (H()) S -ype, it finds unit vector such that è7 H(X)è S -VPe/4.

---

Algorithm 1: Negative Curvature Finding(X, J)..
1 Yo U-nnffom([3 (2)B)x)rr)) (r)) where Bx(r) the norm ball centered at & with radius r; for 1 = 1..... g do
y Il all 4 Output y
1/ Vf(())
R2 is E-smooth and p-Hessian Lipschitz. For any 0 < 60 I, we specify our choice of parameters and constants we use as follows:
Proposition 3. Suppose the function
88
8
T
log
d0-
(2)
Vpc
60
TTpe
Suppose that & satisfies Amin (V*)(x)) S ppc. Then with probability at least 8g. Algorithm 1 outputs unit vector é satisfying
e e"H(x)ēs /pp/4.
using ((7)= =0
log vpc
iterations, where H. stands for the Hessian matrix of function f-
Proof. Without loss of generality assume & 0 by shifting R such that & is mapped to 0.
Define a new r-dimensional function
hy(x))== f(x) (V)(
(4)
for the ease of our analysis. Since (V)(O),x; x) is a linear function with Hessian being 0, the Hessian of h equals the Hessian of f. and (x) is also ê-smooth and p-Hessian Lipschitz. In addition, note that (0) V f()) - (()) = 0. Then for all x E IR",
[ (H(Ex) H(()): x
(
H({x) dg H(O)x
---
Furthermore, due to the p-Hessian Lipschitz condition of both f and hy, for any & E [0, 1] we have [[H(Ex) - H(O)] $ p||x|| which leads to
[ *(0)x S |||x||
(6)
Observe that the Hessian matrix O0) admits the following eigen-
H(O)
where the set {u, Da forms an orthonormal basis of IR" Without loss of generality, we assume the eigenvalues X1, .2.....7. An corresponding un u2..... ........ Un satisfy
Ao
An:
(8)
in which d <PC. If X, < /pe/2, Proposition holds directly. Hence, we only need to prove the case where An
2, in which there exists some p' with
Ap vpc Apti, A S /pc/2 Apt+1-
We use 6lI, G1 separately denote the subspace R" spanned by {u) U...... J (up+1, Up422.... un), and use G 6 to denote the subspace of R" spanned by (ui, u ) {up +1, Up-2u ....., Un. Furthermore, we define Yt, EL (x),y)) us.
Yt.L En (o) us Yt,jl Σn' (1) un ye.r == Ein (u:yy) y1) respectively denote the component of in Line 3 in the subspaces G 6,, 161,6,. G and let a == ||vegl//llvddl
Observe that
Pr 0o 2 So Pr (Io..l/rr 2 6o v//
(10)

---

where Vo.1 == (ur, yo) denotes the component of Yo along un Consider the case where ag z v m/n, which can be achieved with probability
R do Vol(BB (1))
Pr
60 2
21
60
n
60-
(11)
n
(1)(
π
We prove that there exists some with S to S J such that
1 I vpe/(8e).
(12)
Assume the contrary, for any 1 i I, we all have IIve.= /TE/(8E). Then l
satisfies the following recurrence formula:
|y++1,111 || - (1 + /pe/
||rا S (1 VPE/(2)))))))))) + | 1/
(13)
where = of
lys/l (Vhy(T3e/llyell) H(0) (rye/ and |||1//Iy=+1 - pr/L due to (6). Hence,
1144,1111 $ (1+
v/p
+
||||
| - (1+
vpc -
8pr
1y
(14)
28
|
2
Vp
which leads
Iyye, S |/ + (2)/ + Spr/
& I1 45/pt/(88)+ V [9)-
(15)
Similarly, we can have the recurrence formula for [yy,lll:
|y++1,1| 2 (1+ /pc/ /20))2)
|| 2 (1 vpc/(20) |xxl
(16)
Considering that ||lll/Ixx+1 S pr/E due to (6), we can further have
|1 2 (1 vpc/(2() pr/(az())l>>)ll
(17)
Intuitively, |yy+ should have faster increasing rate than ||ye, in this gradient-based Hessian power method, ignoring the deviation from quadratic approximation. As a result, the value the value o₁ n /ly,,nll/llss //y/// || should be con-decreasing. It is demonstrated in Lemma 17 in Appendix B that, even if we count this deviation in, 0r can still be lower bounded by some constant Ominn:
50 04 auin
4 V n'
vists
(18)
by which we can further deduce that
lly |I 2 IIvo. + vpe/l- pri(amia O)²
|No. + +TVP<
AISIA (19)
Observe that
1
1 (1+ 5
5
5 p pe (8E)
3
/pc
| ( 7VPE/8(((
(20)
|| II
8g
S
Since lly S Ily we have 1t....l//lll>>>> S /p</ (8E), contradiction. Hence, there here
exists some fo with to S I such that t. I1//ly /pc/ (8E). Consider the normalized
vector = /t,/r, we use ê. and épr to separately denote the component of é in G', and 6/. Then,
| - (8E) whereas || 2 1 - (E/(8 Then,
e H(0) (ē ) (()) + ép) of. H(0) + oT. ē
(21)
since H( 6 and (()) 6 Due the (-smoothness of the function, all eigenvalue of the Hessian matrix has its absolute value upper bounded by & Hence.
+(O)@e S elleT l12 pc/(6)) Further according to the definition of G|,, we have o H())ēp S / 1//2.
(22)
(23)
Combining these two incqualities together, we can obtain
è7 H(()) = o H()ee_ o é0)) S /pell 112/2 pe/(6119) - Upe/4.
(24)
In practice, the value of [|ye|] can become large during the execution of Algorithm 1. To fix this, we can renormalize y: to have fz-norm at the ends of such iterations, and this does not influence the performance of the algorithm.
Remark 4.

---

2.2 Faster negative curvature finding based on accelerated gradient descents
this subsection, we replace the GD part in Algorithm by AGD obtain an accelerated negative curvature finding subroutine with similar effect and faster convergence rale, based on which we fur- ther implement our Accelerated Gradient Descent with Negative Curvature Finding (Algorithm 2). Near any saddle point R" with Amin (H(()) S -vp,, Algorithm 2 finds a unit vector such that é" H(xjē= /pe/4.
Algorithm 2: Perturbed Accelerated Gradient Descent with Accelerated Negative Curvature
Finding(Xo: Xo, 17, 7,8. ,','')
(perturb
2o < Xg. Xo. 0: 0. 1. T do
for
3
if / S and t Epennnt > I then
X (ni (Bx()")) where Uniform(Bx("") is the f2-norm ball centered & with radius r', 2e X4. (x(),, perturb < 8;
X; + Uniform
if t perzunt g' then x x1-
X. x (1)) V
f218)
ê. + X
X,+1 t - ((Z() - C):
Vi+1 X++1 Xti
21 f 1 + 1)
12
if fportubb o 0 and f tporunt < g' then
13
Ze+1 & x r',
T x X++1 C-
Ze+1
X 1-
14
else
15
f (x411 S f(((+1) + (Vf 2441) - - X 2| then
16
(X441 V(41)
V)-1,
Ze41 <- Xx+1 0)v,+1;
The following proposition exhibits the effectiveness of Algorithm 2 for finding negative curvatures near saddle points:
Proposition Suppose the function f: 12" - is E-smooth and p-Hessian Lipschitz. For any
0 < 60 S 1, we specify our choice of parameters and constants we use as follows:
=
1
0 = (pe)
g'
(pe) log
32v2
(
48
AVE
pc
7 0²
8 = ?
r' SuE π
(25)
4p
32
V pn
then for a point & satisfying Amin 2 ((x) I -Vpc. if running Algorithm 2 with the uniform
perturbation in Line 5 being added at &. = O, the unit vector è in Line 7 obtained after T' iterations satisfies:
H[(}e -
-vp//4)
60-
(26)
The proof of Proposition 5 is similar the proof of Proposition 3, and is deferred to Appendix B.2.
2.3 Escaping saddle points using negative curvature finding
this subscction, we demonstrate that our Algorithm and Algorithm 2 with the ability to find negative curvature near saddle points can further escape saddle points of nonconvex functions. The
(NCE) subroutine was originally introduced [22, Algorithm 3] and is called when detect that the current momentum v, coincides with a negative curvature direction z,, this case, reset the momentum v, and decide whether to exploit this direction based on the value of v.
This NegativeCuraauueEEXlliiiit

---

intuition works follows: we start with gradient descents or accelerated gradient descents until the gradient becomes small. At this position, we compute the negative curvature direction, described by a unit vector é, via Algorithm I or the negative curvature finding subroutine of Algorithm 2. Then, we add perturbation along this direction of negative curvature and go back gradient descents or accelerated gradient descents with an additional MegativeCurvatureExllooaai Footnote 3). It has the following guarantee:
subroutine (see
Lemma 6. Suppose the function f R R is t-smooth and p-Hessian Lipschitz. Then for any point X RR, there exists a unit vector è satisfying e" H((x))e S /Pt where H. stands for the
Hessian matrix of function f. the the following inequality holds:
f(x0-
f2(10) 415 (x))
- s(x0))
(27)
384
where f/ stands for the gradient component of f along the direction é
Proof. Without loss of generality, we assume X O. We can also assume (V)(0), è) S this is not the case we can pick - instead, which still satisfics -() < v In practice, to figure out whether we should use é or é, we apply both of them in (27) and choose the one with
4
smaller function value. Then, for any x zgê with some ze > 0, we have 8² (x)
//c + pre
0ug
due to the p-Hessian Lipschitz condition f. Hence,
0f (x) S (1( Dra
ypc Ie parz
(28)
by which we can further derive that
((rl) f(0) s f1(0)
p
v
(29)
3"
Settings xe = / gives (27).
We give the full algorithm details based on Algorithm in Appendix C.I. Along this approach, we achieve the following:
Theorem (informal, full version deferred to Appendix C.3). For any e > 0 and a constant < 8 I I, Algorithm 2 satisfies that at least one of the iterations will be e-approximate second- order stationary point in
0( (((((50)
log
(30)
e1.76
iterations, with probability at least 1 - 8, where f is the global minimum of f.
Intuitively, the proof of Theorem 7 has two parts. The first part is similar to the proof of [22, Theorem 3], which shows that PAGD uses Ö(log" n//c--75 iterations to escape saddle points. We show that there can be at most Ö(A, /c.77) iterations with the norm of gradient larger than e using almost the same techniques, but with slightly different parameter choices. The second part is based on the negative curvature part of Algorithm 2, our accelerated negative curvature finding algorithm. Specifically, at each saddle point we encounter, we can take Õ O(logn/e n//+/11 iterations to find its negative curvature (Proposition 5), and add perlurbation in this direction decrease the function value by O 1.5) (Lemma 6). Hence, the iterations introduced by Algorithm 4 can be at most Ö( log fnier) = Ōlog (llogn/c.755 which is simply an upper bound on the overall iteration number. The detailed proof is deferred to Appendix C.3.
Remark 8. Although Theorem 7 only demonstrates that our algorithms will visit some approximate second-order stationary point during their execution with high probability, straightforward to identify one of them if we add termination condition: once Negative Curvature Finding (Algorithm 1 or Algorithm 2) is applied, we record the position Xt, and the function value decrease due to the following perturbation. If the function value decrease is larger than 381 V as per Lemma 6, then the algorithmms make progress. Otherwise, Xt, is an e-approximate second-order stationary point with high probability.

---

3 Stochastic setting
In this section, we present stochastic version of Algorithm using stochastic gradients, and demon- strate that can also be used to escape saddle points and obtain a polynomial speedup in log n compared to the perturbed stochastic gradient (PSGD) algorithm in [21].
3.1 Stochastic negative curvature finding
In the stochastic gradient descent setting, the exact gradients oracle Vf of function cannot be accessed. Instead, we only have unbiased stochastic gradients gxx; 0) such that
fx)) (Ee-D(g((x; 0)]
Vx E R"
(31)
where D stands for the probability distribution followed by the random variable 0. Define
<(x:0) := g(x: 0) V.((x)
(32)
be the error term of the stochastic gradient. Then, the expected value of vector <(x: 0) at any x C _2" equals Further, we assume stochastic gradient g(x; 8) also satisfies the following assumptions, which were also adopted in previous literatures; see e.g. [9, 20, 21, 351.
Assumption 1. For any E RR, the stochastic gradient g(x;0) with 0 ~ DD satisfies: Pr[[Ilg(x:)) 0)- fx(())l 2 t)] S 2 eexp(-f/(22')
Vt E R.
(33)
Assumption For any E sup)(D), g(x; 0) is ê-Lipschitz for some constant E: (l((x100) 0) g(x2: 0) - E x x2ll- Vx1,X2 C IR".
(34)
Assumption 2 emerges from the fact that the stochastic gradient is often obtained as exact gradient of some smooth function.
g(x;0) V 0)
(35)
this case, Assumption 2 guarantees that for any 0 ~ D, the spectral norm of the Hessian of f(x: 0)
is upper bounded by f. Under these two assumptions, we can construct stochastic version Algorithm 1, as shown in Algorithm 3.
Algorithm 3: Stochastic Negative Curvature Finding(Xo r., Ts. m))
Yo + 0, Lo
2 for = I.... T,
Sample {0(1) ((2) _(m)) D;
g(y:-1)
Li=1 (g(xo y1-1; 0(0) g(xo: 060))):
& ~ N0 1)
Yt yt yt 1 (gly: 1) &t/ 1),
L, + Lyell L and yı + y: T
7 Output y /Te.
Similar the non-stochastic setting, Algorithm be used escape from saddle points and oblain polynomial speedup log n compared to PSGD algorithm [21]. This is quantitatively shown in the following theorem:
Theorem (informal, full version deferred to Appendix D.2). For any > 0 and constant 0 8 S L, our algorithm' based Algorithm using only stochastic gradient descent satisfies that least one of the iterations Xt will be an c-approximate second-order stationary point in
((((x)))5) log"
(36)
iterations, with probability at least 1 1 8, where f is the global minimum of f.
*Our algorithm based on Algorithm 3 has similarities to the Neon2reline algorithm in [3]. Both algorithms find second-order stationary point stochastic optimization in Ó(log² n/c²) iterations, directed perturbations based results of negative curvature finding. Nevertheless. our algorithm enjoys simplicity by only having single loop, whereas 2 has nested loop for boosting their confidence.
both apply

---

4 Numerical experiments
In this section, we provide numerical results that exhibit the power of our negative curvature finding algorithm for escaping saddle points. More experimental results can be found in Appendix E. All the experiments are performed on MATLAB R2019b on a computer with Six-Core Intel Core i7 processor and 16GB memory, and their codes are given in the supplementary material.
Comparison between Algorithm and PGD. We compare the performance of our Algorithm I with the perturbed gradient descent (PGD) algorithm in [21] on test function f21 T22 16 i
1
1 2 I 1
with a saddle point at (0, 0). The advantage of Algorithm is illustrated in Figure 1.
g 2
So00
Sucos
byp Socp
(C:00)
03607 1A5A
R.40)
valo
Figure I: Run Algorithm and PGD landscape f(1 x2)
11 2. 2.22- Parameters: vj 0.05
(step length), r 0.1 (ball radius in PGD and parameter in Algorithm 1). M 300 (number of samplings). Left: The contour of the landscape is placed the background with labels being function values. Blue points represent samplings of Algorithm 1 time step Exeen 15 and ENCOD = 30, and red points represent samplings of PGD time step fRGD 45 and tyan 90. Algorithm transforms distribution a distribution concentrating on two points indicating negative curvature, and these figures represent intermediate states of this process. It converges faster than PGD even when ANOGD & fyaD- Right: histogram descent values obtained by Algorithm and PGD, respectively. Set INCGD fecD = Although run three times of iterations PGD, there are still over 40% of gradient descent paths with function value decrease no greater than 0.9, while this ratio for Algorithm is less than 5%.
initial uniform-circle
and
Comparison between Algorithm 3 and PSGD. We compare the performance of our Algo- rithm 3 with the perturbed stochastic gradient descent (PSGD) algorithm in [21] on a test function (21 = (x] //2 3r, + (aq + =²)² /2. Compared to the landscape of the previous ex- periment, this function more deflated from a quadratic field due to the cubic terms. Nevertheless, Al Algorithm 3 still possesses a notable advantage compared to PSGD as demonstrated in Figure 2.
Socus Serbebe-
30 Xibeebeee
Colon serplingg
comple
serging
3z + (af + + Parameters: 1) 0.02 (step length), 0.01 (variance PSGD and Algoritmm 3), M 300 (number of samplings). Left: The contour of the landscape is placed on the background with labels heing function values. Blue points represent samplings
Figure 2: Run Algorithm 3 and PSGD landscape f211
time step fsscaD 15 and fswCOD 30, and red points represent samplings of PSGD at time step (ssco = 30 and 4rSaD 60. Algorithm 3 transforms an initial uniform-circle distribution into a distribution concentrating on two points indicating negative curvature, and these two figures represent intermediate states of this process. It converges faster than PSGD even when ÍSNCCID & (ySaD- Right: A histogram of descent values obtained by Algorithm and PSGD, respectively. Set ESNCOD fesan 60. Although we run two times of iterations in PSGD, there are still over 50% of SGD paths with function value decrease no greater than 0.6, while this ratio for Algorithm 3 less than 10%.
Algorithm
and
10

---

Acknowledgements
We thank Jiaqi Leng for valuable suggestions and generous help on the design of numerical exper- iments. TL was supported by the NSF grant PHY-1818914 and a Samsung Advanced Institute of Technology Global Research Partnership.
References
[1] Naman Agarwal, Zeyuan Allen- Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma, Finding approximate local minima faster than gradient descent, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1195-1199, 2017, arXiv:1611 1.01 146.
[2] Zeyuan Allen-Zha, Natasha 2: Faster non-convex optimization than SGD, Advances in Neural Informa- tion Processing Systems, pp. 2675 2686, 2018, Itxiv::77 706.48694.
[3] Zeyuan Allen-Zhu and Yuanzhi Li, Neon2: Finding local minima via first-order oracles, Advances in Neural Information Processing Systems, pp. 3716-3726, 2018, arXiv:171 .06673.
[4] Srinadh Bhejanapalli, Behnam Neyshabur, and Nati Srebro, Global optimality of local search for low rank matrix recovery. Proceedings of the 30th International Conference Neural Information Processing Systems, pp. 3880-3888, 2016, arXiv:1605. 1Xii:1605.00222 00221..
[5] Alan Bray and David Dean, Statistics of critical points of Gaussian fields on large-dimensional spaces, Physical Review Letters 98 (2007). no. 15, 150201, arXiv:cond moauddmma06611000 1023..
[6] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford, Accelerated methods for nonconvex optimization, SIAM Journal on Optimization 28 (2018), no. 2, 1751-1772, wxXiv:1611.0075555
[7] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford, Accelerated methods for nonconvex optimization, SIAM Journal on Optimization 28 (2018), no. 2, 1751-1772.
[8] Yann N. Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Ben- gio, Identifying and attacking the saddle point problem in high-dimensional non-convex optimization, Advances in neural information processing systems, pp. 2933-2941, 2014, arXiv: 10Xiv:1406.2555 406.2572.
[9] Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang, Spider: Near-optimal non-conver opti- mization via stochastic wath-integrated differential estimator, Advances Neural Information Processing Systems. pp. 689-699, 2018, arXiv: 807 01655.
[10] Cong Fang. Zhouchen Lin, and Tong Zhang. Sharp analysis for nonconvex SGD escaping from saddle points, Conference on Learning Theory. pp. 1192-12344 2019, (XXv:1902.00047
[11] Yan V. Fyodorov and Ian Williams, Replica symmetry breaking condition exposed by random matrix calculation of landscape complexity, Journal of Statistical Physics 129 (2007), no. 5-6, 1081-1116.
[12] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan, Escaping from saddle points online stochastic gra- dieni for tensor decomposition, Proceedings of the 28th Conference on Learning Theory, Proceedings of Machine Learning Research, vol. 40, pp. 797-842, 2015, arXiv:1503
[13] Rong Ge. Chi Jin. and Yi Zheng, No spurious local minima in nonconvex low rank problems: A uni- fied geometric analysis, International Conference on Machine Learning, pp.
PMLR, 2017,
a1Xiv:1704. 170.0000
[14] Rong Ge. Jason D. Lee, and Tengyu Ma. Matrix completion has no spurious local minimum, Advances in Neural Information Processing Systems, pp. 2981-2989, 2016, 1atd::1605.072711
[15] Rong Ge. Jason Lee, and Tengyu Ma, Learning one-hidden--ayee layer neural networks with landscape design. International Conference on Learning Representations. 2018, arXiv:1711.0055
[16] Rong Ge, Zhize Li, Weiyao Wang, and Xiang Wang, Stabilized SVRG: Simple variance reduction for non- convex optimization, Conference on Learning Theory. pp. 3394-1448, PMLR, 2019, arXiv: 1905,00529,
[17] Rong Ge and Tengyu Ma, On the optimization landscape of tensor decompositions, Advances in Neural Information Processing Systems, pp. 3656-3666 Curran Associates Inc., 2017, arXivv1706.05553
[18] Moritz Hardt, Tengyu Ma, and Benjamin Recht, Gradient descent learns linear dynamical systems, Jour- nal of Machine Learning Research 19 (2018), no. 29, 1-44, utXiv:1609.055
[19] Prateek Jain, Chi Jin, Sham Kakade, and Praneeth Netrapalli, Global convergence of non-convex gradi- ent descent for computing matrix squareroot, Artificial Intelligence and Statistics, pp. 479- 2017,
a50iv:1507. 05854.
[20] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael Jordan, How escape sad- dle points efficiently, Proceedings of the 34th Internatoonal Conference on Machine Learning, vol. 70, pp. 1724 1732, 2017, MxXi:1703.000887

---

[21] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, and Michael I. Jordan, On nonconvex optimiza- tion for machine learning: Gradients, stochasticity, and saddle points, 2019, EXXi:1102.048811
[22] Chi Jin, Praneeth Netrapalli, and Michael I. Jordan, Accelerated gradient descent escupes saddle points faster than gradient descent, Conference on Learning Theory. pp. (042-1085, 2018, utXiv:1111.0445
[23] Michael I. Jordan, On mundient-basedd optimization: Accelerated, distributed, asynchronous and stochas- sic optimizatiin, https: htmpp://www youtube. www/ http://tchhhhttt /wttaaacrrr-vV22ggggaaooo 2017.
[24] Zhize Li, SSRGD: Simple stochastic recursive gradient descent for escaping saddle points, Advances in Neural Information Processing Systems 32 (2019), 1523-1533, arXiv:1904.09265.
[25] Mingrui Liu, Zhe Li, Xiaoyu Wang, Jinfeng Yi, and Tianbao Yang. Adaptive negative curvature descent with applications non-comvex optimization, Advances in Neural Information Processing Systems 31 (2018), 4853-4862.
[26] Yurii Nesterov and Boris T. Polyak, Cubic regularization of Newton method and its global performance, Mathematical Programming 108 (2006), no. 1, 177-205.
[27] Yurii F. Nesterov, A method for solving the convex programming problem with convergence rote O(1 (1))))) Soviet Mathematics Doklady, vol. 27, pp. 372-376, 1983.
[28] Sun, Qing Qu, and John Wright, A geometric analysis of phase retrieval, Foundations of Computational Mathematics (2018), no. 5, 1131-1198, arXiv:1602.0668 0666446..
[29] Nilesh Tripurameni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael I. Jordan, Stochastic cubic regu- larization for fast noncorves optimization, Advances in neural Information Processing Systems, pp. 2899 2908, 2018, arXiv: 1,0288.
[30] Yi Xu, Rong Jin, and Tianbao Yang, NEON+; Accelerated gradient methods for extracting negative curvature for non-convex optimization, 2017. arXiv:1712.01033,
[31] Yi Xu, Rong Jin, and Tianbao Yang. First-order stochastic algorithmss for escaping from saddle points almost linear time, Advances in Neural Information Processing Systems, pp. 5530-5540, 2018.
arXiv:1711.0101
[32] Yaodong Yu, Pan Xu, and Quanquan Gu, Third-order smoothness helps: Faster stochastic optimization algovithms for finding local minima, Advances in Neural Information Processing Systems (2018), 4530- 4540.
[33] Xiao Zhang, Lingxiao Wang, Yaodong Yu, and Quanquan Gu, A primal-dual analysis of global optimality in nonconvex low-rank matrix recovery, International Conference on Machine Learning, pp. 5862-5871,
PMLR, 2018.
[34] Dongruo Zhou and Quanquan Gu, Stochastic recursive variance-reduced cubic regularization methods, International Conference Artificial Intelligence and Statistics, pp. 3980-3990, 2020, arXiv: 1901.1111118
[35] Dongruo Zhou, Pan Xu, and Quanquan Gu, Finding local minima stochastic nested variance reduc- fion, 2018, 1rXiv:1806.08
[36] Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic variance-reduced cubic regularized Newton meth- ods, International Conference on Machine Learning, pp. 5990-5999, PMLR, 2018, EXXi::8802.04999
[37] Dongruo Zhou, Pan Xu, and Quanquan Gu, Stochastic nested variance reduction for nonconvex optimiza- fion, Journal of Machine Learning Research 21 (2020), no. 103, 1 1-63, arXiv: 1iii:1800000000 100.18816.781...


Reviews:
[{"review_id": "kwUcT2T1Lre", "reviewer": "Reviewer_ub9p", "summary": "This paper provides an improved method for computing stationary points of nonconvex functions. The authors give an algorithm which, given an $L$-smooth $\\rho$-Hessian Lipschitz nonconvex function $f$, computes an $(O(\\epsilon), O(\\sqrt{\\rho \\epsilon}))$-second order stationary point of $f$ using $O(\\eps^{-7/4} \\log n)$ gradient computations of $f$. This matches the $\\epsilon$ dependence  achieved by several previous works in the area (for example [6,7,20]) but  improves the dependence on $\\log n$, where $n$ is the dimension, by polynomial factors. The algorithm is also of similar simplicity to the previous state-of-the-art method given in [20], and combines the perturbed AGD framework given there with some clever observations to achieve the result.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "All algorithms in this line of work combine accelerated gradient descent with a mechanism to exploit negative curvature in the objective. The main contribution of this work is a clever interpretation of perturbed gradient descent itself as a curvature exploitation routine: this significantly simplifies the algorithm and allows their approach to obtain results for stochastic gradient oracles as well.  \n\nThe analysis of the algorithm is relatively straightforward and easy to follow. The proof of the negative curvature exploitation routine seems fully correct to me, and in my brief skim I did not see any issues with the combination of this with the acceleration framework of [20]. The paper does a good job motivating the negative curvature detection idea-- the algorithm the authors propose is both the simplest and fastest algorithm in the literature for finding stationary points of nonconvex functions. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "While the result obtained is nice and of obvious practical importance, the analysis of acceleration seems to be heavily borrowed from [20], outside of the clever improvement to the negative curvature exploitation. In addition, the experiments only benchmark solution quality and iteration complexity against an unaccelerated method (PGD from [19])-- it would be interesting to see if the claimed iteration complexity translates to [20]. My score is borderline between a 7 and an 8 for these reasons: I would be happy to raise my evaluation if these concerns are addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "i46ENHnAxZr", "reviewer": "Reviewer_Ff6E", "summary": "In this work, the authors study the escaping saddle points problem for nonconvex optimization. Previously Jin et al. proposed a perturbed accelerated gradient descent (AGD) method which finds $\\epsilon$-second-order stationary points in $O(\\log^6 n/\\epsilon^{1.75})$ number of iterations, where $n$ is the dimension. By utilizing a refined perturbed negative curvature estimator, the authors successfully improves the dependence of dimension from $\\log^6 n$ to $\\log n$. Experiment results suggest that their algorithm performs well in practice. ", "questions": "", "limitations": "", "rating": 6, "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": "The main contribution of this work is a robust Hessian power method. Compared with previous approaches such as Jin et al. which estimate the negative curvature direction by a random added perturbation, this work further replaces the random perturbation by the previous estimated direction, which is a more accurate estimate. The idea is neat, the presentation is clear, and the experiments are comprehensive. Here are my additional comments. \n\n- One of the issues of this work is the so-called ‘robustness’ property. The authors name the ‘robustness’ due to the facts that replacing GD by either SGD or AGD will not prevent the algorithm from finding negative curvature. I find it a bit confusing, since normally I would use the word ‘robustness’ to describe that an algorithm is robust to some adversarial attacks brought by the opponent, which is far away from the meaning in this work. \n\n- Another issue of this work is the difference between the proposed estimator Algorithm 1 and the Neon 2 estimator proposed by Allen-zhu and Li. It seems that these two estimators utilize the same idea, which is to estimate the negative curvature direction through the Hessian-vector product. However, Algorithm 1 estimates the negative curvature with a single loop with high probability, while Neon 2 needs an additional boosting step to achieve a similar goal. Can the authors elaborate more on the connection and difference between them? \n\n- Finally, for the stochastic setting, some earlier works [1, 2] proposed algorithms to find second-order stationary points without a nested-loop structure. [3, 4] studied third-order smoothness assumption and show that it can help algorithms find second-order stationary points faster. [5, 6] showed that escaping from saddle points on the low-rank matrix factorization problem is identical to finding the global minima. [7] studied a stochastic variant of the cubic-regularization method and showed a theoretical guarantee. The authors may want to comment on these related works. \n\n[1] Ge, R., Li, Z., Wang, W., & Wang, X. (2019, June). Stabilized SVRG: Simple variance reduction for nonconvex optimization. In Conference on learning theory (pp. 1394-1448). PMLR.\n\n[2] Li, Z. (2019). SSRGD: Simple stochastic recursive gradient descent for escaping saddle points. arXiv preprint arXiv:1904.09265.\n\n[3] Yu, Y., Xu, P., & Gu, Q. (2018). Third-order smoothness helps: Faster stochastic optimization algorithms for finding local minima. Advances in neural information processing systems. \n\n[4] Zhou, D., Xu, P., & Gu, Q. (2020). Stochastic nested variance reduction for nonconvex optimization. Journal of machine learning research.\n\n[5] Ge, R., Jin, C., & Zheng, Y. (2017, July). No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning (pp. 1233-1242). PMLR.\n\n[6] Zhang, X., Wang, L., Yu, Y., & Gu, Q. (2018, July). A primal-dual analysis of global optimality in nonconvex low-rank matrix recovery. In International conference on machine learning (pp. 5862-5871). PMLR.\n\n[7] Zhou, D., Xu, P., & Gu, Q. (2018, July). Stochastic variance-reduced cubic regularized Newton methods. In International Conference on Machine Learning (pp. 5990-5999). PMLR.\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the limitations and there is no negative societal impact about this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "S8kVVceX7y5", "reviewer": "Reviewer_sM4q", "summary": "The paper considers SGD and accelerated GD approaches. While their results are similar to that of Jin et al., they achieve much better iteration dependence on log n: log n for AGD and log^2 n for SGD. ", "questions": "", "limitations": "", "rating": 7, "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": "Their SGD algorithm also enjoys the property of being a single-loop approach, which allows it to achieve simplicity and reduce a smaller number of hyper-parameters. One of key ideas in the paper is a power SGD-based approach which allows one to efficiently find a direction to escape from a saddle point.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe the paper has the following shortcomings:\nI’m confused what the authors mean by “single-loop”. Algorithm 6 uses Accelerated Negative Curvature Finding, which introduces a nested loop and has the same problem with hyperparameters.\nI think the paper and the main body should be more self-sufficient.For example, Theorem 3 (one of the main results) references Algorithm 6, but the algorithm itself is deferred to appendix. Negative Curvature exploitation from [20] is used, but the motivation behind it is unclear, unless one checks the original paper..\nLine 252:  “we can construct the stochastic version of Algorithm 1, as shown in Algorithm 3”. It’s not clear to me why Algorithm 3 is a version of Algorithm 1.\n\nMinor issues:\nLine 151 - y_{t, ||} is used everywhere\nLine 208 - assumption on < ∇ f, \\bar e> should be a part of the statement\nI think it would be more convenient if theorems, statements and propositions had the same numeration.\nLemma 2 - I suggest simply saying for “x_{t+1} = x_t - η ∇ f(x_t)”, since the current statement is imprecise.\nLemma 9 - Please remind what G_\\perp and G_|| are\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "J1DnLEZmuqf", "reviewer": "Reviewer_YK72", "summary": "In this paper, the authors propose a simple gradient-based algorithm for a smooth function. And it outputs an \\epsilon-approximate second-order stationary point with the complexity O(\\log n/\\epsilon^1.75), which is polynomially better in terms of log(n) and matches their complexities in terms of 1/\\epsilon. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "This paper is technically sound, and the experiments also seem convincing. However, this paper requires some improvements.\n1.\tThe main contribution of this paper is an idea of implementing a robust Hessian power method using only gradients, which can find negative curvature near saddle points and achieve a polynomial speedup in log(n) compared to the perturbed gradient descent methods. However, the authors should add some comparisons with existing works based on negative curvature descent such as [26] and [R1] in both theory and practical.\n2.\tThe author should explain the main differences between the proposed algorithm and the related works [26] and [R1].\n\n3.\tIn the experiment section, the compared algorithms are too few. Can the authors provide more comparisons to other advanced optimization algorithms?\n\n4.\tThe experiments are done only for the special non-convex functions, and the authors should provide more results for more general non-convex fucntions.\n5.\tIn Line 165, it may be \\alpha_t=\\|y_{t,\\|}\\|/\\|y_t\\| instead of \\alpha_t=\\|y\\|_{t,\\|}/\\|y_t\\|.\n\n[R1] Mingrui Liu, Zhe Li, Xiaoyu Wang, Jinfeng Yi, Tianbao Yang.  Adaptive Negative Curvature Descent with Applications in Non-convex Optimization.  NeurIPS 2018", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1.\tThe main contribution of this paper is an idea of implementing a robust Hessian power method using only gradients, which can find negative curvature near saddle points and achieve a polynomial speedup in log(n) compared to the perturbed gradient descent methods. However, the authors should add some comparisons with existing works based on negative curvature descent such as [26] and [R1] in both theory and practical.\n2.\tThe author should explain the main differences between the proposed algorithm and the related works [26] and [R1].\n\n3.\tIn the experiment section, the compared algorithms are too few. Can the authors provide more comparisons to other advanced optimization algorithms?\n\n4.\tThe experiments are done only for the special non-convex functions, and the authors should provide more results for more general non-convex fucntions.\n5.\tIn Line 165, it may be \\alpha_t=\\|y_{t,\\|}\\|/\\|y_t\\| instead of \\alpha_t=\\|y\\|_{t,\\|}/\\|y_t\\|.\n\n[R1] Mingrui Liu, Zhe Li, Xiaoyu Wang, Jinfeng Yi, Tianbao Yang.  Adaptive Negative Curvature Descent with Applications in Non-convex Optimization.  NeurIPS 2018\n\n----------after feedback---------------  \n\nThe authors address my comments well, so I increased my score.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "72"}, "extra_text": {}}]

Author rebuttal:

Meta-review: ​​This paper proposes a robust Hessian power method to find negative curvature direction, based on which (stochastic) gradient descent can find the local minima with improved gradient complexity (the improvement is in the poly-log dependence in the problem dimension $n$). All the reviewers are in strong support of this paper.  I, therefore, recommend acceptance.
Decision: Accept (Poster)