Correspondence between neuroevolution and gradient descent — part 1/3

Cleaned-text code points [0, 15884). Bibliography omitted here; source.md includes it.

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

Advertisement

View all journals

Saved research

Search

Log in

Content Explore content

About the journal

Publish with us

Sign up for alerts

RSS feed

Article

Open access

Published: 02 November 2021

# Correspondence between neuroevolution and gradient descent

Stephen Whitelam ORCID: orcid.org/0000-0002-0086-6803 1 ,

Viktor Selin 2 ,

Sang-Won Park 1 &

…

Isaac Tamblyn 2 , 3 , 4

Nature Communications volume 12 , Article number: 6317 ( 2021 ) Cite this article

11k Accesses

21 Citations

21 Altmetric

Metrics details

## Abstract

We show analytically that training a neural network by conditioned stochastic mutation or neuroevolution of its weights is equivalent, in the limit of small mutations, to gradient descent on the loss function in the presence of Gaussian white noise. Averaged over independent realizations of the learning process, neuroevolution is equivalent to gradient descent on the loss function. We use numerical simulation to show that this correspondence can be observed for finite mutations, for shallow and deep neural networks. Our results provide a connection between two families of neural-network training methods that are usually considered to be fundamentally different.

### Similar content being viewed by others

### Gradient-based learning drives robust representations in recurrent neural networks by balancing compression and expansion

### Deep neural networks with controlled variable selection for the identification of putative causal genetic variants

### The neural coding framework for learning generative models

### Explore related subjects

Applied mathematics

Statistical physics

## Introduction

In broad terms there are two types of method used to train neural networks, divided according to whether or not they explicitly evaluate gradients of the loss function. Gradient-based methods include the backpropagation algorithm 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 . The non-gradient-based methods (sometimes called “black box” methods) include stochastic processes in which changes to a neural network are proposed and accepted with certain probabilities, and encompass Monte Carlo 9 , 10 and genetic algorithms 11 , 12 , 13 . Both gradient-based and non-gradient-based methods have been used to train neural networks for a variety of applications, and, where comparison exists, perform similarly well 14 , 15 , 16 , 17 . For instance, recent numerical work shows that stochastic evolutionary strategies applied to neural networks are competitive with explicit gradient-based methods on hard reinforcement-learning problems 16 .

Gradient-based- and non-gradient-based strategies are different in implementation and are sometimes thought of as entirely different approaches 18 . Here, we show that the two sets of methods have a fundamental connection. We demonstrate analytically an equivalence between the dynamics of neural-network training under conditioned stochastic mutations, and under gradient descent. This connection follows from one identified in the 1990s between the overdamped Langevin dynamics and Metropolis Monte Carlo dynamics of a particle in an external potential 19 , 20 . In the limit of small Monte Carlo trial moves, those things are equivalent. Similarly, we show here that a single copy of a neural network (a single individual) exposed to parameter mutations that are accepted probabilistically is equivalent, in the limit of small mutation size, to gradient descent on the loss function in the presence of Gaussian white noise. The details of the resulting dynamics depend on the details of the acceptance criterion, and encompass both standard- and clipped gradient descent. Such a mutation scheme corresponds to the simple limit of the set of processes called “neuroevolution” 13 , 16 , 21 , 22 , 23 . This connection demonstrates explicitly that optimization without access to gradients can, nonetheless, enact noisy gradient descent on the loss function.

In simple gradient descent, equivalent to noise-free overdamped Langevin dynamics, the parameters (weights and biases) x of a neural network evolve with training time according to the prescription \(\dot{{{{\bf{x}}}}}=-\alpha \nabla U({{{\bf{x}}}})\) . Here, α is a learning rate, and ∇ U ( x ) is the gradient of a loss function U ( x ) with respect to the network parameters. Now consider a simple neuroevolution scheme in which we propose a mutation x → x + ϵ of all neural-network parameters, where ϵ is a set of independent Gaussian random numbers of zero mean and variance σ 2 . Let us accept the proposal with the Metropolis probability \(\min \left(1,{{{{\rm{e}}}}}^{-\beta {{\Delta }}U}\right)\) . Here, β is a reciprocal temperature, and Δ U is the change of the loss function under the proposal. This is a Metropolis Monte Carlo algorithm, a Markovian dynamics that constitutes a form of importance sampling, and a common choice in the physics literature 9 , 10 , 24 . In physical systems, β is inversely proportional to the physical temperature, and we consider finite values of β in order to make contact with that literature. However, in the context of training a neural network it is interesting to consider the zero-temperature limit β = ∞ , where mutations are accepted only if the loss does not increase. That regime is not normally considered in particle-based simulations.

Our main results can be summarized as follows. When β ≠ ∞ the weights of the network evolve, to leading order in σ , as \(\dot{{{{\bf{x}}}}}=-(\beta {\sigma }^{2}/2)\nabla U({{{\bf{x}}}})\) plus Gaussian white noise. Averaged over independent realizations of the learning process, this form of neuroevolution is therefore equivalent to simple gradient descent, with learning rate β σ 2 /2. In the limit β = ∞ , where mutations are accepted only if the loss function does not increase, weights under neuroevolution evolve instead as \(\dot{{{{\bf{x}}}}}=-(\sigma /\sqrt{2\pi })| \nabla U({{{\bf{x}}}}){| }^{-1}\nabla U({{{\bf{x}}}})\) plus Gaussian white noise, which corresponds to clipped gradient descent on U ( x ) 25 . Note that conditioning the acceptance of neural-network parameter mutations on the change of the loss function for a single copy of that network is sufficient to enact gradient descent: a population of individuals is not required.

In this paper, we use the term “neuroevolution” to refer to a sequence of mutation steps applied to the parameters of a single copy of a neural network and accepted probabilistically. In general, neuroevolutionary algorithms encompass a broader variety of processes, including mutations of populations of communicating neural networks 16 and mutations of network topologies 21 , 26 , 27 . Similarly, the set of procedures for particles that can be described as “Monte Carlo algorithms” is large, and ranges from local moves of single particles—roughly equivalent to the procedure used here—to nonlocal moves and moves of collections of particles 24 , 28 , 29 , 30 , 31 . The dynamics of those collective-move Monte Carlo algorithms and of the more complicated neuroevolutionary schemes 21 , 26 , 27 do not correspond to simple gradient descent. Here, we demonstrate a correspondence between one member of this set of algorithms and gradient descent, the implication being that, given any potentially complicated set of neuroevolutionary methods, it is enough to add a simple mutation-acceptance protocol in order to ensure that gradient descent is also approximated. The neuroevolution-gradient descent correspondence is similar to the proofs that neural networks with enough hidden nodes can represent any smooth function 32 : it does not necessarily suggest how to solve a given problem, but provides understanding of the limits and capacity of the tool and its relation to other methods of learning.

Our work provides a rigorous connection between gradient descent and what is arguably the simplest form of neuroevolution. It complements studies that demonstrate a numerical similarity between gradient-based methods and population-based evolutionary methods 16 , 17 , and studies that show analytically that the gradients approximated by those methods are, under certain conditions, equivalent to the finite-difference gradient 33 , 34 , 35 .

The paper is structured as follows. We summarize the neuroevolution-gradient descent correspondence in section “Results”, and derive it in section “Methods”. Our derivation uses ideas developed in ref. 20 to treat physical particles, and applies them to neural networks: we consider a different set-up (in effect, we work with a single particle in a high-dimensional space, rather than with many particles in three-dimensional space) and proposal rates, and we consider the limit β = ∞ that is rarely considered in the physics literature but is natural in the context of a neural network. We can associate the state x of the neural network with the position of a particle in a high-dimensional space, and the loss function U ( x ) with an external potential. The result is a rewriting of the correspondence between Langevin dynamics and Monte Carlo dynamics as a correspondence between the simplest forms of gradient descent and neuroevolution. Just as the Langevin-Monte Carlo correspondence provides a basis for understanding why Monte Carlo simulations of particles can approximate real dynamics 31 , 36 , 37 , 38 , 39 , 40 , 41 , so the neuroevolution-gradient descent correspondence shows how we can effectively perform gradient descent on the loss function without explicit calculation of gradients. The correspondence holds exactly only in the limit of vanishing mutation scale, but we use numerics to show in section “Numerical illustration of the neuroevolution-gradient descent correspondence” that it can be observed for neuroevolution done with finite mutations and gradient descent enacted with a finite timestep. We conclude in section “Conclusions”.

## Results

In this section, we summarize the main analytic results of this paper. These results are derived in section “Methods”.

Consider a neural network with N parameters (weights and biases) x = { x 1 , …, x N }, and a loss U ( x ) that is a deterministic function of the network parameters. The form of the network does not enter the proof, and so the result applies to neural networks of any architecture (we shall illustrate this point numerically by considering both deep and shallow nets). The loss function may also depend upon other parameters, such as a set of training data, as in supervised learning, or a set of actions and states, as in reinforcement learning; the correspondence we shall describe applies regardless.

### Gradient descent

Under the simplest form of gradient descent, the parameters x i of the network evolve according to numerical integration of

Here, time t measures the progress of training, and α is the learning rate 3 , 4 , 5 , 6 , 7 .

### Neuroevolution

Now consider training the network by neuroevolution, defined by the following Monte Carlo protocol.

1. Initialize the neural-network parameters x and calculate the loss function U ( x ). Set time t = 0.

2. Propose a change (or “mutation”) of each neural-network parameter by an independent Gaussian random number of zero mean and variance σ 2 , so that $${{{\bf{x}}}}\to {{{\bf{x}}}}+{{{\boldsymbol{\epsilon }}}},$$ (2) where ϵ = { ϵ 1 , …, ϵ N } and \({\epsilon }_{i} \sim {{{\mathcal{N}}}}(0,{\sigma }^{2})\) .

3. Accept the mutation with the Metropolis probability \(\min \left(1,{{{{\rm{e}}}}}^{-\beta [U({{{\bf{x}}}}+{{{\boldsymbol{\epsilon }}}})-U({{{\bf{x}}}})]}\right)\) , and otherwise reject it. In the latter case we return to the original neural network. The parameter β can be considered to be a reciprocal evolutionary temperature.

4. Increment time t → t + 1, and return to step 2.

For finite β , and in the limit of small mutation scale σ , the parameters of the neural network evolve under this procedure according to the Langevin equation

where ξ is a Gaussian white noise with zero mean and variance σ 2 :

Eq. ( 3 ) describes an evolution of the neural-network parameters x i that is equivalent to gradient descent with learning rate α = β σ 2 /2 in the presence of Gaussian white noise. Averaging over independent stochastic trajectories of the learning process (starting from identical initial conditions) gives

which has the same form as the gradient descent equation ( 1 ). Thus, when averaged over many independent realizations of the learning process, the neuroevolution procedure 1–4, with finite β , is equivalent in the limit of small mutation scale to gradient descent on the loss function.

In the case β = ∞ , where mutations are only accepted if the loss function does not increase, the parameters of the network evolve according to the Langevin equation

where η is a Gaussian white noise with zero mean and variance σ 2 /2:

The form ( 6 ) is different to ( 3 ), because the gradient in the first term is normalized by the factor \(| \nabla U({{{\bf{x}}}})| =\sqrt{\mathop{\sum }\nolimits_{i = 1}^{N}{(\partial U({{{\bf{x}}}})/\partial {x}_{i})}^{2}}\) , which serves as an effective coordinate-dependent rescaling (or vector normalization) of the timestep, but ( 6 ) nonetheless describes a form of gradient descent on the loss function U ( x ). Note that the drift term in ( 6 ) is of lower order in σ than the diffusion term (which is not the case for finite β ). In the limit of small σ , ( 6 ) describes an effective process in which uphill moves in loss cannot be made, consistent with the stochastic process from which it is derived.

Averaged over independent realizations of the learning process, ( 6 ) reads

The results ( 3 ) and ( 6 ) show that training a network by making random mutations of its parameters is, in the limit of small mutations, equivalent to noisy gradient descent on the loss function.

Writing \(\dot{U}({{{\bf{x}}}})=\dot{{{{\bf{x}}}}}\cdot \nabla U({{{\bf{x}}}})\) , using ( 3 ) and ( 6 ), and averaging over noise shows the evolution of the mean loss function under neuroevolution to obey, in the limit of small σ ,

equivalent to evolution under the noise-free forms of gradient descent ( 5 ) and ( 8 ).

In section “Numerical illustration of the neuroevolution-gradient descent correspondence” we illustrate numerically the correspondence described here, and show that it can be observed numerically for non-vanishing mutations and finite integration steps. In section “Methods” we detail the derivation of the correspondence.

## Discussion

### Numerical illustration of the neuroevolution-gradient descent correspondence

In this section, we demonstrate the neuroevolution-gradient descent correspondence numerically. We consider single-layer neural networks for the cases of infinite and finite β , and a deep network for the case of infinite β .

#### Shallow net, β = ∞

In order to observe correspondence numerically, the neuroevolution mutation scale σ must be small enough that correction terms neglected in the expansion leading to ( 25 ) and ( 55 ) are small. The required range of σ is difficult to know in advance, but straightforward to determine empirically: below the relevant value of σ , the results of neuroevolution will be statistically similar when scaled in the manner described below.

We consider a simple supervised-learning problem in which we train a neural network to express the function \({f}_{0}(\theta )=\sin (2\pi \theta )\) on the interval θ ∈ [0, 1). We calculated the loss using K = 1000 points on the interval,

where