AdaDGS: An adaptive black-box optimization method with a nonlocal directional Gaussian smoothing gradient
Authors: Hoang A Tran
Guannan Zhang
Venue:  (2021)

Abstract: The local gradient points to the direction of the steepest slope in an infinitesimal neighborhood. An optimizer guided by the local gradient is often trapped in local optima when the loss landscape is multi-modal. A directional Gaussian smoothing (DGS) approach was recently proposed in (Zhang et al., 2020) and used to define a truly nonlocal gradient, referred to as the DGS gradient, for high-dimensional black-box optimization.  Promising results show that replacing the traditional local gradient with the DGS gradient can significantly improve the performance of gradient-based methods in optimizing highly multi-modal loss functions.  However, the optimal performance of the DGS gradient may rely on fine tuning of two important hyper-parameters, i.e., the smoothing radius and the learning rate.  In this paper, we present a simple, yet ingenious and efficient adaptive approach for optimization with the DGS gradient, which removes the need of hyper-parameter fine tuning.  Since the DGS gradient generally points to a good search direction, we perform a line search along the DGS direction to determine the step size at each iteration. The learned step size in turn will inform us of the scale of function landscape in the surrounding area, based on which we adjust the smoothing radius accordingly for the next iteration. We present experimental results on high-dimensional benchmark functions, an airfoil design problem and a game content generation problem. The AdaDGS method has shown superior performance over several the state-of-the-art black-box optimization methods.

Under review as a conference paper at ICLR 2021
ADADGS: AN ADAPTIVE BLACK-BOX OPTIMIZATION METHOD WITH A NONLOCAL DIRECTIONAL GAUSSIAN SMOOTHING GRADIENT
Anonymous authors Paper under double-bling blind review
ABSTRACT
The local gradient points to the direction the steepest slope an infinitesimal neighborhood. An optimizer guided by the local gradient is often trapped in local optima when the loss landscape is multi-modal. directional Gaussian smoothing (DGS) approach recently proposed in (Zhang al. (020) and used to define a truly nonlocal gradient, referred to as the DGS gradient, for high-dimensional black-box optimization. Promising results show that replacing the traditional lo- cal gradient with the DGS gradient can significantly improve the performance gradient-based methods in optimizing highly multi-modal loss functions. How- ever, the optimal performance of the DGS gradient may rely on fine tuning of two important typer-parameters i.e., the smoothing radius and the learning rate. In this paper, we present a simple. yet ingenious and efficient adaptive approach for optimization with the DGS gradient, which removes the need of hyper-parameter fine tuning. Since the DGS gradient generally points to good search direction, we perform a line search along the DGS direction to determine the step size at each iteration. The learned step size in turn will inform us of the scale of fune- tion landscape in the surrounding area, based on which we adjust the smoothing radius accordingly for the next iteration. We present experimental results high- dimensional benchmark functions, an airfoil design problem and a game content generation problem. The AdaDGS method has shown superior performance over several the state-of-the-art black-box optimization methods.
INTRODUCTION
We consider the problem of black-box optimization, where we search for the optima of a loss func- tion F: : Rd - R given access to only its function queries. This type of optimization finds applica- tions in many machine learning areas where the loss function's gradient is inaccessible, unuseful, for example, in optimizing neural network architecture (Real et al., 2017), reinforcement learning (Salimans al. 2017), design of adversarial attacks (Chen al. 2017). and searching the latent space of generative model (Sinay et al. 2020).
The local gradient, i.e., VFww), is the most commonly used quantities guide optimization. When F(x)) is inaccessible, we usually reformulate ((()) (x) as functional of (()). One class of meth-
ods for reformulation Gaussian smoothing (GS) (Salimans al. 2017 Liu al. 2017 Mania
et al. 2018). GS first smooths the loss landscape with d-dimensional Gaussian convolution and rep- resents (= by the gradient of the smoothed function. Monte Carlo (MC) sampling is used es- timate the Gaussian convolution. It is known that the local gradient V F()) points to the direction of the steepest slope in an infinitssmaal neighborhood around the current state ær. An optimizer guided by the local gradient is often trapped in local optima when the loss landscape is non-convex multi- modal. Despite the improvements (Maggiar et al. 2018; Choromanski et al. 2018 2019) /ennrr & Koltun 2020 Maheswaranathan al. 2019 Meter al. (201)). GS did not address the challenge of applying the local gradient to global optimization, especially in high-dimensional spaces.
The nonlocal Directional Gaussian Smoothing (DGS) gradient, originally developed in (Zhang et al. 2020). shows strong potential to alleviate such challenge. The key idea the DGS gradient is to conduct ID nonlocal explorations along d orthogonal directions in Rdd each of which defines

---

Under review as a conference paper at ICLR 2021
local directional derivative ID integral. Then, the d directional derivatives assembled to form the DGS gradient. Compared with the traditional GS approach. the DGS gradient can use large smoothing radius to achieve long-range exploration along the orthogonal directions This enables the DGS gradient to provide better search directions than the local gradient, making it particularly suitable for optimizing multi-modal functions. However, the optimal performance of the DGS gra- dient may rely on fine tuning of two important hyper-parameters, i.c., the smoothing radius and the learning rate, which limits its applicability in practice.
In this work, we propose AdaDGS, an adaptive optimization method based on the DGS gradient. Instead of designing a schedule for updating the learning rate and the smoothing radius as in (Zhang et al. (020)). we learn their update rules automatically from a backtracking line search (Nocedal & Wright 2006). Our algorithm based on simple observation: while the DGS gradient generally points to good search direction, the best candidate solution along that direction may not locate in nearby neighborhood. More importantly, relying on single candidate in the search direction based on prescribed learning rate is simply too susceptible to highly fluctuating landscapes. Therefore, we allow the optimizer to perform more thorough search along the DGS gradient and let the line search determine the step size for the best improvement possible. Our experiments show that the introduction of the line search into the DGS setting requires a small but well-worth extra amount of function queries per iteration. After each line search, we update the smoothing radius according to the learned step size, because this quantity now represents an estimate of the distance to an important mode of the loss function, which we retain in the smoothing process. The performance and comparison of AdaDGS to other methods are demonstrated herein through three medium- and high-dimensional test problems, in particular, a high-dimensional benchmark test suite, an airfoil design problem and a level generation problem for Super Mario Bros.
Related works. The literature on black optimization is extensive. We only review methods closely related to this work (see (Rios& & Sahinidis, 2009 Larson et al. 2019) for overviews).
Random search. These methods randomly generate the search direction and either estimate the directional derivative using GS formula or perform direct search for the next candidates. Examples are two-point approaches (Flaxman et al., 20055 Nesterov & Spokoiny) 2017 Duchi et al. 2015] Bubeck & Cesa-Bianchi, 2012). three-point approaches (Bergou et al. 2019), coordinate-descent algorithms (Jamieson et al. 2012). and binary search with adaptive radius (Golovin et al. 2020).
Zeroth order methods based local gradient surrogate. This family mimics first-order methods but approximate the gradient via function queries (Liu et al. 2017 7 Chen et al.] 2019; Balasubramanian & Ghadimi 2018). A exemplary type of these methods is the particular class of Evolution Strategy (ES) based on the traditional GS, first developed by (Salimans et al. 2017). MC is overwhelmingly used for gradient approximation, and strategies for enhancing MC estimators is an active area of research, see, e.g., (Maggiar et al. 20188) Rowland et 2018) Maheswaranathan et al. 2019; Meier al. 2019 Sener & Koltun| 2020). Nevertheless, these effort only focus on local regime, rather than the nonlocal regime considered in this work.
Orthogonal exploration. It has been investigated in black-box optimization, e.g., finite difference explores orthogonal directions. (Choromanski et al. 20188) introduced orthogonal MC sampling into GS for approximating the local gradient; (Zhang et al. 2020)) introduced orthogonal exploration and the Gauss-Hermite quadrature to define and approximate a nonlocal gradient.
Adaptive methods. Another adaptive method based on DGS gradient can be found in (Dereventsov eet al. 2020). Our work is dramatically different in that our update rule for the learning rate and smoothing radius drawn from line search instead of from Lipschitz constant estimation. The long-range line search can better exploit the DGS direction and thus significantly reduce the number of function evaluations and iterations. Line search is a classical method for selecting learning rate Nocedal & Wright 2006) and has also been used in adaptation of some nonlocal search techniques, see, c.g., (Hansen 2008). In this work, we apply backtracking line search on DGS direction. We do not employ popular terminate conditions such as Armijo (Armijo) 1966) and Wolfe condition (Wolfe) 1969) and always conduct the full line search, as this requires a small extra cost, compared to high-dimensional searching.
2

---

Under review as a conference paper at ICLR 2021
2
THE DIRECTIONAL GAUSSIAN SMOOTHING (DGS) GRADIENT
We are concerned with solving the following optimization problem
min F(æ),
wER-
where (x1,,..,,aa)) Tta) E I& consists of d parameters, and F R + -R is d-dimensional loss function. The traditional GS method defines the smoothed loss function as Fa(x) Bu-A((oL..)) [F(x + ow)], where (0,, Ia) is the d-dimensional standard Gaussian distribution, and >> 0 is the smoothing radius. When the local gradient (xx) is unavailable, the traditional GS uses (z) = (u [F(x + ou) u] (Flaxman et al. 2005) to approximate V by ex- ploiting lim (z) (x(x) (i.e., setting o small). Hence, the traditional GS is unsuitable for defining a nonlocal gradient where large smoothing radius a is needed.
In (Zhang et al. 2020). the DGS gradient was proposed circumvent this hurdle. The key idea was to apply the 1D Gaussian smoothing along d orthogonal directions, so that only 1D numerical inte- gration needed. In particular, define a 1D cross section of F(x)) Gly x. E) F(x++ E), y E R, where æ is the current state of F and is unit vector in Rd. Then, the Gaussian smoothing of F(x) along& & is represented as Go (y tive of the smoothed F(x) along c is ID expectation
E) := (1/v/x)) f& Gly + σee x {) exp(-v² /2) The deriva-
G. 00| x 4 = Be-N((.1) [G(ov] x., e),
where Ø|| denotes the differential operator. Intuitively, the DGS gradient is formed by assembling these directional derivatives on orthogonal directions. Let == (E....., Ea) be an orthonormal system, the DGS gradient is defined as
= (x)) (0 (0
x. Ex)
where E\t and be adjusted during an optimization process.
Since each component of V., (F)()) only involves a 1D integral, Zhang et al. 2020) proposed to use the Gauss-Hermite (GH) quadrature rule (Abramowitz Stegun 1972), where each component [ (0) æ, {) is approximated as
M Wm F(x: (2 20m-
2 M (G. x)) VTO
Here (Um) are the roots of the M-th order Hermite polynomial and (wm LM m==1 are quadrature weights, the values of which be found in (Abramowitz & Stegun| 1972). It was theoretically proved in (Abramowitz & Stegun 1972) that the error of the GH estimator is ~ M1/(2 (2M)) that
much smaller than the MC's eитor 1/VM. Applying the GH quadrature each component of V (F.e())()) the following estimator is defined for the DGS gradient:
[9 [G, (0) x, Ei).. 9 (G. x. Ex)l E.
(2)
Then, the DGS gradient is readily integrated first-order schemes replace the local gradient.
THE ADADGS ALGORITHM
In this section, we describe an adaptive procedure to remove manually designing and tuning the update schedules for the learning rate and the smoothing radius of the DGS- gradient descent (Zhang et al. 2020). Our intuitions are: (i) for multimodal landscapes, choosing one candidate so- lution along the search direction according and (ii) the optimal step size, known, is a good indicator for the width of optima that dominates the surrounding area and could be used to inform smoothing radius update. Following this rationale, AdaDGS first uses backtracking line search to estimate the optimal learning rate, and then uses the acquired step size update the smoothing radius. AdaDGS is straightforward to implement and
single learning rate may make insufficient progress,
3

---

Under review as a conference paper at ICLR 2021
find this strategy to overcome the sensitivity to the hyper-parametee selection that affects the orig- inal DGS method. As we shall see, the most important hyperparameters in AdaDGS control how aggressive want to conduct the line search. Our key advantage in high- nigh-dimensional optimization is that with a modest budget for line search (compared to that for computing DGS gradient), we can still get very generous number of function evaluations along DGS direction and approximate the optimal learning rate. We suggested some default values of these hyperparameters which are proven to be universally good throughout our test. However, if one prefers, they can definitely adjust these for a more aggressive line search. For example, even doubling or tripling the number of points to be visited along DGS direction will increase the total number of function evaluations by small fraction (5% and 10% correspondingly).
Recall the gradient descent scheme with DGS
It-1 3z de V.V. V, (F)),)
where Tt and 1+++1 are the candidate solutions at iteration / and L + 1, and X is the learning rate. The details of the AdaDGS algorithm is described below.
Learning rate update via line search. At iteration i, we perform the line search along V.l (m)e v (()()((m)))
within the interval [x. - Lmin
[ [F]()]]] 3t Lmax [ [M](a)] where Lmax and Lmiu are
||
the maximum and minimum exploration distances, respectively. We visit S points in the interval, equally spaced on a log scale, and choose the best candidate. The corresponding contraction factor
is = min (Imin/ Tmmax) (mmax)//CC 31((S-1)). More rigorously, the selected learning rate is
Imaxp
IV [F[[)]] where
arg min F 24 - je S-1
(3)
(xx))
The default value of Linx is the length of the diagonal of the search domain. This value could be refined by running some test iterations, but our algorithm is not sensitive such refining. The default value of Limi is Linn = 0.005Lmax The default value for S is S = m12 0.05MMd,, where Md is the number of samples required by the DGS gradient. This means that when d is high, we spend roughly 5% budget of function evaluations for line search. Note that when S is large, p= 0.9 and the actual minimum exploration distance is T.max0.9S-1 < Temin- As long as the DGS gradient points to a good search direction, the line search along a ID ray much more cost-effective than searching in d- dimensional spaces.
Algorithm 1: The AdaDGS algorithm
1: Hyper-parameters:
M: # GH quadrature points
Lmaxi the maximum exploration
Timi: the minimum exploration
S: # function eval. per line search
aot initial smoothing radius
y: tolerance for triggering random exploration
Smoothing radius update. The smoothing ra- dius Tr adjusted based on the learning rate
2: Input: The initial ær
learned from the line search. The initial ra- dius dg is set to be on the same scale as the width of the search domain. At iteration f, we set o, to be the mean the smoothing radius and the learning rate from iteration - i.e.
3: Output: The final state ær
4: Set = L. (or random orthonormal matrix)
5: for t = .,... T do
Evaluate (G(v20, U. x. (.) b
for i= 1,..., do
Compute 9 [G., xr, E.)] in Eq.
0, = - (o )
9: end for
10: Assemble V (a::) in Eq.
because both quantities indicate the land- scape of the loss function.
11: Update x according to Eq.
12: Set Øe+1 = Z: - >e V [F (xx)
The number of Gaussian-Hennan
points. The AdaDGS method is not sensitive to the num-
13:
Set a.+1 = { + Aa) according to Eq.
14:
if F((:)) (ax,1))// F(x;-1) < then
ber of GH points. We do not observe signifi- cant benefit of using more than 5 GH quadra- ture points per direction. In some tests (Sec-
15:
Generate random rotation
16:
Set 0++1 = do
tion 4.3). 3 GH quadrature points per direc- tion are sufficient.
17:
end if
18:
end for
4

---

Under review as a conference paper at ICLR 2021
Random exploration. We incorporate the following strategies to support random exploration and help the AdaDGS algorithm escape undesirable scenarios. We use the condition (F(x)) F(zz-1)l/F((zz < y to trigger the random exploration, where the default value for is 0.001. Users can optionally trigger these strategies when the method fails to make progress, e.g., insuffi- cient decrease too small step size.
Reset the smoothing radius. Since is updated following Eq. (4 becomes small with the learning rate. Thus, we occasionally reset a to its initial value. We set a minimum interval of 10 iterations between two consecutive resets. In many of our tests, the function values reached by AdaDGS within 10 first iterations (before the radius reset is triggered) are already lower than those by its competitors can at the end.
Random generation of E. Keeping the directional smoothing along fixed set of coordinates may eventually reduce the exploration capability. To alleviate this issue, we occasionally change the nonlocal exploration directions by randomly generating orthogonal matrix 3. An important difference between our approach and the random perturbation strategy (Zhang et al.) 2020) is that the approach in (Zhang et al., (020)) only add small perturbation to the identity matrix, but we generate a totally random rotation matrix.
EXPERIMENTS
We present the experimental results using three sets of problems. All experiments were implemented in Python 3.6 and conducted on set of cloud servers with Intel Xeon E5 CPUs.
4.1 TESTS ON HIGH-DIMENSIONAL BENCHMARK FUNCTIONS
We compare the AdaDGS method with the following (a) DGS: the baseline DGS with polynomial decay update schedule developed in (Zhang al. 2020), (b) ES ES-Bpop: the standard OpenAl evolu- tion strategy in (Salimans et al., (017) with a big population (i.e., using the same number of samples
AdaDGS), (c) ASEBO Adaptive ES-Active Subspaces for Blackbox Optimization (Choroman- ski et al. 2019) with a population of size + 3 log(d), (d) IPop-CMA: the restart covariance matrix adaptation evolution strategy with increased population size (Auger & Hansen 2005), (e) Nesterov:
the random search method in (Nesterov & Spokoiny 2017). (I) FD: the classical central difference
scheme, and (g) TuRBO: trust region Bayesian optimization (Eriksson et al. 2019). The information
of the codes used for the baselines is provided in Appendix.
We test the performance of the AdaDGS method on 12 nigh-dimensional benchmark functions (EI-
Abd 2010 Jamil & Yangl 2013). including Fi (xr): Ackley, F2(x:): Alpine, F3(x:): Ellipsoidal, Fa(x)): Quintic, F=( Rastrigin, Fa(::): Rosenbrock, Fr(x)): Salomon, Fs():): Schaffer's F7, Fz(x)): Sharp-Ridge, Fio (x): Sphere, Fn (x): Trigonometric, and Fi2(x): Wavy. To make the test functions more general, we applied the following linear transformation to æ,
R(x + Zopt Dloc),
which first moves the optimal state Zopt to new random location Pise and then applies a random rotation R to make the function non senseaaraalee. We substitute z into the standard definitions of the benchmark functions to formulate our test problems. Details about those functions are provided in Appendix.
The hyper-parameters of the AdaDGS method are fixed for the six test functions. Specifically, Liuxx is the length of the diagonal of the domain, S = 200 (= 0.05MM),, To ~ 5 * width, and M = 5. Since S large, the minimum exploration distance is easily small and do not need to concerned with Temin We choose contraction factor to be 0.9. We turned off the random perturbation by setting y = O. For each test function, we performed 20 trials, each of which has random initial state, random rotation matrix R and random location of Øloc-
The comparison between AdaDGS and the baselines in the 1000D case are shown in Figure I Additional results are shown in Appendix C where the loss decay is plotted in log-scale. The AdaDGS has the best performance overall. In particular, the improvement of AdaDGS over baseline DGS is significant, demonstrating the effectiveness of our adaptive mechanism. AdaDGS shows substantially superior performance in optimizing the highly multimodal functions F1, F2, FJ. Fs. Fr, Fs, Fii which is significant in global optimization. For the ill-conditioned functions Fs, F
5

---

Under review as a conference paper at ICLR 2021
Filr): Adkay 1000
9000
Frih: Abons 1930D
-10" Rite: Elipossia 1280D
10f
Pela's Quintic
5500
20
2.5
16
5000
4000
3000
3
2000
0.6
1.6
function ansiuationa
111
function avalarionn x10
function evaluationa x000
Bistrigio 1000
Felx:: Rosechoock 1000
Fiaz:: Sakeson 1000
Fiish Scuder 100D
2.0
2
150
1.6
100
0.5
60
0.6
function ovaluations -10
function eveluations
Bunation ovaluatione
ovaluation
10" File): Shirp Todge 1003
Fitet Sparce 19000
110 Futao Trigrommntts 1053
Friit Wasy 1000
2.5
1.5
0-
1.5
0.5 1unctoon evaluations
F Function evaluations
-10'
F FTunction evaluation
Runction evaluations
x300
AdaDGS
DGS
ASEBO
ES- ES-Bpap
Nesterov
IPap- CMA
FD
TuRBO
Figure 1: Comparison of the loss decay w.r.t. # function evaluations for the 12 benchmark functions in 1000D. Each curve is the mean of 20 independent trials and the shaded areas represent [mean- 3std, m3an+3 The global minimum is (a = O except for i = 11, where F11 (Topt) = 1. The AdaDGS has the best performance overall, especially for the highly multi-modal functions Fi. F2. F4, Fg. F7, Fs. Fu, Fui- All the methods fail to find the global minimum of F12 which has no global structure to exploit.
and Fg, AdaDGS can least match the performance of the best baseline method, e.g., IPop-CMA. The test with sphere function Fig show AdaDGS converges within 2 steps, confirming the quality of DGS search direction. For F12- all the methods fail to find the global minimum because it is highly multi-modal and there is no global structure to exploit, which makes it extremely challenging for all global optimization methods. We also tested AdaDGS in 2000D, 4000D and 6000D to illustrate its scalability with the dimension. The paper-pprameters are set the same as the 1000D cases. The results are shown in Figure 2 The AdaDGS method still achieves promising performance, even though the number of total function evaluations increases with the dimension.
4.2 TESTS ON AIRFOIL SHAPE OPTIMIZATION
We applied the AdaDGS method to design 2D airfoil. We used computational fluid dy- namics (CFD) code, XFoil v.6.91 (Drela 1989), and its Python interface v.1.1.10 The Xfoil conduct CFD simulations of airfoil given 2D contour design. The first step is to choose an appropriate parameterization for the upper and lower parts of the airfoil. In this work, we used the ttate- Class/Shape function Transformation (CST) (Kulfan 2008). Specifically, the upper/down airfoil geometry is represented as x(x) = Vi(1= 2 (o::: (1)x - N))- AA ene, where E [0, 1), N is the polynomial order. The polynomial 'Avaliable https: : / / thub.
1-yyhhn

---

Under review as a conference paper at ICLR 2021
1500 Ackrey
2.5 -10
HDx Alpise
=100 Polel: Ellipookiil
-10
Hisk Quisric
05
10
20000
20000
20000
20000
40000
40000
-40000
40000
80000
60000
60000
00030
1.5
1.5
Looss
0
function evalaations
function evalustions
function evalustions -10'
function evaluations
-10*
Reserigin
=10
Fdle]: Rowebhook
Felelp Salnmon
=10
FL(e): Schulfer
600
2000
20000
2000
20000
40000
4000D
500
40000
10
60000
60000
1.5
6000D
60000
60000
400
Losa
Loss
500
6-
200
0.5
100
5
10
# function ovaluations.. 10
function evaluations 11
function avakustions, 10²
ffunction evauations, 10
=10" Poleh: Sharp-Stddge
-10
Fila): Spiere
<100
Pi Trionomettie
Figlat: Wary
10
1.4
20000
20000
20000
20000
40000
4000D
40000
1.2
40030
60000
6000b
80000
60030
Loss
Lo06
0.8
1
0.4
0.2
function oval.ations,..d 10'
function ovaluations .10"
function evalustions.. -00
function evaluations,.t 10"
Figure 2: Tests on AdaDGS's scalability in 2000D, 4000D and 6000D. The hyper-parameters
the same as the 1000D case. The AdaDGS still achieves promising performance, even though the number of total function evaluations increases with the dimension.
Table I: The airfoil lift and drag values after 1500 calls to XFoil. AdaDGS provides the best design with the biggest Lift-Drag.
coefficients A, and the position of the airfoil tail Aste are the parameters needed to be opti- mized. We used two different CST polynomials to parameter- ize the upper and lower part of the airfoil, where the polyno- mial degree for each polyno- mial is set to 6 by following the suggestion in (Ceze et al.). Then, the dimension of the op- timization problem is d = 15. The initial search domain is set to 1]., We simulated all models with Reynolds number 12c6, speed 0.4 mach and the angles of attack from 5 to 8 de- grees. The initial condition is the standard NACA 0012 AIR-
The best design after 1500 simulations
Init
AdaDGS
ASEBO
ES ES-Bpop
Lift
0.0473
2.6910
1.2904
1.1931
Drag
0.0161
0.0133
0.0097
0.0100
Lift-Drag
0.0312
2.6777
1.2821
1.1831
Foil
The best design after 1500 simulations
Nesterov
Ipop-CMA
FD
TuRBO
Lift
0,8575
1.1403
0.8606
2.0747
Drag Lift-Drag
0.0095
0.0072
0.0071
0.0097
0.8480
1.1331
0.8535
2.0650
Foil
FOIL. The hyper-parameters of the AdaDGS method are Lmx is the length of the diagonal of the
domain, Lmm = 0.005 S = 12, ou = search domain width, M = 5 and y = 0.001. The gain function is set to Lift-Drag and the goal is to maximize the gain. The results With 1500 simulations, all the methods reach shape with Lift > Drag, which means the airfoils can fly under the experimental scenario. Our AdaDGS method produced the best design, i.e., biggest
shown in Table T
7

---

Under review as a conference paper at ICLR 2021
Dift-Drag. The other baselines achieved lower Drag than the AdaDGS but did not achieve very high Lift force.
4.3 TESTS ON GAME CONTENT GENERATION FOR SUPER MARIO BROS
We apply the AdaDGS method generate variety of Mario game levels with desired attributes. These levels are produced by generative adversarial networks (GAN) (Goodfellow et al., 2014)). which map from latent parameters to high-quality images. To generate game level with desired characteristic, one needs to search in the latent space of the GAN for parameters that optimize a prescribed stylistic or performance metric.
In this paper, we evaluate the performance of AdaDGS in generating game levels for two different types of objectives: (i) levels that have the maximum number of certain tiles. We consider sky tiles (i.e., game objects that lie in the above half of the image) (MaxSky Tiles)) and enemy tiles (MaxEnemies); (ii) playable levels that require the Al agent perform maximum certain action. We consider jumping (MaxJumps) and killing an enemy (MaxKills). These characteristics are often considered for evaluating latent space search and optimization methods (Volz et al. 2018 2019, Fontaine et al. (020). Specifically for type (ii) objective, Baumgarten to evaluate the playability of the level and the objective functions. We set unplayable penalty to be 100 and add that to the objective function when the generated level is unplayable. The game levels are generated from a pre-trained DCGAN by (Fontaine et al.] 2020). whose inputs are vectors in 1,, 1] Details of the architecture can also be found in (Volz et al. 2018).
the Al agent developed by Robin
The hyper-parameters of the AdaDGS method are set at default values for the four tests. Specifically, Limax is the length of the diagonal of the domain, Limin 0.029 (= 0.005 S 12, do search domain width, M = 3 and y = 0.001. We start with E being a random orthonormal matrix generated by scipy. . stat s.tts.orte ortho group. rvs. As demonstrated in (Volz et al. [2018), the IPop-CMA is by far the mostly used and superior method for this optimization task, so we only compared the performance of our method with IPop-CMA. We used the pyema v.3.0.3 with the population size be 17 and the radius be 0.5, as described in (Fontaine et al. 2020). We apply tanh function to the latent variables before sending it to the generator model, because this model was trained on [-1, 1|32, 50 trials with random initialization are run for each test.
The comparison between AdaDGS and IPop-CMA are shown in Figure 3. AdaDGS outperforms IPop-CMA in three out of four test functions and is close in the other. We find that Ipop-CMA can also find the best optima in many trials, but it is casier to get stuck at undesirable modes, c.g, local minima. Taking the MaxSky Tiles case as example. There are 4 types of patterns, shown in Figure 4 are generated by AdaDGS and IPop-CMA in maximizing MaxSkyTiles, The top-left pattern in Figure ii the targeted one, and the other three represent different types of local minima. The probability of generating the targeted pattern is 90% for AdaDGS, and 74% for IPop-CMA.
Adusske/Ties
MlanEnennees
Mankcils
10
IPop-EMM
(PAD-CMA
-20
A01D08
Loca
-10
Losa
-15
100
-10
500
1003
500
1000
600
1000
500
1000
# +unnction evaluations
+unccton eva Lations
# function avaluation
# #utcction evaluztions
Figure 3: Comparison of the loss decay w.r.t. function evaluations for four objectives. From left to right: generate Mario level with i) maximum number of sky tiles. ii) maximum number of enemies, iii) forcing AI Mario to make the most kills, and iv) forcing AI Mario to make the most jumps.
CONCLUSION
We developed adaptive optimization algorithm with the DGS gradient, which successfully moved the need of hyper-parameter fine tuning of the original DGS method in (Zhang et al. 2020). Experimental results demonstrated the superior performance of the AdaDGS method compared to
https: http://wwwwwwtbbbbeeoo
8

---

Under review as a conference paper at ICLR 2021
Figure 4: The levels generated by optimizing MaxSkyTile Tiles objective have four patterns. From top left, clockwise: High number (>80) of sky tiles, medium number (= 40) of sky tiles, medium number of sky tiles with ground, and low number (= 20) of sky tiles. The top-left type of patterns the targeted pattern and the other three represent local minima. The probabilities of generating four types of patterns are: AdaDGS: 90%. 4%, 2%, 4% and IPop-CMA: 74%, 8%, 8%, 10% (from top left, clockwise). AdaDGS shows better performance on generating the targeted pattern.
several the state-of-the-art black-box optimization methods. On the other hand, the AdaDGS method has some drawbacks that need to addressed. The most important one sampling complexity. The GH quadrature requires M x d samples per iteration, which is much more than samples required by MC estimators. The reasons why the AdaDGS outperforms several ES-type methods are due to the good quality of the DGS gradient direction and the line search which significantly reduces the number of iterations. However, when the computing budget is very limited (e.g.. only allowing d function evaluations for d-dimensional problem), then our method becomes inapplicable. One way to alleviate this challenge is to adopt dimensionality reduction (DR) techniques (Choromanski et al.) 2019), such as active subspace and sliced linear regression, and apply the AdaDGS in a subspace to reduce the sampling complexity. Incorporating DR into the AdaDGS method will be considered in our future research.
REFERENCES
M. Abramowitz and I. Stegun (eds.). Handbook of Mathematical Functions. Dover, New York, 1972.
Youhei Akimoto and Nikolaus Hansen. Projection-based restricted covariance matrix adapta- tion for high dimension. In Proceedings of the Genetic and Evolutionary Computation Con- ference 2016, GECCO 16, pp. 197204, New York, NY, USA, 2016. Association for Com- puting Machinery. ISBN 9781450342063.
doi: 10. 10.1145/29088122298888
URL https:
19e./1145/299 1111:1111115/299881188 2908863
Larry Armijo. Minimization of functions having lipschitz continuous first partial derivatives. Pacific
Math., 16(1), 1966.
A. Auger and N. Hansen. A restart ema evolution strategy with increasing population size. In 2005 IEEE Congress on Evolutionary Computation, volume 2, pp. 1779-1776 Vol. 2, 2005.
Krishnakumar Balasubramanian and Saeed Ghadimi. Zeroth-order (non)-convex stochastic opti- mization via conditional gradient and gradient updates. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS18, pp. 34593468, Red Hook, NY, USA, 2018. Curran Associates Inc.
El Houcine Bergou, Eduard Gorbunov, Peter Richtrik, and Peter Richtárik. Stochastic three points method for unconstrained smooth minimization. arXiv: 1902.03591, 2019.
Sbastien Bubeck and Nicol Cesa- Cesa-BBanchhi Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012. ISSN 1935-8237. doi: 10.1561/2200000024. URL http:// http:://cc..d1.../1111......
22000000241

---

Under review as a conference paper at ICLR 2021
Marco Ceze, Marcelo Hayashi, and Ernani Volpe. A Study of the CST Parameterizattin Character- istics. doi: 10.251416.2009-7766 URL /ntp:::t////// /ttp:://arr.aaaaaa org/ wttp:////////ooooooooooeooooeee/ abs aaaaaabas100000 http///a/aa////////////
6.2009-3767
Pin-Yu Chen, Huan Zhang, Yash Sharma, Jinfeng Yi, and Cho-Jui Hsieh. Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute mod- cls. In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, AlSec 17. pp. 1526, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450352024. doi: 10.114553128572.314442 $128572.31400
URL
1145/
Xiangyi Chen, Sijia Liu, Kaidi Xu, Xingguo Li, Xue Lian Lin, Mingyi Hong, and David E. Cox. Zo-adamm: Zeroth-order adaptive momentum method for black-box optimization. In NeurIPS, 2019.
Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani. Richard E Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. International Conference Machine Learning, pp. 969-9777 997999977440 2018.
Krzysztof M Choromanski, Aldo Pacchiano, Jack Parker-Holder Yunhao Tang, and Vikas Sind- hwani. From complexity to simplicity: Adaptive es-active subspaces for blackbox optimization. In Advances Neural Information Processing Systems 32, pp. 10299-10309. Curran Associates, Inc., 2019.
A. Dereventsov, C. G. Webster, and D. Daws Jr. An adaptive stochastic gradient-free approach for high-dimensional blackbox optimization. ArXiv, arXiv:2006. 10887, 2020.
Mark Drela. Xfoil: An analysis and design system for low reynolds number airfoils. In Thomas Mueller (ed.). Low Reynolds Number Aerodynamics, pp. 1-12, Berlin, Heidelberg, 1989. Springer Berlin Heidelberg. ISBN 978-3-642-84010-44
John C. Duchi, Michael I. Jordan, Martin J. Wainwright, and Andre Wibisono. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61:2788-2806, 2015.
Mohammed El-Abd. Black-box optimization benchmarking for noiseless function testbed using artificial bee colony algorithm. In Proceedings of the 12th Annual Conference Companion on Genetic and Evolutionary Computation, GECCO 10, pp. 17191724, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 47014503..735. doi: 10. 10.1145/1830761 1830794.
URL http:ttt:////o //o1: htt///i..gg//////// /t0gg/10... 1 1145/1 830761. 830794]
David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local bayesian optimization. In Advances Neural Information Process- ing Systems, pp. 5497-5508, 2019.
Abraham D. Flaxman, Adam Tauman Kalai, Adam Tauman Kalai, and H. Brendan McMahan. On- line convex optimization in the bandit setting: gradient descent without a gradient. Proceedings of the 16th Annual ACM-SIAM symposium on Discrete Algorithms, pp. 385-394, 2005.
Matthew C. Fontaine, Ruilin Liu, Ahmed Khalifa, Julian Togelius, Amy K. Hoover, and Stefanos Nikolaidis. Illuminating mario scenes in the latent space of generative adversarial network. arXiv:2007.05674, 2020.
Daniel Golovin, John Karro, Greg Kochanski, Chan-Soo Lee, Xingyou Song, and Qiuyi Zhang- Gradientless descent: High-dimensional zeroth- optimization. ArXiv, abs/ /t///991..663111 2020.
I. Goodfellow, Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. Advances in Neural Information Processing Systems, 2014.
Nikolaus Hansen. CMA-ES with Two-Point Step-Size Adaptation. Research Report RR-6527, INRIA, 2008. URL https://hal faell.nnriii inrianiii.. http:/inria0002665..1 00276854
10

---

Under review as a conference paper at ICLR 2021
Kevin G. Jamieson, Robert D. Nowak, and Benjamin Recht. Query complexity of derivative-free op- timization. In Proceedings of the 25th International Conference on Neural Information Process- ing Systems Volume 2, NIPS12, pp. 26722680, Red Hook, NY, USA, 2012. Curran Associates Inc.
Momin Jamil and Xin-She Yang. A literature survey of benchmark functions for global optimisation problems. I 4:150-194, 2013.
Brenda Kulfan. Universal Parametric Geomelry Reprexentation Method "CST" 2008. doi: 10.2514/6.2007-22 URL htth::tp:://art
Jeffrey Larson, Matt Menickelly, and Stefan M. Wild. Derivative-free optimization methods. Acta Numerica, 28:287-404, 2019.
Sijia Liu, Jie Chen, Pin-Yu Yu Chen, and Alfred O. Hero. Zeroth-Order Online Alternating Di- rection Method of Multipliers: Convergence Analysis and Applications. arXiv e-prints, art. arXiv:1710.07804, October 2017.
Loshchilov, T. Glasmachers, and H. Beyer. Large scale black-box optimization by limited- memory matrix adaptation. IEEE Transactions on Evolutionary Computation, 23(2):353-358, 2019.
Alvaro Maggiar, Andreas Wachter, Irina Dolinskaya, and Jeremy Staum. A derivative-fire trust- region algorithm for the optimization of functions smoothed via gaussian convolution using adap- tive multiple importance sampling. SIAM Journal on Optimization, 28(2): (472):1478-107, 2018.
Niru Maheswaranathan, Luke Metz, George Tucker, Dami Choi, and Jascha Sohl-Dickstein. Guided evolutionary strategies: Augmenting random search with surrogate gradients. Proceedings of the 36th International Conference on Machine Learning, 2019.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies is competitive for reinforcement learning. In NeurlPS, 2018.
Florian Meier, Asier Mujika, Marcelo Matheus Gauy, and Angelika Steger. Improving gradient estimation in evolutionary strategies with past descent directions. Optimization Foundations for Reinforcement Learning Workshop NeurlPS 2019, 2019.
Yurii Nesterov and Vladimir Spokoiny. Random gradient- free minimization of convex func- tions. Foundations of Computational Mathematics, 17(2):527-566 2017. doi: 10.1007/
$10208-015-9296-2 URL/ttts:://do: http:///to...rg11111//////////// 2tt///20222001--266-6-6-0
Nocedal and S. Wright. Numerical Optimization. Ppringer-Verlag New York, New York, USA, 2006.
E. Real, S. Moore, A. Selle, Saxena, Y. L. Suematsu, Tan, Q. Le, and A. Kurakin. Large- scale evolution of image classifiers. International Conference on Machine Learning (ICML), pp. 2902-2911, 2017.
Luis Miguel Rios and Nikolaos V. Sahinidis. Derivative-free optimization: review of algorithms and comparison of software implementations. Glob Optim, 56:1247-1293, 2009.
Mark Rowland, Krzysztof Choromanski, François Chalus, Aldo Pacchiano, Tamás Sarlós, Richard E. Turner, and Adrian Weller. Geometrically coupled monte carlo sampling. Proceed- ings of the 32nd International Conference Neural Information Processing Systems, NIPS18, pp. 195205, Red Hook, NY, USA, 2018, Curran Associates Inc.
Tim Salimans, Jonathan Ho, Xi Chen, and llya Sutskever. Evolution strategies as scalable alterna- tive to reinforcement learning. arXiv preprint arXiv:1703.03864 2017.
Ozan Sener and Vladlen Koltun. Leamning to guide random search. In International Confer- ence on Learning Representations, 2020. URL htttps://opeeevieeeets net htt./oormmmmmmmm l
B1cHooBKwS

---

Under review as a conference paper at ICLR 2021
Mor Sinay, Elad Sarafian, Yoram Louzoun, Noa Agmon, and Sarit Kraus. Explicit gradient learning for black-box optimization. International Conference on Machine Learning, 2020.
Vanessa Volz, Jacob Schrum, Jialin Liu, Simon M. Lucas, Adam Smith, and Sebastian Risi. Evolv- ing mario levels in the latent space of deep convolutional generative adversarial network. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '18, pp. 221228, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 978 145035618. doi: 10.114533005555320055.. URL https::tt///ooo. /doi. wwtp:oogg//.0.... /20444522222220 32 3205517
Vanessa Volz, Boris Naujoks, Pascal Kerschke, and Tea Tušar. Single- and multi-objective game- benchmark for evolutionary algorithms. In Proceedings of the Genetic and Evolutionary Com- putation Conference, GECCO '19, pp. 647655, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 978 978145036111 111118 18. doi: 10.1145/3322100..33188888 URL https:
o/dbi.oorg/1..1145////// 707 3321805
Wolfe. Convergence conditions for ascent methods. SIAM Review, 11(2), 1969.
Jiaxin Zhang, Hoang Tran, Dan Lu, and Guannan Zhang. A novel nonlocal gradient for high- dimensional black-box optimization. ArXiv, abs/2002.03001, 2020.
APPENDIX
A DEFINITION OF BENCHMARK FUNCTIONS
Here provide the definition of the 12 benchmark functions tested in Section Let 52 denote the search domain. make the test functions more general, we randomly translate the functions so that the optimal state Topt moves to new location Booc and then apply rotation. This transformation can be written as
== + Topt Tloc):
where R is a rotation matrix making the functions non-separable and Whoe a random location in 0.82. The optimization will need to travel farther to reach the new optimal state. We substitute into the standard definitions the benchmark functions formulate our test problems.
Fi (w)): Ackley function
d cxp Σ cos( (cxx)) + a + cxp(1),
Fi (xx = a cxp
b
where the dimension and = 20, = 0.2,c 2T are used in our experiments. The
initial search domain E [-32.768, 32. 768] The global minimum is (xopt) 0 Topt.
(O...., O). The Ackley function represents non-convex landscapes with nearly flat outer region. The function poses a risk for optimization algorithms, particularly hill-climbing algorithms, be trapped in one of its many local minima.
F2(x)): Alpine function
F2
Σ 1=1
2, sin(x;)) 0.1ærl,
where the initial search domain is æ E 1000 10jd. The global minimum is (x = 0, with gd
solutions. We choose Topt (O,...,00 0). This function represents multimodal landscapes with non-unique global optimum.
Fa(x): Ellipsoidal function
Fa(x)) = Σ 10
1=1
where is the dimension and x E [-2, is the input domain. The global minimum is (x 0 Topt (0, ...,...0 This represents convex and highly ill-conditioned landscapes.
12

---

Under review as a conference paper at ICLR 2021
Fa(x):: Quintic function
Fa(x))
Σ
3x + 4x. + 2n. 10x; 4/,
where E [-10, 10] the initial search domain. The global minimum is fx at is either -1 or 2. We choose Zopt (-1,..., landscapes with global structure.
This function represents multimodal
Fs (a): Rastrigin function
(z 10d Σ [ 10 cos(22x))).
where d is the dimension and æ E [-5.12, 5.12 the initial search domain. The global mini-
mum is (atpp) 0 at Fopt with global structure.
(O,..., , 0). This function represents highly multimodal landscapes
Fo(:): Rosenbrock function
d-1
Fe(x) Σ [100(x;41 =²²²² + (z; 1)²].
where d is the dimension and æ E [-5, 10 is the initial search domain. The global minimum is (atapt) = at Topt = (1,- ....... 1). The function unimodal, and the global minimum lies in
bending ridge, which needs to be followed to reach solution.
Fx()): Salomon function
d Σ
F+(x)) =
2m
+ 0.1.
where [-100, 100j is the initial search domain. The global minimum is I (xops) 0
Copt (O...., 0). This function represents multimodal landscapes with global structure.
Fa(:): Schaffer function
1)) 2
1
Σ (Vs: Vs, sin (50s
with 8; V + x2+1
Fs(x)) d
where x E [-10 100] is the initial search domain. The global minimum is f (Zopt) = 0 at
Topt (O....,,) 0). This function represents highly multimodal landscapes.
Fa(w): Rharp-Ridge function
Fo(x) 100
where dl is the dimension and x E [010, 10 d is the initial search domain. The global minimum is f (Xope) = Topt = (0, . 0). This represents conver and anisotropic landscapes. There is sharp ridge defined along x2 +... + =3 that must be followed to reach the global minimum, which creates difficulties for optimizations algorithms.
[ Sphere function
d
Fio (1)(
where [-5.12,,5.4 5.12 is the initial search domain. The global minimum is fx 0, Topt = (0, .). The Sphere function represents wnimodal, isotropic landscapes, and can be
used to test the quality of the search direction.
13

---

Under review as a conference paper at ICLR 2021
(ar(:): Trigonometric function
Fii()) -1+ Σ
0.9)²] ] 6 6sin 0.9)² + (x, 0.9)
where a: E [-500, 500] is the initial search domain. The global minimum is (( = 1, at
Topt (0.9, 0.9). This function represents multimodal landscapes with global structure.
Faz(2): Wavy function
F12 (x) =
1 d
Σ cos cos( exp
- 2
where 1: 10, [-- Tí is the initial domain. The global minimum is f 0, at Copt (0. 0). This function represents multimodal landscapes with no global structure.
B ADDITIONAL INFORMATION ABOUT THE BASELINE METHODS
B. THE ES-BPOP METHON
ES-Bpop refers the standard OpenAl evolution strategy in (Sllimans al. 2017) with the big population, i.e, the same population size as the AdaDGS method. The purpose using big population is compare the MC-based estimator for the standard GS gradient and the GH-based estimator for the DGS gradient given the same computational cost.
B.2 THE ASEBO METHOD
ASEBO refers Adaptive ES-Active Subspaces for Blackbox Optimization proposed in (Choro- manski et al. 2019). This is the state-of-the-arr method in the family of ES. It has been shown that other recent developments on ES, e.g., (Akimoto Hansen, [2066] Loshchilov et al. 2019), underperform ASEBO in optimizing the benchmark functions. We use the code published at /tttp:://itthut c jparkerth der AASE/ASE by the authors of the ASEBO method with default hyper-parameteer provided in the code.
B.3 THE IPoP-CMA METHOD
IPop-CMA refers to the restart covariance matrix adaptation evolution strategy with increased
population size proposed in (Auger & Hansen, 2005). We use the code pyema v3.0.3 available at htttps://githhb com/ CMA-EE CMA-CM/PPPPPPPP ES/pycma The main subroutine we use is cma fmin, in
which the hyper-paramccters are
restarts=9; the maximum number of restarts with increasing population size;
incpopsize=2: multiplier for increasing the population size before each restart; 0o: the initial exploration radius is set to 1/4 of the search domain width.
B.4 THE NESTEROV METHOD
Nesterov refers to the random search method proposed in (Nesterov Spokoiny 2017). We use the stochastic oracle
F++1 = xt Fx (x,,, ut).
where u, is a randomly selected direction and F'(ar, u.) the directional derivative along u,- According to the analysis in (Nesterov & Spokoiny (017), this oracle is more powerful and can be used for non-convex non-smooth functions. As suggested in (Nesterov & Spokoiny 2017), we use forward difference scheme to compute the directional derivative.
B.5
THE FD METHOD
FD refers to the classical central difference scheme for local gradient estimation. We implemented FD code following the standard numerical recipe.
14

---

Under review as a conference paper at ICLR 2021
B.6 THE TURBO METHOD
TuRBO refers to Trust-Region Bayesian Optimization proposed in (Eriksson et al. 2019), which is the state-of-the-art Bayesian optimization method. We used the code released by the authors at https://g1tthin cww/uber research/TuRee.
C ADDITIONAL RESULTS ON HIGH-DIMENSIONAL BENCHCHMARK FUNCTIONS
AdaDGS converges to the global minimum in six of our test functions. Other baselines fail to converge for any of the test functions with the same number of function evaluations. In Figure [] we plot the performance of AdaDGS and other baselines in log scale to show the convergence of our method. Figure 6 compares the convergence rate of the AdaDGS when changing the dimension of the test functions. With exception of Rastrigin function, the convergence rate does not change when we increase the dimension from 1000 to 6000.
File Aekley 1930
Fúle Testrigs 1O6D
Fiteh Sakeow 2008
10"
10P
10/
10"
124
124
57"
0.5
Vfnnction wakkticra
12
Furctin makkatoos
Lundion essurtions
Mo20: Sharp-llite D060
10
Fistt Spoen 13000
Fylsk Trgraoesttcc 33KD
102
10"
Ftc.
10
I funntioo erakeloro
Furciton oelleaooo
4 lJnc3o1 Vnd unDua
X10
AGEBO Spop
Nostargy
iPop CMM
Figure 5: Comparison of the loss decay w.r.t. # function evaluations in log-scale. AdaDGS converges to the global minimum in six of the test functions: Fi, Fs. F7, Fg. Fio. Fui Other baselines fail to converge for any of the test functions. Each curve is the mean of 20 independent trials.
Frlsi: AdMas
Plfa): Rasrignn
Filel: Sakeua
33000
1200
20200
560 FlAu))
13800
105
10000
10
4620
10
15
20
255
0
10
20
30
40
0
20
40
lterations
terations
Berations
Ky(e]: Sharp- ltskgg
Pyr lel Sptree
[e' Trignommettr
10
10
10
1350
10000
Pla) Alcee)
10P
4300
P0g- 516mg)
1nP
4380
5000
4020
104
16
18
Iseations
Figure 6: Illustration of the dimension dependence of the convergence rate of AdaDGS method. The convergence rate, i.c., the number of iterations to converge, does not change when we increase the dimension from 1000D to 6000D, with exception of Rastrigin function. All the tests need 60 iterations or less.
15


Reviews:
[{"review_id": "o3FGam6lpsA", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "SUMMARY\n\nThe paper is heavily based on [Zhang et al., 2020], where the approach of building a \"truly non-local gradient\" is brought forward. That idea appears in many variants in the literature. As far as I can see, it simply amounts to estimating the gradient from samples in a deliberately chosen distance from the current reference solution. The scientific and practical value of the baseline method [Zhang et al., 2020] is all but clear. The current paper improves upon that baseline by getting rid of two tuning parameters, which is a nice contribution.\nIn other words: The contribution of the paper in itself is valuable, provided that the baseline method is. I find the second part near-impossible to judge from the provided material. Why should a bunch of 1D estimators be vastly superior to a vector estimator? Looking for an answer I checked [Zhang et al., 2020]. However, there is no unbiased comparison with competitors, since all results are subject to extensive problem-specific hyperparameter tuning.\n\n\nTHE PROPOSED METHOD\n\nSection 2 provides a motivation of the method of [Zhang et al., 2020]. There is not much detail, in particular no pseudo code, and the various tuning parameters are missing.\n\nThe proposed method is based on line search. The search itself replace the learning rate parameter, which is then used with with an exponentially fading record technique to adapt the sampling radius.\n\nWhen setting the algorithm parameters, it is assumed that there is a bounded domain inside of which optimization is performed. However, at least conceptually, all test functions are defined on unbounded domains (real vector spaces). In my opinion, a solid optimization algorithm should not depend (critically) on the presence of bounds. Gradient descent does not, so why should a line search method?\n\nAlso, the default target precision is quite bad: L_{min} = L_{max} / 200, or 0.5% of the diameter of the space. In a 1000D unit hypercube that's roughly 0.158. I don't think that's a satisfactory precision. An evolution strategy will happily identify the optimum to arbitrary precision, and close to numerical precision in practice. Instead of limiting the algorithm in such a way it should feature a truly adaptive mechanism.\n\nI simply cannot believe the condition $|F(x_t) - F(x_{t-1})| / |F(x_{t-1})| < \\gamma$. What prevents us from dividing by zero? The condition seems to assume that the optimal value is zero. That's a no-go.\n\nUnder \"reset the smoothing radius\" it is claimed that the method \"converges\" in less than 10 optimization steps. How comes? Did I overlook a second order method? No first order method ever converges that fast, unless the problem is completely trivial. Anyway, the very need for a reset mechanism and the absence of a detection/trigger mechanism is a bad sign.\n\nRandom generation of the rotation matrix: It should be said that sampling a random orthogonal matrix from the uniform distribution is a cubic time procedure, which is surely undesirable. On the other hand, generating a fresh matrix from time to time is obviously a good idea.\n\n\nAN IMPORTANT (SIDE) NOTE ON EVOLUTION STRATEGIES\n\nThe paper includes many weak and even clearly wrong statements about ES. I see lots of misconceptions, not only in this paper. Somehow, when it comes to ES, the ML community seems to live in a parallel universe; it really started to invent its own reality. ES research does not (primarily) take place at ML conferences, but at GECCO, FOGA, PPSN and a few others. However, nobody in ML seems to read any further than Salimans plus a few (good) papers published in JMLR. When talking about ES, ignoring these conferences simply does not work. Nearly none of the algorithms discussed in ML actually qualify as ES, according to the very definition of the method. More often than not, there is no ranking (and selection) of solutions, and no step size control, which was at the core of ES since their inception nearly 50 years ago. The NES family of algorithm was exploring an interesting connection to the gradient-based world. However, concluding that ES are gradient estimators is just wrong.\n\nHere is a concrete point how this attitude affects the current paper. Appendix B.2 states verbatim: \"ASEBO refers to Adaptive ES-Active Subspaces for Blackbox Optimization proposed in (Choromanski et al., 2019). This is the state-of-the-art method in the family of ES.\"\nWow...what? I must have lived behind the moon, I missed the new SOTA. That statement is shared by exactly no single lead figure in evolution strategies research. Maybe it was made up by the authors, or claimed by the cited paper or github repository -- I don't know, and it is anyway useless to track down its origin. In my surprise, I checked the ASEBO repository and the paper cited therein. There the ASEBO algorithm was found to be superior to several variants of CMA-ES. Knowing the compared algorithms well, none of the experimental results on analytic benchmarks looked even remotely plausible to me. I quickly fired up a control experiment on the 1000-dimensional sphere, where ASEBO was reported to reduce the function value by about a factor of two in 20K function evaluations. With identical setup, the three ES variants I tested reduce it by a factor between 30 and 100, with zero tuning, including an 11-lines (1+1)-ES. My test also included LM-MA-ES, which was included in that benchmark, where it did not do anything.\nIs it just me? This reminds me of \"alternative facts\". It is no wonder that ML research is chasing its own tail.\n\nCiting again from the paper: \"A exemplary type of these methods is Evolution Strategy (ES) based on the traditional GS, first introduced by (Salimans et al., 2017).\"\nThe term \"evolution strategy\" goes back to Ingo Rechenberg's PhD thesis, published in the 1970es. The state-of-the-art is marked by CMA-ES and its variants. For a very brief history check wikipedia: https://en.wikipedia.org/wiki/Evolution_strategy). NES plays only a very minor side role in the development.\nIn 2017, Salimans was standing on the shoulders of giants. There exists a vast (and in parts old) literature on evolution strategies, including very relevant but rarely cited work on applications in RL. The OpenAI paper simply leverages that literature, in poor a way, and without citing it properly (maybe that's where the problem started). The algorithm described therein has the same extremely slow convergence speed as pure random search (due to a lack of step size control), unless it is combined with ADAM, which is apparently done in the experiments but not even stated.\n\nA different point -- the paper\nOllivier, Yann, et al. \"Information-geometric optimization algorithms: A unifying picture via invariance principles.\" The Journal of Machine Learning Research 18.1 (2017): 564-628.\ndescribes the gradient flow of proper ES, which are based on ranking of solutions. This flow is defined on the statistical manifold of search distributions, not directly on the search space. There is really a lot more behind evolution strategies than what was put forward in the Salimans paper. In particular I argue that ES should not be listed under the heading \"Zeroth order methods based on local gradient surrogate\". The gradients estimated by ES have never been local.\n\nA final point, highlighting the often shallow understanding of methods like CMA-ES: The covariance matrix has a quadratic number of coefficients in the problem dimension. For successful adaptation, it requires roughly a quadratic number of data samples -- that's how its learning rates are tuned. Anyway, they are not well tuned for problem dimensions much larger than 100. When running an experiment on a 10^3-dimensional problem this means that we need a function evaluation budget in the order of 10^6 for the technique to have a meaningful effect. When running for 20K evaluations, CMA does not make sense. Just drop the CMA technique and save 99% of the computation time. Or better, use a low-rank approach like LM-MA-ES. The method is even cited [Loshchilov et al., 2019], but then ignored.\n\n\nEXPERIMENTS\n\nIt is quite clear that the experiments are not designed to answer any specific research question. Instead, there is a battery of generic performance tests, with the single focus of being best in class. That's unreasonable. For example, it cannot be expected that the new method outperforms the same method with optimal learning rate schedule. It may still be considered superior if it comes close, removes two tuning parameters, and the adaptation mechanism is robust.\n\nI appreciate the code supplement. However, it does not allow me to reproduce the experiments since it does not include the competitor methods. Indeed, I quickly implemented a CMA-ES control experiment straight into the provided code, using the ellipsoid benchmark. The performance curve I get looks VERY different from what is reported. It is initially MUCH faster and then slows down when it needs to adapt the covariance matrix.\nI also ran a few control experiments, with my own code. I picked the Rosenbrock function as an example. Critical information is missing in the paper, like the initial step size. No matter what I do, I fail to reproduce the plots, even qualitatively. The only way to make CMA-ES stall completely for 5000 evaluations is to start with a too small step size.\n\nLine search is not a new technique, and it was applied to ES for step size control. The resulting \"Two-point adaptation\" technique is the maybe second-best step size adaptation rule for CMA-ES. Here is a link to the original technique, which was refined over the years:\nhttps://arxiv.org/abs/0805.0231\nWith the small function evaluation budget (compared to the problem dimension) used in all experiments, results are dominated by initialization and step size control. Therefore please compare to this method.\n\nThis paper claims to provide a well working algorithm, however, it provides very few experiments. The ES community has an established standard benchmark suite: https://github.com/numbbo/coco. It includes a \"high-dimensional\" problems track, and it delivers far more insights into strengths and limitations of algorithms than the presented material.\n\nA simple but very important test problem is missing: the sphere function. I would really like to see the performance on this problem, since it is directly related to the quality of the gradient estimator. With a perfect gradient, an exact line search solves the problem in a single step. However, does that happen? If not, what is the limiting factor -- the gradient or the line search? The sphere would be a good opportunity for a deeper investigation and real insights.\n\nThe most important experiments are missing! The contribution of the paper is to remove tuning parameters from Zhang's method. Therefore I'd like to see the effect of the new automatic choice, with manually tuned (optimal) and naive parameter choices as baselines. Does the new mechanism work close to optimal or not? That's the core question that needs to be answered.\n\nThe way the numerical results are presented is highly problematic. On smooth unimodal problems, any well-designed ES based on ranking of solutions exhibits convergence at a linear rate. The better the rate, the faster does the algorithm converge asymptotically. This rate is the slope of the graph of $\\log(f(x_t) - f(x^*))$ as a function of $t$ (time). Therefore, in all serious ES research, performance plots ALWAYS use a log-scale for the vertical axis. I would go so far to say that the presented plots are close to meaningless.\n\nTable 1: Please plot progress curves instead of an arbitrary single point in time (1500 function evaluations).\n\nSection 4.3 reads as if super mario level generation would be a widely used benchmark. Then why does the (actually very nice) paper by Volz et al. have only 11 citations on Google scholar?\nAlso, citing a youtube video for the A-star Mario agent is unhelpful. I'd like to see the method or the code or both, but not a demo. This is supposed to be research, not entertainment. Also, that agent is a hopelessly over-optimistic definition of a \"playable\" level.\nThere is problem-specific hyperparameter tuning for this task, and only a single baseline method tested, for a shady reason. Please provide a complete comparison to all baselines and avoid problem-specific tuning. This is black-box optimization. If you tune then it counts towards your function evaluation budget.\n\nAppendix A, description of the Rosenbrock problem: \"The ridge changes its orientation d - 1 times.\"\nThe function is a 4th order polynomial. The ridge is parabola-shaped. There are no discrete changes whatsoever. Anyway, the function evaluation budget is so low that no algorithm even gets into the mode of really following the ridge, and approaching the optimum is completely impossible. In my opinion, even using the benchmark in this regime is misleading.\n\n\nCONCLUSION\n\nThe proposed method may or may not be of value, I cannot really tell. The most relevant comparison experiments are missing. Furthermore, frankly, after my own experimentation, I do not have trust in the results. Also, I need to see BBOB/COCO benchmark results, including baselines.\nAnd finally, please correct various statements on ES.\n\n\nRECOMMENDATION\n\nThe paper has many weaknesses. Most prominently, the experimental evaluation is problematic at least, and the most important experiments are missing. Therefore I recommend to reject the paper.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "byDpyNNKKz", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\n\nIn this paper, the authors apply a line-search of the step-size parameter of DGS (Zhang et al., 2020)) to reduce tunning. A heuristic update rule of the smooth parameter in DGS (Zhang et al., 2020))  is also used.  Overall, I think it is an incremental work of DGS (Zhang et al., 2020)).  The contribution is too marginal. \n\n\nPros\n\n1. The paper is well written and well organized. \n\n2. Twelve synthetic functions and two practical problems are evaluated.  The set of synthetic functions covers the most character of multi-model problems and is suitable for the evaluation of the performance of AdaDGS on multi-model problems.\n\n\n\nCons.\n \n1.  There are several hyperparameters of the proposed AdaDGS, e.g., L_{min}, L_{max},  S,  and gamma.  How to choose these hyperparameters?  Does AdaDGS sensitive to these hyperparameters?\n\n2.  In the experiments on synthetic problems, the initialization point and optimal point are not clear. What is the x_{opt} for each synthetic problem?  What is the initialization point for each method?  Actually, the optimization performance depending on the distance between the initialization point and the optimal point. It is challenging for problems with a large distance. For example, the authors can check the performance on rotated Ackley and Rastrigin with x_{opt} = 100* ones(d,1) and x_{ini} = 0 .  I would like to see a comparison with other baselines on problems with increasing distance || x_{opt} - x_{ini} ||. The authors can fix x_{ini} at zeros, and set x_{opt} = 2*ones(d,1) ,  x_{opt} = 5*ones(d,1) and x_{opt} = 10*ones(d,1).\n\n3.  For high-dimension multi-model problems, a large population size can reduce stuck at bad local optimum at the early phase.  In the experiments, the population size of CMA-ES is different from AdaDGS. Keep the population size the same can reduce the influence of this factor.  I would like to see a comparison with CMA-ES with a population size the same as AdaDGS. \n\n4.  In the experiments, the dimensions of synthetic problems are thousands.  The regime of dimensions of problems that are suited for AdaDGS is not clear.  I would like to see a comparison with baselines on  100-dimensional problems.\n\n\nKindly reminding: the template may be inappropriately used. It is not “Published as a conference paper at ICLR 2021”.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Zn_SkoeQQ2V", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "** Summary **\n\nThis paper considers the problem of adapting the learning rate and smoothing parameter in the Directional Gaussian Smoothing (DGS) algorithm. The authors claim DGS is particularly sensitive to these parameters and thus attribute the strong experimental results to these changes. \n\n** Primary Reason for Score**\n\nThe sole contribution of this work is an online hyperparameter optimization approach to improve DGS. The comparisons vs. other methods are strong, but there is no comparison vs. DGS/other approaches to learn hyperparameters for DGS. That should be the focus here, since the contribution of this paper is solely the adaptive mechanism. It would be useful for example to know if this method is able to learn the best values without any prior information. That may make the use of backtracking line search more prominent across other methods, as if it is just useful for DGS then it may have limited impact.  \n\n** Strengths **\n\n1) The topic of learning hyperparameters on the fly is well-motivated and an important direction to improve many existing methods. \n2) The experiments are interesting, with a wide range of tasks considered. The authors use a significant number of seeds, and present the results clearly. \n3) The discussion of performance on different tasks (in particular, Section 4.1) is useful. \n4) The authors included several (challenging) baselines to demonstrate the performance. \n5) The proposed idea of including dimensionality reduction techniques seems like interesting future work.\n\n** Weaknesses **\n\n1) It is not clear how much improvement the adaptive component makes vs. DGS. It would be great to see detailed ablation studies of the individual hyperparameter optimization methods and whether they learn optimal configurations without prior knowledge. For instance, it is entirely possible that DGS performs better than AdaDGS and the reader wouldn’t know. That is the minimum that should be included however, ideally we would be able to understand where the gains come from (assuming they exist).\n2) DGS itself is not published (as far as I can see) and has only been cited once. Therefore, it is hard to see significant impact for this work, as it is presented as a method to improve *just* DGS. It would be interesting to see if the proposed method can improve other algorithms too. \n3) It would be useful to get a comparison vs. other hyperparameter optimization methods, since that is the sole contribution of the work. This has been studied extensively (for example, online-learning approaches or blackbox methods like PBT/Hyperband). \n4) Section 4.3 is a nice application of blackbox optimization methods, however, given the noise in Figure 3, it is hard to be convinced that AdaDGS is any better than IPop-CMA. \n5) We don’t get to see how the new meta-parameters were chosen. It is alluded to on p4, for example: “We do not observe significant benefit of using more than 5 GH quadrature points per direction. In some tests, 3 GH quadrature points per direction are sufficient.” but we never see this. Given the hyperparameters for the baselines were likely taken off the shelf, it is possible that AdaDGS was simply tuned better for the tasks. \n\n** Minor issues **\n\n- It would be useful to include a wall-clock comparison, if possible.", "extra_scores": {}, "extra_text": {}}, {"review_id": "CYhx3o2WXl8", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors study the problem of global non-convex optimization with access only to function valuations. Specifically, they propose an approach to automatically control the hyper-parameters of Directional Gaussian Smoothing (DGS) a recently proposed solution for the problem. Their proposed solution trade-offs some additional function evaluations per parameter update to perform a line search for the optimal learning rate. Then the tuned learning rate informs the update for the Gaussian smoothing parameter. The proposed automated tuning approach is supported by a large set of experiments that include standard global optimization benchmarks as well as practical applications.\n\nPros:\n1) The authors provide intuition behind the key choices of their automated tuning approach.\n2) The experimental results are comprehensive and the proposed approach has (sometimes substantially) better performance than the alternatives.\n\nCons:\n1) The proposed tuning techniques are not very particular to the specifics of the DGS algorithm. Line search for tuning the learning rate is applicable to a wide variety of optimization algorithms. The update rule of Equation (4) could be applicable to any algorithm that employs Gaussian smoothing. It would be helpful if the authors explained how their tuning heuristics are tied to DGS.\n2)  The main effort of the authors is to avoid having to use learning rate and smoothing update schedules as they introduce many hyper-parameters. However, the author's tuning approach also introduces many hyper-parameters as well like $L_{\\max}$, $L_{\\min}$, $\\gamma$ and $S$. It would help if the authors explained why the newly introduced parameters can be chosen in a more straightforward fashion compared to the parameters they replace. \n3) In the experimental analysis, the authors show that DGS with their tuning approach outperforms the baselines. Given that plain DGS (with some default adaptation schedule) is not part of the baselines, it is not clear if the performance difference should be attributed to DGS or the tuning mechanism. Adding DGS as a baseline would go a long way towards analyzing the contribution of the tuning algorithm. \n\nFor now, I am assigning a weak reject score. However, I am willing to substantially increase my score if the authors address the above concerns.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The main goal of this paper is to develop a new adaptive strategy to remove the need of hyperparameter fine tuning, which hinders the performance of DGS (Zhang et al., 2020) method. This paper applies a line-search of the step-size parameter of DGS  to reduce tuning.  A heuristic update rule of the smooth parameter in DGS (Zhang et al., 2020)) is also used. 

Pros
+ The topic of learning hyperparameters on the fly is well-motivated and an important direction to improve many existing methods.
+ A wide range of tasks are considered in the experiments are interesting, with a wide range of tasks considered. 


Cons
- Reviewers have found the contribution to be incremental and marginal. Specifically, the reviewers have expressed concerns on the impact of the work since it verifies improvement upon DGS only. The paper could be stronger by showing evidence of improving other algorithms. 
-  In the work of [Zhang et. al., 2020], there are two parameters that require careful selection - the learning rate and smoothing radius. However, the proposed approach still relies on some hyperparameters. Although the authors claim that the method is not sensitive to these hyperparameters, it could be better justified. 
- The initial version lacks evaluation of the adaptive mechanism, although the authors added the comparison in the revised version. 
- The paper could be further improved by comparing against other hyperparameter optimization methods. 

We acknowledge the detailed response and the modifications of the manuscript. We believe the paper will make a more profound contribution and impact after addressing some of the major concerns raised by the reviewers. 

Decision: Reject