Variance-Reduced Gradient Estimation via Noise-Reuse in Online Evolution Strategies
Authors: Oscar Li
James Harrison
Jascha Sohl-Dickstein
Virginia Smith
Luke Metz
Venue: NeurIPS 2023 poster (2023)
Keywords: Evolution Strategies
unrolled computation graph
online gradient estimation
variance reduction
stochastic gradient estimation
TL;DR: We propose a variance-reduced unbiased online evolutionary strategies method for gradient estimation in unrolled computation graphs.

Abstract: Unrolled computation graphs are prevalent throughout machine learning but present challenges to automatic differentiation (AD) gradient estimation methods when their loss functions exhibit extreme local sensitivtiy, discontinuity, or blackbox characteristics. In such scenarios, online evolution strategies methods are a more capable alternative, while being more parallelizable than vanilla evolution strategies (ES) by interleaving partial unrolls and gradient updates. In this work, we propose a general class of unbiased online evolution strategies methods. We analytically and empirically characterize the variance of this class of gradient estimators and identify the one with the least variance, which we term Noise-Reuse Evolution Strategies (NRES). Experimentally, we show NRES results in faster convergence than existing AD and ES methods in terms of wall-clock time and number of unroll steps across a variety of applications, including learning dynamical systems, meta-training learned optimizers, and reinforcement learning.

Variance-Reduced Gradient Estimation via Noise-Reuse in Online Evolution Strategies
Oscar Li James Harrison , Jascha Sohl-Dickstein o Virginia Smith Luke Metz
Machine Learning Department, School of Computer Science Carnegie Mellon University Google DeepMind
Abstract
Unrolled computation graphs prevalent throughout machine learning but present challenges to automatic differentiation (AD) gradient estimation methods when their loss functions exhibit extreme local sensitivtiy, discontinuity, blackbox characteristics. In such scenarios, online evolution strategies methods are a more capable alternative, while being more parallelizable than vanilla evolution strategies (ES) by interleaving partial unrolls and gradient updates. this work, we propose a general class of unbiased online evolution strategies methods. We analytically and empirically characterize the variance of this class of gradient estimators and identify the one with the least variance, which we term Noise- Reuse Evolution Strategies (NRES). Experimentally? than existing AD and ES methods in terms of wall-clock time and number of unroll steps across a variety of applications, including learning dynamical systems, meta-training learned optimizers, and reinforcement learning.
show NRES results in faster convergence
Introduction
First-order optimization methods are a foundational tool machine learning. With many such methods (e.g., SGD, Adam) available in existing software, ML training often amounts to specifying a computation graph of learnable parameters and computing some notion of gradients to pass into an off-the-shelf optimizer. Here, unrolled computation graphs (UCGs), where the same learnable parameters are repeatedly applied to transition a dynamical system's 's inner state, have found their use in various applications such as recurrent neural networks 212). meta-training learned optimizers
3
hyperpameter tuning 5 6) dataset distillation 7 g and reinforcement learning ( 10
While large number of automatic differentiation (AD) methods exist to estimate gradients in UCGs [T]. they often perform poorly over loss landscapes with extreme local sensitivity and cannot handle black-box computation dynamics or discontinuous losses
To handle these shortcomings, evolution strategies (ES) have become a popular alternative to produce gradient estimates in UCGs [14]. ES methods convolve the (potentially pathological or discontinuous) loss surface with a Gaussian distribution in the learnable parameter space, making it smoother and infinitely differentiable. Unfortunately, vanilla ES methods cannot be applied onling the computation must reach the end of the graph to produce a gradient update, thus incurring large update latency for long UCGs. To address this, recently proposed approach, Persistent Evolution Strategies [13] (PES), samples a new Gaussian noise in every truncation unroll and accumulates the past sampled noises to get rid of the estimation bias in its online application.
In this work, we investigate the coupling of the noise sampling frequency and the gradient estimation frequency in PES. By decoupling these two values, we arrive at a more general class of unbiased,
'Correspondence to: <oscarli cmu cdu.. "Now at OpenAl.
'Code available https:://githubb.. wttpeauwu.cmm//////eeeeee coom/Ocarcarr.in Liniose wtw.osoeReeuseeeiiiiiieeeeee Exvolution-Strateee
'Online here means method can produce gradient estimates using only truncation window of an unrolled computation graph instead of the full graph, thus allowing the interleaving of partial unrolls and gradient updates.
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

(a)
Learned Optimber T- 1000
(b)
0.626
method
online?
unbiased?
low variance?
T
8.625
FullES
0.624
TES 3 PES [1S
x
0.623
X
0.622
NRES (ours)
-1.0
0.5
0.0
0.5
1.0
Figure 1: (a) The pathological loss surface in the learned optimizer task (Sec. 5.2) along random e direction; such surfaces are common in UCGs but can make automatic differentiation methods unusable, leading to the recent development of evolution strategics methods. (b) Comparison of properties of different evolution strategies methods. Unlike prior online ES methods, NRES produces both unbiased and low-variance gradient estimates.
online ES gradient estimators. Through a variance characterization of these estimators, we find that the one which provably has the lowest variance in fact reuses the same noise for the entire time horizon (instead of over a single truncation window as in PES). We name this method Noise-Reuss Evolution Strategies (NRES). In addition to being simple to implement, NRES converges faster than PES across a wide variety of applications due to reduced variance. Overall, we make the following contributions:
We propose class of unbiased online evolution strategies gradient estimators for unrolled compu- tation graphs that generalize Persistent Evolution Strategies [5.]
We analytically and empirically characterize the variance of this class of estimators and identify the lowest-variance estimator which we name Noise-Reuse Evolution Strategies (NRES).
We identify the connection between NRES and the existing offline ES method FullES and show that NRES a better alternative to FullES both in terms of parallelizability and variance.
We demonstrate that NRES can provide optimization convergence speedups (up to 5-60x) over AD/ES baselines in terms of wall-clock time and number of unroll steps in applications of 1) learning dynamical systems, 2) meta- mneta-trainng learned optimizers, and 3) reinforcement learning.
2 Online Evolution Strategies: Background and Related Work
Problem setup. Unrolled computation graphs (UCGs) [5] are common in applications such as training recurrent neural networks, meta-training learned optimizers, and learning reinforcement learning policies, where the same set of parameters are repeatedly used to update the inner state of some system. We consider general UCGs where the inner state E IR is updated with learnable
f((s 0) for T time steps starting from an initial state 8p- At each time step / E (l...., T). . the state 8; incurs a loss T. (8)). As the loss I, depends on / applications of 0, we make this dependence more explicit with loss function L. : _dt + R and xx) = Ls(s: 5 We aim to minimize the average loss over all T
parameters O E Id through transition functions: {ff : R' x R + R'
T..
time steps unrolled under the same 6, ming [((0)T)) where
1 Σ Lo).....,,..)
L ④T)
(I)
Loss properties. Despite the existence of many automatic differentiation (AD) techniques to estimate gradients in UCGs (II], there are common scenarios where they are undesirable: 1) Loss surfaces with extreme local sensitiviy: With large number of unrolls in UCGs, the induced loss surface is prone to high degrees of sharpness and many suboptimal local minima (see Figure ID. This issue is particularly prevalent when the underlying dynamical system is chaotic under the parameter (0) of interest [13], e.g. in model-based control [12 and meta-learning ( In such cases, naively following the gradient may either a) fail converge under the normal range of learning rates (because of the confficting gradient directions) or b) converge to highly suboptimal solutions using a tuned, yet much smaller learning rate. 2) Black-box or discontinuous losses: As AD methods require defining a Jacobian- product (forward-movt
or a vector-Jacobian product (reverse-moud mode)) for every elementary operation in the computation graph, they cannot be applied when the UCG's inner dynamics are inaccessible (e-g., model-free reinforcement learning) or the loss objectives (e.g. accuracy) are piecewise constant (zero gradients).
Evolution Strategies. Due to the issues with AD methods described above, a common alternative is to use evolution strategies (ES) to estimate gradients. Here, the original loss function is convolved with an isotropic Gaussian distribution in the space of 8, resulting in infinitely differentiable loss
[0] xas a E Zzo denotes a copies of 0, example: L.(10 xa [0]] = L, 10,

---

(a)
Online Evolution Strategies Protocol
(b)
How different unbiased OES methods share noise?
Truncation window
Worker"
longth
PESWorker
Sample
Sample
Sample
Accumulated noise
Truncation window langth W
Le +
xp Worker
fN B++
S W
Sample
Rouse
Sample
Accumulated
Worker MV
K divides
NRESWarker
nead to
Sample
Rouse
Rouse
Horizon length
accumulate
(a) Illustration of step-unlocked online ES workers working independently at different truncation windows. Here central server sends # (whose gradient to be estimated) to each worker and receives the estimates over partial umrolls from each. The averaged gradient can then be used in first-order optimization algorithm. (b) Comparison of the noise sharing mechanisms of PES, GPESH, and NRES (ours). Unlike PES (and CPPSS=77) which samples new noise in every (some) truncation window and needs to accumulate the noise, NRES only samples noise once at the beginning of an episode and reuses the noise for the full episode.
Figure 2:
function with lower sharpness and fewer local minima than before (a 0 is hyperparameter);;
++ Ec- Laxa) L[ + e]xr).
An unbiased gradient estimator of is given by the likelihood ratio gradient estimator 16 1 L( dxxr)c. This estimator only requires the loss evaluation (hence is zeroth-order) but not an explicit computation of the gradient, thus being applicable in cases when the gradients noninformative (chaotic piecewise constant loss) not directly computable (black-hox loss). To reduce the variance, antithetic sampling is used and we call this estimator FullES (AlgorithmB)) Bin the Appendix):
FullES(O) -0t 1 (L.(0 + x)xx)))xxxx)))))))))))) L. <)xi)
The term Full highlights that this estimator can only produce gradient estimate after a full sequential unroll from t = to T. We call such a full unroll an episode following the reinforcement learning terminology. FullES can be parallelized [4 by averaging N parallel gradient estimates using i.i.d. e's, but is not online and can result in substantial latency between gradient updates when T is large.
Truncated Evolution Strategies. To make FullES online, Metz al. (3] take inspiration from truncated backpropagation through time (TBPTT) and propose the algorithm TES (see Algorithm 6 in the Appendix). Unlike the stateless estimator FullES, TES is stateful: TES starts from saved state (from the previous iteration) and draws a new e; for antithetic unrolling. To make itself online, TES only unrolls for a truncation window of W steps for every gradient estimate, thus reducing the latency from O(T) to O(W). Analytically,
W
(P)
[T [T=+<(00)>)11 + ((//W)1)))) T.++:((0)Kr, - ((r/W)+1]<)) ((7/W)+1 FCr/// (4)
20
1-- 2 (O the time step 7 which TES starts from is also a random variable drawn from the uniform distribution T Unif W....
Here, besides the Gaussian random variables e T/W
W) It is worth noting that Vicol al. [5] who also analyze online ES estimators do not take the view that the time step 7 an online ES estimator starts from is a random variable; as such their analyses do not fully reflect the "online" nature captured in work. When multiple online ES Workers (c.g., TES workers) run in parallel, different workers will work at different i.i.d. time steps T, (which we call rtep-unlocked workers) (see Figure 2 a)). We provide the pseudocode for creating step-unlocked workers and for general online ES learning in Algorithm and in the Appendix.
TES is a biased gradient estimator of (2). Note that in (4. only the 0's in the current length- W truncation window receive antithetic perturbations, thus ignoring the impact of the earlier 0's up to time step T. Due to this bias, optimization using TES typically doesn't converge to optimal solutions.
Persistent Evolution Strategies. To resolve the bias of TES, Vicol et al. [15] recognize that TES samples new noise in every truncation window and modifies the smoothing objective into:
0 + Bie,) L( + ei]xw,..., 10 er/w]
(5)
'The random variable t will always be sampled from this uniform distribution. In addition, we will assume the time horizon I' can be evenly divided into truncation windows of length W, i.e. T' = 0 (mod W).
3

---

Algorithm 1 Persistent Evolution Strategies
15
Algorithm 2 Noise- Reuse Evolution Strategics (ours)
class Wwo.kerrOOlinneSWorrrrooo
class WerSSWWrerOOOnnneeSWWrkee
def' init (self. W):
def init (self, W):
self.T = 0; self.s* = so; self.s self, W W; self. = 0 E Rd
self.T 0: self.s 80; self.s
self. W W
def' maadient.stimatt(sell.. 0):
def gradient.estimatc(ss if self.T == 0: # only sample at beginning
8):
sample at every truncation window
# this is 111 selfff += E now self. ET/W + f+/w41
c ~ of
c e~ e~N(00 o² ldxx)
self.E=
# reuse for this apisoda
(8 8 )= = (selfia* self.s Leam = 0: Lisum 0 for in range(1, +1)):
(st ( (self.s
Luum = 0; Luum
in range(1, self.W+1))
8 ti (s + 0004 c) S 4:
fall.
18 +.
self.e) self.e)
c)
Taum += + (a+)
Lum += (1
Leum += List (5)
Luu += Lis
9 (Leum Loum) ///m)/ 1/222 self.W). self. self.st st: self.s
g 0= (L Luum)) (20²) /2o2222f...W) self.s = = =
self.e
self.T = self.T +
self.T = self.T + W
if self.T 2 T: reset at the and
self.T 2 T: # reset at the end
self.r = 0; self.s* so; self.s =
self.T = 0; self.s* = 80; self.s = 80
self.ş 0
return g
return
They show that an unbiased gradient estimator is given by (see Algorithm !
PES(0)
LT+:(10 + ei]xw...., ((//w)))xx))
20RW
-b -ellww........ (l/))
(ss)+
Σ ()) + +0/++//)))) (6)
with randomness in both {E:} and T. To eliminate the bias of TES, instead of multiplying only with the current epsilon <//W+1 PFS multiplies it with the cumulative sum of all the different iid noise sampled so far (self. in PESWorker). As we shall see in the next section, this accumulation of noise terms provably results in higher variance, making PES less desirable in practice. We contrast the noise sampling properties of our proposed methods with PES in Figure [b)..
Hysteresis. When online gradient estimators are used in training, they often suffer from hysteresis, or history dependence, as a result of the parameters 0 changing between adjacent unrolls. That is, the parameter value Ou that worker uses in the current truncation window is not the same parameter 0_1 that was used in the previous window. This effect is often neglected [15, under an assumption that is updated slowly. To the best of our knowledge, [17) is the only work to analyze the convergence of an online gradient estimator under hysteresis. online gradient estimates are computed without hysteresis in order to isolate the problem. However, in Section 5
the following theoretical analysis, we assume all
we show empirically that even under the impact of hysteresis, our proposed online estimator NRES can outperform non-online methods (e.g., FullES) which don't ton't suffer from hysteresis.
3 A New Class of Unbiased Online Evolution Strategies Methods
As shown in Section 2 TES and PES both sample a new noise perturbation e for every truncation window produce gradient estimates. Here we note that the frequency of neise-sharing (new noise every truncation window of size W) is fixed to the frequency of gradient estimates (a gradient estimate every truncation window of size W). However, the former is a choice of the smoothing objective (5). while the latter is often a choice of how much gradient update latency the user can tolcrate. this section we break this coupling by introducing a general class of gradient estimators that encompass PES. We then analyze these estimators' variance to identify the one with the least variance.
Generalized Persistent Evolution Strategies (GPES). For given fixed truncation window size W. we consider all noise-sharing periods K that are multiples of W. K = cW for E 2t, o < T/W. K being a multiple of W ensures that within each truncation window, only single is used. When

---

= W, we recover the PES algorithm. However, when K is larger than W, the same noise will be used across adjacent truncation windows (Figure 2())). With new noise sampled every K unroll steps, define the -smoothed loss objective as the function:
0 + [ T( + E1)xx, 10 +pr/K)lxer..)
where r: (z+)² - z the modified remainder function such that r(z: y) is the unique integer E [1. where r qy + for some integer q. This extra notation allows for the possibility that T not divisible by K and the last noise EfT/K] used for only r(T, K) K steps.
We now give the analytie form of unbiased gradient estimator of the resulting smoothed loss Lemma 1. An unbiased gradient estimator for the K K-smoothed loss is given by
W
GP)S 20
1
Σ
L++ + ei]xx...., 10 (0+(L//K==xxxx-//
[ Σ 6
- (10+)(0--e)) =1)xx..... E| (0-((///))1)xxrraa)))
(2
with randomness in and {c; [c))[=/k] [T/K]
GPES x algorithm. Here, for the truncation window starting at step T, the noise Crr/K]41 is used as the antithetic perturbation to unroll the system, If T is not divisible by K, then this noise has already been sampled at time step / = [r/K] K in an earlier truncation window. Therefore, to know what noise to apply at this truncation window, we need to remember the last used e and update it when t becomes divisble by K. We provide the algorithm for the GPESK gradient estimator in Algorithm in the Appendix. Note that GPESK=w is the same as the PES algorithm.
Variance Characterization of GPESK- With this generalized class of gradient estimators GPESK. one might wonder how to choose the value of K. Since each estimator is an unbiased gradient estiamtor with respect to its smoothed objective, we compare the variance of these estimators as function of K. To do this analytically, we make some simplifying assumptions:
Assumption 2. For a given 0 E Rd and t E [T] = {1, (1....,T), there exists set of vectors {9} IR " such that for any {u, R Rd Fi=1, the following equality holds:
(. + U1 + U2 0 + v.) L. - vn 0 U2 0 0 = (0.) (g))
(8)
Remark 3. This assumption is more general than the quadratic I., assumption made in 15 (expla- nation see Appendix (D). Here one can roughly understand of as time step i's smoothed loss's partial derivative with respect to the i-th application of 6. For notational convenience, we let g" = E gf
k-j (roughly the total derivative of smoothed step-t loss with respect to 0) and gk.j E -(-x)) of for j E (1...., [t/ }}} (roughly the sum of partial derivatives of smoothed step-t loss with respect to all 0's in the j-th sharing window of size K (the last window might be shorter)).
With this assumption in place, we first consider the case when W = and K = cW = c c [T]. In this case, the GPESK estimator can be simplified into the following form:
Lemma 4. Under Assumption when W 1, GPES = E. (E/z/ol+
E. E ges
With this simplified form, we can now characterize the variance of the estimator CPESS==(0 Since it's a random vector, we analytically derive its total variance (trace of covariance matrix)
Theorem 5. When W = 1 and under Assumption for integer c C [T].
(C(Cov(GPESx = (d 2)
(11
T
T
[t/el
Σ
|
d..r((2) (9)
T
T
2
J=
7 '[x]] is smallest integer 2 xx; | is the largest integer < x
Prooof's for all the Lemmas and Theorems in Appendix D
5

---

Learned Optimizer
7= 1 1000, W
10a
Figure 3: Total variance of GPESK vs. noise-sharing period K for different 0,'s from the learned trajectory of PES. GPESk (NRFS) has the lowest total variance among estimators of its class (including PES) for cach 0,-
tnCoviCCPts.e
10a
10a
10a
166
64
256
1000 (NRES)
(PES)
nhareig peried (E(.TT]
To understand how the value of K changes the total variance, we notice that only the nonnegative third term in (9) depends on it. This term measures the pairwise squared distance between non- overlapping partial sums S'. for all j. When T, for every 1 [T', there is only a single such partial sum as [t/c]
In this case, this third term reduces to its smallest value of 0. Thus:
Corollary 6. Under Assumption _ when W = 1, the gradient estimator GPESK=r(0) has the smallest total variance among all [GPESK K E [T]} estimators.
Remark 7. To understand Corollary O intuitively, notice that at a given time step (i.e., a length-1 1 truncation window), any GPESK=< gradient estimator (c (TT) aims to unbiasedly estimate the total derivative of the smoothed loss at this step with respect to 0, which we have denoted by g'. By applying new Gaussian noise perturbation every e < T steps, the GPESk estimators indirectly estimate ge by first unbiasedly estimating the gradients inside each size-c noise-sharing window: {gb,)} [1/cl and then summing up the result (notice g' = [t/cl gdg). To obtain this extra (yet unused) information about the intermediate partial derivatives, these estimators require more randomness and thus suffer from a larger total variance than the GPESk=T' estimator which directly estimates g'.
j=
Experimental Verification of Corollary 6 We empirically verify Corollary 6 meta meta-training learned optimizer task (T' 1000; see additional details in Section (5.2). Here we save trajectory of 02 learned by PES (i denotes training iteration) and compute the total variance of the estimated gradients (without hysteresis) by GPES with different values of K in Figure 3aa (W =). In agreement with theory, K 7 has the lowest variance.
4 Noise-Reuse Evolution Strategies
NRES has lower variance than PES. As variance reduction is desirable in stochastic optimization (18. by Corollary 6 the gradient estimator GPFS x is particularly attractive and can serve crriance-reduced replacement for PES. When K T, we only need to sample a single e once at the beginning of an episode (when t 0) and reuse the same noise for the entirety of that episode before it resets. This removes the need keep track of the cumulative applied noise (E) (Figure
making the algorithm simpler and more memory efficient than PES. Due to its noise-reuse property, we name this gradient estimator GPESK= the Woise-Reuse Evolution Strategies (NRES) (pseudocode in Algorithm 2) Concurrent with our work, Vicol [9] independently proposes a similar algorithm with different analyses. We discuss in detail how work differs from [19 in Appendix [B] Despite Theorem 5) assuming W = 1, one can relax this assumption to any W that divides the horizon length T. By dehning "mega" UCG whose single transition step is equivalent W steps in the original UCG, we can apply Corollary to this mega UCG and arrive at the following result.
Corollary 8. Under Assumption when W divides T, the NRES gradient estimator has the smallest total variance among all GPES FFEKK=WW estimators e E (T/W).
NRES is a replacement for FullES, By sharing the same noise over the entire horizon, the smoothing objective of NRES is the same FullES's. Thus, we can think of NRES as the online counterpart to the offline algorithm FullES. Hence NRES can act as a drop-in replacement to FullES in UCGs. A single FullES worker runs 2T unroll steps for each gradient estimate, while a single NRES runs only 2W steps. Motivated by this, we compare the average of T / i.idd NRES gradient estimates with FullES gradient estimate as they require the same amount of compute.
NRES is more parallelizable than FullES. Because the T/W NRES gradient estimators independent of each other, we can run them in parallel. Under perfect parallelization, the entire NRES gradient estimation would require O(W) time to complete. In contrast, the single FullES gradient estimate has to traverse the UCG from start to finish, thus requiring ( time. Hence, NRES is T/W times more parallclizable than FullES under the same compute budget (Figure (a))

---

(a) Gradient estimation FullES
under the same per-update budget of 27 unrolls
(b)
T
1000, W
(-00% ei)
FullES
total vartance CrvC
(17)) time to return j
iter.
NRES
TIN
Wornerft
Epande length
(x10
f1
w
NRES, (0z)
(())
Returns
1.47
0.38
804.34
385.01
OOW) time (parallelization)
Worker
2
15.74 + 1.90
513.50 + 74.71
201.38
30.18
Total variance lower than
3.20 = 0.50
681.85 + 86.90
(Theorem 9)
Worker
ki the cara partebutton
4.47
181.06
24.97
4.42
1: 0.68
288.61 1 46.77
epliods
6.33
1.08
448.30
non-paralieltaalle same starting time
unroltiitt the caroon updiae
8
6.62
1 0.89
154.86
28.21
Figure 4: (a) Comparison of FullES and NRES gradient estimation under the same unroll budget. Unlike FullES which can only use a single noise perturbation e to unroll sequentially for an entire episode of length T. NRES can use T/ /W parallel step-unlocked workers each unrolling inside its random truncation windows of length W with independent perturbations e This results in T/W x speed-up and variance reduction (Theorem p) over FullES. (b) The total variance of NRES and FullES estimators under the compute budget at the same set of 0, checkpoints Figure Ba). NRES achieves significantly lower total covariance.
NRES can often have lower variance than FullES. We next compare the variance of the average of T/W ii.dd NRES gradient estimates with the variance of 1 FullES gradient estimate:
Theorem 9. Under Assumption
2 for any W that divides T, if
T/w
W-R
T/W
W-B
Σ
g
(10)
L-
1111
( 1111
then for iid (0)) T/W estimators.
Lr(Cov((Ta T/W NRES.(0)) I (FCoo(FulIES())..
Remark 10. To understand the inequality assumption in (10), we notice that it relates the sum of the squared 2-norm of vectors {E (B-:+1 9 T/W with the squared 2-norm of their sum. When these vectors pointing in similar directions, this inequality would hold (to see this intuitively, consider the more extreme case when all these vectors are exactly in the same direction). Because each term > ( 9" can be understood the total derivative of the sum of smoothed losses in the k-th truncation window with respect to 8, we see that inequality (IO) is satisfied when, roughly speaking, different truncation windows' gradient contributions are pointing in similar directions. This is often the case for real-world applications because if we can decrease the losses within truncation window by changing the parameter 0. we likely will also decrease other truncation windows' losses. At high-level, Theorem shows that for many practical unrolled computation graphs, NRES is not only better than FullES due its better parallelizability but also better due to its lower variance given the same computation budget.
Empirical Verification of Theorem We empirically verify Theorem 9 in Figure (b) using the same set up of the meta-training learned optimizer task used in Figure 3 a). Here we compare the total variance of averaging T/W = 1000 ii.d NRES estimators versus using FullES gradient estimator (same total amount of compute). We see that NRES has significantly lower total variance than FullES while also allowing T/W 1000 times wall-clock speed up due to its parallelizabilit..
5 Experiments
NRES is particularly suitable for optimization in UCGs in two scenarios: 1) when the loss surface exhibits extreme local sensitivity; 2) when automatic differentiation of the loss is not possible/gives noninformative (e.g., zero) gradients. In this section, we focus on three applications exhibiting these properties: a) learning Lorenz system's 's parameters (sensitive), b) meta-training learned optimizers (sensitive), and e) reinforcement learning (nondifferentiable) and show that NRES outperforms existing AD and ES methods for these applications. When comparing online gradient estimation methods, we keep the number of workers N used by all methods the same for fair comparison. For the offline method FullES, we choose its number of workers to be W/Tx the number of NRES workers all tasks (in order to keep the same number of unroll steps per-update) except for the learned optimizer task in Section where we show that NRES can solve the task faster while using much fewer per-update steps than FullES.
7

---

(a)
(b)
Lorenz System 702000
training loss Lil 9- (Inrr), intel)
Lorenz system T 2000
Srendomm
(95% contidince Interon)
20
FJIES
50
250
450
aptimication trajectorics (8i) by differant GPESc
TES W 100, 200
W 200, W 100, 0.04, SGD icamiing rate: le
PES W- 100. 200.N-200 200
NREES W8 100, d2 (ours)
3.2
K-4W
10W
(NRES)
PES W 100, 20000
3.0
loss
convengged W-
Inle)
2.8
10²
2.6
2.4
2.2
4x101
32
3.4
3.6 Intr)
3.2 2.4
3.6
3.2 34
3.6
3.2
34
3.6
3.2 3.4 3.6
200 250
wall-clock (seconds)
Figure 5: (a) The pathological training loss surface of the Lorenz system problem (left) and the optimization trajectory of different GPESx gradient estimators (right). NRES's 's trajectory is the smoothest because of its lowest variance. (b) Different ES methods' loss convergence the same problem. NRES converges the fastest.
5.1 Learning dynamical system parameters
In this application, we consider learning the parameters of a Lorenz system, a canonical chaotic dynamical system. Here the state & = (It, Ut. 21) E R is unrolled with two learnable parameters a, with the discretized transitions (dt 0.005) starting so (Io. yo. z0) (1.2, 1.3, 1.6):
T++1 = Fz + ayy: - zz dt)dt; ye+1 = y + [x+- (r z+) yr dt; 2++1 = 21 + x 3/+ - 8/3 2tdtt.
Due to the positive constraint on r > 0 and a > 0, we parameterize them as 0 = (In(r), In())) E R? and exponentiate the values in each application. We assume we observe the ground truth 2-coordinate
=f for E [T].T T = 2000 steps unrolled by the default parameters (r ada) = (28, 10). For each step t, we measure the squared loss [{())) = (2t- 2² Our goal is to recover the ground truth parameters gg: = (ln)) In(10) by optimizing the average loss over all time steps using vanilla SGD. We first visualize the training loss surface in the left panel of Figure 5]a) (also see Figure 8 in the Appendix) and notice that it has extreme sensitivity to small changes in the parameter 6.
To illustrate the superior variance NRES over other GPES estimators, we plot in the right panels of Figure the optimization trajectory of 0 using gradient estimator GPESk with different values of K under the same SGD learning rate. We see that NRES's trajectory exhibits the least amount of oscillation due to its lowest variance. In contrast, we notice that PES's trajectory is highly unstable, thus requiring a smaller learning rate than NRES to achieve possibly slower convergence. Hence, we take extra care in tuning each method's s constant learning rate and additionally allow PES to have decay schedule. We plot the convergence of different ES gradient estimators in wall-clock time using the same hardware in F (We additionally compare against automatic differentiation methods in Figure in the Appendix; they all perform worse than the ES methods shown here.)
In terms of the result, we see that NRES outperforms 1) TES, as NRES is unbiased and can better capture long-term dependencies; 2) PES, as NRES has provably lower variance, which aids convergence in stochastic optimization; 3) FullES, as NRES can produce more gradient updates in the same amount of wall clock time than FullES (with parallclization. each NRES update takes O(W) time instead of FullES'ss O(T) time). Additionally, we plot the asymptotically converged loss value when we train with significantly larger number of particles (N = 20000) for PFS and NRES. We see that by only using N 200 particles, NRES can already converge around its asymptotic limit, while PES is still far from reaching its limit within our experiment time.
5.2 Meta-training learned optimizers
In this application [3] the meta meta-paaameters of a learned optimizer control the gradient- based updates of an inner model's parameters. The inner state s; is the optimizer state which consists of both the inner model's 's parameters and its current gradient momentum statistics. The transition function ft computes an additive update vector to the inner parameters using 0 and random training batch and outputs the next optimizer state 81+1- Each time step I's meta-loss T.ţ evaluates the updated inner parameters' generalization performance using sampled validation batch.
We consider meta-training the learned optimizer model given in 3 (d 1 1762) to optimize 3- layer MLP on the Fashion MNIST dataset for T = 1000 steps. (We show results on the same task
We don't 't learn the third parameter, fixed at 8/3, so that we easily visualize 2-d loss surface.
8

---

a
Leared Optimizer 7 1000
Learned Optimizer T= 1000, 1= N= 100
Fondom soods ovcrage (15% confidincc intohvol
10
randdmm seeds everage (95/6 roniisetce interval
FullES NN 10
PES (GPES K-
TES W 1-=1, N- 100
smoothed training
PES W = 1, 100
non smoothed training
GPES K=
NRES = (ours)
8x 2x
GPES K 64
NRES (GIPES K 1000
10a
24:3571
5-30-1
1000 2003
3500
4000
5000
6000 7000 6000
1000
2002
4000 5000 6030 7000 wall-clock time (seconds)
3000
8000
wall-clock time (seconds)
the learned optimizer task in wall-clock time. NRES reaches the lowest loss fastest. (b) The loss convergence of GPESS gradient estimators with difference K values on the same task. NRES converges the fastest due to its reduced variance.
Figure 6: (a) Different ES gradient estimators' training loss convergence
with higher-dimension and longer horizon in Appendix E. 1.1.2 This task is used in the training task distribution of the state of the art learned optimizer VeL. 20 The loss surface for this problem has
high sharpness and many suboptimal minima as previously shown in Figure [a). We meta-train with Adam using different gradient estimation methods with the same hardware and tune each gradient estimation method's meta learning rate individually. Because AD methods all perform worse than the ES methods, we defer their results to Figure in the Appendix and only plot the convergence of the ES methods in wall-clock time in Figure (
Here we see that NRES reaches the lowest loss value in the same amount of time. In fact, PES and FullES would require 5 and 9x (respectively) longer than NRES to reach loss NRES reaches early on during its training. while TES couldn't 't even reach that loss within our experiment time. It is worth noting that, for this task, NRES only require 2-N W = 200 unrolls to produce an unbiased, low-variance gradient estimate, which is even smaller than the length of single episode (T 1000). In addition, we situate NRES's performance within our proposed class of GPESK estimators in Figure 6 (b. In accordance with Corollary R. NRES converges fastest due its reduced variance.
5.3 Reinforcement Learning
It has been shown that ES is scalable alternative policy gradient and value function methods for solving reinforcement learning tasks [1]. In this application, we learn a linear policy IT] (following (II) using different ES methods on the Mujoco [22) Swimmer (d = 16) and Half Cheetah task (d = 102). We minimize the average of negative per-step rewards over the horizon length of T= 1000, which is equivalent to maximizing the undiscounted sum rewards. Unlike 14 we don't use additional heuristic tricks such as 1) rank conversion of rewards, 2) scaling by loss standard deviation, or 3) state normalization. Instead, we aim to compare the pure performance of different ES methods assuming perfect parallel implementations. To do this, we measure method's 's performance as function of the number of sequential environment steps it used. Sequential environment steps are steps that have to happen one after another (e.g., the environment steps within the same truncation window). However, steps that are parallelizable don't 't count additionally in the sequential steps. Hence, the wall-clock time under perfect parallel implementation is linear with respect to the number of sequential environment steps used. As all the methods we compare are iterative update methods, we additionally require that each method use the same number of environment steps per update when measuring each method's 's required number of sequential steps to solve a task. We tune the SGD learning rate individually for each method and plot their total rewards progression on both Mujoco tasks in Figure 7
Here we see that TES fails to solve both tasks due to the short horizon bias 23 making it unable to capture the long term dependencies necessary to solve the tasks. On the other hand, PES, despite being unbiased, suffers from high variance, making it take longer (or unable in the case of Half Cheetah) to solve the task than NRES. As for FullES, despite using the same amount of compute per gradient update as NRES, it's much less parallelizable as discussed in [ - it takes much longer time (10x and 60x) ) than NRES assuming perfect parallelization. In addition to the number
We show the performance of ES methods on another task from this distribution in Appendix E.1. We additionally compare the ES methods on learning non- lonelinear (d = 726) policy on the Cheetah task in Appendix E.1.3

---

(a) Swimmer, T 1000
(b) Half Cheetah, T 1000
Frendoom
(50% InterORO
raenium
1953 intervall
RIES
FES 336, Ai 20
FES W
undiscounted sum rewards
400-
300
N125 W L00, (AI))
undiscounted rewards
2003
N125 Jouts
300
200-
talk sking trsdrai
100-
tast sating treahed
20300
-1000
523001
107
10
10
10
10a
10
of sequential environment steps
sequential environment steps
Figure 7: ES methods' performance vs. the number of sequential environment steps used in solving the Mujoco (a) Swimmer task and (b) Half Cheetah task. NRES solves the tasks fastest under perfect parallelization.
of sequential steps, we additionally show the total number of environment steps used by each method in Table 3 in the Appendix NRES also uses the least total number of steps to solve both tasks, making it the most sample efficient.
6 Additional Related Work
Beyond the most related work in Section 2 in this section, we further position NRES relative to existing zeroth-order gradient estimation methods. We also provide additional related work on automatic differentiation (AD) methods for unrolled computation graphs in Appendix
Zeroth-Order Gradient Estimators. this work, we focus on zeroth-order methods that can estimate continuous parameters' gradients to be plugged into any first-order optimizers, unlike other zeroth-order optimization methods such as Bayesian Optimization (24). random search (25), or Trust Region methods (26] (7). We also don't compare against policy gradient methods [9. because they assume internal stochasticity of the unrolling dynamics, which may hold for deterministic policy learning [e.g., 22). Within the space of evolution strategies methods, many works have focused improving the vanilla ES method's variance by changing the perturbation distribution 21]
considering the covariance structure [32, and using control variates [33] However, these works do not consider the unrolled structure of UCGs and are offline methods. In contrast, reduce the variance by incorporating this unrolled aspect through online estimation and noise-reuse. As the aforementioned variance reduction methods work orthogonally to NRES, it is conceivable that these techniques can be used in conjunction with NRES further reduce the variance.
7 Discussion, Limitations, and Future Work
In this work, we improve online evolution strategies for unbiased gradient estimation in unrolled com- putation graphs by analyzing the best noise-sharing strategies. By generalizing an existing unbiased method, Persistent Evolution Strategies, a broader class, we analytically and empirically identify the best estimator with the smallest variance and name this method Noise-Reuse Evolution Strategies (NRES). We demonstrate the convergence benefits of NRES over other automatic differentiation and evolution strategies methods on a variety of applications.
Limitations. As NRES is both an online method and an ES method, it naturally inherits some limitations shared by all methods of these two classes, such as hysteresis and variance's linear dependence on the dimension d. We provide detailed discussion of these limitations in Appendix F
Future Work. There are some natural open questions: 1) choosing better sampling distribution for NRES. Currently the isotropic Gaussian's 's variance σ² tuned as a hyperparameter. Whether there are better ways to leverage the sequential structure in unrolled computation graphs to automate the selection of this distribution is open question. 2) Incorporating hysteresis. Our analysis assumes no hysteresis in the gradient estimates and we haven't 1 observed much impact of it in our experiments. However, understanding when and how correct for hysteresis is interesting direction.
Acknowledgments
We thank Kevin Kuo, Jingnan Ye, Tian Li, and the anonymous reviewers for their helpful feedback.
10

---

References
[1] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, (8):1735-1780, 1997.
[2] Kyunghyun Cho, Bart Merrienboer, Caglar Gulcehre, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. In EMNLP. 2014.
[3] Luke Metz, Niru Maheswaranathan, Jeremy Nixon, Daniel Freeman, and Jascha Sohl-Dickstein. Understanding and correcting pathologies in the training of learned optimizers. In International Conference on Machine Learning. 2019.
[4] James Harrison, Luke Metz, and Jascha Sohl-Dickstein. closer look Iearned optimization: Stability, robustness, and inductive biases. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances Neural Information Processing Systems, 2022.
[5] Dougal Maclaurin, David Duvenaud, and Ryan Adams. Gradient-based hyperparameter op- timization through reversible learning. In International Conference on Machine Learning, 2015.
[6] Luca Franceschi, Michele Donini, Paolo Frasconi, and Massimiliano Pontil. Forward and reverse gradient-bases hyperparameter optimization. In International Conference on Machine Learning, 2017.
[7] Tongzhou Wang, Jun-Yan Zhu, Antonio Torralba, and Alexei A Efros. Dataset distillation. arXiv preprint 1rxivv11811 10959, 2018.
[8] George Cazenavette, Tongzhou Wang, Antonio Torralba, Alexci Efros, and Jun-Yan Zhu. Dataset distillation by matching training trajectories. In Proceedings of the IEEE/CVF Confer- ence on Computer Vision and Pattern Recognition, pages 4750-4759, 2022.
[9] Richard S Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforcement learning with function approximation. Advances in Neural Information Processing Systems, 1999.
[10] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, 2015.
[11) Atilim Gunes Baydin, Barak A Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation in machine learning: survey, Journal of Machine Learning Research, 18: 1-3,, 2018.
[12] Paavo Parmas, Carl Edward Rasmussen, Jan Peters, and Kenji Doya. PIPPS: based policy search robust to the curse of chaos. In International Conference on Machine Learning, 2018
Flexible model-
[13] Luke Metz, C Daniel Freeman, Samuel S Schoenholz, and Tal Kachman. Gradients are not all you need. arXiv preprint arXiv:2111.05803 2021.
[14] Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and llya Sutskever. Evolution strategies as a scalable alternative to reinforcement learning. arXiv preprint arXiv: 7703.03864 2017.
[15] Paul Vicol, Luke Metz, and Jascha Sohl-Dickstein. Unbiased gradient estimation in unrolled computation graphs with persistent evolution strategies. In International Conference on Machine Learning, 2021.
[16] Peter W Glynn. Likelihood ratio gradient estimation for stochastic systems. Communications of the ACM, 33(10):75-88 84, 1990.
[17] Sherre-yves Massé and Yann Ollivier. Convergence of online adaptive and recurrent optimization algorithms, arXiv preprint arXiv:2005.0556 2020.
[18] Chong Wang, Xi Chen, Alexander Smola, and Eric P Xing. Variance reduction for stochastic gradient optimization. Advances in neural information processing systems, 26, 2013.
11

---

[19] Paul Vicol. Low-variance gradient estimation in unrolled computation graphs with es-single. In International Conference on Machine Learning. 2023.
[20] Luke Metz, James Harrison, C Daniel Freeman, Amil Merchant, Lucas Beyer, James Bradbury, Naman Agrawal, Ben Poole, Igor Mordatch, Adam Roberts, et al. Velo: Training versatile learned optimizers by scaling up. arXiv preprint arXiv:221 1.09760, 2022.
[21] Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies competitive for reinforcement learning. In Advances Neural Information Processing Systems, 2018.
[22] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In International Conference on Intelligent Robots and Systems, 2012.
[23] Yuhuai Wu, Mengye Ren, Renjie Liao, and Roger Grosse. Understanding short-horizon bias in stochastic meta-optimization. In International Conference Learning Representations, 2018.
[24] Peter Frazier. tutorial on bayesian optimization. arXiv preprint arXiv: 1 2018.
[25] James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of Machine Learning Research, 13(2), 2012.
[26] Alvaro Maggiar, Andreas Wachter, Irina S Dolinskaya, and Jeremy Staum. derivative-free trust-region algorithm for the optimization of functions smoothed via gaussian convolution using adaptive multiple importance sampling. SIAM Journal on Optimization, 28(2):1478-133) 1507, 2018.
[27] Guoqing Liu, Li Zhao, Feidiao Yang, Jiang Bian, Tao Qin, Nenghai Yu, and Tie- Yan Liu. Trust region evolution strategies. In AAAI Conference on Artificial Intelligence, 2019.
[28] Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. In Interna- rional Conference on Machine Learning, 2018
[29] Niru Maheswaranathan, Luke Metz, George Tucker, Dami Choi, and Jascha Sohl-Dickstein. Guided evolutionary strategies: augmenting random search with surrogate gradients. Interna- tional Conference on Machine Learning, 2019.
[30] Alexandru Agapie. Spherical distributions used in evolutionary algorithms. Mathematics, (23), 2021. ISSN 2227-7390.
[31] Katelyn Gao and Ozan Sener. Generalizing Gaussian smoothing for random search. In International Conference on Machine Learning. 2022.
[32] Nikolaus Hansen. The ema evolution strategy: A tutorial. arXiv preprint 1rXiv:1604.000 2016.
[33] Yunhao Tang, Krzysztof Choromanski, and Alp Kucukelbir. Variance reduction for evolution strategies via structured control variates. In International Conference on Artificial Intelligence and Statistics, 2020.
[34] Martín Abadi. Tensorflow: learning functions at scale. In Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming, pages 2016.
[35] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, nigh-performance deep learning library. Advances in Neural Information Processing Systems, 2019.
[36] Tianqi Chen, Bing Xu, Chiyuan Zhang, and Carlos Guestrin. Training deep nets with sublinear memory cost, arXiv preprint 1600x 2016.
[37] Corentin Tallec and Yann Ollivier. Unbiasing truncated backpropagation through time, arXiv preprint arXiv 08209, 2017.
12

---

[38] Aidan N Gomez, Mengye Ren, Raquel Urtasun, and Roger B Grosse. The reversible resid- ual network: Backpropagation without storing activations. Advances Neural Information Processing Systems, 2017.
[39] Ronald Williams and David Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural Compulation, 1(2):270-280, 1989.
[40] David Silver, Anirudh Goyal, Ivo Danihelka, Matteo Hessel, and Hado van Hasselt. Learning by directional gradient descent. In International Conference on Learning Representations, 2021.
[41] Corentin Tallec and Yann Ollivier. Unbiased online recurrent optimization. arXiv preprint arXiv:170..05043, 2017.
[42] Asier Mujika, Florian Meier, and Angelika Steger. Approximating real-time recurrent learning with random kronecker factors. Advances in Neural Information Processing Systems, 31, 2018.
[43] Frederik Benzing, Marcelo Matheus Gauy, Asier Mujika, Anders Martinsson, and Angelika Steger. Optimal kronecker-sum approximation of real time recurrent learning. In International Conference on Machine Learning, 2019.
[44] Alex Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.
[45] Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus). arXiv preprint 1606::1606.08415 2016.
[46] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 2017.
[47] Luke Metz, C Daniel Freeman, James Harrison, Niru Maheswaranathan, and Jascha Sohl- Dickstein. Practical tradeoffs between memory, compute, and performance in learned optimizers. In Conference on Lifelong Learning Agents, 2022.
[48] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint 160.::6606.015000 2016.
[49] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milhe and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL
http://github com/ hoo///oooo//aax
13


Reviews:
[{"review_id": "xwkrjXt3uB", "reviewer": "Reviewer_Wtuw", "summary": "This paper studies online evaluation strategies for unrolled computation graphs. Especially, the authors 1). propose a general class of unbiased online evolution strategies that generalizes Persistent Evolution Strategies (PES), named Generalized Persistent Evolution Strategies (GPES). The key idea is to share noise across truncation windows instead of sampling every round. 2). characterize the variance and variance reduction properties of their strategies. 3). study a special case of the general class strategies, named Noise Reuse Evolution Strategie (NRES), show the variance advantage of NRES over other estimators. 4). experimentally show the advantages of NRES across a variety of applications, including learning dynamical systems, meta-training learned optimizers, and reinforcement learning.", "questions": "Given a time $T$, FullES returns one gradient g=[L([\\theta+\\epsilon]_{\\times T})-L([\\theta-\\epsilon]_{\\times T})]{\\epsilon}/{2\\sigma^2}, and NRES (Algorithm 2) returns $T/W$ gradients $g_1,\\dots, g_{T/W}$, where g_k=[\\sum_{t=Wk+1}^{Wk+W}L_t([\\theta+\\epsilon]_{\\times t})-L([\\theta-\\epsilon]_{\\times t})]{\\epsilon}/{2\\sigma^2 W}. By definition, there is $g=W/T \\sum_{k=1}^{T/W} g_k$. In this case, if we choose learning rate $\\eta_{FullES} = \\eta_{NRES}T/W$, there should be no difference between FullES and NRES. So why is there such a big improvement in the experiments?\n\nOne minor typo: Algorithm 6 line 10: not $L_t^s$, should be $L_{self_.\\tau +1}^s$.\n", "limitations": "Theoretical work. No limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea of reusing noise to reduce variance is interesting and a bit counterintuitive. For first order method, reusing noise always lead to a larger variance (If the noise is reused, averaging gradients cannot reduce the variance of the noise). However, it seems for evolution strategy, such a simple method could significantly reduce variance and improve the performance.\n- Experimental results are comparable to the previous methods and show a remarkable improvement.  \n- The paper is well writen. The proof in the appendix is well organized and seems correct.", "weaknesses": "- No comparision between NRES and first order method.\n- The authors did not explain the some parameter setting in the experiments. Especially, in Figure 5 and 6, why choose a different N when comparing online ES and FullES?\n- For online ES, the algorithm update $\\theta$ every truncation window, thus the loss will never be in the form of (7). In this case, it seems NRES is still biased. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Comparison between NRES and first order methods**. We have provided discussions of automatic differentiation (first order) methods in Section B Additional Related Work in the Appendix. Besides, we have provided empirical comparisons between NRES and 4 different first order AD methods on the Lorenz task and the learned optimizer task in our paper. As these first order methods all perform worse than ES methods (line 241 and 261), we have deferred their results to Figure 8 and 9 in the Appendix.\n\n**How $N$ is chosen for the experiments**. As we have described on line 188-190, because a FullES worker’s gradient estimate uses $2T$ steps while an NRES worker uses $2W$ steps, we by default maintain a ratio of $T/W$ between the number of NRES and FullES workers to keep the per-update number of unrolls constant. This is how we choose N for online ES and FullES on the Lorenz task (Figure 4(b)), the Swimmer task (Figure 6(a)), and the Half Cheetah task (Figure 6(b)). For the learned optimizer task (Figure 5(a)), we empirically find that we can use significantly fewer online ES workers to achieve good performance  –  we only need $200$ total unrolls ($100$ NRES workers each antithetically unrolling for $1$ steps) per meta-gradient update. Because $200$ total unrolls is shorter than the minimum number of unrolls FullES needs per update (at least $2\\times T = 2000$ unrolls), we have to relax the default number of worker ratio and allow FullES to use more workers (we choose $N=10$ after tuning it among $\\\\{1, 3, 10\\\\}$ (line 840-842).\n\n**Bias in NRES**.\nAs we have discussed in the paragraph on _hysteresis_ (line 105-113), it is indeed correct that, as we update $\\theta$ every truncation window, the loss in the current window has some historical dependence on past values of $\\theta$ (hysteresis), making NRES gradient biased in practice. However, it is worth noting that all the prior works on online gradient estimation methods (including TES, PES and first order methods like UORO and DODGE) also have bias from hysteresis. Although we didn’t observe much impact of hysteresis in our experiments, we believe understanding and correcting hysteresis is an interesting direction of future work as we have discussed in line 323-325.\n\n**Understanding the improvement of NRES over FullES**.\nGiven the same computation budget of $2T$ unrolls, we can use it either to produce one FullES gradient estimate or to produce $T/W$ i.i.d. NRES gradient estimates. The reviewer’s current description assumes the same NRES worker sequentially produces these $T/W$ gradient estimates – instead, these $T/W$ NRES gradient estimates are produced by independent workers and thus can happen simultaneously. In contrast, the single FullES worker has to unroll sequentially for $T$ steps from start to finish. Thus NRES can complete the same amount of total unrolls with $T/W \\times$ less time than FullES (see line 191-195). This ability to achieve extra parallelization is the primary reason we see such a big improvement of NRES over FullES in the experiments."}, {"review_id": "q27ClEpb5a", "reviewer": "Reviewer_77pb", "summary": "In this paper, the author(s) extended the well-known Persistent Evolution Strategies via noise-reuse and proposed an improved version with reduced variance. The main contribution of this paper is to provide detailed mathematical proof to validate their claim.", "questions": "see above", "limitations": "No comments here.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Considering this significant contribution to the evolution strategies and other related ML communities, I personally suggest accepting this high-quality research paper.\n\nIn this paper, the author(s) also discussed the main limits of their method. These discussions about the possible limitations (hysteresis and complexity) are highly encouraged for academic research because this can better reflect the whole state of their method.\n\nFurthermore, the author(s) pointed out that “whether there are better ways to leverage the sequential structure” beyond the isotropic Gaussian distribution. I agree that this is an interesting open question (worth to be investigated).", "weaknesses": "Some notes are given in order to further improve this paper:\nFor Section 5.3 Reinforcement Learning, the removal of “additional heuristic tricks” can help us focus on the underlying mechanism, which is very critical for algorithmic understanding, no matter from a practical or theoretical perspective. We often prefer general-purpose design principles, though these “additional heuristic tricks” sometimes work well in some cases. Given that only the linear policy was used in experiments, it is highly expected to include also the more challenging non-linear policy with higher dimensions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating the significance of our contribution.\n\n**Non-linear RL policy**. We initially experimented with linear policies on the Mujoco tasks because\n1. it has been observed by Rajeswaran et al that using linear policies can yield performances comparable to state-of-the-art results on continuous control (Mujoco) tasks;\n2. we want to keep our experiments consistent with prior works on ES (Mania et al, Vicol et al), which also experiment with linear policies.\n\nHowever, following your suggestion, we have conducted an additional experiment where we train a multi-layer perceptron policy used by Schulman et al on the Half Cheetah task, which thereby increases the total number of parameters by $6.5\\times$. We tune each ES method’s SGD learning rate individually and report the result in Figure 3(b) in the attached pdf in the common response. Here we constrain all the methods to use the same number of total environment steps. We notice that among the four methods, only NRES has successfully solved the task. For the rest of the methods, although FullES comes close to solving the task, it requires $50\\times$ more theoretical wall clock time than NRES. Besides, both PES and TES are far away from solving the task under the same budget. This result demonstrates NRES’s ability to learn non-linear, higher-dimensional policy for reinforcement learning and also provides additional evidence of NRES’s significant advantage over other ES methods. Thanks for the suggestion to explore this direction.\n\nMania, H., Guy, A., & Recht, B. (2018). Simple random search provides a competitive approach to reinforcement learning. Advances in Neural Information Processing Systems, 31.\n\nRajeswaran, A., Lowrey, K., Todorov, E. V., & Kakade, S. M. (2017). Towards generalization and simplicity in continuous control. Advances in Neural Information Processing Systems, 30.\n\n\nSchulman, J., Levine, S., Abbeel, P., Jordan, M., & Moritz, P. (2015, June). Trust region policy optimization. In International conference on machine learning (pp. 1889-1897). PMLR.\n\nVicol, P., Metz, L., & Sohl-Dickstein, J. (2021, July). Unbiased gradient estimation in unrolled computation graphs with persistent evolution strategies. In International Conference on Machine Learning (pp. 10553-10563). PMLR."}, {"review_id": "Aarsa8A0qI", "reviewer": "Reviewer_FJdn", "summary": "This work proposes a method for optimizing unrolled computation graphs (e.g. recurrent networks, etc.). When using ES to optimize a computation graph, the graph must be fully rolled out. Recent methods (PES) have examined using a truncated window to optimize, so that optimization can occur without a full unroll. PES aims to unbias the estimator by accumulating truncation noise during an online rollout, however, it produces high variance. \n\nThis paper presents a generalization to PES, GPES, that decouples the frequency of noise injection and gradient estimation. A specific instantiation, named NRES, samples the noise only once per episode. This reduces variance as it removes the need for noise accumulation. \n\nExperiments are presented on a two-parameter chaotic Lorenz system, where NRES outperforms previous work. An RNN-based meta-learning setup is also evaluated wherein the transition function defines an update over inner parameters, along with a reinforcement learning setup to solve Mujoco tasks.", "questions": "How does NRES compare to FullES in terms of pure computational budget? What are the scaling patterns of additional parallelization?\nHow do non-ES methods perform on the Mujoco tasks?\n\nAdditionally, ablations on hyperparameters such as the noise variance and # of workers would grant insight into the nuance of the method.\n", "limitations": "Limitations are discussed in section 7 -- they largely relate to ES in general. ", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper provides an extremely thorough investigation of their proposed framework. The framework includes a generalization of previous work, along with a theoretically-justified instantiation with desirable properties on unbiased estimation and low variance. This is an original idea that is promising. The quality and clarity of the writing is excellent. The work sets up for additional work in investigating the properties of GPES methods, including variations on the proposed NRES.", "weaknesses": "The final experiments on meta-learning and reinforcement learning are lacking detail. A more precise experimental setup would strengthen the argument of the paper. In addition, comparisons to non-ES based methods would give more context on how such methods compare to other solutions in the field. The experiments present wall-clock time as the unified axis, but discussion in the paper mentions total computation budget -- a figuring comparing the methods using some consistent measure of computation would strengthen the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the quality and clarity of our writing and the originality of our idea.\n\n**Experiment details**.\nWe have provided detailed descriptions of the experimental set ups and how we have tuned the hyperparameters for each experiment in Appendix E. We will make this more obvious in the main paper.\n\n**Comparison against non-ES based methods**.\nThe primary non-ES methods we compare against are automatic differentiation gradient estimation methods. As we have explained in line 58-63, AD methods struggle to be useful in problems with chaotic loss surfaces. For these problems, we have already compared against $4$ AD methods on the Lorenz task and the learned optimizer task in our experiments. Because AD methods all perform worse than ES methods (line 241 and 261), we show their results in Figure 8 and 9 in the Appendix.\n\n**Measure of computation**.\nThere are naturally two ways to measure the amount of computation an optimization algorithm needs to reach a given performance level on unrolled computation graphs: \n* **Measure 1**:  the total number of unrolls, which characterizes the total amount of work (energy) used by the algorithm. In reinforcement learning, this measure is also treated as the empirical sample complexity. \n* **Measure 2**: the number of sequential unrolls, which is linearly proportional to the theoretical wall clock time a parallel algorithm needs assuming good implementation and computing hardware.\n\nSince we focus on parallel ES algorithms, our primary measure of computation is through Measure 2 (we use Measure 2 for the RL experiments in the paper). Empirically, we have also compared ES algorithms by the actual wall-clock time and calculated how many times NRES improves over other methods. This actual wall-clock improvement is a conservative estimate of NRES’s theoretical wall-clock improvement captured by Measure 2 because we only use a single GPU card (which has a limited amount of parallelization ability). However, the actual wall-clock speed up should approach the theoretical speed up (Measure 2) as we scale up on the amount of compute hardware.\n\n**Comparing NRES and FullES in terms of pure computation budget**. Despite our focus on Measure 2, we also observe an improvement in Measure 1 (total number of unrolls) because of the variance reduction benefit of NRES over FullES (Theorem 8). We have provided the statistics of both measures for the RL experiments in Table 3 in the Appendix. In the Table below, we redisplay these results for RL and additionally provide these measures for the meta-training learned optimizer task in Figure 5(a). Here we see that NRES is not only significantly more parallelizable than FullES (Measure 2), but also reduces the total amount of compute/sample (Measure 1).\n\n|| reach 0.61 loss in learned optimizer||solve Mujoco Swimmer||solve Mujoco Half Cheetah||\n|-|-|-|-|-|-|-|\n||# of sequential unrolls (Measure 1)|# of total unrolls (Measure 2)|# of sequential unrolls|# of total unrolls|# of sequential unrolls|# of total unrolls|\n| FullES  | $2.46 \\times 10^6$  | $4.92 \\times 10^7$ | $2.50 \\times 10^4$ | $1.50 \\times 10^5$  |  $6.28 \\times 10^5$  | $7.54 \\times 10^6$  |\n| NRES | $\\mathbf{1.95 \\times 10^4}$  | $\\mathbf{4.00 \\times 10^6}$  |  $\\mathbf{2.40 \\times 10^3}$ |  $\\mathbf{1.11 \\times 10^5}$ |  $\\mathbf{1.02 \\times 10^4}$  | $\\mathbf{5.81 \\times 10^6}$ |\n\n**Non-ES methods on the Mujoco task**.\nAs the Mujoco task’s transition dynamics do not support automatic differentiation, the most relevant methods are policy gradient methods, which require having stochastic policy and apply likelihood ratio (LR) gradient estimation in the action space. (In contrast, ES applies LR in the parameter ($\\theta$) space and can handle deterministic policy). We compare the reported results by Rajeswaran et al which have used natural policy gradient to train linear policies on the two Mujoco tasks we have considered in this paper:\n||Number of environment steps to solve||\n|-|-|-|\n||Swimmer|Half Cheetah|\n|(Rajeswaran et al) + stochastic linear policy|$1.45 \\times 10^6$|$1.13 \\times 10^7$|\n|NRES (ours) + deterministic linear policy|$\\mathbf{1.11 \\times 10^5}$|$\\mathbf{5.81 \\times 10^6}$|\n\nAs we can see, NRES improves over this policy gradient method in solving these Mujoco tasks.\n\nRajeswaran, A., Lowrey, K., Todorov, E. V., & Kakade, S. M. (2017). Towards generalization and simplicity in continuous control. Advances in Neural Information Processing Systems, 30.\n\n\n**Ablation on the noise variance $\\sigma$**.\nAs we have described in line 946, all ES methods require tuning the hyperparameter $\\sigma$ which controls the variance of the smoothing distribution: on the one hand, setting $\\sigma$ too small might not provide sufficient loss smoothing, making the optimization difficult to converge. On the other hand, setting $\\sigma$ too large might shift the global optimum of the smoothed surface away from the true minimum. Following the reviewer’s suggestion for an ablation, we provide experiments on the impact of $\\sigma$ on both NRES and FullES’s performance on the Mujoco Half Cheetah task in Figure 2 in the common response pdf (where we have tuned the learning rate for each value of $\\sigma$ and each method separately). Here we see that although insufficient amount of loss smoothing ($\\sigma = 0.001$) could lead to slow convergence, there exists a range of hyperparameters ($\\sigma=0.004$ and $\\sigma=0.01$) that can allow both ES methods to solve the task. For both cases, NRES improves significantly over FullES.\n\n**Ablation on the number of workers $N$**.\nAs the NRES workers are independent, the variance of the average of their gradient estimates scales with $1/N$. We provide an experiment on the impact of $N$ on NRES’s performance on the Mujoco Swimmer task in Figure 3(a) in the common response pdf. We see that having more workers can reduce the number of sequential steps to converge but also require a greater cost per sequential step."}, {"review_id": "Z7NQSLtA9J", "reviewer": "Reviewer_hYKW", "summary": "This paper generalizes PES based on noise-reuse, generating a more general class of unbiased online ES gradient estimators. The authors analytically characterize the variance of the estimators and identify the lowest-variance estimator named Noise-Reuse Evolution Strategies (NRES). Experiments on learning dynamical systems, meta-training learned optimizers, and reinforcement learning show that NRES results in faster convergence than existing AD and ES methods in terms of wall-clock time and number of unroll steps.", "questions": "1. In Theorem 8, it's said that the required assumption often holds in real-world applications. Can you give more explanation and evidences?\n\n2. In the experiments, the x-axis of figures is measured by wall-clock time. Why not use the number of iterations?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper proposes a general framework GPES by generalizing the existing PES algorithm based on noise-reuse.\n2. The paper gives a theoretical analysis of unbiasedness and variance for GPES, and identifies the lowest-variance gradient estimator under this setting named NRES, which always reuses noise.\n3. The paper proves that under some reasonable conditions, NRES has lower variance than FullES.\n", "weaknesses": "1. The proposed GPES is a simple and direct generalization of the existing PES. The novelty is not very strong.\n\n2. The experiments need to be improved, e.g., adding the empirical comparison on longer sequences and higher dimension problems.\n\n3. Why GPES can be better than PES? An intuitive explanation is needed.\n\nMinor issue: Step-unlocked is used without explanation.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Novelty of the contribution**. We agree with the reviewer that our proposed class of unbiased online ES gradient estimators GPES is a simple, intuitive generalization of PES. (In fact, we view the simplicity of the method as an important practical benefit.) However, _we respectfully disagree that our work lacks novelty_, as the main contributions of our paper aren’t only in introducing this class but more importantly in:\n1. providing a theoretical characterization of the total variance of this class of estimators;\n2. provably identifying the estimator NRES has the least total variance within this class;\n3. empirically verifying the improvement of NRES over PES and other GPES estimators.\n\n**More experiments on longer sequences and higher-dimensional problems**.\nWe believe our current experiments’ scale is already sufficient to prove NRES’s advantage over other ES baselines, and note that the scale is comparable to the scale considered in the most relevant prior work PES (which also uses $d \\le 2000$ and $T$ around $1000$). However, to further demonstrate our algorithm NRES’s ability in handling higher-dimensional and longer sequence problems, we provide more experiments in the common response (Figure 1 in the attached pdf). To summarize the result, we increase the parameter dimension $d$ and sequence length $T$ each by (more than) $10\\times$ on the learned optimizer task. For both cases, our proposed method still achieves significant wall-clock savings over all other ES methods.\n\n**Intuitive explanation of why GPES can be better than PES?**\nWe do not claim that any GPES estimator is better than PES. Instead, we prove through Theorem 5 and Corollary 6 that NRES is better than other GPES estimators (including PES) due to its least amount of total variance. We thus assume the reviewer is asking for the intuition of _why NRES has lower variance than PES_ (please let us know if that’s not the case):\n\nLet’s consider size $W=1$ truncation window for simplicity. When PES and NRES unroll over the same time step $t$, both methods aim to estimate the **total derivative** of step $t$’s smoothed loss ($\\widehat{L_t}$) with respect to $\\theta$: $\\frac{d\\widehat{L_t}([\\theta]\\_{\\times t})}{d\\theta}$ (notice $\\theta$ has been repeatedly applied $t$ times to compute this loss). This total derivative is equal to the sum of partial derivatives $\\frac{d\\widehat{L_t}}{d\\theta} = \\sum_{i=1}^t \\frac{\\partial \\widehat{L_t}}{\\partial \\theta_i}$, where each term is with respect to the $i$-th time step’s application of $\\theta$. By applying a new gaussian noise at every time step, PES can produce an unbiased estimate of each partial derivative. In contrast, because NRES uses the same gaussian noise for all time steps, it cannot individually estimate each partial but only their sum. However, to optimize $\\theta$, we only need this sum (i.e. the total derivative) but not the individual terms. _The cost PES pays for having a separate yet unused estimation for each partial derivative is a larger variance than NRES_, since it needs more randomness to obtain this extra information. We will add this intuitive explanation to the paper as a remark.\n\n**Understanding why Theorem 8’s assumption often holds in real world**.\nTo understand our claim that Theorem 8’s assumption often holds in the real world, we can reorganize our explanation in line 200-207 in three steps: \n1. In many real world applications of unrolled computation graphs, if we update the parameter $\\theta$ using the loss gradient from a specific truncation window, the losses in other truncation windows will also decrease. This is because there is a correlation between performing well at different time steps. For example, in a learned optimization task, the inner model parameters gradually improve during the training by a learned optimizer. Here, if the inner model over the last truncation window achieves lower validation losses (thus improved generalization), the earlier windows’ inner model snapshots will likely also generalize better and have lower validation losses.\n2. Given Step 1’s observation, we can conclude that different truncation window losses’ total derivatives with respect to the same $\\theta$ should largely point in the same direction. (Otherwise Step 1 would not be observed).\n3. When different truncation windows’ gradients are pointing in similar directions, the assumption (Equation (10)) in Theorem 8 would hold true. To see this intuitively, consider the extreme case where each window’s gradient (the vector $\\sum_{t=W(k-1) + 1}^{Wk} g^t$) lies exactly in the same direction (on the same line). In this case, Equation (10) is almost trivially satisfied.\n\nWith the above three steps, we see that Theorem 8’s assumption would often hold true in the real world. We have also provided empirical verification of Theorem 8’s conclusion under this assumption in Figure 3(b) in the main paper, which provides further evidence that such assumptions would hold in real applications.\n\n**Why use wall-clock time instead of number of iterations?**\nSince our work focuses on parallel ES methods, we choose measures of computation that can allow us to compare the parallelizability of these algorithms in terms of actual/theoretical time they take to run. Number of iterations is not such a measure, because _different algorithms could require significantly different amounts of time to run while still using the same number of update iterations and total computation_. For example, given the same computation budget of $2T$ unrolls per update, FullES can only afford to run 1 worker from start to finish, thus taking $T$ units of time per update. In contrast, NRES can simultaneously run $T/W$ independent workers each over a truncation window of length $W$, in total taking only $W$ units of time because of the parallelization. In this case, NRES can achieve a $T/W\\times$ time speed up over FullES even if they use the number of iterations to converge (see line 191-195). \n"}, {"review_id": "L6NnhcJqxZ", "reviewer": "Reviewer_w7MW", "summary": "The study considers numerically estimating gradients for online (reinforcement) learning.\nThe parameters are perturbed and from the performance of the perturbed models the gradient is estimated.\nIn an online setting, the proposed method decouples the number of steps between gradient estimates (which are then used by a first order gradient based optimiser) and the number of steps between changing the perturbation.\nTwo aspects are relevant in the paper: The variance of the gradient estimate and the ability to parallelise the methods.\n", "questions": "\n* What is the exact definition of a  „chaotic loss surfaces“? Where is the proof that the Lorenz „loss surface“ is really chaotic when changing r and a?\n* Under the used „sequential environment steps“ measure, would a  global random search algorithm that  which evaluates 10^50 independent random policies only have a cost of one? Would this be the ultimate baseline method, outperforming all proposed algorithms? \n\n\n", "limitations": "OK", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "I could not find anything that I would call wrong in the manuscript.\n\n", "weaknesses": "Allmost all research is to a certain degree incremental. The main problem of the research presented in the paper that is that the increment is rather small, it lacks originality and novel „surprising“ insights. \n\nThe problem setting is not new.\nThe proposed algorithm, as properly stated in the manuscript, can be viewed as a slight generalisation of „Persistent evolution strategies“ [13].\nThe canonical way to apply a Monte Carlo method such as ES to non-episodic RL tasks is to split the state-action-reward sequence into „pseudo-episodes“ . This is also done/suggested in other other non-ES RL algorithms, e..g., in \tProximal Policy Optimization. This is also sometimes referred to as truncation. \nThe problem of how many (pseudo-)episodes are needed to evaluate a perturbation to get a reliable signal to be exploited by ES for RL has also been studied, for example see \nHeidrich-Meisner and Igel. Hoeffding and Bernstein Races for Selecting Policies in Evolutionary Direct Policy Search. ICML 2009\n\nTwo aspects are relevant in the paper: The variance of the gradient estimate and the ability to parallelise the methods. The first one leads to a non-surprising result, which was simultaneously discovered in another work, properly cited by the authors: [19].\nIn my evaluation, the patalllization, while being useful in practice, is rather technicality.\n\nThe discussion the (parallel) runtime is partly not convincing.\nI understand that \n1. FullES takes O(T) time, it sees the states from s^+_0 to s^+_T (and s^-_0 to s^-_T)\n2. calling Algorithm 2 takes O(W) time, it sees the states s^+_tau to s^+_tau+W (and s^-_tau to s^-_tau+W)\n3. T/W independent calls of Algorithm 2 can be fully parallelised, so on T/W nodes taking the average over T/W independent calls starting from the same state s+ / s- also takes O(W) time\n(Please correct me if I am wrong).\n\nSo I think „Under perfect parallelization, the entire  NRES gradient estimation would require O(W) time to complete. In contrast, the single FullES  gradient estimate has to traverse the UCG from start to finish, thus requiring O(T) time. Hence, NRES is T /W times more parallelizable than FullES with the same compute budget.“ is a bit misleading. Because a single FullES  gradient estimate sees all steps from 0 to T, while Algorithm 2 looks at several „parallel“ trajectories starting from the same state running for W steps. I think this is qualitatively different. In the RL setting, you cannot in general not replace   information collected over a time period with information collected from an ensemble where the ensemble members start from the same state. Think of an RL task where the rewards are always zero in the first 0.99*T steps.  \n\nThe „Instead, we aim to compare the pure performance of different ES methods   assuming perfect parallel implementations. To do this, we measure a method’s performance as a  function of the number of sequential environment steps it used. Sequential environment steps are    steps that have to happen one after another (e.g., the environment steps within the same truncation window). However, steps that are parallelizable don’t count additionally in the sequential steps.“ \nThis means that global random search, which evaluates 10^50 independent random policies has only a cost of one?\nThis would then be the ultimate baseline method, outperforming all proposed algorithms. \n\nThe manuscript lacks clarity. For example, some statements about „chaotic loss surfaces“ are confusing. Being chaotic is a well defined mathematical property.\nIt starts to make sense in the experiments. The Lorenz system is chaotic, which inmates the first place refers to perturbations of the system state.\nThe experiments always start from the same initial state. Optimised are the coefficients of the Lorenz system. What is the exact definition of a  „chaotic loss surfaces“? Where is the proof that the loss surface is really chaotic when changing r and a (citation missing). \n\nA comparison with an evolution strategy that uses the perturbations also for the update, such as (1+1) CMA-ES with restricted covariance matrix) would have been interesting.\n\nHyperparameter tuning seems to be crucial. The description in the appendix is appreciated. \nThe Lorenz training suffers from instabilities. There are countermeasures, like gradient clipping.\nOne could also move to an optimiser that decouple gradient magnitude and update step length, for example Adam. Adam is used later, but for the \nLorenz experiments the manuscript sticks to SGD. How are the results with Adam (and corresponding learning rate tuning)?\nThis may be important because the experiments lead to to strong statements „AD methods perform worse than ES methods“ (Appendix) and one has to rule out that the problem is not the optimiser but really the AD as such.\n\n\n\nMinor:\n\n* Instead of talking about a trick and adding a reference, simply state that you use \\nabla_theta E_x~p(x|theta) [ f(x) ] = E_x~p [ f(x)  \\nabla_theta \\ln p(x|theta), that is clearer (referring to this as a trick makes me cringe).\n\n* The embedding in the existing literature is weak. One may not need no go back to Rechenberg and Schwefel when talking about evolution strategies (although it does not harm), but citing [12] as the only source for evolution strategies for RL is in my evaluation not OK.\n* The first epsion in line 73should be in bold font.\n* The hyperparameters are relevant, the main paper should point out to the appendix where the hyperparameters selection is discussed more clearly.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Originality of contribution**.\nIt is correct that NRES, while being simpler to implement than PES, is not a large algorithmic deviation from PES. However, the insight that reusing noise in truncation windows can both theoretically and empirically achieve significant variance reduction for unbiased online ES methods is a major and novel contribution of our paper. We want to emphasize that it is the combination of 1) noise reuse and 2) truncation that makes our contribution unique and novel. In contrast, the references the reviewer provides only consider either of these two ideas individually: on the one hand, it is true that the non-ES literature has explored the idea of truncation windows before, but such prior works have not considered the noise reuse aspect over multiple such windows. On the other hand, although the paper by Heidrich-Meisner and Igel evaluates a perturbation ($\\theta$ plus noise) multiple times (similar to the idea of noise reuse), every such evaluation is an independent sample over the entire episode but not over a random truncation window. We believe the existence of these prior works on each concept alone does not diminish the contribution of our work. In addition, we note that we have provided a detailed discussion in Section B (line 507-541) of the various aspects our work differs and improves over the contemporaneous work of [19] in analyzing online ES algorithms.\n\n**Understanding the parallelization argument**.\nUnfortunately, the reviewer’s summary of how NRES is parallelized is incorrect. The reviewer assumes that all the parallel $T/W$ NRES workers would start unrolling from the same pair of antithetic states $s_+$ and $s_{-}$, thus covering the same truncation window. However, as shown in Figure 2(a), for an NRES update, each NRES worker would each maintain its own pair of antithetic states (see Algorithm 2) and would independently work at different truncation windows (we call these independent workers _step-unlocked_ (line 90-92)). By independence, different workers’ truncation windows should largely be non-overlapping and collectively cover almost all of the possible truncation windows in an episode. Thus the reviewer’s question of having no NRES worker cover the last $1\\\\%$ of an episode length for multiple updates would not be possible under our assumption and implementation.\n\n**Measuring the number of sequential steps of global random search**.\nIn our RL Mujoco experiments, we have constrained the total number of environment steps per gradient update to be equal for all the ES methods (line 289). For example, on the Swimmer task, both FullES and NRES use a total of 6000 steps per update. This would have prevented the reviewer’s degenerate case of using $10^{50}$ of parallel workers in global random search at the cost of only a single episode worth of sequential steps $T=1000$. Besides, using $10^{50}$ episodes would also compare unfavorably in the total number of environment steps needed to solve a task, where we also show NRES is the best among all the ES methods.\n\n**What does _chaotic_ mean?** Mathematically, a function being chaotic means the function’s output is extremely sensitive to small changes in the function’s input. However, chaotic can be used to describe different functions in different contexts: when we say the Lorenz system is chaotic, the chaotic function is the dynamical system which maps from an initial state to a future state evolved under its dynamics. In contrast, _when we say the Lorenz system has a chaotic loss surface, the chaotic function is the loss function, which maps from the learnable parameter $\\theta$ to its loss value_. Prior works on TES and PES have both used the term “chaotic” to describe the loss surfaces arising from unrolled computations. Thus we believe we use the term “chaotic” clearly and in a manner consistent with prior work. We have also shown that the Lorenz task’s loss surface is indeed chaotic through the visualizations in Figure 4(a) (left panel) and Figure 7. For example, in Figure 7(b), we see that the loss has extreme oscillations on the line segment connecting the initialization and ground truth parameters. If the reviewer believes there are other portions of our paper that lack clarity, please let us know.\n\n**Comparison against (1 + 1) CMA-ES with restricted covariance matrix**.\nOur paper focuses on online evolution strategies that use truncation windows for gradient estimation. We have compared against the offline method FullES because the online ES methods stem from it and prior works haven’t theoretically and experimentally analyzed the benefit of online ES over FullES. However, beyond FullES, we believe other offline ES methods (such as (1+1) CMA-ES) do not fit into the comparison scope of our current paper. We leave holistic comparisons of different classes of ES methods as future work.\n\n**Adam or gradient clipping cannot help automatic differentiation methods learn on the Lorenz task**.\nWhen the loss surface has extreme sensitivity and many suboptimal local minima, not only can the gradient’s magnitude become extremely large, but the gradient’s direction can also become non-informative. The alternative methods the reviewer proposed (gradient clipping or Adam optimizer) can potentially handle the cases of extreme gradient magnitude, but are not suitable to handle such non-informative gradient direction problems. Experimentally, we have tried using Adam with learning rates spanning over 9 different orders of magnitude ($10^{-1}$ to $10^{-9}$) and also gradient clipping over 3 orders of magnitude of thresholds. Under all of these optimizer hyperparameters, we are unable to make the de facto automatic differentiation methods backprop through time (BPTT) to reach a loss of lower than 300 (initialization loss is at 312) on the Lorenz task (where NRES and FullES can reach a loss lower than 50), thus proving the issue really lies in the AD gradient estimation methods but not in the chosen optimizers.\n"}]

Author rebuttal:
We want to thank all the reviewers for your reviews and comments. We address each reviewer’s questions and feedback in an individual response. For new plots created for the rebuttal, we have included them in the uploaded pdf in this common response. Below is a summary of the new plots in the pdf:
* **Figure 1(a) (Reviewer hYKW)**: We compare ES gradient estimators on an $11 \times$ higher-dimensional ($d=19330$) learned optimizer task than that considered in Figure 5(a). To increase the parameter dimension, we increase the width of the multilayer perceptron used by the learned optimizer. For this higher-dimensional problem, NRES can still provide a $3.8\times$ wall clock time speed up over PES and a $9.7 \times$ wall clock time speed up over FullES.
* **Figure 1(b) (Reviewer hYKW)**: We compare ES gradient estimators on the learned optimizer task with a $10\times$ longer sequence length ($T=10000$) than that considered in Figure 5(a). For this problem, NRES still achieves a $2.1 \times$ wall clock speed up over PES and a $3.5 \times$ speed up over FullES.
* **Figure 2 (Reviewer FJdn)**: We perform an ablation study on the impact of the noise variance $\sigma^2$ on the performance of FullES and our proposed method NRES in solving the Mujoco Half Cheetah task. While setting $\sigma$ too small makes both methods fail to to solve the task, there still exists a range of larger $\sigma$ values under which both methods can solve the task successfully. For these cases, NRES always achieves a more than $50\times$ reduction in the number of sequential steps used over FullES. 
* **Figure 3(a) (Reviewer FJdn)**: We perform an ablation study on the impact of the number of workers $N$ on the performance of NRES in solving the Mujoco Swimmer task. Here, increasing $N$ can help NRES use fewer sequential steps to solve the task but at a larger per sequential step compute cost.
* **Figure 3(b) (Reviewer 77pb)**: We compare ES gradient estimators on training a non-linear, ($6.5\times$) higher-dimensional policy network on the Mujoco Half Cheetah task under a fixed budget of total number of environment steps. Only our proposed method NRES has solved the task.


Meta-review: This work introduces an evolution strategies method for unrolled computation graphs. In these problems usually the graph needs to be fully rolled out. Existing methods get around this problem by considering truncated optimization windows to optimize. This method instead (PES) introduces a way to compute an unbiased estimator by accumulating truncation noise during an online rollout. The new method is evaluated on a couple of experimental benchmarks. The reviewers agreed this is a meaningful contribution to the ES literature and thus I recommend its acceptance to the conference.
Decision: Accept (poster)