Correspondence between neuroevolution and gradient descent — part 2/3
Cleaned-text code points [15884, 31733). Bibliography omitted here; source.md includes it.
is the output of a single-layer neural network with one input node, one output node, M = 30 hidden nodes, and N = 3 M parameters x i . These parameters are initially chosen to be Gaussian random numbers with zero mean and variance \({\sigma }_{0}^{2}=1{0}^{-4}\) . The correspondence is insensitive to the choice of initial conditions, and we shall show that it holds for different choices of initial network.
We performed gradient descent with learning rate α = 10 −5 . We chose the learning rate arbitrarily, and verified that the results of gradient-descent simulations were unchanged upon a changing learning rate by a factor of 10 and 1/10. We used Euler integration of the noise-free version of Eq. ( 6 ), updating all weights x i at each timestep t gd = 1, 2, … according to the prescription
where
and
We did neuroevolution following the Monte Carlo procedure described in section “Neuroevolution”, in the limit β = ∞ , i.e., we accepted only moves that did not increase the loss function. We chose the mutation scale
where λ is a parameter. According to ( 6 ) and ( 12 ), this prescription sets the neuroevolution timescale t evol to be a factor λ times that of the gradient-descent timescale. Thus, one neuroevolution step corresponds to λ integration steps of the gradient descent procedure. In figures, we compare gradient descent with neuroevolution as a function of common (scaled) time t = α t gd = α λ t evol .
In Fig. 1 (a) we show the evolution of four individual weights under neuroevolution (using mutation scale λ = 1/10) and gradient descent (weights are distinguishable because they always have the same initial values). The correspondence predicted analytically can be seen numerically: individual neuroevolution trajectories (gray) fluctuate around the gradient descent result (black), and when averaged over individual trajectories the results of neuroevolution (green) approximate those of gradient descent. In Fig. 1 (b) we show the individual and averaged values of the weights of neuro-evolved networks at time t = 10 compared to those of gradient descent. In general, the weights generated by averaging over neuroevolution trajectories approximate those of gradient descent, with some discrepancy seen in the values of the largest weights. In Fig. 1 (c) we show the loss under neuroevolution and gradient descent. As predicted by ( 9 ), averaged neuroevolution and gradient descent are equivalent.
a Evolution with time of 4 of the 90 weights of the neural network ( 11 ) under the gradient descent equation Eq. ( 12 ) (black: “gradient” stands for “gradient descent”), and under neuroevolution with mutation scale λ = 1/10 [see ( 14 )]. Here and in subsequent panels we show 25 independent neuroevolution trajectories (gray, marked “evolution”) and the average of 1000 independent trajectories (green, marked “ \(\left\langle {{{\rm{evolution}}}}\right\rangle \) ”). b All weights at time t = 10 under the two methods. c Loss as a function of time.
In Supplementary Fig. 1 we show similar quantities using a different choice of initial neural network; the correspondence between neuroevolution and gradient descent is again apparent.
In Fig. 2 (a) we show the time evolution of a single weight of the network under gradient descent and neuroevolution, the latter for three sizes of mutation step σ . As σ increases, the size of fluctuations of individual trajectories about the mean increase, as predicted by ( 6 ). As a result, more trajectories are required to estimate the average, and for fixed number of trajectories (as used here) the estimated average becomes less precise. In addition, as σ increases, the assumptions underlying the correspondence derivation eventually break down, in which case the neuroevolution average will not converge to the gradient descent result even as more trajectories are sampled.
a Time evolution of a single neural-network weight, for three different neuroevolution mutation scales [see ( 14 )]. b The quantity Δ( t ), Eq. ( 15 ), is a measure of the difference between networks evolved under gradient descent and neuroevolution.
In Fig. 2 (b) we show the mean-squared difference of the parameter vector of the model under gradient descent and neuroevolution,
Here, N is the number of network parameters; \({x}_{i}^{{{{\rm{gradient}}}}}(t)\) is the time evolution of neural-network parameter i under the gradient descent equation Eq. ( 12 ); and \(\left\langle {x}_{i}^{{{{\rm{evolution}}}}}(t)\right\rangle \) is the mean value of neural-network parameter i over the ensemble of neuroevolution trajectories. The smaller the neuroevolution step size, the smaller is Δ( t ), and the closer the neuroevolution-gradient descent correspondence.
In Supplementary Fig. 2 we show the evolution with time of the loss for different mutation scales (the left-hand plot is a reproduction of Fig. 1 (c)). The trend shown is similar to that of the weights in Fig. 2 .
#### Deep net, β = ∞
One feature of the correspondence derivation is that the architecture of the neural network does not appear. As long as the loss U ( x ) is a deterministic function of the neural-network parameters x , correspondence between gradient descent and neuroevolution will be observed if the mutation scale is small enough (it is likely that what constitutes “small enough” does depend on neural-network architecture, as well as the problem under study. The required mutation scale can be determined empirically, even without access to gradient-descent results: when correspondence holds, the results of neuroevolution simulations will be statistically similar, when scaled as we have described).
To demonstrate invariance to architecture we repeat the previous comparison, now using a deep neural network (we train the net to reproduce the target function \({f}_{0}(\theta )=\sin (\pi \theta )\) on the interval θ ∈ [ − 1, 1]). The network has 8 fully-connected hidden layers, each 32 nodes wide, and 7489 total parameters. As before we use tanh activations on the hidden nodes, and have one input node and one output.
Results are shown in Fig. 3 . In panel (a) we show the evolution of two parameters of the network, under gradient descent and for neuroevolution with step-size parameter λ = 1/10 [see ( 17 )]. As for the shallow net, the correspondence is apparent. Neuroevolution averages (green lines) are taken over 100 trajectories. In panel (b) we show the loss, for gradient descent and two different neuroevolution step-size parameters. As expected, the correspondence is more precise for smaller λ . As before, for large enough λ the correspondence breaks down: see Supplementary Fig. 3 .
Panel a shows 2 of the 7489 parameters of the network. Panel b shows the loss, for two different neuroevolution step-size parameters [see ( 17 )].
In Fig. 4 we show all parameters of the deep net at training time t = 5, under the two dynamics. We show the results of gradient descent in black, and independent neuroevolution trajectories in gray. As predicted analytically, the neuroevolution results fall either side of the gradient-descent result, and the network constructed by averaging over independent neuroevolution trajectories (green) is essentially identical to the network produced by gradient descent.
We show all 7489 parameters x i of the deep net of Fig. 3 at training time t = 5. As predicted analytically, the neural network created by averaging (green symbols) over a noninteracting population of neuroevolutionary processes (gray symbols) is essentially the same network as that produced by gradient descent (black symbols). For clarity, weights are ordered by their final values under gradient descent.
In Fig. 5 , we illustrate the dynamics of learning and the scale of the loss function by showing a comparison between the target function \({f}_{0}(\theta )=\sin (\pi \theta )\) and the net function f x ( θ ). We show the latter at three different training times, for gradient descent and neuroevolution trajectories.
Loss versus time and comparison of the target function \({f}_{0}(\theta )=\sin (\pi \theta )\) and the net function f x ( θ ) at three different training times, for the learning dynamics of Fig. 3 ( λ = 1/10 for the neuroevolution results).
#### Shallow net, finite β
In this section, we illustrate the gradient descent-neuroevolution correspondence for finite β . We consider the same supervised-learning problem as before, and set the network width to 256 nodes. We did neuroevolution with the Metropolis acceptance rate with reciprocal temperature parameter β = 10 3 . This choice is arbitrary, but is representative of a wide range of finite values of β . Finite-temperature simulations are common in particle-based systems 24 . Here, temperature has no particular physical significance, but comparing simulations done at finite and infinite β makes the point that different choices of neuroevolution acceptance rate result in a dynamics equivalent to different gradient-descent protocols.
We did gradient descent using the integration scheme
where α = 10 −4 is the learning rate. Comparing ( 3 ) and ( 16 ), we set the neuroevolution mutation scale to be
where λ is a parameter. Thus, one neuroevolution step corresponds to λ integration steps of the gradient descent procedure. In figures, we compare gradient descent with neuroevolution as a function of common (scaled) time t = α t gd = α λ t evol .
Results are shown in Fig. 6 , for step-size parameter λ = 1. In panel (a) we show the evolution with time of two of the weights of the network. The noise associated with neuroevolution at this value of β is considerable: individual trajectories (gray lines) bear little resemble to the gradient-descent result (black line). However, the population average (green line, average of n = 1000 trajectories) shows the expected correspondence. The correspondence is less precise than that shown previously, because we use a larger effective step size and each trajectory is much noisier than its infinite- β counterpart.
Panel a shows two parameters of the network, panel b shows the loss, and panel c shows the parameter Δ, Eq. ( 15 ), a measure of the difference between the average network produced by neuroevolution and the network produced by gradient descent.
In Fig. 6 (b) we show the loss, with line colors corresponding to the quantities of panel (a). In addition, we show the loss of the average network produced by neuroevolution (red line), \(U(\left\langle {{{\bf{x}}}}\right\rangle )\) , which, if correspondence holds, should be equal to \(\left\langle U({{{\bf{x}}}})\right\rangle \) (green line). The initial fast relaxation of the loss (the boxed region) shows a difference between gradient descent and averaged neuroevolution results; doing neuroevolution for smaller step-size parameter λ = 1/10 (inset) reduces this difference, as expected.
In panel (c) we show the parameter Δ, Eq. ( 15 ), a measure of the difference between the average network \(\left\langle x\right\rangle \) produced by neuroevolution and the network produced by gradient descent, as a function of n , the number of trajectories included in the average. If correspondence holds, this quantity should vanish in the limit of large n ; the observed trend is consistent with this behavior.
In Supplementary Fig. 4 , we compare a gradient-descent trajectory with a set of neuroevolution trajectories, periodically resetting the latter to the gradient-descent solution. The periodic resetting tests the correspondence for a range of initial conditions. The correspondence between gradient descent and the averaged neuroevolution trajectory is approximate (averages were taken over 152 trajectories, fewer than in Supplementary Fig. 4 ) but apparent.
### Conclusions
We have shown analytically that training a neural network by neuroevolution of its weights is equivalent, in the limit of small mutation scale, to noisy gradient descent on the loss function. Conditioning neuroevolution on the Metropolis acceptance criterion at finite evolutionary temperature is equivalent to a noisy version of simple gradient descent, while at infinite reciprocal evolutionary temperature the procedure is equivalent to clipped gradient descent on the loss function. Averaged over noise, the evolutionary procedures correspond to forms of gradient descent on the loss function. This correspondence is described by Equations ( 3 ), ( 5 ), ( 6 ), and ( 8 ).
Correspondence in the sense described above means that each neural-network parameter evolves the same way as a function of time under the two dynamics. Correspondence implies that the convergence properties of the two methods are the same (see e.g., Fig. 3 (b)) and that the neural networks produced by the same methods are the same (see e.g., Fig. 4 ). The generalization properties of those networks will then also be the same.
The correspondence is formally exact only in the limit of zero mutation scale, and holds approximately for small but finite mutations. It will fail when the assumptions underlying the derivation are violated, such as when the terms neglected in ( 22 ) and ( 23 ) are not small, or when the passage from ( 28 ) to ( 29 ) is not valid because the change β U ( x + ϵ ) − β U ( x ) is not small. It is straightforward to determine empirically where correspondence holds, even without access to gradient-descent results: the results of neuroevolution, with time scaled as described, will be statistically similar when the mutation size is small enough. The time duration for which the correspondence holds increases with decreasing mutation scale (see e.g., Fig. 2 (b)). We have shown here that the correspondence can be observed for a range of mutation scales, and for different neural-net architectures.
More generally, several dynamical regimes are contained within the neurevolution master equation ( 19 ), according to the scale σ of mutations: for vanishing σ , neurevolution is formally noisy gradient descent on the loss function; for small but nonvanishing σ it approximates noisy gradient descent enacted by explicit integration with a finite timestep; for larger σ it enacts a dynamics different to gradient descent, but one that can still learn; and for sufficiently large σ the steps taken are too large for learning to occur on accessible timescales. An indication of these various regimes can be seen in Fig. 2 and Supplementary Fig. 2 .
Separate from the question of its precise temporal evolution, the master equation ( 19 ) has a well-defined stationary distribution ρ 0 ( x ). Requiring the brackets on the right-hand of ( 19 ) to vanish ensures that P ( x , t ) → ρ 0 ( x ) becomes independent of time. Inserting ( 20 ) into ( 19 ) and requiring normalization of ρ 0 ( x ) reveals the stationary distribution to be the Boltzmann one, \({\rho }_{0}({{{\bf{x}}}})={{{{\rm{e}}}}}^{-\beta U({{{\bf{x}}}})}/\int {{{\rm{d}}}}{{{\bf{x}}}}^{\prime} {{{{\rm{e}}}}}^{-\beta U({{{\bf{x}}}}^{\prime} )}\) . For finite β the neuroevolution procedure is ergodic, and this distribution will be sampled given sufficiently long simulation time. For β → ∞ we have \({\rho }_{0}({{{\bf{x}}}})\to \delta \left(U({{{\bf{x}}}})-{U}_{0}\right)\) , where U 0 is the global energy minimum; in this case the system is not ergodic (moves uphill in U ( x ) are not allowed) and there is no guarantee of reaching this minimum.
We have focused on the simple limit of the set of neuroevolution algorithms, namely a non-interacting population of neural networks that experience sequential probabilistic mutations of their parameters. We have illustrated the correspondence at the level of population averages, Equations ( 5 ) and ( 8 ). However, no communication between individuals is required, and each individually observes the correspondence defined by Equations ( 3 ) and ( 6 ).