AI Glossary / Probabilistic machine learning / Intermediate

Covariance matrix adaptation evolution strategy

Definition

Covariance matrix adaptation evolution strategy, or CMA-ES, is a randomized method for optimizing functions of continuous parameters without requiring their gradients. It samples candidate solutions from an evolving multivariate normal distribution and adapts that distribution using the relative quality of evaluated candidates.

What it means

Some optimization problems offer only an input-output interface: choose settings, run a simulator or experiment, and receive a score. Derivatives may be unavailable, unreliable, or expensive. CMA-ES searches by learning where promising settings lie and which combinations of parameter changes are useful.
Its covariance matrix describes the search distribution, not the uncertainty of a Bayesian posterior. The matrix can represent correlations between search directions. This helps the algorithm explore elongated or rotated regions rather than treating every parameter as an unrelated coordinate.

How it works

Maintain a mean vector m, a positive step size sigma, and a covariance-shape matrix C. Sample a population of candidates from a normal distribution with mean m and covariance sigma² C. Evaluate each candidate using the objective function and rank the results.
Move the mean toward a weighted combination of selected candidates. Adapt covariance using successful search steps and accumulated directional information, often described through evolution paths. Adapt the overall step size to control the scale of exploration.
Repeat until a budget or stopping rule is reached. The complete algorithm includes carefully designed learning rates and update rules; merely replacing a covariance with the sample covariance of the best points is not a full implementation of CMA-ES.

Three practical examples

• Simulator tuning: optimize continuous model settings when each run returns a performance score but usable derivatives are unavailable.
• Engineering design exploration: search combinations of continuous design parameters, with explicit handling of feasibility constraints and evaluation cost.
• Machine-learning configuration: tune a modest set of continuous hyperparameters when validation performance is a black-box objective, while protecting a separate final evaluation set.

Think of it this way

Think of searching for a low point on a landscape by sending scouts around a moving camp. Their results guide both the camp's location and the shape of the next search area. The analogy is limited: CMA-ES follows statistical update rules, and a finite collection of scouts cannot guarantee discovery of the world's lowest valley.

Worked example

Consider an original illustration of selection and mean recombination, not a complete CMA-ES generation. Minimize f(x1, x2) = x1² + 4x2². Four evaluated candidates are A = (1, 0), B = (0, 1), C = (−0.5, 0.5), and D = (2, 0).
Their objective values are 1, 4, 1.25, and 4. The best two are A and C. With illustrative recombination weights 0.75 and 0.25, the new mean is 0.75A + 0.25C = (0.625, 0.125).
Its objective value, if evaluated, is 0.625² + 4 × 0.125² = 0.453125. That improvement is a property of this constructed example, not a guarantee for weighted averages on arbitrary objectives.
Separately, if sigma = 0.5 and C = diag(4, 1), the actual sampling covariance is sigma² C = diag(1, 0.25). The coordinate standard deviations are 1 and 0.5. This distinguishes the shape matrix from the overall sampling covariance; covariance and step-size adaptation remain additional operations.

Illustrative case study

Fictional case: Cedar Design tunes three continuous simulator parameters. The team gives CMA-ES a fixed evaluation budget and compares it with random search and an available gradient-based baseline.
Repeated runs produce different outcomes, so analysts report variability rather than only the best result. They also discover that an apparently excellent candidate violates a design constraint and revise the evaluation protocol to handle feasibility explicitly. The team retains tested feasible solutions and records the search settings. This case describes an evaluation process, not a claimed optimization win.

Common misconceptions and mistakes

CMA-ES does not require gradients, but it is not automatically better than gradient methods when reliable derivatives exist. It also does not guarantee a global optimum within a finite evaluation budget.
The covariance matrix is an adaptation mechanism for search, not an estimate of causal relationships among parameters. Its shape may reflect promising directions in the objective landscape.
The basic method targets continuous variables. Integer, categorical, bounded, or constrained problems require appropriate treatment. Objective noise can misrank candidates, and large parameter dimension increases the cost of maintaining a full covariance representation.

Business use

CMA-ES can be useful when evaluation is available but the objective is awkward to differentiate. Its practical value depends on how much improvement it finds per unit of evaluation cost.
Specify parameter scales, valid ranges, the objective, and stopping rules before comparing optimizers. Track the best verified feasible result separately from the current search mean. For noisy objectives, use an evaluation design that distinguishes genuine gains from random variation. Benchmark multiple runs and compare methods under the same budget rather than relying on one favorable trajectory.

People also ask

Why adapt covariance instead of only step size?

Covariance changes the relative sizes and orientation of search directions; one scalar step size cannot describe those relationships.

Is CMA-ES a genetic algorithm?

It belongs to the broader evolutionary-computation family, specifically evolution strategies, with a distinctive adaptive continuous search distribution.

Does it use the exact score magnitudes for selection?

Standard selection is based on rankings, making the ordering of candidate quality central. Other practical decisions and variants may still depend on additional information.

Check your understanding

If C stays fixed and sigma doubles, what happens to the sampling covariance?

Answer: It becomes four times larger because the covariance is sigma² C. Standard deviations double. This is why sigma should not be confused with a variance.

Related terms

• Derivative-free optimization
• Covariance matrix
• Multivariate normal distribution
• Evolution strategy
• black-box optimization
• step-size adaptation
• population-based search
• evolution path

Learn next

Learn multivariate normal sampling, then separate the roles of mean, covariance shape, and step size. Reproduce the worked recombination calculation before studying the full covariance and evolution-path updates. Finally, compare optimizers on a small objective using equal evaluation budgets and repeated runs.

• Step size

More in Probabilistic machine learning

• Correlated topic model - A correlated topic model, or CTM, is a probabilistic topic model that uses a logistic-normal distribution for a document's topic proportions.
• Coupling flow - A coupling flow is a normalizing flow built from invertible coupling transformations.
• Covariance graph - A covariance graph is a graphical representation of marginal independence assumptions, commonly expressed through zeros in a Gaussian covariance matrix.
• Data processing inequality - The data processing inequality states that processing an observation cannot increase its mutual information about an upstream variable when the processing...
• Data tempering - Data tempering is a Bayesian computational strategy that moves through a sequence of posterior distributions by gradually incorporating observations or...
• Deadly triad in reinforcement learning - The deadly triad in reinforcement learning is the combination of function approximation, bootstrapping, and off-policy learning.

Sources

Nikolaus Hansen, “The CMA Evolution Strategy: A Tutorial,” original author tutorial, sampling, recombination and covariance adaptation: https://arxiv.org/pdf/1604.00772 Independent source review: Hansen’s sampling equation and weighted-recombination explanation were read.

Previous: Covariance matrix Next: Covariant derivative (healing brush)