Optimization With Only a Score
Some optimization problems give you almost nothing to work with. You can hand the problem a vector of numbers and get back a single score, and that is all. There is no gradient, no formula you can differentiate, sometimes not even a guarantee that the same input returns the same score twice. Tuning the gains of a controller in a physics simulator looks like this. So does fitting the parameters of a chemical model, or choosing the learning rate and dropout of a neural network.
The Covariance Matrix Adaptation Evolution Strategy, almost always shortened to CMA-ES, is one of the most respected tools for this kind of problem when the variables are continuous. Its standard form was published by Nikolaus Hansen and Andreas Ostermeier in 2001, in the journal Evolutionary Computation, under the title «Completely Derandomized Self-Adaptation in Evolution Strategies.» Twenty-five years later it is still a standard first choice, and a standard baseline, for hard black-box problems with a few dozen to a few hundred variables.
Sampling From a Gaussian
CMA-ES does not keep a population of individuals the way a genetic algorithm does. It keeps a probability distribution: a multivariate normal with a mean vector m, a global step size σ, and a covariance matrix C. Each generation it draws λ candidate solutions from that distribution, evaluates them, and sorts them from best to worst.
The new mean is a weighted average of the best μ candidates, usually the top half, with better ones receiving larger weights. So the center of the search moves toward the region where good solutions were just found. That part alone is a fairly ordinary evolution strategy. What makes CMA-ES different is what it does next with the covariance matrix and the step size.
The default population size is small. Hansen’s tutorial on the method recommends λ = 4 + ⌊3 ln n⌋, where n is the number of variables. For a 100-dimensional problem that gives 17 samples per generation. The suggested defaults for the other internal parameters are also derived from n, which is why practitioners rarely tune them.
Learning the Shape of the Search
Picture a long, narrow valley that runs diagonally across the search space. A plain random search with circular steps wastes most of its samples climbing the walls, because almost every direction points uphill except the one along the valley floor. To make progress it would need tiny steps, and tiny steps make the walk along the valley painfully slow.
The covariance matrix fixes this. After each generation, CMA-ES looks at the steps that led to the selected candidates and nudges C so that those directions become more likely in the future. Over many generations the sampling distribution stretches into an ellipsoid aligned with the valley. The algorithm has, in effect, learned which combinations of variables move together.
This is called the rank-μ update, because it uses information from all μ selected steps at once. On a convex quadratic function, the learned covariance tends toward a matrix proportional to the inverse of the Hessian. That is the same matrix a Newton or quasi-Newton method tries to approximate with derivatives. CMA-ES gets there using nothing but the ordering of sampled points.
Evolution Paths
The second idea in the 2001 paper is called cumulation. Instead of looking only at the current generation, CMA-ES keeps a running, exponentially fading sum of the recent movements of the mean. Hansen and Ostermeier call this the evolution path.
The path carries information a single generation cannot. If the mean keeps moving in roughly the same direction, the steps add up and the path grows long. If it zigzags back and forth, consecutive steps cancel and the path stays short. The rank-one update adds the outer product of this path to the covariance matrix, which strengthens directions of consistent progress.
The two updates complement each other. The rank-μ update is efficient with large populations, while the rank-one update with cumulation works well with the small default population. The modern algorithm uses both.
Step-Size Control
Shape is only half of the problem. The algorithm also has to decide how far to step overall, and a covariance matrix learned from past steps cannot answer that by itself, because it adapts too slowly.
CMA-ES handles this with a second evolution path, built in a coordinate system where the current covariance has been factored out. The rule then compares the length of this path with the length expected under pure random selection. If the path is longer than expected, successive steps are pointing the same way and the step size is too small, so σ grows. If it is shorter, steps are cancelling each other and σ shrinks. The paper calls this cumulative step-size adaptation.
The rule is short. It lets the algorithm take large steps far from the optimum and converge quickly once it gets close, without a manually designed schedule like the cooling schedule in simulated annealing.
Invariance
Hansen’s tutorial on the method names invariance as one of the governing principles of its design. CMA-ES only uses the ranking of candidates, never their raw scores, so its behavior does not change if the objective function is replaced by any strictly increasing transformation of itself. Squaring a positive objective or taking its logarithm makes no difference.
It is also invariant, given a matching starting point and covariance, to rotations, translations and general linear transformations of the search space. A badly scaled, rotated problem is, for CMA-ES, the same problem as a well-scaled one once the covariance has adapted. This is why the 2001 paper reported speed-ups of several orders of magnitude on badly scaled, non-separable functions, and a factor of three to ten on moderately mis-scaled ones.
There is a theoretical account of why this works. The Information-Geometric Optimization framework, published by Yann Ollivier and coauthors in the Journal of Machine Learning Research in 2017, shows that the rank-μ update of CMA-ES can be read as a natural gradient step on the parameters of the search distribution. The algorithm came first and the theory came later, which is a common order of events in this field.
Restarts and Larger Populations
With its default settings, CMA-ES behaves like a fast local search. On a function with many local optima it will often converge cleanly to the wrong one. The standard fix is to restart.
Anne Auger and Nikolaus Hansen proposed IPOP-CMA-ES at the 2005 IEEE Congress on Evolutionary Computation. Each time the run stalls, it restarts with the population size doubled. Larger populations smooth over small bumps in the landscape and make the search more global. On the 25 test functions of the CEC 2005 special session on real-parameter optimization, IPOP-CMA-ES ranked first overall. A later variant, BIPOP-CMA-ES, alternates between large and small populations, and the two were among the best performers in the Black-Box Optimization Benchmarking workshops of 2009 and 2010.
Case: An 867-Parameter Driver
One well-known use in machine learning is the 2018 World Models paper by David Ha and Jürgen Schmidhuber. They trained a variational autoencoder to compress game frames and a recurrent network to predict what comes next. The part that actually chose actions was a small linear controller with 867 parameters, and they did not train it with gradients. They evolved it with CMA-ES, using a population of 64, on the CarRacing task. The agent reached an average score of 906 ± 21, which the authors reported as the first result to solve that environment.
The choice made sense. A reinforcement learning reward is noisy and delayed, and 867 parameters is well within the range where CMA-ES is comfortable. Every candidate can also be evaluated on a separate CPU core, so the method parallelizes almost perfectly.
Hyperparameter tuning is another natural fit. In 2016 Ilya Loshchilov and Frank Hutter compared CMA-ES with Bayesian optimization methods for tuning a convolutional network on MNIST, running evaluations on 30 GPUs in parallel, and argued that CMA-ES is a competitive option when many evaluations can run at once. Today the method is easy to try: the pycma library is maintained by Hansen, and the Optuna framework includes a CMA-ES sampler.
The Quadratic Cost
The weakness is the covariance matrix itself. For n variables it has about n²/2 free entries, and the standard algorithm needs memory and time per sample that grow quadratically with n. It also needs on the order of n² evaluations to learn a full matrix. With a few hundred variables this is fine. With tens of thousands it becomes impractical, which is why nobody trains the weights of a large neural network with standard CMA-ES.
Several variants trade expressiveness for scale. In 2008 Raymond Ros and Nikolaus Hansen proposed sep-CMA-ES, which restricts C to a diagonal matrix and brings the cost down to linear. It loses the ability to learn correlations between variables, but in their experiments it needed fewer evaluations than full CMA-ES on several problems above a hundred dimensions, including the non-separable Rosenbrock function. Limited-memory versions such as LM-CMA, inspired by L-BFGS, keep a few vectors instead of a full matrix.
Closing Thought
What I find most interesting about CMA-ES is how little it assumes. It never reads the value of the objective, only the order of the candidates. And yet, from that ordering alone, it reconstructs something close to the curvature of the problem, the same information a second-order method gets from derivatives. A lot of «nature-inspired» optimizers are described by their metaphor. CMA-ES is better described by what it estimates, and that is probably why it has outlasted so many of them.
By: Max Johnson B.
Deja una respuesta