Gradientless Descent: High-Dimensional Zeroth-Order Optimization
Authors: Daniel Golovin
John Karro
Greg Kochanski
Chansoo Lee
Xingyou Song
Qiuyi Zhang
Venue:  (2020)
Keywords: Zeroth Order Optimization

Abstract: Zeroth-order optimization is the process of minimizing an objective $f(x)$, given oracle access to evaluations at adaptively chosen inputs $x$. In this paper, we present two simple yet powerful GradientLess Descent (GLD) algorithms that do not rely on an underlying gradient estimate and are numerically stable. We analyze our algorithm from a novel geometric perspective and we show that for {\it any monotone transform} of a smooth and strongly convex objective with latent dimension $k \ge n$, we present a novel analysis that shows convergence within an $\epsilon$-ball of the optimum in $O(kQ\log(n)\log(R/\epsilon))$ evaluations, where the input dimension is $n$, $R$ is the diameter of the input space and $Q$ is the condition number. Our rates are the first of its kind to be both 1) poly-logarithmically dependent on dimensionality and 2) invariant under monotone transformations. We further leverage our geometric perspective to show that our analysis is optimal. Both monotone invariance and its ability to utilize a low latent dimensionality are key to the empirical success of our algorithms, as demonstrated on synthetic and MuJoCo benchmarks.


Published as a conference paper at ICLR 2020
GRADIENTLESS DESCENT: -EROTH-ORDER OPTIMIZATION
HIGH-DIMENSIONAL
Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee Xingyou Song, Qiuyi (Richard) Zhang"
Google Brain (dgg, karro, gpk, chansoo, xi xingyousong, qiuyi 2goggee com
ABSTRACT
Zeroth-order optimization is the process of minimizing an objective f(z), given oracle access to evaluations at adaptively chosen inputs x. In this paper, we present two simple yet powerful Gradientl ess Descent (GLD) algorithms that not rely an underlying gradient estimate and are numerically stable. We analyze our algorithm from a novel geometric perspective and present novel analysis that shows convergence within an e-ball of the optimum in OkkQ log(n) log (R)e)) evaluations, for any monotone transform of a smooth and strongly convex ob- jective with latent dimension k < n, where the input dimension is R is the diameter of the input space and Q is the condition number. Our rates are the first of its kind to be both 1) noly-logartthmically dependent on dimensionality and 2) invariant under monotone transformations. We further leverage our geometric perspective to show that our analysis optimal. Both monotone invariance and its ability to utilize a low latent dimensionality are key to the empirical success of our algorithms, as demonstrated on BBOB and MuJoCo benchmarks.
INTRODUCTION
We consider the problem of zeroth-order optimization (also known gradient-free optimization, or bandit optimization), where our goal is to minimize an objective function f R² - IR with as few evaluations of (x) possible. For many practical and interesting objective functions, gradients are difficult to compute and there is still a need for zeroth-order optimization in applications such as reinforcement learning (Mania et al., 2018; Salimans et al., 2017: Choromanski al., 2018), attacking neural networks (Chen et al., 2017; Papernot et al., 2017). hyperparameter tuning of deep networks (Snoek et al., 2012), and network control (Liu et al., 2017).
The standard approach to zeroth- function values and apply a first-order optimization algorithm (Flaxman al., 2005). Nesterov & Spokoiny (2011) analyze this class of algorithms as gradient descent on Gaussian smoothing of the objective and gives an accelerated ( log( + F))))) iteration complexity for an L- Lipschitz convex function with condition number Q and R = ||00- x"1 and F = f(a) - fx="). They propose a two-point evaluation scheme that constructs gradient estimates from the difference between function values at two points that are close to each other. This scheme was extended by (Duchi et al., 2015) for stochastic settings, by (Ghadimi & Lan, 2013) for nonconvex settings, and by (Shamir, 2017) for non-smooth and non-Euce -uclliede norm settings. Since then, first-order techniques such as variance reduction (Liu et al., 2018), conditional gradients (Balasubramanian & Ghadimi, 2018), and diagonal preconditioning (Mania al., 2018) have been successfully adopted in this setting. This class of algorithms are also known as stochastic search, random search, or (natural) evolutionary strategies and have been augmented with variety of heuristics, such as the popular CMA-ES (Auger & Hansen, 2005).
optimization is, ironically, to estimate the gradients from
These algorithms, however, suffer from high variance due to non-robust local minima highly non-smooth objectives, which are common in the fields of deep learning and reinforcement learn-
Author list in alphahetical order.

---

Published as a conference paper at ICLR 2020
ing. Mania et al. (2018) notes that gradient variance increases training progresses due to higher variance in the objective functions, since often parameters must be tuned precisely to achieve rea- sonable models. Therefore, some attention has shifted into direct search algorithms that usually finds a descent direction u and moves to x + ōu, where the step size is not scaled by the function difference.
The first approaches for direct search were based on deterministic approaches with a positive span- ning set and date back to the 1950s (Brooks, 1958). Only recently have theoretical bounds surfaced, with Gratton et al. (2015) giving an iteration complexity that is a large polynomial of n and Dodan- geh Vicente (2016) giving an improved O L Le)).. Stochastic approaches tend to have better complexities: Stich et al. (2013) uses line search to give O(nQ log(F/e)) iteration complexity for convex functions with condition number Q and most recently, Gorbunov al. (2019) uses impor- tance sampling to give O(nQ log( (F/e)) complexity for convex functions with average condition number Q. assuming access to sampling probabilities. Stich et al. (2013) notes that direct search algorithms are invariant under monotone transforms of the objective, property that might explain their robustness in high-variance settings.
In general, zeroth order optimization suffers an at least linear dependence on input dimension л and recent works have tried to address this limitation when n is large but f(x) admits a -ow-dimeniional
structure. Some papers assume that fzz depends only on k coordinates and Wang al. (2017)
applies Lasso to find the important set of coordinates, whereas Balasubramanian & Ghadimi (2018)
simply change the step size achieve an (k(g(((n)))) (c)) iteration complexity. Other papers
sume more generally that f (x) = g(Axz) only depends on a k-dimensional subspace given by the range of PA A and Djolonga et al. (2013) apply low-rank approximation to find the low-dimensional subspace while Wang et al. (2013) use random embeddings. Hazan et al. (2017) assume that (xx sparse collection of k-ddgree monomials on the Boolean hypercube and apply sparse recov- ery to achieve a Onn²) runtime bound. We will show that under the case that f(x) = g(P
our algorithm will inherently pick up any low-dimensional structure (xx) and achieve a con- vergence rate that depends on k log(n). This initial convergence rate survives, even if we perturb
= =(x)=g(PA=) + h(x). so long as h(z)) is sufficiently small.
We will not cover the whole variety of black-box optimization methods, such as Bayesian opti- mization or genetic algorithms. In general, these methods attempt to solve a broader problem (e.g. multiple optima), have weaker theoretical guarantees and may require substantial computation at each step: e.g. Bayesian optimization generally has theoretical iteration complexities that grow ex- ponentially in dimension, and CMA-ES lacks provable complexity bounds beyond convex quadratic functions. In addition to the slow runtime and weaker guarantees, Bayesian optimization assumes the success of inner optimization loop of the acquisition function. This inner optimization is often implemented with many iterations of a simpler zeroth-order methods, justifying the need to understand gradient-less descent algorithms within its own context.
1.1 OUR CONTRIBUTIONS
In this paper, we present GradientLess Descent (GLD), class of truly gradient-free algorithms (also known as direct search algorithms) that are parameter free and provably fast. Our algorithms are based a small step in a randomly chosen direction, there is a significant probability that we will reduce the objective function value. We present novel analysis that relies facts in high dimensional geometry and can thus be viewed as a geometric analysis of gradient-free algorithms, recovering the standard convergence rates and step sizes. Specifically, we show that if the step size is on the order of O Vn ), we can guarantee an expected decrease of 1 - 2 in the optimality gap, based on geometric properties of the sublevel sets of smooth and strongly convex function.
simple intuition: for well-conditioned functions, if we start from a point and take
Our results are invariant under monotone transformations of the objective function, thus our conver- gence results also hold for a large class of non-convex functions that are a subclass of quasi-convex functions. Specifically, note that monotone transformations of convex functions are not necessarily convex. However, monotone transformation of convex function is always quasi-convex. The maximization of gqass-ccncaav utility functions, which is equivalent to the minimization of quasi- convex functions, is an important topic of study in economics (e.g. Arrow & Enthoven (1961)).
2

---

Published as a conference paper at ICLR 2020
Comparison of zeroth order optimization for well-conditioned convex functions where R a 2"I and F = fzz) f(z"). 'Monotone' column indicates the invariance under monotone transformations (Definition 4). "k-Sparse" and "k-Affine" columns indicate that iteration
Table 1:
complexity is poly(k, log(n)) when f(x) depends only k-sparse subset of coordinates rank-k affine subspace.
Algorithm
Iteration Complexity
Monotone
k k-Sparse
k-Affine
Nesterov & Spokoiny (2011)
nlog R F)/c)
No
No
No
Balasubramanian & Ghadimi (2018)
bolog(F7c
No
Yes
No
Stich et al. (2013)
(og(Fe))
Yes
No
No
Gorbunov et al. (2019)
log F/c)
Yes
No
No
This paper (GLD)
log RR/e)
Yes
Yes
Yes
Intuition suggests that the step-size dependence on dimensionality can be improved when f f(x) admits dineeninnai structure. With careful choice of sampling distribution f(x) = g(P AA), where P is a rank k matrix, then our step size can be on the order of O vFr as our optimization behavior is preserved under projections. We call this property inviriinne and show that the number of function evaluations needed for convergence depends logarithmically on Unlike most previous algorithms in the high-dimensional setting, no expensive sparse recovery or subspace finding methods are needed. Furthermore, by novel perturbation arguments, we show that our fast convergence rates robust and holds under the more realistic assumption when f()) = ((Pxz) + (()) with (x)) being sufficiently small.
show that
Theorem (Convergence of GLD: Informal Restatement of Theorem and Theorem 14). Let f(x) be any monotone transform of convex function with condition number Q and || x= Let y be sample from an appropriate distribution centered at x. Then, with constant probability,
f()) - f(x)) < (f(x) ((xx)) (1-5m))
5nQ)
S T log( R//)) function evaluations. Furthermore, for functions f'xx) = ((P ax) + h(x) with rank k matrix PA and sufficiently small h())), we only require Õ log(n) log( Rf()) evaluations.
Therefore, we can find Fr such that |
Another advantage of our non-standard geometric analysis is that it allows us to deduce that our rates are optimal with a matching lower bound (up to logarithmic factors), presenting theoretical evidence that gradient-free inherently requires M(nQ) function evaluations to converge. While gradient-estimation algorithms can achieve a better theoretical iteration complexity of O(n/Q), they lack the monotone and affine invariance properties. Empirically, erties are important to successful optimization, as validated by experiments on synthetic BBOB and MuJoCo benchmarks that show the competitiveness of GLD against standard optimization proce- dures.
that invariance prop-
PRELIMINARIES
We first define few notations for the of the paper. Let X' be compact subset of R and let || denote the Euclidean norm. The diameter of X, denoted || = max,,x' ||æ - x']], is the R be a real-valued function which attains its minimum at x=" We use f(X) (f(x) x E X3 to denote the image of f on a subset X' of IR". and B(c, r) = {x Rm ||e x|| S r) denote the ball of radius r centered
maximum distance between elements in X. Let f
Definition 2. The level set of f at point x E X La()) {y E X :f()) = f(x))- The sub-level set of f at point E X is (f( tu E X f(w) < f(x)). When the function is clear from the context, we omit it.
Definition 3. We say that f is a-strongly convex for a > 0 if f(v) Z f(x) (V B1y - =1 for all x, y E X' and 3-smooth for 3 > 0 if f < f(x) (Vf(x) y f f all x, E X.
3

---

Published as a conference paper at ICLR 2020
Definition 4. We say that f is monotone transformation f ifg f(X) I is monotonically (and strictly) increasing function.
Monotone transformations preserve the level sets of function in the sense that Cz(f) Lg f). Because our algorithms depend only on the level set properties. our results generalize to any monotone transformation of strongly convex and strongly smooth function. This leads to extended notion of condition number.
Definition 5. A function f has condition number Q 2 if it is the minimum ratio //ax over all functions such that f is a monotone transformation of and is 0-strongly convex and 3 smooth.
When we work with low rank extensions of we only care about the condition number of within a rank k subspace. Indeed, if f only varies along a rank k subspace, then it has a strong convexity value of 0, making its condition number undefined. If f a-strongly convex and 8-smooth. then its Hessian matrix always has cigenvalues bounded between and 3. Therefore, we need a notion of a projected condition number. Let A E Bdxk be some orthonormal matrix and let PA AAT T be the projection matrix onto the column space of A.
Definition For some orthonormal A E TRdxk with d k, a function I has condition number restricted to A, Q(A) 2 1, if it is the minimum ratio 3/Ox over all functions such that is monotone transformation of g and h(y) = (Ay) is a-strongly convex and B smooth.
ANALYSIS OF DESCENT STEPS
The GLD template can be summarized follows: given a sampling distribution D, we start at zo and in iteration t, we choose a scalar radii r, and we sample yt from distribution r,D centered around Te, where rt provides the scaling of D. Then, if (w)) fIz). update It+1 y: otherwise, we set Z++1 = It. The analysis of GLD follows from the main observation that the sub- level set of monotone transformation of strongly convex and strongly smooth function contains a ball of sufficiently large radius tangent to the level set (Lemma 15). In this section, we show that this property, combined with facts of high-dimensional geometry, implies that moving in a random direction from any point has good chance of significantly improving the objective.
As we mentioned before, the key to fast convergence is the careful choice of step sizes, which we describe in Theorem 7. The intuition here is that we would like to take as large steps possible while keeping the probability of improving the objective function reasonably high, so by insights in dishesninnional geometry,
choose step size of ((1/ Also, we show that if fz) admits
latent rank-k structure, then this step size can be increased to @(1/ ([1/k) and is therefore only dependent on the latent dimensionality of f()), allowing for fast high-dimensional optimization. Lastly, our geometric understanding allows us show that our convergence rates are optimal with matching lower bound. Without loss of generality, this section assumes that far) is strongly convex and smooth with condition number Q.
3.1 STEP SIZE
Theorem 7. For any such that
5Q ||x - E [Ci, C2), can find integers 0 S k1, < log C2 Ti
3
such that if r 2 C1 or r = 2-2h kg C2. then a random sample from uniform distribution over
B, B(x, r) satisfies vn)
f(y) - (()))(x))+ f(x)) f(x))) (1 (1- sii))
with probability at least 1.
Proving the above theorem requires the following lemma about the intersection of balls in high dimensions and it is proved in the appendix.
Lemma 8. Let B1 and By be two balls in R2 of radi T1 and r2 respectively. Let be the distance between the centers. If 12 fal and r2 2 l 4n then
vol (B, n B2) c, vol (Bi),
where Cn is dimension-deependent constant that is lower bounded by 1 at n.
4

---

Published as a conference paper at ICLR 2020
3.2 GAUSSIAN SAMPLING AND Low RANK STRUCTURE
A direct application of Lemma 8 seems to imply that uniform sampling of high- dimensiona ball necessary. Upon further inspection, this can be easily replaced with much simpler Gaussian sampling procedure that concentrates the mass close to the surface to the ball. This procedure lends itself to better analysis when (x) admits a latent low-dimensional structure since any affine projection of Gaussian is still Gaussian.
Lemma 9. Let B1 and Bg be two balls in In of radii T and r2 respectively, Let be the distance between the centers. If E
12/n" [n) and 122 2 L -- and X (X1, are independent
Gaussians with mean centered at the center of B1 and variance á. then
Pr[X B2) C,
where c is a dimension- innepeeden- constant.
Assume that there exists some rank & projection matrix PA such that f(z) g(PAx)) where is much smaller than n. Because Gaussians projected a k-dimensional subspace are still Gaussians, we show that our algorithm has a dimension dependence on k. We let (A) be the condition number of 9 restricted to the subspace A that drives the dominant changes in f(x).
Theorem 10. Let f(x) g(Px)) for some unknown rank k matrix PA with k < and suppose (I x²) )I E (C1, C2] for some numbers C1, C2 E Rt. Then, there exist integers s
|P
A
5Q
ki, k2 log Ci such that if 2 Ci or or=== 2 C2. then a random sample y from a Gaussian
distribution Nzx I)) satisfies
- f(0) (f())) -1-NAQG(A)
with constant probability.
Note that the speed-up up in progress is due to the fact that we can now tolerate the larger sampling radius of 22(1 /VR),, while maintaining a high probability of making progress. le is unknown, we
can simply use binary search to find the correct radius with an extra factor of log(n) in our runtime.
The low-rank assumption too restrictive to be realistic; however, our fast rates still hold, at least for the early stages of the optimization, even if we assume that [z) ((PAa) + h(x) and [M(x) < 6 a full-rank function that bounded by 8. this setting, we can show that convergence remains fast, at least until the optimality gap approaches 5.
Let f(x) g(Pa=) h(x:) for some unknown rank k matrix PA with k < where g, are convex and hh| S ó. Suppose tQ |PA 201 E [C1, C2) for some numbers C2 C22 E R+
Theorem 11.
3
where: minimizes g(2). Then, there exist integers S k1, l2 loog E₁ such that if 2 C₁ or r 2 22. then a random sample y from Gaussian distribution N(x, (²1) satisfies
f(y) f(=) S (f(x) f(x))) (1 (o)d
with constant probability whenever f(x) - f(x*)= ) 2 (A).
3.3 LOWER BOUNDS
We show that our upper bounds given in the previous section are tight to logarithmic factors for any symmetric sampling distribution DD. These lower bounds are easily derived from our geometric perspective we show that a sampling distribution with large radius gives an extremely low probability of intersection with the desired sub-level set. Therefore, while cradient-approximatio algorithms can be accelerated to achieve a runtime that depends on the square-root of the condition number Q. gradient- methods that rely on random sampling are likely unable to accelerated according to our lower bound. However, to apply to a broader class of objective functions, beyond smooth and convex, so the results can be useful in practice despite the seemingly worse theoretical bounds.
emphasize that monotone invariance allows these results
5

---

Published as a conference paper at ICLR 2020
Algorithm 1: Gradientless Descent with Binary Search (GLDD-eearch)
Input: function: f: IR" + IR, 8,: number of iterations, zng starting point,
D: sampling distribution, R: maximum search radius, r: minimum search radius Set K log( R/r)
for & 0...... do
Ball Sampling Trial i: for k= 0, ..... K do
Set riA = 2 R. Sample Ui ~ ri D.
end
Update: T++1 = arg ming {s() y= zt, y = 24 + v1,k)
end
10 return
Theorem 12. Let y + v, where u is a random sample from r'D for some radius r > and 'D standard Gaussian or any rotationally symmetric distribution. Then, there exist region X with positive measure such that for any x E X,
f(w) - f(x)) ) 2 (f(x) - [(xx)) (1-
/ log(nQ)
nQ
with probability at least poly(n())
4 GRADIENTLESS ALGORITHMS
In this section, we present two algorithms that follow the same Gradientless Descent (GLD) tem- plate: GLD-Search and GLD-Fast, with the latter being an optimized version of the former when an upper bound on the condition number of function is known. For both algorithms, since they are monotone-invariant, we appeal to the previous section to derive fast convergence rates for any monotone transform of convex f(x) with good condition number. We show the efficacy of both algorithms experimentally in the Experiments section.
4.1 GRADIENTLESS DESCENT WITH BINARY SEARCH
Although the sampling distribution D is fixed, have choice of radii for each iteration of the algorithm. We can apply a binary search procedure to ensure progress. The most straightforward version of our algorithm is thus with a naive binary sweep across interval in [r, R] that is un- changed throughout the algorithm. This allows us to give convergence guarantees without previous knowledge of the condition number at a cost of an extra factor of log(n/e).
Theorem 13. Let zo be any starting point and f a blackbox function with condition number Q. Running Algorithm I with < R || and D (O,
standard Gaussian returns
/ point xr such that || x² < 2Q after (nQQ (og(n))/\//e)) function evaluations with high probability.
Furthermore, if f(x) g(P ax) admits low-rank structure with PA rank k matrix, then only require O(kQ, log(n) log(n][(\l/ee²)) {)] function evaluations to guarantee [ - x x²)ll < e.
This holds analogously even if f(z) ((P + h(x)) is almost low-rank where [h] S and
60ōkQy(A)
4.2 GRADIENTLESS DESCENT WITH FAST BINARY SEARCH
GLD-Search (Algorithm 1) uses naive lower and upper bound for the search radius ||ar =*|| which incurs extra factor of log(1/c) in the runtime bound. In GLD-Fast, we remove this extra factor dependence on log(1/e) by drastically reducing the range of the binary search. This is done by exploiting the assumption that f has a good condition number upper bound Q and by slowly halfing the diameter of the search space every few iterations since expect T, - x² as

---

Published as a conference paper at ICLR 2020
Algorithm 2: Gradientless Descent with Fast Binary Search (GLDD-Fast)
Input: function f R" - IR, Z,;: number of iterations, zn starting point,
D: sampling distribution, Rt diameter of search space, Q: condition number bound
Set K ( (), H = nQ (Q)
for t ...... .T do
Set R= = R/2 when 7' 0 mod (every H iterations).
Ball Sampling Trial i:
for == ..., 0, 0...., K do
Set = 2-2 RR Sample Vi.k ri,h D.
end
Update: J++1 = arg min; {f()) -= zt. y xz + +1)
10 end
return 2t
Theorem 14. Let Zy be any starting point and f a blackbox function with condition number upper bounded by Q. Running Algorithm with suitable parameters returns point FT such that f f(x)) after O(nQ log" (Q) log([IX(I/c)) function evaluations with high probability.
Furthermore, f(x) = (( admits a low-rank structure with P A a rank l matrix, then we only require Ok (A) log(n) ) log (Q,(A) ())()))())e) function evaluations to guarantee [P (PAle (IT x²)l| S c. This holds analogously even if f(x)) = (P x.) + h((x)) is almost low-rank where [h| <
and 6 > 605k0,
5 EXPERIMENTS
We tested GLD algorithms on simple class of objective functions and compare it to Accelerated Random Search (ARS) by Nesterov & Spokoiny 1), which has linear convergence guarantees on strongly convex and strongly smooth functions. To our knowledge, ARS makes the weakest as- sumption among the zeroth-order algorithms that have linear convergence guarantees and perform only constant order of operations per iteration. Our main conclusion is that GLD-Fast is compa- rable to ARS and tends to achieve reasonably low error much faster than ARS in high dimensions (2 50). low dimensions, GLD-Search is competitive with GLD-Fast and ARS though it requires no information about the function.
We let Ha,3,x R be diagonal matrix with its i-th diagonal equal to + (B a)) ;-} In simple words, its diagonal elements form an evenly space sequence of numbers from to Our objective function is then fa,8.n R" + I as fx)) = 1/rr Ha,d,n which is a-strongly convex and 8-strongly smooth. We always use the same starting point
Ja (I,..., 1), which requires ||||| = VQ for our algorithms. We plot the optimality gap f(b)) - f(xx) against the num- ber of function evaluations, where b, is the best point observed so far after evaluations. Although all tested algorithms are stochastic, they have a low variance on the objective functions that we use; hence we average the results over 10 runs and omit the error bars in the plots.
We ran experiments on f188. with imperfect curvature information â and 3 (see Figure in ap- pendix). GLD-Search is independent of the condition number. GL.D-Fast takes only one parameter, which is the upper bound on the condition number; if approximation factor is z, then we pass 8z as the upper bound. ARS requires both strong convexity and smoothness parameters. We test three dif- ferent distributions of the approximation error; when the approximation factor is 2, then ARS-alpha gets (a/2, 2, f), ARS-beta gets (a, 2B),, and ARS-even gets (a/v2, VEB) input. GLD-Fast is more robust and faster than ARS when the condition number is over- wwer-apprxximated When the condition number is underestimated, GLD-Fast still steadily converges.

---

Published as a conference paper at ICLR 2020
Dimension
Lo9 Opdnmaii Gop
-
-2
-8- Fast
--- GDD 3DD-errrhh
-3
ARS
Evelaations
(Thousardss)
5
Dimension 10
Dimansion - 20
Dimonsion - 50
Dimenson 190
Log Opdimatyy Gap
-5
3
A85
-6--
-0- CLD Search
-15
4 Evaluation (Thousands)
Evaluations
Figure 1: The average optimality gap on a quadratic objective function that is strongly convex and smooth objective (top): and its monotone transformation (bottom). Further experiments on non- convex BBOB functions show similar behavior and are in the appendix.
5.1 MONOTONE TRANSFORMATIOON
In Figure 1, we ran experiments on f1,8. for different settings of dimensionality n. and its monotone transformation with g(y) exp(-v7). For this experiment, we assume perfect oracle for the strong convexity and smoothness parameters of f. The convergence of GLD is totally unaffected by the monotone transformation. For the low-dimension cases of a transformed function (bottom half of the figure), we note that there are inflection points in the convergence curve of ARS. This means that ARS initially struggles to gain momentum and then struggles to stop the momentum when it gets close to the optimum. Another observation is that unlike ARS that needs to build up momentum, GLD-Fast starts from large radius and therefore achieves a reasonably low error much faster than ARS, especially in higher dimensions.
5.2 BBOB BENCHMARKS
To show that practicality of GLD on practical and non-convex settings, we also test GLD algorithms on variety of BlackBox Optimization Benchmarking (BBOB) functions (Hansen et al., 2009). For each function, the optima is known and we use the log optimality gap as a measure of competance. Because each function can exhibit varying forms of non-smoothness and convexity, all algorithms are ran with a smoothness constant of 10 and a strong convexity constant of 0.1. All other setup details are same as before, such as using a fixed starting point.
The plots, given in Appendix C, underscore the superior performance of GLD algorithms on various BBOB functions, demonstrating that GLD can successfully optimize diverse set of functions even without explicit knowledge of condition number. We note that BBOB functions are far from convex and smooth, many exhibiting high conditioning, multi-modal valleys, and weak global structure. Due to our radius search produce, our algorithm appears more robust to non-ideal settings with non-convexity and conditioning. As expected, we note that GL.D-Fast tend to outperform GLD- Search, especially as the dimension increases, matching our theoretical understanding of GLDD.
5.3 MUJOCO CONTROL BENCHMARKS AND AFFINE TRANSFORMATIONS
We also ran experiments on the Mujoco benchmarks with varying architectures, both linear and nonlinear. This demonstrates the viability of our approach even in the non-convex, high dimensional setting. We note that however, unlike e.g. ES which uses all queries to form a gradient direction, algorithm removes queries which produce less reward than using the current arg- max, which can be an information handicap. Nevertheless, we see that our algorithm still achieves competitive performance on the maximum reward. We used horizon of 1000 for all experiments.
8

---

Published as a conference paper at ICLR 2020
We further tested the affine invariance of GLD on the policy parameters from using Gaussian ball sampling, under the HalfCheetah benchmark by projecting the state of the MDP with linear policy to higher dimensional state Ws, using matrix multiplication with orthonormal W. Specif- ically, this setting, for linear policy parametrized by matrix K, the objective function is thus J (KKW) where π (Ws) KWs. Note that when projecting into high dimension, there is slowdown factor of log daes. where dnew, dotd the new high dimension and previous base di- mension, respectively, due to the binary search in our algorithm
dold
higher dimensional space. For our HalfCheetah case, we projected the 17 base dimension to 200-length dimension, which 200 suggests that the slowdown factor factor log 17 3.5. This can be shown in our plots in the appendix (Figure 15).
Table 2: Final rewards by GLD with linear (L) and deep (H41) policies on Mujoco Benchmarks show that GLD competitive. We apply an affine projection on HalfCheetah to test affine invariance. We use the reward threshold found from (Mania et al., 2018) with Reacher's threshold (Schulman al., 2017) for a reasonable baseline.
Env.
Arch
Rew. (10*, 10", Max) Queries
Rew. Thresh.
HalfCheetah-vl
3799, 3903, 4064
3430
HalfCheetab-vl. Proj-200
L
1594. 3509, .4342
3430
HalfCheetah-vl
H41
2741, 3074, 3392
3430
Hopper-v1
1017, 3359, 3375
3120
Hopper-v1
H41
2708, 3370, 3566
3120
Reacher-v]
L
-70,
-10
Reacher-vl
H41
-2,1,
-10
Swimmer-vl
L
365, 369, 369
325
Swimmer-vl
H41
353, 369
325
Walker2d-v1
1027 2201, 2201
4390
Walker2d-v1
H41
1630, 1963, 2146
4390
CONCLUSION
We introduced GLD, robust zeroth-order optimization algorithm that is simple, efficient, and show strong theoretical convergence bounds via our novel geometric analysis. As demonstrated by our experiments BBOB and MuloCo benchmarks, GLD performs very robustly even in the non-convex setting and its monotone and affine invariance properties give theoretical insight on its practical efficiency.
GLD is very flexible and allows easy modifications. For example, it could use momentum terms keep moving in the same direction that improved the objective, or sample from adaptively cho- sen ellipsoids similarly to adaptive gradient methods. (Duchi et al., 2011; McMahan & Streeter, 2010). Just as one may decay or adaptively vary learning rates for gradient descent, one might use similar change the distribution from which the ball-sampling radii are chosen, perhaps shrinking the minimum radius as the algorithm progresses, or concentrating more probability mass on smaller radii.
Likewise, GLD could be combined with random restarts or other restart policies developed for gra- dient descent. Analogously adaptive per-coordinate learning rates Duchi et al. (2011) 1); McMahan & Streeter (2010), one could adaptively change the shape of the balls being sampled into ellipsoids with various length-scale factors. Arbitrary combinations of the above variants also possible.
9

---

Published as a conference paper at ICLR 2020
REFERENCES
Kenneth Arrow and Alain C. Enthoven. Quasi-concave programming. Econometrica: Journal of the Econometric Society, pp. 779-800, 1961.
Anne Auger and Nikolaus Hansen. A restart evolution strategy with increasing population size. In Evolutionary Computation, 2005. The 2005 IEEE Congress on, volume 2, pp. 1769-1776. IEEE, 2005.
Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order (non)-convex stochastic opti- mization via conditional gradient and gradient updates. In Advances in Neural Information Pro- cessing Systems, pp. 1455-3464, 2018.
Samuel H Brooks. A discussion of random methods for seeking maxima. Operations research, (2):244-251) 1958.
Pin-Yu Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsich. Zoo: Zeroth order opti- mization based black-box attacks to deep neural networks without training substitute models. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pp. 15-26. ACM, 2017.
Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani. Richard E Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. arXiv preprint arXiv: 1804. 02395, 2018.
Josip Djolonga, Andreas Krause, and Volkan Cevher. High-dimensional gaussian process bandits. In Advances in Neural Information Processing Systems, pp. 1025-1033, 2013.
Mahdi Dodangeh and Luis N Vicente. Worst case complexity of direct search under convexity. Mathematical Programming, 155(1-2):307-332, 2016.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(ul):2121-2159 2011.
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, (1(5)27788-2800 2015.
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium Discrete algorithmss, pp. 385-394. Society for Industrial and Applied Mathematics, 2005.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal Optimization, 23(4):2341 11-2223112366 2368, 2013.
Eduard Gorbunov, Adel Bibi, Ozan Sener, El Houcine Bergou, and Peter Richtárik. A stochastic derivative free optimization method with momentum. arXiv preprint arXiv:1905. 2019.
Serge Gratton, Clément Royer, Luís Nunes Vicente, and Zaikun Zhang. Direct search based on probabilistic descent. SIAM Journal Optimization, 1513::151--1511 2015.
Nikolaus Hansen, Steffen Finck, Raymond Ros, and Anne Auger. Real-Parameter Black-Box Op- timization Benchmarking 2009: Noiseless Functions Definitions. Research Report RR-6829, INRIA, 2009.
Elad Hazan, Adam Klivans, and Yang Yuan. Hyperparameter optimization: spectral approach. arXiv preprint / 7066006444 2017.
Shengqiao Li. Concise formulas for the area and volume of a hyperspherical cap. Asian Journal of Mathematics and Statistics, 4 4(1):66-70, 2011.
Sijia Liu, Jie Chen, Pin-Ye Yu Chen, and Alfred O Hero. Zeroth-order online alternating direction method multipliers: Convergence analysis and applications. arXiv preprint arXiv:1710.077 2017.
10

---

Published as a conference paper at ICLR 2020
Sijia Liu, Bhavya Kailkhura, Pin- Pu Chen, Paishun Ting, Shiyu Chang, and Lisa Amini. Zeroth- order stochastic variance reduction for nonconvex optimization. Advances in Neural Informa- tion Processing Systems, pp. 3727-3737, 2018.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search provides competitive approach to reinforcement learning. arXiv preprint arXiv:/803.07055 2018.
H. Brendan McMahan and Matthew J. Streeter. Adaptive bound optimization for online convex optimization. In COLT 2010 The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010, pp. 244-256, 2010.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Technical report, Université catholique de Louvain, Center for Operations Research and Econo- metrics (CORE), 2011.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pp- 506-519. ACM, 2017.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as scalable alternative reinforcement learning. arXiv preprint arXiv:1703.0386/ 2017.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/1 fos//107.000 1007006377, 2017. URL 1707. 06447.
Ohad Shamir. An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52):1-11, 2017.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems, pp. 2951-2959, 2012.
Sebastian U Stich, Christian L. Muller, and Bernd Gartner. Optimization convex functions with random pursuit. SIAM Journal Optimization, 23(2):1284-1308 2013.
Yining Wang, Simon Du Sivaraman Balakrishnan, and Aarti Singh. Stochastic zeroth-order opti- mization in high dimensions. arXiv preprint 1710:1111000051,, 2017.
Ziyu Wang, Masrour Zoghi, Frank Hutter, David Matheson, and Nando De Freitas. Bayesian opti- mization in high dimensions via random embeddings. Twenty-Thie Third International Joint Con- ference Artificial Intelligence, 2013.

---

Published as a conference paper at ICLR 2020
A PROOFS OF SECTION 3
Lemma 15. h has condition number Q, then for all x E X, there is a ball of radius Q x²1 that is tangent at x and inside the sublevel set (h)..
Proof. Write h = go f such that f' is a-strongly convex and 3-smooth for some B = Qo and is monotonically increasing. From the smoothness assumption, have for any s.
f f(= 165-VV16 [V(())
5 + (Vi(a), 8 VV(()) + + /V
f(x) + 3 [1.11- -
Consider the ball B B(x - f | For any y B, the above inequality implies f(y) & f(x). Hence, when we apply 9 on both sides, we still have h(y) I h(x)) for all y E B. Therefore, B C S/
By strong convexity, [[)( a||x~>01| x² ||- It follows that the radius of B is at least g1[x- [||]-==||| n
Proof of Lemma& 8. Without loss of generality, consider the unit distance case where & = 1. Further- more, suffices to prove for the smallest possible radius r2 = 4n
Since [r r2 < f < +22, the intersection B B2 is composed of two hyperspherical caps glued end to end. We lower bound vol (B, n B2) by the volume of the cap C1 of B, that contained in the intersection. Consider the triangle with sides r1, and l. From classic geometry, the height of C₁ is
C1 = +1 -3)) > 0.
(1)
The volume of spherical cap is Li (2011),
1
+ 1
vol (C1) vol (Bi)
T
2
1-
2 2
where / the regularized incomplete beta function defined as
1od ta 1- -1 (1-1)~ dt
(a
So 10-1(1 1))0-1 dl
where & E [0, and a, E (0, xs). Note that for any fixed and b, [a b) is increasing in x. Hence, order to obtain a lower bound on vol (C1), we want to lower bound
r or equivalently,
upper bound 2 "
Write r1 2Va
for some [1,2]. From Eq. (1),
a²
C1
+
4n
8n
32n²
Hence,
1
8
1
+
4a
16yn
n
Since s(a) + 4a is convex in [1,2], g(a) max(g(1).g(2)) 12. It follows that
e < 1 (12 1)
n 4/m So, 1 d
1 16n To complete the proof, note that As goes infinity, this value converges to
F1 16.5
r
V, I 185
nn+1 !) is increasing in and V
1.
1 as B Bz.
12

---

Published as a conference paper at ICLR 2020
Proof of Lemma' 7. Let 5nQ Let 9 (1 1) vr." Let Bg Blcg, r4g) be ball that has
on its surface, lies inside f and has radius 7ig = Q || - x= Lemma 15 guarantees its existence. Suppose that
vol (Bz n Bn) 2 1 vol (Bx)
(2)
and that a random sample y from Bn belongs to Bg, which happens with probability at least z Then, our guarantee follows by
f(0) f(x*)
S f(g) - f(x²)
- (1-v)f(x)) + -((=))))(()
S (1 D) (f(x)) ((x"))
where the first line follows from Lemma 15 and second line from convexity of f.
Therefore, it now suffices to prove Eq. 2. To do so, we will apply Lemma 8 after showing that the radius B2 and B, are the proper ranges. Let l |x - cyll and note that
S | all + rg
(3)
Sv x= rg || x + Q 11 x=1l
(v Q (1 (1- v)) || xx'|
(4)
bq 16 ==||-
Since is outside of Bg. we also have
L rg Q
119
-
x
x
-e- x"1l
4 | ==1|-
(5)
50
It follows that
1 bb
x s.
2
2 5Q
In the loga space, our choice of k1 is equivalent starting from log, C1 and sweeping through the range [log2 C1, logz C2] the interval of size 1. This is guaranteed to find point between á and t, which is also an interval of size 1. Therefore, there exists a k1 satisfying the theorem statement, and similarly, we can prove the existence of k22
Finally, it remains to show that rig
2 (1 - 1/(4n))e. From Eq. (3), it suffices to show that || gl I /. From Eq. (4),
A or equivalently v || x*
< In
Tn
I 41l || x01l 2011 vQ(1 v
For any Q. 2 1, 1
So,
vQ(1 レ) 5m (1 w) 1 <
1 in
(6)
and the proof is complete.
Proof of Lemma 9. Without loss of generality, let l = 1 and B, is centered at the origin with radius T2 and B₁ is centered at éj = (1, (I.,,..,,)) Then, we simply want to show that
Pr + X1) +
X?
<
2 2
Go
By Markov's inequality, we see that Σ - X? < 2r = 2/n with probability at most 1/2. And since X1 is independent and r2 2 1 1/ n, it suffices to show that
Pr X1) < 4/n > 2((
Since X, has standard deviation at least T / 2 1/ (2n), we see that the probability of deviating least a few standard deviation below is at least constant.
13

---

Published as a conference paper at ICLR 2020
Proof of Theorem 10. We can consider the projection of all points onto the column space of A and since the Gaussian sampling process is preserved, our proof follows from applying Theorem 7 re- stricted onto the k-dimensional subspace and using Lemma in place of Lemma 8.
Proof of Theorem 11. By the boundedness of h. since f(x) f(x)) 60ōkQ, (A), we see that g(P A²) g(x*) (08kQ,(A) 20 O. By Lemma 9, see that if we sample from a Gaussian
distribution y ~ Ma, _ I), then if 2" is the minimum of g(x) restricted to the column space of A, then
((PA)) 9(2²) S (9(PAz) g(2")) (1
5 (A)
with constant probability. By boundedness h. we know that h(y) S h(x) 26. Furthermore, this also implies that (P (P S g(²*) + 26. Therefore, we know that the decrease is at least
f(0) f(x)) = AV) ((P + h(y) h(x²)
S (P) - 9(²²) + 28
$ (g(P -9(=")) (1- 5kQ (A)
+ +
S (o(PA g(PAAt + 26)
(1-
+ 25
5kQ, 9 (A)
(1-
1
$ (f(x) - f(x²) + 48)
+ 26
5kQ, (A)
$ (f(x) - s(x))) (1 5kQ, (A)
1
+ 65
Since f(x) f(x*) (A), we conclude that (f(x) f(x))) (1- (A),((A) ) + 68 5
-((x))((x'))
1 and our proof is complete.
Proof of Theorem 12. Our main proof strategy is to show that progress can only be made with radius size of O( (lw/lo((n)))((((n)oo (nQ))n(()//())))) larger radii cannot find descent directions with high probability. Consider a simple ellipsoid function f(x) = x." Dr. where D) is diagonal matrix and Dn <
D222 S S... S. Dnn, where WLOG we let D1 = 1 and Dü Q for 1. The optima x with ((x)==0)
Consider the region X ( (2, In In 2 x 2 0.9, | S 0n))(Q Then, if we let (O0, /) be standard Gaussian vector, then for some radius we see that the probability of finding a descent direction is:
Pr[f(x + rv) f(x)] Pr (a) r21)2
Σ
Dala; rv;) $ at Σ
D
1>1
1>1
Pr
2r + 22 + Q
(2ram + - S
< Pr
2r 5 <-Q) Σ
2r - Q Σ
5>
1>1
Pr
12 < -Q Σ
Z/U;
1
Qr Σ 1/
2
i>1
1>1
14

---

Published as a conference paper at ICLR 2020
By standard concentration bounds for sub-exponential variables, we have
Σ 0 - 2 S 2e 2n--1112))
Pr
1t
Therefore, with exponentially high probability, Eisi X? 2 n//2. Also, since |ai| z 0.1/(Qmm) Chernoff bounds give:
Pr
Σ Jyt;
21
2e -50Q4))
Therefore, with probability at least 1 1/(n))²
| uiXi S Vlog(nQ)/Q.
Qrn =2(glog(n)) then we have
Q
Σ n
Qr
1
Σ X -20( (o(ooo(())))
2
We conclude that the probability of descent is upper bounded by Pr e1 S -Q( -(((log(n()) This probability is exactly Φ(-1), where is the cumulative density of standard normal and I (ll/log(n() By naive upper bound, we that
(--1)
1
-2. 2/ dx
2
J
C
22? dx
<
DC
1
C
-P112
T
Since Q logg((()): we conclude that with probability at least 1 1/poly(n(), we have f(v) f(x*)( 2 fxx - f(**).
Otherwise, we are in the case that Qrn s Ol O(Vlog(nQ)). Arguing simiarly before, with high probability, our objective function and each coordinate can change by at most Ol ((/))onn))) (Qn)).
Next, we extend our proof to any symmetric distribution D. Since rotationally symmetric, if we parametrize (r, 0) is polar-coordinates. then the p.d.f. of any scaling of D must take the form p(v) = pr (0). where u() induces the uniform distribution over the unit sphere. Therefore, is random variable that follows D. then we may write Y Rv //lll where a random scalar with p.d.f (r) and v is a standard Gaussian vector and R, X are independent.
As previously argued, ||u|| [0.5n, 1.5m] with exponentially high probability. Therefore, if > ((vlog(nQ)/(Q) the same arguments will imply that Y is a descent direction with polynomially small probability. Thus, when Y is descent direction, it must be that R S S [lo((n))/Q) and as argued previously, lower bound follows similarly.
B PROOFS OF SECTION 4
Proof of Theurem 13, By the Gaussian version of Theorem (full rank version of Theorem 10), long binary search sweeps between minimum search radius r S -3 ||
x²I| and
15

---

Published as a conference paper at ICLR 2020
maximum search radius of the diameter of the whole space R || the objective value will decrease multiplicatively by 1 5n in each iteration with constant probability. Therefore, if | o*Il 2 2Qc and we set r yi and R = || then with high probability, we expect f(2r) f(**) & 3Q²e² after T = O(nQ log([)))/(((E)) iterations, where we note that F = f(xo)
f(x*) - ||| by smoothness.
Otherwise, there exists some 2G such that || - x"1 < 2Qc, then f(xr) - f(x") I f(x)) f(x') I 4300c². Therefore, by strong convexity, conclude that in either case, 12 2²1 < 2Q Finally note that each iteration uses binary search that requires function evaluations.
O(log(R/e)) R/r)) O(log(n||
Therefore, by combining these bounds, we derive result. The low-rank result follows from applying Theorem 10 and Theorem instead.
Proof of Theorem 14. Let H O(nQ log(Q)) be the number of iterations between successive dius halving and we initialize R || and half R every H iterations. We call the iterations between two halving steps an epoch. We claim that ||x; - zoll S R for all iterations and proceed with induction the epoch number. The base case is trivial.
Assume that ||2;; - zall S R for all iterations in the previous epoch and let iteration i, be the start of the epoch and iteration is + H be the end of the epoch. Then, since ||=;, - =x"1 < R, we see that f (zx,) - f(x") < 3R² by smoothness. If
R S ||x; z='l < 4VQR for all in the previous L.Q epoch, then by the Gaussian version of Theorem 7 (Theorem 10), since do binary sweep from 1Q to 4VQR, we can choose 'D accordingly so that we are guaranteed that our objective value will decrease multiplicatively by 1 अहर with constant probability at cost of (log(Q)) function evaluations per iteration. This implies that with high probability, after O(nQ log(Q)) iterations, we conclude
-((,))))
f(x))) < < 1Q -
7 | x²1 < a n22
a
Otherwise, there exists some و < H such that || -x 2 4VQR or -iii,jj-'' =5 n प/ it is the former, then by strong convexity, f(x - (x*) 2 al| - 12 2 23R², which contradicts the fact that (ffr,))-(x"") & 3RR by smoothness. If is the latter, then by smoothness, reach the same conclusion:
f(r - f(x²) f(r,+s)) f(x²)) s -|1,,,11-1111 x²113 R²
Therefore, by strong convexity, we have
f(r,
f(x))
R 2
| x² S
And our induction is complete. Therefore, we conclude that after log([) ((l/e) epochs, we have | - 2= I c. Each epoch has H iterations, each with ((lo(())) function evaluations and so result follows.
The low-rank result follows from applying Theorem 10 and Theorem 11 instead. However, note that since we do not know the latent dimension k, we must extend the binary search to incur an extra log(n) factor in the binary search cost.
16

---

Published as a conference paper at ICLR 2020
C
FIGURES
Condition Number =
Condition Number
Condition Number =
Condition Number 16
Log Opdimality G3p
-16
-5
(eD-Search -9- ARS
-24
-15
-32
-
Evaluations
Evaluation
Figure 2: The average optimality gap by the condition number of the objective function.
Approximation factor 0.125
Approximation factor 0.25
Appr oximation fa -
Approximation factor
Log Optiaalty Gap
GLD-Swethh
-10
-9- GLD Fast
AlS--lpha
-20
ARS bata
-22
ARS-wvin
Evaluations (Thousards)
Evalustions (Thousands)
Evalustors (Thousanda)
Evaluations (Thousands)
Figure 3: The average optimality gap by the accuracy of the condition number estimate, where approximation factor is the ratio of estimated to true condition number. The dimension n = 20.
C.I BBOB FUNCTION PLOTS
Figure 4: Convergence plot for the BBOB Rastrigin Function.
Convergence Plcts Rastrigin Function
Dimension
Dimension 10
Dimension 20
Dimension
Log Optmalty Cap
2-
GLD Search
6 Evalaations (Thousanas)
Exolaations (Thousands)
Evaluations (Thousands)
Evaluations (Thossnnch)
Figure 5: Convergence plot for the BBOB BentCigar Function.
Convergence Plots for BentCigar Function
Dimension
Dimension 10
Dimension 20
Dimension
12
12
12
Log Opsiattyy
8
ARS
GLD-Fad
0-
910
Evalustions (Thousonds)
Evaluadins (Thousands)
Evalustions (Thousands
Evoluations (Thourand5)
17

---

Published as a conference paper at ICLR 2020
Figure 6: Convergence plot for the BBOB BuccheRastrigin Function.
Convergence BuecheRastrigh Function
Dimension
Dimension
Dimension
Dimansian
6.4
Log Optimaat 63p
6.2
ARS
GLD-Fast
GLD Search
910
910 Evaluntions (Thousonas)
Evalustions (Thousards)
Evalusaions (Thousards)
Evalustions (Thousands)
Figure 7: Convergence plot for the BBOB DifferentPowers Function.
Convergence Plots for DifferentPowers Function
Dimension
Dimension 10
Dimension 20
Dimension 40
Log Optmaliy G3p
ARS Search
-6-
9:10
0124456
Figure Convergence plot for the BBOB Discus Function.
Convergence Discus Function
Dimenslon
Dimension 10
Dimension 20
Dimension
Log Opanalty 63p
GLD Fast
GLD Search
3-
0
7 Evaluatonn (Thousands)
Evalustions (Thousands)
Evaluacions (Thousands)
Evaluations (Thousands)
Figure 9: Convergence plot for the BBOB Ellipsoidal Function.
Convergence Plats for Ellipsoidal Function
Dimension
Dimension 10
Dimension 20
Dimension
Log Optnatty 6dp
ARS GLD-Fed
010
9100
Evalustions (Thousands)
Evaluadion (Thousonds)
Evaluations (Thousands)
Evoluctions (Thourands)
18

---

Published as a conference paper at ICLR 2020
Figure 10: Convergence plot for the BBOB Katsuura Function,
Convergencc
Function
Dimansion --
Dimension
Dimension
Dimension
Log Oppmmaiit Gap
ARS
GLD
GLD-Search
012
310
1 7 90
0 4 5 9
012 2
9
Evaliation [Thousands)
Evaluations (Thousands)
Evaluation (Thousands)
Eraliations (Thousands)
Figure 11: Convergence plot for the BBOB SchaffersF7 Function.
Convergence Plats for SchaffersF7 Function
Dimension
Dimension
Dimension =
Dimension
Log Optimality cap
0.25
-0.4
-0.6 0.00
-0.6
ARS
FastFast
GLD Search
0.88
00.6
0.50
-0.8
0.1
Evaluctions (Thousands)
Eraluations (Thousands!
Evalutionn IThousares!
Evaluatoon 1Tho usar d5l
Figure 12: Convergence plot for the BBOB Il-CConite SchaffersF7 Function.
Convergence Schaffers 7llConndiionedd
Dimension
Dimension
Dimension
1.4
Log Optimaity Cap
1.6
1.2
ARS
1.0
GLD-Fiel
0.6
GiD-Search
0.5
0.4
0.4
0.5
2
91
0 1
910
2
910
1 3
5 6
9
Evolustions (Thousands)
Evaluations (Thousands)
Evaluadons (Thousands)
Evalustions (Thousands)
Figure 13: Convergence plot for the BBOB SharpRidge Function.
Convergence Plots for SharpRidge Function
Dimension
Dimension
Log Optmarryyy 6up
ARS GaD-fast CLD-Search
ludionn 10
910
01
Evaluations (Thousanss)
Evaluttoon
Evalustions
19

---

Published as a conference paper at ICLR 2020
Figure 14: Convergence plot for the BBOB Weierstass Function.
Convergence
Function
Dimension
Dimension
Dimension
Dimensian
2,5
2-9-9-4---7-
Log Opd0pmaatt 63p
2,0
2.4-
1.8
ARS
GLD-Fast
2.0
GLD Search
1.5
1.4-
9100
910
Evalustions (Thousards)
Evalustions (Thousards)
Evaluntions (Thousonas)
Evalustions (Thousands)
20

---

Published as a conference paper at ICLR 2020
C.2 MUJOCO CONTROL PLOTS
Figure 15: Plot of maximum reward so far found by algorithm. Main line is the median trajectory
across 3 runs.
HalfCheetah
Reacher
Swimmer
5000
500
3000
-100
2000
200
1000
0-
2000
Reward
60000
10000
Hopper
Walker
15.00
25.0
Linear
3000
Hidden Layer
2500
1500
Linear Projected-200
500
10000
30000
40000
20000
80000
Queries
Figure 16: Example rewards found by all samples by algorithm.
HalfCheętah
Reacher
Swimmer
4000
400
3000
300
-500
2000
200
1000
1000
100
0-
1500
01
PY
Reward
10000
30000
40000
Hopper
Walker
3500
2500
Hidden Layer Linear
3000
2000
2500
1500
2000
1000
1000
500
0
-500
1000
10000
30000
40000
20000
80000
200000
Queries
21


Reviews:
[{"review_id": "r1gG4uu3FB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes stable GradientLess Descent (GLD) algorithms that do not rely on gradient estimate. Based on the low-rank assumption on P_A, the iteration complexity is poly-logarithmically dependent on dimensionality. The theoretical analysis of the main results is based on a geometric perspective, which is interesting. The experimental results on synthetic and MuJoCo datasets validate the effectiveness of the proposed algorithms.\n\nThe theoretical contribution of this paper is nice and valuable. My main concern is the structure f(x) = g(P_A x) + h(x) looks somewhat limited. A more natural form is moving the perturbation into g, i.e, f(x) = g(P_A x + h(x)). \n\nThe experiments on Mujoco do not satisfy the assumption previous. Is there any real-world application which matches the theoretical analysis?\n\nIn summary, I think this is a good paper and tend to accept it.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1ePXMhaYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "** Summary\nThe paper proposes a novel zeroth-order algorithm for high-dimensional optimization. In particular, the algorithm as an instance of direct search algorithms where no attempt is made to estimate the gradient of the function during the optimization process. The authors study the optimization of monotone transformations of strongly-convex and smooth functions and they prove complexity bounds as a function of the condition number, the dimensionality and the desired accuracy. These results are also extended to the case where the function actually depends on a lower-dimensional input. Without any knowledge of the actual subspace of interest, the algorithm is able to adapt to the (lower) dimensionality of the problem. The proposed algorithms are tested on synthetic optimization problems and in a few Mujoco environments for policy optimization.\n\n** Overall evaluation\nThe paper is a solid theoretical and algorithmic contribution to the zeroth-gradient optimization literature. The positive aspects of the paper are:\n- Novel algorithm with strong theoretical guarantees improving or generalizing previous state-of-the-art methods.\n- Ability to adapt to low-dimensional problems and more in general to monotone transformations of convex functions.\n- Efficient version.\n\nNegative aspects of the paper that the authors may address are:\n- The empirical validation is rather weak at the moment. It provides some evidence of the effectiveness of the proposed method but it uses only one baseline and a very few type of optimization problems. Although in my opinion the main contribution is on the theoretical side, a more thorough empirical validation would be welcome.\n- Some theorem statements can be made clearer and some comparisons should be more explicit (see detailed comments later).\n\nDetailed comments:\n1- The authors explicitly mentioned in the introduction that they do not compare/discuss alternative approaches such as Bayesian optimization (BO). Although I agree the approaches may be different, BO is probably the most popular type of black-box optimization. Furthermore, many methods (e.g., GP-UCB https://arxiv.org/abs/0912.3995) come with strong theoretical guarantees on the regret and so optimization performance both under the Bayesian assumption (i.e., the function is generated from a prior) and the \"frequentist\" case (i.e., the function is an arbitrary element of a bounded RKHS). Furthermore, there are also adaptive BO methods that adapt to the actual dimensionality of the problem, in a similar spirit as the low-dimensional case studied in this paper. See e.g., https://arxiv.org/abs/1903.05594 and http://papers.nips.cc/paper/8115-efficient-high-dimensional-bayesian-optimization-with-additivity-and-quadrature-fourier-features. I would appreciate if the authors would at least provide a high-level discussion on similarities and differences between these type of approaches.\n2- Thm7: r = 2^k1 C_1 and r = 2^-k2 C_2 are the only two possible radii? Is the statement valid for any choice in the range?\n3- Thm13: Unlike the statements in Sect.3.2 and 3.3, here the result is reported in terms of x_T (instead of f(x_T)). This is perfectly fine, but the guarantee you obtain is not an epsilon accuracy, but Q^{3/2}epsilon. If we want to obtain an epsilon accuracy, how much is the number of evaluation going to change? It seems like it would just make an additional Q appear in the log, but I would like the authors to confirm.\n4- Thm13: \"High-probability\": could you make this more explicit? Can I make the probability arbitrarily close to 1? How would it appear in the number of iterations? As just a log(1/delta) term?\n5- Thm14 is reported for \"suitable parameters\". Although this choice of parameter actually appears in Alg.2, it would be more complete to report it in the statement as well.\n6- Fig1 bottom line, first two charts display a weird behavior for GLD-Fast, where the error seems to plateau and spot decreasing. Can you explain why this is happening? Is it due to wrong parameters \\hat alpha and \\hat beta?\n\nMinor comments:\n- In the proof of Lem.8, it would be helpful to have a graphical representation of the spheres and the hyperspherial caps.\n- In the proof of Lem.15, you mention \"strong smoothness assumption\", it should be just smoothness.\n- It would be helpful to have more intuition on the why the algorithm is able to adapt to the actual dimensionality of the problem. My understanding is that the probability to pick a point of lower value is increased and since the algorithm is testing different radii and pick the best point, it successfully adapt to this better situation.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1geUE_Hcr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nUpdate after rebuttal: I found the rebuttal convincing and I liked the fact that concerns regarding empirical justification were addressed. Consequently, I increase my score from \"Weak Reject\" to \"Weak Accept\".\n--------------------------\nThis paper focuses on derivative-free, or zero-th order, optimization. That is the setting where a function may be continuous and/or smooth and/or (quasi)-convex, however, we do not have access to the gradients. As such, it is not possible to apply standard gradient descent methods. The paper proposes an algorithm for \"gradientless\" descend. The basic intuition is that by careful randomly sampling it is quite probable that a lower objective value will be attained. Doing so recursively can then lead to the optimum with high probability. Clearly, in such a setting it is quite important to clarify what is \"careful random sampling\". To this end the paper casts this as sampling from a Gaussian ball of specific radius, chosen such that the samples are with high probality below the current level set (the hyperplance of equivalent solutions f(x) as our current solution f(x_t)). The paper derives and proves various theorems on how to select the optimal radius and how to perform the sampling. Specifically, the case of strongly convex and smooth functions is analyzed, however, the paper also shows how this generalizes to functions after a monotone transformation (thus leading to quasi-convex functions) and with extra error perturbations. The proposed algorithm is compared on a synthetic experiment, and a selection of MuJoCo benchmarks.\n\nStrengths:\n+ The derivations and the theorems are non-trivial. There is some serious analysis regarding the selection of radius of Gaussian balls. I would like to congratulate the authors for this. I particularly like the extension to having a perturbing function h(x), leading to a more realistic setup.\n+ I also particularly like that the algorithm is able to recover subspaces automatically. This definitely makes the algorithm much more practical and more efficient.\n+ The writing and the presentation are rather clear and well taken care of. Although there are several theorems, it was not too hard to follow the flow of the paper. The algorithm boxes are also concise and clear, helping with understanding the final result.\n\nWeaknesses:\n+ Although the contributions of the work are mostly on the theoretical side, I have a hard time grasping how useful is the algorithm in practice. For one, there is the assumption of strongly convex and smooth function. Granted, there is the relaxed case of having the perturbing function h(x), howevrer, in that case it seems that the algorithm becomes a slower by an order of 60 δ k Q_g(A). How fast or slow is this in practice? Even with applying the monotone function, the algorithm becomes more practical by being applicable to quasi-convex setups. However, how realistic is that a function will in practice be strictly monotone? While most of this may be hard to be theoretically proven, they can be experimentally tested.\n\n+ Also, given that the paper is interested in black box functions, we cannot have much information regarding the function. So, what happens when the function is not strongly convex or not always smooth? Furthermore, how realistic is to know the condition number, that is the maximum derivative (or an upper bound of it) since we do not have access to the gradients in the first place?\n\n+ I would say that the paper could benefit from a more extensive experimental section. Currently only a single synthetic function is analyzed, also under a single monotone exponential transformation. From a more practical point of view, MuJoCo environments are also examined. However, there exist no comparisons with other methods in the literature, including ARS. Another relevant algorithm to compare with would be the stochastic tree points (Bergou et al., 2019), if not experimentally at least theoretically. In the end, it quite unclear whether the algorithm work well in practice. Some experiments that could shed light would relate to how sensitive the algorithm is to the convexity/smoothness assumptions, how sensitive the algorithm is to the perturbing function h(x), how sensitive is the algorithm to the present of a lower-dimensional subspace that needs to be discovered. And for the MuJoCo experiments, the algorithm can compare at least with ARS.\n\n+ In the experiments it seems the paper is particularly good in high dimensions. Can this be more precisely connected to the derived theory in the discussion of the experiments? Does this relate to the better subspaces k that are discovered automatically by the algorithm?\n\n+ It is unclear how many evaluations are needed per step, that is what is the K value in the algorithm box? Also, there are at least two balls to sample from, so twice as many evaluations, correct?\n\n+ It is unclear why Bayesian Optimization is not considered for at least comparing experimentally. Currently, the paper discards them on the grounds that they do not provide strong theoretically guarantees. However, it would be interesting to examine at least in practice how good/bad are these algorithms in comparison to the proposed one. Two recent bayesian optimization papers that can be considered for continuous and discrete inputs are\n\n[1] BOCK: Bayesian Optimization with Cylindrical Kernels, C. Oh, E. Gavves, M. Welling, ICML 2018\n[2] BOCS: Bayesian Optimization of Combinatorial Structures, R. Baptista, M. Poloczek, ICML 2018\n\n+ The paper does not have a conclusion. That shows great sloppiness. Also, i/n the abstract, do you mean to say k>=n or k<=n?\n\nTo conclude, I recommend weak rejection only because I am not completely convinced by the experiments and do not know if the proposed algorithm is competitive against reasonable baselines and in more complex setups. I am more than happy to upgrade my score if experiments become more clear.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers an interesting algorithm on zeorth-order optimization and contains strong theory. All the reviewers agree to accept.
Decision: Accept (Spotlight)