Faster Gradient-Free Methods for Escaping Saddle Points
Authors: Hualin Zhang
Bin Gu
Venue: ICLR 2023 notable top 25% (2023)

Abstract: Escaping from saddle points has become an important research topic in non-convex optimization. In this paper, we study the case when calculations of explicit gradients are expensive or even infeasible, and only function values are accessible. 
Currently, there have  two types of gradient-free (zeroth-order) methods based on  random perturbation and negative curvature finding  proposed to escape saddle points  efficiently and converge to an $\epsilon$-approximate second-order stationary point. 
Nesterov's accelerated gradient descent (AGD) method can escape saddle points faster than gradient descent (GD) which have been verified in first-order algorithms. However, whether  AGD could accelerate the gradient-free methods is still unstudied. To  unfold this mystery, in this paper, we propose two accelerated  variants for the two types of gradient-free methods of escaping saddle points. We show that our algorithms can find an $\epsilon$-approximate second-order stationary point with $\tilde{\mathcal{O}}(1/\epsilon^{1.75})$ iteration complexity and $\tilde{\mathcal{O}}(d/\epsilon^{1.75})$ oracle complexity, where $d$ is the problem dimension. Thus, our methods achieve a comparable convergence rate to their first-order counterparts and have fewer oracle complexity compared to prior derivative-free methods for finding second-order stationary points.

Published as a conference paper at ICLR 2023
FASTER GRADIENT-FREE METHODS FOR ESCAPING SADDLE POINTS
Hualin Zhang' Bin Gu
NNajjing University of Information Science & Technology MMBZAA (zhanghualing) 1n98, jsgubin) ema semail... com
ABSTRACT
Escaping from saddle points has become important research topic in non- convex optimization. In this paper, we study the case when calculations of explicit gradients are expensive even infeasible, and only function values accessi- ble. Currently, there have two types of gradient-free (zeroth-order) methods based random perturbation and negative curvature finding proposed escape sad- dle points efficiently and converge to an e-approximate second-order stationary point. Nesterov's s accelerated gradient descent (AGD) method can escape saddle points faster than gradient descent (GD) which have been verified in first-order algorithms. However, whether AGD could accelerate the gradient-free free methods still unstudied. To unfold this mystery, in this paper, we propose two accelerated variants for the two types of gradient-free methods of escaping saddle points. We show that our algorithms can find an e-approximate second-order stationary point with (1//E177) iteration complexity and (dde oracle complexity, where d is the problem dimension. Thus, our methods achieve a comparable convergence rate to their first-order counterparts and have smaller oracle complexity compared to prior derivative-free methods for finding second-order stationary points.
INTRODUCTION
Non-convex optimization has received increasing attention in recent years because lots of modern machine learning (ML) and deep learning (DL) tasks can be formulated optimizing models with non-convex loss functions. In this paper, we consider non-convex optimization with the following general form:
min f(x), xER
where fxx is differentiable and has Lipschitz continuous gradient and Hessian.
In this paper, focus situations when first-order information (gradient) is not always directly cessible. Many machine learning and deep learning applications often encounter settings where the calculation of explicit gradients expensive even infeasible, such as black-box adversarial attack on deep neural networks (Papernot et al., 2017; Madry et al., 2018; Chen et al., 2017; Bhagoji et al., 2018; Tu et al., 2019), policy search in reinforcement learning (Salimans et al., 2017: Choromanski et al., 2018; Jing et al., 2021), I), hyper-parameter optimization (Bergstra & Bengio, 2012). There- fore, zeroth-order optimization, which utilizes only the zeroth-order information (function value) to optimize the non-convex problem Eq. (1), has gained increasing attention in machine learning.
In general, the goal of non-convex optimization problem Eq. (1) is to find an e-approximate first- order stationary point (FOSP, see Definition 3), since finding the global minimum is -arhar.. Gra- dient descent is proven to be an optimal first-order algorithm for finding an c-approximate FOSP of non-convex problem Eq. (1) under the gradient Lipschitz assumption (Carmon et al., 2020; 2021), which needs gradient query complexity of (+)). However, for non-convex functions, FOSPs can be local minima, global minima and saddle points. The ubiquity of saddle points makes high- dimensional non-convex optimization problems extremely difficult and will lead to highly subopti- mal solutions (Jain et al., 2017; Sun al., 2018). Therefore, many recent research works have fo- cused on escaping saddle points and studying propertics of converging to an e-approximate second- order stationary point (SOSP, see Definition 4) using first-order methods.

---

Published as a conference paper at ICLR 2023
A recent line of work showed that first-order methods can efficiently escape saddle points and con- verge to SOSPs. Specifically, Jin et al. (2017) proposed the perturbed gradient descent (PGD) al- gorithm by adding uniform random perturbation into the standard gradient descent algorithm that find an c-approximate SOSP in Oloog* d/c²) gradient queries. Under the zeroth-order setting, Jin et al. (2018a) proposed a zeroth-order perturbed stochastic gradient descent (ZPSGD) method, which studied the power of Gaussian smoothing and stochastic perturbed gradient for finding lo- cal minima. The role of Gaussian smoothing is to reduce zeroth-order optimization to a stochas- tic first-order optimization of Gaussian smoothed function of problem Eq. (1). They proved their method can find an e-approximate SOSP with function query complexity of Ô (d2 /e). Vlatakis-Gkaragkkon
et al. (2019) proposed the perturbed approximate gradient descent (PAGD) method using the forward difference of the coordinate-wis. gradient estimators, which finds an c- approximate SOSP in Ô (dlog* d/c²) function queries. Recently. Lucchi et al. (2021) proposed a random search power iteration (RSPI) method, which alternatively runs the random search step and zeroth-order power iteration step, and can find an (c, j-aprrxximtt SOSP ([) S ( (x)) > -22/3) in Od log d function queries. Zhang et al. (2022) proposed a zeroth- order gradient descent method with zeroth-order negative curvature finding that can find an (e, 5), approximate SOSP (x)]l S c, Amia (V= f(x)) 2 -5) in O + dlog function queries.
g3.3
Table 1: Comparison of different zeroth-order methods for finding e-approximate second-order sta-
tionary points.
Algorithm
Reference
Main Technique
Function Queries
ZPSGD
Jin et al. (2018a)
Random perturbation
PAGD
Gaaaako-Gs et al. (2019)
Random perturbation
dlog
RSPI
Lucchi et al. (2021)
Negative curvature finding
dllog
ZO-GD-NCF
Zhang et al. (2022)
Negative curvature finding
0
dlog d 63.6
Algorithm 1
Theorem
Random perturbation
ding" d c7/4
Algorithm 3
Theorem
Negative curvature finding
0
d dlog e7/4
guarantees -apprroxiat SOSPs; ** guarantees (c, 6) appprxximtte SOSPs.
Although gradient descent has achieved optimal convergence rate for finding FOSPs under gradi- ent Lipschitz assumption, potential improvements are achievable under additional Hessian Lipschitz assumption (Carmon al., 2021). Nesterov's AGD combined with some special mechanisms, has been proved to be able to find e-approximate FOSPs with less query complexity. Carmon et al. (2017) proposed variant of Nesterov's AGD with "convex until guilty" mechanism, which can find an e-approximate FOSP with gradient query complexity O ( log 2. Recently, Li & Lin (2022) proposed a restarted accelerated gradient descent method that can find an e-approximate FOSP in gradient query complexity O( (( which adds a restart mechanism to Nesterov's AGD,
On finding SOSPs, Nesterov's AGD also proved be more efficient than GD. Jin et al. (2018b) studied a variant of Nesterov's AGD named perturbed AGD, and proved that it can find an c- approximate SOSP in Ölog" d/e7/4) gradient queries. Their method added two algorithmic fea- tures to Nesterov's AGD: random perturbation and negative curvature exploitation, monotonic decrease of the Hamiltonian function (see Eq. (4)). Allen-Zhu & Li (2018) proposed a first-order negative curvature finding framework named Neon2 that can find the most negative curvature direction efficiently. Combining Neon2 with CDHS method of Carmon et al. (2018) can find an e-approximate SOSPs in Óllo Óllog//e7/4) 7/4) gradient queries, which improved the complexity of perturbed AGD method by a factor of poly(log d) due to the use of negative curvature finding subroutine. Recently, Zhang & Li (2021) proposed single-loop algorithm that also achieves the same function query complexity, which replaced the random perturbation step in perturbed AGD with accelerated negative eurvature finding.
ensure the
Given the advantages of Nesterov's AGD in finding SOSPs in first-order optimization, is then natural design AGD based zeroth-order methods for finding SOSPs with smaller function query complexity. To the best of our knowledge, it is still vacancy in zeroth-order optimization.
Contributions The main contributions of this paper are summarized as follows,
2

---

Published as a conference paper at ICLR 2023
We study the complexity of two AGD based zeroth-order methods for finding approximate SOSPs. We first study a zeroth-order version the perturbed AGD method (Algorithm 1) using the central finite difference version of the coordinate-wis wise gradient estimator, which can be proved to have a lower approximation error compared to its for- ward counterpart. The total function query complexity of Algorithm 1 for finding approximate SOSP log d/e+).
Due to the efficiency of the negative curvature finding for finding the most negative cur- vature direction near saddle, we further study zeroth-order version of the perturbed AGD with accelerated negative curvature finding subroutine (Algorithm 3), which uses the finite difference of the two coordinate- wise gradient estimators to approximate the Hessian- vector product. We show that Algorithm 3 can further improve the function query complex- ity of Algorithm by a factor of poly(log d).
Finally, conduct several empirical experiments to verify the efficiency and effectiveness of our methods escaping saddle points.
PRELIMINARIES
2.1 NOTATIONS
Throughout this paper, we use bold uppercase letters A, B to denote matrices and bold lowercase letters y denote vectors. We use || denote the Euclidean of a and the spectral norm of matrix. We use (x(r) to denote the &g ball with radius r centered at point x. We use (-))
to hide absolute constants and log factors.
2.2 DEFINITIONS
Definition 1. For a differentiable noncontxx F: + R. f L-Lisschitz smooth if Vx.y E R -f(y) f||x yll.
Definition 2. For a twice differentiable voncovexx f RRd R. f p-Hessian Lipschitz if
Yx.y ER', [ , v f(y)l I p||x~ yll-
Definition 3. For a differentiable function f. we say x is an e-approximate first-order stationary point if | [x)] S.
Definition For a twice differentiable function f. we say x is an c-approximate second-order stationary point if
[V[(x)] S. and Amin (Vin)(((())) -vpE
2.3 ZEROTHI-ORDER GRADIENT ESTIMATOR
In this subsection, we introduce central difference coordinate-ve wise gradient estimator, which is widely studied in literature zeroth-order optimization (Ji et al., 2019; Iatakis-Gkaragkouni, et al., 2019; Lucchi et al., 2021),
d f(x + ue,) - [(xx - we;)
(x()) = Σ
Ci
(2)
2/1
where e; is the i-th standard basis vector with 1 its i-th coordinate and 0 otherwise. When analyzing the approximation eтror of the above gradient estimator, previous work only exploited the smoothness property of the gradient of f. not the property of Hessian Lipschitz (which is a basic assumption for analyzing the second-order convergence properties). To fill this gap, we establish the following lemma.
Lemma 1. For a twice differentiable function f: .ddd - R. assume that f is p-Hessiaa Lipschitz. then for any given smoothing parameter μ and any Rd,, we have
1
[( - 22 ddd ''d
Note that, under the Hessian Lipschitz assumption, the central difference has a lower approximation emorr than that of (ldd)p) error under the f-smooth assumption (Ji et al., 2019).
3

---

Published as a conference paper at ICLR 2023
2.4 SIROTH-ORDEL HESSIAN- VECTOR PRODUCT ESTIMATOR
In this subsection, we show how to approximate the Hessian- vectorr product under the setting that we only have access to the zeroth-order information. By the Hessian Lipschitz property, easy to check that the Hessian-vector product fx) can be approximated by the difference of two gradients Vx(x + v) - fx() with approximation error up to ([]v]] for some with small magnitude. On the other hand, by Lemma I, V + v), fx(x) can be approximated by the central difference coordinate- zeroth-order Hessian-vectus product estimator follows, which was previously studied in (Ye et al., 2018; Lucchi et al., 2021; Zhang et al., 2022):
gradient estimator with high accuracy. Then we define the following
Hy = Vf(x fx(xx
(3)
f(x+ V no;)) fxx + mo))
C; Σ f(x uo;;) f(xx me;) 24
Ci
2
Above, the notation H. (z) can be seen as the Hessian matrix of f at point with small perturbations and we don't t need to know the explicit expression since we only need to study the approximation error of it, which is established in Lemma 2.
Lemma (Zhang et al. (2022)). For a twice differentiable function f R assume that is p-Hlessian Lipschitz, then for any smoothing parameter and x E IRd, we have
|i
vdp²
11Hy(x)v f(x(vv sp p
2
3
2.5 HAMILTONIAN
The following function, which takes the form of Hamiltonian, was proposed by Jin et (2018b) to tackle the problem of monotonic decrease of the function value for the momentum-based algorithms in the nonconvex setting,
E, f(x))
21 llvel?
where V X, x,-1 is the momentum.
3 ALGORITHM DESCRIPTION
In this section, propose novel Nesterov's accelerated method based algorithms that can escape saddle points and converge to an e-approximate SOSP using only zeroth-order oracles.
3.1 ZEROTH-ORDER PERTURBED ACCELERATED GRADIENT DESCENT
In this subsection, we introduce the zeroth-order perturbed accelerated gradient descent method in Algorithm 1. The algorithms consist three parts: the random perturbation steps, the accelcrated gradient descent steps and the negative curvature exploitation steps. The random perturbation step called when the gradient is small and no perturbation is added over the past T iterations. Let ype* and set the parameters of Algorithm follows,
g²
0 = 4/R
7 1)
46
T = ViXc,
r = 17c -3
(5)
4p
where e constant and max(1, log / with f(xo) f(x*) < 00.
Since we only have access to the zeroth-order information, we can verify if a point x is an e- approximate FOSP by using the coordinate- gradient estimator based the following fact:
4

---

Published as a conference paper at ICLR 2023
Algorithm Zeroth Order Perturbed Accelerated
Gradient Descent
1: Vo <- 0, ppeturb f- 0
Algorithm Negative Curvature Exploitation
2: for 0, I.... do
(x,, Vt, 8) (Jin al., 2018b)
3: if [V](( _ 3. and (perturb
1: Vvll Il 2 s then
then
4:
Xt t X + Se, &e
Unif (Bo(r)),
2:
X++1 f X₃
3: else
Epeaturb
f
4:
8 = v v
5:
Yr + X + (1 - -8)ve
5:
X++1 + arg (x f(x)
6:
Xx+1 + fr)))
Return (x++1,
7:
Vi+1 f- X Xx
8:
Eq. (6) holds then
9:
(Xt+1, Vi+1) NCE(X;, Vt.s)
Proposition Assume that f is p-Hessian Lipschitz, with choice of the smoothing parameter p in Eq. (2) such that I V 2pv2 we can conclude that if [|V f(x)ll < 3e then we have [ S
3e
if f 3. then we have [[]((=)
The proof of this proposition directly follows from Lemma 1. The random perturbation is uniformly randomly selected from the f2-ball with radius r. The second part of the Algorithm is the Nes- terov's accelerated gradient descent steps with its gradients estimated by Eq. (2).
The negative curvature exploitation step is called when the following condition holds:
f(xx) S f(y.) + A f(y:),, - -y.) ? -1l. x;11
If this condition hold, then the function have an approximate large negative curvature between X and ys. In this case, the accelerated gradient step may decrease the function value the Hamil- tonian. Then we call the negative curvature exploitation step to further decrease the Hamiltonian. Specifically, when Eq. (6) doesn't 't hold, we have the following lemma:
Lemma 3. Assume that f() is t-smooth, p-Hessian Lipschitz and set the learning rate 1 S 1 (2m7,, 4)- Then, for each iteration where Eq. (6) does not holds, have:
37
0
pd
E E.
1v.l [VV
2n
48
On the other hand, when Eq. (6) holds, i.e., negative curvature direction observed, then we have the following lemma:
Lemma 4. Assume that f(-) t-smooth and p-Hessian Lipschilz. Then, for each iteration where Eq. (6) holds, we have:
E S min 82
pd
ps
2n
9-
Remark 1. The results in Lemma 3 and 4 are similar to the ones in Jin et al. (2018b) while with ad- ditional system ervor terms induced by the smoothing parameter μ. Lemma 3 and 4 together ensure the monotonic decrease of the Hamiltonian in each iteration long as the smoothing parameter І is sufficient small.
Then we set / = Vixc = @(VK) and denote & == -x>3>>>>- = = Based on Lemma 3 and Lemma 4, we further prove that when the current approximate gradient is large, 32
i.e., [xx))l 1 (or equivalently, [Vx)( 5. according Lemma 1). We have the follow-
ing average decrease lemma:
Lemma 5 (Large gradient). f
3< with μ S O((1 1/2 in Line 3 of Algorithm 20/2)
4
for all E [0, FT, then by running Algorithm I with < Ô ((7))) in Line 6 and μ S Ō (1))) in
3/6
Line 8, we have F.g En -8.

---

Published as a conference paper at ICLR 2023
On the other hand, when the current approximate gradient is small and perturbation is added over the past T iterations, then we add uniform random perturbation in (r(r). If there exist a large negative curvature direction of the current point, have
Lemma 6 (Negative curvature). Suppose [X)(( < ( thus [VI((+)]I S c),
Amin (V= S -V and no perturbation is added iterations [t T,t). t). Then by running Algorithm 1, we have Egg - Egg S -8 with probability at least 2
Utilizing the above lemmas, we finally get the following main result.
Theorem 1. Assume that [() is t-smooth and p-Hessian Lipschitz. For any > 0, S E (xx0)
I" S A, if we set the hyperparameters as in Eq. (5) and choose == ( in Line 3 and 8, = O a.rx) in Line 6 of Algorithm 1, respectively, then with probability at least 8, one of the iterates of X₁ will be an e-approximate SOSP. The total number of iterations is no more than
A 2//22 2/44 log () and the total number of function queries (oracle complexity) is no more
O
5/4
than
( (
(dSy 2/4
d ped
o
log
Proof outline. We first prove two monotonical descent lemmas (Lemma 3 and Lemma 4) of the Hamiltonian each iteration and an improve or localize property in Appendix B. Next, in Appendix C, we prove that Hamiltonian will decrease by & in I iterations in both large gradient and negative curvature scenarios.
Remark 2. Note that, Theorem only ensures that with high probability, one of the iterates will be an c-approximate SOSP. It is then natural to add a termination condition to make the algorithm more practical: Once the pre-condition of random perturbation step is reached, record the current iterate point Xtg and the current function value of the Hamiltonian Eng before adding the random perturbation. If the decrease of the Hamiltonian is less than & after T iterations, then, with high probability Xtg is an c-approximate SOSP according to Lemma 6.
3.2 ZEROTH-ORDER PERTURBED ACCELERATED GRADIENT DESCENT WITH ACCELERATED NEGATIVE CURVATURE FINDING
In this subsection, we introduce how to utilize the negative curvature finding to accelerate escaping saddle points. The main task of the negative curvature finding is to find the approximate most negative eigenvector direction near a saddle point. Then adding a perturbation this direction will obtain a more efficient decrease of the function value.
Classical methods for computing the most negative eigenvector direction like the power method and Lanczos method require the computations of the Hessian- vector products. Since we have only ac- cess to the zeroth-order information, an efficient way to approximate the Hessian-vector product to utilize the zeroth-order desssian-vettor product estimator in Eq. (3). The accelerated negative cur- vature finding subroutine is self-contained in Line 11-13 of Algorithm when Ç / O. The following lemma states that the accelerated negative curvature finding using zeroth-order Hessian-vector vector prod- uct estimator can find a negative curvature direction in almost the same iteration complexity as the Lanczos method.
Lemma 7. Suppose /I (x,))l
<
4 Amin 2 f(x))) S -VpE and no perturbation is added in do 1, let K ype and set the parameters as follows,
3c
iterations [t T', Itt For any
1
Ø²
2
" 48
0
A
7
11
4p
evd
g' = 32 K log
π
(7)
No /
32
pd
Then by running Algorithm 3 for T' iterations after adding the random perturbation in Line 5, with probability at least 5p. have êT T f(x, < yor

---

Published as a conference paper at ICLR 2023
Algorithm 3 Zeroth-Order Perturbed Accelerated Gradient Descent with Accelerated Negative Cur- vature Finding
1: Pperturb f- --9 1,,y0 Xo, x +- X0, 0
2: for = 0.l...., do
3:
if [V(((x)) || 1 3e and t Epenurb T' then
4:
5:
X = x Et ~ Unif((Bo(r')
6:
Yi = xz,5 V fxx), Eperturb t t
7:
if'
perturb g - and :perturb
g' then
8:
x
9:
X₁ t arg min (E /.x+ [F,) f(x)
10:
Yr = x,, =
11:
X,+1 = =Y- -n(Vf(y)) ()
Ve+1 Xt+1 Xt
13:
Ye+1 = X++1 + (1 0)v
14:
if (penuurd # g and Epentur < 9' then
15:
(y++1; (x, x) + r', yc-1 1 X==1-8
[|x-11 xI Xx]+1-
16:
else f(x++1) & f(y++1) + (((()++)), X Yet1) - X++1|l then (X++1, Vi+1) - NCE( V)+1,8)
18:
Yo+1 X++1 + (1 0)v-1
Then moving along the direction of è, the function value of f will make further decrease according to the following lemma:
Lemma 8 (Zhang & (2021), Lemma 6). Suppose the function f Rd R is E-smooth and p- Hessian Lipschitz. Then for any point E TRd, if there exist unit vector é satisfying @V2 f(x)) f < 2 where (x(x)) is the directional
De 4 then we have f (xo Xo
fxxx)
(66) f(xo) 334
(x(
derivative along the direction é.
Remark 3. In the first-order setting, f2(xx) (V)())) E). However, in the zeroth-order setting,
the directional derivative cannot be computed directly. To tackle this problem, one can simply compare the function value of two opposite directions, i.c., Line 9 of Algorithm 3.
Theorem 2. Assume that f()) is E-smooth and p-Hessian Lipschitz. For any > 0, f(x))
f S As, if we set the hyperparameters as in Eq. (7) with ōn 3842, V and choose fu
Ō 1/2 in Line 3 and 16. μ Ō (17z)) in Line 11 of Algorithm Then with probability at least 1-8 8, one of the iterates of xt in Algorithm 3 will be c-approximate SOSP. The total number and the total number of function queries log( (V/2)))
of iterations is no more than A1 22/4
274
(oracle complexity) no more than
dD 12 67/1
wdss) 862
log(
Remark 4. Similar to Algorithm 1, we can also add an termination condition for Algorithm 3: Once the pre- pre-condition random perturbation step is reached, record the current iterate point Xto and the current function value fxxt,) before adding the random perturbation. If the decrease of the function is less than 384 o after J' iterations, then, with high probability Xt,, is an e-approximate SOSP according Lemma 8.
Remark (Proof outline). The main difference between Algorithm I and Algorithm 3 is the way in which random perturbations are added. Specifically, in Algorithm 1, we add uniform random perturbation nearby a first-order stationary point. If it is saddle point, then by running the zeroth- order accelerated gradient descent for T = VFXc = Õ(VR) steps, the value of Hamiltonian
function will decrease by & = == Ex = 6(v (.) In Algorithm 3, the perturbation is

---

Published as a conference paper at ICLR 2023
added along approximate negative curvature direction, which is obtained by running I' /2 bo/pe) steps of zeroth-order accelerated negative curvature finding (Line 11-13). Then moving along the negative curvature direction, the value of Hamiltonian function will decrease by 384
(no more log term as in 6). Thus, the total function query complexity induced by Algorithm 3 is O(d Vollog( EVd. 60 ype
dd 1210 574
log( (VAA,) ))
=
662
NUMERICAL EXPERIMENTS
In this section, we conduct several numerical experiments to verify the effectiveness of the proposed methods for escaping saddle points and the efficiency compared with the existing methods. Spe- cially, we run zeroth-order perturbed accelerated gradient descent (Algorithm 1) and zeroth-order perturbed accelerated gradient descent with accelerated negative curvature finding (Algorithm 3) against the perturbed approximate gradient descent (PAGD) and the random search power iteration (RSPI) method. All experiments are performed on a computer with a six-core Intel Core i5-10500 CPU.
4.1
CUBIC REGULARIZATION PROBLEM
0-20
d+120
04220
5=1000
86-
60
8.6
0.3
-04
-03
-01
-42-
-0.2
-03
-02
-42
P620
Pernbee
-03
-42
-03
-84
Permibs
-04
-1.4
-04
-42
-05
-12
-05
-26
-05
-22
-03
-47
-07
-07
d3
14
25
Fanction Query
on Query
Function Qarry
Fundion Query
-02
-02-
-02-
-03
-03
-03
-03
-05
-05
-07
176
-07
Herd lo1s
Derelions
182
Becaiions
Figure 1: Performance of different algorithms to minimize the cubic regularization problem with growing dimensions. Confidence intervals show mini-max intervals over ten runs
We first consider the cubic regularization problem (Liu et al., 2018), which is defined as:
min f(x) XER
x Ax
|
Above, A randomly generated diagonal matrix with only one diagonal entry -1 and the rest diagonal entries are uniformly distributed between [1, 2]. So that with increase of the dimension, the negative curvature directions that can escape from the saddle point will be more difficult to explore. In this experiment, we set 10- 2 To test the ability of different algorithms to escape from saddle points, we initialize all algorithms at a strict saddle point Xa (0.
In this experiment, we run Algorithm 1, 3, PAGD the above cubic regularization problem from strict saddle point. For Algorithm and 3, the parameter settings basically follow Eq. (5) and Eq. 0.001 and the perturbation radius and r' are set to 0.001. The
(7). Specifically, Lipschitz constants and p are selected based on a coarse grid search of the region {0.1, 1, 10, 100) 10.1, 10, 100}. Since all algorithms have certain randomness, repeatedly run each algorithm multiple times and report the averaged function value versus the averaged number of function queries and the number of iterations in Figure 2.
choose
The results in Fig. illustrate that Algorithm 1, 3 can escape saddle points using less iterations than PAGD and converge faster than PAGD. On the other hand, in all dimensions, the number of
8

---

Published as a conference paper at ICLR 2023
iterations for escaping saddle points almost the same. This verifies the result in Lemma 6 and that the number of iterations of Algorithm 1, are only log dependent on the dimension
4.2 QUARTIC FUNCTION
21.0
20,01.10
20) tndee AOL
21 02 SJ
15
2=20
(b) d=100
(c) d=200
Figure 2: Performance of different algorithms to minimize the quartic function with growing dimen- sions. Confidence intervals show mini-max intervals over ten runs.
Then we consider the following quartic function (Lucchi et al., 2021),
d
d
d
f(11, T2 R2..,,,,.
Σ
2
Σ
+
2
(9)
1=1
i=1
which has strict saddle point at Xo (O...., 0)T and two global minima (I...., 1)T and (-1,...,-D))
In this experiment, Search Power Iteration (RSPI) and ZO-GD-NCF on the above quartic function staring from its saddle point. Especially, also run an acceleration version of RSPI, which replaces the finite difference gradient estimator in RSPI by the SPSA estimator (Spall et al., 1992). The parameter settings of PAGD are taken from Katakis-Gkaragken are taken from the appendix of Lucchi et al. (2021). For Algorithm and 3, the parameter settings basically follow Eq. (5) and Eq. (7). Specifically, we choose 10-1 and the perturbation radius and r' are set to 0.01. The Lipschitz constants and are selected based on coarse grid search of the region (10, 20, 100, 150, 200} x {0.1, 1, 10). Since algorithms have certain randomness, repeatedly run each algorithm multiple times and report the averaged function value versus the averaged number of function queries Figure 2.
Algorithm 1, 3. perturbed approximate gradient descent (PAGD), Random
al. (2019) and the parameters of RSPI
The results in Fig.2 illustrate that both Algorithms and 3 can efficiently escape saddle points and converge quickly to the global minimum. Note that, for all dimensions, Algorithms 1 and escape saddle points with fewer function queries than PAGD. This verifies the theoretical result that algorithms and 3 take ((VK) iterations for escaping saddle points when the initial point is saddle point, while PAGD takes @(k) iterations. For high dimensional problems, the computational cost of RSPI for escaping saddle points is expensive. In contrast, RSPI with SPSA estimator much more efficient.
CONCLUSION
In this paper, study the complexity of two zeroth-order AGD based algorithms for escaping saddle points and converging to SOSPs. The first method is a zeroth-order version of the perturbed AGD which the central finite difference version of the coordinate-wise gradient estimator. The second method extracts accelerated negative curvature findings by using the finite difference of two coordinate- wise gradient estimators. Both methods improve the function query complexity of prior zeroth-order methods for converging to SOSPs.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENT
The authors thank four anonymous reviewers for their helpful comments and suggestions. Bin Gu was partially supported by the National Natural Science Foundation China under Grant 62076138.
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. Advances in Neural Information Processing Systems, 31, 2018.
James Bergstra and Yoshua Bengio. Random search for hyper-parameee optimization. Journal of machine learning research, 13(2), 2012.
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), pp. 154-169, 2018.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. "convex until proven guilty": Dimension-fie acceleration of gradient descent non-convex functions. In International con- ference on machine learning, pp. 654-663. PMLR, 2017.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal on Optimization,, 28(2):155111772, 2018.
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71-120,, 2020.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points ii: first-order methods. Mathematical Programming, 185(1):315-355, 2021.
Pin-Yo Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop Artificial Intelligence and Security, pp. 15-26, 2017.
Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. In International Conference on Machine Learning, pp. 970-977007 978. PMLR, 2018.
Prateek Jain, Chi Jin, Sham Kakade, and Praneeth Netrapalli. Global convergence of non-convex gradient descent for computing matrix squareroot. In Artificial Intelligence and Statistics, pp- 479-488. PMLR, 2017.
Kaiyi Ji, Zhe Wang, Zhou, and Yingbin Liang. Improved zeroth-order variance reduced algo- rithms and analysis for nonconvex optimization. In International conference on machine learning, pp. 3100-3109. PMLR, 2019.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How escape saddle points efficiently. In International Conference on Machine Learning, pp. 1724-1732. PMLR, 2017.
Chi Jin, Lydia Liu, Rong Ge, and Michael Jordan. On the local minima of the empirical risk. Advances in Neural Information Processing Systems, 31, 2018a.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference On Learning Theory, pp. 1042-1085. PMLR, 2018b.
Gangshan Jing, He Bai, Jemin George, Aranya Chakrabortty, and Piyush K Sharma. Asynchronous distributed reinforcement learning for lqr control via zeroth-order block coordinate descent. arXiv preprint arXiv:2 12411 2021.
10

---

Published as a conference paper at ICLR 2023
Huan Li and Zhouchen Lin. Restarted nonconvex accelerated gradient descent: No more polyloga- rithmic factor in the o(e complexity. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 12901-12916. PMLR, 17-23 Jul 2022.
Mingrui Liu, Zhe Li, Xiaoyu Wang, Jinfeng Yi, and Tianbao Yang. Adaptive negative curvature de- scent with applications in non-convex optimization. Advances in Neural Information Processing Systems, 31, 2018.
Aurelien Lucchi, Antonio Orvieto, and Adamos Solomou. On the second-order convergence prop- erties of random search methods. Advances in Neural Information Processing Systems, 34, 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018
Nicolas Papernot, Patrick McDaniel, lan Goodfellow, Somesh Jha, 7. Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, pp. 506-519, 2017.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as scalable alternative reinforcement learning. arXiv preprint arXiv:1703.0338 2017.
James C Spall al. Multivariate stochastic approximation using a simultaneous perturbation gradi- ent approximation. JEEE transactions on automatic control, 37(3):332-344 1992.
Ju Sun, Qing Qu, and John Wright. A geometric analysis of phase retrieval. Foundations of Com- 2018.
putational Mathematics, 18(5):1131-11
Chun-Chen Tu, Paishun Ting, Pin-Yu Chen, Sijia Liu, Huan Zhang, Jinfeng Yi, Cho-Jui Hsieh, and Shin-Ming Cheng. Autozoom: Autoencoder-basse zeroth order optimization method for attack- ing black-box neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 33:742 799, 07 2019.
Vasiillisl Vlatakis- Gkaragkounis, I Lampros Flokas, and Georgios Piliouras. Efficiently avoiding saddle points with zero order methods: No gradients required. Advances in Neural Information Processing Systems, 32, 2019.
Haishan Ye. Zhichao Huang, Cong Fang, Chris Junchi Li, and Tong Zhang. Hessian-aware zeroth- order optimization for black-bor adversarial attack. arXiv preprint arXiv:1812.11377 2018.
Chenyi Zhang and Tongyang Li. Escape saddle points by simple muadient-descent based algorithm. Advances in Neural Information Processing Systems,
2021.
Hualin Zhang, Huan Xiong, and Bin Gu. Zeroth-order negative curvature finding: Escaping saddle points without gradients. arXiv preprint arXiv:2210.01496, 2022.
APPENDIX
A AUXILIARY LEMMAS
Lemma 9 (Nesterov et al. (2018), Lemma 1.2.3 & 1.2.4). If is L-Lipschitz smooth, then for all T. Rd
f Ily x!
If(y) - f(x) - Vf(x) (y- x)| If J is p-Hessian Lipschitz, then for all x, E IRd,
2
VV - fx(x) fxx(x -x)| 2111 - -x1
11

---

Published as a conference paper at ICLR 2023
and
f(y) - ((x))vf(x)(G) - x) - x) x -x)
L lly x|3
Lemma 1. If f is p-Hessian Lipschitz, then for any given smoothing parameter μ. and any at E IR. if f is t-Lipschitz smooth, we have
1
-
S 36 dp
(10)
Proof.
d
fxx + ue;) - -(x - pes) Vf(z))
Vf(x)= V coord f()
Σ
=
2p
1
Σ (f( ue:) - f(x - 22 2
2/
Since f is p-Hessian Lipschitz, for E [d]. we have
f(x + pes) - -e: -2V.)))
f(x + pe:) - f(x) -VV,(()) - 1¹² [z)(
f(x AV.)) - 12 2
(2.((z)
2
< f(x uei) - f(x) vz)(()) 2
1²
(x))
+
f(x f(x pe,) pei) f(x) +V.f(z)
2 (if(()
22 6
- u
where due to Lemma 9.
V (xx) v fx)
d
Σ (f(x + mes) s(x mei) - 2/
2/
1
Σ (f(x ue:) - f(x pes) - ((x))
2p
1=1
1
ppu 2
vdpp?
5
/d
24
3
6
Lemma 10 (Jin al. (2018b), Lemma & 25). Define
A
0)
(N1 +
Let [1, denote the two eigenvalues of A, then can be rewritten as A for any E N:
(0 I)A' = (1 A-A
1-1
A' 1))
(w) 1) 1) - (1
0) Σ A
0
1-(1 (1
r=0
12

---

Published as a conference paper at ICLR 2023
Lemma 11 (Jin al. (2018b). Lemma 30). Ler 8 E (0, 1041 define
- (2-0 - x)
-(1 - 0)(1 (01--7) =1)
and let x E 1
(2- 03-
8²
Denote (at
-b,)= = (1 0) A then for any t 2 3 + 1, we have
2a 0 1
1
(
a-) 2 2(1 min
}.
b ==0
0 1
T=0
Lemma 12 (Jin al. (2018b); Lemma 32). Let 0 E 10,1/4) define
(2 0)(1 x) -(1 - (1 x1-x)
A
and let x E 11-007
8a + Denote (as
-b:) = (1 0) A', then for any 2 0, we have
maxflack 16el3 S (t+ -) 0)
Lemma 13 (Jin al. (2018b), Lemma 34). Under the same setting as in Lemma 12, for any se- quence c,, any t 2 (2116), we have:
a 50(1/2)
|col Σ lo
[-1
(col + Σ
aa, dle S0(1/VZ)
Ey - ---
T=1
Lemma 14 (Jin et al. (2018b), Lemma 36). Ler f E 1/4), define
(2 0)(1 - x) -(1 (1)-0-11-)) x1
and let x E [-1144, 0), denote (at, -b,) = (1 0) A'. Then any 0 S r I t, we have
2 + t 1]]a++1 - -b-1l-
Me-rlla, - by <
0
Lemma 15 (Jin al. (2018b), Lemma 37). Under the same selting in Lemma 14, let A(x) A
()) then we have
and g(x) = (1 [A(](]]]
1. g(x) is monotonically decreasing function for æ E [-1,02 0)2).
2. For any x E [82/(2 - 8²), 1), we have g(z) S 10/00/222/0/ 82))
Lemma (Jin et al. (2018b), Lemma 38). Under the same setting as in Lemma 14, we have
|0r+1 be+1l 2 la, byl (az, bb,) = A) (1) and
0 (1 |a, - bel z
min!
[
V|ol))*
2
0
Lemma 17 (Zhang & Li (2021), Lemma 21). Consider the sequence with recurrence:
f+2 = (1 + <) 0) - -0){)),
for some 0. Then we have
1 (C 0 11² + C2(2 - 0 11)))
& =
2
where J (22 0)2
4(1-0)
C₁
2-0-1 + (1FK) E1. C2
1-0+H
2p [1+x)p E1-
Eo
24
13

---

Published as a conference paper at ICLR 2023
B PROOF OF HAMILTONIAN LEMMAS IN THE ZEROTH-ORDER SETTING
Lemma 3. Assume that f() is E-smooth and set the learning rate 1 S 22:0 E (2n7, 2) Then, for
each iteration & where Eq. (6) does not hold, we have:
pd
E S Et
|vel
[V +
27
4
48
Proof.
X++1 ty, (
y++1 6x++1 + (1 - 0)(x++1 -xi)
1 By smoothness, with 1) S 18
we have
-y:) - + l
((x+11 sf(y:) + (VS(y)), Xx+1 -
||x++1 - yell
2
672
vf(x:)) =f(y)) ( + |
2
According to the update rule the accelcrated gradient descent, we have
||x+1 - xel2 lly+ f)v)())) - x212
= =Ily= - 22 (vf(y:). - -xx + +
Dividing both sides by 21). have
X1+1
x1l1
lly: x, x1 ( -v.)+ + 111 " f(y)))1
2n
2n7
Then we have
1
f(x++1)
||x-1
-2
21y
<f(y:)
+ llye - -x:11 + +
1
-xi "
- 17 (V)())). 1
&f(x)) + .nî (
2n
=f(y:)
Ily: xz|13 + (V/(y)), x x - - (v)())).....) + 20 + ())))11
2n
As long as the following condition holds:
f(x)) 2 f(y.) + (Vf())), --xxx--- -1)-371 -x
we have
f(x(+1) + 2n
|x++1 - xel12
<f(x)) +
1+
Iy: x:112 - 1eennn(vtin (V(())).((.))) + = (1 f(
2n
Note that
- -VSS(y)) 11 (V/()))))))))
4,().) -V(x)))
and
( v vf(r:)11
=1V + 2 (y))), v5(x)) vS())) -/o))))))///->)))>+>>>>)>>>>>> + -/.)) v
Combine the two equations with the above incquality, we have
1
f(x(+1) + |x,_1 xx
27
14

---

Published as a conference paper at ICLR 2023
(f(x,)
1 17
lyye 1x,12- 71(1-8n)
Vf(y))) + (V)(y)). Vs(y)) vf(x,))
2n
+ 1111 + En)
1V vf(x))112
<f(x))
1 mM
1,y x111? 17 (n) V [ + li ( (111
23 (V V(())))))
1
211
11(1 + En) [Vy() V((x))11
=f(x)) 1 117
1 En Ben
V ff(y))l +m( by
1 En ][ vf(r))1.
Iy: x111² 1
2n
2
2B
2
Take
and 17 S z. we have
f(x++1) + 1
|x++1 x211
2n
5f(x;)) + 1 1+ 177
llye x:12 1 [Vy,) + 37 (1)()))) Vf(y,)
2n
1 + 17?
2n7 Iy: x112 4 [V + p²
<f(x)) +
48
Using the fact that I|y: Xel (1 -0]]|x x11 have
1
[(x++1)
+
-
||x+1 - x2
21
<f(x,) + 1 T/7 (1 0))
- x 1|
" [
+ pdddd
2m
4
48
=f(x)) + - ||x, X4-1
1|2
29
82
17 0)2
l|vel1 - f +
pd
211
21
48
<s(x:) + ||x, Xx- -11 112
0
|v.11
!
[[V[(x)) +
p²du*
4
21
2n
48
Lemma 4. Assume that f(-) is E-smooth and p-Hessian Lipschitz. Then, for each iteration & where Eq. (6) holds, we have:
x² 1 272 ps3
pddp² 9r
E S E. min
2nj
Proof. When ||v/|| 2 then x.-1 Xx, we have
8²
E f(x++1) f(x;) EE,
llvell 3 E,
27
2n
When ||vel| S happens, we have
f(xx) = f(y:) + (VI(y:), xx - yı) 1 yr) -x))
(()G))()) - y.),
where Ge - a(x: - y.). and a E [0, 1]. When the following condition holds:
f(x)) <)(r.) + (fʃ())), x - x y.) - 11xx yell2
=f(y:) + (Vf(y)) -ya)+ + (vf(x)) - vf(y.), -Y:) IIxe -.el?.
we have
2 (x: - -v.) - -o)) ( vf(y)). -vi) - -111x - 2 1111xx-y11
-
15

---

Published as a conference paper at ICLR 2023
[V)(()))
+ +B11x V\/x))
-x.1() - - 11: - yell
2
7 Y-
8
xx y+11 + 1
VV(y.) vs(y:)]1
2
23
7 B
x ytl1? p²du²²
2
1833
Take 8 3 we have
5 [x yr [())()) - y.) - - y2
1
1x:
pdd
97
Note that min ( 8) (xx) -6)} - 0. Without loss of generality, we assume that (Vf(x)). 6) & 0. Since x arg min (x + 6,x, -6 f(x), we have
1 +2 v
f(x++1) - f(x 8) f(x:) + ( (x,)) 0) 1 V & f(x))
where G 6x=x; + a'5 and a' [0, 1|. Since ||c: -lll S 2s and lines up with yr Xx, we have
87 v <6 V2 f((:)6 + V2 ((C) V ((G)111188 S --11818 + 2ps|18112 + dp²
9y
7 s² 2ps 2
97
Finally we get
1 (7782 ps3
p²dpt
S E. 1778² pss pdd
Ett1 [(x++1) S fxx))
9r
97
Lemma 18. the Eq. (6) does not holds, then for all steps in [t, t T), we have:
1T
2m Fr FATT) n du T
Σ
-x,-xx-1l1
0
48
T=1+1
Proof. The proof directly follows from the results of Lemma 3.
C
PROOF OF MAIN RESULTS OF ALGORITHM 1
Recall the parameter settings in Algorithm 4,
0
Vpc
7
r= meX -888
=
48'
4
==
4
3
4p
16 V
where K
Denote
ypc
3
2 -
M = EVK
g - - XC,
c f
-
c-
Lemma 19. After running the NCE with μ S 0 1/2 for one step, we have
E E, < 22.
Proof. According to Lemma 4, with the choice of the smoothing parameter such that S Ö e222
have
x2
pddu
Ex+1 - E, 5 - min
2nj 772² ps
5 - 2 28.
97
16

---

Published as a conference paper at ICLR 2023
Lemma 20. Let 0 be origin point. Denote
o
-
Then the zeroth-order AGD update be rewritten
X++1
A
X1
A
( + +,,,
(II)
Xx
Xn
0
(2 (2-0) f()))
-(1- - (I 11-7 )
where A
I
0
Proof.
X(+1 = (2 0)x, -1-11-0000 00x 2 - 0)x, - (1 0)x
Then have
Xx+1
(2 - (I - -n)
-(1 -1-0)0-~~/1111) ( Xt (x
(v)(0) + +
I
=A²
X1
A r-
(v
X0
Lemma 21. for any T S t, we have ||+|| S R, then for any S have
1. |6+|| S (M + vdpz²
2. ||, 8,-1 ||| s |O(B|xx+ xx-- R x1 x- vdu²)
3. Ei=1 ||6, - - S O EI ||x,~ - Xx--1l1 + tpp dyr²)
Proof. For the first inequality, by using the second inequality of Lemma 9, we have
[Vf(y+) Vf(0) V2 f0) P |y+112= 2 11(2 -))x (1 0)
Using Lemma 1, we have
|| || -( Vf(0) v0,(),, II
<y-)) Vf(0) V |0,,,++ - - (())
<O + Vdpp²).
For the second inequality, we have
o - 0 - - - - ---1)-
Then we have
[Vvf(,)) Vfly, ((0(() - y1--))
/'' (v-f(x+-1 + fly, yr-1)) V² f())))dB( 11ll
<|| 1/' (V2 + 0ly, - 1) 22 (0)))001 ly. -v--rr-ih S م-mspmm mmax(11y--))) [|y--llllllyl111 lly.- U|ly, -y-ill
<O(pR)([1x - X + ||x--1 xy-21l)
Thus.
||,, 8--1|1
17

---

Published as a conference paper at ICLR 2023
< (1/1)))-77/5-----100/)-------111 - v2 -y--1)l
- x, + Xx,-
Then we have
Σ ||, x- x Dddd
16, 5 S O Rt
C.I. LARGE GRADIENT
0² Let S be the subspace with eigenvalues in 72- { and 8 be the complementary subspace.
Lemma 22 (Large momentum large gradient). If l/v 2 Ml or [V]((,)]I 2 2l.M, and at iteration t only AGD is used with smoothing parameter μ S O 2/2 perturbation, we have:
01/9077 C 1/2) and without NCE or
46 Es+1 - Es S g
Proof. When ||vell 2
SvR
and p S (
1/2
1/22),
using Lemma have
t
0 1/ +
dp
2² c
p² ) 22 2 Vovce* 2 p² S -52 l
2² eVVEc=
E+41 Es S
S7(
21
48
Vk 12
E
46
- 0 00 <
g
holds for large enough constant c. Lipschitz assumption, have
When ||vell S M and [x((x,)| 2 2l.11 then by gradient
|Vf(y 2 [f(x))| - IVf - f(x:))) 2 [V)( E(1 0)vlvlll 2 l.M.
Using Lemma 3, with p S 0 - 1/2), we have
E411 E, - - "1V dp
2xc -ddppt I -22 2 2 ppddut
$
-S2
4
48
- é VRC
8
48
-
0
c) s
g
g
holds for large enough constant
Lemma 23. If IPs. Vf(xo)) 2 3. |voll < M. (TPp & 2/ppe.l p
Õ 3/s and for E [0, T /4] only AGD steps are used, then we have
E Eg -8.
Proof.
Define x-1 = Xn
Vo- Without loss of generality, set x
0. Using Lemma 20, we have
X X4-1
= A--1 1-1
(
0
Σ 1-1
t-1
V (() 6
-Vo)
7=0
Denote
(2- n74,)
(]
-(1 () n211)
A,
0
18

---

Published as a conference paper at ICLR 2023
where Ay is the j-th eigenvalue of V² Denote
- (1 03.
Then we have for the j-th eigen-direction
2-1
L-1 -
4
211 = =60"
Σ (v
Σ af?
Σ
+1
()
7=0
where
(1)
Σr=
Di-1-r
6)
1) E
ar
For j E S", using Lemma, , we have
D[-1 0 at
(i)
2 1 (z)) Then rewrite the above equation as
1-1
z =1 Σ
( +601).
(t + 800 +
-
where 866) = 1-1 (1)
= pf 004) 566) qi
For all j E S
1-1 Σ
t-1
[860]
pl 8 $ Σ
p + 880) 1880) 186")
+ Σ
800) 1
p
1
10
Σ
1500 -4th
7=0
T=0
r=0
r=1
Then by Souchy-Swartziie inequality,
t-1
1-1
0| =
Σ
100012 <
Σ
(106))
+ Σ
1860 1)2 22
Σ
1860 2 + Σ
186)
600 12
jES
jES
T=1
jES
JES
r=1
1-1
$
Σ
100
12 2
Σ
(15(0)
1)2
S 22110011=
21
Σ
11+ 81-111
jESc
JES
Assume that E5/1- - Eo 2- -E. By Lemma 18 and choose 1 S <O(( x- )1/0)
- = Ō
3/8
(1))7z))
have ||x, xool S 11 V ||x,- 122 S /
2n/88 - +
g2
np²dus
J. With / S
0
48
O((
0-1- 11/4 ) Ō (d)j1a))) by Lemma 21 we have ||óoll s 0(p By Lemma 18 and
de
Lemma 21, we have
Σ 10 =
x x, 1 < 04p2gr9)
So we have |IPs:0l| S 0(pF2) S O(
By Lemma 11, -ngg) (5)
b,
< 0()) mlx (0, v nnl Ayl, then
Dr ar
Σ l0! (1) 0010 < O())
Σ jES=
max m/>p]] [0
n
jeSe
Since the NCE step is not reached, then we have:
f(xo) 2f(8)) + (tf()o), - vo) =f(yo) + (VS(yo), Xo= yoo) + (((())) Vf(yo), xo))) -xo)
2 |1x0 - yoll2
2
-
-
2 -1 yoll
1
[f(())) vs(r0)1 7 B
25(80) + +VV/(y0). Xo -oo)
2 ||xo yoll2
28
19

---

Published as a conference paper at ICLR 2023
p²dux
2 B
2f(yo) + (Vf(yo), Xo - -yu)
1|x0
yoll?
723
2
p²
=f(o)) + (V Xo - yvo)
711x00
-voll
72y
where the last step is by taking 3 = Then we have
1
pd 727
2 [xo yo) [Sx)(x( - yo) 2
- -111x0 yoll?
where Co =
(1 Φ)yo and @ E [0, 1]. Note that (1 - -0)vo = yo Xa.
have
2 V v 2 72(1 0)2 ?|lvol1 pp
1
pdd
>llvol
18y
where the last inequality uses the fact that 0 S 1/2 Using the Hessian Lipschitz property, we have
(pc)3/1
vpc
[V3 - v2 (xxo)l s pllvoll s pllvoll S SaM-
c
2%
vl
2
Then we have
pd 4rl1vol12
pdd
2 2
/ppl|voll
By
VkC
Since
6 9|1-0] 0j²
(VvE)), we have
dd
Σ
Σ
Σ
+
Vpc
jES
5: 001
j: m0-663
pdd
<o(vpe)llvo)
+
Vp
With S 0 1pad
&vee 22/4 = Ö
5/8 21/4
then we have
|| - =P )
/oeelvool
ddp
s =
Vpc
Then we have
|x||| Pl 2n
min jES
(
|Pp:: (v)(0 +8+ v)Il
T=0
pvdp2
201
17 1
Ps [((]]]]
PP - Pl
6
20 T1E gz
I
which contradicts with ||x; xoll |xx|| S S. So we have
Eg// Eo -8.
Lemma 24. If voll S Al and ( S 20.14,E9 Eo 2 -8,4 3( 3/8
(177))
and for any
t [0, /22 only SGD steps are used. Then Vt [9/4, T/2):
|Ps S ' and v. v.I.V'' f(x)) Pslv: S Vp
20

---

Published as a conference paper at ICLR 2023
Proof. Since // Fsp 2- 8. By Lemma 18 and choose S 50(( x - )1/4
= Ö (d) )
p
we have |2; -xx-xol 5 v E ||x x111 -
2n + 32 dod
48 S s. Define x-1
16
X0 - Vo. Without loss of generality, set xo = 0. Using Lemma 20, we have
1-
(0 + d,
Xx X,-1
A
Σ
Aー
-Vo)
Define A. = (V 42 {0))dd Then we have
V)(x)) (0) + (V2 ((0) + A.)x = $5(0) + (V ((0) + 4, + VS(0)- - VS())
1-1
A A (0) 7/(0) + ((0 0) (-v)
|-1 (I 0) Σ
-
(
(() (I 0) AA-L
+ A.x + - -
0
T=0
If we choose 5 ((55))))) (174
we have
| x1 S p|xx,|? <0(p9)) < O S 5/20
pVap²
[V - [0
5/220
6
By Lemma 11, we have
1-1 1 (1 (1 0)
AA - 0) =(1 0) A) (1)
Denote
(o6)) -b6)) = (1 0) Aj.
By Lemma 12, maxjes {1a 1101),1100)) 160 s (t 1)(1 07'/2, then we have when 2 g/4
26 log }), # S ②g ()))))
IPP (1-12//001 (I 0) D A - ()) v/(0)) 12=
(at - (0)
T=0
JES
p²ddu 4
< 22/400
36
|Ps (') (I A' (-h))
(1 - S 2/440.
jES
Using Lemma 13, for all j S, we have
( (I 0) 1-1 AA ())) )0)) ()
H-1 af 1-
1-1 102 Σ 180) 800
= Ind
Σ
0=0
1=1
Using Lemma 21 and choose S Ö (2//2)
), we have
1-1
A --1 (8) s 2115._1 2 2t
1222-112 ?
IIPs ((0 0)
110 1. 1/p=500 )
400
T=U
Thus we have for any t E 1 T1.
|P&V S c
21

---

Published as a conference paper at ICLR 2023
Using Lemma 20, we have
1-1
A -l-l-r ($/10)
Vz = (1 -1)
Xt X2-1
-(1 ((1 A1) (-vo) - -n111
-1)
Σ
==0
-n -1 11 Σ A 1 (6:
1-1
==0
By Lemma 12, fort 2 g/ /4 g log f). we have
(xx))" 1/2 (1 - A²
A (-v) 1
Σ
11/2200001
= C(t + 1) vvol2
-vo)
jES
2
1
0
3
pfc
3
By Lemma 10, we have
Imdy (1 -1) 1-1
() -Iyd (1 0)
1-1
1
-11[ A
(A)-
---
==U
T=0
=1 (A) -A-11) 0)) |.
By choosing μ Ō(()/)) > then we have
(P) 12 (1 -1) -1) A A (v/10) |
0=
(1) 1A7 1/2 (al - - - (0 + 1/2 (1000)))
JES
<
(t + -1) [) s O
1 vpc
(t + 1) - -)) 2((V) + p²dpu
36 )
Vpc
1
< l 0 <
3 V!
By Lemma 13, for any j E S, we have
I(V2 (0) -1) Σ A t 1-r (0))01
1-1
)011
7=0
1-1
1/2 =/
(ar - a 16, S v + Σ (869 1 -(2,)) D).
7=0
Using Lemma 21 and choose μ S Ō (1/14)) we have
Σ A 1 (0) 11a 11 2t Σ 1|,, 1
1-1
t-1
[|P))
-1)
7=0
7m1
5o(np² & 0 2
0
<
3 /p
1
Thus we have
T.P. S Vp
Lemma 5. 1f
2 3c with μ S <0((12000) 3e 1/2) in Line 3 of Algoritlum I for all E 10, Fl. (((220))))
20//a)
in Line 8, we have then by running Algorithm with μ < 0(57 in Line 6 and μs S Ō 3/2
F.g Fn < -8.
22

---

Published as a conference paper at ICLR 2023
3e )1/2) in Line 3 of Algorithm 1. Then Proof. According to lemma 1, if we choose μ S 0((2 2pv/
get if [xx,)) I 4. then [xx)]l I c, otherwise |/ f (x,, || 2 &. According Algorithm 1, if [x+)) 2 1. then for all r E [o, F1, the perturbation step is not reached.
According to Lemma 19, as long as the NCE step reached, then we have the Hamiltonian we decrease by & in single step. And according to Lemma 3 and Lemma 4, the Hamiltonian decrease monotonically in all steps, so we have Lemma holds.
Then we prove that if the NCE step is never reached in all steps T E (0, Lemma 5 holds. Let t = arg go (tllv, I V I 11. When t ( /4, F), then we have Eg - Eo S Eg/4 Eo S -6 according to Lemma 22. Then we discuss the case when t E [0, /4]. Using Lemma 24 by setting t as initial step, we have
S e and v [(x S Vle.ll"
+ +
S M... 1f 2 + 2.2 then Hamiltonian will decrease by & by Lemma 22. Otherwise, t2 E [t1 + T 9/4,t + 922, we have V S i by prediction of Lemma 5, we have || fXxx2)))
Let i2 = arg +9/49
3e
4. so we have PS V (xx,, )l 2 1. By Lemma 18,
|xx, x1, s 2. holds, then we have
v_,[PsT V2 f(x;;) S SV. fx, Pslli,, + +[V2)(x,, v f(x,, Mlllv,, 12 1 $2ppe.l
So according to Lemma 23, the Hamilton will decrease by 6.
C.2 NEGATIVE CURVATURE
Lemma 25. Suppose [V]() < 35 ( thus [()]| S E) and Xmin (V2 -Vp Xa and 1
X/ are at distance at most r from X. Let Xg - X The and vo = =Vo- = û where e1 is the minimum
eigen-direction of 42 f(x) and ro 2 v3. Then, running zeroth-order AGD starting at (x))Vo)
56r
and (x6, vo) respectively and set < Ö
13//6 we have
min - E, E, E -.
Proof. Assume that
min(F5 - Fo, F'g - Fg} 2 -28, where En and E% are Hamiltonians at (Xo, vo) and (xóo vo), respectively. By Lemma 18 and choose
S 0 2174 ) we have for any & $ J.
max ( [|x, - 11. |x] +1} S max |x; - -xp -x0 ||x - X²1 + x/ -i1}
AnE T
du
Sr + max{[Ix-- - xoll: |x| x S r +
+
92
S 257
0
48
Let 0 be the origin. Let w.
Xx- x/, according to lemma 20, we have
We+1 A'
W1
Σ A
(x A 1+
Wo
Σ A t-r [r)
W:
Wo
0
W-1
0
T=1
T=0
where & Vf(y.) - ff(r)) v2f(0)(x, y') =. Let A. (V2 f(oy: + (1 o)y))
(')(O)) then we have
A - v/) + - e = (1 0)w, - (1 -1100w,--) + ex b
where -
vfly)) - vf(y)). Since vo vo- we have w1 = Wos
|| S pmax{llx - -||, ||| - i1) < 2p and ||&a|| I (p + /| + pV ddp
Then
3
prove by induction that
t-1
In (I
0) Σ A 1--
(5t (0)
|| 1
| (I
A
We Wo
II
2
0=0
23

---

Published as a conference paper at ICLR 2023
For reasonably small μa, it is easy to check the base case holds for t = 1 as ||||| = 4n. Then assume that for all steps less than or equal to i, the induction assumption holds. Then we have
|well -I1 (I
0) A
Wo
(I
0)
Σ A (0) || S 0) A'
(Wo Wo
|| 11 (I
0)
Σ
1-1
A
-
(5t
00)
||
Wo
T=0
T=U
2 (I
0) A'
Wo
11.
Wo
then we have
|l&lll so(pS) + [wr- +
pV
0) A'
(wo Wo
1 I1
0) 0) A-1
(wo)
11) +
pV
3
(o
3
pVdy2
50(p5) 0) A'
Wo
||
Wo/
3
where the last inequality uses Lemma 16. For the case t + 1, we have
In (I 0) Σ A
Er 0
(I
A
0) |||$
==0
==
() ((as))la A)
(wo) (wo)
||+ pV dup
Σ (I 0) r-r
3
Without loss of generality, assume that the minimum eigenvector direction of V f(x) is along the first coordinate e1 with the corresponding x 2 matrix A₁. Let (a." -b( (1 0) A₁. we
choose μ1 S ( 213//
). then
21/z
pVdp²
Inn (I 0) E
& 0
Σ
- ait
(1)
3
T=0
1
Σ1 Σ
(1) a
(Olpe) -bf))/
r=0
1
{((np
+ 1)la - 10
r=0
{0(n
0) A
Wo
1 2 |l (I
0)
Wo
ll.
wo
Wo
where the second inequality used Lemma 16 that la? inequality used Lemma 14 and the fourth inequality used induction. Then we have
- n142
> and 1 S Ō
13/5 217z
); the third
7 < f Then we finished the proof of the
[wel] 2 (I A)
Wo Wo
1-1 | - (I 0)
12) 2 2
(6)
(I A)
wo
12
1 (1 (()))
wo
4
where the last inequality Lemma 16 and Amin ( (z)). Since ro 2 24,va we have
6g,
F = (22 Then
1 (1 + (()) ro 2 45 |w || = =|x X
which is contradicted with VI S T, max fexx - T11. ||x =|] S 29. Therefore the following inqualty holds
min(E, - Ev, E'g - En} s -28.
Since max (Eo - F, - A. max(s(xo) - (xx, f(x)) - ((x) S or+ 4² A/2 S8. Then we
have
min(Eg - E, E'g - E} s -8.
24

---

Published as a conference paper at ICLR 2023
Lemma 6. Suppose [x,)
||
3e ( thus [x)(x)) c). Amiu (xxx)) I -V and 4
perturbation added in iterations [ T, fl. Then by rumning Algorithm 1, we have Eg - Egg S - with probability at least 58
2
Proof. According to precondition of Lemma perturbation will be added at iteration 0, then the Hamiltonian will increase by at most &. According to Lemma 19, Hamiltonian will decrease by 26 least one NCE step called and thus E, Eg I -6. Otherwise NCE step never reached in iterations [0, J. In this case, denote by (r) the ball with radius r around Xo. Let X' C Bx, (r) be the region where Hamiltonian will not decrease by 6 if the AGD sequences started from at point x E X. Then by Lemma 25, the width of region no more than ro 24,vd' then have
56r
Vol(2) Vol(Bxo (r)) S ro x Vol(B(o-1(r))
(r))
ro rdd2 1 - TVTI 1/2) 2
68
Vol(BR (f) (r))
Then, with probability at least 1
se 23,
we have Fg Eo S -8.
C.3 PROOF OF THEBRRE 1
Proof. Consider the set H {-|7 E [0, [an]]]]] I 3r and suppose that all x, not e-approximate SOSPs. H = 0, then no perturbation added and by Lemma 5, we have Eg - Eg < -.. Else if H + 0. then define r' = arg min H. Then by Lemma 6, we have Er'+g - - E - E S -6. Thus the Hamiltonian will decrease by at least & (/(277) per step and the total steps is no more than 25 In all 277,, steps, Lemma 6 is called at most 20 times. Denote by the event that the argument of Theorem is true and denote by A,, e the event that the argument of Lemma 6 is true. Then by union bound, have 24, 66 1 - 6. 23,
8
(1,...,L - [
Pr(A) 2 Pr(N, = Pr A,) 2 1 E, Pr(A,) 21 21
D PROOF OF MAIN RESULTS OF ALGORITHM
Algorithm Renormalization(;/ r')
Zeroth-Order
Accelerated
Negative
Curvature
Finding
without
1: X + (iif((B((r')
2: Yo f X0
3: for t = 0,...... T' do
4:
Xx+1 = Yt. |
v-- (
+ +x) f((())
y
yx
5: Vi+1 = Xt+1 Xt
6:
Yt+1 X + 0)ve+1
return
X x xI
Lemma 26. The output of the algorithm 4 is the same as the unit in Algorithm 3. Denote the sequence of {xr} obtained by Algorithm 4 and Algorithm 3 by X1, X1.9 and
{x2.0. X2.1 X2,,9 respectively. Then we have
X1.9
X x
|1, X
X2.91 - X
Proof. We prove this by induction that
X2,
x
X1.6 - x r
V2.6 X
V1.6 x
||,2
X||
|
25

---

Published as a conference paper at ICLR 2023
It is easy to check that the base case holds for k = 0. Then we assume that the above equations holds for all & I t. Then we have
X2,4+1 - y2, x 112. - xx1
(55(" 32,t -
|22t x11 + +X) V5(x))
pd
-2, x 1| y|,, - x||
(v)()),;) {((()) 1|y,, - (y12 x- ((--x-(((((1a)) -
nd
Denote by 11, the value of V1.441 before renormalization, then
x1,+11 = V1,t n (Vf(v1.)) - +x())), Ví,-- xx,04 + (1 (1)0(xx(,,+ x1,1)
Then we have
122 - X1
( = 11y2, - x|| (y 1 - x-
(x1,041 - x),
X2
rd
pd
and
y2, x
V2,++1 x== x2 -8+ -0) - -x -))
(y x);
r'
then we have
V2, - x
1l2,1+1 - -x|1
1y,,411 -x|1.
r'
So we have
X2,4+1 - X y2, - x11
(x (xi,,01 - x) 1y2, x 11', -x1
(x),411 - x) x)= ||y2,411 - *1
(x 2).
xd
r
rd
rd
Then we finish the proof of the induction.
Note that V2 fx) has the following eigendecomposition: (xx Auuuy. where {um_>} forms an orthonormal basis of Rdd Without loss of generality, assume that λ S X2 S .... Aa and X1 < -Ve.. If Aa= I /2, then Lemma holds directly. Then we prove the case when Xa 2 /pc/2 and assume that X f -vpc I > 1). Let S be the subspace of Rd spanned by [u,, u2...., up} and S be subspace spanned by {up+1 up42,..., Uz) Then we have the following lemma:
Lemma 27. Denote o4 ||x,,- x
where Xt,S is the component of x, in the subspace S. Then, T during all the I'' iterations of Algorithm 4. we have 04 2 Omunn v d' given that an = / d 80-
Proof. Define x-1 Xg vo. Without loss of generality, we assume that 0. Consider the t worst case that Oz / a do and the component Fo,d along equals 0. Assume that the eigenvalues satisfy
A = Ap Ap-1
Ad-1 -VEc.
-2 V.) and assume that A lies in the direc- tion that make or as small as possible. Then, the component As S should be in the opposite direction to vss and the component Ag= in S should be in the direction of ge. Then we have both /I/ ||x ||xx,s>
Define A = [y=ll v fly: 1v.
and |s ||/llyell being non-decreasing. Note that
x = X + (1 - ()(++ - x.) 7 2 ((0) + (1 - 0)(++1 xx))
Then we consider the following recurrence formula:
|x++2,8=| || S (1 + ( + (1 - 0)( - ||xt,s- (I)) + 1/| As-ll-
Since ||xt,s= [xa]| is non-decreasing, we have
AAs=
|||||
|
X ||
||||
|xo
|
|x ||
|x+11.=1| ||
X
X
x
Xx
Xx,s| ||
X
1 - 0o
26

---

Published as a conference paper at ICLR 2023
|| |x++1||
2 x2
Vdp²,
PM
S 2pr',
2
3
where the last second step uses Lemma 2 and the last step is due our choice of f such that vdy² I n² Then we have
|x+22.5 || S (1 + 1/pe + 2npr ((2 0) (x - (1 - x(s II)
Then by Lemma 17, we have
|xt,s=| 5( ++Kg
)$ )²
2 (1-2 21150
(1-2-0-1s0
0 MS.
||x0,s
+
1
(1 + k5s )(x00, (2 - 0 + +ss))*
2
(1 + (gs J1s
+ use |x0ose||
1
+(
(1 + Kss= kss=)|[xoss+ 1] (2- - 1000-14:0 -1ss)))
2118=
(1
(1+ kige)))) 11s=
+ )²
)t (1--
2 2 0 (-2-0-1ss) M.. ||x0,s= + |x00.00|| II
+
1 + us.
||x0.=
|x00):111) )) (2 - 0 + +us=)*
2
20150
155
2ps
1s50
1 + Kic )d |xx |1 - + ps=))
=( 2
where Kg= = TTpe + 21pr' usee = v ((2 - 0)²
4(1 0) Suppose for some value 6, we have Itkge
0% 2 Omin for any S k < 1111.11 Then we have
||++,, 2 (1+ + T DE) 2 (1 (
(1
0) (1 || ||x,, (I) - 7/ Asl.
Since ||x+,,sl|// ||/xx11 2 Omin holds for all 1 1> O, we have
llv+t.
2
Omin then
Ty41ll
||s
|
vdu²
pr
y++1.s|
Omin |
Ommin
2
3
<
Omin
where the last second step uses Lemma 2 and the last step is due our choice of i such that vdy² < 72 Then we have
npr'
| || 2 (1+ + -1PP-
) - 0)||x++1.s|1 - (1 - 01l)x
O'min
Then by Lemma 17, we have
| 2 1 + Kg yd
(122- 2ps
2 2-
0 ps
|xo,s|| +
(1 +
(2 - 0 + us)
2
(1 Ks)
+( 2 - + MS
|x0,s||
(1 + ks)]|
(2 - -)=s)))
2ps
(1 + +Ks))s
+ KS yo,
2 2 - 11s |xo, +
||x0,sl|
(2 0 us)
2
2/15
Ms
+ Kis ye.
||x0,s||
=( 2
(2- 0 + +ss
2
where KS- = 1T
ner''
ps
V(12- -0)2 1(100) ). Then we have
Omin
|x,s||
+ kis y ||xo,s||
2 + ps y,
2
(
|x,,==|
1 + Kis 2/| 2||x0.s==|
2 2- 0 + +ts-
where
1 Ks
2(1 + ks)(1 Kgg)) =1
+ 2)mpr'
Ki 2 2mpr' /amin
I 1+ K6ge
Omin
2 0 + us
2(1 + 1s
2 2- 9) (1
2 2-0) = (1+
Ms.
2 0 V
(2 - 0)2
4(1 - 8)
1 )1
1
(2 - 8)2 02)
4(1 8)
2 - 0 + MSe
2 0
1 + ks
02 Ks - 0)2
1
02 + Kg- (2 - 0)2
2(nis - -is)
2 1 3mpr'
=(1+ + 2 - /\
1+Ks Ks
(1
2 0
V\
) 2
0
amin 0
27

---

Published as a conference paper at ICLR 2023
Then we have
|x,ss||
x
4pr
x0,s|
| ||
X ||
(1
(1 (1-1/53 1/11//²²>>
exp(
g1 7'1
[Xx.s=
||
2 xo
Omin
2 x1,
2 xo,
X0,sc
So we have
X0.5
Ott
2 Omin
VIxxS 12
8 xo,50 |x 11
Thus for all t S gi, we have 0₁ 2 Omin.
Proof of Lemma
Proof. As stated above, we only need to prove the case when da Vy Then there ex- 2
ist some p' such that Ao S -vpe/2 S A/+11 Let S' be the subspace of Fd spanned by {ui, ug....., ugy' and S be the complementary subspace. Define Xt,S'
Σ (u, xx) u, Xt, = 2i=p/+1 (u: x1) u, and let at = ||xx,s||||(xx] |//| We know that with probability at least
π d Vol(B (1)) 21 21
d = 1 - 80. dog
π d0 d
(o)(I)(
we have ap Vdo. Then we prove that there exists some to with 1 S t S T' such that
| ||
ue 88
Assume the contrary holds that for any 1 S sts g1, 1xx.g.stell
/pc and 1y vTe Then 88
||sta||
lls
st
we consider the case when s achieves the largest possible value and we have the following recurrence formula:
||x++,,5011 S
+ (1 - ([ |xx,s ()) + 1/] s
Since
vTc 88
for any 1 < k < L + 1, then we have
1/ s
A
2p
122
Vdp²
2pr
S
| ||
+ (1
0) x
Xt,sic|
4E y
Vper"
2
Vpc
where the last is step is due to Lemma 2 and our choice of μ such that vdya² S 22
Then we have
|x++2,=01|| S (1 + pp/p/2 2pr /vpe 0) 0)|xx++1.8001 (1- 0) [||/,, Il).
Then we have
+ Kisss
X1, S ||x ||(
)(2 - 0 + ''
2
where K. = PP /PE,
pSS uis
/22- 0)2
111-9 It
By Lemma 27, we have ||x 2
teeey.
[xx,.]
(2 -0- 0 + +s) for any 1 1515 g'. Then we have
2
(xge ||
2 2xx0
1 + Kig
g'
2 0 + 188 )
|s
|1o.s||
1 KS
2 8 + us
2
+ kighe
g' (2 2 0 + 11s
2 - 0 + use 3' <
2 d 1 Kig
g' 3/22 2- - uSe g.
a0
1 Ks
V π 1tks
2 + us
where
1+K8 Kg
(ns kS/)
< KS Kig
5
1 + KS
(1 + K1s)(1 k:500)
1 - (Ks - 1is:0)/2
+ (KS - k55'0
<1 //pp// /2 - prr(
ypc
Amin
T/pp
4
16
28

---

Published as a conference paper at ICLR 2023
2 0 + Ms
+
Pgte
2-
1
S
0 + ps
1 2-0
(1
+
Mgre
2-0
(1 ([*n))2-00)
4(1-0)
)1 v1
1(1-0)
(12 07²
2(K8 gic
Kg 15
T/D6
(pE)
4
2(R8 Mateel
1 1
2(x8 Matee)
40
16v
0
Then we have
|
2 d (1
(pc)
16v8 )
Vp
V π
S
||
80
88
So we conclude that there exist some
S to I T' such that |
ypc 87
Consider the
normalized vector xio then we have ||ég: || I Then we have
vir se
and ||ós 2 ||e|| - ||égre|
2
ypc 8
è f(Ojē =(égr + te.) ) (V² +ég)) = T V² V(0)@e + ē5.
v2 f(0)ès
<ellēgre||
upc
jés 112 v
pe
(1
pe
)2 v 4
pc
2
64
2
88
D.1 PROOF OF THEOREM 2
Proof. Recall the parameters setting of Algorithm 3:
3
1
0
7
LVd.
5n 384
11
48
4 4VR R
4p
g' = 32 vi log(
80 Spp
3 CA
π
8
32
pd
where CA is large enough constant. Define new parameter 9 = =KCCA. From Lemma 5 we know if (x+]l 2 3e for any r E F.. then by running Algorithm 3 have E Eo S 8. Then we first assume that for each time we can escape saddle points successfully, i.e., after g' iterations of the perturbation step, have é 2 f(E) S yTc
4. Then by Lemma 8, we have
min 1 10) f(x (00) S f(x
e Vo and the total times of random perturbations is no more than 384()(xx) / By union bound, the probability that least one time the negative curvature finding fails to escape saddle points is upper bounded by (84(f(xx) V' 5 S
( V [ S f(x) 384
120
Then we assume that we never encounter SOSP in the rest steps. Set the total number of iterations to be T = max? the number of periods containing only large gradient steps, then we have
& ( 768 ,' V O
(A/t//20//4 log(
(Vdd)) de"
Denote by the o
c7/4
N 2
T
384(f(xo) -
3 2 (20)
P
84)
P
A g
2( + g")
By Lemma 5 we have the Hamiltonian will decrease by N No > A,, which cause a contradiction. Thus we have with probability least 5, we must encounter an e-approximate SOSP during the T iterations.
L
E PARAMETER SETTINGS OF THE NUMERICAL EXPERIMENTS
29

---

Published as a conference paper at ICLR 2023
Table 2: Parameter settings of the cubic regularization problem experiment.
Algorithm
Parameters
d 20, 100, 200, 1000
PAGD
8 10,
1/6,r 0.01, Lthresh = 30, Ithresh
100
ZO-Perturbed-AGD
10, 1,
1/ 0.001, 0.001
Po-Perturbed-AGD-ANC
{ 10 1.7 1/ 0.001. 1 0.001
Table 3: Parameter settings the cubic quartic function experiment.
Algorithm
Parameters
d 20
PAGD
20, 1/2,r 10-3 4hresh 10, Othresh e/100
RSPI
( = 20, 1,02 = 0.6,Po. Pa. 0.8, To, = 5, T TDFII 20
RSPI(SPSA)
= 1.75, 20
= 0.65, Pv. = 0.8, To, 15, T TDFPI 100
ZO-GD-NCF
= 20, 10, =1/E
ZO-Perturbed-AGD
8 = 20, p 10, 1/f,r r- = 0.01, 0.001
HO-Perturbed-AGD--NN
E 20, p = 10, 11 = 1/2,r r 0.01, 14 0.01
d = 100
PAGD
{= 100, 1/6,r 10 Lthresh 10, Ithresh e//10 100
RSPI
ł= 100, 01 = 1, = 0.65. Pa. 0.95, T,, 15, TDr 20
RSPI(SPSA)
100, = 1.75, 02 0.65, Po: 0.95, To, 15, TDFPI 100
ZO-GD-NCF
t= 100, 10, 1/2
Z0-Perturhed-ACh AGD
= 100, p 10, = 1/e,r r = 0.01, 0.001
ZO-Perrubbd-AGD-ANCC
2 100, p- 10,1 1/6,r 0.01, 0.01
200
PAGD
== 110, 1/E,r = 10 finessh 10. Ithresh = c/100
RSPI
== 200, 01 = 1.5, 02 = 0.65, Pr. 0.96, 7 15, T TDFPI
RSPI(SPSA)
= 200, 01 = 1.75.
0.65, Po: 0.98, Ta 15, TDMPI 100
ZO-GD-NCF
= 150, 10, 17 1/6
Z0-Perturbed-AGD
t= =200,
10, 11 = 1/2, 0.01, 11 0.001
ZO ZO-Perrurbe--AGD-ANCCE
t= 200, p= 10, 1/2,7 0.01, 0.01
30


Reviews:
[{"review_id": "crzIFuscEgo", "reviewer": "Reviewer_kuK4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of escaping from saddle points, a basic problem in nonconvex optimization. Specifically, this paper considers function evaluations, i.e., zero-order inputs, and is able to give algorithms with ~O(1/eps^1.75) iteration complexity and ~O(d/eps^1.75) query complexity. Although this 1/eps^1.75 dependence has been achieved by gradient-descent based methods, this paper is first one to achieve the same dependence for gradient-free methods. Finally, numerical experiments are conducted to corroborate the theory results.", "summary_of_the_review": "Overall, I think this is a novel and outstanding work in studying zeroth-order methods for escaping from saddle points, and I’m happy to recommend acceptance for ICLR 2023. Nevertheless, the paper still has space to improve as mentioned above.", "strength_and_weaknesses": "From my perspective, this paper has the following strengths:\n\n- This is the first work which gives zeroth-order methods for escaping saddle points with matching eps dependence compared to first-order methods. This is a great contribution to me and significantly improves our understanding of zeroth-order methods.\n\n- Two algorithms are proposed to achieve the result of ~O(1/eps^1.75) iteration complexity and ~O(d/eps^1.75) query complexity. The second one based on negative curvature finding only has one logarithmic term in d.\n \n- The theory results are corroborated by numerical experiments on two instances: cubic regularization and quartic functions. Codes are also provided in the supplementary material.\n\nNevertheless, the paper may still have space to improve from the following aspects:\n\n- It would be very helpful if the authors can illustrate more on the practical cases where both escaping from saddle points is a vital problem and we have to use zeroth-order methods instead of first-order methods. In the introduction, the authors mentioned the situations where the calculation of explicit gradients is expensive or even infeasible, such as black-box adversarial attack on deep neural networks. This is still a bit vague to me; would be helpful to explain how we have the function evaluation access in such problems.\n\n- The writing in this paper is a bit sloppy in general and has space to further polish. From a relatively superficial reading, I can already spot the following glitches:\n\n- - Second paragraph in Page 1: non-convex problem 1 -> non-convex problem (1). This also applies to a few following places.\n\n- - Third paragraph in Page 1: O(1/eps^2) -> Theta(1/eps^2) (Here, the authors are talking about the optimality of gradient descent, so a lower bound or tight bound should be reflected here.)\n\n- - Second half of Page 2: proposed a first-order Negative curvature finding framework -> … negative (should be small letter instead of capital letter here)\n\n- - End of Page 2: with fewer function query complexity -> with smaller function query complexity, or with fewer function queries\n\n- - Beginning of Page 3, second bullet point in contributions: Due to the efficiency of the negative curvature finding for finding the most negative curvature direction near a saddle. We further study -> …, we further study (currently, the first sentence is not complete)\n\n- - Beginning of Page 4: By the property Hessian Lipschitz -> By the Hessian-Lipschitz property \n\n- - Middle of Page 5: The second part of the Algorithm 1 is the Nesterov’s accelerated gradient descent steps with its gradients estimated by 2 -> … with its gradients estimated by Eq. (2) (otherwise it reads like the gradient is estimated by the value 2)\n\n- - Page 5, after Eq. (6): Specifically, when 6 doesn’t hold -> Specifically, when Eq. (6) does not hold (in formal English writing, abbreviations are supposed to be open). Same change shall be applied to the statement of Lemma 3: when 6 does not holds -> when Eq. (6) does not hold\n\nIn addition, I also have a couple of questions for the authors:\n\n- It would be helpful to give detailed comparison between Algorithm 1 and Algorithm 3. Algorithm 1 gives slightly worse query complexity results (extra poly-log d overhead); so why is this of general interest over Algorithm 3?\n\n- In Eq. (2) in Section 2.3, a central difference coordinate-wise gradient estimator is applied. In fact, in numerical analysis, higher-order central difference formulae have been studied, see for instance Li https://www.sciencedirect.com/science/article/pii/S0377042704006454?via%3Dihub It would be of general interest to discuss whether using a higher-order central difference formula could further improve the results.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XFIi5q-JFrf", "reviewer": "Reviewer_Y99G", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes two zeroth-order Nesterov’s accelerated gradient descent based algorithms that can escape saddle points and converge to second order stationary points. The main idea of the work is to use the central finite difference gradient estimator to approximate the gradient. The theoretical results show that the proposed can converge to second-order stationary points with fewer function queries. \n", "summary_of_the_review": "Overall, this is a good paper, and I would recommend an \"accept\".", "strength_and_weaknesses": "Strength \n\nOverall, the paper is well written and the related work are well cited. The introduction is clearly organized. The derived convergence results match the state-of-the-art one and are faster than previous zeroth-order algorithms for escaping saddle points. Numerical results illustrate the effectiveness of the proposed algorithms.\n\nWeaknesses\n\n1. Since the work focused only on the deterministic optimization, this may restrict the application scenarios of the algorithm. It'd be nice if the authors have further insights for stochastic  optimization as well.\n\n2. The algorithms use $\\mathcal{O}(d)$ function evaluations per iteration to enable a high accuracy approximation of the gradient,  which may also not\nbe practical in realistic applications when the dimension of the problem is large. I wonder if such a gradient estimator is necessary?\n\n3. Since the algorithms are similar to the Jin et al. and Zhang et al., it would be helpful to explain what novel theoretical analysis techniques are used in this work.\n\n4. In theoretical results, the value of parameter $\\mu$ is set to be very small, is it the same in the experiment? Since in practice, too mall $\\mu$ may cause system error. It would be better for the authors to explain how to choose the parameter u in the experiment.\n\n5. Minor issues:\n\nit seems that $\\mathcal{H}_f$ only appear in section 2.4, where is it used?\n\nAlgorithm 2 is from Jin et al. 2018, you should add a cite here or delete it and add a footnote.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "G1TYSo09k_V", "reviewer": "Reviewer_sdTo", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors provide to their knowledge the first two variants of Nesterov's accelerated gradient-free algorithms for escaping saddle points of minimization problem, with comparable convergence rate to their first-order counterparts and smaller oracle complexity compared to prior derivative-free methods for finding second-order stationary points.\n", "summary_of_the_review": "Based on \"Strength And Weaknesses\" above, I recommend borderline accept for this paper. After my major concerns above about the complexities are solved by the authors, I would like to raise my rating. ", "strength_and_weaknesses": "Pros: This paper studies a significant novel research problem. Theorems and experiments look solid. The presentation looks generally clear, brief and neat. \n\nCons: There are some points that need to be clarified, especially those about complexity results, See \"Clarity, Quality, Novelty And Reproducibility\" for detail. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "BY14k69YAnD", "reviewer": "Reviewer_85d1", "summary": "", "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": "", "summary_of_the_paper": "The paper shows convergence to an ε-second-order stationary point for zeroth-order methods. They substantially improve existing bounds, achieving ε^-7/4 dependence on ε and quasi-linear dependence on problem dimension. They present two algorithms: the first algorithm and its analysis are based on the Jin et al’18. The second algorithm, based on the Hessian-vector product idea, substantially improves the logarithmic factors. One of the main component in their analysis is better estimation of discrepancy between the true gradient and its approximation, based on the Lipschitz Hessian property.\n\n", "summary_of_the_review": "Solid paper, accept.", "strength_and_weaknesses": "My main concern about the paper is the lack of explanations:\n-- The algorithms should be explained in more details. I’m familiar with Jin et al’18, so I had a good idea what happens in Algorithms 1 and 2. However, while I could parse Algorithm 3, I can’t say I understood what happens there.\n-- Similarly, it would be great to explain the choice of parameters (I mean, why their values make sense), especially μ in Theorem 1.\n-- Proof outline for Section 3 should be added.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%