Reviews: CMA-ES with Optimal Covariance Update and Storage Complexity

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).