Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
Authors: Zixiang Chen
Dongruo Zhou
Quanquan Gu
Venue: NeurIPS 2021 Submitted (2021)

Abstract: Escaping from saddle points and finding local minimum is a central problem in nonconvex optimization.
Perturbed gradient methods are perhaps the simplest approach for this problem. However, to find $(\epsilon, \sqrt{\epsilon})$-approximate local minima, the existing best stochastic gradient complexity for this type of algorithms is $\tilde O(\epsilon^{-3.5})$, which is not optimal. In this paper, we propose \texttt{Pullback}, a faster perturbed stochastic gradient framework for finding local minima.  We show that Pullback with stochastic gradient estimators such as SARAH/SPIDER and STORM can find $(\epsilon, \epsilon_{H})$-approximate local minima within $\tilde O(\epsilon^{-3} + \epsilon_{H}^{-6})$ stochastic gradient evaluations (or $\tilde O(\epsilon^{-3})$ when $\epsilon_H = \sqrt{\epsilon}$). The core idea of our framework is a step-size ``pullback'' scheme to control the average movement of the iterates, which leads to faster convergence to the local minima. 

For the case where is deterministic function, it has been shown that vanilla gradient descent fails 24 to find local minima efficiently since the iterates will get stuck at saddle points for exponential time Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
Anonymous Author(s)
Affiliation Address email
Abstract
Escaping from saddle points and finding local minimum is a central problem in nonconvex optimization. Perturbed gradient methods are perhaps the simplest approach for this problem. However, find (c, v -pprroxmiitee local minima, the existing best stochastic gradient complexity for this type of algorithms is Ö(c-3.) which is not optimal. In this paper, we propose Pullback, a faster perturbed stochastic gradient framework for finding local minima. We show that Pullback with stochastic gradient estimators such SARAH/SPIDER and STORM can
2
find (c, appproximate local minima within Ō(c (H) stochastic gradient evaluations (or Ö(E=3) when ен = vt). The core idea of our framework is a step-size "pullback" scheme to control the average movement of the iterates, which leads to faster convergence to the local minima.
11
Introduction
In this paper, we focus on the following optimization problem min F(x) (x]
(1.1)
XER
where f(x; Rd - IR is a stochastic function indexed by some random vector &, and it is differentiable and possibly nonconvex. We consider the case where only the stochastic gradients V [x(x; E) are accessible. (I.1) can unify a variety of stochastic optimization problems, such as finite- sum optimization and online optimization. Since in general, finding global minima of a nonconvex function could be an NP-hard problem [12], one often seeks to finding an (c, CH -approxxiimttt local minimum x, i.e., / F(x) S c and Amin (V²F(x) 2 -H,, where V F(x) is the gradient of F 20 and Amiin 2 F(x)) is the smallest eigenvalue of the Hessian of F at x. In many machine learning
14
15
16
17
18
19
21 applications such as matrix sensing and completion [5, 11], suffices to find local minima due
fact that all local minima are global minima.
25 [8]. To address this issue, the simplest idea is add random noises as perturbation the stuck iterates. Jin et al. [13] showed that the simple perturbation step is enough for gradient descent to escape saddle points and find (e, -apprrxiiie local minima within ((1/e²) gradient evaluations,
28
28 which matches the number of gradient evaluations for gradient descent to find e-stationary points [19]. Such matching results suggest that perturbed gradient methods find local minima efficiently,
30 at least for deterministic optimization. When it comes to stochastic optimization, a natural question arises:
Can perturbed stochastic gradient methods find local minima efficiently?
To answer this question, first look into existing results of perturbed stochastic gradient methods 34 for finding local minima. Ge et al. [10] showed that perturbed Stochastic gradient descent can find
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

35 (c, VE) -approxxxee local minima within (ppoly(e-1)) stochastic gradient evaluations. Daneshmand
36 al. [7] showed that under a specific CNC condition, stochastic gradient descent is able to find
37 (e, v Vap-approx local minima within ((1/E²) stochastic gradient evaluations. Later on, Li [17]
38 showed that simple stochastic recursive gradient descent (SSRGD) can find -c. -aprrxximae
39 local minima within ((55).5) stochastic gradient evaluations, which is the state-of-the- tfftthe-artts date, However, none of these results by perturbed stochastic gradient methods matches the optimal result
40
((e-)) for finding e-stationary points, achieved by SPIDER [9]. SNVRG [30] and STORM [6] (See also Arjevani et al. [4] for the lower bound results). Therefore, whether perturbed stochastic gradient methods can find local minima efficiently finding stationary points still remains unknown.
41
42
44
In this work, we give an affirmative answer to the above question. We propose a general framework named Pullback, which works together with existing popular stochastic gradient estimators such as SARAH/SPIDER and STORM find approximate local minima efficiently. We summarize our contributions as follows:
45
46
47
We prove that Pullback finds (c, "approximate local minima within Ō(6-3 3 + E 6) stochastic gradient evaluations. Specifically, in the classic setting where EØ Ve, our Pullback together with the SARAH/SPIDER estimator enjoys an O( ($) stochastic gradient complexity, which outperforms previous best known complexity result ( achieved by Li [17]. Our result also matches the best possible complexity result Ō -() achieved by negative curvature search based algorithms [9, 31], which suggests that simple methods such perturbed stochastic gradient methods can find local minima as efficiently as the more complicated ones.
49
50
51
52
54
55
Besides, also show that Pullback with a recent proposed STORM estimator is also able find (c, apppoooixee local minima within Ō(c-3 3 + ( stochastic gradient evaluations.
56
At the core of our Pullback is novel step-size "pullback" scheme to control the average movement of the iterates, which may be of independent interest to other related nonconvex optimization algorithm design.
58
59
60
To compare with, we summarized related results of stochastic first-order methods for finding local minima in Table 1.
61
Table 1: Comparison of of different optimization algorithm for find approximate local minima of non convex online problems.
Algorithm
Gradient complexity
Classic Setting
Neon2
Noon2+Natasha2 [1]
Ö 3.25 + c +
CH
Ö(e-3.5
needed
Neon2+SCSG [3]
Ö 10/3 + -2 +
cH
Ö( -3.5
needed
#NVRG*+Neonl [31]
Ö 3 + 367 1 + +
D(c-3.0g
needed
SPIDER-SFO"
(+Neon2)[9] (HODERR)SFO"(NNNo22)9))
Ö +e =em +
Ö(e
needed
Perturbed SGD [10]
Poly(d, (t,dd, ,,x)))
O(Poly(t- Ō(c-))
No
CNC-SGD [7]
Ö( + cH 100
No
SSRGD [17]
ÖlE 3 + Ee + cH
Ō(e 3.0)
No
Pullback (This paper)
Ole + +
No
Notations We use lower case letters to denote scalars, lower and upper case bold letters denote
63 vectors and matrices. We use |- to indicate Euclidean norm. We use Bx(r) to denote a Euclidean ball center with radius We also use the standard O and Ω notations. We use Auain (M) to denote
85 the minimum eigenvalue of matrix M. We say On = O(b,)) if and only if 3C > 0, N > 0, Vn. >
66 N. o, S Cb.: an ((b,,)) if a, 2 Cb,,- The notation Ô is used to hide logarithmic factors.
87 2 Related Work
In this section, we review some important related works.
69 Variance reduction methods for finding stationary points. Our algorithm takes stochastic gradient estimators as its subroutine. In specific, Johnson and Zhang [14], Xiao and Zhang [28] proposed
71 Stochastic Variance Reduced Gradient (SVRG) for convex optimization in the finite-sum setting.
Reddi et al. [25], Allen-Zhu and Hazan [2] analyzed SVRG for nonconvex optimization. Lei et al. [16]

---

73
proposed a new variance reduction algorithm, dubbed stochastically controlled stochastic gradient (SCSG) algorithm, which finds e-stationary point within O( O(e-10/3) stochastic gradient evaluations. Nguyen et al. [21] proposed a SARAH algorithm which uses a recursive gradient estimator for convex optimization, and it was extended to nonconvex optimization in [22]. Fang et al. [9] proposed a
74
75
78
77
SPIDER algorithm with a recursive gradient estimator and proved an O(E stochastic gradient evaluations to find a e-stationary point, which matches a corresponding lower bound. Concurrently,
78
Zhou et al. [30] proposed an SNVRG algorithm with nested gradient estimator and proved an Ō( S) stochastic gradient evaluations to find a e-stationary point. Wang et al. [27] proposed a Spiderboost algorithm with a constant step size, achieves the same O gradient complexity. Pham al. [23] extended SARAH [22] to proximal optimization and proved O(E gradient complexity for finding stationary points. Recently, Cutkosky and Orabona [6] proposed recursive momentum-based algorithm called STORM and proved an ( gradient complexity to find e-stationary points. Tran-Dinh et al. [26] proposed SARAH-SGD algorithm which hybrids both SGD and SARAH algorithm with an Ô gradient complexity when is small. Li et al. [18] proposed PAGE
79
80
81
82
84
85
86
algorithm with probabilistic gradient estimator which also attains an O(e-²) gradient complexity. In our work, we employ SARAH/SPIDER and STORM as the gradient estimator in our Pullback framework since they are most representative and simple use.
88
89
90
Utilizing negative curvature descent to escape from saddle points. To escape saddle points, a widely used approach is first compute the direction of the negative curvature of the saddle point and move away along that direction. In stochastic optimization, to find (c, < >approximate local minima, [1] proposed Natasha algorithm using Hessian vector product to compute the negative curvature + EE + + + Later, Xu et al. [29] proposed a Ncon method which computes the negative curvature direction with perturbed stochastic gradients, -3
91
92
direction with the total computation cost of Ö(E 3.25
94
95
whose total computational cost is O(1-10/3 + 6 - + E ).))). [3] proposed Neon2 negative curvature computation subroutine with Oc-110/3 2 +
96
97
+CH stochastic gradient evaluations.
Fang et al. [9] then showed that SPIDER equipped with Neon2 can find (c, -approximate local minima within Ōc- + c 2
98
" stochastic gradient evaluations, while independently Zhou et al. [31] proved that SNVRG equipped with Neon2 can find (c, CH )apppooxiiatee local minima within Ō + + Z -3 + 'H stochastic gradient evaluations. In contrast to this line of works, our algorithm is simpler since does not need to use the negative curvature search routine.
99
100
102
3 Preliminaries
103
104
In this section, we present assumptions and definitions that will be used throughout our analysis.
105 We first introduce the standard smoothness and Hessian Lipschitz assumptions.
106
Assumption 3.1. For all &, f(: is L-smooth and its Hessian is p-Lipschitz continuous w.r.t. x, i.e. for any x1, X2, we have that
107
[ 4 V fxx2; S L||x - X2112, ((x;k) (²x S pl|xi x2l12
108
This assumption directly implies that the expected objective function F(x) is also L-smooth and its Hessian is p-Lipschitz continuous. This assumption is standard for finding approximate local minima in all the results presented in Table
110
111
Assumption 3.2. The squared difference between the stochastic gradient and full gradient is bounded by o² < co, i.e., for any x, & IRd, [xV] VF()) o²
112
118 Assumption 3.2 is standard in online/stochastic optimization for finding second-order stationary points [9. 17), and immediately implies that the variance of the stochastic gradient is bounded by o². 115 It can be relaxed to be ||V f (x: { F 2x))ll has o-Sub-Gaussian tail.
114
116 Let Xo E Rdd be the starting point of the algorithm. We assume the gap between the initial function value and the optimal value bounded.
117
118
Assumption 3.3. We have A = F(xo) - infy F(x) < +00.
119 Next, we give the formal definition of approximate local minima ka. second-order stationary points).
3

---

Definition 3.4. We call x E R an (c, EH) approximate local minimum, if
121
[V S e,, Amin Fx)) 2 -f
122
The definition of (c, (H) >approximate local minima is a generalization of the classical (c, vo)- approximate local minima studied by Nesterov and Polyak [20], Jin al. [13].
123
124
4
The Pullback Framework
125
In this section, we present our main algorithm Pullback. We begin with reviewing the mechanism of perturbed gradient descent in deterministic optimization, and then we discuss the main difficulty of extending it to the stochastic optimization case. Finally, we show how we overcome such a difficulty by presenting our Pullback framework.
126
127
128
129
How does perturbed gradient descent escape from saddle points? We review the perturbed gradient descent [13] (PGD for short) with its proof roadmap, which shows how PGD finds (e, v approximate local minima efficiently. In general, the whole process of perturbed gradient descent can be decomposed into several epochs. and each epoch consists of two non-overlapping phases: the gradient descent phase (GD phase for short) and the Escape from saddle point phase (Escape phase for short). In each epoch, PGD starts with the GD phase by default. In the GD phase, PGD performs vanilla gradient descent to update its iterate, until at some iterate X, the norm of the gradient
131
132
133
134
135
136
V F F()) is less than the target accuracy O(c). Then PGD switches to the Escape phase. In the Escape phase, PGD first adds uniform random noise (or Gaussian noise) to the current iterate x,
137
then it runs Latres = Ō(E -122) steps of vanilla gradient descent. PGD then compares the function value gap between the current iterate and the beginning iterate of Escape phase x. If the gap is less than threshold F Ö(c2.5), then PGD outputs x as the targeted local minimum. Otherwise, PGD starts a new epoch and performs gradient descent again.
138
140
141
To see why PGD can find (c, appaooxxiime local minima within Ō(c²2) gradient evaluations, we do the following calculation. First, when PGD is in the GD phase, the function value decreases Ō(e²) per step (following the standard gradient descent analysis). When PGD in the Escape phase, the function value decreases F/ = ( per step on average. Therefore, the total number of steps
142
143
144
145
will be bounded by Ö(E-?) which is in the same order as GD for finding e-stationary points.
148
L Limitation of existing methods. However, extending the two-phase PGD algorithm from determinis- tic optimization to stochastic optimization with a competative gradient complexity is very challenging.
148
149
We take the SSRGD algorithm proposed by Li [17] as an example, which uses SARAH/SPIDER [9] as its gradient estimator. Unlike deterministic optimization where we can access the exact function value
150
151
F (x) and gradient V Fx)) defined in (1.1), in the stochastic optimization case we can only access the stochastic function fxx: {) and the stochastic gradient fx(x; E). Therefore, in order to estimate the gradient norm F(x)l2 (which required at the beginning of Escape phase). a naive approach (adapted by Li [17]) is to sample big batch of stochastic gradient V (x E.),..., fx {g) and uses their mean to approximate Fxx). Standard concentration analysis suggests that in order to achieve an c-accuracy, the batch size B should be in the order Ōcc Thus, each Escape phase leads to a F = ( function value decrease with at least Ō number of stochastic gradient evaluations, which contributes Ö(1/c'.5 2) Ō(c 3.5) gradient complexity in the end. This is already worse than the (c)33) gradient complexity of SPIDER for finding e-stationary points.
152
153
154
155
156
157
159
160
Our approach. Here we propose our Pullback framework in Algorithm 1, which overcomes the aforementioned limitation. In detail, Pullback inherits the two-phase structure of PGD and SSRGD, and it takes either SARAH/SPIDER
161
162
STORM [6] as its gradient estimator. The two gradient in Algorithms
163
estimators are summarized as subroutines GradEst-SPP -PIDER and GradEst- and 3 respectively, and we use d, to denote their estimated gradient at iterate x,, The key improvement of Pullback is that, it directly takes the output of the gradient estimator GradEst to estimate the true gradient V Fx)), which avoids sampling big batch of stochastic gradients as in Li [17] and thus saves the total gradient complexity. A similar strategy has also been adapted in [9], but for the negative curvature search subroutine. However, such a strategy leads to new problem to be solved.
165
166
167
168
Since we use de to directly estimate V F((x)) (x;:), in order to make such an estimation valid, we need to guarantee that the error between d, and V F is small enough, e.g., up to O(e) accuracy. Notice
169

---

Algorithm Pullback
Input: Initial point X1, step size 17 and 7H. perturbation radius r, threshold parameter hhres average movement D.
1: di < GradEst(O, 0, 0, x1), 0, < FIND+
2: while FIND = false do
3: 8 = + 1, l1 +- I, tIn
4: while |dd/12 > do
5: JJ f /-///delaa { ("PullBack"]
6: X++1 X, n.d. d +
7:
end while
8:
m, t f, Uniform (r), X + d GradEst X411), t+1
9:
for k = 1k=0.... 0..... Lires do
10:
+ иH. D - Σi=m, 1.113 if D (t m. 1)D then
11:
12:
Set r/ such that Eiem, of d m, +DD ("PullBack")
Xe+1 x m,d,, d++1 GradEst(I, d,, Xx, X.41 FIND + false, break
14:
end if
Xt+1 X n.dr, de- GradEst(l, de, X1, Xx+1)
b+1
16:
end for
end while
Output: Xm,
Algorithm 2 GradEst- d,, X4, Xx+1, b, B)
Input: Big batch size B, mini-batch size b, loop length q
1: if't mod q = 0 then
2: Generate E fi+1..... ch
Set de+1
EE V/(x
3: else
4: Generate 4..1...., 4.. Set Set d, + E [[((4+)) -V((x=((-))x
5: end if
Output: d++1
that the recursive structure of SARAH/SPIDEER and STORM suggests the following error bound:
Vt. |dd V =
Σ ||x+1 xx
(4.1)
172
where 8; is some reference index only related to Therefore, order to make the error |d, FF(x;) (22x small, it suffices to make the movement of the iterates ||x+11 x;ll2 small either individually or on average. We achieve this goal by our proposed step-size "Pullback" scheme. In de- tail, in the GD phase, when the norm of the estimated gradient ||d]]2 is large, we pull the step-size Y back a smaller value via normalization, which forces the movement ||x++1 x:ll2 = 7/2 ///ldd/12 = to be small. Such an approach is also adapted by Fang et al. [9] a normalized gradient de- scent for finding first-order stationary points. the Escape phase, which starts at m,-th step, we record the accumulative squared movement starting from Xm,+1 (after the perturbation step) as D Ei=m,+1 ||x+,] - x,112 E Di=ma n7 d; When the average movement D/(t m, 1) is large, we pull the last step size back to a smaller value, which forces the average movement DI(L m. 1) be small. Fortunately, such simple step-size calibration scheme allows to well-control the error between d, and V (xx,), and to reduce the gradient complexity.
173
174
176
178
181
182
183
5 Main Results
185
In this section, we present the main theoretical results. We first present the convergence guarantee of Hallback-SPIDER. which uses GradEst-SPIDER to estimate the gradient d, in Algorithm
186
Theorem 5.1. Under Assumptions 3.1, 3.2 and 3.3, choose batch size B Ō = VB, set step size n = a/(2VL), TH = Ö(L-1), perturbation ra-
8² -)
188
dius < min
(2Be,, / /2log(4/0)) (log(4/))m=²²/BBB) threshold fthee
5

---

Algorithm 3 GradEst-STORM(, d, Xs, X,+1, B)
Input: Initial batch size B, mini batch size b and weight parameter
1: if't 0 then
2: Generate t S1+1
c Set de+1
Ex ([(x+1ii(+1)1
3: else
4: Generate $/+1 fi+1...., Ei+1
5: Set d++1 < a) d: Ei= Vf(x;E 1/bb + EE \1
6: end if
Output: d,+1
(1/(m)==)) and D (4B(2)) Then with high probability, Pullback-SPIDER can find (e, -approxmxxe local minima within
190
181
stochastic gradient evaluations.
Remark 5.2. In the classical setting e VCH, our result gives Ö(e gradient complexity, which
192
outperforms the best existing result Ö for perturbed stochastic gradient methods achieved by SSRGD [17]. For sufficiently small e, Arjevani et al. [4] proved the lower bound of gradient complexity l(e + 2 for any first-order stochastic methods find (c, -approximate local minima. Our results matches the lower bound Ö( (3))) when é S e//5 For the general case, there is still gap in the dependency of си between result and the lower bound, and we leave to close as future work.
193
194
196
198
199
Next, we present the convergence guarantee of Pullback-STORN, which uses GradEst-STORM to estimate the gradient d, in Algorithm 1.
200
Theorem 5.3. Under Assumptions 3.1, 3.2 and 3.3, choose the mini batch size = Ö
201
OPEE)) and initial batch size B 6², set step size 7) o2(6)). 7H Ö(L-)),
203
weight a = 562 log(4/6)/h, threshold fares = O(1((nee)), perturbation radius r S and D = o²/(41BL2). Then with high probability, Pullback-STORN can find -aprrxxiiit local minima within (oLAC + op L stochastic gradient evaluations.
min (2bL), log(4/o)" (eb"") (oggl//))//H2//////
204
205
206
207
Remark 5.4. Different from Sellback-SPIDER the estimation error ||d, - VF(x)) of
208
Pullback-STORM controlled by the weight parameter a. This allows come up with simpler single-loop algorithm instead of a double-loop algorithm.
209
Proof Outline of the Main Results
211
Due to the page limit, we only outline the proof of Theorem 5.1 and leave the proof of Theorem 5.3 the appendix.
212
213
Let e denote the difference between true gradient Fx,) and the estimated gradient d,, which is
e, d, (xx)). The following lemma suggests that the estimation error ||e||l2 can be bounded.
Lemma 6.1. Under Assumptions 3.1 and 3.2, set b g VB, o/(2/BL), o/(2BBL)
and D < d² /(ABL)), then with probability at least - 6, for all we have
||Er|22 S / log 4/5jo/vB.
217 Specifically, by the choice of B in Theorem 5.1 we have that ||c/|22 I c/2.
Proof of Lemma 6.1. By GradEst-SPIDER presented in Algorithm 2 have
B
E
( - VVF(x+1)]
mod g = 0,
==1
1111 E, +
- -F(x)+)) V t mod + 0.
219
By the L-smoothness in Assumption 3.1 we have
[V (in1) Vf(x; (i.1) - VF(X4+1 + & 2TT||x411 - xell2-

---

220
Then by Assumption 3.2 and Azuma Hooffdinn inequality (See Lemma D.1 for details), with
221
probability least 1 6, we have
o22
41.
Vt > O, || - 4lg((4/6)
||
x:
(6.1)
2= 11/4//
222
Notice that bradEst-SPIDER is parallel with Pullback. Thus we need to further bound (6.1) by
considering iterates in three different cases: (1) for step in the GD phase, we have ||x-1 - x; 11 < 1
223
224
due to the "Pullback" scheme; (2) for i m, for some s in the Escape phase, we have x xx112 <
225
r²: and (3) for the other steps in Escape phase, we have on average, ||x;- xx - D. Therefore
226
we have
( B
0²
412 b -
8 8log(4/8)o²
|E:11 S 410g(4/0)
max
B
227
Lemma 6.1 guarantees that with high probability [Xx < ||eel2 e, which ensures
228
| FVV 2l < 2e when the algorithm terminates. Next lemma bounds the function value de-
229
230
crease the GD phase, which also valid for Sallback-STORM,
Lemma 6.2. Suppose the event in Lemma 6.1 holds, e/(2L), then for any 8, we have (m, 1.)
F(xx,)) F(xm.)
8
The choice of y in Theorem 5.1 further implies that the loss decreases by at least ae/(16//11) per step on average.
232
233
Proof of Lemma 6.2. For any t, St Mg, we can show the following property (See Lemma D.2),
F(x--1) S F(x,)
7t 2
de Tt Th 1|e 2 + 2
xx+1
x
(6.2)
235
Plugging the update rule Xc+1 = Xx 1/ into (6.2) gives,
11
F(x++1) = F(x,) ||x++1 x111
+
2Te
2
L
< F(x:)) 17²
+
2n
< FX,))
where the first inequality holds due the fact that n n//ld, and ||ez|12 S <e/2, and the second inequality is by 7)- = >//[|del2 S n//- < 12L)..
237
238
Following Lemma shows that if xm. a saddle point, then with high probability, the algorithm will break during the Escape phase and set false. Thus, whenever Xm, is not local minima, the algorithm cannot terminate.
240
Lemma 6.3. Under Assumptions 3.1 and 3.2, perturbation radius r < Lnnen / (Cp)
size лN S min log p-p-0-pp1111000 (----1-1)), 1/(C log (nees OII--t), Aaness = 2 log(nnen (10-0--(----1-))/0/0 (/nnn)))))))))))))))))))))))))") = Ö( 1 5T and D < C² 2 : where = VB > 16 16log(4/)) (n) ( Then for < -CH, with probability at least 1 28 algorithm breaks in the
242
243
C Ollog(d (olg(ddines)) thres 15) Õ(1) We also set
245 any s, when Auin
246
Escape phase.
247 Proof of Lemma 6.3. Let {xi}. ; {x{} be two coupled sequences by running Pullback- from Xm x +1 with Xm,+1 Xm,+1 roel. where Xm,+ Xm,=1 E Bxm, (r). Here ör /d and e; denotes the smallest eigenvector direction of Hessian 2 FxF(x..).
7

---

When Amin' Muin(( FV2F(xm,)) v -H under the parameter choice in Lemma 6.3, we can show that least one of two sequence will escape the saddle point (See Lemma D.3). To be specific, with probability at least 1 d,
250
251
LMHEH
max m. < +fmm
{||x: - Xm, + +12,, ||| x z Cp
(6.3)
253 (6.3) suggests that for any two points X,,+1,X X,,+1 satisfying Xm,+1 - 1 xm,+1 = rue1, at least one of them will generate a sequence of iterates which finally move more than E H / (Cp). Thus, let
254
S C Bm, (r) be the set of Xm,+1 which will not generate sequence of iterates moving more than LANEn then in the direction e1, the "thickness" of S is smaller than ro- Simple integration shows that
256
Cp
257
the ratio between the volume of and Bm, is bounded by 6. Therefore, since Xm,+1 +1 is generated from Xm, by adding uniform random noise in ball B,, (r), we conclude that the probability for
259
X1 locating in is less than 5. Applying union bound, we get with probability at least 1 26,
LUECH
3mg < t < m. Lisress ||x Xm,+1
(6.4)
Cp
260 Denote as the event that the algorithm does not break in the Escape phase. Then under E, for any 261 m. < < my + litres, we have
[x -
x1 184-x,,te
S
Σ 1=m,
|| - xxll2 S (t - m,) i=m,
Σ
|x+11 - x S (t m.) VD.
262
where the first inequality is due to the triangle inequality and the second inequality is due to Cauchy- Schwarz inequality. Thus, by the choice of fihres and D, we have
263
x Xm, alla (t mm,))DD lires VD V LпнCи
P
254
Then by (6.4), we know that P(E) < 26. Therefore when Amin least 1 28, Pullback breaks in the Escape phase.
( (V²F(Xm.)) S -eH, with probability
285
286
Next lemma bounds the decreasing value of the function during the Escape phase if the algorithm breaks in the Escape phase(i.e. FIND is false).
267
Lemma 6.4 (localization). Suppose the result of Lemma 6.1 holds, and лN S 1/ log(4/0)) perturbation radius s min { log(4 (lg((//))zzr /2/)))2222(BB)
set the step size
and D = d4B(().)) Suppose the algorithm breaks in the Escape phase starting at Xm,, then we have
270
log log(4/0)mHo²
F(xm.) ) - F(xe44)) 2 (l.41 m..
B
272
Proof of Lemma 6.4. For any m, < 1 we can show the following property (See Lemma D.2),
F(x++1) S F(x:)
Thi d 1| 2
||
xi+1
x:1.
(6.5)
2
2
273
Plugging the update rule x;+1 = X; nf, into (6.5) gives,
F(x++1) S F(x:)
ni ||: 11
L |x++] - xi
217
S F(;:) + THE 8 llog( (og(4/5)a2
|| x:112
(6.6)
2
4m
where the the second inequality holds due to Lemma 6.1 and m S mH S 1/L2) for any + mm
<i <
275 1s41. Telescoping (6.6) from i = m,
to 4,+1 1, we have
F(X),))) S (1m + 4пи log(4/0)(ts41 - m. - 11) 02
1-1-1
Σ
|x - x,13?
B
AmH
i=
8

---

278 Finally, we have
5
X - xx11
1)ml x²
F( - F Fxxes11)
4 4log (log(4/0)(/-11- ma
41H
B
i=m, +1
D 4log 4log(4/8)1HO²
= (ts+1 m2 1)
B
o²
4
4log(4/0)mH²²
[1s+1 m, 1)
16nH BL2
B
2 (t&+1 m, 1) 4log(4/8)) 2
(6.7)
B
277
where the last inequality is by the choice of 7711 S (LL 128 logglog((4 (4/))) For = m, we have (See Lemma D.2)
F(xm,+1 +1) S FX,m,) + (l|dm,lla Imem, 122 + Lr/2)r
(6.8)
279
Plugging
|mm,ll 1l2 and ||em, 1la S e/2 into (6.8) gives,
2 2log(4/6)
F(xm,+1) FXxm,) + (4e + Lr/2)r S F(xm.) +
(6.9)
B
where the last inequality is by the choice r S min (og(4/8))H (2BE), 00 Combining (6.7) and (6.9) and applying ts+1 m, 2 gives.
/
280
281
Fxxm,, F(x 2 [4(1a41 my -1) log 4 m/H
log (Og(4
2 (1s+1 m.)
B
B
282
283
Now, we can provide the proof of Theorem 5.1
284
Proof of Theorem 5.1. The analysis can be divided into two phases, i.c., GD phase and Escape phase. The function value will decrease at different rates in different phases.
285
GD phase: In this phase, ||d:l2 2 c and |||||2 S c/2 due to Lemma 6.1. Thus the gradients of the function are large FVF(x))lz ll2 2 c/2. Lemma 6.2 further shows that the loss decreases by least
286
/ / (16/BI) on average.
289
Escape phase: In this phase, the starting point Xm,, satisfies || (xm. )ll < ||dm, |2 + ||elle S 2e. If Xm, is saddle point with Amin (VxF(X,,)) S -EH. then by Lemma 6.3, with high probability will break Escape phase, set FaND+-False and begin a new GD phase. Further by Lemma 6.4, the loss will decrease by at least log(4/8))z0² / per step on average.
291
Pullback-SPIII
293
Sample Complexity: Note that the total amount for function value can decrease is most A F(xo) infx F(x) < +oo. So the algorithm must end and find an (e,e e japproxximaee local minimum within O(VBLAO-'<- + BLAG iterations. Notice that on average we sample
max (b, B/q} /B examples per iteration, so the total sample complexity is O(BLAo-
296
B3/2 LAg 2). Plugging in the choice of B = Ō(o2e + o²ppen"" in Theorem 5.1, we have the
297
298
total gradient complexity
ō 60
OP
oP¹LA
(000
OLA x
OPiLA
63
+
+
cEH
299
where the equation is due to the Young's inequality.
301
7
Conclusions
302 In this paper, we propose a perturbed stochastic gradient framework named Pullback for finding local minima. Pullback can find (e,eer)-aprroximal local minima within Ö( -3 + + stochastic gradient evaluations, which matches the best possible complexity results in the classical e Ve setting. Our results show that simple perturbed gradient methods can be as efficient as more sophisticated algorithms for finding local minima.
305
305

---

References
307
308
[1] Allen-Zhu, Z. (2018). Natasha 2: Faster non-convex optimization than sgd. In Advances in neural information processing systems, pages 2666-
310
[2] Alh, Z. and Hazan, E. (2016). Variance reduction for faster non-convex optimization. In International Conference on Machine Learning, pages 699-707.
312
[3] Allen-Zhu, Z. and Li, Y. (2018). Neon2: Finding local minima via first-order oracles. In Advances in Neural Information Processing Systems, pages 3716-3726.
313
[4] Arjevani, Y., Carmon, Y., Duchi, J. C.. Foster, D. J., Sekhari, A., and Sridharan, K. (2020). Sedond-order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pages 242-299. PMLR.
315
317
[5] Bhojanapalli. S., Neyshabur, B., and Srebro, N. (2016). Global optimality of local search for low rank matrix recovery. arXiv preprint 1605.::600.0722)
319
[6] Cutkosky, A. and Orabona, F. (2019). Momentum-based variance reduction in non-convex sgd. In Advances in Neural Information Processing Systems, pages 15210-15219.
320
[7] Daneshmand, H., Kohler, J., Lucchi, A., and Hofmann, T. (2018). Escaping saddles with stochastic gradients. arXiv preprint arXiv; 1803.05999
322
323
[8] Du S. S., Jin, C., Lee, J. D., Jordan, M. I., Poczos, B., and Singh, A. (2017). Gradient descent can take exponential time to escape saddle points. arXiv preprint arXiv: 1705.
324
325
99] Fang, C., Li, C. J., Lin, Z., and Zhang. T. (2018). Spider: Near-optimal non-convex optimization via stochastic inth-integrated differential estimator. In Advances in Neural Information Processing Systems, pages
327
328
[10] Ge, R., Huang, F. Jin, C., and Yuan, Y. (2015). Escaping from saddle points coints-online gradient for tensor decomposition. In Conference on Learning Theory, pages 797-842.
online stochastic
329
330
[1I] Ge, R., Jin, C.,, and Zheng, Y. (2017). No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, pages 1233-1242. PMLR.
331
332
[12] Hillar, C. and Lim, L.-H. (2013). Most tensor problems are np-hard. Journal of the ACM (JACM), 60(6):1-39.
334
335
[13] Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., and Jordan, M. I. (2017). How to escape saddle points efficiently. In International Conference on Machine Learning. pages 1724-1732. PMLR.
336
337
[14] Johnson, R. and Zhang, T. (2013). Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pages 315-323.
338
339
[15] Kallenberg, O. and Sztencel, R. (1991), Some dimension-free features of vector-valued martin- gales. Probubility Theory and Related Fields, 88(2):115-247.
[16] Lei, L., Ju, C., Chen, J., and Jordan, M. I. (2017). Non-convex finite-sum optimization via scsg methods. In Advances in Neural Information Processing Systems, pages 2348-2358.
342
[17] Li. Z. (2019). Ssrgd: Simple stochastic recursive gradient descent for escaping saddle points. In Advances in Neural Information Processing Systems, pages 1521-1531.
344
345
[18] Li, Z., Bao, H., Zhang, X., and Richtárik, P. (2020). Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. arXiv preprint arXiv:2008. 10898.
346
347
[19] Nesterov, Y. (1998). Introductory lectures on convex programming volume i: Basic course. Lecture notes, 3(4):5.
349
[20] Nesterov, Y. and Polyak, B. (2006). Cubie regularization of newton method and its global performance. Mathematical Programmingg 1077))51772005.
10

---

351
[21] Nguyen, L. M., Liu, J., Scheinberg, K., and Takáč, M. (2017a). Sarah: A novel method for machine learning problems using stochastic recursive gradient. In International Conference on Machine Learning, pages 2613-2621. PMLR.
352
[22] Nguyen, L. M., Liu, J., Scheinberg, K., and Takáč, M. (2017b). Stochastic recursive gradient algorithm for nonconvex optimization. arXiv preprint
355
356
[23] Pham, N. H., Nguyen, L. M., Phan, D. T., and Tran-Dinh, Q. (2020). Proxsarah: An efficient algorithmic framework for stochastic composite nonconvex optimization. Journal of Machine Learning Research, 21(110):
358
359
[24] Pinelis, I. (1994). Optimum bounds for the distributions of martingales in banach spaces. The Annals of Probability, pages 1679-1706.
380
361
[25]
Reddi, J., Hefny, A., Sra, S., Poezos, B., and Smola, A. (2016). Stochastic variance reduction for nonconvex optimization. In International Conference on Machine Learning, pages 314-323.
[26] Tran-Dinhs Q.. Pham, N. H., Phan, D. T., and Nguyen, L. M. (2019). Hybrid stochastic gradient descent algorithms for stochastic nonconvex optimization. arXiv preprint arXiv:1905.00920
384
365
[27] Wang, Z., Ji, K., Zhou, Y., Liang, Y., and Tarokh, V. (2019). Spiderboost and momentum: Faster variance reduction algorithms. Advances in Neural Information Processing Systems, 32:2406- 2416.
366
357
388
[28] Xiao, L. and Zhang, T. (2014). A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24(4):2057-2075.
369
370
[29] Xu, Y., Jin, R., and Yang, T. (2017). First-order stochastic algorithms for escaping from saddle points in almost linear time. arXiv preprint 1rXiv:17/1.0194..
[30] Zhou, D., Xu, P., and Gu, Q. (2018). Stochastic nested variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, 31:3921-3932.
373
374
[31] Zhou, D., Xu, P., and Gu, Q. (2020). Stochastic nested variance reduction for nonconvex optimization. Journal machine learning research.
375

---

Checklist
378
377
1. For all authors...
378
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
379
(b) Did you describe the limitations of your work? [Yes] We note in Remark 5.2 that there is a gap in the dependency of ε between our result and the lower bound. We will explore this in future work.
381
382
383
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work studies the theoretical aspect of optimization algorithms, thus it does not have any negative social impact.
384
385
386
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
389
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
390
(b) Did you include complete proofs of all theoretical results? [Yes]
391
3. If you ran experiments..
392
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
394
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
385
396
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
397
398
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
399
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
401
(a) If your work uses existing assets, did you cite the creators? [N/A]
402
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
404
405
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
406
407
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
409
5. If you used crowdsourcing or conducted research with human subjects...
410
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
412
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
413
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
415
12


Reviews:
[{"review_id": "vnuTLuQGhn", "reviewer": "Reviewer_zSqf", "summary": "The paper proposes a new approach called \"Pullback\" for escaping saddle points and finding local minimum that matches the same complexity as SGD. The approach perturbs a stochastic gradient estimators (SARAH/SPIDER) and STORM by an element uniformly on the ball of radius $r$. The proposed method is able to find an $(\\varepsilon, \\sqrt{\\varepsilon})$-approximate local minima within $\\mathcal{O}(\\varepsilon^{-3.5})$ stochastic gradient evaluations. This is the fastest known algorithm achieving the optimal rate of $\\mathcal{O}(\\varepsilon^{-3})$. The proof techniques appear to be similar to previous works and the gradient estimator used to achieve this result is known. ", "questions": "", "limitations": "", "rating": 5, "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": "The paper is well-written and the introduction provides a sufficient background to understand the question of interest: \"Can perturbed SGD methods find local minima efficiently?\" Most of the paper is devoted to explaining the algorithm, which is done quite clearly, and a sketch of the proof. While I did not check all the details of the proof, the proof does appear correct and I appreciated that all the assumptions were clearly stated. \n\nWhile I appreciate the theoretical question of finding fastest known algorithm for escaping saddle points under the stochastic setting, I would like the author to elucidate why this question is of broader importance to the ML community. While I understand there is a line of research in this area, it is not clear to me that saddle points are even a problem when one uses a stochastic algorithm. Would the author be able to point to literature which shows that saddle points appear in large-scale problems and in particular, stochastic algorithms would get stuck in them? Or more broadly why finding a local minima in the stochastic setting is hard? I would highly suggest that the author add some experiments (simulated and/or real data) which (1). shows that the proposed algorithm is implementable and (2). if possible, generate a problem that has saddle points and run the proposed algorithm on such a problem. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations and potential negative societal impact their work. This work is purely theoretically and mainly combining known algorithms. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "dJLPO2wyeLX", "reviewer": "Reviewer_AFDY", "summary": "This papers looks into stochastic gradient methods with the goal of avoiding saddle points in nonconvex optimization. The main contribution of this work is a *perturbed* stochastic gradient framework (called \"Pullback\") which, by using a particular normalization scheme, finds an $(\\epsilon, \\epsilon_H)$-approximate local minimum (that is, an $x$ s.t. $||\\nabla F(x)|| \\leq \\epsilon$ and $\\lambda_{\\textrm{min}}(\\nabla^2 F(x)) \\geq -\\epsilon_H$) in $\\tilde{O}(\\epsilon^{-3} + \\epsilon_H^{-6})$ stochastic gradient evaluations. When $\\epsilon_H = \\sqrt{\\epsilon}$ (referred to as the \"classic setting\" in the paper), their method results in a total of $\\tilde{O}(\\epsilon^{-3})$ stochastic gradient evaluations, which improves upon all previous perturbed methods. This rate also matches (in the classic setting) the rate previously attained by SPIDER-SFO+ (+Neon2) (though this previous method requires an additional negative curvature search routine).", "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": "________  Major Comments  ________\n\nWhile it is written decently well, there is a key discussion missing from the paper that, in my opinion, is crucial to better placing the work in the right context. To elaborate, the main claim of novelty in the paper is that (focusing on the \"classic setting\" for the moment) it achieves a $\\tilde{O}(\\epsilon^{-3})$ rate for reaching an approximate local minimum using a *perturbed* SGD-type method (and so, crucially, *without* needing to rely on a (black-box) negative curvature search routine). This distinction is made because (as mentioned in the summary above), this rate has previously been achieved through a combination of SPIDER-SFO+ with Neon2. This type of simplification---particularly in the absence of improved convergence rates---certainly deserves a justification that goes beyond what is now found in the paper (\"In contrast to this line of works, our algorithm is simpler since it does not need to use the negative curvature search routine.\"). For example, exactly how much more costly is it to run the negative curvature search routine? What additional operations would it entail? Is there a (perhaps empirically motivated) setting in which perturbation really does help?\n\nThat said, I do feel this sort of improved understanding is important, in part due to earlier work in finding approximate local minima via perturbed methods (e.g., Ge et al. (2015)), and more generally as a means of validating these (intuitively appealing) perturbation schemes. These methods have also been important in the deterministic setting, e.g. Jin et al. (2017) (as the paper cites), and see also Jin et al. (2018) [3]. Admittedly this work still does not match previous methods in the general $\\epsilon_H$ setting (more on that below), but its contributions are a step in the right direction.\n\n\n________  Minor Comments  ________\n\n- Title: Should be \"Finding Approximate Local Minima\", rather than \"Finding Local Minima\"\n\n\n- p.1: \"which matches the number of gradient evaluations for gradient descent to find $\\epsilon$-stationary points\" \n\n\t- It should be clarified that this is true when only smoothness (i.e., Lipschitz continuous gradient) is assumed. With higher-order smoothness (e.g., Lipschitz continuous Hessian), better gradient evaluation complexities are possible. In fact, it would generally be helpful to mention earlier on in the paper what smoothness assumptions are made.\n\n\n- p.1: \"perturbed Stochastic gradient\" => \"perturbed stochastic gradient\"\n\n\n- p.1: The paper mentions \"$\\epsilon$-stationary points\" without first defining it or contrasting it with approximate local minima.\n\n\n- p.2: \"Besides, we show\" => \"{Furthermore/In addition/etc.}, we show\"\n\n\n- p.2: \"To compare with, we summarized related results\" => \"To compare with previous methods, we summarize related results\"\n\n\n- p.2: \"Comparison of of different optimization algorithm for find approximate local minima of non convex online problems.\" => \"Comparison of different optimization algorithms for finding approximate local minima of nonconvex stochastic problems.\"\n\n\n- p.2: \"In specific\" -> \"Specifically\"\n\n\n- p.3: \"Assumption 3.2 is standard in online/stochastic optimization for finding second-order stationary points\"\n\n\t- It would be better to stick to either \"approximate local minima\" (as defined in the introduction), or \"second-order stationary point\" (though this is only later defined).\n\n\t- In fact, the assumption is standard for settings outside of searching for approximate local minima; perhaps a better phrasing would be: \"Assumption 3.2 is standard in online/stochastic optimization, including for finding approximate local minima, and immediately...\"\n\n\n- p.4: \"which is in the same order as GD for finding $\\epsilon$-stationary points.\"\n\n\t- Again, it depends on the level of smoothness assumed, and so this should be clarified.\n\n\"in the same order\" => \"of the same order\"\n\n\n- p.4: \"competative\" => \"competitive\"\n\n\n- p.4: \"big batch of stochastic gradient\" => \"big batch of stochastic gradients\"\n\n\n- p.4: \"is that, it\" => \"is that it\"\n\n\n- p.5: In Algorithm 1, it would be nicer to e.g. have {\"PullBack\"} as a (right-aligned) comment (or something similar).\n\n\n- p.5: \"which starts at m_s-th step\" => \"which starts at the m_s-th step\"\n\n\n- p.5: \"well-control\" => \"carefully control\"\n\n\n- p.6: Regarding the reference in Remark 5.2 to the lower bound of Arjevani et al. (2020): as stated, the remark is misleading, as the lower bound is for stochastic first- and second-order methods. (In contrast, SPIDER and SPIDER-based methods rely on multi-point queries). Arjevani et al. also give a stochastic first- and second-order method (Algorithm 5) which achieves (ignoring Lipschitz and variance parameters) a rate of $\\tilde{O}(\\epsilon^{-3} + \\epsilon^{-2}\\epsilon_H^{-2}+\\epsilon_H^{-5})$, though it also relies on a negative curvature estimation.\n\n\n- p.9: \"Our results show that simple perturbed gradient methods can be as efficient as more sophisticated algorithms for finding local minima.\"\n\n\t- The authors should clarify here that they are as efficient *in the classic setting*, and are only nearly as efficient in the more general setting.\n\n\n- It would be useful to mention the following works, given the way they also highlight, in the deterministic setting, the distinction between pertubation-based and non-perturbation-based methods for finding approximate local minima: \n\t- Agarwal et al. (2017) [1]\n\t- Carmon et al. (2018) [2]\n\t- Jin et al. (2018) [3]\n\n\n[1] Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. \"Finding approximate local minima faster than gradient descent.\" In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1195-1199. 2017.\n\n[2] Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. \"Accelerated methods for nonconvex optimization.\" SIAM Journal on Optimization 28, no. 2 (2018): 1751-1772.\n\n[3] Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. \"Accelerated gradient descent escapes saddle points faster than gradient descent.\" In Conference On Learning Theory, pp. 1042-1085. PMLR, 2018.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors study the theoretical aspect of optimization algorithms, which they have adequately addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "ES0d0Ln4VQX", "reviewer": "Reviewer_wd5r", "summary": "This paper presents a perturbed stochastic gradient framework for solving the stochastic optimization problem and finding local minimum. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposed a novel method of perturbed gradient descent and tackled the challenges of finding local minimum for general (nonconvex) optimization problems. The literature review, comparison with existing methods along with the limitations, motivation of the proposed method, and theoretical analysis were very well written and the thought process was very clear. There are a few questions and concerns, and I am listing them here:\n1. As authors were trying to answer the question if PGD can get to local minimum with theoretical guarantee, I am wondering what are the most significant contributor to such guarantee. What is the interplay between the Pullback and two phase design? \n2. I am not sure if the pullback was fully justified in the theoretical analysis. For example, could you be more specific on the step-size?\n3. I was expecting further justification of the proposed method with empirical study. \n\nOverall, I think it would be better to justify pullback with more details in the theory and with empirical study on both the step-size mechanism and the two phase design. \n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any potential issue related to societal impact. Regarding the limitation of the work, I have already stated it in the main review section.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not have ethical concerns to the work. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "7_n883X4QtC", "reviewer": "Reviewer_Au4C", "summary": "This paper studies the perturbed gradient methods for stochastic optimization to escap from saddle points and find local minimum. New complexity is proved, which is sharper than the previous results.", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "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": "Originality: This paper studies the perturbed gradient methods for stochastic optimization to escap from saddle points and find local minimum. The new $O(\\epsilon^{-3})$ complexity is proved, which is sharper than the revious $O(\\epsilon^{-3.5})$ one of SSRGD, and maches the $O(\\epsilon^{-3})$ one of SPIDER+DFO$^+$, which is achieved by a more complex negative curvature search. I think this is a novel contribution.\n\nQuality: The theory is technically solid. It is supported by proofs. This is a complete work.\n\nClarity: This paper is written well. The proof is organized well. The main resutls are proved in only three pages.\n\nSignificance: This paper proposes a new technique and achieves the state-of-the-art result by a simpler method. It address a difficult task in a better way than previous work. I think it is a significant job. Other researchers may be likely to follow this work.\n\nI am not familar with the topic of escaping from saddle points in nonconvex stochastic optimization. No comment and criticism for this paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitation is discussed in Remark 5.2.", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes and analyzes a stochastic first-order optimization method called “Pullback,” proving that it achieves the optimal rate of convergence to $(\epsilon,\sqrt{\epsilon})$-approximate local minima under appropriate assumptions. 

After reading the paper and discussing it with the reviewers, I concur with reviewer ADFY’s major concern, that the complexity bound proved in the paper was known under identical assumptions. It is true that prior results on perturbed SGD/AGD also did not strictly innovate on oracle complexity, but I believe the significance of those papers was mostly due to them considering very minor changes to classical algorithms. In contrast, the proposed algorithm seems like a fairly intricate modification of SPIDER and STORM.

Since the proposed theoretical guarantee does not innovate on oracle complexity and does not pertain to a well-known method, its remaining pathway to significance is through showing that the proposed algorithm performs better in practice than existing ones. In their replies, the authors suggest that this is indeed the case, and report some preliminary empirical findings backing these claims. However, the submission itself has no experiments and the information in the authors’ reply is not sufficient for getting a clear picture of the practical performance of the proposed method. For example, the authors do not indicate how the different algorithms are initialized, and whether the poor performance of SGD and SPIDER are related to a pathological initialization. Moreover, a single optimization problem would not make a convincing case for the performance of any optimization method.

With these observations in mind, I encourage the authors to revise and resubmit their paper, placing a much greater emphasis on the practical performance of the algorithm. 
Decision: Reject