On the Relationship Between the OpenAI Evolution Strategy and Stochastic Gradient Descent

Xingwen Zhang, Jeff Clune, Kenneth O. StanleyarXiv 2017 · OpenReview

Abstract

Because stochastic gradient descent (SGD) has shown promise optimizing neural networks with millions of parameters and few if any alternatives are known to exist, it has moved to the heart of leading approaches to reinforcement learning (RL). For that reason, the recent result from OpenAI showing that a particular kind of evolution strategy (ES) can rival the performance of SGD-based deep RL methods with large neural networks provoked surprise. This result is difficult to interpret in part because of the lingering ambiguity on how ES actually relates to SGD. The aim of this paper is to significantly reduce this ambiguity through a series of MNIST-based experiments designed to uncover their relationship. As a simple supervised problem without domain noise (unlike in most RL), MNIST makes it possible (1) to measure the correlation between gradients computed by ES and SGD and (2) then to develop an SGD-based proxy that accurately predicts the performance of different ES population sizes. These innovations give a new level of insight into the real capabilities of ES, and lead also to some unconventional means for applying ES to supervised problems that shed further light on its differences from SGD. Incorporating these lessons, the paper concludes by demonstrating that ES can achieve 99% accuracy on MNIST, a number higher than any previously published result for any evolutionary method. While not by any means suggesting that ES should substitute for SGD in supervised learning, the suite of experiments herein enables more informed decisions on the application of ES within RL and other paradigms.

Introduction

In 2017, OpenAI demonstrated that a specific variant of Evolution Strategies (ES) could rival state-of-the-art reinforcement learning (RL) methods on complex tasks like Atari games. This result was surprising because evolutionary methods were generally considered ineffective for optimizing neural networks with millions of parameters. The lack of interpretability regarding how ES relates to Stochastic Gradient Descent (SGD) has hindered a deeper understanding of these results. This paper aims to reduce this ambiguity by analyzing ES as a noisy gradient approximator within the controlled environment of MNIST.

Methodology

We employ several experimental setups to dissect the mechanics of ES:

  1. Gradient Correlation: We directly compare the gradient estimated by ES ($g^{ES}$) with the "true" gradient ($g^{True}$) calculated via backpropagation. Using the Pearson correlation coefficient, we measure how much the evolutionary direction aligns with the steepest descent direction.
  2. The SGD Proxy: We hypothesize that ES is essentially SGD with a specific amount of independent noise. We created a "Proxy" algorithm ($g^{Proxy} = g^{True} + \text{noise}$) and tuned the noise level to match the observed correlation of ES.
  3. Limited Perturbation and No-mini-batch ES: To address communication bottlenecks and exploit the inherent stochasticity of ES, we tested variants where offspring only perturb subsets of parameters or evaluate on different random data subsets.

Results and Analysis

Our experiments on MNIST provide several key insights into the relationship between ES and SGD.

Low Correlation Sufficiency

A primary finding is that successful optimization requires surprisingly little alignment with the true gradient. As shown in Figure 1, ES with 10,000 offspring maintains a stable correlation of approximately 3.9% with the true gradient throughout training. Despite this low signal-to-noise ratio, the algorithm is capable of training deep networks to high accuracy.

Figure 1: The correlation between the ES-estimated gradient and the true gradient remains stable at approximately 4% throughout the 2,000 iterations of training.

Validation of the SGD Proxy

The SGD-based proxy almost perfectly matches the learning curves of ES. In Figure 2, the validation accuracy of the proxy tracks the actual ES performance with high fidelity. The zoomed-in sections reveal that even the stochastic "jitter" in the validation accuracy is replicated, confirming that ES functions as a gradient-following algorithm that trades precision for parallelizability.

Figure 2: Validation accuracy of the ES Proxy compared to actual ES with 10k offspring. The near-identical curves validate the hypothesis that ES acts as a noisy gradient approximator.

Record-Breaking Evolutionary Performance

By scaling the population size to 50,000 offspring and utilizing the "no-mini-batch" approach—where each offspring evaluates on a different random subset of data—ES achieved 99% accuracy on MNIST. This represents the highest result ever published for an evolutionary method on this dataset. To achieve parity with standard SGD, ES requires a correlation of approximately 20%, corresponding to roughly 274,000 offspring per iteration.

Discussion

The primary advantage of ES in RL is not its optimization efficiency but its communication efficiency. While SGD requires workers to exchange massive gradient vectors, ES workers only need to communicate a random seed and a scalar reward. This allows ES to scale across thousands of CPUs far more easily than SGD. Furthermore, the "no-mini-batch" ES effectively smooths the objective function by averaging out dataset noise across thousands of offspring, leading to more stable updates in certain regimes.

Conclusion

While ES is not a replacement for SGD in supervised learning due to the high computational cost of forward passes, its role as a scalable, noisy gradient approximator makes it a powerful tool for RL. This study provides a framework for understanding ES performance and informs its application in high-dimensional optimization problems.

Summary updated

Abstract

Because stochastic gradient descent (SGD) has shown promise optimizing neural networks with millions of parameters and few if any alternatives are known to exist, it has moved to the heart of leading approaches to reinforcement learning (RL). For that reason, the recent result from OpenAI showing that a particular kind of evolution strategy (ES) can rival the performance of SGD-based deep RL methods with large neural networks provoked surprise. This result is difficult to interpret in part because of the lingering ambiguity on how ES actually relates to SGD. The aim of this paper is to significantly reduce this ambiguity through a series of MNIST-based experiments designed to uncover their relationship. As a simple supervised problem without domain noise (unlike in most RL), MNIST makes it possible (1) to measure the correlation between gradients computed by ES and SGD and (2) then to develop an SGD-based proxy that accurately predicts the performance of different ES population sizes. These innovations give a new level of insight into the real capabilities of ES, and lead also to some unconventional means for applying ES to supervised problems that shed further light on its differences from SGD. Incorporating these lessons, the paper concludes by demonstrating that ES can achieve 99% accuracy on MNIST, a number higher than any previously published result for any evolutionary method. While not by any means suggesting that ES should substitute for SGD in supervised learning, the suite of experiments herein enables more informed decisions on the application of ES within RL and other paradigms.
BibTeX
@misc{zhang2017relationship,
  author = {Xingwen Zhang and Jeff Clune and Kenneth O. Stanley},
  title = {{On the Relationship Between the OpenAI Evolution Strategy and Stochastic Gradient Descent}},
  year = {2017},
  eprint = {1712.06564},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1712.06564},
}
Figure