CMA-ES

Imagine you are trying to find the highest point on a foggy hillside. You cannot see the slope — you can only ask "is this spot higher than the last one?" Standard optimization algorithms demand that you know the gradient, the direction of steepest ascent, at every step. But what if the function has no gradient, or is too noisy, or is a black box you cannot peek inside?

CMA-ES — the Covariance Matrix Adaptation Evolution Strategy — was designed for exactly this situation. Introduced by Nikolaus Hansen and Andreas Ostermeier in 1996 and refined into its modern form by 2001, it treats optimization as evolution: a population of candidate solutions is sampled from a multivariate Gaussian distribution, the better solutions are selected, and the distribution itself is updated to concentrate probability mass near the good region.

The key insight is what gets updated. Naïve evolution strategies only move the mean. CMA-ES also updates the full covariance matrix — the parameter that controls the shape, size and orientation of the search cloud. If the landscape stretches along a diagonal, the ellipse tilts to match it. If the optimum is near, the ellipse shrinks. The algorithm learns its own geometry from the history of successful steps, without ever computing a derivative.

That makes CMA-ES a member of a family of methods called non-convex optimization strategies, but one that can handle landscapes far wilder than gradient descent can manage.

The canvas below shows a 2-D fitness landscape (brighter = higher fitness). A Gaussian search cloud — drawn as an ellipse — samples candidate points, keeps the best, and updates its mean and covariance matrix each generation.

<!-- {{c_title_comment}} -->
<div class="controls">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<canvas id="canvas" width="360" height="270"></canvas>
<div class="info-row">
  <span id="gen-stat">{{gen_stat_init}}</span>
  <span class="sep">|</span>
  <span id="sigma-stat">{{sigma_stat_init}}</span>
</div>
<div id="status" class="status"></div>

/* {{c_layout_comment}} */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; background: #fff; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
canvas { display: block; border: 1px solid #d0d7df; border-radius: 8px; width: 100%; }
.info-row { font-size: .85rem; color: #444; margin-top: .35rem; display: flex;
            gap: .35rem; align-items: center; }
.sep { color: #aaa; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.3em; margin-top: .3rem; color: #0a7d33; }

// Code not found

Press Step to advance one generation at a time and observe how the ellipse tilts, stretches and shrinks toward the peak. Press Run to let it converge automatically. Notice that on a diagonal ridge the ellipse rotates to align with it — that rotation is the covariance matrix at work.

At each generation, CMA-ES maintains three core state variables: the mean $\mathbf{m}$, the covariance matrix $\mathbf{C}$, and the step size $\sigma$. Updating them is where the magic — and the cost — live.

Sampling. $\lambda$ new candidates are drawn as $\mathbf{x}_k = \mathbf{m} + \sigma\,\mathbf{C}^{1/2}\,\mathbf{z}_k$ where each $\mathbf{z}_k \sim \mathcal{N}(\mathbf{0}, \mathbf{I})$. Computing $\mathbf{C}^{1/2}$ via eigendecomposition costs $O(n^3)$ but only needs refreshing every $O(n)$ generations.

Mean update. The new mean is the weighted average of the $\mu$ best candidates (the elite half):

$$\mathbf{m}' = \sum_{i=1}^{\mu} w_i\, \mathbf{x}_{i:\lambda}$$

Covariance update. This is the heart of CMA-ES. Two complementary mechanisms adapt $\mathbf{C}$:

• Rank-$\mu$ update — accumulates the outer products $(\mathbf{x}_{i:\lambda} - \mathbf{m})(\mathbf{x}_{i:\lambda} - \mathbf{m})^{\top}$ from all elite samples, giving a low-rank estimate of the local curvature.
• Rank-1 update — maintains an evolution path $\mathbf{p}_c$, a running sum of consecutive mean shifts that captures correlations across generations, and adds $\mathbf{p}_c\,\mathbf{p}_c^{\top}$ to $\mathbf{C}$.

Together they give the update $\mathbf{C}' = (1-c_1-c_\mu)\mathbf{C} + c_1\,\mathbf{p}_c\mathbf{p}_c^{\top} + c_\mu\sum_i w_i(\mathbf{x}_{i:\lambda}-\mathbf{m})(\mathbf{x}_{i:\lambda}-\mathbf{m})^{\top}$.

Step-size control. A separate evolution path $\mathbf{p}_\sigma$ tracks whether consecutive steps are correlated; if they are, $\sigma$ increases (steps are too small); if they zigzag, $\sigma$ shrinks. This cumulative step-size adaptation keeps the algorithm in a productive regime.

Computational cost. The full algorithm is $O(n^2)$ per function evaluation in $n$ dimensions once the eigendecomposition is amortized — expensive compared to gradient descent's $O(n)$, but gradient-free methods that only scale the axes (diagonal covariance) fail on rotated or ill-conditioned problems. CMA-ES trades cost for robustness.

The algorithm is not NP-hard to run; the covariance update is polynomial. What is hard is the underlying black-box optimization problem itself: no algorithm can find the global optimum of an arbitrary function in polynomial time with only function-value queries.

CMA-ES shines wherever gradients are absent, noisy or misleading:

• Neuroevolution and reinforcement learning: OpenAI's 2017 paper showed CMA-ES and related evolution strategies matching deep-RL performance on Atari and MuJoCo without backpropagation. The policy network weights are the search space.
• Robot locomotion: physical simulations are noisy and sometimes non-differentiable (contact forces, joint limits). CMA-ES tunes gait parameters directly from episode returns.
• Aerodynamic shape optimization: computational fluid dynamics solvers are expensive black boxes. CMA-ES finds wing profiles that reduce drag without needing adjoint solvers.
• Hyperparameter search: neural network training is sensitive to learning rate, batch size, architecture choices — CMA-ES explores this space more efficiently than random search when the number of hyperparameters is moderate ($n \lesssim 100$).
• Protein and drug design: scoring functions for molecular fitness are expensive, non-differentiable and full of local optima. CMA-ES navigates them with far fewer evaluations than grid search.

CMA-ES is considered one of the best general-purpose optimizers for problems with $n$ up to a few hundred dimensions and expensive-to-evaluate objective functions. For very high-dimensional problems ($n \gg 1000$), variants like sep-CMA-ES (diagonal covariance) or VD-CMA trade some power for scalability. Compare this landscape with non-convex optimization more broadly, or with discrete methods like simulated annealing which tackle similar rugged landscapes.

CMA-ES does something quietly remarkable: it treats the search distribution itself as the thing to be learned. By updating a full covariance matrix from the history of successful steps, it builds an internal model of the landscape's geometry — its ridges, valleys and correlations — without ever computing a gradient.

The price is quadratic cost in dimension, but the payoff is an optimizer that degrades gracefully on the hardest real-world problems: noisy, non-differentiable, multi-modal black boxes that defeat gradient-based methods entirely. Three decades after its introduction, CMA-ES remains one of the most reliable tools in the optimization toolkit.

So the next time you see a robot learning to walk or a wing shape being tuned by simulation, there is a good chance a search ellipse is somewhere in the loop — rotating, shrinking, chasing the peak.