A linear time natural evolution strategy for non-separable functions

Yi Sun, Tom Schaul, Faustino J. Gomez, Jürgen SchmidhuberGECCO (Companion) 2013 · OpenReview

TL;DR

This paper introduces R1-NES, a novel Natural Evolution Strategy (NES) that efficiently optimizes complex, high-dimensional, non-separable functions. By approximating the search distribution's covariance matrix with a low-rank structure, R1-NES achieves linear time complexity with respect to dimensionality, significantly outperforming existing methods on challenging benchmarks.

What Problem Does This Paper Address?

Many real-world optimization problems involve functions where the parameters are highly interdependent (non-separable) and the dimensionality can be very large (e.g., optimizing neural network weights). Traditional black-box optimization methods, like standard Natural Evolution Strategies (NES), often struggle with these problems. While some methods achieve linear complexity by using diagonal covariance matrices, they fail on non-separable functions because they can only adapt to axis-aligned changes. More sophisticated methods that can handle non-separability often have a computational cost that scales quadratically or cubically with dimensionality, making them impractical for very high-dimensional problems. This paper aims to bridge this gap by developing an algorithm that is both efficient (linear time complexity) and effective on high-dimensional, non-separable functions.

Methods

The core innovation of R1-NES lies in its novel parameterization of the search distribution's covariance matrix. Instead of using a full covariance matrix (which is computationally expensive) or a diagonal matrix (which is too restrictive), R1-NES uses a rank-one approximation: $C = \sigma^2 (I + uu^T)$. Here, $\sigma$ controls the overall scale, and $u$ is a single vector that captures the predominant direction of the search distribution. This allows the algorithm to adapt to a single, dominant non-separable direction in the problem landscape.

The algorithm leverages the natural gradient, a principled way to update search distributions that accounts for the geometry of the parameter space. The paper derives how to compute this natural gradient efficiently with the rank-one covariance matrix, achieving a computational cost that is linear in the dimensionality ($O(d)$) per sample. To handle potential numerical instabilities arising from the parameterization, they introduce a reparameterization of $\sigma$ and $u$ into $(c, v)$ and use an additive update strategy for $u$ when certain conditions are met. The overall algorithm follows the standard NES loop: sample, evaluate, compute natural gradient, and update parameters.

Datasets

The paper evaluates R1-NES on the "Black-Box Optimization Benchmarking" (BBOB) collection of twelve noise-free unimodal functions. These functions are specifically transformed to be non-separable and to avoid trivial optima, making them challenging for optimization algorithms.

Key Insights and Ideas

  • Rank-One Covariance is Sufficient for Many Non-Separable Problems: The key insight is that for many challenging non-separable functions, a single dominant direction captured by a rank-one covariance matrix is enough to achieve excellent performance, significantly reducing computational cost.
  • Natural Gradient + Low-Rank Covariance = Scalability: Combining the principled natural gradient update with a low-rank covariance approximation is crucial for achieving both effectiveness on non-separable problems and scalability to high dimensions.
  • Linear Complexity is Achievable for Non-Separable Optimization: The paper demonstrates that it's possible to achieve $O(d)$ complexity per function evaluation for non-separable problems, a significant improvement over existing methods that often scale quadratically or cubically.
  • Careful Reparameterization is Key for Stability: The reparameterization of $\sigma$ and $u$ and the conditional additive update strategy are essential for numerical stability, preventing issues that can arise with direct gradient updates on the rank-one parameters.

Key Results

  • State-of-the-Art Performance: R1-NES achieves the best reported results to date on the 512-dimensional Rosenbrock function.
  • Significant Speedup: On problems where R1-NES is well-suited, it can solve them up to 512 dimensions in a practical amount of time, whereas methods like xNES would take hours or even years. For example, a typical xNES run in 64 dimensions takes hours, while R1-NES takes minutes.
  • Linear Scaling: Figure 4 clearly shows that both SNES and R1-NES scale linearly with dimension in terms of computation time per evaluation, while xNES scales cubically.
  • Effectiveness on Non-Separable Functions: Figures 3 and 5 demonstrate R1-NES's strong performance on various non-separable benchmark functions, often outperforming xNES and SNES.

Limitations and Future Work

  • Limitations on Certain Functions: R1-NES struggles on functions where the Hessian has multiple eigendirections that are significantly different in magnitude and not aligned with the coordinate axes (e.g., Ellipsoid, RotatedEllipsoid, Tablet functions, as shown in Figure 6). This is because the rank-one parameterization can only capture a single dominant direction.
  • Future Work: The authors propose extending the algorithm to incorporate multiple search directions (e.g., a rank-k approximation) and to allow each search direction to shrink as well as grow. This would address the limitations observed on functions with complex Hessian structures.

Summary updated

Abstract

We present a novel Natural Evolution Strategy (NES) variant, the Rank-One NES (R1-NES), which uses a low-rank approximation of the search distribution covariance matrix. The algorithm allows computation of the natural gradient with cost linear in the dimensionality of the parameter space, and excels in solving high-dimensional non-separable problems.
BibTeX
@inproceedings{sun2013linear,
  author = {Yi Sun and Tom Schaul and Faustino J. Gomez and Jürgen Schmidhuber},
  title = {{A linear time natural evolution strategy for non-separable functions}},
  booktitle = {GECCO (Companion)},
  year = {2013},
  url = {https://openreview.net/forum?id=ggRYay7HsB5},
}
Figure