Escaping saddle points in zeroth-order optimization:  two function evaluations suffice
Authors: Zhaolin Ren
Yujie Tang
Na Li
Venue: Submitted to ICLR 2023 (2023)
Keywords: zeroth-order optimization
nonconvex optimization
escape saddle points

Abstract: Zeroth-order methods are useful in solving black-box optimization and reinforcement learning problems in unknown environments. It uses function values to estimate the gradient. As optimization problems are often nonconvex, it is a natural question to understand how zeroth-order methods escape saddle points. In this paper, we consider zeroth-order methods, that at each iteration, may freely choose 2$m$ function evaluations where $m$ ranges from 1 to $d$, with $d$ denoting the problem dimension. We show that by adding an appropriate isotropic perturbation at each iteration, a zeroth-order algorithm based on $2m$ function evaluations per iteration can not only find $\epsilon$-second order stationary points polynomially fast, but do so using only $\tilde{O}(\frac{d}{\epsilon^{2.5}})$ function evaluations.

Under review as a conference paper at ICLR 2023
ESCAPING SADDLE POINTS IN ZEROTH-ORDER OPTI- MIZATION: TWO FUNCTION EVALUATIONS SUFFICE
Anonymous authors Paper under double-blind review
ABSTRACT
Two-point zeroth order methods are important in many applications of zeroth-order optimization arising in robotics, wind farms, power systems, online optimization, and adversariable robustness to black-box attacks in deep neural networks, where the problem be sigh-dimensional and/or mareing Furthermore, such problems may be nonconvex and contain saddle points. While existing works have shown that zeroth-order methods utilizing (?(d) function valuations per iteration (with d denoting the problem dimension) can escape saddle points efficiently, it remains an open question if zeroth-order methods based on two-point estimators can escape saddle points. In this paper, we show that by adding an appropriate isotropic perturbation at each iteration, zeroth-order algorithm based on 2m (for any S m I d) function evaluations per iteration can not only find c-second order stationary points polynomially fast, but do so using only (d/e2s) function evaluations.
INTRODUCTION
Two-point (or in general 2m-point, where 1 S < d d being the problem dimension) estimators, which approximate the gradient using two (or 2m) function evaluations per iteration, have been widely studied by researchers in the zeroth-order optimization literature, in convex (Nesterov and Spokoiny 2017 Duchi et al. 2015) Shamir (0017). nonconvex (Nesterov and Spokoiny (017)) online (Shamir 2017). as well as distributed settings [Tang et al. 2019). A key reason for doing so that for applications of zeroth-order optimization arising in robotics (i et al. 2022). wind farms (Tang al. 2020a), power systems (Chen et al.) (2020), online (time-varyingg optimization (Shamir 2017 learning-basee control (Malik et al.) 2019 Li et al. (021). and improving adversarial robustness to black-box attacks in deep neural networks (Chen al. 2017). may be costly or impractical to wait for sid) (where d denotes the problem dimension) function evaluations per iteration to make step. This is especially true for high-dimensional and/or time- varying problems. See Appendix A for more discussion. However, despite the advantages of zeroth-order methods with two-point estimators, there has been a lack of existing work studying the ability of two two-point estimators to escape saddle points in nonconvex optimization problems. Since nonconvex problems arise often in practice, is crucial to know if two-point algorithms can efficiently escape saddle points of nonconvex functions and converge second-order stationary points.
To motivate the challenges of escaping saddle points using two-point zeroth-order methods, we hegin with review of escaping saddle points using first-order methods. The problem of efficiently escaping saddle points in deterministic first-order optimization (with exact gradients) has been carefully studied in several earlier works (Jin al. 2017 2018). key idea in these works is the injection of an isotropic perturbation whenever the gradient is small, facilitating escape from a saddle if a negative curvature direction exists even without actively identifying the direction. However, the analysis of efficient saddle point escape for stochastic gradient methods is often more complicated. In general, the behavior of the stochastic gradient near the saddle point can difficult to characterize. Hence, strong concentration assumptions as subGaussianity, boundedness of the variance or bounded gradient estimator (Ge et al. [2015] Daneshmand et al., 2018 Xu al. 2018 Fang et al. 2019 Roy et al. 2020 Vlaski and Sayed 2021b), creating an analytical issue when such idealized assumptions fail to hold.
typically made the stochastic gradients being used, such
Indeed, though zeroth-order methods can be viewed as stochastic gradient methods, common zeroth order estimators, such as two-point estimators (Nesterov and Spokoiny (017).. are not subGaussian, and can have unbounded variance. For instance, it can be shown that the variance of the two-point

---

Under review as a conference paper at ICLR 2023
estimator is the order of [(d] ((d]V (Nesterov and Spokoiny 2017), with both dependence on the problem dimension d as well as on the norm of the gradient. which can be unbounded. Due to non-subGausiianity and unboundednesss. it is tricky to bound the effect of such zeroth-order estimators and establish tight concentration inequalities that facilitate its escape near saddle points. In addition, the large variance of the zeroth-order estimator is also an issue away from saddles when the gradient is large. While this is not an issue to show function improvement in expectation, as we discuss later, this becomes an issue when guaranteeing high probability bounds.
Due to these difficulties, previous works on escaping saddle points in zeroth-order optimization have exclusively focused on approaches requiring ([d) function evaluations per iteration to accurately estimate the gradient (Bai et al.] [2020] Vlatakis-Gkaragkee
et al. 2019), or in some cases negative curvature directions (Zhang et al. [022,] Lucchi et al., (021) or the Hessian itself (Balasubrama nian and Ghadimij 2022). reducing in sense the zeroth-order problem back to first-order one. However, as explained earlier, two-point or 2m-point zeroth-order algorithms are important for high-dimensional and/or time-varying problems in many applications areas. This raises an important question: Can two-point zeroth-order methods escape saddle points and reach approximate second order stationary points efficiently?
Our Contribution. In this work, we show that by adding an appropriate isotropic perturbation at each iteration, a zeroth-order algorithm based any number of pairs (m ranging from 1 to d) of function evaluations per iteration can not only find (c, (t)) order stationary points (ef. the definition later in Definition 1 polynomially fast, but do so using only ((polylog())//2) function evaluations, with probability of at least - 6. In particular, this proves that using single two-point zeroth-order estimator at each iteration (with appropriate perturbation) suffices to efficiently escape saddle points in zeroth-order optimization, with high probability. Moreover, for functions that are (e, v)) strict-saddle (see Definition 3 for definition of strict saddle functions), our results become (polyyog ))//)"") which is significant improvement when >>>>>>>>>>> E; strict saddle functions have been identified as an important class of functions in nonconvex optimization, with several well-known examples such as tensor decomposition (Ge et al. 2015), dictionary learning and phase retrieval (Sun) jet al. 2015). A comparison of our results with existing zeroth-order and first-order methods is shown in Table [ We also provide numerical results in Appendix G showing that our proposed two-point algorithm requires fewer total function evaluations to converge than zeroth order methods that use 2d function evaluations per iteration, for a nonconvex test function proposed in Du et al. (2017).
To overcome the theoretical challenges that were discussed earlier, we i) first show, via careful analysis, that zeroth order methods can make function value improvement across iterates with large gradients with high probability, even when only a single two-point estimator (which can have significant variance large gradients) is used per iteration. ii) Second, near saddle points, we overcome issues caused by the unbounded variance and -un-suuaaussinity of zeroth-order gradient estimators by developing new technical tools, including novel martingale concentration inequalities involving Gaussian vectors, to tightly bound such terms. In turn, this allows us to show that the noise emanating from the zeroth-order estimators will not overwhelm the effect of the additional isotropic perturbative noise, facilitating escape along negative curvature directions. To the best of our knowledge, both analyses are novel, and may be independent contributions on their own.
Related Work. Due space considerations, we defer full discussion of related work to Appendix A
PROBLEM SETUP
We make the following assumptions on the class of functions f Rd - which we consider. Assumption (Properties of f). We suppose that f IRd R satisfies the following properties:
1. f is twice-differentiable and lower bounded, i.e. f == min, f(x) -0.
2. f is L-Lipschitz, i.e. [[V [Vf(=)-V[(())) ff(() < -|| - - Vx, Rd
3. f is p-Hessian Lipschitz. i.e. [(x) f()()) < e|| - all Vx, y E Rd.
In our work, we focus on finding approximate second order stationary points, defined below. Definition 1. A point E Rd is an (c,4))-second order stationary point if
[V((a]] < 6, and Amin Amin (V² -
2

---

Under review as a conference paper at ICLR 2023
Iteration Complexity
Fun. evaluations per iter.
Jin et (0117) (deterministic) Fang al. (2119) (SGD)
First-order
Bai ct al. (020
0
Vlatakis Vlatakis-Gkaraghe Gkaragkounis et al.
2019
0
(dd
Zeroth-order
Balasubramanian and Ghadimi
(002
Ô
Lucchi et al. [2021
Zhang et al. 2022
(d)
Al Algorithm (this paper)
2m
Table Selected comparison of convergence results to (c, O ( second order stationary points in smooth, nonconvex functions; for 1, the convergence is to (c, 2// second order stationary points. For the term & in the denominator is (i) vi when the function f is (e, u -strict saddle for & > O(ve) (see Definition 3 for a definition) and (ii) O(VE) if otherwise.
We define an (c, (c.:))apppoxximat saddle point as follows.
Definition 2. A point E Rd is an (e, aapproxximee saddle point, if
[f(x)) < and Amia Ainin(V2f (V2((x) - -9.
Following past convention (Jin al. 2019a), we will focus particular on escaping (c, / points. For notational simplicity, in Tollowing text, we refer to ( points simply as saddle points and (e, the definition of e-approximate saddle points above, it is known that many nonconvex functions with saddle points, such as orthogonal tensor decomposition (Ge et al. 2015), phase retrieval and dictionary learning (Sun al. 2015),, satisfy what is known strict saddle condition (Ge et al.) 2013). For the Hessians of the saddle points of such functions, there is always a strict negative eigenvalue whose magnitude bounded from below. We provide a precise definition below.
order stationary points as e-second order stationary points. Beyond
Definition 3. A wvice-differentill function f(x is (c, -sstritt saddle, if for any point x, at least one of the following is true:
V 2 or Amin {=f(z))
As a corollary of Theorem (to be stated later), for functions f which are (e, 2b) strict saddle, assuming
that 1b 2 ppc, the sample complexity of our algorithm scales as ÿ max (La (max(L ()(())))))))))) which me*
scales Ω me? when is of size (2(1). Thus, in this setting, for two-point estimators, where m ===11 1, the dependence on and in our sample complexity (as measured by function evaluations)
matches that achieved by the algorithms in Vlatakis Gkaragkounis et al. (2019); Zhang al. (202
which have to use 2d function evaluations per iteration to estimate the gradient.
In our work, consider the following batch symmetric two-point veroth-order estimator.
Definition 4 ((Batch) two-point zeroth-order estimator with perturbation). We define m--btch two-point zeroth order estimator as follows:
[xx uZz) f(x uZz) Zi,
(m) (x)
(I)
2u
where Z, f.dd N(O, 7), and 0 is smoothing radius.
3

---

Under review as a conference paper at ICLR 2023
Such 2m zeroth-order gradient estimators have frequently been studied in zeroth- optimization works (see e.g. Nesterov and Spokoiny (2017).. To facilitate efficient escape from saddle points, our proposed Algorithm L adds isotropic perturbation at each iteration.
Algorithm 1: Zeroth-order perturbed gradient descent (ZOPGD)
input: ; 2g, horizon T, step-size 17, smoothing radius u, perturbation radius r, batch size m for step / .,..., do
(m) Sample ((m) = (Z 1=1 ~ [(,, I) to compute gu (xI)).
(mm) (xx) + Y,) where Y, ~ N(0, 1)
Update 1 = dz - ga
We now state an informal version of our main result, and follow that with few remarks.
Theorem 1 (Main result, informal version of Theorem J. Consider running Algorithm
[ Let Ô hide
polylogarithmic terms in ó and other parameters. Suppose (0, 1/e]. Suppose upe S min (1, L such that &b S min L.. where
min (,, 1,
f() is (c, (.,1))-stric saddle for any up /pc otherwise.
Vpc
Suppose
miu miiu(vevTT) vpd
, ,r= (=)=((),;)000 0
ma Then, in (max
(f(xa) - ( p2[[(v0) -1)
T= Ω
11E2
m854
(dmax(Le L, (ff(o)))) -M) + dmax (((00)))))))
á
mibe
maps
á [dmxx L,, 122)) - -)
mobe2
iterations (with each iteration using 2m function evaluations), with probability least at least half the iterates are e-approximate second-order stationary points.
Remark 1.
As the choice 1y in Proposition (Appendix) D) and Theorem ( (Appendix] respectively
imply, the f
f(zo)-f" term in the sample complexity comes from the large gradient iterations ge*
(Proposition 4 whereas the Ô
term comes from the escape saddle point phase.
Comparison to gradient-based methods. For first-order escape saddle point algorithms, standard perturbation- based methods (without acceleration) find (c, ((Vc))-secome
stationary point using (1)e2)) iterations for deterministic GD (Jin et al. 2019a while for standard SGD the best-known rates are slower at ((1))".) (Fnn al. 2019). contrast, our sample complexity (as where J is defined in Eq. (2 The
measured by the total number of function evaluations) is Ô
extra (linear) dependence on d is typical for zeroth-ord -oder algorithms (see e.g. Nesterov and Spokoiny (2017)); ); intuitively, gradient calculation for d-dimensional functions requires O(d) calculations agnostically, so it makes sense that zeroth-order algorithms requires d times more iterations. For general non strict-saddle functions, our dependence on c sits between that of the deterministic methods and SGD methods, and suggests the benefit of specialized treatment of seroth-ordes methods over considering them simply as a subclass of SGD methods. Moreover, for (e, v/-- strict-saddle functions where di = 2(1), our sample complexity becomes Ō d ). with an e dependence that matches that of the best existing sample complexity for aon-accelerated first-order escape saddle point methods Jin et al. (017)
Comparison to existing zeroth-order methods. As Table I suggests, sample complexity significantly outperforms that of Bai et al. (2020) and Balasubramaniann and Ghadimi (2022), and also
II our paper, we focus on the case vpc < L; otherwise, by the L-Lipschitz assumption, Amia X f=))) 2 T. for all x E IRd, which implies e-first order stationary points also e-second order stationary points.
4

---

Under review as a conference paper at ICLR 2023
that in Lucchi al. 2021),
which is random search method. The sample complexity in Vlatakis
Gkaragkounis et al. (2019) ; Zhang et al. (2022) outperform our method, with a function evaluation
complexity of ( However, for for (c, -)- strict-saddle functions where & = (2(1), our sample
complexity becomes (14) ) which matches the sample complexity in Vlatakis- Vlatakis- Gkaragkounis et al. (2019); Zhang et al. (2022). Moreover, a key limitation of their methods is a requirement to use ((d)) function evaluations estimate the gradient at each iteration, which may not be practical in realistic applications when d is large. In contrast, our method supports any number of function evaluations at each iteration between to d. Moreover, numerically, we found that for test nonconvex function proposed in Du et al.] (2017), our method (with two-point estimators) takes fewer function evaluations to escape saddle points and converge to the global minimum than the methods in Klatakis-Gaaragkouiis et al. (2019); Zhang et al. 20222).
3 PROOF STRATEGY AND KEY CHALLENGES IN THE ZEROTH- SETTING
Broadly speaking, our proof include two major parts, i) characterizing the progress made in iterations when the gradient is large (which we can define be iterations / where || [.+)]l 2 e) (Section 3.1 ii) and iterations when we are at an e-approximate saddle point (where progress may be made along the negative eigendirection of the Hessian matrix) (Section first-order case (c.g. Jin et al. (2019a)), the zeroth-order setting brings forth several challenges as we explain later in the individual subsections. sketch out our high-level proof outlines, and provide statements of the main technical results. Note that due to the space limit, the full proof is provided in the Appendix.
While the approach is similar to the
the rest of this section, we explain these challenges,
3.1 SHOWING FUNCTION DECREASE WHEN GRADIENTS ARE LARGE
Challenge. Due to the noise in two-point (or 2m where m is a small constant) zeroth-order gradient, even when the gradient is large, it may not always be possible to make progress at each iteration, especially when m < d is used in the gradient estimation equation in Eq. ① While it is tempting to use an expectation-basee argument to handle this issue, it is known that expectation- sppeetation-based function decrease arguments are insufficient for escape saddle point purposes (see e.g. Proposition 1 in Ziyin al. (02T)) ). We tackle this issue by using high-probability arguments instead; note that achieving these high-probability bounds is highly nontrivial due to the large variance of the two-point zeroth-order estimator (scaling with times the squared norm of the gradient). Hence, any single iteration of the zeroth-order method may in fact lead to a function increase rather than decrease.
High-level proof outline. (i) We first characterize the function value change for our proposed algorithm (Lemma]) D. (ii) Next, we tackle the issue of the possibility that the function value might increase for any given iteration. The key idea here is that across any small consecutive number of iterations, there will be one iteration where the zeroth-order estimator is sufficiently aligned with the gradient direction (Lemma 14 in Appendix D). (iii) Along with a series of other technical results in Appendix D we then show that the function makes sufficient progress across the duration of the algorithm, with high probability (Proposition D. To more concretely illustrate the key analytical challenge, we next introduce the following function decrease lemma, proved in Appendix D
Lemma 1 (Function decrease for batch zeroth-order optimization). Suppose at each time t, the algorithm performs the update step (with batch-size parameter 1 1 S d)
I++1 = It -1 17 9h
(m) (x+) + +.).
where
((m)) (xx)
(x))
1
Mi + uZze.) - sax uZer))) Ze
m
2u
1=1
where each Z1, is drawn i.id from (O, I), u. > 0 is the smoothing radius, and Y, ~ N(0, 1 with > 0 denoting the perturbation radius.
Then, there exist absolute constants e > 0, C1 2 such that, for any T E z and T 2 r >>>0 >0 > 0 and 8 E (0, 1/el. upon defining Ho, (6) to be the event which the inequality
f(x+) - f(v)) S
3n
Σ t=0
Z ( + ("
e m
Σ Div((2))1
4
m
5

---

Under review as a conference paper at ICLR 2023
Tup end log T
edd (oog T
+ +Tmmfulpp
T
+ ne1r + L.) log + + Lnj
(3)
8
is satisfied (where = log(Co (e0(CcmmT//i /6)) we have
(T + 4)0
P(NT=1Ha,--0) 2 5
P(Ho,, (0)) 2
for any 0 S S.
Our goal is to show that we can arrive at a contradiction f f(r)) < ming f(x) when there is a large number of steps which VV fxx))l 2 (Proposition As we can see from Eq. 3 this implies that we need to prove a lower bound of the form
m Σ
Σ
T-1
2
eI 2d
T-1 [
Σ
m
for some a which is not too large (an example would be picking such that it only scales loga- rithmically in the problem parameters). However, is tricky to prove such lower-bound in the
zeroth- veroth-order setting. In particular, for small batch-sizes m, 1 E [fx) could be small
even as | [xx())) is large; this because for each i E [m] Zz,; could have negligible component in the V((x)) direction. This necessitates a more delicate analysis to prove bound similar to Eq. (4p. Due to space reasons, we defer our more detailed proof approach outline to Appendix D (see the discussion immediately following Lemma [I] result which limits the number of large-graden gradient.
The results in Appendix D euulminatss in the following
Proposition (Bound on number of iterates with large gradients, informal version of Proposi-
tion Let å E (0, 1/e] be arbitrary. Letting Ô hide polylogarithmic dependencies on ô (and other parameters), consider choosing u, and T such that
a VVEE Vpd
r= O(e),
m dT.
T T= ((((=))-1)+
TY6
Then, with probability at least 1 - O8)), there are at most T/4 iterations for which [v(())] 2
3.2 MAKING PROGRESS NEAR SADDLE POINTS
Challenge. The noise in two-point zeroth- estimators makes the analysis around c- approximate saddle points challenging, because the concentration properties of the (non-suGGaussian) noise hard to characterize. Intuitively, a noisier estimator might facilitate easier escape from saddle point. However, without appropriate concentration bound, the noise may behave in unpredictable ways, preventing escape from saddle regions. Previous analysis of saddle point escape using stochastic estimators typically requires these estimators satisfy subGaussian properties (Jin et al. 2019a Fang et al. 2019), which zeroth-order estimators do not satisfy.
High-level proof outline. (i) We first prove technical result showing that the travelling distance of the iterates can be bounded in terms of the function value decrease (i.e., Improve or Localize, Lemma (ii) Next, at any e-saddle point, we consider coupling argument and define two sequences running near-identical zeroth-order dynamics, differing only in the sign of their perturbative term along the minimum eigendirection of H which denotes the Hessian of the saddle (Lemma 3.. Using Lemma in point (i). if we assume for contradiction that the two sequences both "get stuck" and make little function value progress, the dynamics of the difference between the two sequences will remain small as both sequences remain close to the saddle point. iii) However, since the perturbation vectors of the two sequences differ in the (most) negative direction H, the norm of the the difference of the two sequences will grow exponentially so long as a). the sequences remain close to the saddle point (and thus the Hessian has a negative curvature direction) and b). the effect of the zeroth-order stochastic noise can be controlled. This leads to contradiction, implying that sufficient function decrease must have been made (Propasition5]iae Appendix (iv) To show that the zeroth- order stochastic noise can be controlled, prove technical result (Proposition 2). providing

---

Under review as a conference paper at ICLR 2023
concentration bound for the product of (possibly unbounded) subGaussian random vectors that scales linearly with the dimension d. This enables us to control the effect of the zeroth-order noise near saddle points, and is essential in showing that the eventual sample complexity scales linearly with d.
We provide a more detailed proof sketch below, where we claborate more on our analytical challenges and ideas. We first introduce an informal statement of key technical result that bounds, with high probability, the travelling distance of the iterates in terms of the function value decrease.
Lemma 2 (Improve or Localize, informal version of Lemma 23 Consider the perturbed zeroth- order update Algorithm Let 8 E (0, 1/e] be arbitrary. Consider any T. = Q ( log(1/6)). and any to 2 O. For any F > O, suppose (xTT,+t)) - [( > - F, i.e. f((1to) [IT,,+to) F.
Letting Ô hide polylogarithmic terms involving Ö, suppose
min (VE, (VE.VT)) u ==Ō
Vid
r Ō
min
( (T,
F f.
1 n=
m m dLL
Vid
Then, with probubility at least 1 - 0 (=A) (here T 2 Ts denotes the total number of iterations), for each T E {0,1,...,Tp we have that
100
|| 11 s ΦT, (6. F), where Or, (6, F)= max Ts / =1) +
Intuitively, the above result shows that if little function value improvement has been made, then the algorithm's 's iterates have not moved much such that remains approximately in saddle region if started out in a saddle region. Next, Lemma formalll introduces the coupling we have mentioned, setting the stage for the rest of our arguments. For notational convenience, in this section, unless otherwise specified, we will assume that the initial iterate xo is e-saddle point.
Lemma 3. Suppose To is an c-approximate saddle point. Without loss of generality, suppose that the minimum eigendirection of H := ((x) is the e direction, and let y to denote -Amin (V² f(x)) (note 2 /Pe.. Consider the following coupling mechanism, where we run the zeroth-order gradient dynamics, starting with Fy. with two isotropic noise sequences. Y, and Y; respectively, where (Yi) -YY)), and (Yi); (Yo), for all other & 1. Suppose that the sequence (Zi, (eereemm is the same for both sequences. Let {xr) denote the sequence with the (Yi) noise sequence, and let the {2/} denote the sequence with the {Y') noise sequence, where
1/41 = -17
Z Z. + 7/4 Z. Z. 2i. + +X,)
z66 = No.
and Hy, = What - -1f,i-- with H b,it = v2f(2' + de uZ,) for some df E [0. 11. and
2
Hi H = V - al.,,- uz() for some a',,,- E [0, Then, for any 2 0.
8141 2141 2'41
nH 1r 10 (T)
Σ (1 nH) TH, H)
=
Woo (1+1)
Wn(++1)
Σ (1 nH) ( Eu(T) 2 nH "
-=
Wc((+)
Wy((+13
where
Soo (t)
m
Ze, ZT, - 1)V5(xx), (1)
m Σ - (l) (t) S. (1).
1
- -1)Vf(a)).
1=1
m
1
(t()) = m
Ze. Ze,,H,,,.... He,,,,,, (t) = m
クタ Zu H., Ea(t) (u())) (t),
2
N1 '- v2 {2f((rr (1 a)ai)da.
8, Y, Yi.
7

---

Under review as a conference paper at ICLR 2023
Our goal is to show that the dominating term in the evolution of the difference dynamies comes from the Wp term involving the additional perturbation. To this end, we need to bound the remaining terms, W our Wn, W.. A key technical challenge is to find a precise concentration bound for the W 9o (t + 1) term, where
m 1 m Σ
oo (t++1== = Eu-
For the simplicity discussion, we assume for the time being that m 1, and drop the index in the subscript of Zr Since ] I, heuristically, assuming that Z, Z / satisfies "nice" concentration properties, utilizzng the independence the Z, across time and the fact that (I - n 3 (1 + 77)4, we would like to show that with high probability,
H Σ (1 m)) ( -) II -V())) Fr-1]
90 (1)1 S
vf(x:)))
(5)
where J--1 is allnaaa containing all randomness up and including iteration 1, such that v, and x', are both F,-1, but 7, is not. Then, assuming that Eq. 5 holds, since
IE - (V) ((a))) | = O(d)llf((.) - -----/(( v
[r-1]
it follows that
[|W, 00 (+)l S "N ((d) Σ (1 -) -V(((==)))((()))) (+4))
With this bound I so [I) eventually prove in Proposition 5 in Appendix E.3 that algorithm escapes any s-saddle point with constant probability and that the O(d) term appearing in the square root term above will eventually lead an (dd dependence the sample complexity We note that the (d) dimension dependence matches that of the best-known existing upper bound for finding first-order stationary points in smooth nonconvex zeroth-order optimization (Nesterov and Spokoiny 2017), and has been conjectured to be the best possible dimension dependence for general smooth nonconvex zeroth-order optimization (Balasubramanian and Ghadimi 2022).
Key technical challenge The key challenge in the above argument is to show that equation in the form of Eq. (5) could in fact hold. At first glance, that an inequality such as Eq. (5) should hold is rather non-obvious - this is because while the variable (Z, () f (x+)
f(
Fi-1 is mean-zero, it is subExponential rather than subGaussian. In fact, even in the subGaussian case, given a sequence of random vectors To,... 1t-1. such that each B Fr-1]
O, and
that each x, F is sura-sub with parameter a, E F_ (which is an appropriate generalization of subGaussianity for vectors, proposed in Jin al. (2019b)) proving concentration
|E 2. Ô (v E= is very delicate matter. In our case, the analogue of x, is (1 - (.o2,-1)(VVaa. [)(v((z)) fxxx))) while the analogue of o2 is (1 + (1+m)) F () -V((;))) F- Existing techniques (cf. Tropp ct al. 2015); Jin et al. (2019b) rely crucially on subGaussian properties that allow for each the moment- -oonent-generating function OY F, to be defined for any fixed (and non-random) 0 > where Y, takes the form
inequality of the form
0
Y.
such that B[Y, [F-1]= = (since E[x, Fy-1] = 0), and the eigenvalues Y, are + +| ||. In the case when x, is merely subExponential, the Moment Generating Function (MGF), EY F,-1], will no longer be well-defined at any fixed (and non-random) > This poses challenge in [)(f((z)) vf which is
setting, since x, takes the form (I (2, subExponential rather than subGaussian. While it may be possible to force - H (Z, (2,
f(())(=;) (f(()) to be Bab-Gaussian, say by normalizing Z, to have norm vd (note any
Foor general S d, there will also he (11/m) dependence in the sample complexity.
8

---

Under review as a conference paper at ICLR 2023
bounded random vector is also subGaussian), such that [ -)g -g I & 2 for any vector
g E Rdd a careful examination of the argument in Proposition 5 would show that this results in a O(P)) rather than ((d) dependence in the sample complexity, incurring a heavy price on the overall sample complexity (extra factor d) if d large.
Our solution To overcome the issue, we build on the following observation: with high probability, for any vector g E Rdd, [ g is bounded within some log factor of |[g||- On the event [ g ((199))). }. the variable
1)g (, -1g
1111-1 -9
behaves approximately like a subGaussian random vector since Z, N(,, La). Based on this intuition, after some careful analysis, we can show that ZZ ()(V)(())) subGaussian on the event that Z fz(z)) is bounded within some log factor of [ )l. which happens with high probability. This then allows to show that this event, the corresponding MGF well-defined for all fixed 0 > 0, enabling us to prove a concentration inequality of the form Eq. ( This intuition is crystallized in the following proposition, which proves more general bound than what we strictly need. For notational simplicity, we introduce the function Ir(x) == log (I log(z)). Proposition 2. Let Ft, 1 2 -1 be filtration. Let (Ze)z20 be sequence of random vectors following the distribution N (O, 1) such that Ze E Fr and independent of Ft-1, and let (Ux (22 be a sequence of random vectors such that Us E Fi-1- For each T 2 0, let
Fr-1 | is
W
MAZZZ, - 1)es,
where each Mg is deterministic matrix of appropriate dimension. Then, there exist some absolute constants d', >> such that for any T zt and â E (0, 1/e], the the following statements hold:
For any > 0, with probability at least we have
|W S d0 Σ M1B3 1 log(Cdr/O)
2. For any B > b with probability least 8.
either Σ
M. [MBBd((CCT/))))
1=0
} (log(Crd/0) + log(log(B/b) + 1)) IIM |1
or [W
max
Moreover, as is clear from the bounds above, we may pick C 2 1 such that log (g) 2 1, A5 E (0, 21-
With this result, along with a series of other technical results in Appendix E.3 we can show that the algorithm makes function decrease of F with 211) probability near an (-aadlee point (Propo- sition 5in Appendix E.3). Armed with Proposition 5 as well as Proposition [ the main result in Theorem [ then follows. The complete detailed analysis can be found in Appendix (Escaping saddle point) and Appendix l (main result).
4 CONCLUSION
In this paper, we proved that using two function evaluations per iteration suffices to escape saddle points and reach approximate second order stationary points efficiently in zeroth-order optimization. Along the way, we gave the first analysis of hiihhhioobbbele probability function change using two(or more) moint zeroth-order gradient estimators, as well as a novel concentration bound for sums of subExponential (but not subGaussian) vectors which are each the products of Gaussian vectors. These technical contributions may be independent interest to researchers working in zeroth-order optimization as well as general stochastic optimization. There are few limits of the current results which lead to several interesting future directions, such as extension to noisy function evaluations, as well as studying if some zeroth-order estimators such asymmetric two-point estimators (Nesterov and Spokoiny] (017) or single-pone estimators (Flaxman et al. 2005) could actually escape saddle points without additional perturbation noise.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Adolphs, L.. Daneshmand, H., Lucchi, A., and Hofmann, T. (2019), Local saddle point optimization: A curvature exploitation approach. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 485-495. PMLR.
Antonakopoulos. K., Mertikopoulos, P., Piliouras, G., and Wang. X. (2022). Adagrad avoids saddle points. In International Conference on Machine Learning, pages 731-771. PMLR.
Avdiukhin, D., Jin, C., and Yaroslavtsev, G. (2019). Escaping saddle points with inequality constraints via noisy sticky projected gradient descent. In 11th Annual Workshop on Optimization for Machine Learning.
Avdiukhin, D. and Yaroslavtsev, G. (2021). Escaping saddle points with compressed sgd. Advances in Neural Information Processing Systems, 34:10273-10284.
Bai, Q., Agarwal, M., and Aggarwal, V. (2020). Escaping saddle points for zeroth-order non-convex optimization using estimated gradient descent. In 2020 54th Annual Conference on Information Sciences and Systems (CISS), pages 1-6. IEEE.
Balasubramanian, K. and Ghadimi, S. (2022). Zeroth-order nonconvex stochastic optimization: Handling constraints, high dimensionalityy and saddle points. Foundations of Computational Mathematics, 22(1):35-76.
Chen, P.-.,, Zhang, H., Sharma, Y., Yi, J., and Hsieh, C.-J. (2017). 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.
Chen, Y., Bernstein, A., Devraj, A., and Meyn, S. (2020). Model-free primal-dual methods for network optimization with application to real-time optimal power flow. In 2020 American Control Conference (ACC), pages 3140-3147. IEEE.
Criscitiello, C. and Boumal, N. (2019). Efficiently escaping saddle points on manifolds. Advances in Neural Information Processing Systems, 32.
Daneshmand, H., Kohler, J., Lucchi, A., and Hofmann, (2018). Escaping saddles with stochastic gradients. In International Conference on Machine Learning, pages 1155-1164, PMLR.
Du, S. S., Jin, C., Lee, J. D., Jordan, M. I., Singh, A., and Poczos, B. (2017). Gradient descent can take exponential time to escape saddle points. In Advances in neural information processing systems, pages 1067-1077.
Duchi, J. C.. Jordan, convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, (5):27888--28 28066.
M. L., Wainwright, M. J., and Wibisono, A. (2015). Optimal rates for zero-order
Fang. C., Lin, Z., and Zhang. T. (2019). Sharp analysis for nonconvex sgd escaping from saddle points. In Conference on Learning Theory, pages 119--1234. PMLR.
Flaxman, A. D., Kalai, A. T., and McMahan, H. B. (2005). Online convex optimization in the bandit setting: gradient descent without gradient. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. pages 385-394.
Ge, R., Huang, F., Jin, C., and Yuan, Y. (2015). Escaping from saddle points-onling stochastic gradient for tensor decomposition. In Conference on Learning Theory, pages 747-
Ge. R., Li, Z., Wang, W. and Wang, X. (2019). Stabilized svrg: Simple variance reduction for nonconvex optimization. In Conference on learning theory, pages 1394-1448, PMLR.
Han, A. and Gao, J. (2020). Escape saddle points faster on manifolds via perturbed riemannian stochastic recursive gradient. arXiv preprint 2..::2000.1219/1
Huang, M. (2021). Escaping saddle points for nonsmooth weakly convex functions via perturbed proximal algorithms. arXiv preprint arXiv:2102.028877
10

---

Under review as a conference paper at ICLR 2023
Huang, M., Ji. K., Ma, S., and Lai, L. (2022). Efficiently escaping saddle points in bilevel optimization. arXiv preprint arXiv:2202.03662
Jin, C., Ge, R., Netrapalli, P., Kakade, S. M., and Jordan, M. I. (2017). How to escape saddle points efficiently. In International Conference on Machine Learning, pages 1724-1732. PMLR.
Jin, C., Netrapalli, P., Ge, R., Kakade, S. M., and Jordan, M. I. (2019a). On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. arXiv preprint urXiv: 04
Jin, C., Netrapalli, P., Ge, R., Kakade, S. M., and Jordan, M. I. (2019b). A short note on concentration inequalities for random vectors with subgaussian norm. arXiv preprint arXiv:
Jin, C., Netrapalli, P., and Jordan, M. I. (2018), Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference On Learning Theory, pages 1042-1085. PMLR.
Larson, J., Menickelly, M., and Wild, S. M. (2019). Derivative-free optimization methods. Acta Numerica, 28:287 404.
Lee, J. D., Panageas, I., Piliouras, G., Simchowitz, M., Jordan, M. I., and Recht, B. (2019). First-order methods almost always avoid strict saddle points. Mathematical programming, 176(1):311-35)
Li, J., Balasubramanian, K., and Ma, S. (2022). Stochastic zeroth-order riemannian derivative estimation and optimization. Mathematics of Operations Research.
Li, Y., Tang, Y., Zhang, R., and Li, N. (2021). Distributed reinforcement learning for decentralized linear quadratic control: A derivative-free policy optimization approach. IEEE Transactions on Automatic Control.
Li, Z. (2019). Ssrgd: Simple stochastic recursive gradient descent for escaping saddle points. Advances in Neural Information Processing Systems, 32.
Liang, G., Tong, Q., Zhu, C., and Bi, J. (2021). Escaping saddle points with stochastically controlled stochastic gradient methods. arXiv preprint arXiv:2103.00 04413..
Lucchi, A., Orvieto, A., and Solomou, A. (2021). On the second-order convergence properties of random search methods. Advances in Neural Information Processing Systems, 144255333-26455
Malik, D., Pananjady, A., Bhatia, K., Khamaru, K., Bartlett, P., and Wainwright, M. (2019). Derivative- free methods for policy optimization: Guarantees for linear quadratic systems. In The 22nd international conference on artificial intelligence and statistics, pages 2916-2925. PMLR.
Mokhtari, A., Ozdaglar, A., and Jadbabaie, A. (2018). Escaping saddle points in constrained optimization. Advances in Neural Information Processing Systems, 31.
Nesterov, Y. and Spokoiny, V. (2017). Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):277-566.
Panageas, I., Piliouras, G., and Wang, X. (2019). First-order methods almost always avoid saddle points: The case of vanishing step-sizes. Advances Neural Information Processing Systems, 32.
Reddi, S., Zaheer, M. Sra, S., Poczos, B., Bach, F., Salakhutdinov, R., and Smola, A. (2018). A generic approach for escaping saddle points. In International conference on artificial intelligence and statistics, pages 1233-1242. PMLR.
Roy, A.,
Balasubramanian, K., Ghadimi, S., and Mohapatra, P. (2020). Escaping saddle-point faster under interpolation-like conditions. Advances in Neural Information Processing Systems, 33:12414-12425.
Shamir, O. (2017). An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. The Journal of Machine Learning Research, 1803):1703
Staib, M., Reddi, S., Kale, S., Kumar, S., and Sra. S. (2019). Escaping saddle points with adaptive gradient methods. In International Conference Machine Learning, pages 5956-5965. PMLR.

---

Under review as a conference paper at ICLR 2023
Sun, J., Qu, Q., and Wright, J. (2015). When are nonconvex problems not scary? arXiv preprint 1rX.v:1510.06096
Sun, T., Li, D., Quan, Z., Jiang, H., Li, S., and Dou, Y. (2019a). Heavy-ball algorithms always escape saddle points. arXiv preprint NE4i::1907.09699
Sun, Flammarion, N., and Fazel, M. (2019b). Escaping from saddle points on riemannian manifolds. Advances in Neural Information Processing Systems, 32.
Tang, H., Lian, X., Qiu, S., Yuan, L.,, Zhang, C.,, Zhang, T., and Liu. J. (2019). Deepsqueeze: Parallel stochastic gradient descent with double-pare pass compensamedd compression. arXiv preprint OrXiv:/907.07:::
Tang, Y., Ren, Z., and Li, N. (2020a). Zeroth-order feedback optimization for cooperative multi-agent systems. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 3649-3656, IEEE,
Tang. Y., Zhang, J., and Li, N. (2020b). Distributed sero-order algorithms for nonconvex multiagent optimization. IEEE Transactions on Control of Network Systems, 8(1):269-281.
Tropp, J. A. et al. (2015), An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-230.
Vershynin, R. (2018). High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press.
Vladimirova, M., Girard, S., Nguyen, H., and Arbel, J. (2020). Sub-weibull distributions: Generaliz ing sub-gaussian and sub-exponential properties heavier tailed distributions. Stat, 9(1)=e31.
Vlaski, S. and Sayed, A. H. (2021a). Distributed learning non-convex enviromments part Polynomial escape from saddle-points IEEE Transactions Signal Processing, 69: 19:1227-1270.
Vlaski, S. and Sayed, A. H. (2021b). Second-order guarantees of stochastic gradient descent in non-convex optimization. IEEE Transactions on Automatic Control.
Tlatakis-Gkaragkouiis E.-V., Flokas, L., and Piliouras, G. (2019). Efficiently avoiding saddle points with zero order methods: No gradients required. Advances in Neural Information Processing Systems, 32.
Wang, J.-K., Lin, C.-H., and Abernethy, J. (2021). Escaping saddle points faster with stochastic momentum. arXiv preprint 2XXi:2206600295.
Xu, Y., Jin, R., and Yang, T. (2018). First-order stochastic algorithms for escaping from saddle points in almost linear time. Advances in neural information processing systems, 31.
Zhang, C. and Li, T. (2021). Escape saddle points by a simple gradient-descent based algorithm. Advances in Neural Informtionn Processing Systems, 34:8545-8553
Zhang, H., Xiong, H., and Gu, B. (2022). Zeroth-order negative curvature finding: Escaping saddle points without gradients. arXiv preprint arXiv:2210.01496.
Ziyin, L.,, Li, B., Simon, J. B., and Ueda, M. (2021). Sgd with a constant large learning rate can converge to local maxima. arXiv preprint ar arXiv:2107.11772
12

---

Under review as a conference paper at ICLR 2023
A RELATED WORK
Two-point methods in zeroth-order optimization. Two-point (or in general 2m--oint, where 1 S < d with d being the problem dimension) estimators, which approximate the gradient using two (or 2m) function evaluations per iteration, have been widely studied by researchers in the zeroth- order optimization literature, in convex (Nesterov and Spokoiny| 2017: Duchi et al. 2015 Shamir 2017). nonconvex (Nesterov and Spokoiny 2017), online (Shamir 2017). as well as distributed settings (Tang et al. 2019). A key reason for doing so is that for applications of zeroth-order
optimization arising in robotics (Li et al. 2022), wind farms (Tang et al.) (220a), power systems
2020). online Sime-varying) optimization (Shamir 2017). learning- based control (Malik) ctt al. 2019 Li et al. 2021), and improving adversarial robustness to black-box attacks in deep neural networks CChnn et al. 2017). ) it may be costly or impractical to wait for ((d) (where d denotes the problem dimension) function evaluations per iteration to make step. This is especially true for high-dimensional and/or time-varying problems. Indeed, for high-dimensional problems, two-point estimators can make swift progress even in the initial stage compared 2d-point estimator, and can reach a higher-quality solution if computation is limited ( (Tang et al. 2020b Chen et al., (0077). For instance, consider the work in (Chen et al. 2017). which studies the use of zeroth-order estimators to perform black-box attacks on deep neural networks, in order to identify (and then defend against) adversarial images that may lead to misclassification.
(Chen et al.
the paper, the authors employed two-point zeroth-order estimators, due to the high computational cost of using 2d function evaluations per iteration for hundreds of iterations (here dl is the dimension of an image, which in this case is over 20000). The authors showed empirically that their two-point estimators worked well: however there over no accompanying theoretical results.
For online or time-varying environments, two-points estimators also often preferable. Since zeroth- order methods are often used in physical systems whose environment drifts or changes over time, this leads naturally to time-varying or online optimization. For these problems, 2d 2d-point estimators will not produce a good estimation because the underlying function can drift to a very different problem while waiting for the 2d function evaluations. Indeed, the fewer function evaluations an optimization procedure needs, the faster it can catch up with the time-varying environment. In fact, for online optimization. it has been shown that two points estimator is optimal for convex Lipschitz functions (Shamir (017). Thus, two-point estimators are a natural fit for time-varying online optimization problems.
Saddle point escape with access to deterministic gradient. While standard gradient descent can escape saddle points asymptotically (Lee et al.) 2019 Panageas et al.) 2019). is known that standard gradient descent may take exponential time to escape saddle points (Du et al. (017)) Hence, when access to deterministic gradient is available, research has centered on escaping saddle points with adding perturbation (Jin et al. (017). momentum/accceleattinn based methods (Jin et al., 2018 Sun cet al. 2019a; [taabb et al. 2019), or cradient-based robust Hessian power/curvature exploitation methods (Zhang and Li 2021 Adolphs et al. 2019). In addition, there has also been work on escaping saddle points devoted to specific optimization settings, such as constrained optimization (Mokhtari et al. 2018 Avdiukhin et al.) 2019), optimization of weakly convex functions (Huang 2021), bilevel optimization (Huang et al. 2022), as well as on general manifolds (Sun et al. 2019b
Criscitiello and Boumal 2019 Han and Gao 2020).
Saddle point escape in stochastic gradient descent (SGD). In practice, only stochastic gradient estimators are available in many problems. While SGD may converge local maxima in worst-case scenarios ZZyin et al., (02T)) under assumptions such as bounded variance or subGaussian noise, there have been many works that have studied the problem of saddle point escape in SGD (Ge et al., 2015 Daneshmand et al. 20188) Xu et al.) 2018 JTn et al.] 2019a] Vlaski and Sayed 20216). The best existing rate (without considering momentum/vvrianne of Fang et al. 2019)) which converges to e-second order stationary points using (11/ 3-300) stochastic gradients. While zeroth-order gradient estimators may also be viewed as stochastic gradients, they typically do not satisfy the bounded/subGauseee
reduction techniques) appears to belong to that
noise assumptions that are assumed in these works, making a direct comparison inappropriate. Escaping saddle point via momentum methods in SGD has also been studied ( (Wang et al. 202T Antonakopoolos et al. 2022); 3 while we do not consider incorporating momentum in our works, this may be interesting future work. A number of papers has also considered the specialized setting of escaping saddle points in nonconvex finite-sum optimization (Reddi et al. 2018 Liang al. 2021), with many considering the case where variance-reduction is
13

---

Under review as a conference paper at ICLR 2023
used (Ge et al. 2019 Li 2019). While the finite-sum problem is quite different from our problem, the variance reduction approach considered in these works may be a relevant future direction. The saddle point escape problem has also been studied in other specific settings such compressed optimization (Avdiukhin and Yaroslavtsev 2021), distributed optimization (llakki and Sayed (021a), or in the
overparameteriization case (Roy al. 2020).
Saddle point escape with zeroth-order information. The problem of escaping saddle points in zeroth-order optimization has been studied less often, and we have already listed all known works comparable to our work in the introduction (Bai et al. 2020; Vlatakis- Saaakii-Gaaaakkount et al., 2019) Balasubramanian and Ghadimi 2022); more detailed comparison of these works with our results
has been provided in the discussion following the statement of our main result Theorem [ We would
like to mention that Roy et al. (2020) also includes a convergence result of Ô 11.0
for the case with
noisy function evaluations, which incomparable to existing work which focuses the case with exact function evaluation. In addition, |Roy et al. (2020) also makes a subGaussian assumption on the estimator noise, which zeroth-order estimators in our paper do not satisfy. Nonetheless, considering the extension to noisy function evaluations will make for important future work.
Zeroth-order optimization. Our work rests on line of research zeroth-order optimization which focuses on constructing gradient estimators using zeroth-order function values (Flaxman et al. 20055 Duchi al. 2015 Nesterov and Spokoiny 2017, [Shamir 2017 Larson et al.) 2019). As we have discussed, for smooth nonconvex functions, it is known that two-poin ero-poonn zeroth-order estimators suffice to find first-order e-stationary points using (dde²) function evaluations (Nesterov and Spokoiny 2017). Our work studies the more complicated problem of reaching e-second order stationary points, attaining a rate of (d)e2.))
B PROOF ROADMAP
We begin by introducing several key concentration inequalities in Appendix C which we will frequently use in our proofs. We then describe in detail (and prove) the sequence of results that lead up Proposition 4 in Appendix D showing that there cannot be too many iterations with large gradients. Next, we describe the saddle point argument in detail, and prove Proposition D in Appendix E.3 Finally, we combine these results and prove our main result Theorem 2 (whose informal version is Theorem in Appendix
Throughout our proofs, absolute constants, as denoted by e.g. d C),, may change from line to line. However, within the same proof, for clarity, we try to index different constants differently. We assume 2 and m S d.
Notations.
We shall denote the conditional expectation and conditional probability by Eyl: E[- Fl and (.) = -P(, (F) where F is a sigma-algebra.
C CONCENTRATION INEQUALITIES
This section serves to introduce several probabilistic results which will be useful for our main proofs in subsequent sections. We first introduce subGaussian, subExponential and norm-subGaussian random vectors in Appendix C.I Next, in Appendix C.2 we provide concentration bounds for norm- subGaussian and subExponential random vectors. We then prove novel concentration inequality involving products of subGaussian random vectors in Appendix C.3 We conclude by stating some
concentration bounds for Appendix C.4 random variables.
C. SUBGAUSSIAN, SUBEXPONENTIN AND NORM-SUBGAUSSIAN RANDOM VECTORS
We first define subGaussian and subExponential random vectors. A detailed reference for these concepts can be found in Vershynin (2018).
Definition 5 (subGaussian and subExponential random vectors). A random vector Rd is a-subGaussian (SG(o)), if there exists > 0 such that for any unit vector g E Sd-1,
E (exp(A(gg E(>]))] exp(A2o²/2) V.ER. R.
14

---

Under review as a conference paper at ICLR 2023
Meanwhile, a random vector Rd is o-subExponential (SE(o)), if there exists > 0 such that for any unit vector g E gd-1
(xxp(Agg x B[x]))] V exp(>2o2/2) =
An alternative concentration property for random vectors revolving around its norm, known as corm-suuhaaussiantty (Jin al. 2019b), is also relevant.
Definition 6 (norm-subGausian random vectors). A random vector æ E Rd is o-norm-subGaausiann (nSG(rr)) there exists a > such that
P[| Ex! 8)
S 2e 2n S. 0.
We recall the following result which provides several examples of nSG random vectors, In particular, tells random vector Rd that is (a/ Subbaasannn is also o-subGaussian.
Lemma 4 (Lemma in Jin et al. (201b)). There exists absolute constant such that the following random vectors are all coG
1. A bounded random vector Rd that || S
2. A random vector a: E Rd, where = Gee and the random variable & E R is o-subGaussian.
3. A random vector Rd that is (a/Va) (u))ssssbuussica
In addition, if x E Rd is zero-mean nSG(a), its component along single direction is also subGaus- sian.
Lemma 5. Suppose Bd is zero-mean nSG(o)). Then, for any fixed vector Rd (v, x) is zero-mean suloo-aassaasinn
Proof. Without loss of generality, we assume that gd-1 is unit vector. That (0, a)) is zero-mean follows directly from æ being zero-mean and being fixed. Meanwhile, since (v, æx) S || ||=||, for any s 2 0, it follows that
P((uv, x>) 2 < |P[[|=]|| 2 2) 2e
where the last inequality follows from the fact that zero-mean and also nSG(o). Hence (v, a)) is zero-mean SG(o), as desired.
C.2 CONCENTRATION BOUNDS FOR NORM- SORM-SUBGAUSSIAN AND SUBEXPONENTIAL RANDOM VECTORS
We begin by giving concentration bounds for norn-subGaussian random vectors. To do so, introduce the following condition.
Condition 1. Consider random vectors , Fn Rdd and corresponding fillattion Fs generated by (Z),..., I.). We assume æ; Fi- is zero-mean, nSG(a;;) with o; E Fi-1, i.e,
E [c F=-1]=
and
[[ F(-1) < 2e 2-? Vs 2 0,
where is measurable function of (æ -i 1) for each i.
For norm subGaussian random vectors satisfying Condition [
we first have the following bound.
Lemma 6. Suppose (æ1...., vn)) E Rd satisfy Condition 7 i.e. each æ; F,-1 is mean-zero. nSG(o,) with o; E F, Let {u:} denote a sequence of random vectors such that u, E F; for every E [n]. Then, there exists absolute constant c, such that for any 8 E (0, 1) and X > 0, with probability at least 8,
Ui x.)) $ cA Σ
24 12
log(1/5).
15

---

Under review as a conference paper at ICLR 2023
Proof. We note that if 2; is mean-zero and nSG(o,)) then by Lemma (u,, x., and u; sullllssSuaaaasiaann The rest of the proof follows from the proof Lemma 39 in Jii et al. (2019a) (key idea exponentiate and then apply Markov's inequality). For completeness,
F is zero- zero-mean
restate the proof here. Observe that for any i, since (u; is ||u Susuaassann for any > 0, we have that
E [Cx;, 2i)) [i-1 & exp(>2|lu:l1
For any À > O and 2 O, observe that
a
X Xuui 2..) - >211ee11 1// 02/222
exp
U, x.) >²1lu:11 :l//o??22222
2 exp(ds)
exp
Ue x.)) - X2|u,l1 x2uu110o?/? 0?/22
exp(->o)
U₁ x²) >311ue11 0312
|Fa-1
exp
E
exp
Un xi) - 2211ui11 E [exp (A(un) an) - 2211eenli ( F exp(-1s)
1=1
E
exp
un ax)) - 2211,,11202 02/22 /2 exp(- (88) ... S.. eexp(-As)
t=1
Above,
ii follows from the fact that (u, xx.) [F,-1 is zero-mean and llllllllluuuuiteteee subGaussian for each The final result then follows by picking 1/ and log((/8).
[n].
Assuming Condition 1 the following concentration result also holds for sequence of nSG random vectors.
Lemma 7 (Lemma 6, Corollary 7 and Corollary in Jin et al. (019b) combined). Suppose (x1,... ).,) E Rdd satisfy Condition 7 Then, there exists an absolute constant such that for any fixed (0, 1). 0 0, with probability at least -6, 5,
< c0
of + 0
log(2d/8).
1=1
Moreover, there are two corollaries.
1. ([Jin et al. 2019b Corollary 7)) When {az} is deterministic, there exists an absolute constant such that for any fixed â E (0, 1), with probability at least 8.
Σ x; Sc
log log(2d/8)
o
2. ([Jin et al. 2019h Corollary 8)) Suppose that the {a;} sequence is random. Then, there exists an absolute constant e such that for any fixed â (0,1) and probability at least 1 1-60 ö:
> 0, with
either Σ
2 or Σ æ;
2
Sc
max
oo (log(2d/6) + log(log BB/b))
We state here a Bernstein trrnstein-typeeee concentration inequality for sub-exponential random variables, which also need.
16

---

Under review as a conference paper at ICLR 2023
Lemma 8 (Bernstein concentration inequality). Consider sequence of independently distributed o-subexponential variables #1, 21...., In E R, with mean E|æ,] I co for some d' >> and each
i E [n]. Then, there exists absolute constant C' > O, such that for any (0, 1), with probability at least 5,
n
2; S Co(n + log(1/6))
(6)
Proof. The result of Eq. 6 follows by applying Bernstein's inequality to > 2i- 2;
E
a (so each
summand is mean-zerr zeroo.. Per Bernstein's 's inequality, (cf. Theorem 2.8.1 in Vershynin 2018 ) there exists an absolute constant e > 0 such that for any 2 0,
a E(x,)) 2 8 S exp (-omin ( 8² =
no? )
I
Σ
Pick (n (n+ 1og(1/6) Then,
min 52 min
{ n + log(1/0) (log(1/8))
c'n n nn+ log(1/6) ) + log(1/6)
no?
c
c
Continuing, we have that
P
Σ x -x.-E<a 2 S exp
(-emin
! : s exp -c (-o(1) n 1og(1/0) )) S 8.
82
Thus, it follows that with probability at least 1 -
log(1/0)
Σ x, 5 n log(1/0)
Σ -
+ nn'a
where implication holds since by assumption, E[x,] S c'o for some e' > 0. Then, by setting C = max(1 d', 1/c), the desired result follows.
C.3 A NOVEL CONCENTRATIO INEQUALITY FOR THE ZEROTH-ORDER SETTING
In the zeroth-order setting, will frequently have to bound the norms of terms of the form
W,
M(ZZ, - T)o,,
t=0
where M, is known and fixed quantity, while Z4 is random, and i depends 2o and the history of previous 1-11, 12,) s, and is hence measuuuale For our purposes, it suffices to consider Z; ~ N(0, I).
To see why such a bound will be useful, as mentioned in the main text and we will see again later in the full proofs. in the analysis of escaping saddle points, we need to bound a term of the form
W 9o (T) = EU-n) (()) - f(())))
where = (2 (assuming that zy is an c-saddle point), and x, and 2 are two coupled sequences.
Comparing with Eq. 77, we see that for the equation above, we can define M, = 1 nH) --
(a fixed and known quantity) and v, = Vx(x)) - V (clearly, V f((x)) V ((x() is F,-1-
measurable). This motivates why we wish to bound terms of the form Eq.
Observe that each (2,7, - T)e, F term subExponential rather than subGaussian. While is possible to define norm-subEx comm-subExponetiaz vectors in analogous way to norm-subGaussian vectors, the corresponding moment generating function (MGF) for subExponential random variables is not defined on the entirety of IR. When bounding a sum in the form (Z,2, - I)u,, this creates subtle but challenging technical issue.
17

---

Under review as a conference paper at ICLR 2023
Following the intuition outlined in the main text, we bypass this difficulty by proving the following result. For notational simplicity, we introduce the function
Ir(x) = log (z: log(2)).
(8)
We now recall Proposition which we first introduced the main text.
Proposition 2. Let Ft. t 2 -1 be filtration. Let (Zi)t2 be a sequence of random vectors following the distribution N (0, I) such that Ze E Fe and independent of Fi-1, and let (Vi)e20 be a sequence of random vectors such that Ut E Ft-1. For each t 2 let
W Σ MelZiz 1)us,
where each M2 is deterministic matrix of appropriate dimension. Then, there exist some absolute constants such that for any T Zt and â E (0, 1/e), the following statements hold:
1. For any > O, with probability at least - we have
IW S do Σ [110300r0C//0000) log(Cdr/
For any B > > O, with probability least
T-1
either
M. IMI13 B
1=0
Σ II
[AA ) (log(Crd/0) + log(log(B/b) + 1))
max
Moreover, as is clear from the bounds above, may pick C 2 1 such that log (g) 1, Aa E (0, d.
Proof. We will focus on proving the first point, since the second follows as a natural corollary of our proof of the first part and the proof of (Jin al., 2019b] Corollary 8). For simplicity, we shall assume Ve F O in the intermediate steps; extension to the general case is straightforward.
First of all, for 0 I
let
g(a: 8) = --/2 -
2 (21())))
(x² - 1)e 1)e- 12/2 dx =
2 π
ae a2 8
8 21r(1/8)
V
(g((1))
It's not hard to see that for a fixed E 1/e). g(a; 8) is continuous and strictly increasing over E [0, 1). Then, since log + S x for x 2 1, by plugging in a = (og() we get
Ir(1/6) log log(1/)) log(1/6) (log(1/8))²
log log (1/8)
1 1,
(log(1/8))²
log(1/6)
(og((10))
which leads
8 2 (1(0/
2
g(26:
28e
2e
2/0²
6 V28
> 0
log (1 1/5)
for 8 E (0, 1/e]. Furthermore, we obviously have (0; 8) < 0. Therefore g(a; 8) 0 has unique solution in (0, 28), which we denote by (d) These results imply that, for a random variable Z following the standard normal distribution, have
2
211(118)
E (
1)1 20055
((8)
By letting Wa(z)) denote the the principal branch of the Lambert W function, it can be shown that
28 1r(1/5)
a(8)=
Wo
(log(1/6))
18

---

Under review as a conference paper at ICLR 2023
and
00
(a())
P(((0) - 12 (21r(1/)) 21 -
12 dx +
- dx
V2T
221((1/6)
V2T J0
21r(1/0)
a(6)
a(d)
2 1 - 2
2
exp
2
V2T
= 1 2
21og (1/8)
V2n
8
21-2 2
2 21 - C6
2
2T
for any 8 E (0, 1/e]. where we define the absolute constant C =
Now let A, denote the event
ZTTr |evel
A = a()) I
I /21r(118)
Since Z, ///l/o// conditioned on F.-1 follows the standard normal distribution, have
(A.) 2 -5
and
Ex,-1 [v]] (ZeZg 1) 1/ A. 0.
Moreover, for any random vector u E Fi-1 that is orthogonal to Ut, we have
Ey. [u (z 1) 01 A.l Ey. 1u Ze] Ey, 2 v2 AA = 0,
where we used the fact that Z is independent of Z,_ U2 conditioned F.-1. Therefore Ex, [Z, T)ee1 A.] =0
Consider defining then the random variable Q₂ by
Q: = (Z,Z, D)ut 1A.
We now show that Q2 F
norm-subGauusian Let u E Rd with ||u]| = be arbitrary. We have
u TTQ =u- (Z,Z,
I)u 14,
T
U2
+
(Z,Z, -1) 1A
|1 1|
|
12 12/2
1A. + (1-110)12
u Te
||0.
1
(1:11 ||:011
(Z,Z, - -Nyr 1A
12, ve 12
-u- m
1 + u 7.77, U1 AA,
||0:|1' 2|
where we denote 1.1
Tee. Teyl
Since
12, 0r 1
||: -1) IA, S o (21r(1/5) 1),
Vt
we see that u T ve Furthermore, since 10
12, v. - 1)
LA. conditioned on F is |u vy (2 ( 1) -usuuGauusnian.
u1 Zr 01 A.l 17, u1 w 20rl///rr)11llee/l
have
Py.-, (lu] 7,777
1 2 s) < P,. (Iz Tn 21/ 25)
and since Zeu |u
Fi-1 follows the standard normal distribution, we see that u 2,2, er
1A is
110)// |u ||1|v subGaussian variable. Note that TTQ Qu is just the sum of /2 2 (r(1)))
[Z] [
T0, - 1): 1. and u. Z.Z, Uo 1A, conclude that u Q2 is subGaussian with
parameter
(21r(1/8) 1) vel 221r(1/8) ||||a||
19

---

Under review as a conference paper at ICLR 2023
(Ir val + |lelllle|ll) 22221((1/0) / /ut vol2 2 + | ||
=2v21r(1/8][bul))
whenever 8 E (0, 1/el. Consequently, by (Jin et al. 2019b Lemma 1), we see that Q: F is 8Ir(1/6) vell norn-suGGaussian.
It follows easily that M,Q. FF-1 is mean-zero and
Hence, by (Jin et al. 2019a Lemma 6), we know that there exists an absolute constant e >> 0 such
that for any 0 and 0, we have that with probability least 1 8,
Σ M.Q
S cB Σ
d0r(1/6)))M1))1)
log(2)/)).
Now, consider denoting the event
T-1 = A = 11 Uel (a(0)]leell \2Ir(1/0)]looll)) Vt 70 13}
By the union bound and Eq. ( note that
P(A) 2 1-1166 TC6.
Moreover, note that on the event A, ΣE 1== M.Q. = EED (. -T)u,. Hence,
P
Σ Mc(ZZz
1)ue
c
d(Ir(1/8)) 11ee1 + log(2d/))
1
1 log(2d/0), and happens
2 P
Σ M,Y 200
Σ
dlr((/6)))11M 1 1 +
1 log(24/0) + P((9))
2
M,Y,
> c0
d(r(1/6))) M +
2 1 (6+
Now, by rescaling d to 6/(CT 1), we get the desired result. Note this C' is different from the C in the statement of the lemma by an absolute multiplicative factor.
C.4 SUB-WEIBH WEIBULL RANDOM VARIABLES
In our work, we occasionally require bounding sums of heavy-tailed distribution, e.g. higher powers of || where Z (0, I). To this end, we consider the following definition of sub-Weibull random variables.
Definition 7. We say that a random variable X E sub- Weibull( K, a:) for some K, a > O,
P[[ s) < 2exp(-(s/KK)// Vs
0.
For instance, the standard normal distribution is sub-Weit Weibull(1, 1). From the way we define the tail parameter the larger the a, the heavier the tail of the distribution.
In our work, we need show that the sum of nub-Weibull random variables is again sub- Weibull, which is ensured by the following result
Lemma 9, Suppose X and Y are sub- Weibull( Xx, a.) and Kebbbeibllllyyy a) respectively. Then, XY is sub- Weibull(C Ky), 2a) and X + Y is sub- Sabb-Weibull(( (Kx x + Ky), a) for some absolute constant C > O.
helpful result is the following, which bounds the sum of identically distributed sub- Weibull random variables.
20

---

Under review as a conference paper at ICLR 2023
Lemma 10 (Corollary 3.1 in Vladimirova al. (020)). Suppose X,, identically dis-
tributed (K', a) sub- Weibull random variables. 2 ncK', we have
Then, for some absolute constant e >> 0. for all
(-(reck))
1/a
X
28
Sexp
S exp
In work, frequently need bound sums of the k-th power of the norm of standard d- dimensional Gaussian. We do so using Lemma
Lemma 11. Suppose X, idd N(0, Ia) for E [n]. Then, for any l E Zz, there exists absolute constants C' 0 such that for any 8 (0, 1), with probability at least 1 6,
Σ 1 2h
s <nCe (log(1/8))))
In particular, for any 5 E (0, 1/e) such that log (1gg(/6)3 1, it follows that
Σ X,
S 2nCC 2n (log(1/)))
Proof. First, observe that for any j E [d]. (x.) being subExponential, is (1, 1)-subWeibull. Then, by Lemma - = Ej
(cd. 1) for some absolute constant e. Now, follows from _ k))-ubbeibuull Hence, applying definition of Lub-Weibullness in Definition 7 that ||=X,|| 2k is (c* d+
Lemma 10 we have that there exists absolute constant C > 0 such that for any 2 nC' d",
a
(-CrCcc 1/1
Σ
X
2k
28
S exp
D Choosing = (1 + (log(1 ( we arrive then at the desired result.
C.5 SUPERMARTINGALL CONCENTRATION INEQUALITIES
We first state and prove supermartingale-ty type concentration inequality of the form we later require. Lemma 12. Consider filtration of sigma-algebras Fo F C .... C Fn-1 C Fn and a sequence of random variables X1...., Xn, such that X, E Ft. Suppose that
P (Xi a) and
PF. (X, < -b) bb) 2p
(10)
for some a, and p }. Then, for any < s b such that | pl 2 1-p have
(a + p.)
we
n
82
X mi +
< exx
4n(b 11)2 )
V&>
Proof. Observe that by Markov's inequality, for any >> 0.
P
X mp +
=
P
exp
(X, + (1))
2 exp(As)
<
foxp (A (AE (X; + +))] exp(As)
2m
Now, observe that
E
exp
A >
(X,
+10)
E
E
exp
A (xx +
+
i=1
n-1
E
exp
A
Σ
(X, + u))
Ex lexp(AAX, + +
(I)
i=1
21

---

Under review as a conference paper at ICLR 2023
Let us now compute By, /eexp((Xx, -])l:
E E (exp(X(Xx + |1)]
(-00-)) exp(A(x + n4)) P (Xn, E dx) + / exp(A(x + -1) 1)) (X, E dx)
(-boo)
< Pr (Xn S -b) exp + u)) + PTn-1(-b- Xn S Sa) ex)exp(((+++)) nl)
$ pexp(A(-b+ + n)) + (1 p) exp ((a + =)).
Then observe that by choice of f., - + μ O, and that |-b+ 14| 2 (a + p1) P. Since assumed p < 2. this means that
1 2 and so for any k 2 1,
P
1-P I-b+ p 2 (a + p1)
1-b+ 11 2 (a 11)
1 --p)
1/k
= pl #1* 2 (1- p) + 10²²
p
p
Consequently, by Taylor expansion,
pexp(A(- + n)) + (1 exp +1)
(m(p( b+ μ¹*h + (1 (1a + )
0 X (p(p b + 11)*
b + kt
=+
1
k!
k1
k=1
2k 2p | + 2k
2k
b +
2k
< 1 +
(2k)
(k:)
k=1
1=1
exp(X (X2 ( )))
which leads to
By__, (exp(A(X, + +1)] S exp((2(-b+
Now, continuing from Eq.
we have that
E
exp
A 1=1
(X; + +1)
E
exp
A
[X: + 11)
EJ.-, 1 (exp(A(Xx + +1)1
i=1
exp(>?(b- -198
E
exp
x
Σ
(X; 11)
i=1
exp(nx2(b (b)+))))..
Thus, for any À > 0 and & 2 0,
n
E [exxp(AEE> (X, [1)))]
Σ
X, 2 ni -
exp(As)
exp(nx - 11)2 - As))
By finding the minimizing X, we find that
$2 4n(b 12)
P
Σ 2 S <exp
which completes the proof.
We will later require weakened form of supermartingale concentration inequality, as stated and proven below.
Proposition 3 (Weakened supermartingale concentration incquality). Consider a filtration of sigma- algebras Fo C FF.... C F, and sequence of random variables XI,..., Xn such that X; E F, Consider for each i E {1....,n) a bad set B, where 1B, E Fi-1 and suppose
PJ. (X,1 By S <a) =1
and Py. (XI1 bb) 2
22

---

Under review as a conference paper at ICLR 2023
for some b > 0 and 0 S p S 1/2. Then, for any 0 < μ S b such that 1-b+ pal 2 1-P have
(a + p)),
p
I exp (-An (<4n(b- (-An(b- n1)²
2
P
X, nu +
P(x, B.).
ss > 0.
Proof.
We define Qi = XiIBp.
We can then apply Lemma 12 and get
P
Σ Q nn - s exp
4n(b nt)
Since P (X; # Qi for some E [n]) S E, P(X; E B,), it follows that
-nu s Sexp ( (-ati-ntl-))) 11)2
8²
P
Σ
+
P(X: E B:).
1=1
which completes the proof.
D FUNCTION DECREASE IN LARGE GRADIENT REGIME
In this section, we show that sufficient function decrease can be made across the iterations with large gradients. We first restate and prove the function decrease lemma (Lemma I. first introduced in the main text. We then provide a detailed roadmap of our proof the subsequent discussion following the proof of Lemma !
Lemma 1 (Function decrease for batch zeroth-order optimization). Suppose at each time t, the algorithm performs the update step (with batch-size parameter 1 I S d)
It+1 = -1 (9 (x+) + X.).
where
((m) (xt) (xr)
Σ m 1=1
1
f(z + uZt.i) - fax :.Ze..s) Ze,ir
2u
where each Ze, is drawn i.i.d from N0, f), u > 0 is the smoothing radius, and Y, ~ N(0, =) with denoting the perturbation radius.
Then, there exist absolute constants C1 > 0, 2 such that, for any T E Z and T 2 r > 0, and 8 1/el, upon defining Hor (6) to be the event on which the inequality
r-1 m
m
+ ("+
2d
f(x+) - f())) s
Z
[f())))
m
log T
add [lg T
Thu p² d
+ TLm
8
T
+ n (a + nL) log
Lopapp
(3)
8
is satisfied (where = /8)). we have
((Ho,-(5)) 2 + 4)8
P(, 2 57'8
for any S
Proof. First, for each E (-1,... 7), define F, be the sigma-algebra generated by Zo.
(m . (Yo....,,, Y2).
Note that F-1 is the sigma-algebra generated only by xn-
23

---

Under review as a conference paper at ICLR 2023
By Taylor expansion, for any v R2, there exists E [0,1] such that f(x + v) f(x)
(Vf(z). + by V2f(2 + az) y. Therefore
f(z, + uZri)) - f(x ubtn)) = (VI(x), Zc,)) + u
2 Hi
2u
with
H V2 + ax, UZz,)
v2f(2 05. Bs,-uZyr.
2
for some aitt E [0, 11, and
Me+1 Tt 11
Σ
V((m)) + 2i He, + Ye
(12)
By the p-Hessian Lipschitz property of f, it follows that Nu. s splll Ze,ell
Observe that
L
f(1+11) S f1xe + 10,, - I4, (f(zz))
|241 xell?
(i)
1
1
fxx))
[fxx))
17
Z Vf(x)) -
m
m
2
1
Zr 2 ( +
" マ
Z 1 H Z..) + +Y,
2
(1)
Z (((xe)
u² uZ|Z,,, He, Ho,.H.,,...l
$ f(1))
Σ
Z ((x))) 1
m
m s=1
4
i=1
Ln²
1
Z
Z, T, V faas)
+ u²
m
Zi He, He,s
2
+41|8/1?
2
m
im1
(v)
S (1x1)
37
((x)) 2
n7² 2
u² u²p²11 11,
17 (((z)) Yi)
4m
4
1=1
iml
Lnd
22
Zr, 2,,, V (xxx)
u
p2|
Zr,111
+ 4 Y/1?
2
m
37
m
ZT, (+)\?
mu* p2
1
LnZutt p² m /Z,.el
4m
4mn
2m
Lnp
m
Ze Z. V.
(13)
m
Above, to derive (1) we used the L-smoothness of ʃ. To derive ii we used the expression for
(r141 - xx) shown in Eq. 12). To derive fii). we used the fact that ab S (a² + 122/2 for any
a, E Rzo, as well as two applications of the fact that ||a + b1] < 2(Ia]l2 + [[b]13) for any two vectors a, b E Rd. To derive div), we used the fact that Hr.| I pull Zy,il-
To continue from Eq. 13) first observe that we can rewrite
Z 2. ((x)) (2,, 1VV] (sx)),
so that
m Σ
Z.
2
Σ
1u (V)()))
+ +
m
i=1
i=!
24

---

Under review as a conference paper at ICLR 2023
Observe that we can apply the bound in Proposition to
f -1 and since Zr, is independent of Fi-1 for all i, we know there Exist absolute constants 6₁ > 0, C1 2 such that for any 8 (0, 1/c] and 0, with probability least 1 conditioned on Ft-
Σ
Z Mu - nV)(
< c
Σ
m
[ + 1
log(Cidm/0)
+ log log(Cidm//0) (14)
Moreover, since Ci 1, log(Cidm//t) / and 1r(Cimm/f))))) mm/) both are at least as long as d E (0, 1/e].
Observe that conditioned on F:-1, V (xz) is fixed. Hence, we can pick
/amd Ir(C)dm/0)] (
which is Fi-1 measurable, and plug it into Eq. (14) to find that the probability conditioned on Fi-1 of the following event
Σ 2, -
V (==)l
(15)
is at least 8. By taking the total expectation, it follows that the event has total probability at least 1 8. Thus, with probability least 8-
1
1 Σ
Ze 2,, VS
2
+ f
< 4c (Ir(C)ddmm)))) 18))3 d
[ + f(,))
S <e(()(C)dm) 00)) [
(16)
where the last inequality comes from the fact that Ir(C)dm/0) 2 1, our assumption at the outset of the appendix that 2 m, and denoting c2 == 4c1 + 2.
Denote the event Ho. (5) as the event that
37
C2d(Ir(C)dmm/ (5)3
f(x+) - f(x0)= v
Ze,a
((xa)) + Lnp
V (xx))
4m
t=
==1
n p²
Inpzu* p²
Z1,011 +
4m
2m
1=0
t=0 i=1
T-1
(V((z),, Y1)
+
2Lm
Σ |Y||
(17)
holds.
Now, continuing from Eq. 13 and using the bound in Eq. (6)). summing over the iterations from
t= 0 to T - 1. we find using the union bound that Ho, (6)) 2 1 1 IP Ho (6)) 2 1 - 78.
Now, by Lemma 6 for any E (0, 1), O, with probability least 1 8, there exists an absolute constant c3 > 0 such that
(Vf(E))) on
Σ
vf(x;))] + c3ar c3ar> log(1/8))
(18)
0=
Meanwhile, since Y, ~ N(O. (r2 /d)//))).....))))))))) || is sub-exponential with sub-exponential norm cr2 for some absolute constant e 0, and by Bernstein's inequality (Lemma 8) there exists some absolute constant C4 > 0 such that
Σ |xll < (Tr + log(1/8))
(19)
25

---

Under review as a conference paper at ICLR 2023
with probability at least - 8.
To bound Eiso Di=1 7e,ll and Σ E== 1Z,,, both sums of heavy tailed Gaussian
moments, use Lemma 11 which states that for any & Z and ó (0, (), with probability at least 1 6,
ΣΣ
71,ll S CsT d (log(1/6))*)
(20)
for some absolute constants Cs C6 > 0. As in the statement of the proof, using X = (r(Cddm/0) to ease the notation, denote the event that
[(x+) - ((ro) S
3n 4
Σ
V
[xxe)
+ (""
ceLnixa
V [(())))
1=0
1=
Tipu"p p²
1
log 1
+ 2
log c
+ +IInfu'p
cosfeat
+ 1/3ar 2c
log
Lap
holds as Ho.r
Plugging Eq.
T8
1.800 Eq. 19 and Eq. 20) into Eq. 17
by union bound, we see that
Ho.r (0) 2 (r' 4r 8 5 IP(Ho,+) 2 - (r + 4)6.
The final result then follows by rescaling to & and denoting c1 = max c3. 2c,, c / cgc
Outline of proof approach. Similar to the first-order setting, goal is to show that we can arrive at a contradiction f(Tr) < min, f(x) when there is large number of steps at which VV((x))] 2 e. Roughly speaking, Eq. (3) shows, need to prove lower bound of the form
T
m 2 (IADV 20 2 (2 ('+
m
Ia
T-1 Σ (()(())))?
Σ
(21)
m
for some a which is not too large (an example would be picking a such that it only scales loga- rithmically in the problem parameters). However, it is tricky to prove such lower-bound in the zeroth-order setting. In particular, for small batch-sizes m, 1
m Σm (xx)) could be small
even |/ fxx))) is large; this is because for each i E [m]. Zz, could have negligible component the V fx(x)) direction. This necessitates a more careful analysis to prove a bound similar to Eq. (1). We do so using the following approach.
1. Intuitively, whilst for each individual iteration 1, E Z (xx) /| could be small
even as || f || is large, small number of (consecutive) iterations {to. .......... to + tt with high probability, there will be at least one iteration t within (fo...., ... to + We formalize this intuition in Lemma 14 Thus, we consider breaking the time-steps into chunks where each chunk has I consecutive iterations.
}.. such
that 1 "0 I,,, (a,,,
2. Consider any such interval (lo...., la f 13. There are two cases to consider.
(a) The first case is when the gradient throughout all ły iterations is large enough to dominate the perturbation terms. Intuitively, in this case, it is not hard to see that given appropriate parameter choices, the gradient will change little throughout the ty iterations. In fact, as we formalize in Lemma 16 for appropriate choice of it and n, we can show that
1
2 Vf((x))) [Vf(2.)) < 2 v Vt E (to...., to + t, - 1).
26

---

Under review as a conference paper at ICLR 2023
As result, combined with point see that
fotts-1
Z
m
Thus, by choosing a and 17 judiciously, for such intervals, it is possible to show that
fotty-1
m
botey-1
Σ
Z
(x)))
2(IVS((>))))) 20
Σ
[V)(()))
m
toto
L
Ω ((=IVV
Thus, in these intervals, it is possible to obtain function improvement on the order of ( [Vx,))))
(b) The remaining case is when the gradient is small and dominated by the perturbation terms in any one of the l iterations. In this case, as we show in Lemma 17 for each of the ty iterations, the gradient will be small and on the same scale as the perturbation terms. In turn, by choosing r, and 7 appropriately, we can make the perturbation terms small. Thus, whilst these intervals may not contribute to function decrease, they also contribute little in the way of function increase.
3. When there are at least T/4 iterations with large gradient (i.e. [[+(())) 2 e), assuming i divides T, it follows that there are at least T T/(4t)) intervals of length iy where one iteration in the interval contains large gradient. By choosing u, and 17 appropriately such they are dominated by e, it is possible to show that with high probability, such an interval cannot belong to the second case above, and must instead be from the first case. Since [x+]() [ )ll for each & E {4o,.... to + f - }} in this case, and we know that one of the iterations has gradient with size at least e, it follows that we make function decrease progress of at least r){2(=?) for such intervals. By appropriately choosing 7), u and r to limit the effects the intervals of the second form, we can then show a contradiction of the form fIr) f". We demonstrate this formally in Proposition 4
We formalize our approach in the following series of results. First, for analytical convenience, prove the following result showing that for any the perturbation terms ||Y|]] and 1. Σ Z1," are bounded with high probability.
Lemma 13. There exists an absolute constant 03 > O such that, for any E N, the event
log(T/0) d and
m
T 2 log
G+(
|1 S c2r² [+
> 21,ll S d
m
has probability at least T for any 8 E 10.1
Proof. Noting that Y, ~ N(O, (r2/d))), by applying Bernstein's inequality (Lemma 8) it can be shown that with probability at least 8/T.
|| & eg22 (1 log(T/6)
d
where C3 > 0 is some absolute constant. Then by using Lemma I applying the union bound, and redefining the constant C3, we complete the proof.
Next, in Lemma 14 we show that in small number of iterations, with high probability, there exists some iteration & such that & Sm IZ,, v f(x)) 2 /
Lemma 14. There exists an absolute constant C2 2 1 such that, upon defining
(5( = C2 log
T
8>0 0,
27

---

Under review as a conference paper at ICLR 2023
and defining the event
totk-1
1 m
22 1
|
(6; =
m
t=
we have
8
P (B. (6: k)) 2 1-
T
for any ò E (0,1), to and k 2 ty(
Proof. Denote the event
Z (())) < [Vf(21))
Eg
Observe that, conditioned on Ft-1, the set of random variables [1][f(=)]] |2,,, (fz,))) are independent, mean-zero, and subexponential with subexponential norm S clV f(=))) for some absolute constant > O. Hence
Z v < [
P (Et) PA.-
i=1
P
Σ
- > m " [V((2)))))
$ exp (-c'm),
where c' is some positive absolute constant. Then, for any to, & N,
1
for every 16,,10 + k) [x))))
m
k-+
ko+
1 1g.
=
1g. Es [ Eigte-l
t=to
t=fo
exp(-c'm
E
1 E
.... S exp(-cmk)..
t=
Therefore, by letting 62 = max and
C2 m
T
$ 2 (6)
log
we get
1
8
Z
vf(d)
[x(;))] for every E [to, to + k))
m71
<
2
T
which completes the proof.
The term (5) will frequently appear in the proofs to come; in the sequel we denote
C2 T
(8)
log
8 (0,
(22)
m
where 02 2 1 is the absolute constant defined in Lemma We next show that with high probability, the norm difference term [ ff(x))) can be bounded in terms of [ and the perturbation terms ||Y|||--
14
H, (T, as well as
2m
28

---

Under review as a conference paper at ICLR 2023
Lemma 15. Define
[V (6)
Ac(5)=
+nL
Σ
Ze Zi H
Ze,
|
2m
(23)
where t (6) defined Eq. (22). and ler C1 2 be the corresponding absolute constants defined in Lemmal 1
Then there exists an absolute constant C₁ > 0 such that, whenever satisfies
nL (I((())mmI/0)
(24)
Vm
,
we have
P(A(0)) 2
for any d E (0,1/e] and Z+.
Proof. Since Vf is L-Lipschitz, following the zeroth-order update step, we see that
[V V fz,))l - L|| - xzll
(25)
= 1
Σ 2.
u
Zi H Zi, H,, + +Y/
(26)
2m
Now, it follows from Eq. (16) (with slight modification in the absolute constant terms since here the norm is not squared) that there exists some absolute constant C4 > such that for any E (0, 1/e]. we have that with probability at least - 8/", the event
m
Zi
((zz
c4 (((r(C(idn1/0)))
| fx.))l
171
Hence, continuing from Eq.
26 it follows that with probability at least 5/T.
(V - Vf())]
S 1nL [((I[C[idmI/0))12
[Z))) +
Ze, HHe Ze,b + +|xx|1|
2m
and by plugging in the condition Eq.
24
we see that the event
A. ( ff(x))l
ff
+ nL
u
Σ
Ze Z, He se.
+ +|xx|l|
}
2m
1=1
has probability at least 1 8/T.
We show now that if the norm of the gradient dominates the norm of the perturbation terms, and choose the step-size 7 sufficiently small, then in a small number of iterations, the norm of the gradient does not change very much. For notational simplicity, we denote the event
4 n t=
t2,
[V (t)(
Ze, Ze H Zi,i
+ |Xill
2
Lemma 16. Let 8 E (0, 1/e] and T zt be such that T > (8) + 1. Consider any positive integer by (6), and any to {O....,Ie T 1 Ez). Suppose 1) satisfies the condition Eq. 24)
Then, on the event
bott,-1
Eloo,
n
A1(0)
tg
we have
V.f(2))] [()())) & 21/()(=0)1
2
for all i fla....,4o + -1.. 1}.
29

---

Under review as a conference paper at ICLR 2023
Proof. By plugging
[ (tr(
2
Σ
2
H
Zr,
+111al1
(niuter-- Ac(6)). have
into the definition of A(()), that, the event E(to: fy
/ /
[V (
4t)
and consequently,
(1 (1- 4t5(o))
1
[ff(z))] [[ |V/tev) [+ 4lz(0)
/f((,))
which leads
(1
1
1-to
1 t-to
[f((z))] s [Vf()))] 1+ (
(6)
for all / E (lo,.... to + f. Then, since (1 + 1/(4x)) < 2 and (1 1/(4xx)) 2 1/2 for any 2 1, noting that 1'y (0) we get the desired result.
Conversely, in the following result, we show that in a small number of consecutive iterations, the gradient is smaller than the perturbation terms in any of the iterations, then for each of the iterations in this range, the gradient will be small and be on the same scale as the size of the perturbation terms.
Lemma 17. Let E (0, 1/e] and T Zt be such that T > (g) Consider any positive integer i, & (()), and any to E (O....,T- -- - ).)) Suppose satisfies the condition Eq. 24 Then, on the event
-
la+ty-1
1o+ty-1
Eto,
n t=
Ac(8)
n t=
(.(0))
we have
T udd log x
(Tg(T/8)
S S cot,(6)nL
+ 1 1
Vt E (to, t.tt,,...,o.fff.
where is some absolute constant.
Proof. Let t' the first iteration in (to. to + 1,...,tt + tty -1} such that
m
[V/((e)]| (L)
Ze Zu He Zu + +IVe-ll)
(27)
Since we are working on an event which is subset of (to, t'y, 6), t' is well-defined. By ||e s Ze, we see that
u²p
[Vf 8ty
ell + -|
2m
1=1
log 7)² + eas 1+ log(T/6)
cou'd' (8)
d ))
where used the definition of ()))
30

---

Under review as a conference paper at ICLR 2023
Recall that t' is the first time step such that Eq. (27) holds. By deriving similarly in the proof of Lemma 16 we can show that for any E ftv. to 1,...,t -1].
u2d& log 5) +
log(T/6)
[V & (x+)) - (6t)(0)nLcs
d
Meanwhile, for iterations / E [t', 40 + fg), by using the definitions of Az(5) and Ge()), we have
11 )t) [Vf(z=)] nLes u2ddp log ?) 2
VI+ log(T/o)
[V((=e))]l
6+1-6
11 8ty(o))
[)((+)]]
t-t²
1
mLC3 u2d'p log 5) 2
log (og(T/))
1 81)(0)
+ v 11
d
i=0
"
1 + sty(o)
|[
(1+
1
T x) u²dpp log
log(T/5)
+ 86)((()
-1
n/L3
+ V
1+
86)(o)
d
T 2
log(T/0)
1/1/4. 144488((8))Lo)
u2dpp
log 8
+ 11 d
log T) 2
+ 1 log(T/0)
+8))(0)(21A4-1) .I.s. u2dpp
d
T + +1+t 1+
log log(T/0)
< (6tt(6))LLs uP log 8
d
where we used t', S (8) and the fact that (1 - 1/(8x)) s e//4 for all x > 0. By defining o6 1603, we complete the proof.
We next derive useful result showing that the function change f(z,) fxxo) can be decomposed into one component arising from intervals when the gradient dominates noise (which improves function value) and another component arising from intervals with small gradient which may add to function value but whose contributions are bounded in terms of 7, u and r. For now, we focus on the case (5), since it will be useful in proving that there cannot be more than T/4 iterations with large gradient.
Lemma 18 (Function change for large T). Let C1 > 0, > 0, > 0,C, 2 1 be the absolute constants defined in the stalements of the previous lemmas. Let E 1/e), and let 2 (ō)) be arbitrary. Consider splitting {0, (......, 1} into == [T/L intervals:
(k + (0) 1}, K JK-1 {(K (6)
Jss =
Let In denote the set of indices lo such that for every time-step in the interval Jrs the gradient dominates the noise terms as
1
|V > (L)(
2.
Ze, Ze.
+ +||Yil|
(28)
2
m
1=1
Suppose we choose y such that
1 min
mm
m
1 n
(29)
[tt(o)
(Ir( (Cn((((CddmT//))332244 128c, (28)
31

---

Under review as a conference paper at ICLR 2023
Then, on the event
An0)) ) (
su(o)) )n
(R-3
(,) = H4 :1
(8)n
n
Buy (or (Bx=-xxx0000::------4)1
1=0
we have the following upper bound on function value change:
c (ff
uuddpp log 7)²² + /2log + 64 7
2
f(x+)- fxx)
-E
min rEJ
kEh
+ Tmu p² dde [og 5)
T)
3
=La p² cit
log 5)
T
+ n,r 2 (128t 1 log + TaLLip?
(30)
Moreover, (0)) 2 1- (5r+4)6
Proof. Without loss of generality, we may assume that is multiple of (5 Then, any interval Jk = (lo...., + (6) - 1} belongs to one of the following two cases:
Case 1) (Gradient dominates noise): Recall that this means that for every t E Ja, we have
[Vf((x)) (L)nL
u
Zz Hr Z
Zr
+ +|YYll|
2
m
By our choice of y Eq. (29).
apply Lemma
16 to get
min tEJ
Vf(x))
max IEJ
Vf()))]]-
We now consider the two cases when J has fewer than (5()) iterations and when J = JR f
Note also that the event (5) (o))) there exists some E Jg such that
1
( 2 2 [V((2))
This implies then that
Σ
1
2
2
2
min m (f(()))
2
max (
4 tEJ 1=1
tEJx
64
dEJ
(31)
(0)
tEJ
Thus by setting a (2) in Eq. (3) and by choosing 1) such that
T x3d 3d "
1
m S 128c, Lt, (8))
(8)
follows that
3r
Z V
V (xx)) +
(128),(5)
+
Lap xdd
Σ [VS(2)))
4
m
LEJL
i=1
BEJL
311
7,, (ax+)
Σ |V)(2)))1 TEJ.
4
m
(5t
tEJ
i=1
'To accommodate the last interval which has length at most (8) 1, note that the results we require
for the proof, namely Lemma 14 Lemma 16 and Lemma 17 all hold for any interval length f, (t)
32

---

Under review as a conference paper at ICLR 2023
Z (x))))
m
(EJx
!
min tEj
V f(x)))
(32)
2
Case 2) (Gradient does not dominate noise): there exists some t J such that
m Ze 2 He, Ze,
[V (1,
+ +||Yal|
m
By our choice of n7 in Eq. 22 we can apply Lemma 17 to get
d' log T
+ VI+ log (Tg(T/0)
[V)( S (6))
1A JR.
8
d
Hence, by setting 16) in Eq.
3 and choosing 7 such that
c Lnn x 3d
1)
m
128t,(6)
it follows that
Ci Iaf2x3d
Σ f[z))1
+
128t,
BEJo
1 (6)
Σ tEJu
csty(O)nL
12'dpp log x)
T'
+ V
11
log (og()
d
c (60) 64
T T)² u2dpp log
log (
) + +V1
(33)
Without loss of generality, we may assume that 7 is a multiple of (5) Then, any interval J3 = to + (6) 1} belongs to one of the following two cases:
Having studied the two cases, we may now proceed to use them to complete the proof. Let If denote the complement of J in (0, 1,..,, K 1}. Then,
37
(x.)) 2 + 2 C
T
V (x,))11
4
m
m
t=0
Σ keh
37
7
C1
La x
[V((2:)11
m
128f,(8)
m
t=EJk
tEJx
311
Z (x)) 2
TTpaxx
[VS(2))11
+
18)
m
m
kelf
tEJ+
==1
tEJe
E
T
log (0g()
<
min rEJ
(( +
Σ (0)
log ④
+ v
1
2
64
kEl:
kEli
2
T)² log 5)
(Tg(T
<
7 min tEJ
Vf(=))]
(6)3,,1 + Go
V
1
2
d
keh
(34)
'To accommodate the last interval which has length at most (8) 1, we note that the results we require for the proof, namely Lemma 14 Lemma 16 and Lemma 17 all hold for any interval length f, S (t)
33

---

Under review as a conference paper at ICLR 2023
and by Eq.
+ (1(8))99 uuddp log )) + +v1t log log(T/6),
+ c
f(x+) f(x0) S
Σ
min rEJx
d
kEl
log T)
))
+ TmJu p² ed
+ =IIppupp eut log g
T
+ +, r (a + L.) log Tc₁ Tap2r²
Note that we choose a 1 addition, observe that by our choice of (such that d s b), follows that log(2/5)
(og(//)).
We now complete our proof by using the union bound (suppressing the dependence of some of the events on 8 for notational simplicity) to derive
K-1
P(ET) < P(H,)
+
Σ P(A)
+
Σ
P(G)) +
Σ
P( (0
t=0
t=0
k=
(T + T
4)6
+ 7
6
+
2
2
T
K6
(5r + 4) 8.
T
T
T
T
We are now ready to show that sufficiently many iterations have a large gradient, then with high probability, the function value of the last iterate f (XTT, will be less than min, f(x), contradiction. Hence this limits the number of iterations that can have a large gradient.
Proposition 4. Let ci > 02 2 c4 0, cs 0, C₁ be the absolute constants defined in the statements of the previous lemmas, and let 5 E (0, 1/c] be arbitrary. Suppose we choose nj and such that
1/4
1
u dVplog((/o) min (64efe2 20486102
r
T r.c.min
80g 20z
32
Vm
m
S (d) min
Tog(T/5) Sca () 128c, (Ir(CadnT//i)8d)
256t, ((f(r)) - (o) ++) 4
T 2 max
Then, with probability at least 1 66, there are at most T/4 iterations for which [| f(x))) 2
Proof. Without loss of generality, we assume that T is a multiple of ty (ō)), and we similarly split {0, I....,TT T} into K = [T)) intervals Jo.... ... , JK-1- Let 1 denote the set of indices k such that for every t E Jk.
1 m
Ze Lr Li ) +1xx31|
[Vf(=)] (ty(5)LL
Σ
(35)
2
m
We let If denote the complement of Ii in (0, 10,1,... 1,..., K 1}. We denote
==00==1rl n ( n
T-1
( )
(NL
K-1
(aer
k=0
In the remaining part of the proof, unless otherwise stated, we shall always assume that we are working on the event Eg))
By Lemma
18 with T and our choices of 1 and 8 in the statement of the lemma, we have
2
f(TT) f(00)
Σ
7
(0)0)12223 dd log T 5) + /2log(T/0)r
2 ted.
keh
34

---

Under review as a conference paper at ICLR 2023
T Typu p² ca log 88 TTmpuupp ard loog 8
))
ne1 (128t,(0) - LI) log T
8 + +cgln
(36)
Suppose that there are at least T/4 iterations where [x+))l 2 c. Let Ie denote the set of indices k for which there exists some Js with [[+]( c. Then, by the pigeonhole principle, the set J. has at least (6)) members. Note that, by our choices of the parameters 7/, u, it can be shown that
r) 2 log 5)
log(T/0), d
u2 (6tz(8)mL
+
1+
<e,
(37)
while by Lemmal
17 if ls is in If, we have
[V)() S (5))L plog())o((T/)) + V1 11 log(T/8)
1I E Jr.
This implics that Le S 41
Observe that by Lemma 16 for any k E 11, we have
(f) s [Vf((z)) s ((Er)())))))
Vt Js.
This implies in particular that for any & E Le, we have min
V (x;))] 2 + and consequently
7 2
T
e² Tye
Σ
min [[
LE
16
(
2 128
keh
kel.
Hence, by Eq. (36).
The
u2'Pp log T 2 + v (og(T (108
f(xr) f(x0) $
(8) +
64
+ Tmuu p² c log 7)²²
T)²
+In (nL)u* p² a loo 8 ") T
+ neir² (128t + nL) log g
+ Tn ennLr?
(38)
Now, by our choices of r and we have
2
T 2
12''p (108 log ))²² + v (log(T/5)r
(50))
64
uuddtpp log 5) log ( (0)))
< Tn
(1L))
32
T
< Tn
+
2048cz (log 5)
2048cz (T)(T
512t y (8)
where we used log(T/8) and 20² log (T/5) 2 (8). We also have
Tnu 2² d 1og )) -Tn (nL)ut p² dt (oog 7)² + Tea Txpr2
2
< <nn loggoydlog(T/0)
+ Tn ( + Tn 1024t (6) log(T/8)
The
(
35

---

Under review as a conference paper at ICLR 2023
where we used ezd log (T/6) t c2 2 1 and log(T/6) 1. Finally,
T
(128t + 1)c²
2²
(128( + n2) log
1024Lt
L
By plugging these bounds into Eq. (38) we get
Tnp (6)
Tnp
TIp²
2
Typ 2
f(IT) - f(xo)= <
512(y(0)
5121,(0)
2561,(
Therefore, as long as
(6) ((((z)) (M) + T T
n/²
we will get ((xT) < f" which a contradiction. Thus, we can conclude that on the event ET()),
there are most T/4 iterations for which [*=(]] 2
We can now complete our proof by using the union bound (suppressing the dependence of some of the events on 8 for notational simplicity) to derive
P(87) S P(HH)
Σ P(A))
Σ P(C.)
Σ
(0
1=
(T' + 4)8
K8
8 28
S 60.
T
E ESCAPING SADDLE POINT
In this section, we first show that the travelling distance of the iterates can be bounded in terms of the function value improvement (Appendix E.2). Utilizing this result, as well as Proposition 2 in Appendix C.3 which provides concentration bound on the the zeroth-order noise, we then prove that sufficient function value decrease can be made near a saddle point in Appendix E.3
E. KEY QUANTITIES AND NOTATION
We will use 7 to denote -Amin (V² (xx)), where we know that 7 2 /pE.
E.2 IMPROVE OR LOCALIZE
In this subsection, we aim to bound the movement of the iterates across number of steps in terms of the function value improvement made during these number of steps.
We first state simple result separating the norm of the difference between tr and Itg into few different terms.
Lemma 19. Consider the perturbed zeroth-order update Algorithm 7 N.
7 Then, for any to E and
| - x1o0l Vi(lo, + V2(lo. 7) + Va(lo, 7) + Va(lo,
(39)
where
Vi,,,, = 81p² dot+-11 [x:)))) |
Etato
Villo, = =012
Et
1ootT1 1 Em (2. 1)V (Z+)
mn
Va(lo,T) == 4n7 Itot Y;
Vallo, = 4:7
Dt=to 1 Σm uZ,, 2 11, Zr,i
(40)
Proof. For notational convenience, let to Then, applying the form of the perturbed zeroth-order update in Algorithm we get
||,, xo
36

---

Under review as a conference paper at ICLR 2023
111 Ft
1
1²
Zi fzx)
m Σ
uZ, H4, + Yi
< 41)
Zr 2 (
+ 417
n 2z H H1g Zt.i
+ 41)
Σ Y
1=0
< 447
- +
+ +
uZ
H Zi,
+ 417²
Σ Yi
1=
1=
1=
T-1
$ T Σ [
+ 802
Σ
(2 1((()))))))))))))))))
+ +412
Y
+ 41
2
Σ
uZ 1,2
H 2
m
1=
1=1
t=
r=
1=1
V.().T)
V2(0,7)
Va(0,r)
Vi(U,=)
We now proceed to bound the terms Vi r), V2(4o, r), Va(lo, and V4 T).
First, we have the following result bounding (1)
Lemma 20. Let eι > 02 1,c4 > 0, C5 0, C > be the absolute constants defined in the statements of the previous lemmas, and let E (0, 1/e] be arbitrary.
Suppose we choose y such that
1
m
m
S
TT)(o) min
Scd(h((CdmTTBB)) 128c) (I(Ciii(((11)
There are two cases to consider.
1. The first is when 2 tt) In this case, split fot into k= (T/tt)((()) intervals:
J/ = (tu + kt k ........,.... to (K + (0) - 1}, o K
JK-1= fto + (K - (0))))))).......). to
Then, the event
1u+--1 n A.(0)
(n
K-2
Etgrr = Heg. Hop
(8)
)
n 9:(0)
1m1o
1m1g
we have that
lo+r-1
T) 812²T
Σ [Vf(x;)]1
t=
s 64ntt ((f(zo) - f(xx)) + (T:
where
2
N (T: = 64 1,, d''d' log (1og 2) + v 2 (20g(T/0))
+ 0² d log T)
T + TL 2² cad' (108
8
8)
+ n n (0) + nL) log 8 T
+ Lop
+ (00) 12 (2800) (88) + / Volog(T/ōjr
(41)
37

---

Under review as a conference paper at ICLR 2023
2. The second is when < <t((6). Suppose we choose and such that
Vc
1
1/4
1
u S
min
r min
d/plog(T/0)
64c5e2 2048c1 C2
80s 220 32 /os
Suppose the event
tott (=to
(A:(6) (6()) holds. Suppose also that [V S c. Then, (tt. S 7 - 32n (T)(5))
Proof.
We first consider the case where + 2 (6) Let J denote the set of indices & such that for every time-step in the interval Jk, the gradient dominates the noise terms as
1.
f(x))) 8ty(8)LL
u 2
Ze 1 He, Ze.0 + +1xaall
(42)
WLOG, may assume that to O, and denote (i(r) =- Vi(O, WLOG, we also assume that r is a multiple of (5). From Lemma 18 on the event that & (6) holds and by our choice of 17, we have
2
f(x;)- - f(zo)( S
Σ / Vf
7 min LEJ
of +
ueel (og 5)
v /2log(T/8))
2
61
kE1
T log + Tqu" p² c
+TImp u2 ard (10g 5)
))
5
T
+ 7/1 r (128t + nL) log 5
+rq
By Lemma (and our choice of 1j), follows that for any E It, on the event OreJ, Ar(8,,
we have
EIVs(=)] s 4t, minl minl|
LEJ+
IEJC
Thus, the event that (8) holds, for our choice of we have
Σ Σ [IVS(()) < (6)(
Σ
min tEJ
(
kEl LEJ2
keh
s (t)
Σ
min [
2
tEJs
ke4
T)²
$ (6)
(f(co) -
(((x)))((E+))) [(x))())))))))>)))()) +
o4 16,(1)
(PPPpp log o
+ / /2log(TT/)rr
64
Tnu'pp p² c log T
3
add . [oog (32 ))))
+ S6)
+ TLm
T no: ( nL) log + Tc)
+ (6)
Similarly, for any k E If (where If denotes the complement of in (0, 1, ... K 1}. i.e. intervals where the gradient is smaller than than the perturbation terms in some iteration), on the event (NteJ,
9e by Lemma I7 (and our choice of 1)), have
[x:)( S (8) & plog((T/0)) + V2log(T/0)r) Vt Jk.
On the event that (8) holds, this gives us then
Σ Σ [f(x))) < "F (6))(0)) L2 ( (I plog(T/8) v2log((/0)r)
kE tEu
38

---

Under review as a conference paper at ICLR 2023
Hence, the event that (6) holds, have that
[V E E
[IVS(())))*
+1 E EiVS(())11
kEL BEJx
REIFIEM
n t5 uu'dp
of
(10g log )
v (2log((//0)))
Tmuupp cadd log 8 )) + ATINju'p -cp
cdd (oo r) )))
+ 8t)(
(12rt(128t,(0) (L) log T regLnppp2
+ (6)
log V2log(T/ōr)) ))
+ (6)
(0) (lggplog(T//))
This yields the final result for the case 2 t5(
2. We next consider the case where T < 1 (6). Recall the notation that
}
Eto, to + T, = n ---
[V Sty(()nL
Ze Z, He Ze,e
+ |
2
There are two cases to consider.
(a) On the event E(to, to + 8) n t=to
A(())) we have by Lemma 16 that [[v](=)] s (zoo] for each t E {0, (0.1..... T-11-11 -1. Then,
to
Vi r) 8nj²
[Vf(z))] s 81227² (41VV((0))1)) S 32m
where the final inequality uses the assumption that [ S..
(b) Suppose the event E to + + d) n (nloto- A.(o)) n (nt 1ot--1 (r) holds. In this case, by Lemma have that for each E (tu, to + 1........ to + 1}
[V (cst,(0)nL
uddp log 5
T
log log(T (T)5), + 1+
d
SG
where the final inequality follows by our choice of r,. u and r (ef. Eq. (37p). Hence,
Vi(lo, = =
Σ
[++(21]1
t=to
T)² + +v1+
log(T/6))
< 8122"" col)(6)mL
u²'d' log T
d
< T2 < 722
The final result for the case < (5) then follows.
We proceed to bound V2(lo, 7).
Lemma 21. Let e₁ > 0, 02 L, > 0, > 0,C1 > be the absolute constants defined in the statements of the previous lemmas, and let E (0, 1/el be arbitrary and T > be arbitrary. Suppose choose 7i such that
1
m
n <
min ( 128c, (Ir(C,dmm//8))b
(ō)
39

---

Under review as a conference paper at ICLR 2023
Let T. denote integer such that T3 max (T.ty(0)), and for any F > 0, define
B(ô; F) (L) + Nur (T,,
( (T+ ++++, m) (Ir(CT/88)².
b, t,(6)T
Let d, C >
denote the same constants as in the statement of Proposition Denote the event that
either
B(6; F)
to 10
V2(to. r) 8172
Co+r-1 1
d
(I(CTT/0))/V///))11 (. (108
CT2
B(d; F)
or V
Sd
max Σ m
+log
log
(6; F)
holds as L F We show that P P(t (Ō; F)) 2 4. Finally, denote the event (F).T.(F) as the event that I (3 (( F.
Then, on the event (6) n Et (8) O M (F) (where Eo,r, (8) is defined in Lemma 20
8d
V2(to, 7) < B1 F Fy (8) max
(Ir(TT (F NT,
(43)
m
where
CT2
B(o; F*) bi (8: +1)
B1 = log
+ log
log
8
7. is direct consequence of Proposition In the rest of the proof, without loss of generality, we assume that tg = 0 for notational simplicity. On the event Co,r (8; F) n Eo,r, (6) n MM, (F), suppose that
Proof. We note that P( (6; F)) 21 5
(I(CT [I(CT"/))/VV<<>))1 B();F) 8t (5) + No.r (Te.()))))
( Ta d m
(Ir(CT2/6))²
[V(x))) (L, + (T,,))
[xx)) (L) (T.r
11
t=0
T
81 T.
[V 64mTTT((6)(FF + (T,,
T--1
= T
[v.(z:))| 64nItt - f(TT,) + 8)), since f(xo) - f(TT.) S F
VI T.) 2 64n/T (o)( ( + (T,,
where we note the last equation contradicts Lemma 20 For notational simplicity, denote
(CT2
+ log log (((;
-1) )
F): = log
5
by (o;
(6; F) holds, we must have then that Observe that B1 is larger than Br for every 2 1. Since L
V2(0, 7)
S
max Σ
(M/CT9/0))/1///>))11 (6;;;
31 F).
81p
WWe that by construction, B(F:F) b-
40

---

Under review as a conference paper at ICLR 2023
Now, continuing, recalling the definition of (.) = 8nfT, Σi= [xx'')]
d (I(CTT/))
(((0,))s²331 max
807
m
T.
S 2 31 F) max
817
(Ir(CT2/0) /0)) Vi T.)
S (: F) max
T,
3. F) max
(Ir(CT (6))² (0) fIIT)) + Nu. (T,, (T),::)))),nt(((()))))))) (F
m
@
$ (1; F) max
(Ir(CT2) (6CCTT2/))32
Nu. 8))) (
m
c (6; F) (8nl max
(L)CTT/)))² (8(F + Nu. (T., 8)))
We note that i is consequence of Lemma 20 Me,.I,(F) holds, i.e. f(Ita) - f( F.
while comes from our assumption that the event
We next bound Va(to, 7) and Va(to, Lemma 22. Let e > 0 denote the same constant in Lemma 7
Consider any arbitrary 0 < 8 < 1/e,
and let r 2 (ō) be arbitrary. Let (6) denote the event that
Va(to. 7) 4n2
Y
S 4co log(2dT/66)r
where c6 > 0 is an absolute constant. Then, by Lemma 7 P(NNo. (6)) 2 f. Denote the event
m
))}}
T
1
0,(5)
Z1, S ord log
m
where > 0 is an absolute constant. Then, on the event ntots-1 (5)),, we have
m ))
Va T) S 4cT7² 22"= (log
Moreover, for each (PO,())) 2 7.
Proof. The proof for (t 7) follows directly from Lemma 7 by picking eg be the that appears the statement of Lemma Meanwhile, observe that
Valto 7) = 4n²
uZr, 27 Hr 2e.
1=0
1a+T-1
uZr, Z,, Ele, 1)
< 7
1=tp
fot
41 2
p² u 1
t=to
T ))
< 4cm1 27 22² dd
log
5
41

---

Under review as a conference paper at ICLR 2023
Above, to derive (in)) we used the bound that |1, - Ze,ll The final inequality is a conse-
quence of our assumption that - holds. Finally, the result that P(O:())) 2 11 & holds
due to Lemma 11 where we note that we may pick the absolute constant to be equal to 2Cc where c, C are the absolute constants that appear in the statement of Lemma I1
Finally, combining the earlier results, have the following technical result, which bounds the travelling distance of the iterates in terms of the decrease in function value decrease.
Lemma 23 (Improve or Localize). Consider the perturbed zeroth-order update Algorithm 7 Ler é' > 0, > 0, 02 2 1, 0, 0, Cs > 0, C7 > 0, C1 2 1 be the absolute constants defined in the statements of the previous lemmas, and let E (0, 1/e| be arbitrary. Consider any T. 2 tt(ő). For any F > O, suppose f f(TT,) f(xo) > -F, f(x0) f(TT,) < F. Suppose that the event
Plo.T. (6, F) = nf=1 (L (0; F) N. (5)) n (n
(n 1 n A Ge(0)) n (o)
holds, where the events Et (8), L No (6), O1(5) are as defined in Lemma 20 Lemmal 27
and Lemma 22 and (e( and Ac are defined in Lemma 13 and Lemmal 15 Suppose we choose
u, r and such that
Ve
1/4
(Vplog(T/0) min (44ffe2 2048c102
880 Sao2202
32.00
vm
m
5 [ly(d) min Tog(T/0) Sca Bca(I((CrdmTT)))33//33
128c, (Ir(CydmTT(6))j)
Suppose 17 S min {I, E,(oT T0 }. Suppose also pick and small enough such that
1/2 {0,1, ..... To}. we have that
F
F 4og log 1og(2dT/8) 4077/T
" "llog(//8)p11
S min
65c nT, 1og(T
+ 1322c + +1)
8
Then, for each
| =toll S dr, (6, (6,F) F);
where
16d
ΦT, (ò, F)
max max
( max
(I(CTT + (T))
where Br (); is defined as in Lemma 21
Moreover, P(P,, I. F)) 2 1 127.6
Proof. We recall that
Mo+r-1
1 -22 S 81²²
Σ
2
Σ m
Zz ZZ 1)V((())
Vi(fair)
Va(ta.7)
1
lott-1
m
+ 4x7
2
Σ
Ye
+ 41j²
Zr, Z,, H Zt
m
t=oo
Va(a..7)
By Lemma 20 Lemma 21 and Lemma 22 which bound (1a, 7), V2 7), and Vo(lo, Va(lo. respectively, on the event P. P...T, (8, F). we have, for any 0 5 7 S T.,
||.,, xo 2 < V1 + V/2 V3(0,) (0, max (64n)t) (N.))) 32, (5))
42

---

Under review as a conference paper at ICLR 2023
8d (I((TT21))) (F + Nu, =F
+ (6))((6;))))((0)) max
1 m
+ 4catf² (oggod//22/00 + 4cT1 72ppp2ppppp p2 dt (log(T/6))*,
where (T; 5) defined as in Lemma 20
For the simplified bound (which does not contain [T; (T) it remains for us to show that our choice of u and r ensures that Nu. (T,,)) S and
Aco 1og(2dT/0)r + 4cm T2 p²utd (log(T/8))* & {T),tt(0)F.
First, our choice of ensures that
u d p² (log( (T/8))* s2.
Next, recall that
2
(T) = c "6,
T)² udd' log σ
+ /2log(T/8)r
+ Tquu x² ad (10877 )) + +IIn u p² ead (108 7
+ n + L)) log T 8
+ =ng
T2 ( plog(T/0)))) + /2log(T/5)r)
Recalling our choice of such that
min (8) (r) /
it follows that
(80
Nu.r (T.;)) S nT,r²
(T)) + 2c, + 2c, + (128c) + 1) log(T/6) + e + 808 log(T/5)
64
65c3 8
< nTTTr log(1/8)
+ 132c +1 S F,
where the last inequality follows choosing such that p <
Similarly,
1f, log(T
13320
we have
4c, log(2d7 /8)r + T 2u ad (log(T/8))*
(ō) (4c6))og(2dT)) 4ctnTT (log (log(T/8))))
S (o)
By choosing r such that
F 4cg log(2ol)) (2dT + 4c71TT
2 <
it follows that
A Jog(2//888) + TT Pu'd (log(T/8))* < (8),
as desired.
We next lower bound the probability of
Pio.T, P) == of22 (6ro,r F) n (N
Observe that
n+e ( Elg (8)
43

---

Under review as a conference paper at ICLR 2023
1-+--1
K-2 (((()
(n k=0
= (o)
(1)n
n Ar
n
B (0 ( -Bottt--110000---KKK-----
t=
K-2 n
B (iot 1,0 (K))))))) (N ((a000))))))
- Hoorr (6)n
Note this implies that n by Lemma I
- ( (6) (nn A,(0 n - (tosr(0) We note that
P ((
57,6 T
Meanwhile, note that
(
(h
R~= Boothe (K
T (0)) En E
k==
Hence, by Lemma 14, we have that
((122,100) ((n
K-- Bi Blotke, (101101110000))11 (K--0000000000000000--00--111111
AK=
< <P <P(( (( =
T,
Meanwhile, by Lemma 13 and Lemmal
15
we may bound
f--
A(0))()))
T.8
2T,6
3T,6
F
T
T
Hence, it follows that
(o (0) (122
5T.3
T,5
3T,6
97.6
+
+
T
T
T
T
Meanwhile, it follows from our results in the preceding lemmas that
P (( (Cr..r (6; N.N., (.::)) (8)) n (1==))0000))) 3T,8
Hence, it follows that P(Ptt, (6, 2 127.8
E.3 PROVING FUNCTION VALUE DECREASE NEAR SADDLE POINT
We next build on the technical result earlier to prove that each time we are near the saddle point, there is constant probability of making significant function value decrease. We briefly provide high-level proof outline below. In our proof, we introduce a coupling argument connecting two closely-related sequences both starting from the saddle, differing only the sign of their perturbative term along the minimum eigendirection of the Hessian at the saddle. Specifically, when function decrease from a saddle is not sufficiently large, due to the earlier technical result, we know that the coupled sequences will remain within a radius ó of the original saddle for large number (which will denote as T,)) of iterations. We then utilize this fact to show that the difference of the coupled sequence will (with some constant probability) grow exponentially large, eventually moving out of their specified radius ó within T, iterations, leading to a contradiction.
Our first result formally introduces the coupling, setting the stage for the rest of our arguments. For notational convenience, in this section, unless otherwise specified, we will often assume that the initial iterate do is e-saddle point.
44

---

Under review as a conference paper at ICLR 2023
Lemma 3. Suppose Zu is e-approximate saddle point. Without loss of generality, suppose that the minimum eigendirection of H := f(ro) is the e1 direction, and let r to denote -Amin (V2 fxo)) (note y /pe). Consider the following coupling mechanism, where we run the zeroth-order gradient dynamics, starting with In, with two isotropic noise sequences, Ye and Y; respectively, where (Yt)1 -YY),, and (Yt); (Y)), for all other + 1. Suppose that the sequence (e the same for both sequences. Let { denote the sequence with the (Yr} noise sequence, and let the {r/} denote the sequence with the {Y() noise sequence, where
4/41 32/= -1 17
2
bi (.H.H.i + +X;)+
z/6 = Io. +x)),
m
and H == Mi.. Wi
V2f(x's + des, for some deat E [0. 1]. and Hi,,,- = 42 f - -,,,i--Zi;) for some -' E [0, 1). Then, for any 2 0.
with Hight
2
h141 I1+1 x/441 17 T=0
h) ( Eso (T)
7 Σ (T
n "
m).
0=0
(c0(1)1)
(x++11
Σ (T (T
" n 8
x=0
(c(++)
Wp(c41)
where
(t)
1 m
Σ ZZ - (2v)( (1) 1
(Ze.))).)) T - fa)))(a)), (t) Coo
<o (t),
m
(t())
Σ u 7, Z 7r, (t) m 2 7r, 7e. Eu(t) Eu()) (t),
m
H = 1// 4² Mar, + (1- aa)=idda.
Y, = Y, Yi.
Proof. Observe that
hc-1 == 2+41 2'411
It 17 (0)) 00
-it 17 [(VS(xx) - (s(()) + (coo (1) - cg (1)) + - (%
.t. nH1a; 7/( [H: H8 - T (1) (l) n
1
(1 n1ll - E (7) 71 Σ n - "HI, H) 7) Σ (1- (u 7 Σ (1-ml
T=0
Won (++1)
W=(++1)
w,(++1)
W,(++1)
where
1 m
1 1 (Ze,) - 1)V (t) = Eno
So (t) =
Z,,Z,, (xx), (t) =
Ey (t),
m i=1
m
1 m
m
(.(1)
Zz Zo, Heiiees Ed(1) m
Ze, Zr Ze, Ze.,, E.(1)= =v.1) (1,
m
2
A. = / V2f(an + (1 - a)a;)da.
y, = Y2 - Yy,
To derive the final equality, we utilized the fact that an6 To- This completes our proof.
45

---

Under review as a conference paper at ICLR 2023
Suppose zu is an e-saddle point. Recall that 7 > 0 denotes -Amin ( where we know that
[min(e (0,, I, if f() (c, -sttrict saddle for any v > upc
Vpp
otherwise.
In the sequel, for any t 2 0, it is helpful to define the quantities
(1 + m7)2
a(t)² == (1 17772
3(t)² = (177)2 + 2myy'
(44)
(n7)² 2mm
We next introduce some probabilistic events (and their implications) which, if true, can be used to bound the sizes of ||W 9o (t + 1)ll. [t + 1) [[ (t + 1)]l (and as we will see in the next result, indirectly bound WHr (t + 1)ll- These bounds will be useful in the final proof of making function value progress near a saddle point.
Lemma 24. We assume 8 E [0.1/e] throughout the lemma. Suppose that we pick u, r and n as specified in Lemma 23 Suppose T, 2 (5) Suppose also that
[(TT,) - ((r) > F. [(IT.) 5(x0) > -F.
Then, we have the following results.
1. Let (6) denote the event
S6(0)= max (12, roll |1/ zoll s dT. vo
In addition, let So( denote the event
v3 (203pd (log(T/6)))) u² v0
S,(6)= ||alt++ + 1)ll S nB(++ + 1)
Vnp
where Ci is the same absolute constant the es in the preceding lemmas. Then,
P(Sa(0) 2 24T,8
T
2. Consider defining the event (o),), which is the event where
either (1+ dL?
x+ - 21=l1( /6))² 2 Gr, or m
I|W (t + 1)ll
I cm max
Ir
CT2)
dL?
g(t x 1I? g(t + 1)
log
[Cd12)
+ +log
log
Gr, Gr, F\) g(t + 1)
+1
T=0
normalsize holds. Above, c,C refer to the same constants Proposition
and
Tx-1 (1 m
dL²
3(T. Dm 60vd
[(( + 1)mr 2 60yd
Gr, =
Σ
(1)(CTT)))) (5, F)
g(t + 1) =
m
Then, (R((((5) 2 $. Suppose the event
(n()))R((8)) (8)
holds. Then, the event Sgn (5) holds, where
Sgo (8)
\0 S
To-1 (0))
and (5) is defined as (6)=
(8)
I o0 (1 1 (168, F)em,
max
(I((TT))
Ir
CT
2
Σ
dL2
(1 20t- 2;I1. s0((+1)
==0
where
CddT²
(T,((8.P))
Gr, (8, F)) 1)) + +1). 9(1)
G6, loog
log
log
5
46

---

Under review as a conference paper at ICLR 2023
3. In addition, let Sp(8) denote the event
2 2/2log/ (6))(( + 1)vp
S9(6) | (t +1]1
44 50 T.
Vd
Then, ((S, 2 1 T.4
Proof. We consider the three claims separately.
Note that our assumptions satisfy the conditions required Lemma 23
Hence, by
Lemma 23 on the event Po (8, F), we have that ||,, zoll2 z Φτ, (6, F). Simulta-
neously, on the event Po,r, (ô, F), we know that 10mo'Ge(0 holds, i.e.
Ze,0ll 2czdl (log(T/6)) vA st
(45)
Thus, for (.((++ + 1), we have that
[t,(t 1)
7 Σ hH - EG(T)
t
7
Σ
17 H) - (T((TT)
+
17
Σ [T
1H-nnH (
Σ (1 + my) r-r (
1
m
2
Zz H Zz,5
+ 1
2
Ze, Ze
2
2
T=0
i=1
(1 + m7)) r-r
Z 1122
m
i=1
(1)
(1+ (- p(2c)) (log)
17
7=0
(1 (1+
(20g (log (log/))1())) u²
M
(mr)) 2
n5(t 1)
(203pd (log(T/6))3) u²
m
v3
S m) + 1)
(2czpd (log(T u?
v3
n/ 1)
(2czpd (log( (T u
where the inequality in (iv) holds due Eq. 45 the equality in (V) holds due to the definition of 3(t + 1), and the inequality in used the fact that ?
Hence the event
{ [1 xoll² S dr. (ō, F) and } (.)
holds with probability least 1
12T.8 7
Note that by the coupling, the distribution of af the same as that of TT. Thus, by the assumption f(rrr) f(0)) > FF, it follows by similar argument that the bound || - 1 < Φr. (6, F) also holds with probability at least 126.. The claim then follows by an application of the union bound.
47

---

Under review as a conference paper at ICLR 2023
2. For the second claim, observe first that the claim P(R,(8)) 1- is consequence of Proposition 2 Suppose next that f(xr,) ) f(æo) > -F. Then, by definition the event (6). we know that
| - soll² S ΦT, (6, F),
|| - moll2 S dr, (6, F)
where ΦT, (6, F) is as defined in Lemma 23
Suppose now that (0) holds true, and suppose for contradiction that
dL2 | (I(CT///))))
Σ (1+ (1+ (())
=
2 (r,
7,-1
dT?
(B(T:))r))
8
Σ
(1 + m7)
60vd
This implies that there exists some S S t S T3 such that |>+ - x111 - However, we also know that the event Sz()),
80T, (6, F).
||,, - 411 2|| - zoll + 2|12 - æoll s 4ØT, 40,, (6,
This leads to contradiction. We must then have that
[W 90 (t + 1)ll s (6, F)d max {
(1r CT2
(1((CT2)
dL2
x= m (1 + m)) - 1211. =zIl.o((+1))
where
Cdd2
G(ō, F)
(6 F) = log
+
log
log
+1)
g(1)
3. Observe that
Wp(t + 1)=1)11 = Σ -HH = E m
0=0
T=0
which means that Wp + 1) is I-dimensional Gaussian with variance
(1 m7) 2(- 4 2 (1 + ((++( -1 4 + 1)2 2777 + (177)2
(46)
d d
d
7=U
Since ael + 1) < 31 + 1). using the subGaussianity of a Gaussian distribution, it follows that for any with probability at least 8/T,
W ( + +I]l 2 /8) + 1)pr
Vd
For any F O, we are now ready show that the algorithm makes function decrease of F with 2(1) probability near an e-saddle point.
Proposition 5. Suppose that Ita an e-approximate saddle point. Let 0, 0,
0 0, > 0, C7 > 0, C Z 1 be the absolute constants defined in the statements of the previous lemmas, and 8 E (0, 1/e] be arbitrary. Consider any F O. As the statement of Lemma 23
suppose we choose u, r and y such that
Ve
1/4
U. d
min
r S S--min
64c202
2048c102
88g /2c 32
48

---

Under review as a conference paper at ICLR 2023
Vm
m
7 (6)
min (og(TT))) Sc, (c((I((Cjdm11/)))8122 128c1 (ICCCcmmII/)))
Suppose we pick
T. max
1.
(47)
T7p
where
20v viV//p222 + 2017
max log
2vorr, (6, F)
1
ypr
min 2b 1, 1, /pc
f-) is (e, -strict saddle for any vp > /pe otherwise.
Suppose in addition that u, also satisfy the conditions
nv
u
120/3ca
(T)g())))
1
miù
1
max
C' F)
360u(c)) (Ir (2F Si
(6,
2
where (6, F) is as defined in Lemma 23 d, c3, C are the same constants as in the previous
results, and cg = 2/2 + 20 Suppose also that 6r, (6, F) satisfies the bound
ØT. (8.
(48)
loggup
Then, with probability at least 1/4
13T,5
((tt) (1xto) F.
Proof of Proposition Without loss of generality, assume that to 0. By Lemma have
$t+1
= =1++1 - 2/+1
1 Σ (I THH 590 (T) -1 Σ (I nHH (T t=to
1
HJ², - Σ (I (u())
Σ (I -
r=to
r=to
7=
Way (1+1)
Wx(++1)
Wo(++1)
W,(++1)
where
1 m
(t) 1 m
Egu (t)
Z, (x))
(2,,( -1NF(.)) (t) Ego (t) E, (t):
m
m
1 m
m
(t)
V
Z, Z, H1 Ze.s. E.(()
Z 2, Ze., (t)))
- (t). (t).).
m
2
2
He = / v2f(ax + (1- a)a/)da.
Y, Y2 Y/,
Recall that we define for 2 0,
3(t)² == (1 )
alt)2 (1+ 177)21
(1r))2 + 2n7"'
(m7) 2177
Throughout the proof, we suppose for contradiction that
f(TT,) f(x0) -F, S(ITr) (xx0 > -F,
49

---

Under review as a conference paper at ICLR 2023
and assume the event
(n (n_)))((0)) n (
holds, where the events intersected are defined in Lemma 24 Then, by Lemma 24 the event S (6)
(also defined in Lemma 24) holds]
Consider the following induction argument, where we seek to show that there exists an absolute constant cg > 0 such that for every t E {0, 1,..., ,T,),
((t)r and max { go (WW Vd
B(t + 1)p
|| + - log (T/0)
vd
(49)
Combined with lower bound on |W + 1)]l (which makes use of the property that W, + 1) is 1-dimensional Gaussian), will then use the inductive claim in Eq. (49) to show that
(I.)I 2 2 (or))l + [| (T:)II + Wl (T.)l)
Since W,( [[++)] 1) is I I-dimensional Gaussian random variable with a standard deviation that grows exponentially with f, by our choice of Ts, we will see that || x is larger than what expect (since our assumptions imply that max ||,2,, zoll? || xo 2 = Φτ, (6, F), i.e. 2r, and 2/y, both remain close to zo and hence close to each other). This yields a contradiction, implying that on the event we assumed to hold, i.e.
(nZ=)"R (o)
the assumption
((TT,) ((x)) > F,, and -(zz)))((o))) =
((xo)
not true, i.c. one of the sequences must have made function value progress of at least F.
We proceed to prove Eq. (49). Observe that the claim holds for the base case 0: this is true since Th = z/- Now suppose that this holds for all 7 I t. We will seek to show that Eq. (49) holds for
+ 1 as well. We do by bounding the norms of W 90 (t 1), Wn 1), W. (1 and W (t 1) respectively.
1. (Bounding [W,, (t + 1)()) Since the event S (5) holds, follows that for each 2s0o
T, 1, we have that
(1r CT2 W 30 (t 1)1l s (8, P)d max (Nr 5
dI2 (1 + 2 x1ll g(t+1)
where
CdT2
Gr, (6, F) g(1)
)) + +1),
(6 = log
+ log log
and the terms Gr, (8, F) and g [L) are defined as Lemma in Eq. (49) that there exists Cg > 0 such that
24 Recall by the inductive claim
8(t)rr Vd
| x1 S co (T/))
AO
Hence, it follows that
{ Vi++ Ir
(CT2)
Co co
B(t)r Vā
3( 1)mr
IW go (t+ 1)ll < (8, F)n
60v
We may also directly assume that Soo (8) also holds, but our way of reasoning prevents double counting of prohabilities.
50

---

Under review as a conference paper at ICLR 2023
Hence, noting the choice of T, in Eq. 47
by choosing y7 such that
(r
CT
vdl.
1
degG(0,
mm _
11
s
and
60
360((c))<GdL2 (Ir (r(222) (6, Fyy2 (50)
(o F)n < 1.
it follows that
3(t + 1)rr
[ 1)ll
60v/
2. Meanwhile, the term (t 1) can be bounded as follows. By the inductive assumption in Eq. 49 we have that
| = || 241l S log (T/8) (T)
VOSTSE.
Vd
Moreover, the event proof assumes, know that ||2, 2oll?; |0 - zoll²} I Φr, or, F).
max
Thus, using the p-Hessian Lipschitz property, we have
WHit + 1)l1 = Σ - - H
09 10)(
$ Σ (1 + ( 0r. (6, F)
Vd
r=0
(())rr
$ co - 1) log(T/))) Φr. (6, F)
Vd
3(t) Vd.
og log( Ør, (6, F)
Given our choice of T, in Eq. 47 if
1 (T, F)
ToT, log log(T/o))///v//// VT, (6, S
60
60cgep log log( (T/5)
it follows that
3(1 + 1)1r
[t+ 1)ll <
60
3. Mcanwhile, for Wa + 1), since the event (,) holds, we have that
v3
|W. (t + 1)ll S +
(2espd (log (log(T/8)))) w²
mb
Now, by picking
v3
(2capd (log(T/8))) x2 3(1 + 1(mm u S
mp
n + 1) Vi
60
120v303 (dpd((oog((/6))
it follows that with probability 1 - 8/T, || (t 1) <
8(++1)m 60V
4. Meanwhile, observe that since Sp(5) holds, it follows that
w, 2 2og (T)5) + 1)mr
Vd
51

---

Under review as a conference paper at ICLR 2023
Combining the bounds for W go: Wp WH and Wa. it follows that
| -
W 90 (t + 1) + [W, (t
+ 1)ll + [[ ( 1)
s 8( + 1)rr
60 +
+2 22/2log(T/5)
Vd
60
60
B(L + 1)rr
+ 2 (Tg(T/)))
vd
20
where the final inequality uses the fact that 0 < 5 < 1/c (which implies log(T/6) 2 1). Hence, we see that the first part of the inductive claim of Eq. (49) holds with the constant
+ 2v2, and
the second part follows naturally as consequence of our argument above.
Meanwhile, observe that for any y such that np S 2. we have that (1 + 177) nm > 2. Thus, by choosing 7) such that mp Σ 1, have that for any t 1
778
a(I+ 1)² 2 2 (1 -
Hence, following Eq. (46). by choosing L. (T,))) is 1-dimensional Gaussian with variance
at least 2(TT) such that with probability at least 2/3,
((T.)nr 10vd
WW N
Simultaneously, we know that on the event
(.()) (..(())
we have
33(Ts)mr
B(T.)m
I 90 (T.)II + [[ [2.(
60Vd
20v
We note that by Lemma 24 we have
((n n (.,()) 21
24T
T.8
T.8
267,8
+
=
1
T
T
T
T
Thus, with probability at least 2/3
267.8
have
T
((T.)r
| || 2 WT,]l 2
20vd
Thus, choosing T, > ne
_ where
20 11222 + 2177
max
log 2 2 (r, (6, F)
17r
noting that if np < 1/2, then (1 177) क 2 (1 + mソ5) * 2 2, we have that with probability least
2/3
26I,6 T
3(..)nr
(1 + )T)
20vd
20vd 22m + (177)2
lox 12.7, 22,
mp
(1 + m)
20
2217 + (177)
Jon 2 /or, (8,F) 20 1207
2 ΦT, (6,F) > 2 S//oTT. 8).
HDVds/2m + (m
Thus, at least one of | æoll and | so || is larger than VØ(T,, 5), contradiction. Since the two sequences have the same distribution, it follows that with probability at least 1/3 137.6 f(T,)) ((xo) FF.
52

---

Under review as a conference paper at ICLR 2023
In the result above, require upper bound the norm of dr, F) to hold (i.e. equation 48) which in turn necessitates an upper bound on F, the function value improvement we can expect to make. Below,
show how to choose F to be large as possible (up to constants and logarithmic factors) whilst still satisfying equation (48 assuming that u, and v) are chosen appropriately small such that the dominant term of ||r,, (6, F)ll scales with F.
Lemma 25. Consider choosing F such that
F 2 60cglp log(T/8)) ( (129 (16()(CTT/0))) + 1))
Suppose vj S min {
17(0): GØL ).
Suppose we pick u and small enough such that
11/2
Fdb
F 4cs log (2 + Bere
u dlog(T/18)p122
4² S min
2clog(T/0)
65c
+ 6c1 +1)
Then, Nu, (T, S F, and that
Aco TT /8g + 407 T2 puut ddd (log(T/6))*< S
Suppose in addition 7) is small enough so that
(tx
60cgsplog(T/5)
Suppose also that +b and 1j S satisfied.
m d so that To
d. Then, the condition Eq. 48 will be
Proof. We note that since condition
T, <
2x it follows by our choice of r that also satisfies the a
min
T/T, logolo (T)(
65c3 (
6c, +1)
4cg log (8) 4c7rIa
Hence, choice of 17, and r satisfies the conditions in Lemma 23 and it follows then that
(:; (6) max { 16d
Φr, (6, F6 max
(I(CTT//))F + (Tnnt
where (6; F) is as defined in Lemma 21
The condition in Eq. (48 requires that
+
(r, F) 5
60cgtp (T
By our choice of such that
2 60cgup log (T/5)
32n (2))( =
suffices for us to show that
+
2
16d (IrCTT (1)CT)//))2FFTTFFF
60cgsplog(T/5) 2 (2 (6; (6; max
+ (8)
2
m
16d
129n/T.l, 86 3, (6: F (8) max
Without loss of generality, we may के if f() is (e, -stritt saddle for any
53

---

Under review as a conference paper at ICLR 2023
By our assumption, we know that T, 2 d. Thus, further simplifying indicates that it suffices for us to show
2
12 (6; (6) max (Xx
2 600gsplog((T/)
(51)
By choosing F such that
2
$ 2 60cylp log (T/6)
(100 1))
we see that Eq. (51) is satisfied.
Remark Suppose without loss of generality that T, 778" Then, as a consequence of Lemma 25
we note that the amortized function value progress of decreasing function value by F over T. iterations is
F
2
T. 60cglp log(T/5)
(( (100((00)))
J = 0²
(129 21 (60cgt log - (1)))))))))000-33330-00000101111
F PROVING THE MAIN RESULT (INFORMAL STATEMENT IN THEOREM FULL STATEMENT IN THEOREM 2
In this section, prove main result. First, need an additional result (Lemma 26 showing that with high probability, we can bound the function value increase a saddle appears within (6) iterations immediately after have had Т, iterations after the previous saddle. We note that such bound is necessary because our earlier result upper bounding function increase in iterations (see Lemma 18) focused the case where T 2 (o). Next, we state and prove Theorem which the precise version of Theorem in the main text.
Lemma 26 (Function change for small T). Let Ci > 0, C4 > O, C5 > 0,C1 2 1 be the absolute constants defined the statements of the previous lemmas. Let d E (0, 1/e). and suppose 5 < (g)
T Let J denote the interval (0, 10.1..., 1} where T < (.))
Suppose we choose n such that
1) 1
mm (ea S 128c, 128c1 (B(((((CCmm)))))
(o) min
(52)
Suppose also we pick u, and as prescribed in the statement of Proposition Suppose that minee [x=]( S e. Then, on the event
r--1
r-] (..00))
n A((0)
D, (6) = (o) n
we have the following upper bound on function value change:
+1(())mu" p² d (ogg T 3 71 [(x)) [(x0)
+1,(8)Liq'''p eid' (10g 2)
4
T 1 2 (8) + L) log 8
Moreover, P(D,(5)) 2 (8)+
54

---

Under review as a conference paper at ICLR 2023
Proof. Throughout the proof, assume that the event (6) holds.
Let denote {0,1....;T - 1} where < (6). Then, J belongs to one the two following cases.
Case (Gradient dominates noise): Recall that this means that for every E J, we have
1
[V (l)
Zz Zi Zis
+ +11a|1|
2
By our choice of 1 in Eq. (29). we can apply Lemma 16 to get
min SEJ
min||Vf(z))ll== 2
max (x))l] tEJ
Thus by setting a = 128) in Eq.
3
and by choosing such that
e
Lo
"
?
m
(
128c: (o)
follows that
307
m
xd
2 (zx)
+ (288)(())
V fxx))1
m
m
31
Σ [[x)))]
m
64t,(5)
LEJ
IEJ
$
"
V (xx))l
64t (
1EJ
"
max fx:))1
64t (8)
EEJ
YEJJ
16n
Σ
minl
V s " min
V/(,,))] < ?
(53)
(8)
LEJ
4 LEJ
(EJ
where the final bound holds since we assumed min V fx()))] S c.
Case 2) (Gradient does not dominate noise): there exists some t E J such that
m
[V)( (o)
7 H Ze, + ||Yall
m
By our choice of nj in Eq. 29
apply Lemma 17 to get
T
log((18)
[ S (8))L
wdd log z
1+
1i E J.
d
Note that, by our choices of the parameters 17, u, r, it can be shown that
T 2
log(T/0)
u2'pp (5))
log
6,,
d
Hence, by setting (6) in Eq.
3 and choosing 7 such that
Tnp² 3d 1
1)
m
a 128t,
it follows that
e L 2d
17
+
V fxx))l?
(5)
m
55

---

Under review as a conference paper at ICLR 2023
log 7)² +1+
log( log(T/6),
Σ
cstz(6)nL
:)
(6)
IEJ
6²
641, (6)
7 ?
(54)
64
Combining both cases above (Eq. (53) bound
and Eq. (54)
we see that for the choice 128t,(6), the
3r
+
+
e Lnpxxd
[
- 722 (55)
4
m
(
m
4
LEJ
LEJ
always holds.
Recall by Eq.
that we have
37
(((R)) + (
eImpxxdd
f(xx) 1(x0) S
2
[(:)))
1=0
+ Tmuu p² cdd
(1087) 8
T
T + -Lm a (oo 8
T
n (a 1L)
+ TTq
8
By plugging in Eq. (55 above, as well as the choice a 1281,(8), we see that
f(x,) f(ro) < 7 + t p² did [og x
+ + .id (l08 T)*
4
T
+ ncr 2 (128t (8) + nL) log x Lo)))
We can now complete our proof by using the union bound (suppressing the dependence of some of the events å for notational simplicity) derive
P(D;) S PP()))
P(A))
+
P(G))
1=
1=0
( + 4)8
T 7
(4ty + 4)
+
5
T
Armed with Proposition 5 and Lemma 25 high probability, there can be more than T/4 e-saddle points. Combined with Proposition this yields the following result.
we are now ready to show for T sufficiently large, with
Theorem 2. Suppose we pick u, u.r, such that they satisfy the conditions in Proposition 5 and
Lemma 25 Suppose is chosen as prescribed in Lemma 25 Suppose that sb S that Suppose we pick T3 as prescribed in Proposition 5 Suppose in addition we pick
T. 2 n such that
mf
2
F
2 min
4(130ci1z(0) + eı log(T/8) +16)++) e)) 80. log(
65cg + 132c +1)
Suppose also that choose n) such that
Recall we focus on the case ø < L, since otherwise, by the L-Lipschitz assumption, Amin (V² 2 -L for all oo Rdd i.c. e-first order stationary points are also e-second order stationary points.
56

---

Under review as a conference paper at ICLR 2023
0.1 1/
7 -
2c
2x 2
(ogog)plog(T/0)) ty(0) (129 3c (16(1(CT2/8)) + 1))
Suppose
(6) ((f(z)) -f) + -f)
ypp² (f(xo) - f())
T2
256 m/
256ty(6), 1024 (56)
1762
r7
where
④ 20 (2) (60cgs (60cgg log(T/8)) (ty( (129 + Sc (1; (16((((T))))))))) +1)))
20
Then, with probability at least 1 228, there are at least 2/2 c-approximate second onder stationary points.
Proof. Consider defining the following sequence of stopping times:
== < Amin (V²)(x))) /pe),
T++1 = (n T, [f(()))] Amia ( -vpc), A1 vis (T/Ta]
We note that if T. then Tj = T for any i. Let N, denote the (random) number of saddle points encountered in T' iterations.
We observe that
decompose the function change
f(or) - f(zo)
(f(ITN,) - f(xo)) + (f(xT) (IIN,))
N.
N.
=(((m) ((x0)) + Σ (f(ITttT)))) -((x,) +
- ((Tr)T)) + (f(WT) (VTTN.
1=1
Σ (((T, ((x,,))++((()))) ((x0))
(f(r)1))) ((T +(f(xT) (xTN))
U1
U2
We first consider U1. Letting zj == DT for any j 2 T. we have that
[T/T.)
(
Σ
(J(I+,+T,) f(xT:)) 1TKT
(
Now, by Eq. 30 observe that with probability at least any < < T7T., s. we have that
(5T.+1)6 T
6T,6 (note T, 2 4), for
c5 n1 (f(E f(x,)) In S
T
nttt(()222
u'dp
log 8
+
22
64
Tqpu p² c,d [og
T 3
+ LL d
T log
T
ne, 2 + nL) log / Lop
Mu.r.T.
57

---

Under review as a conference paper at ICLR 2023
Suppose pick u, such that Mu,r. S 0.1F. Recall from Proposition that with probability at least 1/3 137,6 (f (f+++T;)- - fxx,, T -F. Choosing such that 1/3 137,5 0.3, and letting μr = 0.1F, we note that |-F + μ4| 0.9F 2 o....F Z 0.3 (Mu,r.T. + p.).
0.7
Now, let Er, denote the bad event on which neither (f(z,,+T)) f(z+)) I, S FF, nor (f(I f(x T S MU.TT S 0.1FF.
We know that e,, has probability at most ST, Let == u E such that PPEE)) S 68. Then,
T
by applying the weakened supermartingale inequality in Proposition we have
T/T. Σ
)] + + S exp F2
82
8²
P
(f(T++TT)) - ((TT,) TT -N,0.9F +
$ E
exp
44(TTT.)F²
66.
Now, pick & = 2F 2 /og(L//)T/TT, then
Σ ((0x4T.)-(zzpp L -N,0.9F 2F /log(L/0)T/T, 78.
Note that supposing for contradiction that there are at least 7/4 saddles, we must then have that N. 2 T/(4),), such that
-N,0.9F 2F Vlog(1/8)T/T.) s F(-0.9T (2V Vlog(1/8)T/T3))
F(-O.TT/)) F(-00177 < {
where we may ensure the last inequality by picking T/T, such that
T/T.- 2 0.125 Vlog(1/5) = 256 256 (lo((15).
Note that choice of T ensures this.
Thus, with probability at least - 76,
T T/T.
U
Σ (f( [(xr (rs)) --0.1//T.))) i
Next, we bound the summand U2. Recall that
N.-1 (f(rre)) I (2r+TT))
U2 = (f(x)) f(x)) Σ
Without loss of generality, we may analyze each of the summands f(xTy1)) (I in the same way as we treat (f(x,, - f(ro)). Let us then consider the summand f(2,) ) f There are two cases to consider.
1. The first is when (6). In this case, since know that |/V (as Ir, is an e-saddle point), follows by Lemma 26 that
< 7 2 ()(6)mm* 22 did3 (log 8 7) 4
T)
+ +1,(8)Ta7u$p aid (log r)
f(xm)) - f(xo)
+ +nar (128t (8) + LL) log T
+ Lxp2
with probability least (1)
T
2. The second case is when TΙ (0). In this case, by Lemma
18 we have that
o 1
T 2 + +2loog(T/))
f(x,) - f(0) <
uddPp log
64
58

---

Under review as a conference paper at ICLR 2023
+ Timu p add (1o8 4)
T 3
+ Tnp end (log =
T
+ 7 n.) log T
+ t T
8
with probability least 1
(67 T
By our choice of u, we know that
t5(ō)mu p² add [og :) 3 Sty(6)r²c + 2 + ar + 1) (T/ cr2
T + eid (log 4) + + nL) log 8 +1,(0)c 2)
(13100014 61 log(T/6) + (.).
Hence, by picking such that
2 rS ((30cg1 + (og( + t1)
follows that
t0(0mmu p² c log 5)
7)
+ +tr(6)Lof'u'p) p² end (108 5) T
4
T
+ h (128() + 11) log 8
+ (1)0 Lippp
Then, T < tf()), with probability least (3tr())+4)
((en)-f(a)) S n
Suppose also that we pick such that
pyee
F
80u (og(T/8)
65c
+ 1320, +
40n/T log(T/5)
65c
+ 13201 +
8
Then, can be verified that
2
F T
T 8 + +2 logg(T//)
2 T
(5)
u'lp log
40 T,
64
log T
T +TL did (1og
+ T Tmu p² a
+ T r2
T + Lopr?
no To
+ LL) log (128t (1)
T,
Then, by union bound, it follows that with probability at least - 98,
N
U2 = (f(x,)) -
(f(I - f(xr,+I.)
me FT T. 2
40
Therefore, by the union bound, with probability at least - 165,
T
(-0.1F + n22
F
f(ITx,) f(zo) = U, U
T;
40
By recalling our choice of F Lemma 25 by choosing 17 such that
0.1 & 7 S 2c 2. (oguploogT//))
() (16()CCT718))
59

---

Under review as a conference paper at ICLR 2023
0.11 Vpc 2
0.1F
60cg)plog(T/5)
17T2 (20
22
it follows that with probability at least 1 - 168,
f(ZTN,) - f(xo) = U1 + U2
T
-0.1F + n//222+ F
Тg
40
T
T
$ T.
(-0.1F + 0.1F/4) (-0.05F).
T.
Choose T such that
207,([(mm) - -
ppp (f(xo) 1))
-(0.551/T.)' f + T2
F >
not
yields contradiction, where
5 20 (200gg00 log (T/6)) (ty(6)) (129 + S (); (16(L)(CT))8)) (16 +
1)))
Hence, with probability at least 1 - 166, there cannot be more than T /4 saddle points. In addition, with probability at least 66, by Proposition 4 there cannot be more than 7/4 iterates with [x; 2 6. Hence, with probability at least 1 - 226, there are at least T/2 e-approximate second order stationary points.
G SIMULATIONS
We test the performance of our proposed algorithm with two-point estimators (ZOPGD-2pt against existing zeroth-order benchmarks using the octopus function (proposed in Du al. (2017) ) of varying dimensions. It is known that the octopus function defined on IRd, which chains d saddle points sequentially, takes exponential (in d) time for exact gradient descent to escape; it has thus emerged as a popular benchmark to evaluate and compare the performance algorithms that seek to escape saddle points. In experiments, compare the performance of our two two-point estimator algorithm (ZOPGD--2pt) with PAGI (Algorithm in Vlatakis- Vlatakis-Gkkaagkkaai Giaragkounis et al.] (2019)) and ZO-GD-NCF (see Zhang et al. 2022)), which are the only two existing zeroth-order algorithms that have (a) ((42)) sample complexity for escaping saddle points (with the latter algorithm yielding the tightest bounds), and (b) performed the best empirically on escaping saddle points (see the simulation results in Zhang al. 20222). We note that both PAGD and ZO-GD-NCF have use 2d function evaluations per iteration to estimate the gradient while our algorithm only needs to use 2 function evaluations. In our plots, we plot the function value against the number of function evaluations. For completeness, we also plot the performance of exact gradient descent (normalized such that its a--xxis is also the number of function queries).
We tested the algorithms for d = 10 and d = 30. To account for the stochasticity in the algorithms, for each algorithm, we computed the average and standard deviation over trials, and plotted the mean trajectory with an additional band that represents 1.5 times the standard deviation. For our algorithmá hyperparameters, we picked
1
4dL 10 20002,r--00 0.05, m = 1 i.e. two-point estimator)
(57)
For PAGD, we used the hyperparameters listed in their paper, and for ZO-GD-NCE, we used the code from their Neurips submission. We note in particular that both methods used the step-size + For initialization, we chose random 2g near the saddle point at the origin, drawn from N 11-10-1300 31axa (fixed for all trials and all algorithms).
As we can see Fig. in both cases, our algorithm reaches the global minimum of the octopus function in significantly fewer function evaluations than PAGD and 20-GD-NCK (approximately 2.5
Using the random seed in our code, note that | fzo))l 0.011 for d 10 and [[V](>))] 0.030
for = 30.
60

---

Under review as a conference paper at ICLR 2023
times faster than ZO-GD-NCE and approximately times faster than PAGD), despite our algorithm only using function evaluations per iteration compared to 2d function evaluations per iteration for both PAGD and ZO-GD-NCC As sanity check, note that the number of function evaluations required for PAGD and XO-GD-NCF to reach the global minimum approximately matches that in Figure offZhang et al. (022); here the correspondence is only approximate since /Zhang al. 2022
only plots one trial while we compute the mean and standard deviation of 30 trials.
This result suggests that in addition to the theoretical convergence guarantees, there might also be empirical benefits to using two-point estimators versus existing 2d-point estimators in the zeroth-order escaping saddle point literature.
-200
-100
Runctton value
-500
20- GD MCF
PAGD
20HGD 2:
minmuu function vo
-1000
4002
1440
5205
31000
5000
10000
11000
20000
25000
300000
35000
40000
R50000
10000
1000
20000
5500
1000
Number funczon auarics
(a) d 10
(b) d 30
Figure 1: Performance on toy octopus function, with r = e, = c, 1 (Here, T, L, are
parameters determining the properties f. Our parameter choice consistent with that in Zhang et al. 2022). See Du et al. (2017) for details about the definitions of r, L and 7.).
61


Reviews:
[{"review_id": "l1Y5MHiUdzn", "reviewer": "Reviewer_nRGh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes zeroth-order perturbed gradient descent algorithm which is the first zeroth order algorithm to the authors' knowledge that finds second-order stationary point with only $2m$ function evaluations per iteration for any $m\\in [1,d]$ ($d$ is the dimensionality), in contrast to $\\Omega(d)$ per iteration in previous similar algorithms. The total number of function evaluations is $\\widetilde{\\mathcal{O}}(d\\epsilon^{-2.5})$. New proof techniques are used to deal with small batchsize $2m$ and large variance without subGaussianity assumption. ", "summary_of_the_review": "Both the achievement in $2m$ function evaluations per iteration and the techniques to deal with small batchsize $2m$ and large variance without subGaussianity assumption look novel. The overall structure and main contribution of this paper look very clear. However, since the advantage of the proposed algorithm is not well supported, as I elaborated in \"**(my major concern)**\" above, I recommend borderline rejection. I would like to raise my rating if the authors can solve my major concern by either adding experiment or improving the total complexity as I elaborated in \"**(my major concern)**\" above. ", "strength_and_weaknesses": "Pros: Both the achievement in $2m$ function evaluations per iteration and the techniques to deal with small batchsize $2m$ and large variance without subGaussianity assumption look novel. The overall structure and main contribution of this paper look very clear. \n\nCons: The advantage of the proposed algorithm is not well supported as I elaborated in \"**(my major concern)**\" below. The proof intuition could be more direct and brief before diving into technical details, as I elaborated in \"**(my second major concern)**\" below. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Y-69NL3pDxx", "reviewer": "Reviewer_ZbmT", "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": "This paper studies the problem of escaping from saddle points, a basic problem in nonconvex optimization. Specifically, this paper considers function evaluations, i.e., zeroth-order inputs, and furthermore only 2m function evaluations are allowed in each iteration. Under such a setting, the authors give an algorithm with iteration complexity ~O(d/eps^2.5*m). ", "summary_of_the_review": "Overall, I think this is a novel work in studying zeroth-order methods for escaping from saddle points, and it could be nice to see this paper at ICLR 2023. Nevertheless, since the result has relatively large power of 1/eps and numerical experiments are absent, it also makes sense for this work to improve further and save for future conferences/journals.", "strength_and_weaknesses": "From my perspective, the most notable strength of this paper is that it is the first work on escaping from saddle points that can use fewer than d evaluation queries in each iteration. This is very much novel because first-order methods and previous zeroth-order methods essentially all use (approximate) gradient information, and it is impressive that escaping saddle points can be achieved by using few than d evaluation queries. It’s also veery nice that there is an explicit relationship between the number of function evaluations per iteration and the overall iteration complexity, expressed by m.\n\nNevertheless, the paper may still have space to improve from the following aspects:\n\n- I feel that the authors should probably give more explanations about why the current method can only achieve 1/eps^2.5 in terms of eps, and why it cannot reach 1/eps^2 (GD) or 1/eps^1.75 (AGD) at the moment. In particular, discussions about how this 2.5 is formed and the difference compared to those exponents in GD-based methods will be very helpful. Is it mainly due to having difficulty in the large-gradient scenario or when we are near saddle points (improve or localize)?\n\n- There is no numerical experiment in this paper. I think writing a code for Algorithm 1 should not be difficult since it simply takes Gaussian samples and there is only 2m evaluations in each iteration. The paper would be stronger if there are numerical results that corroborate the theoretical findings.\n\n- A typo throughout the paper: In a few places, zero-order should be zeroth-order (just imagine that we never say one-order but always first-order).\n\nAt last, I have a suggestion to the authors: It seems that the authors are mainly treating the 2m evaluations as m batches of two-point evaluations. Is it possible to consider fewer batches but more points in each batch? The observation is that Eq. (1) in Definition 3 is simply a first-order central-difference method. 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": "Om_PJZZf8x-", "reviewer": "Reviewer_QY7d", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The authors provide a best-iterate convergence rate for a zeroth-order optimization with constant number of function evaluations per iteration which can escape saddle points efficiently in order to compute a second-order stationary point. ", "summary_of_the_review": "My honest goal is to observe the discussion, since I am not convinced about the importance of the model.\nTo be more precise, why someone should not just wait to get d estimates to approximate grad with finite differences, since the final iterations \\times samples = complexity would be the same, or even better", "strength_and_weaknesses": "In order to understand if the model is really interesting, I would like to ask a model where waiting to get d samples can not be done and it is crucial to have some small progress at every round because it improves some regret quantity. Additionally, the authors claimed that adding constantly isotropic noise instead of sporadically is better, because the algorithm of Flokas et al (the optimal one in combination iteration x samples) has to check the gradient if it is small. This is wrong, by looking the referred algorithm, it examines the ''approximate gradient'', which will be used for the descent (so we have access to that for free).\n\nI am wondering, if the authors start to add a noise adaptive, if they will achieve better rate of convergence.", "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": "ExgBxBtSC8", "reviewer": "Reviewer_Rytu", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "In this manuscript, the authors generalize the well-known idea of adding perturbation to avoid converging to the saddle points in nonconvex optimization, to the zeroth-order setting in which only function evaluations are available. They also provide convergence analysis of their zeroth-order perturbed gradient method and show that to finding an $\\epsilon$ second-order stationary point, it requires at most ${\\cal O}(d/\\epsilon^{2.5})$ number of function evaluations.", "summary_of_the_review": "The results are new only in a limited regime and the existing results outperform the presented ones in the manuscript in most settings.", "strength_and_weaknesses": "It's interesting to provide analysis of zeroth-order methods in escaping from the saddle points without estimating the Hessian matrix. However, as mentioned in the manuscript, this problem has been already studied in the literature and a sample complexity of ${\\cal O}(d/\\epsilon^{2})$ has been provided. The authors argue that the major limitation of obtaining this complexity bound is to compute ${\\cal \\Omega }(d)$ per iteration. However, this is not very convincing and the proposed complexity bound in this manuscript is worse than that of the existing methods. ", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "1PH0PuBsntU", "reviewer": "Reviewer_czK6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper addresses the zeroth-order optimization of black-box functions. Due to the unavailability of gradients, gradient estimations are used. The paper proposes an algorithm as follows: at each iteration, it uses only $2m$, where $1 \\le m \\le d$ and $d$ is the input dimension, to approximate gradients. Then it adds an isotropic perturbation to the gradient estimate in order to escape from saddle points. The authors show that their algorithm can find $\\epsilon$ second-order stationary points using only $tidle{\\mathcal O} (d\\/epsilon^2.5)$ function evaluations. The idea of their convergence analysis is based on that of Jin et al. (2019a) with non-trivial modifications. If the gradient estimate is large, they show that the function can decrease even with only $2m$ evaluations at every iteration. If the current point is near saddle points, they show that there is a constant probability of making the function value decrease.    \n\n", "summary_of_the_review": "I am toward accepting this paper. ", "strength_and_weaknesses": "Strengths:\n- The paper addresses an important problem of the zeroth-order optimization. \n- The theoretical results are novel and interesting: even with 2 samples to estimate the gradient instead of $d$ samples as in existing works, we still find the $\\epsilon$ second-order stationary points after $tidle{\\mathcal O} (d\\/epsilon^2.5)$ function evaluations. This result is valuable for the high-dimensional optimization problem.\n- The approach is based on existing works but provides some new techniques.\n\nWeaknesses:\n- Although the number of evaluations to estimate gradient is reduced from $\\mathcal O(d)$ to $2m$, however, the number of evaluations for convergence guarantees increases compared to existing works. Overall, it seems that their work has no progress compared to existing works. Therefore, the parameter $m$ can be considered as a trading coefficient between the number of samples to estimate gradients and the performance of the optimization. \n- The paper is so long to estimate. I've checked some proof for the case when the gradient is large, but could not check all proofs.  \n ", "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": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject