On the Second-order Convergence Properties of Random Search Methods
Authors: Aurelien Lucchi
Antonio Orvieto
Adamos Solomou
Venue: NeurIPS 2021 Poster (2021)
Keywords: random search
derivative-free
optimization
non-convex
saddle

Abstract: We study the theoretical convergence properties of random-search methods when optimizing non-convex objective functions without having access to derivatives. We prove that standard random-search methods that do not rely on second-order information converge to a second-order stationary point. However, they suffer from an exponential complexity in terms of the input dimension of the problem. In order to address this issue, we propose a novel variant of random search that exploits negative curvature by only relying on function evaluations. We prove that this approach converges to a second-order stationary point at a much faster rate than vanilla methods: namely, the complexity in terms of the number of function evaluations is only linear in the problem dimension. We test our algorithm empirically and find good agreements with our theoretical results.

On the Second-order Convergence Properties of Random Search Methods
Aurelien Lucchi"
Antonio Orvieto
Adamos Solomou
Department of Computer Science
ETH Zurich
Abstract
We study the theoretical convergence properties of random-search methods when optimizing non-convex objective functions without having access to derivatives. We prove that standard random-searde methods that do not rely on second-order information converge to recond-ordes stationary point. However, they suffer from an exponential complexity in terms of the input dimension the problem. In order to address this issue, propose novel variant of random search that exploits negative curvature by only relying on function evaluations. We prove that this approach converges to second-order stationary point at much faster rate than vanilla methods: namely, the complexity in terms of the number of function evaluations only linear in the problem dimension. We our algorithm empirically and find good agreements with our theoretical results.
Introduction
We consider solving the non-convex optimization problem minger* f(x), where f(-) is differentiable but its derivatives are not directly accessible, or can only be approximated at high computational cost. This setting recently gained attention in machine learning, in areas such as black-box adversarial attacks [1 reinforcement learning (51), meta-learning 7 online learning (9) and conditional
optimization (57.
We focus our attention on a popular class of derivative- free methods known as random direct-search methods of directional type These methods optimize f()) by evaluating the objective function a number of (fixed or randomized) directions, to ensure descent using a sufficiently small stepsize.
Direct-search algorithms date the 1960's, including e.g. 44 46). More recent variants include deterministic direct search [5). random direct search (e.g. (54] or the Stochastic Three Points (STP)
method (6)) which randomly sample direction and accept a step in this direction if it decreases the function f(-). As discussed in [40), direct-search methods have remained popular over the years for number of reasons, including their good performance and known global convergence guarantees (54), as well as their straightforward implementation that makes them suitable for many problems. We
refer the reader to 40 15 for survey.
In machine learning, objective functions of interest are often non-convex, which poses additional challenges due to the presence of saddle points and potentially suboptimal local minima (33] Instead of aiming for global minimizer, one often seeks a second-order stationary point (SOSP): ie. solution where the gradient vanishes and the Hessian is positive definite. Indeed, shown by [14] 36 22 221, many machine learning problems have no spurious local minimizers, yet have many saddle points which yield suboptimal solutions and are often hard to escape from [99 While convergence to SOSPs and saddle escape times have been extensively studied in the context of
Alphabetical ordering, all authors contributed equally. In this manuscript, will use the terms "random direct-search" and "random search" interchangeably.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

gradient-based methods [32 16 10 561, prior analyses for (random) direct search have mainly focused on convergence to first-order stationary points 6 54] One exception is the Approximate
Hessian Direct Search (AHDS) method [26], that explicitly computes the Hessian of the objective to obtain second-order worst-case guarantees. However, computing or storing a full Hessian is prohibitively expensive in high dimensions.
Towards better understanding of the complexity of finding second-order stationary points with random search methods, we make the following contributions:
We study the complexity of a simple random search similar to STP (Algorithm[) 1 to reach SOSPs. We find that the (worst-case) complexity requires number of function evaluations that scales exponentially in terms of the problem dimension d. As we will see, the exponential scaling is not an artefact of the analysis. This is intuitive, indeed, if we are at a saddle point where we just have one direction of negatíve curvature, finding good alignment with a random direction becomes exponentially difficult as the dimension of the space increases.
To solve this issue, we design a variant of random search (RSPI, Algorithm 2 that, instead of randomly sampling directions from the sphere, relies on an approximate derivative-free power iteration routine to extract negative curvature direction candidates (unlike (26) that requires an approximation to the full Hessian). This approach is inspired from recent work on gradient-based methods for finding SOSPs [T. 56) and effectively decouples negative curvature estimation from progress in the large gradient setting, As result, RSPI does not suffer from the exponential scaling of the vanilla random search approach: we show that the overall complexity of finding a SOSP in terms of function evaluations becomes linear in the problem dimension.
Finally, we verify results empirically and compare novel algorithm to standard random- search methods. Our results show improvements of RSPI both in terms of algorithm iterations and (crucially) wall-clock time.
2 Related work
Direct-search methods that approximate gradients A wide variety of algorithms enter the class of DFO methods. One common distinction is made according to whether or not the algorithm explicitly computes gradient approximation. Direct-search (DS) and pattern-search (PS) methods only rely on function evaluations to validate a step along a direction, sampled according to some scheme. In contrast, second group of methods explicitly compute gradient approximation [48]
23 Most methods in the latter group rely only on first-order information, except (58] that
incorporates some second-order information compute an estimate of the gradient. However, their approach focuses on convex optimization and therefore does not discuss second-ord -oooer stationarity. Instead, (55) showed that O 2) approximate gradient computations are enough to reach an e SOSP.. Unlike DS, the gradient-free method analyzed in (55) computes an approximation of the gradient and, as a result, it matches the convergence rate guarantees of their exact gradient-based counterparts (up to constants). However, existing lower bounds clearly show that DS methods have a worst rate of convergence. Of special interest to us is the complexity w.r.t. the dimension of the problem, which is exponential, see paragraph "Lower bounds" below.
First-order guarantees of DS. A recently proposed variant of DS is the stochastic- points (STP) approach proposed in 66 that simply samples direction at random on the sphere and accepts the step if it decreases the function. This is, in some sense, a simpler variant of direct search compared to adaptive methods such as [54] that also include an adaptive mechanism of the step-size selection to ensure convergence without having to rely on knowing certain quantities such as the smoothness constant of the objective. As shown in (6), finding point x such that with STP requires ((de-2) function evaluations. If instead the perturbation directions are sampled from a fixed basis and not from the unit sphere, the best known complexity increases to O(fe--) [54] (). Ignoring the dependency on the dimension, these results match the iteration complexity of steepest descent [47).
|| < [V]((
Second-order guarantees for PS and DS. Second-order convergence guarantees have been developed in the context of (generalized) pattern search (GPS) methods, which share similarities with direct search methods. These methods sample update directions from positive spanning set D. The work of [I] proved type of "pseudo-second-ordee stationarity condition for GPS, where

---

the Hessian is positive semidefinite in the directions of the basis D (but not with respect to all vectors in the space). A variant of GPS that explicitly constructs an approximate Hessian was shown by [2] to converge to second-order stationary points under some assumptions on the quality of the approximation. The results discussed so far typically consider the properties of the limit points the sequence of iterates and do not provide worst-case complexity rates of convergence. In contrast, [26) proved convergence to a second-order stationary point as well as derived worst-case guarantees (upper bounds only) for variant of direct search approach that constructs an approximate Hessian matrix using a finite difference approach.
Model-based approaches. Model- methods construct function approximation which is used to compute the next step and updated at every iteration. The literature on such methods is broad and refer the reader to [38] for survey of the relevant work. To the best of knowledge, these methods also require an approximation of the Hessian to obtain second-order guarantees.
(59 24 show that random search suffers from exponential dependency the dimension of the problem. Similar results are discussed in (20) for derivative-free methods that use two function evaluations to approximate derivatives. These results serve motivation for this work
Lower bounds.
to improve the complexity of random search methods in terms of the input dimension. We mostly focus on designing new type of random search that achieves better worst-case guarantees than existing lower bounds for vanilla random search.
Inexaet Power Iteration.
Computing the largest eigenvector of a matrix has many applications in statistics and data analysis. Iterative methods such as the power iteration and the Lanczos algorithm are commonly used to solve this problem 225. Perhaps the most complete and up-to-date analysis of
convergence of inexact power methods for eigenspace estimation can be found in [5] [9]. Crucially, these convergence rates depend on the eigenvalue distribution. If one instead only seeks a direction aligned with a suboptimal but large eigenvalue, the rate becomes independent of the eigenvalue distribution [3]. Alternatively to the power method, stochastic methods such as Oja's algorithm [49 benefit from a cheaper iteration cost. Improvements have been proposed in [52] that analyzes a variance reduced method that achieves a linear rate of convergence. An accelerated variant of stochastic PCA is also proposed in [18].
3 Analysis
We work in Æd with the standard Euclidean norm ||. Our goal is to optimize twice continuously differentiable non-conver function f(-): Rd - R without having access to gradients. We need the following assumption, standard in the literature on SOSPs 33 also in the DFO setting (55).
Assumption 1. The function f(-) is lower bounded, smooth and -essaan Lipschitz.
In line with many recent works on non-convex optimization [32 35 34 16
10 55 our goal is to
find an (e, -ecoondd-rr stationary point (SOSP), i.c. a point x such that:
[x) and Amin (
-7,
with y > O. We analyze two different DFO algorithms: (1) a two-step random search method (RS, Algorithm [T- similar to STP [6] and (2) a novel random search method (RSPI, Algorithm 2 that extracts negative curvature via Algorithm 3 We show that, while the approximation of negative eigendirections requires extra computation, the overall complexity of RSPI find a SOSP is much lower than RS in terms of number of function evaluations.
Theorem 1 (Main result, informal). The complexity - in terms of number of function evaluations of vanilla Random Search (similar STP, Algoritium [] for finding second-order stationary points depends exponentially on the problem dimension (see Lemma and Theorem 5)
This dependency can be reduced to linear by computing approximate negative curvature direction see Theorem 70p.
at each step (i.e. Algorithm
2
We will use O()). ((), 26-) to hide constants which do not depend on any problem parameter.
3.1 Two-step Random Search
We analyze variant of random search that uses a strategy consisting of two steps designed to maximally exploit gradient and curvature. We will use this variant as surrogate for vanilla random searches such as STP [6] that only use step. We note that the convergence rate of the latter
3

---

approach does not theoretically outperform the two-step approach since the gradient step is the same in both approaches. Algorithm I shows that the two-step random search samples two symmetric perturbations from a sphere in R with some radius, and updates the current solution approximation X; if one of the two perturbations decreases the objective function. The sampling procedure is repeated twice at each iteration, using different sampling radii Φ1 and d2- One sampling radius (a, is tuned to exploit the gradient of the objective function while the other (02) is tuned to exploit negative curvature. One could also interpret the two steps although we explicitly write down the two steps for pedagogic reasons. Note that, in our analysis, the values di and d2 are constant, although as is typically the case with step-sizes in gradient-basse analysis into two cases: one for the case when the gradient is large and the other when we are close to a strict saddle (i.e. we still have negative curvature to exploit).
one step algorithm with an adaptive step-size,
will see that in practice, decreasing values can be used, methods (see experiments). We divide the
Algorithm TWO-STEP RANDOM SEARCH (RS).
Similar to the STP method (6. but we alternate between two perturbation magnitudes: is set to be optimal for the large gradient case, while optimal escape saddles.
1: Parameters 01 02 0 (see Theorem 5
2: Initialize X at random
3: for k =0, 2, ........ 2K do
4: Sj 5 (uniformly)
5: X arg f fxx + 01s)),
# Gradient step
6: 82 ~ Sd-1 (uniformly)
7: Xk42 arg ( f(x41 + 0282), f(x d282)}
# Curvature step
8: Optional: Update o and d2 (see experiments)
9:
end for
Case 1: Large gradients. First we consider the case V f(x)l 2 Under this assumption, the stepsize can be tuned to yield a decrease proportional to e/dd.
Lemma 2. Let f()) be -smoohh and
V [xxx)l Algorithm with 0n < </( yields
Eff 1 (xxx) xxs] I -Ω L where E[- [x.] denotes the conditional expectation w.r.. x
The proof follows directly from Lemma 3.4 in and is presented in the appendix.
Case 2: Close to strict saddle. We now address the case where [x)]] < e but Amin (v) < -y, with 7. >> 0. Similarly to the analysis of gradient-basee methods [33 39]. our approach consists in first approximating fxx) around x with quadratic f(x), and then bounding the error on the dynamics. Hence, our first task is to estimate the probability of having a decrease in function value with a single step of random search around a quadratic saddle.
Lemma 3 (Curse of dimensionality of RS around saddle). Consider a d- d-dimensional (d 2 4) quadratic saddle f() cen- tered at the origin with eigenvalues X1 2 ... 2 Nd. with Da < O. Set := |>al and L, == max (>1, 12ll (cf. defini- tion SOSP in Equation 7). Starting from the origin, random step S2 ~ Sd-1 (o2) is such that
20/H0a clutakk 10)
Figure I: Behavior of a step of vanilla random search on a quadratic saddle centered at the origin. The Hessian has - 1 positive cigenvalues equal to 1 and one negative eigenvalue equal Aa. Plotted is the probability of decrease (le6 runs) of least [Aal/2 starting from the origin (a. = 1). Per- formance degrades exponentially with the problem dimension, predicted by Lemma 3
Pr (r(s(s)) f(0) - 2/2
2
(2)
4L1
Moreover, if A1 = A2 = ... = Ad-1 > 0 (worst case sce-
mario), we also have
Pr [(22) f(0) < 7 0 0 (2-dvV))
(3)
Such tuning is optimal, please refer the proof for details.

---

The proof is presented in the appendix and is based on arguments on the geometry of nigh-dimensional spheres: finding an escape direction at random becomes increasingly hard as the dimension increases.
Lemma provides both an upper and a lower bound on the expected number of function evaluations needed by vanilla random search to escape saddle. As it is the case for vanilla gradient descent (19), the complexity grows exponentially with the dimension. We emphasize that the exponential depen- dency itself is not new result (see Section 2 and that can be extended to hold globally (not only for one step) [59]. We will use the upper bound of Lemma 3 to derive a new result in Theorem S that proves convergence to second-order stationary point.
Further, we note that, for the bounds in Lemma 3] the decrease in function value is proportional to of - yet the decrease probability is independent from ož. This might seem unintuitive at first, but is simply due to the radially isotropic structure of quadratic landscapes. However, the landscape around X₃ is only approximately quadratie under Assumption [ we have (for a proof please refer to (3 that [y( f(x)) I lIy x|I for all x, Rd Hence, in order lift the bound the (1/ L2),
). so that the quadratic approximation remains valid. The proof of the next result can be found in the appendix.
non-quadratic case we need to consider "small" perturbations
Lemma 4. Let f()) be Lm-smooth and Lz-Hessian- Je-Hessian-Lipschit.. Assume [ S e and Amin 2 f(xx)) S -y 22/3, Then Algorithm with 02
2/3
is s.t.
2hg
E[f(x*+1) - f(xx)) S -
(4)
4L1
With surprise, see that the exponential complexity already found for the quadratic case in Lemma direecly influences the magnitude of the per-iteration decrease. We remark that the choice
? 2/3 is optimal for our proof, based on Hessian smoothness (see proof of Lemma & 7).
Joint analysis.
We define the following sets that capture the different scenarios:
Ai {x: [x)] 2 e); A2 = {x [V < and Amin (V (x)) )
By Lemma 2 and we have that for any X Ai A2, Equation Sholds the bottleneck scenario being A2. Since under Assumption the function is lower bounded and Algorithm is a descent method, we get convergence in a finite number of steps an SOSP.
Theorem 5.
Fix the desired level of accuracy > Assume f()) satisfies Assumption 7 Two-step RS (Alg. I with parameters order stationary point in O (2 function evaluations, where = (L1/7)) = -2/3)
L A and 2/3
2L2 returns in expectation 2/3) )
3.2 Power Iteration Random Search
The purpose of this section is to modify vanilla random search to reduce the exponential dependency of the convergence rate on the problem dimension, illustrated by the lower bound in Lemma 3] We propose a new type of random search that is coupled with a Serivativee-fre routine (named DFPI) in order to overcome the curse of dimensionality. We note that this type of "hybrid" method is not completely new in the literature, see e.g. [26). but in contrast to prior work, the computational cost of the DFPI routine in terms of the input dimension is low. This is achieved by computing an approximation of the eigenvector corresponding to the most negative eigenvalue of the Hessian based on a noisy power method (29]. which is inspired from recent works Hessian-free negative curvature exploitation techniques in gradient- optimization [41] 10].
rundoom clirection
DFPI disection
Figure 2: Difference between the two procedures to generate #2 when initial- ized at quadratic saddle (blue small values). Each magenta point is ran- dom update direction So ~ Sd (left) or the result of the DFPI procedure with 3 iterations (right).
The resulting method shown Algorithm 2 and the DFPI routine is presented Algorithm
'Let V be an event that happens in trial with probability Then the expected number of trials to first occurrence of V is 1/p.
5

---

We highlight that RSPI does not require computation and storage of the full Hessian (in contrast to AHDS that performs df function calls). We instead approximate only the leading eigenvector using approximate zero-order Hessian-vector products (ss d log d function calls: Lemma 9). This provides a large speed-up high dimensions, see wall-clock times reported later.
Algorithm 2
RANDOM SEARCH PI (RSPI).
Same structure as Alg. | only difference is in line 6: the curvature exploitation step is based on perturbation sampled from non-isotropic distribution aligned with negative cigendirections, computed by Alg ssee Fig
1: Parameters 01, 02
(see Thm 10
2: Initialize Xg at random
3: for k 0, 0, 4, .......22.. 2K do
4:
S (uniformly)
5: Xt+1 arg m f(x 01s1), f(x: 0181))
6: 52 = (FPI 5- Algorithm 3
7: X++2 (xe((((x+1) [(x+1 + 0282), f(x++1 0282)}
8: Optional: Update and 02 (sce experiments)
9: end for
Algorithm 3 DERIVATIVE- FREE POWER lTTRRATION (DFPI)
noisy derivative free power method to approximate negative curvature directions, as shown Lemma Every iteration of DFPI requires 4d function evals, hence the routine requires KDEVI 4d7brm function evals overall.
1: Parameters r. 77 > O and TOM Z (see Theorem 10
2: INPUTS : E R
3: (0) ~ -dd-1 (uniformly)
4: for t 0... T To
do
f(x+r (0 +00,) f(x+ros -c0;
5: Set g+
6: Set g = Σ
(0)
+00)) f(x
20
e
1=1
7: Update: 82 ((+1)
(1)
8+-8-
81
2r
8: Normalize 8/2
((+1)
82
(1+1)
//|s
/||s
[1+1)
9: end for
(Tbre)
RETURN S2
As in the last subsection, we split the analysis into two cases. First, in the case of large gradients, simply re-use the result of Lemma 2 The second case (sufficient negative
iee. [x)]] 2 c, curvature) requires to show that the vector 82 returned by the DFPI procedure (Alg. 3) yields decrease of the objective.
Exploiting negative curvature close to saddle. We consider again the case where || [x S
and Amin (V2 fxxx) < -y. We saw in Lemma that isotropic sampling in the neighborhood of X5 provides a function decrease only after an exponential number of iterations, in the worst case. We show that if the perturbation is instead sampled from a distribution which satisfies the next assumption, the number of required iterations drastically decreases.
Assumption 2. Consider x s.i. Amin 2V2 (x)) < --) The direction S2, output of DFPI after KoeFi function evaluations, returns in expectation a good approximation to the most negative eigenvalue of 2 f(x). Specifically, E(s 2 2 f(x)s2) Amiu ( fx)) + 3.
This assumption which will soon formally validate is motivated by the fact that DFPI is an approximate (noisy) power method on A(x) := - f hence can be used to estimate the maximum eigenvalue of (xx) which is minimum eigenvalue of f2) if S 1/L
Lemma Let f() be smoohh and L Jz--Hesiian-ippshiie The iteration of DFPI can be seen as a || = Or In particular, ! + 0 as r, ş - 0; hence the error can be made as small as needed within the limits of numerical stability. In addition, if f() is quadratic, we have ( 0.
step of noisy power method: s (t+1) = 2I (x))ss())s -urpp with

---

The proof is presented in the appendix. The bound on e()) is enough for us to apply the well-known convergence rates for the noisy power method 29 and to motivate a (log((d) bound on the DFPI iterations needed to satisfy Assumption 2 Before diving into this, show that directly using Assumption actually makes the iteration complexity dimension independent.
Lemma 7. Let f()) be Lmssoothh and Aeteesssinn-ipschiie and assume [ Σ c andd
Amin V2 f(xx)) S - -e/3. Under Assumption RSPI (Algorithm 2 with d2 = 21a (choice
Theorem 5) yields E[f(x++1) - [xx] [)((")), independent of the problem dimension.
Iteration complexity. We now combine Lemma 2
and
Proposition 8. Fix the desired level of accuracy >> O. Assume J() satisfies Assumptions
7 and ?
RSPI (i.e. Alg. 2 with parameters di L.v2nd and 02 21g
2/3
(same choice as Theorem returns
in expectation an (c, (2/3))ssccondorrte stationary point in O (c-2) iteeaations
While Proposition X shows that the number of RSPI independent of the problem dimension, it hides the number of function evaluations needed for the assumption to hold. To include this into the final iee. to drop Assumption 2 we need bound for convergence of noisy
Overall number of function evaluations. iterations is, conditioned on Assumption 2
complexity (Theorem 10p power methods
Lemma 9 (Consequence Corollary 1.1 in [29]] ). Let the parameters of DFPI be such that the error
Somm is small enough (always possible, as shown in Lemma Let n 1/L, Let ? 2//3, for a
fixed RSPI iteration, ToPM O 2/3 L2 log ()) DFPI iterations are enough ensure validity
of Assumption 2 al X5 with probability go(1) ((4)
derivation is included for completeness in the appendix. We are ready state the main result.
Theorem 10. Fix the accuracy > 0. Assume f(-) satisfies Assumption
1 Algorithm 2 with
2/3 parameters LIv2nd and d2 21 (same choice as Theorem 5 combined with DFPI (Alg. 3
with parameters S 1/L1, Tukm = O (c-21/3,, L, log(d) and c, sufficiently small, returns in
3/3
expectation an (e, ( stationary point in O (e -8-3 (/ [nd)) function evaluations.
Proof. Fix s.t. the probability of success p == 1 50(1) e R(d) = O(1) in Lemma 9 is
positive. The number of function evaluations needed for Lemma 9 to hold in expectation at each
step (i.e. the burden of Assumption 2b is then Kom/p O (e 273 Lidlog(d)) We conclude by
Proposition g
Significance and Novelty of the analysis. To the best of our knowledge, the result in Theorem 10 is the first to prove convergence of a type of random search to second-order stationary point with a linear dependency the input dimension. Our experimental results (section(4) confirm this significant speed-up is observed in practice. The analysis presented in appendix relies on some new geometric arguments for digh-dimensional spaces coupled with more classical optimization bounds. We again emphasize that the analysis technique is different from gradient-frea methods that approximate the gradients. For instance [55] define the error between the approximate gradient q( hy) and the exact gradient V f(xx) as ég q( (x)) V f f(xx). They then require this error to be bounded, iee. |eR] S cn ca| where en a constant and is the size of the step used in the finite difference formula. The constant с₁ is directly controlled by h and can be made small as possible to better approximate the result of the gradient- based method. In our case, the update direction is sampled at random, and we therefore have to rely on different proof technique that involves probabilistic geometric arguments in high-dimensional spaces.
'The dependency on the dimension will however show in the final number of function evaluations (Theo- l0p. However, such dependency not exponential even in the worst case.
7

---

How to further speed up DFPI with SPSA. Each DFPI iteration requires 4d function evaluations. While this complexity is necessary to build an arbitrarily good finite difference (FD) approximation of second order information (needed by Lemma 9. in practice more rough estimate of Hessian-vector products can be obtained using cheap randomized techniques. In particular, in the experiments in the next section, we show that an SPSA estimator [53] of g+ and g- is in fact sufficient to achieve acceleration in the performance with respect to the two-step random search. In particular, SPSA
f(xtra! ( 4-0)- f(xxxx - e,; where r, e > 0 and is a vector of 2nd,
computes g+ g as
d random variables, often picked to be symmetrically Bernoulli distributed. SPSA is asymptotically unbiased and only requires function calls, as opposed to the 4d needed by FD. However, the variance of SPSA does not arbitrarily decrease to zero as C, r vanish, as it is instead the case for FD: it saturates [3 As result, Lemma 9 would not always hold. In the appendix, we provide an extensive comparison between FD and SPSA for DFPI: we show that, for the sake of Assumption 2 the error in the SPSA estimator is acceptable for our purposes, for small enough (see use in Alg. 3
4 Experiments
In this section we verify our theoretical findings empirically. Specifically, we set two objectives: (I) to evaluate the performance RS and RSPI, to verify the validity of Theorem []] and (2) to compare the performance of these two methods against existing random search methods. For the latter, we run the two-step Random Search (RS) and Random Search Power Iteration (RSPI) against the Stochastic Three Points (STP) method, the Basic Direct Search (BDS) [54] and the Approximate Hessian Direct Search (AHDS). We recall that AHDS explicitly constructs an approximation to the Hessian matrix in order to extract negative curvature. Descriptions of each algorithm are provided in the appendix.
Setup. All experiments follow similar procedure. In each task, all algorithms are initialized at strict saddle point and executed for the same number of iterations. We report the optimality gap as a function of iterations and wall-clock time. Additionally, we report the norm of the gradient vector in the appendix. Since all algorithms are stochastic, the experimental process is repeated multiple times (wherever possible using different saddle point as initialization) and the results are averaged across all runs. For each task, the hyperparameters of every method are selected based on coarse grid search refined by trial and error. For RS and RSPI the parameters 01 and d2 initialized and updated in the same manner, hence the only difference between the two is that RSPI extracts negative curvature explicitly whereas the two-step RS samples a direction at random (see Figure D
We choose to run DFPI for 20 iterations for all the results shown in the paper. Empirically, observed that performing more iterations does not further improve the overall performance of RSPL. The hyperparameters used for each method are provided in the appendix and the code for reproducing the experiments is available online
Function with growing dimension. (see App. for illustration)
We start by considering the following benchmarking function
f(z1. 3)
+ I
(5)
1=1 2
1=1
which has a unique strict saddle point (i.e. with negative curvature) at P1 (0..... (0. 0.00) 0) and two global minima at P2 = (I,.... 1, and P3 = (-I....,-1, -1. The results in Fig. 3 illustrate that both the two-step RS method as well as the RSPI algorithm are able to consistently escape the saddle across all dimensions. While in oin-dinensional settings (d = 3) the RSPI algorithm is outperformed by the two-step RS and the AHDS in terms of their behavior as function of run-time, the situation is clearly reversed as the dimensionality grows. For d = 100, 200 the two-step RS achieves progress
very slow rate and high number of iterations is needed in order achieve convergence to a second-order stationary point. In contrast, RSPPI successfully approximates the negative curvature of the objective efficiently escape the saddle point, allowing the algorithm to achieve progress at a faster rate. The fact that for d d== 5 the AHDS algorithm requires less time than RSPI converge to a second-order stationary point, indicates that in low-dimensional settings the cost incurred by the power iterations within RSPI is higher than the cost of approximating the entire Hessian matrix. However, for higher values of d, AHDS quickly becomes inefficient and expensive. Further, STP performs worse than RS, simply because it employs only one sampling radius (RS uses two).
8

---

Figett Oivensiee
Hoy Diresdon13
Iyed Disensee 1e0
Divenonn 280
177
A105
80
80
1a
190
190
70
177
028
Figure 3: Performance while minimizing the objective in Eq. (5) for different d. Confidence intervals show min-max intervals over ten runs. All algorithms are initialized at the strict saddle point across all runs. For d= = 100, 200, the lines for STP, BDS and AHDS overlap each other none of the methods achieve progress in terms of function value.
Rastrigin function. Next, we conduct experiments on the Rastrigin function, popular benchmark in the literature 28 For any x E RRd, the d-dimensional Rastrigin function is defined as
d
f(x) = 10d +
(a? 10 cos((2T;)))
(6)
E=1
The function has a unique global minimizer at x" = O, whereas the number of stationary points (including striet saddles) grows exponentially with d. Based on Lemma expect that having single direction of negative curvature will challenge the core mechanism of each algorithm while trying to escape the saddle. To that end, ensure that at each initialization point there exist single direction of negative curvature across all settings of d. More details about the initialization process the results
and the implications The results in Figure illustrate the strong empirical performance of RSPI, not only in comparison to the two-step RS algorithm but also against the rest of the algorithms. RSPI successfully approximates the single direction of negative curvature and escapes the saddle point after one iteration. On the contrary, the two-step RS achieves minimal progress even for low dimensional settings, whereas for d = 20 it requires more than 300 iterations to escape the saddle (see the gradient norm plot in the appendix). For higher dimensional settings, two-step RS does not escape all, supporting our theoretical argument that as the problem dimension grows the probability of sampling a direction that is aligned with the direction of negative curvature decreases exponentially. Lastly, both BDS
given in the appendix.
Ingst Oinaraice 30
rrstt Dinurabn 20
Irput Oliannaioonnnoo 103
Fipit Dimmnsooon 200
2
30'
30
2/5
200
300
220
1
304
305
3474
187 1002
10 0100
1000 K000
Figure 4: Optimality gap on the Rastrigin function function of iterations (top) and running time (bottom). Confidence intervals show min-max intervals over ten runs. All algorithms are initialized at strict saddle point and executed for a total of 500 iterations across all runs, however for d' = 100, 200 no further improvement is achieved after 25 iterations.

---

10a
10-
15r
10
12F
RS
R5
10-1
BDS
10P
BD5
10
AHDS
AHDS
2000
6000
6000
5000
10000
50
100
150
200
250
300
350
400
Beration (k)
Time (sec)
Figure 5: Empirical performance in finding the leading eigenvector of a 550-dimensional random matrix.
Confidence intervals show min-mas max intervals over five runs. All algorithms are initialized at strict saddle point.
and AHDS consistently escape the saddle point across all values of d. However, their performance remains suboptimal compared RSPI.
Leading eigenvector problem. Finally, we consider the task of finding the leading eigenvector of positive semidefinite matrix M Rdxd The problem is equivalent to minimizing f f(x ||xx _ M [4]. Figure S shows the empirical performance in finding the leading eigenvector of 350-dimensional random matrix. While an iteration level AHDS appears to very effective, when the iteration complexity of each method is taken into account it is the slowest to escape. Notably, single iteration of RSPI takes (on average) 0.06 seconds, whereas a single iteration of AHDS takes approximately 9.01 seconds. This experiment clearly illustrates the computational advantages that RSPI provides while provably ensuring convergence to second order stationary points.
Conclusion
We analyzed the convergence of two types of random search methods. The first approach is slight variation of standard random search that converges to second-orde stationary point but whose worst- case analysis demonstrates exponential complexity in of the function input dimension. The second random search approach we propose extracts negative curvature using function evaluations. Importantly, the dependency in terms of the function input dimension becomes linear, a result which we clearly observed in our experimental results, especially in terms of run-time.
There are number of avenues pursue as future work. To start off, (1) a simple extension would be to allow DFPI to store multiple candidates for negative eigendirections. As discussed in [45 and formally shown [27], this can directly boost performance. Similarly (2) one could study the application of zero-th order version of Neon (56). (3) It would be then interesting to also understand if injecting noise the process (additional exploration) can help in escaping saddles [19]. (4) Further, instead of using constant values predefined schedule for σi and d2 could analyze the commonly used adaptive strategy where these values are adapted according to whether the function is being decreased [54). (5) We note that one could in principle relax Assumption ! and instead work with a smoothed version of f()). without requiring differentiabilityy. (6) Finally, would be interesting benchmark DPFI other machine learning problems, including for instance reinforcement learning tasks where random search methods are becoming more prevalent [43 42).
Another potentially interesting direction would be extend our analysis random search methods for min-max optimization problems 3
Broader impact statement. We consider work fundamental research the principles of learning in high dimensional systems. Hence a broader impact discussion is not applicable.
References
[1] Mark Abramson. Second-order behavior of pattern search. SIAM Journal on Optimization, 16(2):115-530, 2005.
[2] Mark A Abramson, Lennart Frimannslund, and Trond Steihaug. A subclass of generating set search with convergence to second-order stationary points. Optimization Methods and Software, 29(5):900-918 2014.
10

---

[3] Konttioiionttnnnnnss Anagnostidis, Aurelien Lucchi, and Youssef Diouane. Direct-search for class of stochastic min-max problems. In International Conference on Artificial Intelligence and Statistics, pages 3772-3780. PMLR, 2021.
[4] Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Ayush Sekhari, and Karthik Sridha- ran. Sedend-order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, pages 242-299, PMLR, 2020.
[5] Maria-Florina Balcan, Simon Shaolei Du, Yining Wang, and Adams Wei Yu. An improved gap-dependency analysis of the noisy power method. In Conference on Learning Theory, pages 284-309. PMLR, 2016.
[6] El Houcine Bergou, Eduard Gorbunov, and Peter Richtarik. Stochastic three points method for unconstrained smooth minimization. SIAM Journal on Optimization, 2020.
[7] James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research, 13(2), 2012.
[8] Ekaba Bisong. Google Colaboratory, pages 59 64. Apress, Berkeley, CA, 2019.
[9] Sébastien Bubeck and Nicolo Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. arXiv preprint urXi:: 2012.
[10] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal on Optimization, 28(2):1751-1777 2018.
[11] Pin- Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 15-26,
2017.
[12] Yuwen Chen, Antonio Orvieto, and Aurelien Lucchi. An accelerated dfo algorithm for finite-sum convex functions. In Proceedings of the 30th International Conference on Neural Information Processing Systems, 2020.
[13] Wing-Sum Cheung. Generalizations of Hölder's inequality. International Journal of Mathemat- ics and Mathematical Sciences, 26, 2001.
[14] Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. Artificial intelligence and statistics, pages 192-204, 2015.
[15] Andrew R Conn, Katya Scheinberg, and Luis N Vicente. Introduction to derivative-free optimization. SIAM, 2009.
[16] Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. Escaping saddles with stochastic gradients. arXiv preprint /803.00000..5505 2018.
[17) Chandler Davis and William Morton Kahan. The rotation of eigenvectors by perturbation. iii. SIAM Journal on Numerical Analysis, 7(1):1 1970.
[18] Christopher De Sa, Bryan He, Ioannis Mitliagkas, Christopher Ré, and Peng Xu. Accelerated stochastic power iteration. Proceedings of machine learning research, 84:58, 2018.
[19] Simon S Du, Chi Jin, Jason D Lee, Michael Jordan, Aarti Singh, and Barnabas Poczos. Gradient descent can take exponential time to escape saddle points. In Advances neural information processing systems, pages 1067-1077, 2017.
[20] John C Duchi, Michael Jordan, Martin J Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5):2788-280) 2015.
[21] Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, pages 1233-1242. PMLR, 2017.
11

---

[22] Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 2981-2989 2016.
[23] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4))234122688, 2013.
[24] Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee, Xingyou Song. et al. Gradientless descent: High-dimensional zeroth-order optimization. arXiv preprint arXiv:1911.0631] 2019.
[25] Gene H Golub and Charles F Van Loan. Matrix computations, 4th. Johns Hopkins, 2013.
[26] Serge Gratton, CW Royer, and Luis Nunes Vicente. A second-order globally convergent direct-search method and its worst-case complexity. Optimization, 105)):10551128, 2016.
[27] Ming Gu. Subspace iteration randomization and singular value problems. SIAM Journal on Scientific Computing, 37(3) 2015.
[28) Nikolaus Hansen, Steffen Finck, Raymond Ros, and Anne Auger. Real-Parameter Black-Box Optimization Benchmarking 2009: Noiseless Functions Definitions. Research Report RR-6829, INRIA, 2009.
[29] Moritz Hardt and Eric Price. The noisy power method: A meta algorithm with applications. In Advances in Neural Information Processing Systems, pages 2861-2869, 2014.
[30] John Hopcroft and Ravi Kannan. Lecture notes: Computer science theory for the information age. Citeseer, 2012.
[31] Kaiyi Ji, Zhe Wang, Yi Zhou, and Yingbin Liang. Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization. arXiv preprint arXiv: 12/6,, 2019.
[32] Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1724 1724-1732. JMLR. org, 2017.
[33] Chi Jin, Praneeth Netrapalli, Rong Ge. Sham M Kakade, and Michael I Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. arXiv preprint arXiv:1902.04811 2019.
[34] Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M. Kakade, and Michael I. Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. arXiv: Learning. 2019.
[35] Chi Jin, Praneeth Netrapalli, and Michael I Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference On Learning Theory, pages 1042-1085. PMLR, 2018
[36] Kenji Kawaguchi. Deep learning without poor local minima. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 586-594, 2016.
[37] Jacek Kuczyáski and Henryk Wožniakowski. Estimating the largest eigenvalue by the power and Lanczos algorithms with random start. SIAM journal on matrix analysis and applications, ((4)):094-1122 1992.
[38] Jeffrey Larson, Matt Menickelly, and Stefan M Wild. Derivative-fre optimization methods. arXiv preprint 1rXXiv1904.110 11585, 2019.
[39] Kfir Y Levy. The power of normalization: Faster evasion of saddle points. arXiv preprint 1rXiv:1611.0483/ 2016.
[40] Robert Michael Lewis, Virginia Torczon, and Michael W Trosset. Direct search methods: then and now. Journal of computational and Applied Mathematics, 124(1-2):191-200 2000.
[41] Mingrui Liu and Tianbao Yang. On noisy negative curvature descent: Competing with gradient descent for faster non-convex optimization. arXiv preprint arXiv:1709.08571, 2017.
12

---

[42] Niru Maheswaranathan, Luke Metz, George Tucker, Dami Choi, and Jascha Sohl- Sohl-Dickstein. Guided evolutionary strategies: Augmenting random search with surrogate gradients. In International Conference on Machine Learning, pages 3264-4274 PMLR, 2019.
[43] Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search provides a competitive approach to reinforcement learning. arXiv preprint
2018.
[44] J Matyas. Random optimization. Automation and Remote control, 26(2):246 253, 1965.
[45] Cameron Musco and Christopher Musco. Randomized block Krylov methods for stronger and faster approximate singular value decomposition. In Proceedings of the 28th International Conference on Neural Information Processing Systems-Voluum 1, pages 1396-1404, 2015.
[46] John A Nelder and Roger Mead. A simplex method for function minimization. The computer journal, 7(4):308-313, -33,, 1965.
[47] Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018.
[48] Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2)5227-566 2017.
[49] Erkki Oja and Juha Karhunen. On stochastic approximation of the eigenvectors and eigenvalues of the expectation of random matrix. Journal of mathematical analysis and applications, 106(1):69-84, 1985.
[50] Mark Rudelson and Roman Vershymin. Smallest singular value of random rectangular matrix. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62(12):1077-1733 2009.
[51] Tim Salimans, Jonathan Ho, Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies scalable alternative to reinforcement learning. arXiv preprint 1rXiv:1703.0884, 2017.
[52] Ohad Shamir. A stochastic PCA and SVD algorithm with an exponential convergence rate. In International Conference on Machine Learning, pages 144-152, 2015.
[53] James C Spall et al. Multivariate stochastic approximation using a simultancous perturbation gradient approximation. IEEE transactions on automatic control, 37(3):332-341, 1992.
[54] Lufs Nunes Vicente. Worst case complexity direct search. EURO Journal on Computational Optimization, 1(1-2):143-13, 2013.
[55] Emmanouil-Vasileii Vlatakis- Gkaragkousss,,, Lampros Flokas, and Georgios Piliouras. Effi- ciently avoiding saddle points with zero order methods: No gradients required. In Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, 2019.
[56] Yi Xu, Rong Jin, and Tianbao Yang. First-order stochastic algorithms for escaping from saddle points in almost linear time. Advances in Neural Information Processing Systems, 31:5530-5540, 2018.
[57] Yingxiang Yang, Negar Kiyavash, Le Song, and Niao He. The devil is in the detail: A framework for macroscopic prediction via microscopic models. Advances Neural Information Processing Systems, 33, 2020.
[58] Haishan Ye, Zhichao Huang, Cong Fang, Chris Junchi Li, and Tong Zhang. Hessian-aware zeroth-order optimization for black-box adversarial attack. arXiv preprint arXiv: 2018.
[59] Zelda B Zabinsky. Stochastic adaptive search for global optimization, volume 72. Springer Science Business Media, 2013.
13


Reviews:
[{"review_id": "m2OoNRmrR3", "reviewer": "Reviewer_369q", "summary": "In this submission, the authors analyse a variant of stochastic three points method which is a derivative free optimisation algorithm using a random search routine. They prove that the method converges to a second-order stationary point but suffers a complexity that increases exponentially with respect to the dimension of the problem. They propose a modification to the algorithm so that the complexity in terms of the number of function evaluations is only linear in the problem dimension. They provide experiments showing that the new method outperforms other random search methods in escaping saddle points for large dimensional problems.", "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": "The authors have two main contributions in this submission. First, they analyze a variant of stochastic three points (STP) method that uses a two-step design which aims to take first and seconder order information into consideration using only the function values without having access to the derivatives. The authors prove that this algorithm converges to a second-order stationary point where the derivative is zero and the Hessian is positive definite. They also show that this method’s complexity increases exponentially with respect to the dimension of the problem. \n\nTo deal with the complexity issue, they propose a modification the algorithm using a derivative-free routine which approximates the eigenvector corresponding to the smallest negative eigenvalue of the Hessian so that they capture the negative curvature. The routine they propose is based on a noisy power method and has a lower computation cost in terms of the imput dimension than the previous methods. They show that the complexity of the new algorithm in terms of the number of function evaluations is linear in the problem dimension. They also provide experiments showing that the proposed method outperforms other random search methods STP, Basic Direct Search (BDS) and the Approximate Hessian Direct Search (AHDS) in escaping saddle points when the problem dimension is large. \n\nThe theoretical contributions for the random search methods seem to be new and interesting. The submission is well written with an easy-to-follow presentation. \n\nThe experiments are limited. The authors do not provide any performance evaluation of the proposed method in any of the machine learning applications mentioned in the introduction. Although, the new method seems to perform well in escaping saddle points in the synthetic problems, its general performance in the mentioned applications is not clear.\n\nFor a wide-range of optimization problems in machine learning, the evaluation of the entire objective function with a full pass through the dataset is either impossible or it is computationally very demanding. Therefore, many algorithms rely on noisy (stochastic) gradient information and use the data in batches. Given that the authors propose algorithms, which require full passes through the data, the algorithms will have limited applications in machine learning. As also mentioned by the authors, it is true that stochastic search algorithms can still be used in reinforcement learning, meta-learning, and so on. However, the authors have not provided any numerical experiments on any one of these applications.\n\nI believe the authors consider their contribution as mainly theoretical  -which explains the limited experiments- but then without experiments on machine learning problems, I do not think this conference is the best fit for this work. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There not immediate potential negative societal impact of the work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "m1hbzdibsG3", "reviewer": "Reviewer_BTuv", "summary": "This work studies the problem of optimizing a non-convex function in a deterministic setting, where the gradient of the function is not accessible. The authors provide analysis of convergence to a second order stationary point, where the gradient of the function is zero and the Hessian matrix is positive definite.   \n\nAssumptions: Let $f$ to be the objective function:\n\n1. $f$ is lower bounded.\n2. The gradient and Hessian of $f$ are Lipschitz\n3. The smallest eigenvalue of the Hessian matrix has a uniform lower bound.\n\nFirst the authors proposed a decent algorithm (Algorithm 1, page 4), which is a variant of vanilla random search method. Their analysis for this algorithm is divided into two parts: The case when the gradient is large (Lemma 2, page 4), and the case when the gradient is small but the smallest eigenvalue of Hessian is negative (Lemma 4, page 5). The latter is the case where they are close to a strict saddle point. Aggregating Lemmas 4 and 5 yields one of their main results, Theorem 5 (page 5). This theorem outlines the fact that convergence to a second order stationary point grows exponentially as a function of $d$ (dimension). To overcome this issue, they proposed Algorithms 2 and 3. The main idea of these algorithms is that instead of a random direction search (which causes an exponential dependency on $d$), they estimate negative curvature directions for escaping a saddle point. This new approach requires $4d$ additional function evaluations at each iteration. As they initially claimed, they could overcome the curse of dimensionality and obtain a linear dependency with respect to $d$. This result is marked out in Theorem 10 (page 7). ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: They worked on a well studied problem. Their proposed Algorithms 2 and 3, can derive linear dependency on dimension which is outlined in Theorem 10 (page 10). This approach is inspired by Carmon et al. (2018), but instead of estimating the Hessian matrix they only estimate negative curvature directions. \n\nQuality: 1. I read the proofs up to Section C. All the theoretical claims are well supported. \n\n2. The authors provided an adequate literature review and gave quite enough intuition about the challenges and their methodology.\n\n3. The paper is quite technical. In the appendix, I appreciate that the authors provided numerical experiments after critical lemmas to provide a clear intuition. \n\n4. They did not give any sense of optimality of their main result in Theorem 10. It would be useful if the authors discussed this. Also, it would be helpful if the authors provided a table to summarize the upper bounds \\ lower bounds in the relevant works.\n\n5. Since both Carmon et al. (2018), and Liu and Yang (2017) deal with the situation where the gradient of the function is available, the provided comparison in Section 3.2 needs more discussion.\n\n6. One point is not clear to me. In the proof of Lemma 3, why is it enough to derive a bound for equation (14)? And to be precise, why do you need the term $\\nabla^2\\tilde{f}(.)$ at point $x_0$?\n\nClarity: The paper is well written. Except for some vague parts which I asked about above and I pointed out here, the proofs are self-contained and clear.\n\nThese are some minor typos and suggestions, up to Section C:\n\n1. In Algorithm 1, the lines 5 and 7. It is evident to me what you mean by that. But mathematically, it may be confusing for the readers when you write argmin on a set.\n2. I think instead of reference [52] in line 52, you should cite the reference [38].\n3. line 172. typo: you should add a parenthesis for the term $\\lambda_\\min$(...).\n4. line 246. typo: Ass ----> Assumption, since throughout the note you wrote Assumption rather than Ass.\n5. line 542. Equation (10), there is a term $(2/3)^{(\\alpha + 1)}$, which should be $(1/2)^{(\\alpha + 1)}$.\n6. line 559. \"In for our first result\" must be a typo.\n\n\nSignificance: Inspired by Carmon et al. (2018) and Lin and Yang (2017), this paper obtained a nearly linear dependency on dimension ($d\\log(d)$) for gradient-free non-convex optimization, which to the best of my knowledge is new in the literature.\n\nI would like to thank the authors for their response. After the rebuttal and re-studying Section 3, I find the discussion provided about Carmon et al. (2018), and Liu and Yang (2017) complete and enough. Considering other reviews and the authors' feedback, my assessment of the paper remains unchanged. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors briefly discuss the limitations of their work. I also pointed out some, along with suggestions to improve the paper in the Main Review section.\n\nSince the paper is quite theoretical, I except no direct social impact at this point.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "GQk8t3kcrz6", "reviewer": "Reviewer_Tejo", "summary": "This paper is related to random-search methods when optimizing non-convex objective functions without having access to derivatives. The authors provided convergence guarantees to a second-order stationary with only access to the function evaluations. Further, they showed some numerical results for highlighting their theoretical results. ", "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": "1- The paper is mostly well-written.\n\n2- SOSP can happen also when norm of gradient is small and the Hessian is positive-semi definite. The text in the first page needs to be modified, unless the authors are considering some other assumptions in their mind such as strict saddles (which in this case the authors should mention it in the text as well).\n\n3- The contributions (in Page 2) are not well-described. Each contribution should be separate (the second contribution is the rest of the first one; needs be re-written in a better way)\n\n4- In Line 67, do the Authors mean $\\mathcal{O}(\\epsilon^{-2})$?\n\n5- In Algorithm 1, the authors need to clarify steps 5 and 7 more. Why one step is Gradient Step and the other is Curvature Step while both steps are very similar to each other? the authors need to mention how the second one is using the curvature information while the first one is not? further, they should not simply say that the choices of $\\sigma_1$ and $\\sigma_2$ are the main difference between gradient and curvature steps. More info is required.\n\n6- In Lemma 3, it can happen that one of eigenvalues to be zero ($\\lambda_i =0$ for some $i$) based on the assumption that $\\lambda_d <0$. How the authors can escape the saddles when eigenvalues of Hessian are not strict? Usually, in order to escape from saddles and converge to SOSP, the assumption \"strict saddles\" is required. The authors need to mention how they can escape saddles with their assumptions.\n\n7- Algorithm 2 is very expensive. Step 6 in Algorithm 2 requires $T_{DFPI} \\times 4d$ functions evaluations, which is indeed unpractical for large dimensional problems. \n\n8- Assumption 2 is very strong, how the authors can justify it?\n\n9- The size of problems for the numerical experiments (both in main body and also in the appendix) are very small ($d \\leq 200$). Why the authors do not consider larger dimensional problems?\n\n10-  In Figure 3, why the methods AHDS and BDS do not improve at all? how the authors select the initial points? are they saddles? The authors need to mention how they select the initial points since in Appendix D2 (Figures 16 and 17) $||\\nabla f||$ is very small from the very beginning, why it happens? \n\n11- The authors need to mention how they tuned the hyper-parameters of each algorithm separately. Are the tuning attempts equal for each algorithm to have a fair comparison?\n\n** Please note that the reviewer's current grade can be upgraded if the authors address the reviewer's main concerns written as above\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They have not. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "7J1jtBNbVzU", "reviewer": "Reviewer_huRV", "summary": "This paper proposed a novel random search method that can converge to a second-order stationary point at a faster rate for high-dimensional problems with only zeroth-order oracle under standard Lipschitz gradient Lipschitz Hessian assumptions. The number of function evaluations is only linear in the problem dimension. Experiments verify the theoretical results. ", "questions": "", "limitations": "", "rating": 7, "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": "Originality: This paper proposed a new random search method to solve high-dimensional problems. This paper is well written and technically adequate. Noisy power iteration based on only zeroth-order oracle (DFPI) is used to estimate the negative eigenvector and avoid the storage of Hessian. It is shown that if the estimation is good enough, the number of outer iteration needed in direct search or the number of calculations of the negative eigenvector is independent of dimension. DFPI provably converges with iteration complexity that is nearly linearly dependent on dimensional, therefore the final computation complexity avoids exponential dependency. I would like to see more zero-order methods for high-dimensional problems are compared in experiments and analyzed in theory.   \n\nQuality: First, theoretical results show the proposed method can achieve better performance on the worst-case analysis than the previous random search methods for high-dimensional problems. Algorithm 2 is similar to the framework of the naive random search method. Algorithm 3 adopts a zeroth-order strategy. Is there any equivalence or intuition between the proposed method and zeroth-order methods? Besides, how about the comparison of the iteration complexity between the proposed method and the AHDS method for high-dimensional problems? \n\nSecond, experimental results show the proposed method can achieve better performance than the previous random search methods for high-dimensional problems. However, zeroth-order methods are another popular type of derivative-free method. My concern is whether the proposed method can achieve better performance than zeroth-order methods for high-dimensional non-convex problems in experiments. \n\nSome other questions:\n1. Is this paper the first to introduce STP with two different stepsizes? If the authors could comment on this point it might be helpful in appreciating the novelty here.\n2. Which one of DFPI-FD and DFPI-SPSA is used for each experiment and why? On line 265, it says \"We choose to run DFPI with SPSA for 20 iterations for all the results shown in the paper.\" but in Table 3, it shows DFPI-FD.\n3. Figure 10-12 gives a comparison of FD and SPSA in terms of spectrum error. However, is there any comparison on convergence speed of RSPI with DFPI-FD and DFPI-SPSA?\n4. In conclusion, it says \"the dependency in terms of the function input dimension becomes linear, a result which we clearly observed in our experimental results\". What do experiments ensure us that the dependency is linear?\n5. In Lemma 9 and Theorem 15, why the probability is $1- \\delta-e^{\\Omega(d)}$ instead of $1- \\delta^{\\Omega(1)}-e^{-\\Omega(d)}$?\n\nClarity: The paper is clearly written and well-organized.\n\nSignificance: The results are significant to the relevant problems, but may not have a broad impact.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of finding second order stationary points via only functional evaluations. The paper considers specifically random search based methods and demonstrates a random search method that establishes convergence to SOSPs within O(d/eps^2) function evaluations. The analysis and results are solid and the algorithmic contribution is strong. The main criticism towards the paper is that of novelty of results compared to existing results on zeroth order optimization convergence to SOSPs which have been shown to achieve the same rate. The relative novelty here is that the paper focuses specifically on random search method as opposed to approximating gradient type of methods that exist in literature. There are benefits of random search methods as elucidated by the authors. 

Overall the paper is right on borderline. I am recommending accept based on the reviewers' unanimous agreement with its contributions. I strongly suggest the authors to do a very clear comparison with Flokas et al stating their result and the comparison of their result with it. 
Decision: Accept (Poster)