Learning to Guide Random Search
Authors: Ozan Sener
Vladlen Koltun
Venue:  (2020)
Keywords: Random search
Derivative-free optimization
Learning continuous control

Abstract: We are interested in derivative-free optimization of high-dimensional functions. The sample complexity of existing methods is high and depends on problem dimensionality, unlike the dimensionality-independent rates of first-order methods. The recent success of deep learning suggests that many datasets lie on low-dimensional manifolds that can be represented by deep nonlinear models. We therefore consider derivative-free optimization of a high-dimensional function that lies on a latent low-dimensional manifold. We develop an online learning approach that learns this manifold while performing the optimization. In other words, we jointly learn the manifold and optimize the function. Our analysis suggests that the presented method significantly reduces sample complexity. We empirically evaluate the method on continuous optimization benchmarks and high-dimensional continuous control problems. Our method achieves significantly lower sample complexity than Augmented Random Search, Bayesian optimization, covariance matrix adaptation (CMA-ES), and other derivative-free optimization algorithms.

Published as a conference paper at ICLR 2020
LEARNING TO GUIDE RANDOM SEARCH
Ozan Sener Intel Labs
Vladlen Koltun Intel Labs
ABSTRACT
We are interested in ferivetive-free optimization of high-dimensional functions. The sample complexity of existing methods is high and depends on problem dimensionality, unlike the dimmensionalityindeeee ods. The recent success of deep learning suggests that many datasets lie on low-dimensional manifolds that can be represented by deep nonlinear models. We therefore consider derivative-free optimization of a high-dimensional func- tion that lies on a latent low-dimensional manifold. We develop an online learn- ing approach that learns this manifold while performing the optimization. In other words, we jointly learn the manifold and optimize the function. Our anal- ysis suggests that the presented method significantly reduces sample complex- ity. We empirically evaluate the method on continuous optimization benchmarks and high-dimensional continuous control problems. Our method achieves sig- nificantly lower sample complexity than Augmented Random Search, Bayesian optimization, covariance matrix adaptation (CMA-ES), and other derivative-free optimization algorithms.
rates of first-order meth-
INTRODUCTION
A typical approach to machine learning problems is to define an objective function and optimize over a dataset. First-order optimization methods are widely used for this purpose since they can scale to high-dimensional problems and their convergence rates are independent of problem dimensionality most cases. However, gradients are not available in many important settings such as control, black-box optimization, and interactive learning with humans in the loop. Derivative- free optimization (DFO) can be used to tackle such problems. The challenge is that the sample complexity of DFO scales poorly with the problem dimensionality. The design of DFO methods that solve high-dimensional problems with low sample complexity is a major open problem.
The success of deep learning methods suggests that high-dimensional data that arises in real-world settings can commonly be represented in low-dimensional spaces via learned nonlinear features. In other words, while the problems of interest are high sigh-dimensional, the data typically lies on low- dimensional manifolds. If we could perform the optimization directly in the manifold instead of the full space, intuition suggests that could reduce the sample complexity of DFO methods since their convergence rates are generally a function of the problem dimensionality (Nesterov & Spokoiny] 2017 Dvurechensky al. 2018). In this paper, we focus on high-dimensional data distributions that are drawn from low-dimensional manifolds. Since the manifold is typically not known prior to the optimization, we pose the following question. Can we develop an adaptive derivative-free opti- mization algorithm that learns the manifold in an online fashion while performing the optimization?
There exist DFO methods that aim to identify low-dimensional search space (Maheswaranathan et al.) 2019 Choromanski et al. 2019). However, they are limited to linear subspaces. In contrast, we propose to use expressive nonlinear models (specifically, neural networks) to represent the mani- fold. Our approach not only increases expressivity but also enables utilization of domain knowledge concerning the geometry of the problem. For example, if the function of interest is known to be translation invariant, convolutional networks can be used to represent the underlying manifold struc- ture. On the other hand, the high expressive power and flexibility brings challenges. Our approach requires solving for the parameters of the nonlinear manifold at each iteration of the optimization. To address this, we develop an efficient online method that learns the underlying manifold while the function is being optimized.

---

Published as a conference paper at ICLR 2020
We specifically consider random search methods and extend them to the nonlinear manifold learn- ing setting. Random search methods choose a set of random directions and perform perturbations to the current iterate in these directions. Differences of the function values computed at perturbed points are used to compute an estimator for the gradient of the function. We first extend this to random search over known manifold and show that sampling directions in the tangent space of the manifold provides a similar estimate. We then propose an online learning method that estimates this manifold while jointly performing the optimization. We theoretically analyze sample complex- ity and show that our method reduces it. We conduct extensive experiments on continuous control problems, continuous optimization benchmarks, and gradient- optimization of an airfoil. The re- sults indicate that our method significantly outperforms state-of-the-art derivative-free optimization algorithms from multiple research communities.
2 PRELIMINARIES
We are interested in high-dimensional stochastic optimization problems of the form
min f(x) = [F( E)]. xERd
(I)
where x is the optimization variable and f Rd + R is the function of interest, which is de- fined as expectation over noise variable c We assume that the stochastic function is bounded (F | < 52). L-Liscchit, and u-smooth with respect to x for all &, and has uniformly bounded variance (E.g (F(( {) - [( S Vr). In DFO, we have no access to the gradients. Instead, we only have zeroth-order access by evaluating the function F (i.e. sampling F)x,)) for the input x).
We are specifically interested in random search methods in which an estimate of the gradient is computed using function evaluations at points randomly sampled around the current iterate. Before we formalize this, we introduce some definitions. Denote the d-dimensional unit sphere and unit ball by Sd-1 and Bd, respectively. We define smoothed function following Flaxman al. (2005). For function f Rdd IR. its 8-smoothed version is f(x By [f(( + 5v)]. The main workhorse of random search is the following result by Flaxman et al. 2005). Let s be a random vector sampled from the uniform distribution over gd-1, Then f(x ds an unbiased estimate of the gradient of the smoothed function:
8 (x).
E g (F(xx + ús, E)s]
We use antithetic samples since this is known to decrease variance (Kroese et al. 2013) and define the final gradient estimator as y(x, s) (F(x + os, - F(x - òs, E) s. Extending (2) to the
antithetic case, Eg, [w(x, = 24 d V (x).
A simple way to optimize the function of interest is the gradient estimate in stochastic gradient descent (SGD), as summarized in Algorithm I This method has been analyzed in various forms and its convergence characterized well for nonconvex smooth functions. We restate the convergence rate and defer the constants and proof to Appendix A.2
Proposition 1 (Flaxman et al. 2005; Vemula et al. 2019). Let f(x) be differentiable, L-Lipschitz. and p-smoooh. Consider running random search (Algorithm 7 for steps. Let k. for simplicity. Then
=
E s (I
3 ONLINE LEARNING TO GUIDE RANDOM SEARCH
Proposition implies that the sample complexity of random search scales linearly with the dimen- sionality. This dependency is problematic when the function of interest is high-dimensional. We argue that in many practical problems, the function of interest lies on a low-dimensional nonlinear
T.- ipschitz and j-smooth: [f(x)) f(y)l S T. ylla and Vxf(x) Vxf(v)ila s sulx-yll yll2 Vx.
2

---

Published as a conference paper at ICLR 2020
Algorithm Random Search
Algorithm Manifold Random Search
for f 1 to do
for to do
g: GGAAESS(xx x =x x ag'
g MANIFOLDGHADDDSSTTT..EEEE
3: x x'
og
4: end for
4: end for
1: procedure GRADEST(x,, 6)
1: procedure MANIFOLDGRRADESTI... 0.5) Normalize: J, GramSchmid((J)
Sample: Si...., 8t gd-1
3: Query: yi = f((x ds;) f(x 68.)
3: Sample: S,....,50 ~ 3 f(x +J,g,) f(x 5Jg8,)
Estimator: g 25 Σ 9/8,
4: Query:
5: return g. NeIN
5: Estimator: 5 20 Σ J1
6: end procedure
return g, (J,s.hec14)
procedure
manifold. This structural assumption will allow us significantly reduce the sample complexity of random search, without knowing the manifold priori.
Assume that the function of interest is defined manifold can be defined via a nonlinear parametric family (e.g. a neural network). Formally, we are interested in derivative-free optimization of functions with the following properties:
n-dimensional manifold (n d) and this
Smoothness: F(,,C) Rd IR is p-smoooth and L-Lipschitz for all ç.
Manifold: E) is defined
n-dimensional manifold M for all Ç.
Representabilitt; The manifold M and the function of interest can be represented using parametrized function classes r-: 0) and g(:; Formally, given &, there exist 0* and e such that Fxx, 5) g(r(x; 8*): *)* VX R
We will first consider an idcalized setting where the manifold is already known (i.e. know 0*). Then we will extend the developed method to the practical setting where the manifold is not known in advance and must be estimated with prior knowledge the optimization progresses.
3.1 UP: RANDOM SEARCH OVER KNOWN MANIFOLD
If the manifold is known a priori, we can perform random search directly over the manifold instead of the full space. Consider the chain rule applied to g( 0): 1) as Vxf(x) [xx 8*) Vrg(r v) where J (x; 6²)) 0r(x;9")/aa and column space of the Jacobian of the parametric family. In light of this result, we can perform random search in the column space of the Jacobian, which has lower dimensionality than the full space.
r(x, 8*). The gradient of the function of interest lies in the
For numerical stability, we will first orthonormalize the Jacobian using the Seham- proce- dure, and perform the search in the column space of this orthonormal matrix since it spans the same space. We denote the orthonormalized version of Jxx; 0*) by J, 0*).
In order to perform random search, we sample an n-dimensional vector uniformly S"-1) and lift it to the input space via (x; 0*)s. As a consequence of the manifold Stokes' theorem, using the lifted vector random direction gives unbiased estimate of the gradient of the smoothed function as
28 Vx.oo (x);
Es [v(x (x; 0*)
where the smoothed function is defined fo- (x) EE-Bz [f(x + 5J, 8Jy(x;) 0*) V)). We show this result as Lemma ii Appendix A.I We use the resulting gradient estimate in SGD. The following proposition summarizes the sample complexity of this method. The constants and the proof are given in Appendix A.2
Proposition 2. Let f(x) be differentiable, L-Lipschitz, and y-smooth. Consider running manifold random search (Algorithm for steps. Let for simplicity. Then
E E (
( - 8
3

---

Published as a conference paper at ICLR 2020
3.2 JOINT OPTIMIZATION AND MANIFOLD LEARNING
When n < d, the reduction in the sample complexity of random search (summarized in Proposi- tion ( is significant. However, the setting of Algorithm and Proposition 2is impractical since the manifold is generally not known priori. We thus propose to minimize the function and learn the manifold jointly. In other words, we start with an initial guess of the parameters and solve for them at each iteration using all function evaluations that have been performed so far.
Our major objective is to improve the sample efficiency of random search. Hence, minimizing the sample complexity with respect to manifold parameters is intuitive way approach the problem. SGD using biased gradients in Appendix AA.3. and show the following informal result. Consider running manifold random search with a sequence of manifold parameters 01, 2/1 ,.... ...,,""" gradients, defined as SUBOPTIMALITY
We analyze the sample complexity
.J for T steps. Then the additional suboptimality caused by biased Eis
[x)), is bounded as follows:
SUBOPTIMALITY( +') SUBOPTIMALITY(01 .0) T - V')2.. (4)
Vxg(r(xx ('))
where SUBOPTIMALITY(HH 1b*) is the suboptimality of the oracle case (Algorithm) 2 Our aim is to minimize the additional suboptimality with respect to O and tha However, we do not have access to (x)(x) since we are in a derivative-free setting. Hence we cannot directly minimize
At each iteration, we observe y(x', s¹). Moreover, s(x(,s')= Vx {) ( due to the smoothness. Since we observe the projection the gradient onto the chosen directions, we minimize the projection of (4) onto these directions. Formally, we define our one-step loss as
L(x', s',",,'',',, = (y(x',s)) s') -s (x0(((x(00)) 2
(5)
28
We use the Follow the Regularized Leader (FTRL) algorithm (Hazan 2016 Shalev-Shwartz 2012) to minimize the aforementioned loss function and learn the manifold parameters:
g++1 16- = arg min Σ c(et 0,,4) + XR(0, v), 0,0
(6)
where the regularizer R(0, v) = [rx((r(x'; (9)) Vxg(r(x': 0);
[|2 is a temporal smooth-
ness term that penalizes sudden changes in the gradient estimates.
Algorithm summarizes our algorithm. We add exploration by sampling a mix of directions from the manifold and the full space. In each iteration, sample directions and produce two gradient estimates Em using the samples from the tangent space and the full space, respectively. We mix them to obtain the final estimate g = (1 3)gm + fge. We discuss the implementation details of the FTRL step in Section [ In our theoretical analysis. we assume that (6) can be solved optimally. Although this is a strong assumption, experimental results suggest that neural networks can easily fit any training data (Zhang et al. 2017). Our experiments also support this observation.
Theorem I states our main result concerning the sample complexity of our method. As expected, the sample complexity includes both the input dimensionality d and the manifold dimensionality n. On the other hand, the sample complexity only depends on ny/d rather than d. Thus our method significantly decreases sample complexity when n < d.
Theorem 1. Let fxx) be bounded, L-Lipschitz, and p-smooth. Consider running learned manifold random search (Algorithm 3
for T steps. Let ke = 1 and km = 1 for simplicity. Then
T
ElVxf(x))l
o <0 (dtT-1 + (dt + nat yr + (n3 + +dtn
T
Proof sketch. We provide short proof sketch here and defer the detailed proof and constants to Appendix A.3 We start by analyzing SGD with bias. The additional suboptimality of using 6", 36 instead of 0* x can be bounded by (4).
4

---

Published as a conference paper at ICLR 2020
The empirical loss we minimize is the projection of onto randomly chosen directions. Next, show that the expectation of the empirical loss is when the directions are chosen uniformly at random from the unit sphere:
Es-- '','','''0'''00 - dT Σ [V Vxg(r(xx; 0*); ll2
A crucial argument in our analysis is the concentration of the empirical loss around its expectation. In order to study this concentration, the analysis of generalization in online learning by Kakade & Tewari (2009). Our analysis bounds the difference
Freedman's inequality (Freedman, 1975), inspired by
Ie Egd-1
Σ T L Σ
L where L L(x", , 0r, 1
t=1
Next, we use the FTL-BTL Lemma (Kalai & Vempala 2005) to analyze the empirical loss Σ L'. We bound the empirical loss in terms of the distances between the iterates Σ ||x++1 x² 1|2- Such bound would not be useful in an adversarial setting since the adversary chooses x", but we set appropriate step sizes, which yield sufficiently small steps and facilitate convergence.
Our analysis of learning requires the directions in 7 to be sampled from unit sphere. On the other hand, our optimization method requires directions to chosen from the tangent space of the manifold. We mix exploration (directions sampled from gd-1) and exploitation (directions sampled from the tangent space of the manifold) to address this mismatch. We show that mixing weight = 1/a yields both fast optimization and no-regret learning. Finally, we combine the analyses of empirical loss, concentration, and SGD to obtain the statement of the theorem.
4 IMPLEMENTATION DETAILS AND LIMITATIONS
We summarize important details here and elaborate further in Appendix B A full implementation is available at https:: // //git thub. coommittee - issl/ /LMRS
Parametric family. We multilayer perceptrons with ReLU nonlinearities to define and We initialize our models with standard normal distributions. Our method thus starts with random search at initialization and transitions manifold random search as the learning progresses.
Solving FTRL. Results on training deep networks suggest that local SGD-based methods perform well. We thus use SGD with momentum solver for FTRL in (6). We do not solve each learning problem from scratch but initialize with the previous solution. Since this process may be vulnerable local optima, we fully solve (6) from scratch for every 100th iteration of the method.
Computational complexity. Our method increases the amount of computation since we need to learn model while performing the optimization. However, in DFO, the major computational bot- tleneck is typically the function evaluation. When efficiently implemented on a GPU, the time spent on learning the manifold is negligible in comparison to function evaluations.
Parallelization. Random search is highly parallelizable since directions can be processed independently. Communication costs include i) sending the current iterate to work- ers. ii) sending directions to each corresponding worker, and iii) workers sending the function values back. When the directions are chosen independently, they can be indi- cated each worker via single integer by first creating shared noise table in pre- processing. For a d-dimensional problem with random directions, these costs are d, k. and k; respectively. The total communication cost is therefore d + 2k. In our method, each worker also needs copy of the Jacobian, resulting in a communication cost of d + 2k + kd. Hence our method increases commu- nication cost from d 2k
Algorithm 3 Learned Manifold Random Search (LMRS)
1:
for = to do
2:
g St GRADEST(X 5)
3:
gm: St MANIFOLDGRADESTTSS J(x;)
4:
g' Bk.
k.
g
+
(1
km gm
.9)mm
5: x(+1 x² ag'
6: g++1 41 arg ming,e Ei Lixt(xx St O, 0. XR(O,
+ 2k + kd.
7: end for
See Algorithms definitions of GRADEST and MANIFOLDGRADDEST.
5

---

Published as a conference paper at ICLR 2020
Hoppeevi
Avergg Rewaar
Averae Reward
1::0
verrgge Rewward
5030
4030
2030
2330
1299
3330
180
Number
Number Episodes
Number Episodes
Walker2d-r1
Ant-o1
Homanold-v1
Average Heearrd
A Average Rowwar
A Avarugee Rawsard
5000
icec
6030
3000
2000
1000
2002
2330
10e0
Number of Exilsdess
N Number of Egissoees
Numbee of Episodes
LMRS
ARS
Guided
CMA-ES
Figure I: Average reward vs, number of episodes for MuJoCo locomotion tasks. each condition, we perform 5 runs with different random seeds. Shaded areas represent standard deviation. The grey horizontal line indicates the prescribed threshold which the task is considered 'solved'.
5 EXPERIMENTS
We empirically evaluate the presented method (referred as Learned Manifold Random Search (LMRS)) on the following sets of problems. i) We use the MuJoCo simulator (Todorov et al.) (0122) evaluate our method on high-dimensional control problems. ii) We use 46 single-objective un- constrained functions from the Pagmo suite of continuous optimization benchmarks (Biscani et al.] 2019). iii) We use the XFoil simulator (Drela 1989) to benchmark gradient-free optimization of an airfoil.
We consider the following baselines. i) Augmented Random Search (ARS): Random search with all the augmentations from Mania et al. (2018). ii) Guided ES (Maheswaranathan al., 2019): A method to guide random search by adapting the covariance matrix. ii) CMA-ES (Hansen 2016): Adaptive derivative-free optimization based on evolutionary search. iv) REMBÓ (Wang et al. 2016): A Bayesian optimization method which uses random embeddings in order to scale to high-dimensional problems. Although CMA-ES and REMBO are not based random search, we include them for the sake of completeness. Additional implementation details are provided in Appendix B
5.1 LEARNING CONTINUOUS CONTROL
random search to learn control of highly articu- lated systems. The MuloCo locomotion suite (Todorov et al.] |l.1)201))) includes six problems of varying difficulty. We evaluate method and the baselines on all of them. We use linear policies and in- clude all the tricks (whitening the observation space and scaling the step size using the variance of the rewards) from Mania al. (2018). We report average reward over five random experiments versus the number of episodes (i.e. number of function evaluations) in Figure [ We also report the average number of episodes required to reach the prescribed reward threshold at which the task is considered 'solved' in Table []] We include proximal policy optimization (PPO) (Schulman et al., 2017 Hill et al. 2018) for reference. Note that our results are slightly different from the numbers reported by Mania et al. (2018) as we use 5 random seeds instead of 3.
Following the setup of Mania et al. 2018))
The results suggest that our method improves upon ARS in all environments. Our method also outperforms all other baselines. The improvement is particularly significant for high-dimensional problems such as Humanoid. Our method is at least twice as efficient as ARS all environments except Swimmer, which is the only low-dimension fails to solve the Humanoid task, which we think is due to biased gradient estimation. Furthermore, CMA-ES performs similarly to ARS. These results suggest that challenging task like Humanoid out of reach for heuristics like local adaptation of the covariance matrix due to high stochasticity and nonconvexity.
problem in the suite. Interestingly, Guided-ES

---

Published as a conference paper at ICLR 2020
Swimmerr-V1 (2 Cores)
Hopper-v1 (8 Curos)
HoliChoctah.vl (10 Cores)
Aveeage Reeward
400
Rawward
Averge Roward
13300
200
4230
200
2390
3330
2390
-20
250
500
750
2393
1250
1500
3750
2000
200
400
60B
339
3000
100
230
300
800
300
900
500
339
Secsonba
Sucoonte
Secundl
Corce)
Clores)
Humanold-v1 (120 Cores)
Average Rewward
0000
Taaward
5000
Averuge Rewurd
8000
8000
w000
3000
5000
3000
2000
1065
2283
3333
500
1000
2520
Lokeo 1266E 1750
Seconds
Seconde
Seconds
LMRS
ARS
Guided
CMA-ES
Figure 2: Average reward vs. wall-clock time for MuJoCo locomotion tasks. In each condition, we perform runs with different random seeds. Shaded areas represent standard deviation. The grey horizontal line indicates the prescribed threshold at which the task is considered 'solved'. Mcasure- ments are performed on Intel Xcon E7-8890 v3 processors and Nvidia GeForce RTX 2080 Ti GPUs. We list the number of cores used for each experiment.
REMBO only solves the Swimmer task and fails to solve others. We believe this is due to the fact that these continuous control problems have no global structure and are highly nonsmooth. The number of possible sets of contacts with the environment is combinatorial in the number of joints, and each contact configuration yields a distinct reward surface. This contradicts the global structure assumption in Bayesian optimization.
Wall-clock time analysis. Our method performs additional computation as we learn the underlying manifold. In order quantify the effect of the additional computation, we perform wall-clock time analysis and plot average reward vs wall-clock time in Figure 2 Our method outperforms all baselines with similar margins to Figure The trends and shapes of the curves in Figures and are similar. This is not surprising since computation requirements of all the optimizers are rather negligible when compared with the simulation time of MuJoCo.
The only major differences we notice are on the Hopper task. Here the margin between our method and the baselines narrows and the relative ordering of Guided-ES and ARS changes. This is due to the fact that simulation stops when the agent falls. In other words, the simulation time depends on the current solution. Methods that query the simulator for these unstable solutions lose less wall-clock time.
Quantifying manifold learning performance. In order to evaluate the learning performance, we project the gradient of the function to the tangent space of the learned manifold and plot the norm of the residual. Since we do not have access to the gradients, we estimate them at 30 time instants, evenly distributed through the learning process. We perform accurate gradient estimation using very large number of directions (2000). We compute the norm of the residual of the projection as Et=l ||V
PJ, .r) (V fxff(")) ]],,, where P (-) is projection onto the column space of A. The results are visualized in Figure Our method successfully and quickly learns the manifold
in all cases.
Self Baselines
Task
Threshold
LMRS
ARS CMA-ES Guided ES
PPO
REMBO
No learning
Offline I.
Swimmer
325
222
381
460
640
790
520
320
325
Hopper
3120
2408
6108
14640
5288
10397
(0/5)
5561
(4/5)
11616
HalfCheetah
3430
1128
4284
2888
8004
6820
(0/5)
6528
3416
Walker
4390
15525
31240
96525
62544
102440
(0/5) 295493
(3/5)
118640
Ant
3580
9240
20440
154440
152400
52553
(0/5)
24520(4/5)
63720(2/5)
Humanoid
6000
108133
220733
1923030
(0/5)
200430
(0/5)
267260(2/5)
451260(2/5)
Table Number of episodes required to reach the prescribed threshold on each MuloCo locomotion task for method, baselines, and ablations. Lower is better. We average over five random seeds.
We denote the number of successful trials as (success/tric trial) and average over successful trials only.
If the number of successful trials is not noted, the method solved the task for all random seeds.
7

---

Published as a conference paper at ICLR 2020
HaltCheetah-v1
Hopper-v1
Ablation studies. Our method uses three major ideas. i) We learn a manifold that the function lies on. ii) We learn this manifold in online fashion. iii) We perform random search on the learned manifold. To study the impact of each of these ideas, we perform the following exper- iments. i) No learning. We randomly initialize the manifold r(:; 0) by sampling the entries of from the standard normal distribution. Then we perform random search on this random mani- fold. ii) No online learning. We collect an of- fline training dataset by sampling x, values uni- formly at random from a range that includes the optimal solutions. We evaluate function values at sampled points and learn the manifold. We perform random search on this manifold without updating the manifold model. iii) No search. We use the gradients of the estimated function (V (rx((((;)) yes))) as surrogate gradients and minimize the function of interest using first-order methods.
Rusding Nood
2000 4000
8000
10c
2000 Number of Episudes
Number of Episodes
Humanoid-v1
Walker2d-v1
Beotdha Nom
MAON corpisss
2016 Number of Episodess
RE0K 500K
205
43K
00x 20K
Number of Episodes
Figure 3: Manifold learning accuracy. We plot -i=1 [Vxx(xx) (x,((xto (Vx In order to estimate the gradient, we use GRADEST with high number of directions.
We list the results in Table We do not include the no-search baseline since it fails to solve any of the tasks. Failure of the no-search baseline suggests that the estimated functions are powerful enough to guide the search, but not accurate enough for optimization. The no-learning baseline outperforms ARS on the simplest problem (Swimmer), but either fails completely or increases sample complexity on other problems, suggesting that random features are not effective, especially on high-dimensional problems. Although the offline learning baseline solves more tasks than the no-learning one, has worse sample complexity since initial offline sampling is expensive. This study indicates that all three of the ideas that underpin our method are important.
5.2 CONTINUOUS OPTIMIZATION BENCHMARKS
We use continuous optimization problems from the Pagmo problem suite (Biscani et al. 2019). This benchmark includes minimization of 46 functions such as Rastrigin, Rosenbrock, Schwe- fel, etc. (See Appendix B for the complete list.) We use ten random starting points and re- port the average number of function evaluations required to reach stationary point. Figure reports the results as performance profiles (Dolan & Moré, (002). Performance profiles rep- resent how frequently method is within distance т of optimality. Specifically, if we de- note the number of function evaluations that method m requires to solve problem p by (p) and the number of function evaluations used by the best method by (*) min. Tm(p). (p), the performance profile is the fraction of problems for which method m is within distance of the best: I/N, E, (p) (p) S r). where 1[]] the indicator function and Np the number of problems.
As can be seen in Figure 4 our method out- performs all baselines. The success of our method is not surprising since the functions are typically defined as nonconvex functions of some statistics, inducing manifold structure by construction. REMBO (Bayesian optimiza- tion) is close to our method and outperforms the other baselines. We believe this is due to
100
Fraction of problems (%)
80
60
LMRS
ARS
Guided ES
the global geometric structure of the consid- cred functions. Both CMA-ES and Guided-ES outperform ARS.
CMA-ES
REMBO
10
10a
100
5.3 OPTIMIZATION OF AN AIRFOIL
Figure 4: Performance profiles of our method and baselines optimization benchmark.
We apply our method to gradient-free opti- mization of a 2D airfoil. We use a computa- tional fluid dynamics (CFD) simulator, XFoil
8

---

Published as a conference paper at ICLR 2020
Airfoil after 1500 Simulations
Init
LMRS
ARS
Guided ES
CMA-ES
REMBO
LIFT
-0.229
2.0126
0.567
1.231
1.418
1.8645
DRAG
0.040
0.0389
0.007
0.0598
0.0249
0.02123
LIFT DRAG
-0.269
1.9737
0.560
1.1712
1.3931
1.8432
Foil
Table 2: Generated airfoils with their lift and drag values after 1500 calls to XFoil
Drela 1989
Drela 1989), which can simulate an airfoil using its contour plot. We parametrize the airfoils using smooth polynomials of up to 36 degrees. We model the upper and lower parts the airfoil with different polynomials. The dimensionality of the problem is thus 72. XFoil can simulate various viscosity properties, speeds, and angles of attack. The details are discussed in Appendix B We plot the resulting airfoil after 1500 simulator calls in Table 2 We also report the lift and drag of the resulting shape. The objective we optimize is LIFT DRAG. Table 2 suggests that all methods find airfoils that can fly (LIFT DRAG). Our method yields the highest LIFT DRAG. Bayesian optimization outperforms the other baselines.
5.4 EFFECT OF MANIFOLD AND PROBLEM DIMENSIONALITY
In this section, we perform a controlled experiment to understand the effect of problem dimension- ality (d) and manifold dimensionality (n). We generate a collection of synthetic optimization prob- lems. All synthesized functions follow the manifold hypothesis: f(x) = gr((x, 8*)). where r(x, f*) is a multilayer perceptron with the architecture Linear(d, 2m) - ReLU - I Linear (2n, n) and g(-) is a randomly sampled convex quadratic function. In order to sample a convex quadratic function, we sample the parameters of the quadratic function from Gaussian distribution and project the result to the space of convex quadratic functions.
We choose d E {100, 1000} and plot the objective value with respect the number of function evaluations for various manifold dimensionalities n in F The results suggest that for a given ambient dimensionality d, the lower the dimensionality of the data manifold n, the more sample- efficient our method. In concordance with our theoretical analysis, the improvement is very signifi- cant when & d, as be seen in the cases
5, 1000 and 2, 100.
Interestingly, our method is effective even when the manifold assumption is violated (n = d). We hypothesize that this is due anisotropy in the geometry of the problem. Although all directions are important when n = d, some will result in faster search since the function changes more along them. It appears that our method identify these direction and thus accelerate the search.
Dimennsion 100
Manifold 1lm
2
Dimension 100
Manifold Dim 25
Dimeusion 100
Manifold 13m 100
1.50
LMRS
LAIRS
1.00
Otgeative
1.00
AIS
Dijecttoon
ARS
ABS
030
022
88
50
156
158
241
so
Numbbr Function Ev Evaluations
Function Evaluntions
Number Function Evaluntions
Dimeusion 1000 / Monifold Dim
Dimecsion 1000
Manifold Dim
360
Diucussio 1000
Monifold Dim
1000
Onjeccive
&
ARS
ARS
OPojestive
9
ARS
0.2
00
Number
200
Evaluations
300
50
350
350
303
221
520
300
330
430
530
830
303
Figure 5: Effect of problem dimensionality and manifold dimensionality. Average objective value
over 10 random seeds vs. number of function evaluations. Shaded areas represent standard devia- tion.

---

Published as a conference paper at ICLR 2020
6 RELATED WORK
Derivative-free optimization. We summarize the work on DFO that is relevant to our paper. For a complete review, readers are referred to toCCutóoio et al. (2017) and Conn et al. (2009). We are specif- ically interested in random search methods, which have been developed as early as Matyas (9655)
and Rechenberg (1973). Convergence properties of these methods have recently been analyzed by Agarwal et al. (2010). Bach & Perchet (2016). Nesterov & Spokoiny (017), and [Duurcchessyy
et al." (2018). A lower bound on the sample complexity for the convex case has been given by Duchi al. (2015) and Jamieson et al. (2012). Bandit convex optimization is also highly relevant and we utilize the work of Flaxman et al. (2005) and [Shamir (2013).
and
Random search for learning continuous control. I Learning continuous control is an active research topic that has received significant interest in the reinforcement learning community. Recently, Sali- mans et al. (2017) and Mania et al. (2018) have shown that random search methods are competitive with state-ol-the
policy gradient algorithms in this setting. Vemula et al. (2019) analyzed this phenomenon theoretically and characterized the sample complexity of random search and policy gradient methods for continuous control.
Adaptive random search. There are various methods in the literature that adapt the search space by using anisotropic covariance as the case of CMA-ES (Hansen et al., 2003 Hansen] (016)) guided evolutionary search (Maheswaranathan al.] 20T9). and active subspace methods (Choromanski iet al. 2019). There are also methods that enforce structure such as orthogonality in the search directions (Choromanski et al. 2018). Other methods use information geometry tools as in Wierstra et al. (2014) and Glasmachers et al. (2010). Lehman et al. (2018) use gradient magnitudes to guide coutt-evolutionary search. [Staines & Barber (2012) use a variational lower bound guide the search. In contrast to these methods, we explicitly posit nonlinear manifold structure and directly learn this latent manifold via online learning. Our method is the only one that can learn an arbitrary nonlinear search space given a parametric class that characterizes its geometry.
Adaptive Bayesian optimization. Bayesian optimization (BO) is another approach to zeroth-order optimization with desirable theoretical properties (Srinivas et al.) 2010). Although we only interested in methods based on random search, some of the ideas we use have been utilized in BO. Calandra al. (2016) used the manifold assumption for Gaussian processes. In contrast method, they use autoencoders for learning the manifold and assume initial availability of offline data. Similarly, Djolonga al.] (2013) consider the case where the function of interest lies on some linear manifold and collect offline data to identify this manifold. In contrast, we only use online information and our models nonlinear. Waan al. (2016) and Kirschner al. (2019) propose using random oiwddimnniional features instead of adaptation. Rolland et al. (2018) design adaptive BO methods for additive models. Major distinctions between our work and the adaptive BO literature include our use of nonlinear manifolds, no reliance on offline data collection, and formulation of the problem as online learning.
7 CONCLUSION
We presented Learned Manifold Random Search (LMRS): a derivative-free optimization algorithm. Our algorithm learns the underlying geometric structure of the problem online while performing the optimization. Our experiments suggest that LMRS is effective wide range of problems and significantly outperforms prior derivative-free optimization algorithms from multiple research communities.
REFERENCES
Alekh Agarwal, Ofer Dekel, and Lin Xiao. Optimal algorithms for online convex optimization with multi-point bandit feedback. In Conference on Learning Theory (COLT), 2010.
Francis R. Bach and Vianney Perchet. sighly-smooth zero-th order online optimization. In Confer- ence on Learning Theory (COLTT) 2016.
10

---

Published as a conference paper at ICLR 2020
Francesco Biscani, Dario Izzo, Wenzel Jakob, Marcus Martens, Alessio Mereta, Cord Kaldemeyer, Sergey Lyskov, Sylvain Corlay, Benjamin Pritchard, Kishan Manani, et al. Esa/Pagmo2: Pagmo 2.10, 2019.
Roberto Calandra, Jan Peters, Carl Edward Rasmussen, and Mare Peter Deisenroth. Manifold Gaus- sian processes for regression. In International Joint Conference on Neural Networks (LJCNN), 2016.
Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard E. Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. In International Conference on Machine Learning (ICML), 2018.
Krzysztof Choromanski, Aldo Pacchiano, Jack Parker-Holder, Yunhao Tang, and Vikas Sindhwar wani. From complexity to simplicity: Adaptive ES-active subspaces for blackbox optimization. In Neural Information Processing Systems, 2019.
Andrew R Conn, Katya Scheinberg, and Luis N Vicente. Introduction to Derivative-Fie Optimiza- tion. SIAM, 2009.
Ana Luísa Custódio, Katya Scheinherg, and Luís Nunes Vicente. Methodologies and software for derivative-free optimization. Advances and Trends in Optimization with Engineering Applica- tions, 2017.
Josip Djolonga, Andreas Krause, and Volkan Cevher. High-dimensional Gaussian process bandits. In Neural Information Processing Systems, 2013.
Elizabeth Dolan and Jorge Moré. Benchmarking optimization software with performance profiles. Mathematical Programming, 91, 2002.
Mark Drela. XFOIL: An analysis and design system for low Reynolds number airfoils. In Low Reynolds Number Aerodynamics, 1989.
John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of function evaluations. IEEE Transactions on Information Theory, 2015.
Pavel Dvurechensky, Alexander Gasnikov, and Eduard Gorbunov. An accelerated method for derivative-fres smooth stochastic convex optimization. arXiv://822.99022, 2018.
Abraham Flaxman, Adam Tauman Kalai, and H. Brendan McMahan. Online convex optimization in the bandit setting: Gradient descent without gradient. In Symposium on Discrete Algorithmss (SODA), 2005.
David A Freedman. On tail probabilities for martingales. Annals of Probability, 3(1), 1975.
Jacob R Gardner, Geoff Pleiss, David Bindel, Kilian Q Weinberger, and Andrew Gordon Wilson. GPyTorch: Blackbox matrix-matrix Gaussian process inference with GPU acceleration. In Neural Information Processing Systems, 2018.
Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming, SIAM Journal on Optimization, 23(4), 2013.
David Ginsbourger, Rodolphe Le Riche, and Laurent Carraro. Kriging is well-suited to parallelize optimization. In Computational Intelligence in Expensive Optimization Problems. Springer, 2010.
Tobias Glasmachers, Tom Schaul, Yi Sun, Daan Wierstra, and Jürgen Schmidhuber. Exponential natural evolution strategies. In Genetic and Evolutionary Computation Conference (GECCO), 2010.
Nikolaus Hansen. The CMA evolution strategy: A tutorial. arXiv:1604.00772 2016.
Nikolaus Hansen, Sibylle D. Müller, and Petros Koumoutsakos. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolutionary Computation, 11()), 2003.
11

---

Published as a conference paper at ICLR 2020
Nikolaus Hansen, Youhei Akimoto, and Petr Baudis. N01:10..28//zemoo.22555553 February 2019.
CMA-ES/pyema Github.
Zenodo,
Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4), 2016.
Ashley Hill, Antonin Raflin, Maximilian Ernestus, Adam Gleave, Anssi Kanervisto, Rene Traore, Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, et al. Stable baselines, https: 2018.
Kevin G. Jamieson, Robert D. Nowak, and Benjamin Recht. Query complexity of derivative-free optimization. In Neural Information Processing Systems, 2012.
Sham M Kakade and Ambuj Tewari. On the generalization ability of online strongly convex pro- gramming algorithms. In Neural Information Processing Systems, 2009.
Adam Tauman Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Jour- nal of Computer and System Sciences, 71(3), 2005.
Johannes Kirschner, Mojmír Mutný, Nicole Hiller, Rasmus Ischebeck, and Andreas Krause. Adap- tive and safe Bayesian optimization high dimensions via one-dimensional subspaces. In Inter- national Conference Machine Learning (ICML), 2019.
Dirk P Kroese, Thomas Taimre, and Zdravko Botev. Handbook of Monte Carlo Methods. John Wiley & Sons, 2013.
Joel Lehman, Jay Chen, Jeff Clune, and Kenneth O. Stanley. Safe mutations for deep and recurrent neural networks through output gradients. In Genetic and Evolutionary Computation Conference (GECCO), 2018.
Niru Maheswaranathan, Luke Metz, George Tucker, and Jascha Sohl-Dickstein. Guided evolution- ary strategies: Escaping the curse of dimensionality in random search. In International Confer- ence on Machine Learning (ICML), 2019.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies is competitive for reinforcement learning. In Neural Information Processing Systems, 2018.
Sébastien Marmin, Clément Chevalier, and David Ginsbourger. Differentiating the multipoint ex- pected improvement for optimal batch design. In Workshop on Machine Learning, Optimization, and Big Data, 2015.
J Matyas. Random optimization. Automation and Remote Control, 26(2), 1965.
Yurii Nesterov and Vladimir G. Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2), 2017.
Ingo Rechenberg. Exolutionsstrategii-- optimierung technischer systeme nach prinzipien der biolo- gischen information. StlliariiBBd Cannstatl: Friedrich Frommann Verlag. 1973.
Paul Rolland, Jonathan Scarlett, Ilija Bogunovic, and Volkan Cevher. High-dimensional Bayesian optimization via additive models with overlapping groups. In International Conference on Artifi- cial Intelligence and Statistics (AISTATS), 2018.
Nikitas Rontsis, Michael A. Osborne, and Paul Goulart. Distributionally ambiguous optimization techniques for batch Bayesian optimization. arXiv: 2017.
Tim Salimans, Jonathan Ho, Xi Chen, and Ilya Sutskever. Evolution strategies as scalable altema- tive to reinforcement learning, arXiv:1703.03800 2017.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv: /700070077777 2017.
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends R in Machine Learning, 4(2), 2012.
12

---

Published as a conference paper at ICLR 2020
Ohad Shamir. On the complexity of bandit and derivative-free stochastic convex optimization. In Conference on Learning Theory (COLT), 2013.
Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In International Conference on Machine Learning (ICML), 2010.
Joe Staines and David Barber. Variational optimization. arXiv: 0r/1::/2/2.4507. 2012.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physies engine for model-based control. In International Conference on Intelligent Robots and Systems (IROS), 2012.
Anirudh Vemula, Wen Sun, and J. Andrew Bagnell. Contrasting exploration in parameter and ac- tion space: A zeroth-order optimization perspective. In International Conference Artificial Intelligence and Statistics (AISTATS), 2019.
Ziyu Wang, Frank Hutter, Masrour Zoghi, David Matheson, and Nando de Freitas. Bayesian op- timization in billion dimensions via random embeddings. Journal of Artificial Intelligence Research, 55, 2016.
Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. Journal of Machine Learning Research (JMLR), 15, 2014.
Andrew Gordon Wilson and Hannes Nickisch. Kernel interpolation for scalable structured Gaussian processes (KISS-GP). In International Conference Machine Learning (ICML), 2015.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017.
13

---

Published as a conference paper at ICLR 2020
A PROOFS
A.1 GRADIENT ESTIMATOR
In this section, we show that when random directions are sampled in the column space of the or- thonormal matrix U, perturbations give biased gradient estimates of the manifold smoothed func- tion. Moreover, when U = U*, resulting gradients are unbiased. We formalize this with the following lemma.
Lemma 1. Let U* be an orthonormal basis for the tangent space of the n-dimensional manifold at point E M, U be another orthonormal matrix, and be a function defined on this manifold. Then
Fix 8 >
By 6Us) 8 Vxfu(x) + BIAS(U)
where BIAS(U) = Eessn | U*]s]. Moreover, bias is O and the resulting estima- is unbiased when U U*
Proof. Without loss of generality, we can assume det U and det U Using this remark, we can state the proof of the lemma as the straightforward application of the manifold Stoke's 's theorem
Eges--1 [f(x
Us)
Esss--1 [ʃ(x UUs)U*s} + Eses--1 [](x (Us) U*]s]
(a)
1
(Us) sds + EsEsn-1 [/(x + OUs) U*}s]
vol(
BIAS(U)
f(x + UU det U S 88n-1
ds + BIAS(U)
vol(dSn-
[s
1
f(x+
det U [
ds + BIAS(U)
(8)
vol(8Sn-1)
J88a-1
1
Vx
f(x (1x-JUU-TU BIAS((U)
vol m
6R
Japn f(x jUv)dv
BUA
vol 1
v0l()
(x) BIA((U).
where vol denotes volume, and we use the definition of the expectation in (a, e), orthonormality of U* in (b.d), manifold Stoke's theorem in (c) and the fact that the ratio of volume to the surface area of n dimeenniiio ball of radius
(e). Moreover, bias vanishes when U U
A.2 SAMPLE COMPLEXITY FOR RANDOM SEARCH AND MANIFOLD RANDOM SEARCH
In this section, we bound the sample complexity of the random search (Algorithm I and the man- ifold random search (Algorithm 2). Our analysis starts with studying the relationship between the function (f) and its smoothed (f) as well manifold smoothed (fu) versions in section A.2.2 We show that L-Lipschitzness and μ s-smoothness of the function extend to the smoothed functions. Moreover, we also bound the difference between the gradients the original function and the gra- dients of the smoothed versions. Next, we study the second moment of the gradient estimator in section A.2.3 Finally, we state the sample complexity of SGD on non-convex functions in sec- tion A.2.I Combining these results, state the final sample complexity of random search and manifold random search in section A.2.4A
A.2.1
CONVERGENCE OF SGD FOR NON-CONVEX FUCTIONS
The convergence of the SGD has been widely studied and here state its convergence result for non-convex functions from Ghadimi & Lan (013) as Lemma and give its proof for the sake of completeness.
14

---

Published as a conference paper at ICLR 2020
Lemma 2 (Convergence of SGD (Ghadimi & Lan 2013 Vemula al. 2019).
Consider running
SGD on f(x) that is u-smooth and L- L-Lipschitz, for steps starting with initial solution xa. Denote Ω = f(x") f(x*) where x" is the globally optimal point and assume that the unbiased gradient estimate has second moment bounded with V. Then,
1 T
852 WV
B
B
(x*)
112
T
Proof. We denote the step size as ar and the unbiased gradient estimate as g", We analyze the step at ( as;
f(x*+1) = f(x' - ag')
< 5(xx) a VVxJ(x')T'' + pa²
(10)
ll
2
where we used the μ smoothness of the function. Taking expectation of the inequality,
Ex [f(x S f(x) a V
Ellg
(11)
Using the bounded second moment of the gradient, and summing from step 1 to T,
TQP
Σ (x (()x(())]]
f(x') Σ
[vf(
(12)
1=1
Re-arranging the terms, we obtain,
UOTV
vxf(x') < Ex -f
2
(13)
+
pTaV
2A Set V VTV. and divide the inequality T in order to obtain the required inequality
T
V fx 113
(14)
A.2.2 PRELIMINARY RESULTS ON SMOOTHED FUNCTIONS
First, we will show that the f smoothness and I-- Lipschitness properties of applies to and f.
lf((xi) fu(x2)] = EVER [f(x] + 0Uv)] Even [/x (fx) &Uv]]l
EVEB [f(x] + jUv) f(x2 + 8Uv)]l
(15)
< EVEB., [[|[x] x2112]1
L||x| X2ll2
where we use L-pischhtz continuity of in (a), and,
[u)(()
(xx(x)))12
VE [f [Uv)] - V [x(x + 8Uv)
Evear fx(1 5Uv)] - EVER" (f 8Uv)]ll
E [f 5Uv) vf(xe + dUv)]lla
(16)
(b)
Fiver +
+ VS((2 + [l]
(c)
5 u| ||| X2112
15

---

Published as a conference paper at ICLR 2020
where use Jensen's inequality and convexity of the norm in (b) and smoothnes of f in (c). Hence, smoothenssss and L- Lipschitness applies to fu for any U. Take and U I, then the smmoootss and L- Lipschitness applies to f.
Next, we will study the impact of using the gradients of the smoothed function instead of the original function.
T T
1 T
V
(x)
Σ
- + vxfu(x)11
T
t=1
(17)
2
2 Σ [x)xux)113 T
[zf vxfu(x)
T 1=1
where we use |a + bllš S 2||a|| + 21 We further bound the left term as
[v,((x)
(x)u(x)113
I Vx)(() Vx B. [f(x + &Uv)]l
| [x](() V J
(18)
[|Ev~BB. [ 2
8²22²
using dominated convergence theorem in (a), the smoothhssess of f in (b) and orthonormality of U and the fact that norm of any point in a unit ball is bounded by 1. By taking n = and U I. this result also implies the same for f. Hence,
2 Σ
V (x)
S
(x)(
22
(19)
T
V f (x)
< Σ
+022 You....u
A.2.3 SECOND MOMENT OF THE GRADIENT ESTIMATOR
We will start with studying the second moment of our gradient estimate for the manifold case. We bound the expected square norm of the gradient estimate
Eses & ||
[2]
EsESo
.8
n F(x' + (1) - F(x' 5Us, Us 27
25
(a)
n²
[F(x** + &Us. - F(x öUs, {2)
482
(b)
n²
(J(x+0Us)) - -f(x - &Us))?]]
2/2
(20)
n
82 BsES"
[F(x + SUs, E) - -[(x + dUs))²
n
EsEgn &
(F(x- (F(x-8Us,{) - f(x SUs))?
82
(0)
2n²Vz
< 2n 2n² +
82
where we orthonormality of U and unit norm property of in (a), add and substract f(x + jUs) f(x - &Us) and use (a + b)² < 2a² + 252 (b), use the bounded variance of F and the Lipschitz smoothness of f in (c).
16

---

Published as a conference paper at ICLR 2020
Second moment of the random search estimator can also computed similarly. And, the resulting bound would be
Vd 82
EeES".E &
13 S 2d
(21)
A.2.4 PROOF PROPOSITION
Proof. Analysis SGD from Lemma
shows that
T
852 PV
(22)
[=1
Using the bound on the second moment of the estimator we derive in
21
1
8
VF 82
Vxf((*)
22 +
(23)
T
T
Using the relationship between f and we derive in
19
1 T [v=f(x)) - 28 +2
852
2d2VF 82
12
(24)
T
We use the property va + & vā + Vb, and solve for a. After we substituted the resulting 6,
+ cid
c2d
T Σ
(25)
T T
where co 2LL C1 V20, and c2 (1V= (2μ 4p8).
A.2.5 PROOF OF PROPOSITION 2
Sample complexity of the manifold random search follows closely the proof of Proposition 1 We summarize here for the sake of completeness. Using the analysis of SGD from Lemma
Proof.
T
PV T
V>f((*)]
(26)
1=1
Using the bound the second moment of the estimator derive in 21 and the relationship between f and fur we derive in 19
1
80 (VVx(x)) S 28 + 2
2n²VF
22
(27)
T
T
82
We first use the property Va + b S Va+ Vb. then solve for a and 8. Finally, we substitute resulting 5 to get the final result as;
1 T
Σ
[xff(t))
< cD
CIR
C2n
(28)
T
T
where co = 4T. e1
V2co and 02 (4V)>520) 3 (2/4 + 41
A.3 PROOF OF THE THEOREM
Proof. We will prove our main theorem using three major arguments. First, we analyze the SGD of non-convex function with biased gradients in section A.3. Second, we show that the expected value of our loss function is equal to the bias term in section A.3.2 order to bound the differ- ence between the empirical loss function minimize and its expectation, we use the Freedman's inequality Freedman 1975). Third, we bound the empirical loss section AA.33 in terms of the dis- tance travelled by the iterates of the optimization ||x x²1|2- Finally, optimize the resulting bound in terms of the finite difference step (6'), SGD step size (a"), and mixing coefficients (3) to obtain the final statement of the theorem in section A.3.4
17

---

Published as a conference paper at ICLR 2020
A.3.1 ANALYSIS OF SGD WITH BIAS
In order to analyze the SGD with bias, we will denote the gradient the iteration t, as g'. Moreover, we will assume that its bias is b' as Elg"] b' + VxF(x, E). Using the p-smoothness of the function F, we can state that
ua² 2 llg'112.
F(x . = FF5'=((5- - ag', s F(x ()) Vx E)g +
(29)
Let's s assume the effect of the bias is bounded as [xF(x' E)Tb² $ B", then
F(x . S F(x aVx (x - b'] p lgg + aB
(30)
2
Taking the expectation with respect to s and &, we get
a: Vxf(x')1
E., (..,s(((((())))) f(x²) +
+ aB'
(31)
2
where Vg. El[lg" [| Summing up from 1 to T and dividing by a, we obtain
T
Ω pal'V
R
B
(32)
We now compute the bound on the bias term (B') using Lemma I and g' = =3' + (1 3)g
FxF(x*,)TTb = (1 - 8) -1 F(x + OUs. OUs -U
(33)
S - (1- B)
(U U*|s|
where we used the fact that function is bounded as F(x, E) < Ω. Since Vx FxF(x, E) lies in the column space of U*, for some p.
TT - U
- =
- - - UU = V Fx, PUUUTU (34)
Choice of bases (U*) is not unique in Lemma 1. It can be any orthonormal basis spanning the tangent space of the manifold. In order minimize Eges--1 Fx* U- U choose
the basis which will set Up to the projection of V Fxx", {) into the column space of U. Then,
[V {) U+ll2 s min
| <) Uqlla S ( Vxg(r(x(; 8*) 3 l|
qER"
(35)
( where last inequality is due Vxg(r(x 8²); ) wtt being in the column space of U. Combining with and 0 < B < 1;
Ω
pa V
Ω
| ( Vxg(r(xt; 11++ 62p². (36)
2
We proceed to bound Σ
| F Vxg(r(x(;0';)))))))))>))))))>))) (1 in the next section.
A.3.2 ROLE OF THE BANDIT FEEDBACK
The true loss we are interested is the effect bias on the SGD. The bias is the sum of the differences between the gradients of the true function (fx(x,) and the estimated one (g(r(x; 0); d)) as derived in (36) On the other hand, the empirical information we have is the projection of this loss to random direction (s) with an additional noise term. In this section, will analyze the difference between the bias and the empirical loss without the noise. We will include the discussion on the noise in section A.3.3
18

---

Published as a conference paper at ICLR 2020
First, we will show that expectation of the empirical loss a direction uniformly chosen from a unit sphere the bias term. In order to show this, we need an elementary result which is Using this result,
Pacso-i((s'v)2) lvll". We show this result in Section A.4.1
Eggge-1 (V vvx(((((x))
d V E(x,E) (()((((x;))))))]] (37)
2
We introduce the notation A(s, SS (VxF(x {) Vx9 (x for clarity and, proceed to bound the difference Ass (, E. | x. *0]l Consider the sequence of differences as,
Z' = A x x' 2)) - ( (9)
(38)
is clear that E/Z' = 0 for all t. Moreover, the differences are bounded due to the Lipschitz conti- nuity. Hence, Z' is martingale difference sequence. We use the Freedman's 's inequality (Freedman 1975) in order to bound > z', similar to the seminal work studying the generalization of online learning by Kakade & Tewari 2009). Freedman's 's inequality (Freedman 1975) states that if Z is martingale difference sequence,
P
Σ
Z
max 2
Σ Var Var(Z*), 3b in mm/s) Vin(ys))
< In
(39)
b for all Before we substitute the Z' in the Freedman's inequality, we need to compute the variance of the Z'. We bound the variance using the definition of the variance
where b is the bound on Z'
(ds' ( (o Eggga-1 [(>" (10P((((6)0-000((11000)))))) 21 V=s((((x)))
(6 Boege-1 (2
| |x2((x Vx9((r(x Fxg((r(x;
(ds VxF(x', (e) Vxx((((x'
d²
(
1V=F(x Vx9((r(x')
(
de
212 + +d
(40)
where we denote the unit vector in the direction of V F( 56) Vxg((r(x); 0'); in (a) and use the Lipschitz property as well as (63) in (b). Finally we substitute this result in Freedman's 's inequality and use the expectation A(s xx xt 0t, 3 from (37). We also introduce the shorthand notation A f Ass xt, Et, 0t, w. With probability at least (T().,
T
21 d
T B[A 6L (++a) vm((h)) Vin(1/>)
A <
max
2
d
1=1
l=q
(41)
We further bound ΣJ, E[A'] by using the fact that 41 is in the form of 52 Sr+ max (2as, 6bele which can be solved for using quadratic formula. We solve this quadratic in Section A.4.2 and show that it implies s < r + 2ac//r + max(4a², 6b)c2. Using the solution of the quadratic formula, get the following final result describing the effect of bandit feedback. With probability 4y (T)..
2L + d
1882 + 4d
1 + 1+d)
Σ EA < Σ
22+
Σ A' (1n(1/++ max max
In(1/s)
d
d
d
1=1
(42)
19

---

Published as a conference paper at ICLR 2020
In summary, bound the difference between the effect of the bias Σ B|A"] and the empirical
loss we minimize Σi=1 A' without the noise term. In the next section, we procede to bound the empirical loss Ei=1 L and the effect of the noise term Σ A A/
A.3.3 ANALYSIS OF THE EMPIRICAL LOss
In this section, we will analyze the empirical loss. Our analysis is similar to the regret analysis of Follow the Regularized Leader (FTRL). However, we do not get an adverserial bound. Our resulting bound is the function of distances of iterates denoted as ||x - x'-1|] 222 Such bound would not be useful in adverserial setting since adversary chooses the iterates. However, we also design the optimization method. Hence, we bound ||x - -x-=112 by setting step sizes accordingly.
We start our analysis with bounding the total empirical loss in terms of the length of the trajectory the learner takes. As consequence of the FTL.-BII. Lemma (Kalai & Vempala 2005).
T
E
C(s x S,,00 (*) L(s', x',", 000 ,b+1)) + R(O" wT)
(43)
We use the Lipschitz smoothness property to convert this into distance travelled by the learner as C(s², ,0, L(s', 5", "', 0h ,1tt1)
u(x'' (' .h V (x (000(((((00::)))))
((xx",s'E"")
T Vxg(r(xx; (0 (
2
28
25
< 4L
$ (V (V=g(r(():0):;) - Vxg(r(x); (x
): (1t)))))
(44)
s 4L (x)(r((xx0))) - Vag(r(x;; o++)) o b
LOAKNURPAME.NNGGI
With properly chosen X, our regularizer enforces the smallest possible update, in terms of learner path length, which is consistent with the current sampled directions. This due to the representabil- ity assumption which guarantees that manifold can be fit perfectly using the parametric family. Hence, there is a solution with = O. Considering the regularizer is the learner path length, with proper choice of X, the FTRL will choose the shortest learner path length.
Among all choices of s s² FxF(x' < V. F(xf"")) would result in the longest distance. Hence, we can bound the learner path distance of our empirical problem with the distances of this oracle problem. We denote the 0 and vi found by this oracle problem as 0, s.. Formally, this upper bound leads to
LEARNERPATHLENNTH S
[x Vxe(r(x'; (1+1)1l
$ Σ
[xg((((* (00 0') Vag(r(x' 1; (000 o4
V~g(r 1 ,4ッ Vxg(r(x'; 34
(45)
| Vxg(T(x(; - "=a')(x-1;0');0
Vxg(r(x* ;+: Exg(r(x"; ( 3t (3
24
xx' x ||2,
20

---

Published as a conference paper at ICLR 2020
as the consequence of the fact that oracle problem solves all gradients perfectly (i.e. FxF(x', (*) [xg(r(x; 0'); )²) for all i > t) in (a), and the functions are w-smooth in (6). Using the fact that gradient norms are bounded,
T Σ c(s',x' x's',x''''' x' ,0000,0)))) s 8
x - x x
112 + 2L.
(46)
1=1
In order to extend this result to the At we use the smoothness of the function
A (s V fx - (xx(r(x'; (x);(x(x)'";;))) (())²
==Vxa(r(x);; 2
8 V y(x*, ((xt,'',)
5(x'x' (ixx's'',')
-
28
28
(47)
y(x', 5(x2)
EvERd se Vx''P(('' + E)
+ L(s', ,',
26
S p000² + Lis xas,,',C 5², 0¹ 2b
By combining 47 and 46
we state
ΣA'
< 8pL Σ
|x -x--xx x
x + 1285T 2LL
(48)
A.3.4 PROOF OF THE THEOREM
We combine the aforementioned three arguments to state the final sample complexity of our method. Our analysis of SGD with bias from (36) combined with the definition of the A gives the following bound on the sample complexity.
Ω aT
V
Ω E
dELA 8²p²..
(49)
Using the concavity of the square root function with Jensen's inequality, convert this bound to
1 (x')
Ω
V g
1 Σ B[A 6
7 Σ Vx
avd,
(50)
xT
2
T
Next, we will bound
D B[A'] using 42). For simplicity, we will analyze two cases
(E T A <1)) 1) and (Ei1 A 1) seperately.
Case 1, Σ A S 1:
We substitute this bound directly in (42).
With probability - 144 4n)n(TT),
1
1 2
21 d Vin(/>)+ + max
8 + 4d 1 + d)
) In(1/)) (51)
E
6L
T T
TV
d
dT
df
Relaxing the upper bound with the fact that dimension is greater than 1,
E[A S
(52)
T
where e₁ = 1+ V(822 + 4) In((/))))) + max (812 + 4, 1212 12222)l((/7))))
Case 2, 1 Σ A' > 1: Using the fact that /5 for and vx + S V + v well
as d 2 1, we can state that with probability - 4v In(),,
EAI
22 V
c3
1
Σ
A
(53)
T
T
T
21

---

Published as a conference paper at ICLR 2020
where 02 max 4, 1212] In(1/) and 1+ 22 In(?/)) Combining this
with the bound (48) and V v x: for x > 1,
203L C2
MAAY
+ ca(120² + SuaVEz
(54)
T
T
We combine two cases and substitute it in (50). The final sample complexity is,
S at + vo ( (²+ S + 1228² (1 11+90c3a Va) + 2eg
Ω
C1,2d
T [x[(x))
T
(55)
where C12 = max e2). We minimize with respect to a' and substitute it.
T Vxf(x')]| S V g
T (1+ (4cgnd) + + + 20ISLLvd
c1.2d
T
T
(56)
Before we solve for 6, we bound Vg & by choosing 3 = 1/d as,
( (1 (1- gm ]
4n²VF
E a. S E
<4L",² +
(57)
82
Next, we solve 8 to obtain the statement of the theorem. With probability - 47 IT())
kidt k2dt + kan + kand T Σ [x())()
kgnă + kgd n
(58)
T
T
where hn 20g hn Ve1,2, his 2us2, ka 4TS2/ucs hs 3(2 and KG (3(2c))
A.4 USEFUL ELEMENTARY RESULTS
A.4.1 EXPECTATION OF (sTv)2 WHEN S IS CHOSEN UNIFORMLY FROM gd-1
Consider I ((O))u(O) where (()) is integral over orthogonal matrices with Haar measure. If e is unit vector, we can show that
B [F(s)] = / ((O)))((O)
(59)
Before we use this result, we define || as an integral over orthogonal matrices O. Using orthog- onality and cyclic property of the trace,
vTv = Tr(vvT)- = Tr(vvT))(O)) / (O0Tw)))((O) / (O (60)
Since the indentity matrix is sum of outer products of one hot vectors e, I e,
/ (OT = (eee (oov)o)((0=)00 (()) = Σ / m((
(61)
Using 59 we can further show
Σ f Tree (0)) = Σ Es [T(ss = dB [(Tv]]
(62)
Hence, combining all,
Exgga- [(sTv] ||v
(63)
d
22

---

Published as a conference paper at ICLR 2020
A.4.2 BOUNDING THE QUADRATIC FORM
We need bound when the following quadratic inequality is correct;
8 S r + max max(20// 6befe.
(64)
We first consider the max as two separate options. Given the original inequality, one of the following correct;
S + 2acy8,
or
8 rr 6bc."
(65)
For the first case, - - 5 Using the quadratic formula, vs is smaller than the largest root as v I ac + Va²c² +r. Hence.
8 8= (vB)² < (ac+ Vatc² + r)² ² = a²è² + e² +r+ 200 a2c² + 4a2 +acc/++ (66)
Combining the resulting bound with the other option gives the final bound as,
r + 20cy + max 4 6b)c²
(67)
B ADDITIONAL IMPLEMENTATION DETAILS
In this section, we provide additional details for the implementation. Our experimental setup is also available open-source along with full implementation of our method at https:/ One key element of our method is the parametric family
github. com/ iintennneeiiiiaa to leam the manifold. We consider multi-layered perceptron with one three hidden layers as Linear(d, 2n) + ReLU - Linear(2n, n) + ReLU > Linear(n, n) for d < 1000 and Linear(d, (d, 1/2d) + ReLU + Linear(1/2d, 2n) + ReLU + Linear(2n, n) + ReLU + Linear(n, n) for d > 1000. We set the dimensionality of the manifold as the number of direc- tions which is hyper parameter. We use grid search over d and k values and choose the best performing one in all experiments, Moreover, we also reinitialize the manifold parameters whenever the estimated gradient's magnitude is less than 1e-6. We perform online gradient descent to learn the model parameters using SGD) with momentum as 0.9. We also perform grid search for learning rate over (1e-4, 1e-3, le 1e-2).
2). We set À 100 for all experiments.
We further discuss snperiment-specinne details below.
MuJoCo experiments. We use linear policies and initialize them as zeros, which corresponds to no action. We use v2-t algorithm from Mania et al. (2018), which includes whitening of the observation space and using top-k directions instead of all. We use grid search over the parameter space described by Mania et al. (2018) for k a and 6.
We use the following functions: sphere, noisysphere, cigar, tablet, cigtab, cigtab2, elli, rosen, rosen_chained, diffpow, rosenelli, ridge, ridge- circle, happycat, branin, goldsteinprice, rastrigin, schaffer, schwefel2.22, lincon, rosen rosen_nesterov styblinski tang. bukin with dimensions d 10 and d = 100 resulting in total 46 problems. We initialize all solutions with zero mean unit variance normal variables and use grid search over 6 E (1e-4, le-3, le- 2, le-1), (2,5, 5, 10, 50), and (1e-4, 1e-3, 3, 1e-2, 1e-
Low-dimensional unconstrained optimization suite.
Airfoil optimization. We initialize the parameters of the manifold with zero-mean unit-variance normal variables. We use grid search over 8 and a E (1e-4, 1e-3, 1e-2, le-1j. For choosing hyper-parameters, we simulate all models with Reynolds number 12e6, speed 0.4 mach, and angle of attack 5 degrees. After the hyper-parameten are set, we used Reynolds number 14c6, speed 0.6 mach and angle of attack 2 degrees for evaluation.
1le4,, 2,-2,,ee-111 k E {2,5, 10, 50),
Implementation details for the baselines. For ARS, we use grid search over the parameters rec- ommended by Mania et al. (2018). For CMA-ES, we use pyema (Hansen et al. 2019) with recom- mended hyperparameters. For Bayesian optimization, we use the REMBO optimizer (Wang et al.) 2016) with the following details. For continuous control problems, we use Structured Kernel In- terpolation (SKI) Wiilson & Nickisch 2015) and perform grid search over hyperparameters using the ranges recommended by GPyTorch (Gardner et al.) 2018). For other problems, we use full GP inference since the number of samples is rather low and perform grid search over kernel pa- rameters following GPyTorch (Gardner et al. 2018). As acquisition function, we perform grid search over Optimistic Expected Improvement (Rontsis et al. (2017), Multi-point Expected Improve- ment (Marmin et al. 2015), and the approach of Ginnsooureer al. (201)).
23


Reviews:
[{"review_id": "rye3yb6ptr", "reviewer": "AnonReviewer3", "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": "The computation times for random search methods depend largely on the total dimension of the problem. The larger the problem, the longer it takes to perform a single iteration.  I believe the main reason why many people use deep reinforcement learning to solve their problems is due to its dimension-independence.  I am not aware of a paper that tries to minimize the sample complexity. Thus, I think the idea in this paper is novel and may have influence on the literature (maybe an encouragement for a shift from deep reinforcement learning to derivative-free optimization methods). \n\nIn terms of presented results I think that there is not much that they could do wrong. They show in Figure 1 that the reward they achieved with their method is only outperformed by Augmented Random Search (ARS) on the Ant task. On all other tasks, their method at least performs on par with ARS which is a good result.\n\nIn Table 1 they show the number of episodes that are needed to achieve the reward threshold. Their method required less episodes than all other methods, but I think this is not the only criteria they should have looked at. So, it might be the case that their iterations take longer to compute than the iterations of the ARS and thereby making it slower. \n\nThe authors have showed that their method has a lower sample complexity, which is their goal of the research (“Our major objective is to improve the sample efficiency of random search.”). However, I am not sure whether this means that it also has a lower computational complexity. They address this issue briefly by stating that “Our method increases the amount of computation since we need to learn a model while performing the optimization. However, in DFO, the major computational bottleneck is typically the function evaluation. When efficiently implemented on a GPU, total time spent on learning the manifold is negligible in comparison to function evaluations.” This would mean that their iterations are performed in less computation time than the ARS, but I would have personally liked to see a number attached to this. \nIf we thus assume that this is the case, then their results are sound. However, I do not see this reduced complexity reflected in the results. If I look at the ratios between the number of episodes it takes to solve the tasks, they seem to be similar to the ones from the ARS. The number of episodes reduces by roughly 50% for all tasks but this keeps the ratio between the different tasks identical. I would have assumed that the ratios would increase in the favor of the larger problems like the Humanoid task. In other words, I still see the influence of the larger dimension in the results. Maybe I am too critical, but to me if they would have just found a faster method without the reduced sample complexity, they would have achieved similar results. \n\nOf course, this problem would not be present if the computation time increases with the number of iterations. In that case, the computation time would not reduce by a “fixed” ratio and would therefore decrease relatively much on the tasks with a higher dimension. But that would require an exact comparison between the computation times for all tasks for both their method and the ARS which I do not see in their results. If all these things are common knowledge, then their results are sound and they have found a large improvement to the already well performing ARS. \n", "extra_scores": {"experience_assessment": "I have read many 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 carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hyx0NWWCcB", "reviewer": "AnonReviewer4", "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": "This paper addresses the problem of optimizing high dimensional functions lying in low dimensional manifolds in a derivative-free setting. The authors develop an online learning framework which jointly learns the nonlinear manifold and solves the optimization. Moreover, the authors present a bound on the convergence rate of their algorithm which improves the sample complexity upon vanilla random search. The paper is overall well written and the core idea seems interesting. However, the reviewer has a few concerns which needs to be addressed. \n \n1) Methodology: This work depends on deep networks to learn the nonlinear manifolds which is justifiable by the power of deep nets. However, several issues may arise.\n\n1.1)  Globally optimizing the loss function of a deep network is no easy task and according to the authors, their theoretical results holds only if equation (6)--which includes the loss function of a deep net-- is globally optimized. \n\n1.2) Even if one could globally minimize the loss function up to a tolerance, this will require a large number of epochs resulting in a high overhead cost for each update of the algorithm. This cost should be considered during the evaluation of the performance of the algorithm. \n\n1.3) Finally, although the authors mention that : \" Experimental results suggest that neural networks can easily fit any training data\", the success of neural networks highly depends on their architecture and carefully tuning their several hyperparameters including the number of hidden layers, the number of nodes in each such layer, the choice of activation function, the choice of optimization method, learning rate, momentum, dropout rate, data-augmentation parameters, etc. One evidence around the necessity of carefully tuning the neural networks lies in appendix B where the authors mention their specific choice of hyperparameters for each experiment as well as the cross validation range they have used. Again, the overhead cost of finding a good deep network through cross-validation or any other method of choice (such as Bayesian optimization or Hyperband) should be considered towards the total cost of the algorithm.\n\n* Note that complex nonlinear manifolds might be better captured by complex yet flexible architecture as the authors also state that: \"If the function of interest is known to be translation invariant, convolutional networks could be deployed to represent the underlying manifold structure\". Hence, a simple fully connected network with fixed hyperparameters is suboptimal in capturing the different manifolds over various problems. This highlights the importance of exploring the space of hyperparameters.\n\n2) Experiments: The results are reported solely over the number of episodes (function evaluations) while the cost of each episode might be significantly different among different methods. Thus, for a thorough examination, reporting the performance over wall-clock time is recommended and required, ideally in both serial and parallel settings . It does not matter whether the time is spent for a function evaluation or for reasoning about the manifold through training the deep network, it should be taken into account.\n\nMinor issues:\n\n1. On page 2, there is a typological error in the footnote in defining the L-Lipschitz concept (replace \\mu with L).\n\n2. On page 3, section 3.1, at the end of the second line, g should be a function of both \\mathbf{r} and psi. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "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.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1gLHy9L9B", "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": "\nIn this paper, the authors first improve the gradient estimator in (Flaxman et al., 2004) zeroth-order optimization by exploiting low-rank structure. Then, the authors exploit machine learning to automatically discover the lower dimensional space in which the optimization is actually conducted. The authors justified the proposed algorithm both theoretically and empirically. The empirical performances of the proposed estimator outperforms the current derivative-free optimization algorithms on MuJoCo for policy optimization. \n\nThe paper is well-motivated and well-organized. I really like this paper, which provide an practical algorithm with theoretical guarantees (although under some mild conditions). The empirical comparison also looks promising, for both RL problems and zeroth-order optimization benchmark. \n\nI have roughly checked the proofs. The main body of the proof looks reasonable to me. However, I have some questions about one detail: In the proof of lemma 1, how the forth equation comes form third equation is not clear. Only manifold stokes' theorem might not enough since there is Us in side of f while U^*s outside of f. I think there should be one more bias term. \n\n\nFor the empirical experiment, it is a pity that the algorithm is not compared with Bayesian optimization, which is also an important baseline.  I am expecting to see the performances comparison between these two kinds of algorithms.\n\nMinor:\n\nThe \"unbiasedness\" of the gradient should be more clear. It is NOT unbiased gradient w.r.t. the original function, but the smoothed version. \n\n=====================================================================\n\nThanks for the reply. The comparison between the proposed algorithm and BO looks promising. \n\nI will keep my score. \n\nI am still confused about the proof of lemma 1. Following the notations in the paper, I was wondering the unbiased gradient should be \n\n$E_{S}[f(x + \\delta U^*s)U^*s]$\n\nThen, the lemma should characterize the difference between \n\n$E_{S}[f(x + \\delta Us)Us]$ and $E_{S}[f(x + \\delta U^*s)U^*s]$.\n\nHowever, current lemma 1 is not bounding this error.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1lK0Nv6KS", "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": "Contributions: \n\t-Authors have proposed a methodology to optimise high dimensional functions in a derivative-free setup by reducing the sample complexity by simultaneously learning and optimising the low dimensional manifolds for the given high dimensional problem. \n\nAlthough, performing dimensionality reduction to learn the low dimensional manifolds is popular in the research community, the extensions made and the approach authors have considered seems to be novel.\n\nComments:\n\t\n\t- Authors have talked about the utilization of domain knowledge on the geometry of the problem. How feasible is to expect the availability of the domain knowledge? Authors have not discussed the downsides of the proposed method if the domain knowledge is not available, and a possible strategy to overcome the same.\n\t- Authors have said that they are specifically interested in random search methods. Is there any motivating reason to stick to the random search methods? Why not consider other sample efficient search methods? \n\t“…….random search scale linearly with the dimensions”, why one should not consider other sample efficient methods that grow sub-linearly as against random search? \nSrinivas, N., Krause, A., Kakade, S. M., and Seeger, M. Gaussian process optimization in the bandit setting: No regret and experimental design. International Conference on Machine Learning, 2010\n\t- Please derive Lemma 1 in the appendix for the sake of completeness.\n\t- I am missing a discussion about manifold parameters like “λ” in the important equations. \n\t- Authors have made a strong claim that neural networks can easily fit any training data, but it may be not be true for many datasets.\n\t - Authors have claimed that they have fast and no-regret learning by selecting mixing weight β=1/d. Author might want to discuss more on this as this is an important metric.\n\t - “ …. total time spent on learning the manifold is negligible…. ” – any supporting results for this claim.\n\t - “…….communication cost from d+2k to d+2k+kd… ” – curious to know if there is any metric like wall-clock time to talk about the optimisation time.\n\n\t- Authors have restricted the comparisons to only three important methods, but it is always comparing with other baselines in the same line. Authors should consider Bayesian optimisation as it is a good candidate for the performance comparison, even though the researchers are interested only in random search methods (just like CMA–ES).\nKirschner, Johannes, Mojmír Mutný, Nicole Hiller, Rasmus Ischebeck, and Andreas Krause. \"Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces.\" arXiv preprint arXiv:1902.03229 (2019).\n\n\t- It is seen from the results that the proposed method is not performing better for low dimensional problem like “Swimmer” function. But according to the initial claim, method was supposed to work better in low dimensional problems. Is it because of the fact that the problem space is not drawn from high dimensional data distributions? \n\t- “…..improvement is significant for high dimensional problems” – It will be better if the authors compare their proposed method with some more derivative-free optimisers that are proven to be good in high dimensions (like high dimension Bayesian optimisation).\n\t-  “The no-learning baseline outperforms random search ……….” – this statement is not very clear, does it mean like the proposed method works only when the problem is reduced from higher dimensions to lower dimensions and not on the lower dimensional problem itself?\n\t- “Performance profiles represent how frequently a method is within the distance T of optimality” – Any thumb rule considered for the choice of T?. Can we think of any relation with standard metrics like simple regret or cumulative regret that are used to measure the optimisation performance?\n\t- “Although BO methods typically do not scale…… ” – Authors have made a strong assumption here. In the literature, we see active research in the context of high dimensional optimisation.\nRana, Santu, Cheng Li, Sunil Gupta, Vu Nguyen, and Svetha Venkatesh. \"High dimensional Bayesian optimization with elastic gaussian process.\" In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pp. 2883-2891. JMLR. org, 2017.\n\t\n\n\nMinor Issues:\n\t“Improve the sample complexity” may not convey the meaning very clearly to the readers, something like “Improve the sample efficiency” or “Reduce the sample complexity” would add more clarity.\n\tInconsistency in the terms used in Proposition 1 and Proposition 2. What does “I” signify in the formula? Was that supposed to be “t”?\n\tEven though the constants are mentioned in the appendix, it is always better to mention the constants used in the algorithm like “α“ as step size for quick understanding.\n\t“Follow The Regularized Leader (FTRL)” is more appropriate than “follow the regularized leader (FTRL)”\n\t“noise table in pre-processing” – Should it mean something relevant to the paper? \n\t“We use widely used…..” – may be consider rephrasing the sentence here\n\t“treshold” – Typo in Table 1\n\tY – Axis in Figure 2 is missing\n\tAppendix B :\n\t“We also perform grid search …. “ would look better\n\tMuJoCo Experiments – is the parameter space continuous and what is the search space considered for n, α and δ. Do we deal with smaller search spaces in every problem? Any other way of searching the parameter space to further improve the efficiency? \n", "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": {}}]

Author rebuttal:

Meta-review: This paper develops a methodology to perform global derivative-free optimization of high dimensional functions through random search on a lower dimensional manifold that is carefully learned with a neural network.  In thorough experiments on reinforcement learning tasks and a real world airfoil optimization task, the authors demonstrate the effectiveness of their method compared to strong baselines.  The reviewers unanimously agreed that the paper was above the bar for acceptance and thus the recommendation is to accept.  An interesting direction for future work might be to combine this methodology with REMBO.  REMBO seems competitive in the experiments (but maybe doesn't work as well early on since the model needs to learn the manifold).  Learning both the low dimensional manifold to do the optimization over and then performing a guided search through Bayesian optimization instead of a random strategy might get the best of both worlds?  
Decision: Accept (Poster)