Covariance Matrix Adaptation Evolution Strategy without a matrix

AI summary

Overview

Research area: Stochastic continuous optimization / nature-inspired algorithms (cs.NE), specifically the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) family.

Technical level: Advanced. The paper combines a proof about multivariate normal distributions with evolutionary algorithm design and a large benchmark study.

Scope: The paper presents MF-CMA-ES, a reformulation of CMA-ES that generates new candidate solutions without ever forming, storing, or decomposing a covariance matrix, while provably keeping the same sampling distribution.

What This Paper Is About

CMA-ES is one of the leading methods for continuous black-box optimization, but it needs to decompose its covariance matrix each iteration, which costs O(n^3) per iteration in n dimensions. That cubic cost is the main obstacle to using CMA-ES on problems with thousands of variables. The paper asks whether the covariance matrix can be eliminated entirely, and answers yes: new individuals can instead be built as randomized weighted combinations of difference vectors stored in an archive of recent populations.

Key Contributions

1. A matrix-free reformulation of CMA-ES. The recursive covariance matrix update is rewritten in non-recursive form (Observation 1), showing the matrix is an exponential smoothing of past rank-1 and rank-μ terms.

2. A proof of distributional equivalence (Theorem 1). The paper proves that a random vector built from weighted combinations of archived difference vectors and evolution paths is Gaussian with covariance matrix exactly equal to the covariance matrix that vanilla CMA-ES would maintain at that iteration.

3. A bounded history window. Because a term generated τ iterations ago contributes a factor of (1 - c_cov)^(τ/2), the paper shows it is sufficient to keep only the h most recent populations. This yields the MF-CMA-ES algorithm, which needs no matrix decomposition and draws λ(μ+1)h + λn standard normal samples per generation.

4. A benchmark comparison with step-size adaptation. The paper couples MF-CMA-ES with the Previous Population Midpoint Fitness (PPMF) rule (CSA is unusable because it requires an eigendecomposition) and evaluates both algorithms on the CEC'2017 benchmark suite.

Main Findings

• Identical distribution, no matrix: Theorem 1 establishes that the difference vectors generated by MF-CMA-ES follow the same multivariate normal distribution as those generated by matrix-based CMA-ES.

• Small windows stagnate: On the quadratic test function with n = 30 and history window sizes h in {10, 30, 60, 80}, small h made the convergence curve drop faster initially but then stagnate; for sufficiently large h the convergence was linear and its rate stabilized at a level comparable to CMA-ES.

• Eigenvalue analysis confirms the window effect: With n = 30, the eigenvalue dynamics of vanilla CMA-ES and MF-CMA-ES with h = 60 were similar, while h = 10 failed to reproduce the desired dynamics. The high condition number for h = 10 indicates the population was confined to a low-dimensional subspace, which explains the poor convergence.

• Comparable behavior without step-size adaptation: With step-size adaptation switched off (σ = 1 in all iterations), the matrix-free and matrix-based variants achieved comparable results on the quadratic function.

• Faster convergence with step-size adaptation: Coupled with PPMF, MF-CMA-ES converged faster than matrix-based CMA-ES and usually produced results of comparable or superior quality on the CEC'2017 suite.

• Statistical test results on CEC'2017 (51 runs per problem, budget MaxFEs = 10000n): Quade test p-values for the null hypothesis were 0.0003 for n = 10, 0.08 for n = 30, and 0.008 for n = 50. The null hypothesis cannot be rejected at n = 30, indicating no significant difference between the algorithms there. Holm-corrected p-values were 0.034 for n = 10 and 0.013 for n = 50; at a significance level of α = 0.05, this favored MF-CMA-ES at n = 10 and CMA-ES-CSA at n = 50.

• Ranking by dimension: At n = 10, MF-CMA-ES outperformed both matrix-based variants. At n = 50, CMA-ES-CSA was superior to MF-CMA-ES, while MF-CMA-ES still outperformed CMA-ES-PPMF.

• One clear exception: Among the ECDF comparisons, only F22 at n = 50 showed CMA-ES-PPMF significantly outperforming MF-CMA-ES. On some problems (e.g., F1 at n = 10 and 30) all methods reached comparable final quality, but MF-CMA-ES converged faster.

• Heuristic window size: The CEC'2017 experiments used h = 20 + 1.4n, derived by finding, for each n, the smallest h giving an MF-CMA-ES convergence rate similar to vanilla CMA-ES on the quadratic function with constant σ.

Methodology in Plain English

The authors start from the observation that the CMA-ES covariance matrix update is a running, exponentially smoothed average of two things: outer products of evolution paths and outer products of weighted difference vectors. Anything that is a smoothed sum of outer products can be rewritten as a sum of the underlying vectors, each multiplied by a random scalar. So instead of storing a matrix, the algorithm stores the difference vectors themselves in an archive, together with the evolution path vectors, and each new individual is generated by picking random weights for those archived vectors.

Because older vectors get down-weighted by the exponential smoothing, only the last h populations need to be stored. The proof shows this construction produces exactly the same Gaussian distribution.

The empirical work has two halves. The first half removes step-size adaptation entirely (σ = 1) and compares convergence curves and covariance eigenvalue dynamics on a separable quadratic function with exponentially spaced coefficients, using 30 independent runs, population size λ = 4n, weights 1/μ, and starting points drawn uniformly from [-0.2, 0.8]^n at n = 30.

The second half adds step-size adaptation. CSA cannot be used in the matrix-free version because it needs the inverse square root of the covariance matrix, so the authors use PPMF, which compares the fitness of current population members against the fitness of the previous population midpoint and raises or lowers σ accordingly, using the threshold θ = 0.2 taken unchanged from prior work. Both algorithms are then run on the CEC'2017 suite with 51 independent runs, a budget of 10000n fitness evaluations, and standard statistical tests (Quade test, Holm correction) and ECDF curves for comparison.

Why This Matters

The paper attacks the root cause of CMA-ES's high-dimensional bottleneck rather than mitigating its symptoms. Prior work either decomposes the matrix less often, restricts the covariance to a low-rank form (MVA-ES, R1-NES), approximates its square root at O(n^2.37) (MA-ES) or O(n log n) (LM-MA-ES), or uses differential mutation with a distribution that explicitly differs from CMA-ES (Differential Evolution Strategy). MF-CMA-ES is distinct in eliminating the matrix while exactly preserving the CMA-ES sampling distribution.

Real-world applications (the paper states CMA-ES is used in scientific research, engineering and industrial applications; high-dimensional black-box optimization of this kind commonly arises in):

• Tuning large numbers of continuous parameters where gradients are unavailable or unreliable.
• Design and calibration problems in engineering in which each objective evaluation is expensive and the search space has many variables.
• Scientific model fitting and parameter estimation with thousands of unknowns.
• Industrial optimization pipelines where a faster per-iteration method allows more iterations within a fixed compute budget.

Industry relevance: The result that MF-CMA-ES should be preferred over CMA-ES-PPMF when the evaluation budget is smaller than the one assumed by CEC'2017 is directly relevant to practitioners who work with tight evaluation budgets. Removing the cubic decomposition also removes a memory and implementation burden, which simplifies deployment on large-scale problems.

Future Directions

• Determine the optimal history window. The paper uses an empirically derived heuristic h = 20 + 1.4n; a principled theory for choosing h, or an adaptive scheme, remains open.

• Find a matrix-free step-size adaptation. Because CSA requires an eigendecomposition it cannot be coupled with MF-CMA-ES. Whether a CSA-equivalent rule can be expressed without the matrix is an explicit open question raised by the design.

• Push toward more efficient methods. The authors position MF-CMA-ES as a stepping stone toward even more efficient methods, and note that the approach simplifies the algorithm and offers a novel perspective on covariance matrix adaptation.

• Extend the empirical picture. The reported tables are partially shown in the truncated text; broader benchmarking across more dimensions, more functions, and larger n would clarify where the matrix-free variant's ranked performance holds.

Target Audience

Researchers and graduate students working on evolution strategies, black-box optimization, or high-dimensional continuous optimization who are already familiar with CMA-ES internals. It is also relevant to practitioners who deploy CMA-ES on problems where the cubic per-iteration cost or the memory for a full covariance matrix is the limiting factor. Readers without background in multivariate normal distributions and evolution strategy notation will find the theorem and proof section demanding.

Authors’ abstract

Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is a highly effective optimization technique. A primary challenge when applying CMA-ES in high dimensionality is sampling from a multivariate normal distribution with an arbitrary covariance matrix, which involves its decomposition. The cubic complexity of this process is the main obstacle to applying CMA-ES in highdimensional spaces. We introduce a version of CMA-ES that uses no covariance matrix at all. In the proposed matrix-free CMA-ES, an archive stores the vectors of differences between individuals and the midpoint, normalized by the step size. New individuals are generated as the weighted combinations of the vectors from the archive. We prove that the probability distribution of individuals generated by the proposed method is identical to that of the standard CMA-ES. Experimental results show that reducing the archive size to store only a fixed number of the most recent populations is sufficient, without compromising optimization efficiency. The matrix-free and matrix-based CMA-ES achieve comparable results on the quadratic function when the step-size adaptation is turned off. When coupled with the step-size adaptation method, the matrix-free CMA-ES converges faster than the matrix-based, and usually yields the results of a comparable or superior quality, according to the results obtained for the CEC'2017 benchmark suite. Presented approach simplifies the algorithm, offers a novel perspective on covariance matrix adaptation, and serves as a stepping stone toward even more efficient methods.