Zeroth-Order Negative Curvature Finding: Escaping Saddle Points  without Gradients
Authors: Hualin Zhang
Huan Xiong
Bin Gu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Non-Convex
Optimization
Zeroth-Order
Saddle Point

Abstract: We consider escaping saddle points of nonconvex problems where only the function evaluations can be accessed. Although a variety of works have been proposed, the majority of them require either second or first-order information, and only a few of them have exploited zeroth-order methods, particularly the technique of negative curvature finding with zeroth-order methods which has been proven to be the most efficient method for escaping saddle points. To fill this gap,  in this paper, we propose two zeroth-order negative curvature finding frameworks that can replace Hessian-vector product computations without increasing the iteration complexity. We apply the proposed frameworks to ZO-GD, ZO-SGD, ZO-SCSG, ZO-SPIDER and prove that these ZO algorithms can converge to $(\epsilon,\delta)$-approximate second-order stationary points with less query complexity compared with prior zeroth-order works for finding local minima.

Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients
Hualin Zhang' Huan Xiong Bin Gu
Nanjing University of Information Science & Technology
2 Harbin Institute of Technology
Mohamed bin Zayed University of Artificial Intelligence (zhanghualing) in98, huan. xiong m jsguhinnjsnniinmilll com
Abstract
We consider escaping saddle points of nonconvex problems where only the function evaluations can be accessed. Although a variety of works have been proposed, the majority of them require either second or first-order information, and only few of them have exploited zeroth-order methods, particularly the technique of negative curvature finding with zeroth-order methods which has been proven to be the most efficient method for escaping saddle points. To fill this gap. in this paper, we propose two zeroth-order negative curvature finding frameworks that replace Hessian-vecte vecttor product computations without increasing the iteration complexity. We apply the proposed frameworks to ZO-GD, ZO-SGD, SC-SCSG Zo SP-DPR and prove that these 70 algorithms can converge to (c, appproxxiaa second- order stationary points with less query complexity compared with prior zeroth-order works for finding local minima.
Introduction
Nonconvex optimization has received wide attention in recent years due to its popularity modern machine learning (ML) and deep learning (DL) tasks. Specifically, in this paper, we study the following unconstrained optimization problem:
12
min f(z) = Σ f((x), FER
where both fi(-) and f()) can be nonconvex. In general, finding the global optima of nonconvex functions is ha-hard. Fortunately, finding local optima is alternative because has been shown in theory and practice that local optima have comparable performance capabilities to global optima in many machine learning problems [14, 15, 26, 17, 16, 19, 27]. Gradient-based methods have been shown to be able to find an e-approximate first-order stationary point (I) [x)]] < <) efficiently, both in the deterministic setting (e.g., gradient descent [32]; accelerated gradient descent [8, 29]) and stochastic setting (e.g., stochastic gradient descent [32, 37]; SCSG [28]; SPIDER [13]). However, in nonconvex settings, first-order stationary points can be local minima, global minima, or even saddle points. Converging to saddle points will lead to highly suboptimal solutions [20, 39] and destroy the model's s performance. Thus, escaping saddle points has recently become an important research topic in nonconvex optimization.
Several classical results have shown that, for H~Hessian Lipschitz functions (see Definition 1), using the second-order information like computing the Hessian [33] or Hessian-vector products [1, 9, 2), can find e-approximate second-order stationary point (SOSP, [V]()]] < c and f²)( > - Ip..). However, when the dimension of x is large, even once access to the Hessian
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

is computationally infeasible. A recent line of work shows that, by adding uniform random pertur- bations, first-order (FO) methods can efficiently escape saddle points and converge to SOSP. In the deterministic setting, [22] proposed the perturbed gradient descent (PGD) algorithm with gradient query complexity (log' d/c²) by adding uniform random perturbation into the standard gradient descent algorithm. This complexity is later improved to Ollgg 6 d/5)..T5) by the perturbed accelerated gradient descent [24] which replaces the gradient descent step in PGD by Nesterov's accelerated gradient descent.
A summary of the results of finding (e, -approxxime SOSPs (see Definition 2) by the zeroth-orded order algorithms. (CoordGE, GaussGE, and RandGE are abbreviations of "coordinate-wis gradient estimator", "Gaussian random gradient estimator" and "uniform random gradient estimator", respectively. RP, RS, and CR are abbreviations of "random perturbation", "random search" and "cubic regularization", respectively.)
Table 1:
Algorithm
Setting
Zo Oracle
Main Techniques
Function Queries
ZPSGD [23]
Deterministic
GaussGE + Noise
RP
5 d d
PAGD [41]
Deterministic
CoordGE
RP
RSPI [30]
Deterministic
CoordGE
RS + NCF
d e//3
Theorem.
Deterministic
CoordGE
NCF
+
dlogg
63.3
ZO-SCRN [5]
Stochastic
GaussGE
CR
0
5.5
d
+
2..
t
Theorem. 3
Stochastic
CoordGE
NCF
d
+
d
27
88
Theorem. 5
Stochastic
CoordGE + (RandGE)
NCF
d
10/3
Theorem. Stochastic
CoordGE
NCF
788
i guarantees (c, Ol -aproxxaito SOSP, and & guarantees (c, 2/3 ( approximate SOSP.
Another line of work for escaping saddle points is to utilize the negative curvature finding (NCF), which can be combined with c-approximate first-order stationary point (FOSP) finding algorithms to find an (c, a)-approxee SOSP. The main task of NCF is to calculate the approximate smallest eigenvector of the Hessian for given point. Classical methods for solving NCF like the power method and Oja's s method need the computation of Hessian- vector products. Based on the fact the Hessian-vector product can be approximated by the finite difference between two gradients, [42, 4] proposed the FO NCF frameworks Ncon+ and Neon2, respectively. In general, adding perturbations in the negative curvature direction can escape saddle points more efficiently than adding random perturbations by a factor of O(poly(log d)) in theory. Specifically, in the deterministic setting, CDHS [9] combined with Neon2 can find an (c, d)-approximmte SOSP in gradient query complexity Ólog d/51.75). Recently, the same result was achieved by a simple single-loop algorithm [44], which combined the techniques of perturbed accelerated gradient descent and accelerated negative curvature finding. In the online stochastic setting, the best gradient query complexity result Ó(1/e²) is achieved by SPIDER-SFO* [13], which combined the near-optimal c-approximate FOSP finding algorithm SPIDER and the NCF framework Neon2 to find (c, 5) -approximate SOSP.
However, the gradient information is not always accessible. Many machine learning and deep learning applications often encounter situations where the calculation of explicit gradients is expensive or even infeasible, such as black-box adversarial attack on deep neural networks [36, 31, 10, 6, 40) and policy search in reinforcement learning [38, 11, 25). Thus, zeroth-order (7O) optimization, which uses function values to estimate the explicit gradients as an important gradient- based black-bor method, is one of the best options for solving this type of ML/DL problem. A considerable body of work has shown that ZO algorithms based on gradient estimation have comparable convergence rates to their gradient-basee based counterparts. Although many gradient estimation- based ZO algorithms have been proposed in recent years, most of them focus on the performance of converging to FOSPs [34, 18, 21, 13], and only few of them on SOSPs [23, 41, 30, 5].
As mentioned above, although there have been several works of finding local minima via ZO methods, they utilized the techniques of random perturbations [23, 41], random search [30], and cubic regularization [5], as shown in Table 1, which are not the most efficient ones of escaping saddle points discussed before. Specifically, in the deterministic setting, [23] proposed the ZO perturbed

---

stochastic gradient (ZPSGD) method, which uses a batch of Gaussian smoothing based stochastic ZO gradient estimators and adds a random perturbation each iteration. As result, ZPSGD can find an c-approximate SOSP using Ô (d fc)) function queries. [41] proposed the perturbed approximate gradient descent (PAGD) method which iteratively conducts the gradient descent steps by utilizing the forward difference version of the coordinate-we
gradient estimators until it reaches a point with small gradient. Then, PAGD adds uniform perturbation and continues the gradient descent steps. The total function queries of PAGD to find an 6-approximate SOSP is Ô (d d/e²). Recently, [30] proposed the random search power iteration (RSPI) method, which alternately performs random search steps and power iteration steps. The power iteration step contains an inexact power iteration subroutine using only the ZO oracle to conduct the NCF, and the core idea is to use a finite difference approach to approximate the Hessian-vector product. In the stochastic setting, [5] proposed zeroth- order stochastic cubic regularization newton (ZO-SCRN) method with function query complexity Ô (d/ 2/2) using Gaussian compling-basee gradient estimator and Hessian estimator. Unfortunately, each iteration of ZO-SCRN needs to solve cubic minimization subproblem, which does not have closed- form- solution. Typically, inexact solvers for solving the cubic minimization subproblem need additional computations of the Hessian-vecte vector product [1] the gradient [7].
Thus, it then natural explore faster ZO negative curvature finding based algorithms to make escaping saddle points more efficient. To the best of our knowledge, negative curvature finding algorithms with access only to ZO oracle still a vacancy in the stochastic setting. Inspired by the fact that the gradient can be approximated by the finite difference of function queries with high accuracy, a natural question is: Can we turn FO NCF methods (especially the state-of-the ofte-of-the-arl Neon2) into ZO methods without increasing the iteration complexity and turn ZO algorithms of finding FOSPs into the ones of finding SOSPs?
Contributions. We summarize our main contributions as follows:
We give an affirmative answer to the above question. We propose two ZO negative curvature finding frameworks, which use only function queries and can detect whether there is a negative curvature direction at a given point x on a smooth, BessiannLLischite function f Rd - R in offline deterministic and online stochastic settings, respectively.
We apply the proposed frameworks four ZO algorithms and prove that these ZO algorithms can converge to (e, appproooee SOSPs, which are ZO-GD, ZO-SGD, ZO-SCSG, and ZO-SPIDER.
In the deterministic setting, compared with the classical setting where 8 = O(Ve) [22, 24, 23, 41], or the special case 8 = 2/3 [30], our Theorem 4 is always not worse than other algorithms in Table 1. In the online stochastic setting, all of our algorithms don't need to solve the cubic subproblem as in ZO-SCRN and our Theorem 6 improves the best function query complexity by a factor of ((1/Ve).
2 Preliminaries
Throughout this paper, we use || to denote the Fuclidean norm of a vector and the spectral norm of matrix. We use O(.) to hide the poly-logarithmic terms. For given set S drawn from [n] == (1,2....,n), define fs(.) == |s| Eies f((.).
Definition 1. For a twice differentiable nonconvex f: Rd + R.
f is E-Lisschitz smooth Vz, y E Rd, [V] - Vf(w)) s f|1x yll-
* is p-Hessian Lipschitz if E Ed. (V - S p||:r vll-
Definition 2. For a twice differentiable nonconvex function f: Rd - R, say
* x. E Rdd is an c-approximate first-order stationary point if | f (2) S x E dd an aapproxitte second-order stationary point if [ S fz)(2) 2 -81
We need the following assumptions which are standard in the literature of finding SOSPs [4, 13, 44]. Assumption 1. We assume that f(-) in (1) satisfies:
3

---

= f < oo where x" == argming f(x).
Each component function f1(x) is E-Lipschitz smooth and p-Hessian Lipschitz.
(For online case only) The variance of the stochastic gradient is bounded: Vx E E V vf(x)]] - o².
We'll also need the following more stringent assumption to get high-probability convergence results of ZO-SPIDER.
Assumption 2. We assume that Assumption 1 holds, and addition, the gradient of each component function fa) satisfies Vi R. V o².
2.1 ZO Gradient Estimators
Given smooth, Hessian Lipschitz function f, central difference version of the deterministic coordinate-wise gradient estimator is defined by
f(x + ue;) f(x ues))
coord (x)
Ci:
(CoordGradEst)
2/1
where 6 denotes a standard basis vector with 1 at its i-th coordinate and 0 otherwise; l is the smoothing parameter, which is sufficient small positive constant. central difference version the random gradient estimator is defined by
V rand (x) 50 + pu) f(x pm)
U,
(RandGradEst)
2/1
where E Rd is a random direction drawn from uniform distribution over the unit sphere; is the smoothing parameter, which is sufficient small positive constant.
Remark 1. Deterministic vs. Random: CoordGradEst needs times more function queries than RandGradEst. However, will be discussed in section 4, it has lower approximation error and thus can reduce the iteration complexity. Central Difference vs. Forward Difference (please refer to Appendix A. Under the assumption of Hessian Lipschitz, smaller approximation error bound can be obtained by the central difference version of both CoordGradEst and RandGradEst.
2.2 ZO Hessian-Vectee Product Estimator
By the definition of derivative: f²f(x) v lim -((-+t))-VVaaa we have V²f(2) can be approximated by the difference of two gradients Vf(x+o)- -Vf(=) for some with small magnitude. On the other hand, vf v), fa)) can be approximated by Veooral(z: (x + v), V Vecord (() with high accuracy, respectively. Then the coordinate-wise Hessian-vector product estimator is defined by:
(z) f(x + to x f(x + ue:) + f(x p..)) f(x + pc:) es.
2/
Note that do not need to know the explicit representation of Hx) is merely used notation for virtual matrix and can be viewed as the Hessian V f²)( with minor perturbations. As stated in the following lemma, the approximation enror efficiently upper bounded.
Lemma 1. Assume that f is p- p-Hessian Lipschitz, then for any smoothing parameter μ and E Rd. have
[[H [3 < (1c vdp2/13
The ZO Hessian-vector product estimator was previously studied [43, 30], but we provide a tighter bound than that in Lemma 6 in [30]. This is because we utilize properties of the central difference version of the coordinate-wi wise gradient estimator under the Hessian Lipschitz assumption. It is then directly concluded that, if f(-) is quadratic, we have p 0 and (x)v fzf(2)|] = 0.

---

3 Zeroth-Order Negative Curvature Finding
In this section, we introduce how to find the negative curvature direction near the saddle point using zeroth-order methods. Recently, based on the fact that the Hessian-vector product V
f(x) u can
be approximated by Vf(x v) V fx() with approximation error up to O1I [|]= [4] proposed
a FO framework named Neon2 that can replace the Hessian-vector product computations in NCF subroutine with gradient computations and thus can turn a FO algorithm for finding FOSPs into a FO
algorithm for finding SOSPs. Enlightened by Neon2, we propose two zeroth-order NCF frameworks (i.e., ZO-NCF- and Deieeeiitemmiiistti) using only function queries to solve nonconvex problems in the online stochastic setting and offline deterministic setting, respectively.
3.1 Stochastic Setting
In this subsection, we focus on solving the NCF problem with zeroth-order methods under the online stochastic setting and propose ZO-NCF-Onlins Before introducing ZO-NCF NCF-Online, we first introduce 2O-NCF NCFFOOnlie- Weak with weak confidence of 2/3 for solving the NCF problem.
We summarize 70-NCF-Omline Weak in Algorithm 1. Specifically, Z0-NCF-Online Weak consists of most T ( log 4) random perturbation with small magnitude a as the starting point. At the 1-th iteration where I 1, , T. set 14, ||,, zoll || to be the smoothing parameter μ in (2). Then we keep updating It-1 = - - (In) mn) where Hy, (2n) - -x) is the 70 Hessian-vector product estimator and stops whenever | æo 2 or the maximum iteration number T is reached. Thus as long as Algorithm I does not terminate, we have that the approximation error ||H, (zo) z0) (=))(=)) 2o)il can be bounded by O(vdr*) according to Lemma 1. Note that, although online in [4] which used the the error bound is poorer by factor of O(v compared to Neon week
82-) iterations and works follows: Given detection point Io, add
difference of two gradients to approximate the Hessian-vector product and achieve an approximation error up (r²)), with choice of in Algorithm 1, the error term is still efficiently upper bounded.
Algorithm 1 ZO-NCF-Onling Weak (f. zo. 8)
T + log(100d) < (1002)1cpp' r f- (100d)Coo
1: 1 C (00g)
2: { < e'
TeT with g' 10,
3: 31 f- x0 +
4: for t = =l,..., do
5: Mr + || zool
6: I++1 It f f: (1r) - mo) with μ pe and i E [ni]
7: if [T Toll ll 2 then return v =oo for uniformly random
Return 1=1
Other than the additional error term caused by 70 approximation, the motivation of CO-NCF-Onnlin Weak is almost the same as Neon online That is, under reasonable control of the approximation
error of the Hessian-vector product, using the update rule of Oja's method [35] to approximately
calculate the eigenvector corresponding to the minimum eigenvalue of fzx) = 1 E fl(oo).
Under similar analysis. we conclude that as long as the minimum eigenvalue of fZ)(zz) satisfies
Amin 2 f(x))) S -8, ZO-NCF Online Weak will stop before T and find negative curvature direction that aligns well with the eigenvector corresponding to the minimum eigenvalue of V v Then we have the following lemma:
Lemma -ZO-NCF--nline- Weak). The output v of Algorithm satisfies: If Xmii then with probability least 2/3, 1 and o 2 f(zo)u S - 33.
( (V2 ((o)) < -8.
We summarize ZO-NCF- Online in Algorithm 2. Specifically, ZO-NCF- repeatedly calls Zo- SLEF-Online-Werd for (log(1 /p)) times to boost the confidence of solving the NCF problem from 2/3 to 1 p. We have the following results:
Lemma 3. In the same setting as in Algorithm 2, define 2 E v. OHHi, (2o))v. Then, if ||a||| 16dp
and m = O (( with probubility at least - Ps we have |0]
5

---

Algorithm 2 ZO-NCF-Online
Input: f() = - Tu. 8 0, p E (0, 1].
1: for (.,........ (log(1/pp) do
2:
U/ k ZO-NCF-ONlimg Weak (f. To. 6)
3:
uf # then
m + 0e e 1/g)1/p) - O )o3
4:
5:
Draw 21 21.... Im uniformly randomly from [n]
(v") (mr))r'
6:
2j 1 k= w
7:
if S T
then return e = Dj
Return U 1
Theorem 1. Let [xx) = 1 Ei= li(x)) where each Si is t-smooth and p-Hessian Lipschitz. For
every point 2o E RRd, every d E (0, f. the output of Algorithm 2 satisfies that, with probability least p. If L, then f2)( = 5I; If + 1. then ||||| and v V S - The
total function query complexity is
dloog (d/D) (dog))
3.2 Deterministic Setting
In this subsection, we focus on solving the NCF problem with zeroth-order methods under the offline deterministic setting and propose Algorithm 3. Since we want to compute the cigenvector corresponding to the most negative eigenvalue of (20) approximately, one can convert it into an approximated top eigenvector computation problem of M := [
We summarize DD-NCF-Determiniisti in
(1 I This is because all eigenvalues of V V=)(2)) in [-
will be mapped to eigenvalues of M [-1, 1], and all eigenvalues V fzo) smaller than -8 will
be mapped eigenvalues of M greater than 1 +
Algorithm 3 300-NCF-Determinns
Input: Function f(.), point zo. negative curvature 0, confidence p E (0, 1].
o log 1 v - (d/p) -20 8 T
1: T
& (do
2: { < e' V8 with g I0,
le'l
3: #1 f In + E. yo + 0,91 E
4: for t = 1.....T . do
5: 1t = |vlll
6:
9t+1 = 2.M(Y:) - yt where = (- +11
7: I++1 = Tu Vt+1 M(yi
8: if | voll 2 then return I -20
Ze+-
Return
Similar to MO-NCF-Onllie-Wern ZO-NCF-Determinnst starts by adding a random perturbation
E to the detection point Fg. To find the negative curvature direction v V (²)())) such that T ((ao))))) S the classical power method which updates through ÆT+1
xo + M 5
[30] will take T 22(5) number of iterations since eigenvalues of M greater than 1 + af grows in speed (1 + 5/2)T. To reduce the iteration complexity T, we can replace the matrix polynomial M with the matrix Chebyshev polynomial (MM) and virtually update IT+1 = zo + Tr (M)5.
Definition 3. Chebyshev polynomial (Tx(x) of the first kind is To(x)
[((x) x,
T (z)) 2x Ta Tn(x) T (z),
then it satisfies T((x)= { cos arccos(
1-,, H[(x V2² 1)" (x -=2-11"1 x>1

---

In the matrix case, we have the so-called matrix Chebyshev polynomial (MM [3], which satisfies:
T++(MM) = 2 - 7T-1(M) Thus, cigenvalues of M greater than + & will grow to 48
(1 (1+ (5/40)) + 8/22
T' 2 (1+ vōtl) so we only need to choose T 2 vejō.
On the other hand, since we only have access to the zeroth-order information, we need to stably compute the matrix Chebyshev polynomial. In algorithm 3, we set f4 I|vell and use M(ye) = ( + // ))yr approximate My, with approximation error up to ( With proper choice of r, it allows us to use the inexact backward recurrence [3] to ensure stable computation of matrix Chebyshev polynomial:
yo
1/2 =, Me+1 2M( Yt-1-
Then the output 2741 2o + pr+1 - -(rr) is close to zo + Tr (M) with a small approximation error. Finally, we have the following theorem:
Theorem 2. Let f(z) = A Ei=1 fa(z) where each fi is E-smooth and p-Hessian Lipschitz. For every point E RR, every 8 E (0, fl. the output of Algorithm 3 satisfies that, with probability at least 1 - p: If 1,, then 2 (x))) = -ŌI; If + 1, then ||||| = and v V (ro)e S - The function query complexity is
d log _ Ve 0
v8
4 Applications of Zeroth-Order Negative Curvature Finding
In this section, focus applying the zeroth-order negative curvature frameworks the following Zo algorithms: ZO-GD, ZO-SGD, ZO-SCSG, and ZO-SPIDER. The following result shows that one can verify if point is e-approximate FOSP using CoordGradEst.
Proposition 1. In the online setting, using CoordGradEst with a batch size of ( 1286² + 1) log
and smoothing parameter S V 'ppvd' we can verify with probability at least - p. either [ 2 c/2 or [[V S c. In the deterministic setting, using once computation of Co- ordGradEst with smoothing parameter p S 2 we can verify with probability 1, either [[V 2 c/2 or [Vf S.
3r
4.1
Applying Zeroth-Order Negative Curvature Finding to ZO-GD and ZO-SGD
We apply ZO-NCF-Online to ZO-SGD to turn it into a local minima finding algorithm, and propose ZC- in Algorithm 4. At each iteration, we use a batch size of O e log [2 Coord- GradEst to verify if x; is an c-approximate stationary point. If not, ZO-SGD CO--SD-NCE DCFD-NCF-LO either estimates the gradient (s)( TST Eies f((( by CoordGradEst (Option I) or RandGradEst (Option
II) with both mini-batch size ( If so, we call the ZO-NCF-Online subroutine. Then, If we find an approximate negative curvature direction u around zt, then we update -T-1 by moving from &, in the direction with step-size 5/p. We have the following theorem:
Theorem 3. Under Assumption 1, we set #1
20yd and other parameters as follows,
Option I:|S] max
320²
2
0'A1 1), K
=0(
iA
2
>
48
12
V 4pvdd
3e
2 k 02
P²A 83
dia
{V
3E
Option H1|S = max
) =
H2 = min
2
32d
4pd
32vdl
where μr and p2 are only used in Line and Line (or Line 6) of Algorithm 4, respectively. With probability at least 1 - Algorithm 4 outputs an (c, -ppprroxxee local minimum in function query complexity
Option 1:6 do
do² do
p
LOlA, e
doz do
dl2 p2
Option 11:6
+
288
85
283
85
7

---

Algorithm 4 ZO-SGD-NCC
Input: Function starting point Ho, confidence p (0, 1), 0 and ó 0.
1: for t .,,., K - do
2:
uniformly randomly choose a set B with batch size O log(2K (2)p
3:
if (V [Voora/ 2 then
4:
uniformly randomly choose S [n]
5:
Option I: 2++1 It v/ coord (21)) Option II: I+41 t It n rand.fs(s))
6:
7:
else
8:
<- 70-NCF-Online (f, 6, 2k
9:
if v then return
else T++1 24
Algorithm 5 570-GD-NCF
Input: Function f, starting point To. confidence p E (0, 1), > and 0.
1: for ( o,..,, K
do
2: if V c (xx)) 3R then
4
3:
Option 1+41 f- Ft. v/ coord (xt)
4:
Option II: : F++1 t Dt 17 rand (fte
5: else
6:
- ZO-NCT-Detemministt ( tt. 6, ))
7: if then return
8: else T++1
31
2
Remark Note that the dominant term of the function query complexity in Option is ( while
in Option II is ( This because CoordGradEst has a lower approximation ervor and thus can reduce the iteration complexity by a factor of d. Then the function query complexity of Option II is dominated by evaluating the magnitude of the gradient (Line 3 in Algorithm 4).
the Deterministic setting, we apply Z0-NCr--eterminnistic to ZO-GD to turn into local minima finding algorithm and propose ZO- DD-FFD-CF in Algorithm 5. The update rule of ZO-GD JO-GD-NCF is similar to that in ZO-SGD-NCE, the only difference is that we don't 't need to use mini-batch sampling of the stochastic gradient. Similarly, we have the following theorem:
Theorem 4. Under Assumption 1, we set #1 20Vd and other parameters as follows,
Option I: K= = x00
p2A 83
EA
3e Apvd'
), 48 48. H2
V
Option II: K= 1
deD
1
{V
3e
), sdl. P2 min
83
Apd 16vde)
where μl and #2 are only used in Line and Line (or Line 4) of Algorithm 5, respectively. With probability at least 1 1 Algorithm 5 outputs an (e, 8) -appproxxeatee local minimum in function query complexity
Option I: 8 deAs
Ve A V8 83
Option II: Ô
2
V8
83
4.2 Applying Zeroth-Order Negative Curvature Finding to ZO-SCSG and ZO-SPIDER
In the stochastic setting, also apply the zeroth-order negative curvature finding to the variance reduction based algorithms: SCSG [28] and SPIDER [13]. Due to space limitation, We defer the detailed discussions of these applications Appendix E and F.
To apply Z0-NCF-Online to SCSG, we first propose zeroth-order variant of the SCSG [28] method in Algorithm 6. At the beginning of the j-th epoch, estimate the gradient fz, (āj-1) by

---

CoordGradEst over batch sampling set I, with size B. In the inner loop iterations, the stochastic gradient estimator o/h1 either constructed by CoordGradEst by RandGradEst over mini-batch sampling set T with size b. Then we apply ZO-NCF-Online to ZO-SCSG and propose the ZO-SCSG-NCF method (see Algorithm 7).
Theorem 5 (informal, full version deferred to Appendix E). With probability at least 3. for both Option and Option II, Algorithm outputs an (e, (.op)))ppxiimtte local minimum in function query complexity
SAS E303 83
0² 2
10, 22 82
Odd
+ 88 82)
We apply ZO-NCF-Online to ZO-SPIDER to turn it into a local minima finding algorithm and propose ZO-SPIDER-NCIF in Algorithm As a by-product, we also propose zeroth-order variant of the SPIDER method in Appendix G that can converge an e-approximate FOSP with high probability rather than expectation. Using the same technique as in SUDER-SFO' [13], that is, instead of moving in large single step with size 6/p along the approximate negative curvature direction as in ZO-SGD-NCF and ZO-SCSG-NCE we can split into 6/())) equal length mini-steps with size 7. As result, we can maintain the SPIDER estimates and improve the so-called non-improvable coupling term 89,2 by a fact of 6.
Theorem 6 (informal, full version deferred to Appendix F). With probability at least 1. Algorithm 8 outputs an (e, -approxximee local minimum in fanction query complexity
(((0-)) oooLi (
ò ((1
slpbs
12 P
a²
odl
(2
)
12
2082
2
pe
82
Remark We can boost the confidence the of Theorem 5 and 6 to p by running log(1/p) copies of Algorithm 7 and 8.
5 Numerical Experiments
Octopus Function. We first consider the octopus function proposed by Du et al. [12]. The octopus function has 2d local optimum: x" (+ +4T)² and 2d saddle points:
(O,...,0) T,T, O..,,,
(+ 4 O)
We compare ZO-GD-NCE, ZPSGD, PAGD, and RSPI on the octopus function with growing dimen- sions. The parameters corresponding to the octopus function are set with 7 L 7 1. All algorithms are initialized at point (0, .... 0)* which is a strict saddle point and the one farthest from the optimal points among the 24 - saddle points.
We set = le - 4, upc for all experiments and report the function value v.s. the number of function queries in Figure For RSPI, we follow the hyperparameter update strategy as described in ([30], Appendix. Section F): We keep constant and update 0i = Po, an every To, iterations. We conduct grid search for To, and Po..
300
3050
4004 500 80l
3803 1988 2680 1906 2000
1000
20065 10000
1508
1500
5000 1000 1990
(a) d=10
(b) d=30
(c) d=50
(d) d=100
Figure 1: Performance of ZO-GD-NCE, ZPSGD, PAGD, and RSPI on the octopus function with growing dimensions.
The results in Figure 1 illustrate that all algorithms are able to escape saddle points. With the increase of the dimension of the octopus function, more function queries are needed for each algorithm to converge to the local minimum. Note that in all experiments, RSPI performs worse than PAGD and

---

ZO-GD-NCF, This is because RSPI is not gradient based algorithm. Although it can efficiently escape from the saddle point using the negative curvature finding, it converges very slowly when the current point is far from the saddle point due to the random search.
We defer more experimental results to Appendix G.
Conclusion
In this paper, we analyse two types of ZO negative curvature finding frameworks, which can be used to find the negative curvature directions near saddle point in the deterministic setting and stochastic setting, respectively. We apply the two frameworks to four ZO algorithms and analyse the complexities for converging to (e, oa-aprroximate SOSPs. Finally, we conduct several numerical experiments verify the effectiveness of the proposed method in escaping saddle points.
As a future work, it would be interesting to study the (zeroth-orde order) unified negative curvature finding frameworks with generic analysis that can be applied to any FOSPs finding algorithms.
Acknowledgments and Disclosure of Funding
The authors thank four anonymous reviewers for their constructive comments and suggestions. Bin Gu was partially supported by the National Natural Science Foundation of China under Grant 62076138.
References
[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, pages 1195- 1199, 2017.
[2] Zeyuan Allen-Zhu. Natasha 2: Faster non-convex optimization than sgd. Advances Neural Information Processing Systems, 31, 2018.
[3] Zeyuan Allen-Zhu and Yuanzhi Li. Faster principal component regression and stable matrix chebyshev approximation. In International Conference on Machine Learning, pages 107-115. PMLR, 2017.
[4] Zeyuan Allen-Zhn Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. Advances Neural Information Processing Systems, 31, 2018.
[5] Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order nonconvex stochastic op- timization: Handling constraints, high dimensionality, and saddle points. Foundations of Computational Mathematics, 22 22(1):35-76, 2022.
[6] Arjun Nitin Bhagoji, Warren He, Bo Li, and Dawn Song. Practical black-box attacks on deep neural networks using efficient query mechanisms. In Proceedings of the European Conference on Computer Vision (ECCV), pages 154-169, 2018.
[7] Yair Carmon and John C Duchi. Gradient descent efficiently finds the cubic-regularized non-convex newton step. arXiv preprint 1rXiv:1612.000
2016.
[8] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. "convex until proven guilty": Dimension-free acceleration of gradient descent on non-convex functions. International Conference Machine Learning, pages 654-663. PMLR, 2017.
[9] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal on Optimization, 28(2): 2018.
[10] Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 15-26,
2017.
10

---

[11] Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard Turner, and Adrian Weller Structured evolution with compact architectures for scalable policy optimization. In Interna- lional Conference on Machine Learning, pages 970-978. PMLR, 2018.
[12] Simon $ Du, Chi Jin, Jason D Lee, Michael Jordan, Aarti Singh, and Barnabas Poczos. Gradient descent can take exponential time to escape saddle points. Advances in Neural Information Processing Systems, 30, 2017.
[13] Cong Fang. Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non- convex optimization via stochastic auth-integrated differential estimator. Advances in Neural Information Processing Systems, 31, 2018.
[14] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-online stochastic gradient for tensor decomposition. Conference on learning theory, pages 797-842. PMLR, 2015.
[15] Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. Advances in Neural Information Processing Systems, 29, 2016.
[16] Rong Ge, Jason D. Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design. In International Conference on Learning Representations, 2018.
[17] Rong Ge and Tengyu Ma. On the optimization landscape of tensor decompositions. Advances in Neural Information Processing Systems, 30, 2017.
[18] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341 -2368, 2013.
[19] Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical systems. Journal of Machine Learning Research, 19(29):1-44, 2018
[20] Prateck Jain, Chi Jin, Sham Kakade, and Praneeth Netrapalli. Global convergence of non-convex gradient descent for computing matrix squareroot. In Artificial Intelligence and Statistics, pages 479 488. PMLR, 2017.
[21] Kaiyi Ji, Zhe Wang. Yi Zhou, and Yingbin Liang. Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization. International Conference on Machine Learning, pages 3100-3109. PMLR, 2019.
[22] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, pages 1724-1732. PMLR, 2017.
[23] Chi Jin, Lydia T Liu, Rong Ge, and Michael Jordan. On the local minima of the empirical risk. Advances in Neural Information Processing Systems, 31, 2018
[24] Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference On Learning Theory, pages 1042-1085. PMLR, 2018
(25) Gangshan Jing, He Bai, Jemin George, Aranya Chakrabortty, and Piyush K Sharma. Asyn- chronous distributed reinforcement learning for Iqr control via zeroth-order block coordinate descent. arXiv preprint arXiv:2107. 12416, 2021.
[26] Kenji Kawaguchi. Deep learning without poor local minima. Advances in Neural Information Processing Systems, 29, 2016.
[27] Kenji Kawaguchi, Jinoyang Huang, and Leslie Pack Kaelbling. Every local minimum value is the global minimum value of induced model in nonconvex machine learning. Neural Computation, 31(12):2233-322 2019.
[28] Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum sum optimization via scsg methods. Advances in Neural Information Processing Systems, 30, 2017.
11

---

[29] Huan Li and Zhouchen Lin. Restarted nonconvex accelerated gradient descent: No more polylogarithmic factor in the O complexity. arXiv preprint arXiv:2201.11411 2022.
[30] Aurelien Lucchi, Antonio Orvieto, and Adamos Solomou. On the second-order convergence properties of random search methods. Advances in Neural Information Processing Systems, 34, 2021.
[31] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. In International Conference Learning Representations, 2018
[32] Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science Business Media, 2003.
[33] Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and its global performance. Mathematical Programming. 108(1):1772205, 2006.
[34] Yurii Nesterov and Vladimir Spokoiny, Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527-566, 2017.
[35] Erkki Oja. Simplified neuron model as a principal component analyzer. Journal of Mathematcal Biology, 15(3):267-27,, 1982.
[36] Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Anan- thram Swami. Practical black-bor box attacks against machine learning. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, pages 506-519, 2017.
[37] Sashank J Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International Conference on Machine Learning, pages 314-323.40 PMLR, 2016.
[38] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as scalable alternative to reinforcement learning. arXiv preprint 1rXiv:1703.0333 03864, 2017.
[39] Ju Sun, Qing Qu, and John Wright. A geometric analysis of phase retrieval. Foundations of Computational Mathematics, 18(5): (8(5):1131-181 1131-1198, 2018
[40] Chun-Chen Tu, Paishun Ting, Pin- Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. Autozoom: Autoencoder based zeroth order optimization method for attacking black-box neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 33:742-749, 07 2019.
[41] Emmanouil- Vasileios Vlatakis-Gkarageee
Lampros Flokas, and Georgios Piliouras. Effi- ciently avoiding saddle points with zero order methods: No gradients required. Advances in Neural Information Processing Systems, 32, 2019.
Vaananouil-Vasileioss
[42] Yi Xu, Rong Jin, and Tianbao Yang. Neon+: Accelerated gradient methods for extracting negative curvature for non-convex optimization. arXiv preprint arXiv: 2017.
[43] Haishan Ye, Zhichao Huang, Cong Fang, Chris Junchi Li, and Tong Zhang. Hessian-aware zeroth-order optimization for black-box adversarial attack. arXiv preprint arXiv: 1812.1111..113777 2018.
[44] Chenyi Zhang and Tongyang Li. Escape saddle points by simple gradient-descent based algorithm. Advances in Neural Information Processing Systems, 34, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
12

---

(b) Did you describe the limitations of your work? [Yes] In the conclusion, we mention way that could improve the current work.
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Please refer to the Appendix for complete proof' the theoretical results.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/relcusing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "fdoOzmEenrB", "reviewer": "Reviewer_Sw24", "summary": "This paper investigates escaping saddle points of nonconvex problems with zeroth order gradient descent method. A general framework is proposed to capture zeroth-order GD, SGD, and some other closely related algorithms. The main result is the convergence to approximate second order stationarities of these algorithms. The main idea is believed to be inspired by [18] and [47], but the results, to my best knowledge, is novel.", "questions": "As far as I have understood, a very related former work is [47]. Even the escaping saddle points results holds for algorithms that are not studied in [47], I would like to see the technical challenges of this paper compared to [47]. Part of the difficulty should come from the diversity and complexity of the algorithms considered in this paper, but anything else? I might have missed some points as reading the paper, it would be great if the authors are willing to provide some guidance.", "limitations": "Considered the choice of hyper parameters and the assumption of Lipschitz Hessian, current experiments is not sufficient for wide application of algorithms.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The problem this paper addresses is well motivated, the writeup is easy to follow, and the novelty and contribution are easy to identified.\n\nWeaknesses: As highlighted in the beginning of the paper, the main technique is to introduce a framework to capture differential ZO methods, but the main article has not focus on this unified framework. Instead of elaborating all the algorithms, the main idea and novelty should have been treated in the main to some extent.\n\n\nThe experimental results should have been presented somewhere in the main article. Reasons of doing this: the main difficulty of using perturbed methods (which have been proven escaping saddle points) is the setting of parameters, the experiments apparently have some hints on the effects of the parameters. Moreover, it is good to see experiments on the Octopus function since it is an important motivation of using any perturbed methods to escape saddle point efficiently instead of using much simpler algorithms like GD (and many first order methods) that has been proven not converging to saddle points either. Brief discussion on these results will make the paper more attractive.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "f8_yqDtieT_", "reviewer": "Reviewer_2jjY", "summary": "The paper addresses the problem of finding stationary points in non-convex settings that are not saddle points (i.e. satisfies second order optimality). It proposes two negative curvature finding (NCF) frameworks that only use zero-order oracles: one offline deterministic and the other online stochastic. The NCF frameworks provide two options of gradient estimation: a coordinate-based estimator and a randomized estimator. The paper then applies this framework to four algorithms and show that these algorithms converge to second-order stationary points. Convergence analysis gives complexity in terms of function queries.", "questions": "1. The authors describe situations when gradient calculations are expensive or infeasible (lines 55-56). Are there empirical results that their gradient-free methods outperform existing methods in these situations?\n2. Experiments would also help to strengthen the claim that iteration complexity does not significantly increase. It would be good to have empirical results on the accuracy versus number of iterations needed, as well as accuracy versus training time, benchmarked against state of the art methods.\n3. CoordEstGrad is calculated by summing across d finite differences calculation (where d is the dimensionality of the problem). This means that there is a dependency on d embedded within CoordEstGrad itself. Is this dependence on d included in the iteration complexity of the framework? For example, Remark 2 says \"CoordGradEst has a lower approximation error and thus can reduce the iteration complexity by a fact[or] of d\". Does this include the summation within the calculation of CoordGradEst? Similar question for Theorem 4 in the comparison of the complexity of CoordGradEst and that of RandCoordEst: does the O(d/epsilon2) vs O(d2/epsilon2) include the computation of CoordGradEst as well?\n4. Some typos/ minor issues\n - Line 30. rho is undefined until line 108. It may be useful to have rho defined earlier.\n - Line 124. Although clear from context, mu is not defined until line 142.\n - Algorithm 1. What is C\\_0? And what does ``with proper choice of r'' (line 171) mean? r is a calculated value in the algorithm based on d, C\\_0 and sigma.\n -  Algorithm 3. What is C\\_1?\n - Line 244. Typo? Should be \"factor of d\" instead of \"fact of d\".\n5. Because of the similarity to the Neon2 paper, it could be useful to explicitly discuss the paper's contribution beyond what was done in Neon2. For example, which part of the theoretical analysis required different techniques than that used in the Neon2 paper?", "limitations": "This work does not appear to me to have negative social impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n - Paper is well-written and logically organized. The notation is generally clear and easy to follow.\n - The paper addresses an important topic within optimization: escaping saddle points. \n\nWeaknesses:\n - No experimental results.\n - Would like clarification on claim that their method turns first-order NCF methods into zero-order NCF methods without increasing the iteration complexity. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cQ1Hudikrp", "reviewer": "Reviewer_keP3", "summary": "This work proposed zeroth-order negative curvature finding (NSF) algorithms for both deterministic and stochastic nonconvex minimization problem that finds $\\epsilon$-SOSP with the same iteration complexity as the state-of-the-arts for finding $\\epsilon$-FOSP, and improved the query complexity of existing algorithms for finding $\\epsilon$-SOSP. ", "questions": "(1) (Important) Line 5 of Algorithm 4 and Line 4 of Algorithm 7 use $\\|\\nabla f(x_t)\\|\\ge\\frac{\\epsilon}{2}$ while line 4 of Algorithm 5 uses $\\|\\widehat{\\nabla}_{coord}f(x_t)\\|\\ge\\frac{3\\epsilon}{4}$, why do they differ? Due to proposition 1, I think you mean CoordGradEst can verify whether $\\|\\nabla f(x_t)\\|\\ge\\frac{\\epsilon}{2}$ with probability $1-p$, so we can always use CoordGradEst as in line 4 of Algorithm 5, yes? If not, the computation of the full gradient $\\nabla f(x_t)$ in Algorithm 4 and 7 involves $n$ function queries and thus the complexity should involve $n$, which seems to eliminate the advantage of SGD for large $n$. \n\t\n(2) (Important) Your Theorems 3 and 4 have probability at least $1-p$. Could you also guarantee that for Theorems 5 and 6 which only have probability at least 2/3 and 3/4 respectively? (e.g. maybe by repeating algorithms multiple times or changing hyper-parameters) How will you accordingly adjust complexity? This is to guarantee that the complexity comparison is fair. \n\n(3) (important) The checklist said you have listed limitations. Where are they? \n\n(4) In the research question in line 87, should not we focus on query complexity instead of iteration complexity? \n\n(5) Line 130 said \"Central Difference vs. Forward Difference (please refer to 131 Appendix B.1)\", where is such Appendix B.1? \n\n(6) Will the small $\\mu$ in the denominator cause numerical error? If so, How to avoid that?\n\n(7) I did not fully understand your Algorithms 1 and 2 until I read Theorem 1. I think it better to make the big picture more clear at the beginning of Section 3. For example, you might first describe the goal of NCF problem: to find the the negative curvature direction $v$ at point $x_0$ defined as $v^{\\top}\\nabla^2 f(x_0)v\\le ??$ such that when $x$ is a nearly saddle point, going along this direction $v$ will escape saddle point $x$. Is my understanding correct? Also, do your Algorithms 1 and 2 differ from [4] only in that you use $\\mathcal{H}_f(x)v$ instead of $\\nabla f(x+v)-\\nabla f(x)$ in [4]? You might make this more clear in the paper. \n\n(8) In line 168, \"Note that, although the error bound is poor by ... up to $\\mathcal{O}(r^2)$\". This sentence seems incomplete since the whole sentence lies in \"although\". For example, do you mean \"although ..., our algorithm only requires function values while [4] requires both function values and gradient values.\"? Also, it is better to use \"poorer\" than \"poor\".\n\t\n(9) In line 6 of Algorithm 2, you might use $\\sum_{k=1}^m$ and $f_{i_k}$ to differentiate from $j$ in $z_j$.\n\t\n(10) In line 196, $\\lambda_i(M)=-\\frac{1}{\\ell}\\lambda_i\\big[\\nabla^2 f(x_0)\\big]+\\big(1-\\frac{3\\delta}{4\\ell}\\big)\\in [-1,1]$ implies $\\lambda_i\\big[\\nabla^2 f(x_0)\\big]\\in \\big[-\\frac{3\\delta}{4},2\\ell-\\frac{3\\delta}{4}\\big]$, yes?\n\t\t\n(11) The intuition of Algorithm 3 looks unclear to me. For example, does $T_t(M)\\xi$ correspond to $y_t$? How does $x_{t+1}=x_0+y_{t+1}-\\mathcal{M}(y_t)$ in line 215 correspond to line 7 of algorithm 3? Also, why not directly applying Algorithms 1 and 2 to the deterministic case ($n=1$) by replacing $\\mathcal{H}_{f_i}$ with $\\mathcal{H}_f$?  \n\n(12) In Algorithms 4 and 5, the two options can be moved to inside \"if\" since we do not need to compute them when \"else\" holds. \n\n(13) In Proposition 1, does $\\mathcal{O}\\left(\\left(\\frac{128 \\sigma^{2}}{\\epsilon^{2}}+1\\right) \\log \\frac{1}{p}\\right)$ mean the batchsize? Also, the statement \"$\\|\\nabla f(x)\\|\\ge \\epsilon/2$ or $\\|\\nabla f(x)\\|\\le \\epsilon$\" always holds. So I wonder: do you actually mean that we can verify whether $\\|\\nabla f(x)\\|\\ge \\epsilon/2$, and similarly we can verify whether $\\|\\nabla f(x)\\|\\le \\epsilon$? It is better to make it more clear. \n\t\n(14) In all the Theorems, do the query complexities mean the number of queries for $f(x)$, or for $f_i(x)$? \n\t\n(15) Line 3 of Algorithm 7 can be moved into \"if $\\|\\nabla f(x_t)\\|\\ge \\frac{\\epsilon}{2}$\" since we do not need to compute ZO-SCSG when \"else\" holds. Also, I think it will be more concise if you remove \"for $j=1,...,T$ do\" in Algorithm 6 since we only need to run it for 1 epoch. \n \t\n(16) You might briefly introduce what is SCSG and SPIDER at the beginning of Sections 4.2 and 4.3. For example, you might say they are variance reduction techniques for non-convex finite-sum problems, and SPIDER has the near-optimal sample complexity, etc. \n \t\n(17) In Algorithm 8, line 3 can be moved into \"if $w_1\\neq \\bot$\". \n\n(18) What novel analysis techniques are used in your proof?", "limitations": "The checklist said you have listed limitations. I did not find them. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: This work is a novel combination of zero-th order algorithms with NSF algorithms. The related work looks adequate and clear to me. \n\t\nQuality: The submission is a complete work. The claims are well supported by theorems and experiments. I did not find out where limitations of this work are explicitly mentioned. \n\t\nClarity: The introduction is clearly written and well organized. There are many unclear points about algorithms and theorems as shown in my questions. \n\t\nSignificance: The results are important since it demonstrates that the proposed zero-th order algorithms can escape saddle point faster than the previous zero-th order algorithms. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "UvLwbREd76n", "reviewer": "Reviewer_eedN", "summary": "This work proposes a zeroth-order negative curvature framework (NCF) that escapes saddle points and converges to a second-order stationary point (SOSP). This framework can be applied to previous zeroth-order algorithms in order to converge to SOSPs. The theoretical results show that ZO-GD achieves similar convergence results to other deterministic ZO methods (with maybe a slightly better dependence on dimension $d$) when $\\delta = \\mathcal{O}(\\sqrt{\\epsilon})$. The stochastic results also achieve similar convergence results as other stochastic ZO methods except in the case $\\delta = \\mathcal{O}(\\epsilon^{2/3})$.", "questions": "All of my questions are listed in the strengths and weaknesses above.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "To the best of my knowledge, this work seems to be quite novel. I have not seen any zeroth-order NCF methods, especially ones that obtain similar convergence results as its ZO peer methods. This is a big strength, and the literature review is in depth and helpful for the reader.\n\nThe theoretical analysis seems to be sound. I was unable to carefully examine all the proofs in the appendix. The paper seems to be only a theoretical contribution, which is fine but experimental results would be a boost to the overall work to show that this method is feasible and effective in practice (more on this later). \n\nOne major issue with this work is its cohesion: I felt that the work seems a bit thrown together. The theoretical results are lengthy, with many theorems/lemmas/corollarys/propositions not including detailed, descriptive, or informative remarks. The theoretical results should be described in a compact and easily digestable manner. In the current state, the results are quite sprawled in Section 4. The same is true for the algorithms. There are no detailed descriptions of Algorithms 4-8. This is problematic. Finally, there is no Conclusion section or any real end of the work. This makes the work feel like a work in progress.\n\nThe last issue is with the (lack of) experimental results. Many of the other ZO methods obtain similar convergence results and showcase their performance in practice. It would be beneficial to show if your ZO NCF method can perform better than a ZO random perturbation method. In my opinion this is something that is critically lacking in the current work.\n\nMinor Issue:\n1. Is Remark 2 supposed to come after Theorem 4? In the remark, it states that the \"dominant term of the function query complexity in Option I is $\\mathcal{\\tilde{O}(d/\\epsilon^2)}$\". However, while true in Theorem 4, the dominant term seems to be $\\mathcal{\\tilde{O}(d/\\epsilon^2 \\delta^3)}$ in Theorem 3.\n\nOverall, I feel that the development of a ZO-NCF method with rigorous theoretical analysis is a great contribution. However, I believe a lot of work still needs to be done to experimentally backup the convergence claims and make the paper cohesive.\n\nI thank the authors for their submission and am looking forward to their response!\n\n===========================================\nUpdate after author rebuttal:\n\nI had missed the experiments in the appendix, but the authors moved a single experiment into the main section (Section 5). Other experiments remain in the appendix. The authors also did a nice job in cleaning up the presentation of the work. For this, I have bumped up my overall score from a 5 to a 7 and presentation from a 2 to a 3. Great job!\n\n**[R1]** Emmanouil-Vasileios Vlatakis-Gkaragkounis, Lampros Flokas, and Georgios Piliouras. Efficiently avoiding saddle points with zero order methods: No gradients required. Advances in Neural Information Processing Systems, 32, 2019.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept