Improving Gradient Estimation in Evolutionary Strategies With Past Descent Directions
Authors: Florian Meier
Asier Mujika
Marcelo Gauy
Angelika Steger
Venue:  (2020)
Keywords: Evolutionary Strategies
Surrogate Gradients

Abstract: We propose a novel method to optimally incorporate surrogate gradient information.  Our approach, unlike previous work, needs no information about the quality of the surrogate gradients and is always guaranteed to find a descent direction that is better than the surrogate gradient. This allows to iteratively use the  previous gradient estimate as surrogate gradient for the current search point. We theoretically prove that this yields fast convergence  to the true gradient for linear functions and show under simplifying assumptions that it significantly improves gradient estimates for general functions. Finally, we evaluate our approach empirically on MNIST and reinforcement learning tasks and show that it considerably improves  the gradient estimation of ES at no  extra computational cost.

Under review as a conference paper at ICLR 2020
IMPROVING GRADIENT ESTIMATION IN EVOLUTION- ARY STRATEGIES WITH PAST DESCENT DIRECTIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Evolutionary Strategies (ES) are known to be an effective black-box optimization technique for deep neural networks when the true gradients cannot be computed, such as in Reinforcement Learning. We continue recent line research that uses surrogate gradients to improve the gradient estimation of ES. We propose novel method to optimally incorporate surrogate gradient information. Our approach, unlike previous work, needs information about the quality of the surrogate gradients and is always guaranteed to find a descent direction that is better than the surrogate gradient. This allows to iteratively use the previous gradient estimate as surrogate gradient for the current search point. We theoretically prove that this yields fast convergence the true gradient for linear functions and show under simplifying assumptions that it significantly improves gradient estimates for general functions. Finally, we evaluate our approach empirically on MNIST and reinforcement learning tasks and show that it considerably improves the gradient estimation of ES no extra computational cost.
INTRODUCTION
Evolutionary Strategies (ES) 2 are a black-box optimization technique, that estimate the gradi- ent of some objective function with respect to the parameters by evaluating parameter perturbations random directions. The benefits of using ES Reinforcement Learning (RL. were exhibited in 4 ES approaches highly parallelizable and account for robust learning, while having decent data-efficiency. Moreover, black-box optimization techniques like ES do not require propagation of gradients, are tolerant to long time horizons, and do suffer from sparse reward distributions (4). This lead to a successful application of ES in variety of different RL settings (5 7 g) Applications of ES outside RL include for example meta learning (9).
In many scenarios, the true gradient is impossible to compute, however surrogate gradients are available. Here, not equal to the true gradient, e.g. they might be biased or unbiased approximations of the gradient. Such scenarios include models with discrete stochastic variables (10), learned models in RL like Q-learning (II), truncated backpropagation through time (12) and feedback alignment (13), see (14) for detailed exhibition. If surrogate gradients are available, it beneficial to preferentially sample parameter perturbations from the subspace defined by these directions (14). The proposed algo- rithm (14) requires knowing in advance the quality of the surrogate gradient, does not always provide descent direction that is better than the surrogate gradient, and it remains open how to obtain such surrogate gradients in general settings.
the term surrogate gradients for directions that are correlated but usually
In deep learning in general, experimental evidence has established that higher order derivatives are usually "well behaved", in which case gradients of consecutive parameter updates correlate and applying momentum speeds up convergence (15) [7). These observations suggest that past update directions are promising candidates for surrogate gradients.
In this work, extend the line of research of (14). Our contribution is threefold:
First, we show theoretically how to optimally combine the surrogate gradient directions with random search directions. More precisely, approach computes the direction of the subspace spanned by the evaluated search directions that is most aligned with the true gradient. Our gradient estimator does not need know the quality of the surrogate gradients

---

Under review as a conference paper at ICLR 2020
and always provides descent direction that is more aligned with the true gradient than the surrogate gradient.
Second, above properties of our gradient estimator allow us iteratively use the last update direction as a surrogate gradient for our gradient estimator. Repeatedly using the last update direction as a surrogate gradient will aggregate information about the gradient over time and results in improved gradient estimates. In order to demonstrate how the gradient estimate improves over time, we prove fast convergence to the true gradient for linear functions and show, that under simplifying assumptions, it offers an improvement over ES that depends on the Hessian for general funcction.
Third, validate experimentally that these results transfer practice, that is, the proposed approach computes more accurate gradients than standard ES. We observe that our algorithm considerably improves gradient estimation on the MNIST task compared to standard ES and that it improves convergence speed and performance on the tested Roboschool reinforcement learning environments.
RELATED WORK
Evolutionary strategies I 2 3) are black box optimization techniques that approximate the gradient by sampling finite differences in random directions in parameter space. Promising potential of ES for the optimization of neural networks used for RL was demonstrated in (4). They showed that ES gives rise to efficient training despite the noisy gradient estimates that are generated from a much smaller number of samples than the dimensionality of parameter space. This placed ES prominent spot
in the RI. tool kit (5 77.). 8).
The history of descent directions was previously used to adapt the search distribution in covariance matrix adaptation ES (CMA-ES) (8) CMA-ES constructs a second-order model of the underlying objective function and samples search directions and adapts step size according it. However, maintaining the full covariance matrix makes the algorithm quadratic in the number of parameters, and thus impractical for high-dimenssonal spaces. Linear time approximations of CMA-ES like diagonal approximations of the covariance matrix (I9) often do not work well, in the sense that their gradient estimates do not converge to the true gradient even if the true gradient does not change over time. Our approach differs as we simply improve the gradient estimation and then feed the gradient estimate to a first-order optimization algorithm.
Our work is inspired by the line of research of (14), where surrogate gradient directions are used to improve gradient estimations by "elongating' the search space along these directions. That approach has two shortcomings. First, the bias of the surrogate gradients needs to be known to adapt the covariance matrix. Second, once the bias of the surrogate gradient is too small, the algorithm will not find a better descent direction than the surrogate gradient.
Another related area of research investigates how to use momentum for the optimization of deep neural networks. Applying different kinds of momentum has become one of the standard tools in current deep learning and it has been shown to speed-up learning in a very wide range of tasks (20: 16 17). This hints, that for many problems the higher-order terms in deep learning models and thus, the gradients do not change too drastically after parameter updates. While these approaches use momentum for parameter updates, our approach can be seen as form of momentum when sampling directions from the search space of ES.
are "well-behaved"
3 GRADIENT ESTIMATION
We aim at minimizing a function f R" - E by steepest descent. In scenarios where the gradient ff does not exist is inefficient to compute, we interested in obtaining some estimate of the (smoothed) gradient of ff that provides a good parameter update direction.
3.1 THE ES GRADIENT ESTIMATOR
ES considers the function fo that is obtained by Gaussian smoothing
(0) E + σς)),
2

---

Under review as a conference paper at ICLR 2020
where a is parameter modulating the size of the smoothing area and (0. is the n-dimensiioal Gaussian distribution with being the all 0 vector and being the n--dimensional identity matrix. The gradient of fo with respect to parameters 9 is given by
ff - Bow lf oe)e],
which can be sampled by a Monte Carlo estimator, see (5). Often antithetic sampling used, as reduces variance ( The antithetic ES gradient estimator using P samples is given by
Σ (1(0 ac.) - -(1 -(0)= c',
DES = 2
where e' are independently sampled from (o,,T) for (1..... ......,P) P}. This gradient estimator has been shown to be effective in RL settings (4).
3.2 OUR ONE STEP GRADIENT ESTIMATOR
We first give some intuition before presenting our gradient estimator formally, Given one surrogate gradient direction our step gradient estimator applies the following sampling strategy. First, estimates how much the gradient points into the direction of by antithetically evaluating f in the direction of Ç. Second, estimates the part of v / that orthogonal Ç by evaluating random, pairwise orthogonal search directions that are orthogonal to Ç. In this way, our estimator detects the optimal lengths of the parameter update step into both the surrogate direction and the evaluated orthogonal directions (c.g. if and f are parallel, the update step is parallel to Ç. and if they are orthogonal the step into direction Ç has length 0). Additionally, if the surrogate direction and the gradient are not perfectly aligned, then the gradient estimate almost surely improves over the surrogate direction due the contribution from the evaluated directions orthogonal to Ç. In the following we define our estimator formally and prove that the estimated direction possesses best possible alignment with the gradient that can achieved with our sampling scheme.
We assume that k pairwise orthogonal surrogate gradient directions ,h are given to our estimator. Denote by R₂ the subspace of R" that spanned by the Ç*. and by Riç the subspace that is orthogonal to RC. Further, for vectors and Vf, we denote by ê and f the normalized vector [ respectively. Let è", ,,..,,! be random orthogonal unit vectors from Riç. Then,
J. and zf
estimator is defined
f(0 7(0+00 o²*) f(O of o5)) 22
f(O + oē¹)
f(O f(0 oē¹)
91
20
20
We write = + Vfic. where Vficc and Vfic are the projections of f on I2, and Riç- respectively. In essence, the first sum in (2) computes Vflic by assessing the quality of each surrogate gradient direction, and the second sum estimates vfic similar to an orthogonalized antithetic ES gradient estimator, that samples directions from R Riç, see (5). We remark that we require pairwise orthogonal unit directions é' for the optimality proof. Due the orthogonality of the directions, no normalization factor like the 1 factor in ①1 is required in ( In practice, the dimensionality often much larger than Then, sampling pairwise orthogonal unit vecotrs e is nearly identical to sampling the e's from a (O, 1) distribution, because in high-dimensional space the norm of ~ (o, I) is highly concentrated around and the cosine of two such random vectors is highly concentrated around O.
For the sake of analysis, we assume that ff differentiable and that the second order approximation f(x e) se f(z) + (c, fz)))) e" Hx)e,, where Hxx) denotes the Hessian matrix of æ. is exact. This assumption implies that
f(0 + oē) -f(0 - - (V)()),
(3)
20
because the even terms cancel for antithetic sampling. The following proposition and theorems provide theoretical understanding, how our gradient estimation scheme improves gradient estimation
3

---

Under review as a conference paper at ICLR 2020
in this smooth, noise-free setting. In the following, we will omit the @ in Vf((). Our first proposition states that T1 computes the direction in the subspace spanned by s'...., 5" ...., c² that is most aligned with v.f.
be pairwise orthogonal vectors in IR. Then, 91 -i (VS, ( + Simi ('), computes the projection of V on the subspace spanned by Ç² ..... Sh ( ,,,,,... ,...,E.. Especially, 91 is the vector of that subspace that maximizes the cosine (V (EE) between f and e. Moreover, the squared cosine between I1 and 7 is given by
Proposition 1 (Optimality of g1). ). Let Ct.
k
k -E + Eiar,e
P
(VI )²
(4)
We remark that when evaluating (Vf, o²) for arbitrary directions v², no information about search directions orthogonal to the subspace spanned by the r's obtained. Therefore, one can only hope for finding the best approximation of f lying within the subspace spanned by the v's. which is accomplished by g1. The proof of Proposition follows easily from the Cauchy-Sehwarr Schwarz inequality and is given in the appendix.
3.3 ITERATIVE GRADIENT ESTIMATION USING PAST DESCENT DIRECTIONS
Our gradient estimation algorithm iteratively applies the one step gradient estimator 9_ by using the gradient estimate of the last time step as surrogate direction for the current time step. Therefore, our algorithm relies on the assumption that gradients are correlated from one time step to the next. This
assumption is justified since it is one of the reasons momentum-baat based optimizers (I5) 16 I7
are
successful in deep learning. We also explicitly test this assumption experimentally, see Figure la
The quality of the gradient estimate at any time step, depends on the quality of the surrogate gradient, which might be restrained because (a) the previous gradient estimate might be very noisy, and (b) the gradient changes with parameter updates. Our algorithm efficiently tackles problem (a), since improves the gradient estimate over the surrogate gradient at any time step. In order theoretically quantify this, we first analyse the case where the gradient does not change with parameter updates, i.e. a linear function optimized. In this setting, we show that our algorithm needs a small factor more than n (dimension) samples to align with the true gradient, see Theorem [ which is close to optimal, because least n samples are required to determine the true gradient. Next, we incorporate problem (b) into our analysis by considering general, non- non-linear functions, for which the gradient changes with parameter updates. We show under some simplifying assumptions that, also in this case, our algorithm builds up an improved gradient estimate over time, see Theorem 2
We first need some notation. Denote by O, the search point, by V.+ v the gradient and by Se the parameter update step at time I, that is, 0,+1 02 + G. The iterative gradient estimation algorithm obtains the gradient estimate & by computing g. with the last update direction G--1 as surrogate gradient and P new random directions é Formally, let ef be pairwise orthogonal unit directions chosen uniformly from the unit sphere, that is, they are conditioned to be pairwise orthogonal and are marginally uniformly distributed. By defining e = E (V ēj and setting Ee gL.. we obtain
Se (V G- + V 8) (7 + (Vfa
(5)
1=1
where we used é = (et.12/1leal]) & = (vie, it = (vSz Then, Equation of Proposition Turrs into
(vf 2
(6)
The next theorem quantifies how fast the cosine between S and f converges 1, if fi does not change over time.
Theorem (Convergence rate for linear functions). Let &e be iteratively computed, as in Equation (5)
using the past update direction and P pairwise orthogonal random directions and let X, = (Vf. be the random variable that denotes the cosine between C. and 7 Sa at time f. Then, the expected
4

---

Under review as a conference paper at ICLR 2020
(1-1x7- x2-1) N-1- Moreover let >> 0 and define T to be the first point time with X? 2 It holds
drift of X2 is B[X? X2-11X1-1 It-1 (1
N - P
E
min 5)/6, In(1/6))
The first bound [[[]] < P while the second bound [T[]] < (1 + (o/6)) is tight for å close to 0 and follows by a variable drift theorem, see appendix. We remark that in smooth and noise-free setting, where one can sample the true directional derivative with Equation (3). a cosine squared 1 can be reached by sampling (1 - 8)NN random orthogonal directions, see Proposition 2 in the appendix. Since our algorithm evaluates
- و is tight for å close and follows by an additive drift theorem,
times more directions per time step, requires approximately min(1/ 1+ samples to reach the same alignment.
Naturally, the linear case is not the most interesting one, However, it is hard to rigorously analyse the case of general f. because Vf+- - fi-1 - and write Vir = a ft-1 1 + Vʃi where vf1 is orthogonal to / and has squared norm 1 oj. Then, the first term of (6) is equal to
unpredictable how the gradient V.fa differs from V Note that H where H is the Hessian matrix of f at 01-1. We define ar = (V fi-1)
(V = (a=(VSe-,,G))) (ati:)/((a(((-aaaa
+ +(V,),+ GVIL,
In the following. we assume that V.fi is direction orthogonal vft-1 chosen uniformly random. Though, this assumption is not entirely true, it allows to get a grasp on the approximate cosine that our estimator going to converge to.
Theorem 2. Let Sa be iteratively computed using the past update direction and P pairwise orthogonal random directions,
Equation (). and let X, (V . be the random variable that denotes the cosine between Çe and V at time Further, write ft = 04 ft-1 f where Z 04 2 0 and assume that 7 I has a random direction orthogonal to v ft-1- Choose &e according to Equation ( and define X, to be the cosine between I and &. Then,
D.INNN111 11--P1) N
P
P N-1
E[X = r4-1]= - + (1- 27
N
The last theorem implies that the evolution of the cosine depends heavily on the cosine a, between consecutive gradients. Let A I-
(1-a?) w=, (1- 22, w= > Then, the theorem implies that the drift
- = -1-1] is positive if 3t-1 S and negative otherwise. Thus, if ag would change over time, we would expect X, to converge to A.
The predicted alignement of the gradient estimate with the true gradient of Theorem 2 plotted in Figure [b] Though the assumptions of Theorem 2 are technically not true, the close of the theoretical prediction gives empirical evidence that the analysis captures the general behaviour of the gradient estimation process.
:ODO:explain comparison to practise plot:
4 EXPERIMENTS
In this section, we will empirically evaluate the performance of our gradient estimation scheme when combined with deep neural networks. Section 4.1] we show that it significantly improves gradient estimation for digit classifiers on MNIST. In Section 4.2, we suggest how to overcome issues that arise from function evaluation noise. Finally, Section 4.3 we evaluate our gradient estimation scheme on RI. environments and investigate further issues arising in this setting.
4.1 GRADIENT ESTIMATION AND PERFORMANCE ON MNIST
We observe that our approach significantly improves gradient estimation compared to standard ES. Figure shows that the key requisite of iterative gradient estimation scheme is satisfied during
5

---

Under review as a conference paper at ICLR 2020
44-
0.6
3.8
0.5
0b30l.ze value
0.6
1000
2000
30000
2002
5000
1000
2000
2002
4000
5002
parameter updabess
parameter updates
(a)
(b)
Figure 1: Improved gradient estimation. (a) The gradients before and after parameter update are highly correlated. The cosine between two consecutive gradients (blue line) and the cosine between two random vectors (green line) plotted. (b) A network is trained with parameter updates according to 9ES using SGD (blue line) and Adam (yellow line) as optimizers. At any step we compute our gradient estimate with four and the true gradient / with backpropagation. The plot shows that the ratio of the cosine between your and v and the cosine between JEs and / is always strictly larger than
training MNIST, that is, that gradients between consecutive parameter update steps are correlated. Figure Tb shows that our approach improves gradient estimation compared to ES during the whole training process and strongly improves it in the beginning of training, where consecutive gradients most correlated, see Figure Ia| We observe that our approach strongly outperforms ES convergence speed and reaches better final performance for all hyperparameters tested, see Figure and Table T
For these experiments, used fully connected neural network with two hidden layers with a tanh non-linearity and 1000 units each, to have a high dimensional model (~ 1.8 million parameters). For standard ES 128 random search directions evaluated each step. For our algorithm the previous gradient estimate and 126 random search directions are evaluated. We evaluated all directions on the same batch of images in order eliminate function evaluation noise and we resampled after every update step. We used small parameter perturbations (a 0.001). This is possible because no function evaluation noise is present and because the objective function is already differentiable and therefore no smoothing is required. We test both SGD and Adam optimizers with leamning rates in the range 100.5 10 100..... 10 10-3
Implementation details:
15.
25
2000
5000
2000
2000
3000
2.0
1.0
1000 2000
3002
4000
3000 2000
3000
4000
5000
3000 2000 3032 6000 3000
Figure 2: Performance of ES (red lines) and our algorithm (blue lines) on MNIST classification. The evolution of the training ligliiklidood is plotted for the best three learning rates found for ES when using the Adam optimizer (top) and SGD (bottom). Our algorithm uses the same learning rates and hyper-parameters as ES.

---

Under review as a conference paper at ICLR 2020
Table 1: Results on the MNIST digit classification task. We report the best loss and the number of steps until the training log-lik log-likelihood drops below 0.6, to observe the performance in the initial stages of learning. The values are for the best performing learning rate for each optimizer.
Optimizer
Steps until loss < 0.6
Best loss
ES Adam Ours + Adam
433
0.242
182
0.216
ES SGD
727
0.305
Ours + SGD
295
0.278
232
3.0
330
135
6:3
55
8.5
637
50
(a) Default ES
(b) Ours with one past sample
(c) Ours with four past samples
Figure 3: Using several past descent directions improves robustness to function evaluation noise. The plots show the performance MNIST digit classification task with (blue lines) and without (red lines) function evaluation noise. The noise created artificially by randomly permuting the fitness values of the evaluated search directions (see Equation 2 in 20% of parameter updates. The x-axis represents the number of proper (i.e. non-permuted) parameter updates. (a) Standard ES does not suffer from this. (b) Function evaluation noise heavily impairs learning for our iterative gradient estimation scheme when using one past update direction as surrogate gradient. (c) Using 4 past update directions as surrogate gradients makes our iterative gradient estimation scheme robust to function evaluation noise.
4.2 ROBUSTNESS TO FUNCTION EVALUATION NOISE
In practice, our iterative gradient estimation scheme may suffer from function evaluation noise because it builds good gradient estimates over several parameter update steps. Suppose that the past update direction is good descent direction but it performs poorly on the current batch used for evaluation due to randomness in the batch selection or network evaluation process. Then, this direction weighted lightly when computing the new update direction, see Equation [5] and therefore the information about this direction will be discarded. We empirically show, that our approach suffers heavily from this issue when artificially injecting noise in the function evaluation process, see Figure 3b). Figure 3c shows, that this issue can be resolved by using the last k update directions for our gradient estimator (see Equation 2}. In this case, a good direction is only discarded, when it performs poorly in & consecutive evaluation steps, which is very unlikely. We remark that the magnitude of the parameter updates naturally limits k. because the k-th last update direction is only useful is still correlated with the current gradient. Concretely, we found that using the last 4 parameters updates was extremely helpful for smaller learning rates, even in the absence of noise (see Figure 3c). However, did not offer advantage for larger learning rates.
4.3 ROBOTIC RL ENVIRONMENTS
For the next set of experiments, we evaluate our algorithm on three robotics tasks of the Roboschool environment: RoboschoolImverteeeenddduo Our approach outperforms ES in the pendulum task, and offers a small improvement over ES in the other two tasks, see Figure The improvement of our approach over standard ES is smaller on RL tasks than the MNIST task. Therefore, are also in RL correlated with the gradient. To test this, we kept track of the average difference between random perturbations and the direction given by our algorithm, after normalizing the rewards.
RoboschooHHallChhhtahhv and RoboschoolAmte
first empirically confirmed that past updated direction
7

---

Under review as a conference paper at ICLR 2020
We found that, the direction of our algorithm had average weight of 1.11 versus the 0.65 of random direction.
RL robotics tasks bring two additional major challenges compared to the MNIST task. First, exploration is crucial to escape local optima and find new solutions, and second, the function evaluation noise is huge due to each perturbation being tested only on single trajectory. Our proposed solution of robustness against function evaluation noise intertwines with the exploration issue. A rather small step size is necessary in order to use more past directions as surrogate gradients. However, exploration in ES is driven by large perturbation sizes and noisy optimization trajectories. We did not observe improvements when combining the approach of using several past directions with standard hyperparameter settings. We believe that an exhaustive empirical study can shed light onto the effect of our approach on exploration and may further improve the performance on RI. tasks. However, running extensive experiments for complex RL environment is computationally expensive.
Implementation details: We use most of the hhper--aramenn parameters from the OpenAl implementation - That is. two hidden layers of 256 units each and with a tanh non-linearity. Further, we use learning rate of 0.01, a perturbation standard deviation of o = 0.02 and the Adam optimizer, and we also apply fitness shaping (19). For standard ES 128 random perturbations are evaluated at each step. For our algorithm the previous gradient estimate and 126 random perturbations are evaluated. For the Ant and Cheetah environments, optima where they stay completely still, instead of running forward. As this happens for both, ES and our algorithm, we tweaked the environments in order to ensure that true solution the task is learned and not some some degenerate optima, we tweaked the environments in the following way. We remove the penalty for using electricity and finish the episode if the agent does not make any progress in a given amount of time. In this way, agents consistently escape the local minima. We use a tanh non- mon-linearity on the output of the network, which increased stability of training, as otherwise the output of the network would become very large without an electricity penalty.
observed with this setup, that agents often get stuck in local
2500
2000
2200
2000
100
1500
500
1000
3000
400
200
0
3000002
2500005
3000000
Figure 4: Performance of our algorithm (red line) and ES (blue line) on three different Roboschool tasks: Ant (left), Cheetah (center) and Pendulum (right). The plot shows the mean average reward over 9 repetitions as a function of time-steps (in thousands).
5 CONCLUSION
We proposed a gradient estimator that optimally incorporates surrogate gradient directions and random search directions, in the sense that it determines the direction with maximal cosine to the true gradient from the subspace of evaluated directions. Such a method has many applications as elucidated in (14). Importantly. our estimator does not require information about the quality of surrogate directions, which allows us to iteratively use past update directions as surrogate directions for our gradient estimator. We theoretically quantified the benefits of the proposed iterative gradient estimation scheme. Finally, we showed that our approach in combination with deep neural networks considerably improves the gradient estimation capabilities of ES, at extra computational cost. The results on MNIST indicate that the speed of the Evolutionary Strategies themselves, a key part in the current Reinforcement Learning toolbox, is greatly improved. Within Reinforcement Learning an out of the box application of our algorithm yields some improvements. The smaller improvement in RL compared to MNIST is likely due to the interaction of our approach and exploration that is essential in RL. We leave it to future work to explicitly add and study appropriate exploration strategies which might unlock the true potential of our approach in RL.
http:/tittuuhoooo htt.///////////ooooooooo///////o stwttiiggintttttiiiioi.iia es- starter
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
[i] Ingo Rechenherg. Evolution strategy: Optimization of technical systems by means of biological evolution. Fromman-Holzboog Stuttgart, 104:15-16, 1973.
[2] Hans-Paul Schwefel. Evolutionsstrategienn für die numerische optimierung. In Numerische Optimierung von Computer-Modelllen mittels der Evolutionsstrategie,, pages 123-176. Springer, 1977.
[3] Yurii Nesterov and Vladimir Spokoiny, Random gradient- minimization of convex functions. Foundations of Compulational Muthematics, 17(2):277-566 2017.
[4] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and llya Sutskever. Evolution strategies as scalable alternative to reinforcement learning. arXiv preprint arXiv: 03864, 2017.
[5] Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard E Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. arXiv preprint /804v: 02395, 2018.
[6] Xiaodong Cui, Wei Zhang, Zoltán Tüske, and Michael Picheny. Evolutionary stochastic gradient descent for optimization of deep neural networks. In Advances in neural information processing systems, pages 6048-6058, 2018.
[7] Rein Houthooft, Yuhua Chen, Phillip Isola, Bradly Stadie, Filip Wolski, OpenAl Jonathan Ho, and Pieter Abbeel. Evolved policy gradients. In Advances Neural Information Processing Systems, pages 5400-5409, 2018.
[8] David Ha and Jürgen Schmidhuber. Recurrent world models facilitate policy evolution. In Advances Neural Information Processing Systems, pages
2018.
[9] Luke Metz, Niru Maheswaranathan, Jeremy Nixon, Daniel Freeman, and Jascha Sohl-dickstein. Learned optimizers that outperform on wall-clock and validation loss. 2018.
[10] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint
2013.
[11] Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-292, 1992.
[12] David E Rumelhart, Geoffrey E Hinton, and Ronald Williams. Learning internal represen- tations by error propagation. Technical report, Californi Univ San Diego La Jolla Inst for Cognitive Science, 1985.
[13] Timothy P Lillicrap, Daniel Cownden, Douglas B Tweed, and Colin Akerman. Random feedback weights support learning in deep neural networks. arXiv preprint arXiv:1411.0247, 2014.
[14] Niru Maheswaranathan, Luke Metz, George Tucker, Dami Choi, and Jascha Sohl-Dickstein. Guided evolutionary strategies: augmenting random search with surrogate gradients. In Interna- tional Conference on Machine Learning, pages 4264 4273, 2019.
[15] Timothy Dozat. Incorporating nesterov momentum into adam. 2016.
[16] Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference machine leurning, pages 1139-1147, 2013.
[17] Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv preprint arXivv1609.04747, 2016.
[18] Nikolaus Hansen. The ema evolution strategy: A tutorial. arXiv preprint arXiv:1604.00772 2016.
[19] Daan Wierstra, Tom Schaul, Tobias Glasmachers, Yi Sun, Jan Peters, and Jürgen Schmidhuber. Natural evolution strategies. The Journal of Machine Learning Research, 15(1):949-99) 9809999900900 2014.

---

Under review as a conference paper at ICLR 2020
[20] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[21] Johannes Lengler and Angelika Steger. Drift analysis and evolutionary algorithms revisited. Combinatorics, Probability and Computing, 27(4):643-666, 2018.
A PROOF OF THEOREMS
In this Section we prove the theorems from the main paper rigorously.
A.1 PROOF OF PROPOSITION I
Note that for this theorem there is no distinction between the directions Ç³ and é For ease of notation, we denote <² s....., . ......., Ç by e e The theorem is a simple application of the Cauchy- E (Vf, E*) the projection of v on the subspace spanned by the e's, and let e = Σm are be vector in that subspace. Then, the Cauchy-Schware inequality implies
Schwarz inequality. Denote by fif
(vl.) = (Viiee)) s v fielllle]]
Equality holds if and only if e and fije' have the same direction, which is equivalent to Ogfour for some a > O. In particular, in this case the cosine squared between v f and cs
v flle 11 V
m
(vS.)}=
Σ E))
(8)
f|
A.2 EXPECTATION OF COSINE SQUARED OF RANDOM VECTORS FROM THE UNIT SPHERE
We need the following proposition for the proof's of Theorem and
Proposition 2. Let û be an N -ddiennsional unit vector, and let é² et.....,"" e be pairwise orthogonal vectors sampled uniformly from the N d-dimensional unit sphere, that they are marginally uniformly distributed and conditioned to be pairwise orthogonal. Then, the expected cosine squared of â and Ep EL,(,, e² is
P
(2, 2
N
Proof. Note that
P =
2
P
(ū, 2)2
|E|l2 (ū, e)²
Σ
20,
(2, 2012
Denote by S the N-dimensional unit sphere. Linearity of expectation implies that
(1, Σ E (ú, 24:2
P
(û, r) de
Vol(S)
10

---

Under review as a conference paper at ICLR 2020
By rotational invariance of the unit sphere, replace é by e1 (1, ...., 0) and obtain
/ 1)2
(ú, = Vol(S)
de
= Vol(S) / us du
P
N Σ i=1
P
de
N. Vol(S)
P
dd
N. Vol(s)
P
N
A.3 PROOF OF THEOREM 1I
In order to prove Theorem use Equation to compute how X2 (V depends on X²_1- Then, we apply variable transformation to X₂ in order to be able to apply the additive and variable drift theorems from (21) which are stated in Section B
We can split the normalized gradient f Vfiā. + Via into an orthogonal Č part and
a parallel to Ś part. holds V f يييي_ 1|2 = 1- (VV,, &1-1 and (Vf Et) = 0 since é is unit vector orthogonal to 1 Recall that Vs1c TB/
Vlic then
( (v_ia_ (1 -1- and therefore by Equation
= (1-
X (V -1-
(10)
Define the random process Y, = 1 - X². . holds
Y = -- (1 x2_ MVLLe, 21) Y-- (1-1(1((515))))) (() and
(11)
E E Y - V ( =v--1 Vv-1 (1 P
N N-1)
(12)
where used Proposition 2 in the N dimensional subspace that is orthogonal to G-11- In order to derive the first bound on T, we bound the drift of Y, for Y,
P
P
Y = 94-1,3t-1 8) -t-1 Vt-1 N -
< 91
8 -
where we used Equation 12 and 1/-1 2 In order apply Theorem we define the auxiliary
process Z, Y 5. Then, T is the expected time that Z, hits O. Since E Z 2111 21-1 S z1-1 8 _ and Zo = 1 5, Theorem 3 implies that
1-6N-1
E E
8
P
In order apply Theorem to show the second bound on T, we need to rescale Y, such that it takes values in {0} Define the auxiliary process Z, by
Ye/8
if Y, 2 8 Y
Z,
(13)
0
8
11

---

E N-I follows by Proposition and Under review as a conference paper at ICLR 2020
Then, T is the expected time that Z, hits 0. The process Z satisfies
2 21| 2-1 (1
P
E Zz 2- 2t 21
S R (Y/00/ 82 211 2
N N
where we used Equations
and
12
Since Zo = Theorem 4 Iimlles for h(2) N-1 that
1/6
+
du
P (1 (m11/(1)8))
P
Pu
A.4 PROOF OF THEOREM 2
In order prove the theorem, we need to understand how X, depends on the value of Xt-1.
holds X? (i + (VSe, Ex) As in Equation 12
we can write (v E,)²
& 4)) and note that TE((VII the definition of & This implies that
P E| (
P N
E((V
E
11 = 21-1 +
(14)
N N-1
To understand how the X, evolves we need to analyze how (V relates to X,-1 ( 2--1)2. To that end, we set ar = (v/,, V and write v = where Vlivi- is orthogonal to Vfr- and has norm - og. Then,
(0.12 (a, (a +ii =
It follows that
( x2-1]
(15)
= =a/=2-1 2 BlV
(16)
1
=0,27 + (1 (1- N
(17)
where we used B(( ((-1) random direction orthogonal to ft and that
which follows from the assumption of Vfivi- being
(il/iw/-...-1)) = ( v 1 & G-11
|BK AiLiii G--11960 }
=l f 11116--1111111
fire-ill [
= (1-a x7²
N -
which follows from
1- 1 1 I 11 2====111 x and Proposition for P=
using that Viivsi a random direction orthogonal to Vi-11. Then, plugging Equation (17) into implies the theorem.
B DRIFT THEOREMS
For the proof of Theorem we use two drift theorems from 21.. which we restate for completeness. Theorem 3 (Additive Drift, Theorem from (I)). Let (X.)teN be Markov chain with state space
C [0, oc) and assume X, = n. Let T be the earliest point in time I 2 O such that X, = 0. If there
exists c 0 such that for all S, x > 0 and for all we have
E[X x] < x cc
Then.
n
T
<
c
12

---

Under review as a conference paper at ICLR 2020
-20
-40
-40
-80
-50
-60
-120
0
250
500
750
1200
1250
1500
1750
2000
250
500
750
1000
1250
1500
1750
2000
(a)
(b)
Figure 5: Performance when optimizing quadratic function. Performances of approach (green), standard ES (blue) and SNES (red). (a) On small dimensional functions (N = 32 and 16 sampled directions per time step) SNES outperforms do not improve further because they do not adapt their stepsize. (b) For high dimensional functions (N 10000 and 16 sampled directions per time step), our approach outperforms SNES and standard ES.
approach and standard ES. Our approach and ES
Theorem 4. Variable Drift, Theorem from (2D) Let (Xt)ten be Markov chain with state space C {0} U (1, and with Xy = n. Let T be the earliest point in time 2 0 such that X, = Suppose furthermore that there is positive, increasing function h [0) - R>o such that for all r E S, x > 0 we have for all t
E[X++1|X, xx-)
Then,
' h(u)
E[T] < h(1)
du
C ADDITIONAL EXPERIMENTS
This section presents some additional experiments. We will incorporate a polished version this section into the experiments section of the main paper, for the camera ready version of the paper.
C.I COMPARISON OF OUR APPROACH TO SEPARABLE NES AND GUIDED ES
We consider the toy task of optimizing a quadratic function f(x) || as considered (14). Figure 5
approach to diagonal approximation of CMA-ES, that is, seperable natural ES (SNES) from (19). that has the same runtime and memory complexity as our approach. While SNES works verv well for small diminsional parameter space (N 32 see Figrue it is clearly outperformed by our approach for high dimensional paramater spaces ( N = 10000, see Figure 5b).
Further, we compare our one step gradient estimator I1 the guided-ES gradient estimator proposed in (14). Again the goal is to optimize quadratic function f(z) || Both estimators receive surrogate gradient Ç for the optimization. The surrogate gradient is created as (14): A normalized random bias (drawn once the beginning of optimization) and normalized noise direction (resampled at every iteration) are added the true gradient. that is, [(x) (z)++(+++++)))) vl (x))ll
Figure 6 shows that approach outperforms guided-ES no matter how the parameter controlling the bias variance trade-off of guided-ES is set.
Implementation details: For Figure 5b has dimension N 10000 and is initalized by sampling
Ho ~ NO, I). A is matrix of dimension 100 x 10000, and its entries are samples from (0 0.001) distribution, where the variance is chosen such that the initial loss is approx 1. For Figure Sa has dimension N 16 and A has dimension 16 x 16. The hyperparamters for our approach and standard ES are the learning rate 3 and perturbation size The hyperparamters for SNES are learning rate
13

---

Under review as a conference paper at ICLR 2020
0
-10
-2
-30
-40
-50
-60
-70
250
500
750
1000
1250
1500
1750
2000
Figure Optimizing quadratic function with biased surrogate gradients. Performances of our approach (green line), SGD using the surrugate gradient for the parameter update (purple line), ES (blue line), guided-ES (yellow line) are plotted. Our approach (green line) improves sharply, making use of the biased gradient, until it becomes useless (crossing with purple line). For guided-ES, we observed a binary behaviour when optimizing for parameter that controls the bias-variance trade-off analysed in (14). Either it follows the surrogate gradient very closely it behaves similarly to ES. This observation is consistent with the analysis conducted in (14). The optimal value that we found for this parameter is very close to 1 and results in performance very close ES (yellow and blue lines).
14

---

Under review as a conference paper at ICLR 2020
3, learning rate Bg for the step size adaptation and perturbation size initialization. We performed
hyperparameter search for all these hyperparameters and plotted the best performance.
15


Reviews:
[{"review_id": "SyxXZ-_0Fr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides a new type of gradient estimator that combines an Evolutionary Strategies (ES) style estimate (using function evaluations at perturbed parameters) along with surrogate gradient estimates (gradient estimates that may be biased and/or high variance). The estimator involves computing antithetic ES estimates in two subspaces: along the set of (normalized) surrogate gradients, and along a set of randomly chosen vectors in the orthogonal complement of the span of the surrogate gradients. The paper provides a proof of the optimality of the estimate, that is, the proposed gradient estimate maximizes the cosine of the angle with the true gradient over the vectors in the subspace defined by the set of surrogate gradients and sampled directions. The paper proposes an additional mechanism for generating surrogate gradients by simply using previous gradient estimates as surrogate gradients, and derives a convergence rate for when this iterative estimator will approximate a fixed, true gradient (e.g. for linear functions). Finally, the paper applies the estimate to two tasks: MNIST classification and robotic control via reinforcement learning, demonstrating improvements on both compared to standard ES.\n\nI think this is a nice contribution, and I enjoyed reading this paper, with one major caveat regarding some of the experiments. The paper is clearly written.\n\nMajor concerns:\n- The paper is missing critical comparisons to existing work. In particular, the paper cites Ref. 14 as another method for using surrogate gradients in optimization. For both examples (MNIST and RL), it is crucial to add the algorithm from that paper as a baseline.\n- In addition, it would also be nice to see one of the diagonal approximations of CMA-ES as a baseline.\n\nOther questions/comments:\n- For the MNIST example, you mentioned that the function is deterministic--how many examples are used for each function/gradient evaluation (the full dataset, or some fixed subset)?\n- It would be nice to see how the performance gap between the proposed estimate and ES varies with the number of parameters (size of the network).\n- It would be nice to compare the orthogonal epsilon to the N(0,I) epsilon case. As mentioned in the paper, the N(0,I) will be nearly orthogonal to the surrogate gradients in high dimensions. For a practical problem (e.g. MNIST), is the orthogonalization strictly necessary?\n\nMinor comments/typos:\n- Fig 2: Add label for the x- and y-axes, and a legend.\n- Use a more semantically meaningful subscript than `our` for the proposed gradient estimate. Perhaps `orth`, since you utilize orthogonal subspaces?\n- Typo in eq. (6) (issue with the subscript on f)\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SkgtRHvaFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper addresses the issue of noisy gradient estimation in a type of evolution strategies popularized by the open AI's reinforcement learning paper. It is a follow-up paper of reference [14], and try to analyze the optimality of the gradient estimation. The goal of the paper is well stated and well motivated. The paper itself is well-organized. However, the novelty of this work is not sufficiently high and its usefulness is questionable. \n\nTheorem 1 is trivial under the assumption stated above the theorem---the numerical approximation of the directional derivative admits the true directional derivative. In other words, the assumption is too strong to claim the goodness of the proposed scheme. \n\nLet's just sample k+P random normal vectors and orthogonalize and normalize them. Let them denoted by the same symbols hat zeta and hat epsilon. The theorem statements holds for this case. Therefore I failed to understand the essential claim of Theorem 1. \n\nAbout Theorem 2 and 3, again, the assumption that he numerical approximation of the directional derivative matches the true directional derivative is too strong to make the claim relevant. Moreover, the effect of P somehow disappear from the analysis. \n\nAll the analysis is done assuming the above mentioned strong assumption. However, in one of the experiments and the existing works, ranking based fitness shaping has been applied to make the algorithm robust. This replaces the function value differences in the gradient estimator with some predefined values depending on the ranking of f-values of each trial vector. This definitely violates the assumption, and it may result in some vector far away from the true gradient, yet the algorithm still works well. Therefore, the hypothesis underlying in this paper---better estimation of the gradient will lead to a better performance---may not be true. At least the numerical experiments provided in this paper do justify this hypothesis.\n\nThe numerical experiments have been conducted to compare the proposed algorithm with the baseline ES algorithm. In a sense it is reasonable to evaluate the effect of the proposed modification in the baseline ES. However, since the baseline ES algorithm is not really efficient on tasks such as the one conducted in Figure 2, the usefulness of the proposed approach is not tested. At least one should compare with the \"canonical\" ES, where the learning rate fixed and sigma is adapted. See https://arxiv.org/pdf/1802.08842.pdf. \n\nUse of the search history proposed in this paper is not really new in ES community. A sort of momentum terms appears in the standard CMA-ES [18] even in two parts of the algorithm and its effectiveness is well-studied empirically. This paper addresses the theoretical aspect of the momentum and this may be new. However, as mentioned above, the assumption is too strong to describe the reality.\n\n\"Linear time approximations of CMA-ES like diagonal approximations of the covariance matrix (19) often do not work well.\" Please specify in what sense the linear time version of the CMA-ES do not work well and provide the evidence (references). ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Ske0aL1AKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper is about improving the quality of surrogate gradients. Their proposal in guaranteed to find a descent direction. In addition to two results, the authors also provide experimental results.\n\nThis paper is presenting a research on a recent topic. Using random search methods or evolutionary strategies in machine learning problems is attracting quite an interest in the last years. However, this particular paper misses several important points and hence, lacks sufficient contribution. \n\nHere are my major comments:\n\n- The technical results are somewhat superficial: The first one is with the big assumption of linearity. This assumption does not hold almost for all problems where random search strategies would be of use. The second result, on the other hand, assumes orthogonality, which almost surely never happens. I must add that the authors also acknowledge the severity of these assumptions.\n\n- It is important to note that the theory here assumes that the gradient does exist but cannot be computed or too expensive to compute.\n\n- I would have expected an experimental study that would properly support the proposed approach. Such a study would have shed light on the computation time and efficiency. The authors solve MNIST problem, which can be quite efficiently solved with a variant of (accelerated) gradient method. Solving it with ES and then improving the result with the proposed approach is not satisfactory. Reinforcement learning experiments could have been noteworthy but the authors have solved quite small problems and did not compare their results extensively against contender approaches like augmented random search. It would have been also nice to see the computation times on large problems since the extensive computation time is a big obstacle for training in reinforcement learning.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose a novel approach to using surrogate gradient information in ES. Unlike previous approaches, their method always finds a descent direction that is better than the surrogate gradient. This allows them to use previous gradient estimates as the surrogate gradient. They prove results for the linear case and under simplifying assumptions that it extends beyond the linear case. Finally, they evaluate on MNIST and RL tasks and show improvements over ES.

After the revisions, reviewers were concerned about: 
* The strong (and potentially unrealistic) assumptions for the theorems. They felt that these assumptions trivialized the theorems.
* Limited experiments demonstrating advantages in situations where other more effective methods could be used. The performance on the RL tasks shows small gains compared to a vanilla ES approach. Thus, the usefulness of the approach is not clearly demonstrated. 

I think that the paper has the potential to be a strong submission if the authors can extend their experiments to more complex problems and demonstrate gains. At this time however, I recommend rejection.
Decision: Reject