Unfortunately, this "diagonal" approach performs poorly when the problem is non-separable because the search distribution cannot follow directions that are not parallel to the current coordinate axes.

In this paper, we propose a new variant of the natural evolution strategy family [17], termed Rank One NES (R1-NES). This algorithm stays within the general NES framework in that the search distribution is adjusted according to the natural gradient [2], but it uses a novel parameterization of the covariance matrix,

## C = Σ 2I + Uu>,

where u and σ are the parameters to be adjusted. This parameterization allows the predominant eigen direction, u, of C to be aligned in any direction, enabling the algorithm to tackle highly non-separable problems while maintaining only O (d) parameters. We show through rigorous derivation that the natural gradient can also be effectively computed in O (d) per sample. R1-NES scales well to high dimensions, and dramatically outperforms diagonal covariance matrix algorithms on non-separable objective functions. As an example, R1-NES reliably solves the the non-convex Rosenbrock function up to 512 dimensions.

The rest of the paper is organized as follows. Sectio 2, briefly reviews the NES
framework. The derivation of R1-NES is presented in Section 3. Section 4 empirically evaluates the algorithm on standard benchmark functions, and Section 5 concludes the paper.

## 2 The Nes Framework

Natural evolution strategies (NES) are a class of evolutionary algorithms for real-valued optimization that maintain a search distribution, and adapt the distribution parameters by following the *natural* gradient of the expected function value. The success of such algorithms is largely attributed to the use of natural gradient, which has the advantage of always pointing in the direction of the steepest ascent, even if the parameter space is not Euclidean. Moreover, compared to regular gradient, natural gradient reduces the weights of gradient components with higher uncertainty, therefore making the update more reliable. As a consequence, NES algorithms can effectively cope with objective functions with ill-shaped landscapes, especially preventing premature convergence on plateaus and avoiding overaggressive steps on ridges [16].

The general framework of NES is given as follows: At each time step, the algorithm samples n ∈ N new samples x1*, . . . , x*n ∼ π (·|θ), with π (·|θ) being the search distribution parameterized by θ. Let f : R
d7→ R be the objective function to maximize. The expected function value under the search distribution is

$$\theta\left|f\left(x\right)\right|$$
$$\mathbf{j}$$
