Note that computing O˜ c log p (x|θ) and O˜ v log p (x|θ) involves only inner products between vectors, which can also be done linearly in the number of dimensions.

Using the parameterization h*c, v*i introduces another problem. When r is small, O˜ c log p (x|θ) tends to be large, and thus directly updating c causes r to grow exponentially, resulting in numerical instability, as shown in Fig. 2(b). In this case, the additive update on u, rather than the update on h*c, v*i is more stable. In our implementation, the additive update on u is used if O˜ c log p (x|θ) > 0, otherwise the update is on h*c, v*i. This solution proved to be numerially stable in all our tests. Algorithm 1 shows the complete R1-NES algorithm in pseudocode.

## 4 Experiments

The R1-NES algorithm was evaluated on the twelve noise-free unimodal functions [6] in the 'Black-Box Optimization Benchmarking' collection (BBOB) from the 2010 GECCO Workshop for Real-Parameter Optimization. In order to make the results comparable those of other methods, the setup in [5] was used, which transforms the pure benchmark functions to make the parameters non-separable
(for some) and avoid trivial optima at the origin.

R1-NES was compared to xNES [3], SNES [14] on each benchmark with problem dimensions d = 2k, k = {1..9} (20 runs for each setup), except for xNES, which was only run up k = 6, d = 64. Note that xNES serves as a proper baseline since it is state-of-the-art, achieving performance on par with the popular CMA-ES. The reference machine is an Intel Core i7 processor with 1.6GHz and 4GB of RAM.

Fig. 3 shows the results for the eight benchmarks on which R1-NES performs at least as well as the other methods, and often much better. For dimensionality under 64, R1-NES is comparable to xNES in terms of the number of fitness evaluations, indicating that the rank-one parameterization of the search distribution effectively captures the local curvature of the fitness function (see Fig.5 for example). However, the time required to compute the update for the two algorithms differs drastically, as depicted in Fig. 4. For example, a typical run of xNES in 64 dimensions takes hours (hence the truncated xNES curves in all graphs), compared to minutes for R1-NES. As a result, R1-NES can solve these problems up to 512 dimensions in acceptable time. In particular, the result on the 512-dimensional Rosenbrock function is, to our knowledge, the best to date.

We estimate that optimizing the 512-dimensional sphere function with xNES (or any other full parameterization method, e.g. CMA-ES) would take over a year in computation time on the same reference hardware. It is also worth pointing out that sNES, though sharing similar, low complexity per function evaluation, can only solve separable problems (Sphere, Linear, AttractiveSector, and Ellipsoid).

Fig. 6 shows four cases (Ellipsoid, StepEllipsoid, RotatedEllipsoid, and Tablet)
for which R1-NES is not suited, highlighting a limitation of the algorithm. Three of the four functions are from the Ellipsoid family, where the fitness functions