CMA-ES with Optimal Covariance Update and Storage Complexity
The covariance matrix adaptation evolution strategy (CMA-ES) is arguably one of the most powerful real-valued derivative-free optimization algorithms, finding many applications in machine learning. The CMA-ES is a Monte Carlo method, sampling from a sequence of multi-variate Gaussian distributions. Given the function values at the sampled points, updating and storing the covariance matrix dominates the time and space complexity in each iteration of the algorithm. We propose a numerically stable quadratic-time covariance matrix update scheme with minimal memory requirements based on maintaining triangular Cholesky factors. This requires a modification of the cumulative step-size adaption (CSA) mechanism in the CMA-ES, in which we replace the inverse of the square root of the covariance matrix by the inverse of the triangular Cholesky factor. Because the triangular Cholesky factor changes smoothly with the matrix square root, this modification does not change the behavior of the CMA-ES in terms of required objective function evaluations as verified empirically. Thus, the described algorithm can and should replace the standard CMA-ES if updating and storing the covariance matrix matters.
The manuscript describes a novel CMA-ES update scheme, the Cholesky-CMA-ES, that approximates the original covariance matrix adaptation (with complexity O(d^3)) by a novel scheme that runs in O(\mu d^2) where d is the optimization problem dimension and \mu the number of samples per iterations (typically O(log(d)). The principle idea of the update is to maintain and update a lower-triangular Cholesky matrix rather than a full covariance matrix (and corresponding sqrt of that). The difference between the Cholesky and the original CMA-ES is due to the lack of estimating a (random) orthogonal matrix E_t in every step. Under quite restrictive assumptions (i.e., assumptions about convergence of a sequence of covariance matrices to an unknown target covariance matrix) the authors give an asymptotic argument that the sequence of E_t will converge to an identity matrix, and thus the two schemes become equivalent.  The validity and the general speed-up of the Cholesky-CMA-ES is illustrated by using standard runtime and convergence plots on selected objective functions and by comparing it to two state-of-the-art CMA-ES alternatives that delay the full covariance matrix update by different means.       
This paper makes a solid contribution to speeding up the celebrated CMA-ES algorithm which is arguably the best algorithm for non-convex black-box optimization when little is known about the topology of the objective function and first or higher-order information is difficult to access or not helpful.   The proposed method speeds up the algorithm considerably and shows no deterioration of optimization performance on the synthetic test cases. Although this is of general importance, one weak point of ANY speed-up proposal for CMA-ES is that, in practice, the overall optimization process is dominated by the runtime of the black-box oracle (the objective function), and, often, the actual runtime of the CMA-ES is negligible compared to that. In addition, in typical scenarios where CMA-ES is used, the dimensionality of the problems does not go beyond a few tens of variables. Only in the case where a single function evaluation is on the order of milliseconds or smaller and the dimensionality is higher, the runtime of CMA-ES plays an important role, and this is targeted scenario here (which may be less realistic in practice).  As theoretical guarantees are notoriously difficult to get for an involved scheme such as CMA-ES, I would like to propose a couple of further empirical experiments and plots that may strengthen the presentation of the results. First, it may be instructive to see the evolution of E_t on selected optimization trajectories, e.g., in different norms. I envision an experiment where the full CMA-ES is used and the approximation is calculated simultaneously and compared. This would give further empirical evidence about the actual fluctuations of E_t over time. Second, it may be instructive to see actual runtimes and performance of CMA-ES without delay strategies in this contribution for completeness. Third, although the used test functions are standard in the evolutionary optimization community I would prefer, on quadratic functions, a simulation study where the spectrum of quadratic forms is varied continuously (see, e.g., Stich and Mueller, PPSN 2012), and compare the solution quality and error in E_t  in dependence of the spectral distribution.  Forth, it would be instructive to see a real-world experiment that accompanies the present simulation results. For instance, policy gradients in real-time robotics applications might be a good choice where speed indeed matters and the parameter space is not too large.