CMA-ES, Live
There is a shape of problem that many optimisers struggle with: a long, thin, tilted valley.
The ants of part 1 took steps along edges and left scent behind. The genetic algorithm of part 2 took steps in genome space, one mutation at a time. Simulated annealing in part 3 had a step size you could watch shrink as the temperature fell. This one learns the shape of the neighbourhood worth searching, and restretches itself to match: CMA-ES
Quick jargon guide
- CMA-ES: the Covariance Matrix Adaptation Evolution Strategy. An optimiser that samples a cloud of candidate points, keeps the best ones, and keeps adjusting the cloud's position, size, and shape to follow whatever has been working.
- Evolution strategy: the family CMA-ES belongs to: evolutionary optimisers for continuous variables, where mutation means adding random numbers rather than flipping genes.
- Mean: the centre of the search cloud, the algorithm's current best guess at where the answer lives.
- Step size (sigma): the overall scale of the cloud. Big sigma means bold, scattered samples; small sigma means cautious, local ones.
- Covariance matrix: the shape of the cloud: which directions it stretches along and how far. This is the star of the show, and adapting it is what the "CMA" stands for.
- Condition number: how stretched the cloud is: the ratio of its longest axis to its shortest. 1 is a circle; 400 is a needle.
- Black-box optimisation: optimising a function you can only evaluate, not differentiate or inspect. You put numbers in, a score comes out.
Steps versus shapes
Valleys like that are everywhere in real problems (the technical word is ill-conditioned). An optimiser proposing moves in random directions wastes almost all of them climbing walls while gradient descent zigzags across the floor of possible solutions.
This requires an optimiser that notices "movement along this axis keeps paying off, movement along that one never does".
CMA-ES keeps a sampling distribution, a fuzzy ellipse of probability. Each generation it draws a cloud of candidate points from the ellipse, scores them, and shifts the centre toward the better half.
It also updates the ellipse's shape. Directions the winners recently moved in get widened. Directions that never produced a winner get squeezed. It saves the historic data of wins in the covariance matrix.
Instead of a fixed cooling schedule, CMA-ES watches its own recent movement. If successive generations keep marching the same way, the steps were too small, so sigma grows. If the path folds back on itself, the steps were too big, so sigma shrinks. Exploration vs exploitation.
Hansen and Ostermeier formalised all of this in 2001[1], and the design is careful enough that the standard version has no parameters you are expected to tune. But, in this version, for fun, there are sliders so you can override that.
The loop on a napkin
- Sample a cloud of candidate points from a Gaussian: centre (mean), scale (sigma), shape (covariance).
- Score every point and rank them.
- Move the mean toward a weighted average of the best few, best weighted most.
- Stretch the covariance along the directions those winners came from.
- Grow or shrink sigma depending on whether recent moves kept pointing the same way.
- Go to step 1.
Watch it
Below, CMA-ES is minimising a landscape drawn as contour shading (darker is worse, the red cross is the global optimum). Blue dots are one generation's samples, the amber rings are the search ellipse at one and two sigma, and the green dot with the fading tail is the mean and the route it took.
Start with the default narrow valley and watch the ellipse for the first few seconds. It begins as a circle, tips over to match the valley's angle, and stretches. Click or drag anywhere on the map to plant the start point somewhere new.
Click or drag on the map to move the start point and restart. Best fitness is the gap to the optimum, so smaller is better and 0 is perfect. Ellipse stretch is the condition number of the covariance matrix (1× is a circle, hundreds is a needle). Both charts use log scales, because a healthy CMA-ES run improves by orders of magnitude, not increments. The run keeps going after it converges, so restart it if you'd like.
The step-size rule
On the smooth valleys the run still works, it just crawls. The step-size rule notices the steady progress and inflates sigma back to something sensible, which you can watch happening on the right-hand chart.
On the egg carton a tiny sigma is fatal. The cloud fits inside a single dimple, every sample agrees the local floor is the best thing going, and the run settles into the nearest dent.
If the sigma is huge, the first generations are chaos.
Then watch the sigma chart. The path the mean traces keeps folding back on itself, the adaptation rule reads that as "steps too big", and sigma falls generation after generation until the cloud shrinks onto something worth exploiting. Thrashing and then recovery is the self recovering step size.
Drop lambda to 6 and each generation's ranking is built from almost nothing. The mean update gets noisy and the covariance estimate gets noisier.
Back to the narrow valley, default settings, and this time watch only the amber ellipse and the stretch readout. Circle, tilt, stretch, and then a needle sliding along the valley floor with the stretch number climbing into the hundreds.
Every other algorithm I've covered in this series would be paying the valley's toll on every single move, but CMA-ES redrew its own geometry so there is no toll left to pay!
A memory of directions
What I like most about CMA-ES is where it keeps what it has learned. The ants kept their knowledge in the world, as scent on edges. The genetic algorithm kept it in a population, spread implicitly across genomes: variety, but no geometry. Simulated annealing had one knob, a step size, and its step size only goes down.
CMA-ES keeps a small, dense summary: one point for "where", one number for "how far", and one matrix for "which way". The matrix is the difference. It is a running record of the directions that recently succeeded, updated every generation, and it turns a search that happens in the landscape into one that builds a model of the landscape's local shape.
Where it gets used
For continuous black-box problems, where the objective is a simulator or a physical measurement or a hyperparameter score with no gradient in sight, CMA-ES is the default serious tool up to a few hundred dimensions (yes, you read that correctly!!).
It has tuned aircraft geometry, robot gaits, controller parameters, and the settings of other learning systems. Hansen's tutorial[2].
When progress stalls, the instinct is to push harder in the direction you were already going. CMA-ES keeps an estimate of which directions have been rewarding you lately, and spend your effort along those, even when they aren't the ones you set off in. Which is surprisingly good life advice to get from a pile of linear algebra.
Common questions
Is this the full CMA-ES?
Simplified. The demo does the real core: Gaussian sampling, ranking, log-weighted recombination of the best mu samples, the rank-mu covariance update, and cumulative (path-based) step-size adaptation. It leaves out the rank-one covariance update with its separate evolution path, plus restarts and boundary handling, which the standard implementations all include.
Why does it keep drifting after finding the optimum?
Because it never knows it has found it. CMA-ES only ever sees relative rankings inside its own cloud, never "you are done".
When would I not use CMA-ES?
When you have gradients, use them. On smooth, differentiable problems, and especially in the millions of dimensions of neural network training, gradient methods win by orders of magnitude.
References
- Hansen, N., & Ostermeier, A. (2001). Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation, 9(2), 159–195. https://doi.org/10.1162/106365601750190398
- Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv preprint arXiv:1604.00772. https://doi.org/10.48550/arXiv.1604.00772