Improving Evolutionary Strategies with Generative Neural Networks
Authors: Louis Faury
Clément Calauzènes
Olivier Fercoq
Venue:  (2020)
Keywords: black-box optimization
evolutionary strategies
generative neural networks

Abstract: Evolutionary Strategies (ES) are a popular family of black-box zeroth-order optimization algorithms which rely on search distributions to efficiently optimize a large variety of objective functions. This paper investigates the potential benefits of using highly flexible search distributions in ES algorithms, in contrast to standard ones (typically Gaussians). We model such distributions with Generative Neural Networks (GNNs) and introduce a new ES algorithm that leverages their expressiveness to accelerate the stochastic search. Because it acts as a plug-in, our approach allows to augment virtually any standard ES algorithm with flexible search distributions. We demonstrate the empirical advantages of this method on a diversity of objective functions.

Under review as a conference paper at ICLR 2020
IMPROVING EVOLUTIONARY STRATEGIES WITH GEN- ERATIVE NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Evolutionary Strategies (ES) a popular family of black-box zeroth-order op- timization algorithms which rely on search distributions to efficiently optimize a large variety of objective functions. This paper investigates the potential bene- fits of using highly flexible search distributions in ES algorithms, in contrast to standard ones (typically Gaussians). We model such distributions with Generative Neural Networks (GNNs) and introduce a new ES algorithm that leverages their expressiveness to accelerate the stochastic search. Because acts as a plug-in, our approach allows to augment virtually any standard ES algorithm with flexible search distributions. We demonstrate the empirical advantages of this method on diversity of objective functions.
INTRODUCTION
We are interested in the global minimization of a black-box objective function, only accessible through zeroth-order oracle. In many instances of this problem the objective is expensive to evaluate, which excludes brute force methods as a reasonable mean of optimization. Also, as the objective is potentially non-convex and multi-modal, its global optimization cannot be done greedily but requires careful balance between exploitation and exploration of the optimization landscape (the surface defined by the objective).
The family of algorithms used to tackle such a problem is usually dictated by the cost of one evalua- tion of the objective function (or equivalently, by the maximum number of function evaluations that are reasonable to make) and by precision requirement. For instance, Bayesian Optimization (Jones) al., 1998, Shahriari et al. 2016) targets problems of very high evaluation cost, where the global minimum must be approximately discovered after few hundreds of function evaluations. When aiming for a higher precision and hence having a larger budget (e.g. thousands of function eval- uations), popular algorithm class is the one of Evolutionary Strategies (ES) (Rechenberg 1978 Schwefel 1977), a family of heuristic search procedures.
ES algorithms rely search distribution, which role is to propose queries of potentially small value of the objective function. This search distribution is almost always chosen to be multivariate Gaussian. is namely the case of the Covariance Matrix Adaptation Evolution Strategies (CMA-ES)
(Hansen & Ostermeier (000). a state-of-the-ar ES algorithm made popular in the machine learn- ing community by good results on parameee tuning (Friedrichs & Igel, 2005| Loshchilov & Hutter 2016). It is also the case for Natural Evolution Strategies (NES) (Wierstra et al.) 2008)
algorithms, which were recently used for direct policy search in Reinforcement Learning (RL) and
shown to compete with state-of-tt oftte-of-the-ass art MDP-based RL techniques (Salimans et al. 2017]. Occa- sionally, other distributions have been used; e.g. fat-tails distributions like the Cauchy were shown to outperform the Gaussian for highly multi-modal objectives (Schaul et al. 2011).
We argue in this paper that in ES algorithms, the choice of a standard parametric search distribu- tion (Gaussian, Cauchy, ..) constitutes a potentially harmful implicit constraint for the stochastic search of a global minimum. To overcome the limitations of classical parametric search distribu- tions, we propose using flexible distributions generated by bijective Generative Neural Networks (GNNs), with computable and differentiable log- probaabbbilssiss We discuss why common existing optimization methods in ES algorithms cannot be directly used train such models and design tailored algorithm that efficiently train GNNs for an ES objective. We show how this new algo- rithm readily incorporate existing ES algorithms that operates simple search distributions,

---

Under review as a conference paper at ICLR 2020
Algorithm 1: Generic ES procedure
input: zeroth-order oracle on f, distribution To. population size repeat
(Sampling) Sample æ1,, .1,-... sid
(Evaluation) Evaluate ((..))....> (().)
( (Update) Update ne to produce a of potentially smaller objective values. until convergence;
like the Gaussian. On a variety of objective functions, we show that this extension can significantly accelerate ES algorithms.
We formally introduce the problem and provide background on Evolutionary Strategies in Section 2 We discuss the role of GNNs in generating flexible search distributions in Section We explain why usual algorithms fail to train GNNs for an ES objective and introduce new algorithm in Section Finally we report experimental results in Section
PRELIMINARIES
In what follows. the real-valued objective function f is defined over compact X' and will generi- cally denote a probability density function over X. We consider the global optimization of f:
x² argmin f(x)
#EX
2.1 EVOLUTIONARY STRATEGIES
The generic procedure followed by ES algorithms is presented in Algorithm 1 To make the update step tractable, the search distribution is tied to family of distributions and parametrized by a real- valued parameter vector 0 (e.g. the mean and covariance matrix of a Gaussian), and is referred to as Ty. This update step constitutes the main difference between ES algorithms.
Natural Evolution Strategies One principled way to perform that update is to minimize the ex- pected objective value over samples æ drawn from Te. Indeed, when the search distribution is parametric and tied parameter 0, this objective can be differentiated with respect to 0 thanks to the log-trick:
and aJ(A) 00
Olog TT(x)) 00
((0) A E., [f(z)]
ENo f(x)
This quantity can be approximated from samples - it is known as the score-function REINFORCE (Williams 1992) estimator, and provides a direction of update for 0. Unfortunately, naively follow- ing stochastic version of the gradient (2) a procedure called Plain Gradient Evolutionary Strate- gies (PGES) - is known to be highly ineffective. PGES main limitation resides in its instability when the search distribution is concentrating, making it unable precisely locate any local minimum. To improve over the PGES algorithm the authors of Wierstra et al. (2008) proposed to descend J(Ø) along its natural gradient (Amari 1998). More precisely, they introduce trust-region optimiza- tion scheme to limit the instability of PGES, and minimize linear approximation of J(0) under Hillback-Leibles (KL) divergence constraint:
argmin 58
[( + 50) J(0)= VoJ S.t (L(TT-8o||To)
To avoid solving analytically the trust region problem solution can be approximated by:
Wierstra et al. (0088) shows that its
80 x (V)(( where Fg = E.g V log oo V log (x)²1
(4)
the Fischer Information Matrix (FIM) of πи. The parameter 0 is therefore not updated along the negative gradient of J but rather along F (.), a quantity known as the natural gradient. The FIM F9 known analytically when no is multivariate Gaussian and the resulting algorithm, Exponential Natural Evolutionary Strategies (xNES) (Glasmachers et al. 2010) has been shown to reach of-t--of-theart performances large ES benchmark.
2

---

Under review as a conference paper at ICLR 2020
detalmmmun
ES iterations
Figure 2:
Example an undesirable behavior of a Gaussian search distribution. The dashed lines represent density level lines of the search distribution. Because the latter cannot have curved profile, it is forced to drastically reduce its entropy until it reaches the straight part the valley.
CMA-ES Naturally, there exist other strategies to update the search distribution For instance, CMA-ES relies on variety of heuristic mechanisms like covariance matrix adaptation and evolution paths, but is only defined when is multivariate Gaussian. Explaining such mechanisms would be out of the scope of this paper, but the interested reader is referred to the work of Hansen (2016) for detailed tutorial on CMA-ES.
2.2 LIMITATIONS OF CLASSICAL SEARCH DISTRIBUTIONS
ES implicitly balance the need for exploration and exploitation of the optimization landscape. The exploitation phase consists in updating the search distribution, and exploration happens when sam- ples are drawn from the search distribution's 's tails. The key role of the search distribution is therefore produce a support adapted the landscape's structure, so that new points are likely improve over previous samples.
We argue here that the choice of a given parametric distribution (the multivariate Gaussian distri- bution being overwhelmingly represented in stute-of-the-att ES algorithms) constitutes a potentially harmful implicit constraint for the stochastic search of a global minimum. For instance, a Gaussian distribution is not adapted to navigate curved valley because of its inability to continuously curve its density. This lack of flexibility will lead it to drastically reduce entropy, until the curved val- ley looks locally straight. At this point, the ES algorithm resembles hill-climber and barely takes advantage of the exploration abilities the search distribution. An illustration of this phenomenon presented in Figure g on the Rosenbrock function. Another limitation of classical search distri- bution is their inability to follow multiple hypothesis, that is to explore at the same time different local minima. Even if mixture models can show such flexibility, hyper--arrmettes like the number of mixtures have optimal values that are impossible to guess priori.
We want to introduce flexible search distributions overcome these limitations. Such distributions should, despite their expressiveness, be easily trainable. We should also be concerned when de- signing them with their role in the exploration/eeploittion trade off: search distribution with too much capacity could over-fit some seemingly good samples, leading to premature convergence. To sum-up, we want design cearrh-distibbutions that are:
more flexible than classical distributions
yet easily trainable
while keeping control over the exploration/ / exploitation trade-off
In the following section, we carefully investigate the class of Generative Neural Networks (GNNs) find parametric class of distributions satisfying such properties.
FLEXIBLE SEARCH DISTRIBUTIONS WITH GNNS
Generative Neural Networks (MacKay 1995) have been studied in the context of density estimation and shown to able to model complex and highly multimodal distributions (Srivastava et al.) (017)) We propose here to leverage their expressiveness for ES, and train them in principled way thanks to the ES objective:
((T) Ex [x())
3

---

Under review as a conference paper at ICLR 2020
As discussed in Section 2 optimizing (s) with baatintt-based methods is possible through the score-function estimator, which requires to be able to compute and efficiently differentiate the log- probabilities of æ.
3.1 GNN BACKGROUND
The core idea behind a GNN is to map latent variable E 2 drawn from known distribution neural network. The parameter represents the weights of this neural network while describe the degrees of freedom of the latent space distribution 2/ We denote 0= (w, 77) and (z) the density of the output variable x.
to an output variable æ = (2) where 9n is the forward-pass
For general neural network architectures, it impossible to compute (o(2)) for samples drawn from the GNN. This is namely why their are often trained with adversarial methods (Goodfellow et al. 2014) for sample generation purposes, bypassing the need of computing densities, but the expense of a good density estimation (mode-dropping). An alternative to adversarial methods was proposed with variational auto-encoders (Kingma & Welling 2013) however the cost of learning two neural networks (an encoder and decoder). A less computationally expensive method consists in restricting the possible architectures to build bijective GNNs, also known as Normalizing Flows (NF) (Rezende & Mohamed| 2015 Papamakarios et al.) 2017), which allows the exact computation of the distribution's 's density. Indeed, if 9,, is a bijection from Z to X' with inverse h, - 9nj the change of variable formula provides way to compute TT (z):
(hn(2)) Ōx
To (2=) = (h,((a)))
(5)
To have a tractable density one therefore needs to ensure that the determinant of the Jacobian [0h,,(z) easily computable. Several models satisfying these two properties (i.e bijectivity and computable Jacobian) have been proposed for density estimation (Rippel & Adams |213) Dinh
al. 2014,220 2016), and proved their expressiveness despite their relatively simple structure.
NFs therefore answer two of our needs when building our new search distribution: flexibility and casiness to train. In this work, we will focus on one NF model: the Non-Linear Independent Compo- nent Estimation (Dinh et al. 2014) (NICE) model, for its numerical stability and volume preserving properties.
3.2 NICE MODEL
The authors of NICE proposed to build complex yet invertible transformations through the use of additive coupling layers. An additive coupling layer leaves half of its input unchanged, and adds non-linear transformation of the first half to the second half. More formally, by noting v = [vi, v2] the output of coupling layer and [M1, U2] its input, one has:
and U2 u2 + t(w1)
(6)
where t is an arbitrarily complex transformation modelled by Multi-Layer Perceptron (MLP) with learnable weights and biases. This transformation has unit Jacobian determinant and is easily invertible:
"1 U1 and U2 = 22 - t(11)
and only requires a feed-forward pass on the MLP t. The choice of the decomposition u = [ur, U2] be arbitrary, and is performed by applying binary filter to the input. By stacking additive coupling layers, one can create complex distributions, and the inversion of the resulting mapping is independent of the complexity of the neural networks t. The density of the resulting distribution is readily computable thanks to the inverse transform theorem
3.3 VOLUME PRESERVING PROPERTIES
The transformation induced by NICE is volume preserving (it has a unitary Jacobian determinant). This is quite desirable in ES context, the role of concentrating the distribution minimum can be left to the latent space distribution v.- The role the additive coupling layers is therefore only to introduce noneaiirasssies in the inverse transform hy that the distribution is better adapted
4

---

Under review as a conference paper at ICLR 2020
to the optimization landscape. The fact that this fit is volume-preservvngg (every subset of the latent space has an image in the data space with the same probability mass) encourages the search distri- bution to align its tails with regions of small value of the optimization landscape, which is likely to improve the quality of future exploration steps. The NICE model therefore fits perfectly our needs for flexible search distribution that is easy to train, and that provides enough control on the explo- ration exploitation trade-off. Other bijective GNN models like the Real-NVP (Dinh et al., 2016) introduce non-volume preserving transformations, which cannot provide such control. In prac- tice, we observed that using such transformations for ES led to early concentration and premature convergence.
AN EFFICIENT TRAINING ALGORITHM
We are now equipped with enough tools to use GNNs for ES: adapted model (NICE) for our search distribution Te, and an objective to train it with:
(() Ex [f(x)]
(8)
Here, describes jointly the free parameters of the latent distribution Va and 7, the weights and biases of the MLPs forming the additive coupling layers.
We start this section by explaining why existing training strategies based on the objective (8) are not sufficient to truly leverage the flexibility of GNNs for ES, before introducing a new algorithm tailored for this task.
4.1 LIMITATIONS OF EXISTING TRAINING STRATEGIES
We found that the PGES algorithm (naive stochastic gradient descent of (8) with the score-function estimator) applied to the NICE distribution suffers from the same limitations as when applied the Gaussian; it is inable to precisely locate any local minimum. As for the Gaussian, training the NICE distribution for ES requires employing more sophisticated algorithms- such as NES.
However, using the natural gradient for the GNNs distributions is not trivial. First the Fischer In- formation Matrix Fe not known analytically and must be estimated via Monte-Carlo sampling. thereby introducing approximation errors. Also, we found that the approximations justifying to follow the descent direction provided by the natural gradient are not adapted to the NICE distribu- tion. Indeed, the assumption behind the NES update (4) is that the loss J(0) can be (locally) well approximated by the quadratic objective:
J(0 + 50) = J(O) + (o))) + " 88 F650
(9)
2
where ry is a given non-negative Lagrange multiplier. For NICE, given the highly non- non-linear nature of To this approximation is bound to fail even close the current parameter and will lead spurious updates. A classical technique (Martens 2010) to avoid such updates is to artificially increase the curvature of the quadratic term, and is known as damping. Practically, this implies using Fe + B1 instead of Fg as the local curvature metric, with 3 non non-negative damping parameter.
We found that to ensure continuous decrease of (0). and because of its highly non-linear nature when using the GNNs, the damping parameter 3 has to be set to such high values that the modifi- cations of the search distribution are too small to quickly make progress and by no means reaches -tate-of-the-art performances. We observed that even if the training of the additive coupling layers performed correctly (i.e the distribution has the correct shape), high damping of the latent space parameters prevents the distribution from quickly concentrating when minimum is found.
unclear how the damping parameter should be adapted to avoid spurious update, while still allowing the distribution to make large step in the latent space and ensure fast concentration when necded. In the following, we present an alternated minimization scheme to bypass the issues raised by natural gradient training for GNN distributions in ES context.
4.2 ALTERNATING MINIMIZATION
So far, we used the parameter to describe both w and r (respectively, the free parameters of the latent space distribution i. and the degrees of freedom of the non-linear mapping 9n), and the
5

---

Under review as a conference paper at ICLR 2020
optimization over all these parameters performed jointly. Separating the roles of w and 7, the initial objective can be rewritten as follows:
(() B. [f() (w,,n)
(10)
Therefore, the initial objective can be rewritten as the expected value of samples drawn from the latent distribution, under the objective f 9t, that is, the representation of the objective function in the latent space. If Vn is standard distribution (i.e efficiently trainable with the natural gradient) and f' o Oy is a well structured function (i.e one for which Va an efficient search distribution), then the single optimization of by classical methods (such as the natural gradient) should avoid the limitations discussed in 2.2 This new representation motivates the design of a new training algorithm that optimizes the parameters and 7) separately.
Alternating Minimization the following, we will replace the notation Te with uw,y to refer the NICE distribution with parameter (w, n)) We want to optimize and y in alternate fashion, which means performing the following updates at every step of the ES procedure:
Wt-1 argmin J [ws, 17))
(11a)
M-- argmin J (w1+1.1)) 11)
(11b)
This means that at iteration i, samples are drawn from Tan. and serve to first optimize the la- tent space distribution parameters w, and then the additive coupling layers parameters 1). For the following iteration, the population is sampled under Tw
The update (Tab of the latent space parameters naturally derived from new representation (T) of the initial objective. Indeed, can be updated via natural gradient ascent of Jus, (w),))) that is with keeping = т/ fixed. Practically, this therefore reduces to applying a NES algorithm to the latent distribution V. on the modified objective function f 9m.
Once the latent space parameters updated, the coupling layers parameters should be optimized with respect to:
J(ur41,7) = Ema, 1. [f(x)]
(12)
At this stage, the only available samples are drawn under Twe To estimate, based on these sam- ples, expectations under T. one must use importance propensity scores:
Twi+ (x)
HW 7) = =En
F(x))
(13)
Twe. (x)
The straightforward minimization of this off-line objective known to lead to degeneracies (Swami- nathan & Joachims 2015 Section 4), and must therefore be regularized. For our application, it is also desirable make sure that the update 7) does not undo the progress made in the latent space in other words, we want to regularize the change in f fo- To that extent, we adopt technique proposed in |Schulman et al. (2017) and minimize a modification on the initial objective with clipped propensity weights:
Twees Twe+i (4) )
7++1 argmin E
f(x)clipp
(14)
(x) clips the value of x between - and 1 1+ The parameter is an hyper-paramete that controls the change in distribution, and the program (4) can be efficiently solved via a gradient descent type algorithm, such Adam (Kingma & Ba 2014).
To sum up, we propose optimizing the latent distribution and the coupling layers separately. The latent space is optimized by natural gradient descent, and the coupling layers via an off policy ob- jective with clipped propensity weights. We call this algorithm GNN-ES for Generative Neural Networks Evolutionary Strategies.

---

Under review as a conference paper at ICLR 2020
Latent space optimization It turns out the GNN-ES can be readily modified to incorporate virtu- ally any existing ES algorithms that operates on the simple distribution V.. For instance, if vu is set to be multivariate Gaussian with learnable mean and covariance matrix, the latent space optimiza- tion (Ta)) can be performed by either xÑES or CMA-FS. This holds for any standard distribution that distribution. This remark allows
to and any ES algorithm operating in a more general framework and to understand it as way to improve existing ES algorithm, by providing principled way to learn complex, non-linear transformations on top of rather standard search distributions (like the Gaussian). In what follows, we will use the GNN prefix in front of existing ES algorithm to describe its augmented version with our algorithm, working as plug-in in. Pseudo-code for this general algorithm can be found in Appendix B
place GNN-ES
4.3 ADDITIONAL TOOLS
Using historic data ES algorithms typically use small populations of samples to estimate expec- tations. Such small sample sizes ingful transformation Пn- To circumvent this problem, we augment the off-line program (14) with samples for past generations thanks to the fused importance sampling estimator (Peshkin & Shelton 2002]. This technique is classical in similar settings like MDP-basee reinforcement learning and counterfactual reasoning (Nedelec et al., 2017 Agarwal et al. 2017) and proves be essential for our problem. Formally, for given horizon T' that controls how far we look in the past, this amounts to storing the samples x drawn from -ō.-r-1..... To, (as well as their respective scores) in a buffer Hr. The objective
for enough data exposure for the GNN to build a mean-
(13 can then be rewritten as:
f(z) T (2) Tw (x)
(W f(z) To, (I) + To, (x)
E B
=T T -T,,,,,
(15)
This technique allows increase the data exposure of the GNN by using past samples (and therefore does not require additional function evaluations) and to reduce the variance of the off-line estimator of the original expectation (12) (Nedelec et al., 2017). To control the change in distribution, the fused propensity weights can then be clipped in a similar fashion than in the program (14).
Mode preserving properties To achieve improved exploration, the search distribution should align its tails with the level sets of the objective function. This is not guaranteed when performing the update step (14) since the GNN's update could simply move the mean of the search distribution without shaping the tails. One way to encourage the GNN's capacity to be allocated to the tails is to impose a mode-preserving property. If μ denotes the location of a mode of the latent distribu- tion, then the mode of the distribution wo generated by the NICE model is located in 9n (1)) (see Appendix A for the proof). is therefore easy to build a map fn based on the initial In that is mode-presse :edeepres:rving:
fz) é gn (T( + fmx
(16)
where /e denotes the mode of the latent distribution u. iteration f. Defined such, fn preserves the mode of the previous search distribution (since S (14) = f (1)),, is trivially still bijection and remains volume preserving. Using the push-forward map fn instead of gy, we explicitly push the flexibility brought by the GNN to impact only the tails of the search distribution. As detailed in
an ablation study presented in Appendix F this additional tool turns out be essential in order to use GNNs for ES.
5 EXPERIMENTAL RESULTS
In all that follows, we build the NICE model with three coupling layers. Each coupling layer's non- linear mapping built with a one hidden layer MLP. with 128 neurons and leaky ReLU (Maas et al. 2013) actívation functions. This architecture is kept constant in all our experiments.
5.1
VISUALIZATION
We present here two-dimensional visualizations of the behavior of a GNN distribution trained with GNN-xNES- the latent distribution is therefore Gaussian. Figure 3a displays the density level lines
7

---

Experimental set-up We present experiments on both unimodal and multimodal objectives for xNES and GNN-XNES. We use the official implementation of xNEsSWith default hyper-parameters (such as the population size X), both as a baseline and as an inner optimization method for GNN- xNES. All experiments run the COmparing Continous Optimizers (COCO) (Hansen et al. 2016) platform, popular framework for comparing black-box optimization algorithms. It namely allows to benchmark different algorithms translated and rotated versions of the same objectives, in order to evaluate multiple configurations with different global minimum positions. We compare xNES and GNN-XNES on functions from the 2018 Black-Box Optimization Benchmark (BBOB) (aasen et al, 2010) suite. When comparing these two algorithms, we impose that their initial search distributions are close order ensure fair comparison. We insist on the fact that the xNES algorithm has the exact same configuration whether it is used by itself or as an inner- optimmzatiiiiionnn al- value Under review as a conference paper at ICLR 2020
3MN
(a) Data space
(b) Latent space
Data space
(b) Latent space
Figure 3: Rosenbrock
Figure 4: Rastrigin
Density level curves (dotted lines) in the data space and in the latent space
of the resulting search distribution on the Rosenbrock function. Figure 3b displays the density level lines of the latent distribution, as well as the learned representation of the objective in the latent space. The search distribution is able to have curved density isolines, enabling better exploration. In the latent space, the global minimum can be reached without navigating curved valley. Figures and[4) provide similar visualizations on the Rastrigin function, highly multimodal but symmetric objective. The GNN lowers the barriers between local minima, making it easier to escape local minimum to the global minimum.
5.2 SYNTHETIC OBJECTIVES
gorithm for GNN-xNES. Further experimental details, including additional for GNN-xNES are provided in Appendix
Unimodal landscapes We run the different algorithms two unimodal landscapes where expect GNN search distributions to bring a significant improvement over the Gaussian as discussed the Rotated Rosenbrock function curved valley with high
in 2.2 These objectives functions conditioning) and the Bent Cigar (an asymmetric and curved Cigar function). Extensive details on these objective functions can found the BBOB documentation (Hansen al. 2010). Results on additional unimodal functions can be found in Appendix E
Performance is measured through Empirical Cumulative Distribution Functions (ECDFs) of the run- time, also known as data profiles (Moré & Wild 2009). Such curves report the fraction of problems solved as a function of the number of objective evaluations. For given precision A, a problem is said to be solved if the best function evaluation made so far is smaller than f f(z*) + A. We create 200 problems, equally spaced on log-scale from A 102 A 10-5 and, as in the COCO framework, aggregate them over 15 function instances. Results are presented in Figure 5 for the two benchmark functions and in dimensions 2, 10.
Multimodal landscapes We now compare the performances the different algorithms on a col- lection of three multimodal objectives: the Rastrigin function, the and the Schwefel function. Extensive details about these objectives can be found in Hansen et al. 2010).
function
available in the Brain library Schaul al. 2010
8

---

Under review as a conference paper at ICLR 2020
netton 1000 mmobeem
gen_
gen_xnes
gen ynes
0.3
250
606
0:00
1008
530
2003
1506
2000
2500
3000
0.
4003
8000
10000
Fesllantoos
(a) Rotated Rosenbrock, d=2
(b) Rotated Rosenbrock, d=5
(c) Rotated Rosenbrock, d=10
1.3
meddonn of 5100 colwed
0.-
2784
2018
2014
gn. Xness
gen Xnds
gen XnIS
326
10:00
61
ZAGS
cxllutioos
evakautiors
#evabastore
(d) Bent Cigar, d=2
(c) Bent Cigar, d=S
(l) Bent Cigar, d=10
Figure 5: ECDFs curves comparing GNN-xNES and xNES the Rotated Rosenbrock and Bent Cigar functions, in dimensions d=2,5,10.
70e3
xnns
3007
xnes
2005
menn www.uttiont
4003
cres
1102
2003
2000
meen
1003
drrension
d drmesstoon
drrensionn
(a) Rastrigin
(b)
(c) Schwefel
Figure 6: Scaling comparison GNN-xNES and xNES on the Rastrigin, Briewank-RRosebree
and Schwefel functions, d=2,5,10.
When using ES algorithms to optimize multimodal functions, it is usual to augment them with restart strategies (Hansen 2016). When convergence is detected, the search distribution re-initialized in order search another part of the landscape, and often the population size is increased. This allows to fairly compared algorithms that converge fast to potentially bad local minima, and algorithms that converges slower better minima. Their exist large variety of restart strategies (Loshchilov al. 2012 Auger & Hansen 2005); as the official implementation of xNES is not equipped with a default one, trigger restart whenever the algorithm makes progress for
than 30 d iterations.
The standard deviation of the search distribution is set back to 1, and its mean sampled uniformly within the compact X' of interest (defined by the COCO framework). At each restart, the population size of the algorithm is multiplied by 2, as in Auger & Hansen (2005). This restart strategy is used for both xNES and GNN-xNES.
We measure performance as the number of functions evaluations to find an objective value smaller than f(**) + 10-5 within budget of d x 10a function evaluations, averaged over 15 function instances. When algorithm is not able to discover the global minimum within the given budget, we use the maximum number of evaluations as its performance. For visualization purposes, this measure of performance is divided by d². Results reported in Figure 6 On all objectives, and for all dimensions, GNN-xNES discovers (in average) the global minimum faster than xNES.
Additional results others multimodal functions presented in Appendix

---

Under review as a conference paper at ICLR 2020
10000
4000
averaged reward
150
averaged reward
8000
Averaged reward
6000
3000
100
4000
2000
gnn, gnn_xnes xixs
2000
gnn. xnes
xnés
xnes
1000
gnn unn_xnes
0
0.5
15
1.5
evaluations 1e3
evaluations
evaluations x 1e3
(a) Swimmer-vl
(b) InvertedDaubbeeennuulmyy
(c) HalfCheetah-vl
Figure 7: Direct Policy Search experiments
5.3
REINFORCEMENT LEARNING EXPERIMENTS
The goal of this section is to present additional comparison between xNES and GNN-xNES on RI.-based objective functions less synthetic than the previously considered BBOB functions. ES algorithms have recently been used for direct policy search in Reinforcement Learning (RL) and shown to reach performances comparable with statc-of-the-art MDP-based techniques (Liu et al.) 2019 Salimans et al. 2017). Direct Policy Search ignores the MDP structure of the RL environment and rather considers it as a black-box. The search for the optimal policy is performed directly in parameter space maximize the average reward per trajectory:
f(z) = Eyopp
Σ JET
(17)
where Par is the distribution of trajectories induced by the policy (the state-conditional distribution over actions) parametrized by æ, and r the rewards generated by the environment. The objective 17 can readily be approximated from samples by simply rolling out M trajectories, and optimized using ES. our experiments we set M = 10 and optimize deterministic linear policies (as in Rajeswaran al. (2017)).
In Figures and we the Mujoco locomotion tasks Swimmer and InvertedDoublePentuie
we report results the GNN-xNES algorithm compared to xNES, when run on
both from the OpenAl Gym (Brockman et al. 2016). Performance is measured by the average reward per trajectory as a function of the number of evaluations of the objective Results averaged over 5 random seeds (ruling the initialization of the environment and the initial distribution over the policy parameters x), In all three environments, GNN-XNES discovers behaviors of high rewards faster than xNES.
6 CONCLUSION
In this work, we motivate the use of GNNs for improving Evolutionary Strategies by pinpointing the limitations of classical search distributions, commonly used by standard ES algorithms. We propose a new algorithm that leverages the high flexibility of distributions generated by bijective GNNs with an ES objective. We highlight that this algorithm can be seen as plug-in extension to existing ES algorithms, and therefore can virtually incorporate any of them. Finally, we show its empirical ad- vantages across a diversity of synthetic objective functions, Reinforcement Learning. Beyond the proposal of this algorithm, we believe that our work highlights the role of expressiveness in exploration for optimization tasks. This idea could be leverage in other settings where exploration is crucial, such a -bsed policy search methods. An interesting line of future work could focus optimizing GNN-based conditional distribution for RL tasks idea already developed in Ward et al. (2019): ; Mazoure et al. (2019). Other possible extensions to our work could focus on investigating lirst-order and mixed oracles, such as in Grathwohl et al. 2001
well as from objectives coming from
Faury et al. (2018).
We used the 1 1 ab lihrary Duan 2016) for our experiments.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Aman Agarwal, Soumya Basu, Tobias Schnabel, and Thorsten Joachims. Effective evaluation us- ing logged bandit feedback from multiple loggers. Proceedings of the 23rd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 687-696. ACM, 2017.
Shun-Ichi Amari. Natural gradient works efficiently in learning. Neural Computation, 10(2):251- 276, 1998.
Anne Auger and Nikolaus Hansen. A restart ema evolution strategy with increasing population size. In 2005 IEEE congress on evolutionary computation, volume 2. pp. 1769-1776. IEEE, 2005.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAi Gym. arXiv preprint 166. 2016.
Laurent Dinh, David Krueger, and Yoshua Bengio. NICE: Non-Linear Independent Components
Estimation. arXiv preprint
2014.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density Estimation using Real NVP. arXiv 2016.
preprint
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking Deep Rein- forcement Learning for Continuous Control. In International Conference on Machine Learning, pp. 1329-1338, 2016.
Louis Faury, Flavian Vasile, Clément Calauzènes, and Oliver Fercoq. Neural Generative Models for Global Optimization with Gradients. arXiv preprint /85500890 2018.
Frauke Friedrichs and Christian lgel. Evolutionary tuning of multiple SVM parameters. Neurocom- puting, 64: 107-117, 2005.
Tobias Glasmachers, Tom Schaul, Sun Yi, Daan Wierstra, and Jürgen Schmidhuber. Exponential natural evolution strategies. In Proceedings of the 12th annual conference on Genetic and evolu- fionary computation, pp. 393-309000 ACM, 2010.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley. Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative Adversarial Nets. In Advances in Neural Infor- mation Processing Systems, pp. 2672-2680, 2014.
Will Grathwohl, Dami Choi, Yuhuai Wu, Geoff Roeder, and David Duvenaud. Backpropagation through the void: Optimizing control variates for black-box gradient estimation. arXiv preprint arXiv:1711.00123, 2017.
Nikolaus Hansen. The CMA Evolution Strategy: tutorial. arXiv preprint arXiv: 160.:00604 2016.
Nikolaus Hansen and Andreas Ostermeier. Completely derandomized self-adaptation in Evolution Strategies. Evolutionary Computation, 9(2):159-195, 2001.
Nikolaus Hansen, Anne Auger, Steffen Finck, and Raymond Ros. Real-parameter black-box opti- mization benchmarking 2010: Experimental setup. PhD thesis, INRIA, 2010.
Nikolaus Hansen, Anne Auger, Olaf Mersmann, Tea Tusar, and Dimo Brockhoff. Coco: A platform for comparing continuous optimizers in black-box setting. arXiv preprint arXiv: 18030886,3 2016.
Nikolaus Hansen, Youhei Akimoto, and Petr Baudis. CMA-ES/pyema on Github. Zen- odo, 1twp:/228811/mmoo225555255 February 2019. URL htt.tt:://c...rg///// 5281/ zerodoo. 2559634
Donald R Jones, Matthias Schonlau, and William J Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13(4):455449 1998.
Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. arXiv preprint 1411v:1412.69800 2014.
Diederik Kingma and Max Welling. 1312.6131 2013.
Auto-encoding Variational Bayes.
arXiv preprint
11

---

Under review as a conference paper at ICLR 2020
Guoqing Liu, Li Zhao, Feidiao Yang, Jiang Bian, Tao Qin, Nenghai Yu, and Tie- Yan Liu. Trust Region Evolution Strategies. Association for the Advancement of Artificial Intelligence, 2019.
Ilya Loshchilov and Frank Hutter. CMA-ES for hyperparameter optimization of deep neural net-
works. arXiv preprint arXiv: 1604.0779, 2016.
Ilya Loshchilov, Mare Schoenauer, and Michele Sebag. Alternative restart strategies for ema-es. In International Conference on Parallel Problem from Nature. pp. 296-305. Springer, 2012.
Andrew L Maas, Awni Y Hannun, and Andrew Y Ng. Rectifier nonlinearities improve neural net- work acoustic models. In ICML Workshop on Deep Learning for Audio, Speech and Language Processing. Citeseer, 2013.
David JC MacKay.
Bayesian neural networks and density networks. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment, 354(1):73-88) 80, 1995.
James Martens. Deep Learning via Hessian-free Optimization. In International Conference of Machine Learning, volume 27, pp. 735-742, 2010.
Bogdan Mazoure, Thang Doan, Audrey Durand, Devon Hjelm, and Joelle Pineau. Leveraging exploration in off- off-policy algorithms via normalizing flows. arXiv preprint WPXiv:995500692 2019.
Jorge J Moré and Stefan M Wild. Benchmarking derivative-free optimization algorithms. SIAM Journal on Optimization, 20(1):172-191, 2009.
Thomas Nedelec, Nicolas Le Roux, and Vianney Perchet. A Comparative Study of Counterfactual Estimators. arXiv preprint atXiv:1704.00773 2017
2017.
George Papamakarios, Theo Pavlakou, and lain Murray. Masked autoregressive flow for density estimation. In Advances in Neural Information Processing Systems, pp. 2338 2347, 2017.
Leonid Peshkin and Christian R Shelton. Learning from scarce experience. In Proceedings of the Nineteenth International Conference on Machine Learning, pp. 498-505, Morgan Kaufmann Publishers Inc., 2002.
Aravind Rajeswaran, Kendall Lowrey, Emanuel V Todorov, and Sham M Kakade. Towards gen- eralization and simplicity in continuous control. In Advances in Neural Information Processing Systems, pp. 6550-6561, 2017.
Ingo Rechenberg. Evolutionssttattgienn. In Simulationsmmethodenn in der Medizin und Biologie, pp- 83-114. Springer, 1978.
Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows. Interna- tional Conference on Machine Learning, pp. 1530-1538, 2015.
Oren Rippel and Ryan Prescott Adams. High-dimensional Probability Estimation with Deep Density Models. arXiv preprint arXiv:1302.51255, 2013.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution Strategies scalable alternative to Reinforcement Learning. arXiv preprint arXiv:1703.03864, 2017.
Tom Schaul, Justin Bayer, Daan Wierstra, Sun, Martin Felder, Frank Sehnke, Thomas Rückstieß, and Jürgen Schmidhuber. PyBrain. Journal of Machine Learning Research, 11:743-746, 2010.
Tom Schaul, Tobias Glasmachers, and Jürgen Schmidhuber. High dimensions and heavy tails for Natural Evolution Strategies. Proceedings of the 13th annual conference on Genetic and Evo- lutionary Computation, pp. 845-852, ACM, 2011.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal Policy 2017.
Optimization Algorithms. arXiv preprint
Hans-Paul Schwefel. Numerische Optimierung von Computer-Modeller mittels der Evolution- sstrategie: mit einer vergleichenden Einführung in die Hill-Climi Saal-CClibing-uae Zufallsstrategie. Birkhäuser, 1977.
12

---

Under review as a conference paper at ICLR 2020
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. Taking the human out of the loop: review of Bayesian Optimization. Proceedings of the IEEE, 104(1): 148-175, 2016.
Akash Srivastava, Lazar Valkoz, Chris Russell, Michael U Gutmann, and Charles Sutton. Veegan: Reducing mode collapse in GANs using Implicit Variational Learning. In Advances in Neural Information Processing Systems, pp. 3308-3318, 2017.
Adith Swaminathan and Thorsten Joachims. Counterfactual Risk Minimization: Learning from Logged Bandit Feedback. In International Conference on Machine Learning, pp. 814-823, 2015.
Patrick Nadeem Ward, Ariella Smofsky, and Avishek Joey Bose. Improving exploration in soft- actor-critic with normalizing flows policies. arXiv preprint 190Xv:/900.00271,2215
Daan Wierstra, Tom Schaul, Jan Peters, and Juergen Schmidhuber. Natural Evolution Strategies. In Evolutionary omputation, 2008. CEC 2008. World Congress on Computational Intelli- gence), pp. 3381-3387. IEEE, 2008
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist Reinforcement Learning. Machine Learning, 8(3-4):229-256 1992.
13

---

Under review as a conference paper at ICLR 2020
A COMPUTING THE MODE OF THE SEARCH DISTRIBUTION
We prove here the fact that z denotes the location of the mode of the latent distribution Vus then gn (n) is a mode for Tw.n- Indeed, under reasonable smoothness assumptions, one has that y is mode for Tw.y if and only if:
( Or
0
(18)
y
Since (2) vn (kn) this is therefore equivalent to:
(x))
(z)
= 0
(19)
dr
Oz
1==b(1)
In the NICE model, we have that and its kernel is reduced to the null vector. Therefore:
(M)
1 for all æ hence the matrix (h,(x) de
is invertible
dx
(z)
(20)
Oz
1=
and therefore μ (y) by definition μ (the only critical point of vw). Hence since hyj" In have that y - (1) which concludes the proof.
B ALGORITHM PSEUDO-CODE
We provide below the pseudo-code for the generic algorithm GNN-A-ES, where is generic ES algorithm operating on a parametric distribution us. The additional hyper-parameters are the horizon I well as the clipping constant e. The function clip(x, lb, ub) clips the input æ between lower-bound ib and an upper-bound ub.
Algorithm 2: GNN-A-ES (ex: GNN-xNES, GNN-CMA-ES)
inputs
objective function f. distribution V. and its related ES algorithm A clipping constant e, NICE model architecture, initial parameters wo, initial weights 7Jo. horizon T, population size X
hyper-parameters:
(Initialization)
Initialize NICE MLPs weights and biases with TJo-
Let H be circular buffer of length T' x A
while not terminate do (Sampling)
Sample Z (2 2x} lid
Vus
iid Tun
Apply fn. to Z, obtain X = fa1.... xx)
~
Evaluate = [f())..... (xx)}.
Let H t- H + P, Fwnmn (ES update)
//One step ES-based optimi zation of the latent space Apply A to the latent distribution
W++1 + A A(w,, (Z,
(GNN update)*
//Many-steps gradient based aptimization of the GNN (m)e)((2) () (x)
M41 = " En,En clip Erew ((a) Enen a(a) - E), Tup-r (x) Eren ((a) (1 + }
end
'The (GNN iteration) step can be performed with virtually any gradient descent solver. all our experiments, used Adam (Kingma & Ba 2014) with learning rate 1e-4 for 500 epochs.
14

---

Under review as a conference paper at ICLR 2020
Algorithm 2 does not detail the mode- preservvigeeeg addition for the sake of readability and clarity. We provide additional details on this procedure here. Let ft be the mode of the latent distribution V... At the (Initialiiattin)) step, ogg 9yu (Ma) where 9,(-) is the push-forward map the NICE model described in Section 3.2 For all round f. 2 1, let (2) = It
97 (14) + og- The variable or represent the push forward mapping of the latent distribution mean under the current model. Every time the latent space is updated the (ES update) step, let ax+1 = fn. (P(41). Then, for the (GNN update), optimize the forward-map fn(2)) = 9n(=) 9n (M(+1) + 0'++1. After this update, we have 4 (H++1) 0t++1 = fz (p4+1), which means that the mode of the search distribution (which is the image of the latent distribution mode) has not been impacted by the GNN update.
C EXPERIMENTAL DETAILS
C.I HYPER-PARAMETER
Baselines We use xNES with its default (adapted) param-passesters (described in Wierstra et al. 2008)) for both its basclines versions and its inner optimization parts in GNN-xNES. The popu- lation size À is one such hyper-parameters, and is therefore set to = + [3 log(d)]- Also, as it is classically done in ES algorithms,
rank-based fitness shaping, designed to make the algorithm invariant with respect to order-preserving cost transformations. We use the same fitness- shaping function as in Wierstra al. (2008).
Across all experiments, tuning for each tasks. We use three coupling layers, each with a single hidden layer MLP with 128 hidden neurons and Leaky ReLU activations. The MLPs are initialized via Glorot initialization, and the clipping constant is set to & = 0.05. The history size T was determined experimentally, and set T [3 * (1 log(d))]. When restarts are used, this history size is divided by the numbers of restart so far (as the population size grows larger).
GNN-ES
the same Syper-parametert for GNN-xNES without fine
C.2 SYNTHETIC ORJECTIVES
Every synthetic objective we used in this work was taken from the BBOB2019 benchmark dataset. Their expression as well as additional details on the framework can be found Haansen et al. (2010) 2016). At the beginning of each experiment, we set the Gaussian search distribution (for xNES) and the Gaussian latent distribution (for GNN-XNES) to standard normal, with a mean uniformly sampled within the compact X' of interest (defined by the COCO framework).
C.3 RL ENVIRONMENTS
Table D provides details on the RL environment used compare GNN-XNES and xNES, like the dimensions of the state space S and action space A, the number dl of the policy's 's degrees of freedom and the maximum number of steps m per trajectory. At the beginning of each experiment, Gaussian search distribution (for xNES) and the Gaussian latent distribution (for GNN-XNES) to standard normal with zero mean. In this particular case, where the function evaluations are noisy, we kept the default population size of the xNES algorithm.
set the
Name Swimmer-vi InvertedDoubieeendluu--
S
A
d
13
2
28
1000
11
12
1000
HalfCheetah-vl
20
126
1000
Table 1: Reinforcement Learning environments
D TWO-DIMENSIONAL VISUALIZATIONS
We provide in Figure 3 additional wwo-dimensional visualizations of the behavior of GNN-XNES, on the Rosenbrock, Rastrigin, Beale and Bent-Cigar functions. We that the NICE distributions can
15

---

Under review as a conference paper at ICLR 2020
(d) (Doubly asymmetrie)
(a) Rosenbrock, global op- (b) Rastrigin, global opti- (c) Beale, global optimum Bent Cigar. global opti- timum at (1,1)
mum at (0,0)
at (3, 0.5)
mum at (0,0)
Figure 8: Two-dimensional visualizations. The black dotted lines represent the isolines of the level curves of a NICE search distribution trained with GNN-xNES.
Algorithm xNES GNN-XNES
mean(# restarts), d=2 mean(# restarts), d=5
mean(# restarts), d=10
2.3
2.7
3.4
1.3
2.5
2.9
Table 2: Mean number of restarts needed to discover the global minimum on the Rastrigin function.
efficiently fit each optimization landscapes, without having to reduce its entropy like multivariate normal would.
E ADDITIONAL RESULTS
We present here some additional results on some unimodal and multimodal synthetic functions. Figure present ECDFs curve obtained from the Attractive Sector function, highly asymmetrical function around its global minimum. such a function, GNN-xNES seems accelerate xNES in small dimensions, however this speed-up disappears in higher dimensions. Figure I0 presents results on the Rosenbrock function (without random rotations). Again, GNN-xNES accelerates the xNES algorithm. Figure 11 present results the multimodal functions Gallagher's 's Gaussian 101 Peaks and Gallagher's ' Gaussian 21 Peaks. Again, GNN-XNES discovers the global minimum faster (on average) than xNES.
In our multimodal experiments, we used simulated restarts as fair mean of comparing different algorithm (this is common practice in order to fairly compare algorithms that converge fast to poten- tially bad local minima to algorithms that converge slowly to the global minimum). If the empirical results prove that GNN-xNES accelerate xNES the discovery of the global minimum, it does not prove that GNN-XNES leverages the flexibility of the GNN to detect the global minimum when xNES misses it. In an attempt to prove that indeed the case, we report in Table 2 the number of restarts needed by both GNN-xNES and xNES to discover the global minimum on the Rastrigin function (averaged over the 15 randomly initialized run). For this instance, GNN-XNES consistently discovers the global minimum with less restarts than xNES.
As detailed Section one can apply Algorithm as a plug-in to any ES method. far, we empirically evaluated the benefits of our approach by comparing xNES against its GNN extension (GNN-xNES). We present in Figure 12 additional evaluations obtained by comparing CMA-ES and its GNN extension (denoted GNN-CMA-ES) on the Rosenbrock function in dimension 2,5 and 10. CMA-ES is considered to be the state-of-the-an ES algorithm, and improving its performances is non-trivial task. On the considered example GNN-CMA-ES improves CMA-ES, highlighting the empirical benefit of our approach for a large class of ES algorithm. One can however observe that the performance boost brought by the GNN extension is milder for GNN-CMA-ES then for GNN- xNES. We suspect that this is due to the use of cumulation via an evolution path in CMA-ES which basically introduces momentum -ike update when optimizing the latent distribution. While using an evolution path makes a lot of sense when optimizing stationary objective, it can be quite harmful for non-stationary ones. We therefore believe that the cumulation step in CMA-ES (for the latent distribution) and the GNN optimization (making the objective optimized by CMA-ES in the
We used the PyCMA library (ansen al. 2019 for these experiments.
16

---

Under review as a conference paper at ICLR 2020
1.
freettin of Smonter SUNNe
0.5
3766 revilustions
2764
evallaaionn
evalluatios
(a) Attractive Sector, d=2
(b) Attractive Sector, d=5
(c) Attractive Sector, d=10
Figure ECDFs curve for the Attractive Sector function, d=2,5,10
0.-
Pection of prok
xnes
Knes
xre5 xnes
160
202
470
702
250
500
750
1000
1256
3155
2000
(a) Rosenbrock, d=2
(b) Rosenbrock, d=S
(c) Rosenbrock, d=10
Figure 10: ECDFs curve for the Rosenbrock function, d=2,5,10
latent space non-stationary) can lead to conflicting updates and might hinder the benefits brought by the GNN's additional flexibility. Designing GNN update strategy complying with the use of evolution paths could therefore be a way of further improving GNN-CMA-ES, and is left for future work.
F ABLATION STUDY
We present here an ablation study for two additional tools that we introduced after the alternating optimization view: the mode preserving (16) extension as well as the history augmentation (15). Figure 1 presents ECDFs curves the Rosenbrock, Rotated Rosenbrock and Bent Cigar functions in 2D, for a version of GNN-xNES that doesn't use history but only the current population. Using history and therefore exposing the GNN larger datasets improves the procedure. Figure[1]]ress similar results on version of GNN-xNES without the mode preserving property (16). Again, one can notice that ensuring that the GNN training is mode-preserving is crucial improve experimental results.
gnn. Xi
qAn XnOS
J00
201
200
dimanttion
(a) Gallagher's Gaussian 101 Peaks
(b) Gallagher's Gaussian Peaks
Figure 11: Scaling comparison of GNN-xNES and xNES on the Gallagher's Gaussian 101 Peaks and Gallagher's Gaussian 21 Peaks functions, d=2,5,10.
17

---

Under review as a conference paper at ICLR 2020
+ grin amaes
Stedion of prosium JOOVE2
gin,, Lcmaas
gtin,
0.6
044
0.4
536 360 1207 1400
1807
5000
wwwuation
*sosustions
(a) Rosenhrock, d=2
(b) Rosenbrock, d=5
(c) Rosenbrock, d=10
Figure 12: ECDFs curves for the Rosenbrock function, (d=2,5,10) comparing the CMA-ES and GNN-CMA-ES
Deedtin of proteer saweed
3785
Xniss
XIIES
02
gnn, ATnSS
ATeL
hittoyy
100
300
363
600
300
100
T08
500
U00
2002
265
(a) Rosenbrock, d=2
(b) Rotated Rosenbrock, d=2
(c) Bent Cigar, d=2
Figure 13: ECDFs curves for xNES, GNN-xNES and GNN-XNES-no-histone for which the history size T 1. Using past populations to estimate expectations improves the optimization.
Peciona of proteem sctved
Xnes
xnes
pAn mp
gan mp
onn Xnos
03
181
300
191 evaluazions
cin
s00
216
460
606
600
1068
503
1006 1500 2008 2500 2008 2500 4068
Rosenbrock, d=2
(b) Rotated Rosenbrock. d=2
(c) Bent Cigar, d=2
Figure 14: ECDFs curves for xNES, GNN-xNES and GNN-XNES- -am.. which is not mode pre- serving. Ensuring that the training of the GNN doesn't impact the mode of the search distribution improves the optimization.
18


Reviews:
[{"review_id": "rkgmrg-iFr", "reviewer": "AnonReviewer2", "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": "Review of “Improving Evolutionary Strategies with Generative Neural Networks”\n\nTypically in ES, the distribution of solution candidates come from a hand-engineered distribution (i.e. multivariate Gaussian, or other parametrized distributions). In place of hand-engineered distribution choices, they introduce the use of GANs as a tool for Evolution Strategies. I liked the novelty of combining the use of GANs in new directions (namely ES/GA).\n\nThe core idea is to model the density function using Generative Neural Networks (GNN, MacKay 1995), and find the parameters of this GNN using tools from the normalizing flows literature for their NICE invertible properties (okay pun intended :) along with GAN-style training using historical data from the ES process.\n\nThey demonstrate their method on traditional blackbox optimization toy tasks (such as Rosenbrok and Rastrigin functions), and also on a few continuous control RL benchmark tasks, to demonstrate improved performance over a strong representative ES algorithm (XNES).\n\nOverall, I liked the work as it provides a fresh way of using GANs with another subfield (ES/GA). If they want to improve the work, I would suggest demonstrating that their approach can solve certain difficult tasks that traditional ES methods (or RL methods) cannot solve. Although the experiments chosen are not difficult ones, I believe they were chosen for clarity to showcase the method, so I think that is fine (in case there are complaints that they experiments are too simple).\n\n(For the record, I was looking to give a score of 7, but the ICLR system made me choose between 6 and 8, and I chose 8.)", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper."}, "extra_text": {}}, {"review_id": "SJg32RMstH", "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": "Summary: In ES the goal is to find a distribution pi_theta(x) such that the expected value of f(x) under this distribution is high. This can be optimized with REINFORCE or with more sophisticated methods based on the natural gradient. The functional form of pi_theta is almost always a Gaussian, but this isn't sufficiently flexible (e.g. multi-modal) to provide a good optimization algorithm. In response, the authors advocate for using a flexible family of generative neural networks for pi_theta. Using NICE as a generative model is desirable because it maintains volumes. This means that we can adjust volumes in latent space and this directly corresponds to volumes in x space. Doing so is useful to be able to tune how concentrated the search distribution is and to explicitly reason about the mode of the search distribution.\n\nOverall, I found that there were a number of technical details that were well motivated, such as how to leverage the 'mode preservation' of NICE, how to use importance sampling to be able to use samples from multiple rounds of optimization when updating theta and the fact that any existing ES algorithm can be used to do the optimization in the latent space. \n\n\n\n\"We found that the PGES algorithm (naive stochastic gradient descent of (8) with the score-function estimator) applied to the NICE distribution suffers from the same limitations as when applied to the Gaussian; it is inable to precisely locate any local minimum.\" \n   I don't understand this. Can't the Gaussian become very concentrated?\n \nYou write: \"ES implicitly balance the need for exploration and exploitation of the optimization landscape. The exploitation phase consists in updating the search distribution, and exploration happens when samples are drawn from the search distribution’s tails.\"\nThis is a weak form of exploration, since there is no explicit mechanism that encourages f(x) to be evaluated at regions that it has never been evaluated on before. The search distribution's tails will have low probability mass, so exploration unlikely. Your proposed method uses a pi(x) that is flexible enough to represent multi-modal distributions. However, how can you ensure that your search procedure actually uses this flexibility? In other words, how is your proposed method any better at exploration that the baseline ES method?\n\nIt would be great to have a slightly more detailed alg. box in the main text for your proposed method, instead of having it in the appendix. Some details I found confusing, such as whether you perform one step of alternating optimization per call to f(x) or if you perform many steps of alternating optimization.\n\nYour \"Mode preserving properties\" trick is cool. However, I don't fully understand how it is used. Surely you need to be able to be able to change the mode of the distribution some time? Do you only use the mode preservation trick at certain optimization steps? Again, incorporating this in the alg box would be helpful.\n\nIn the results, I was disappointed that you required restart strategies. I thought that one of the key advantages of using NICE was that you could capture a multi-modal search distribution. Can you explain?\n\n What do you mean by the 'global volume of the distribution?' What is the volume of a distribution? I understand what concept you're trying to convey, but can you be more precise?\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "BkljioPaFB", "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": "Summary:\n\nAs the title of the paper states, this paper tries to improve evolution strategies (ES) using a generative neural network. In the standard ES candidate solution is generated from a multivariate normal distribution, where the parameters of the distribution are adapted during the optimization process. The authors claim that the gaussian distribution, i.e., the ellipsoidal shape of the sampling distribution, is not adequate for the objective functions such as multimodal functions or functions with curved ridge levelsets such as the well-known Rosenbrock functions. The motivation is clearly stated. The technique is interesting and non-trivial. However, the experimental results are not very convincing to conclude that the proposed approach achieves the stated goal. Moreover, this paper may fit more to optimization conferences such as GECCO. \n\nBecause of the empirical results, I would rate this paper as the border line (around 5), but due to the slightly annoying rating system the rate appears as 6. \n\nComments:\n\nP2: \"Efficient Natural Evolutionary Strategies (xNES) (Sun et al., 2009) has been shown to reach state- of-the-art performances on a large ES benchmark.\" \n\nThis algorithm is \"eNES\" and  this algorithm is not competitive with the state-of-the-art ES such as CMA-ES. The authors might want to refer to exponential NES, which is xNES, proposed by Glasmachers et al 2010.\n\nP5: \"Indeed, other bijective GNN models like the Real-NVP (Dinh et al., 2016) introduce non-volume preserving transformations, which can easily overfit and lead to premature concentration and convergence.\" Has it been reported in a reference? If so provide the reference. If not, the authors should state that it has been observed the authors preliminary study. In any case, I think it depends how the model is used or trained, and this statement itself is not universally true.\n\nP7: \"By using fη instead of gη as the push-forward map of the NICE model, we ensure that the flexibility brought by the GNN only impacts the tails of the search distribution. As detailed in an ablation study presented in Appendix F, this additional tool turns out to be essential in order to use GNNs for ES.\"\n\nI barely understood this point. Please make is clearer.\n\nP8: Experimental results are not very convincing. The experiments are limited to dimension 2, 5, 10 and only a few functions are selected from the BBOB test function suite. How about on 20D? What happens if the target is 1e-8, which is the default setting in BBOB? \n\nFigure 3 looks interesting, and this is what the authors are trying to achieve. Therefore, it looks like the authors reached the stated objective. However, this is only 2D. No results are provided to convince that the proposed strategy achieved the stated objective. \n\nFigure 4  simply looks that the proposed algorithm failed to reach the \"flexibility\" stated in Section 2: \"Another limitation of classical search distribution is their inability to follow multiple hypothesis, that is to explore at the same time different local minima. Even if mixture models can show such flexibility, hyper-parameters like the number of mixtures have optimal values that are impossible to guess a priori.\"\n\nFrom these results, I am not convinced that the proposed strategy really achieved more flexible distribution than the classical methods, and whether the flexibility contributes to improve the performance. \n\nAnother critical point to be discussed is its usefulness. Since this algorithm is proposed to \"improve evolution strategy\" as a black-box optimizer (not for specific tasks), I expect to improve the state-of-the-art performance. Are the reported results outperform the CMA-ES? Based on Glasmachers et al (2010), xNES tends to require more objective function evaluations than CMA-ES, especially for higher dimensional cases. I am curious to know if the proposed approach outperforms the CMA-ES on Rosenbrock functions. \n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Evolutionary strategies are a popular class of method for black-box gradient-free optimization and involve iteratively fitting a distribution from which to sample promising input candidates to evaluate.  CMA-ES involves fitting a Gaussian distribution and has achieved state-of-the-art performance on a variety of black-box optimization benchmarks when the underlying function is cheap to evaluate.  In this work the authors replace this distribution instead with a much more flexible deep generative model (i.e. NICE). They demonstrate empirically that this method is effective on a number of synthetic global optimization benchmarks (e.g. Rosenbrock) and three direct policy search reinforcement learning problems.  The reviewers all believe the paper is above borderline for acceptance.  However, two of the reviewers said they were on the low end of their respective scores (i.e. one wanted to give a 5 instead of a 6 and another a 7 instead of 8.)  A major issue among the reviewers was the experiments, which they noted were simple and not very convincing (with one reviewer disagreeing).  The synthetic global optimization problems do seem somewhat simple.  In the RL problems, it's not obvious that the proposed method is statistically significantly better, i.e. the error bars are overlapping considerably.   Thus the recommendation is to reject.  Hopefully stronger experiments and incorporating the reviewer comments in the manuscript will make this a stronger paper for a future conference.
Decision: Reject