CMA-ES in Optuna: hyperparameter optimization without gradients

CMA-ES in Optuna: Step-by-Step Breakdown of the Evolutionary Strategy for Hyperparameter Optimization

The CMA-ES algorithm is a derivative-free optimization method that effectively solves hyperparameter tuning tasks in complex, multimodal, or noisy search spaces. Unlike gradient-based approaches, it doesn't require the objective function to be differentiable and is robust against local minima. In this article, we'll dissect how it works using the 2D Rosenbrock function as an example to clearly show how the algorithm adapts its step size and search direction.

Initialization: Initial Search Conditions

Before CMA-ES begins, you need to set three key parameters:

• Initial mean (m) — coordinates of the starting point in the search space. In our case — (0, -1).
• Covariance matrix (C) — defines the shape and orientation of the search region. Initially, it's the identity matrix, creating circular symmetry around the center.
• Global step (σ) — search scale. Set to 0.8, corresponding to a confidence ellipse radius of ≈1.96 for 95% probability of points falling inside.

These parameters form the initial normal distribution from which candidates are generated. Importantly: even if the starting point is far from the optimum, the algorithm can adapt thanks to its evolutionary mechanisms.

Generation and Evaluation of Candidates

On each iteration, λ candidates (15 in the example) are generated using the formula:

x_k ~ m + σ · N(0, C)

where N(0, C) is a multivariate normal distribution with zero mean and covariance matrix C. Each candidate is a set of hyperparameters fed into the model to evaluate the objective function (e.g., loss). After computing the function values, the μ best candidates (7 in the example) are selected to form the basis for updating the distribution.

Updating the Search Center via Weighted Average

The center of the new distribution is computed as the weighted sum of the best points:

m_new = Σ w_i · x_i

Weights w_i are calculated on a logarithmic scale:

w_i = [ln((λ+1)/2) - ln(i)] / Σ[ln((λ+1)/2) - ln(j)]

This ensures an exponentially greater contribution from the best candidates. For example, the first point gets a weight several times higher than the seventh. This approach mimics "natural selection": successful solutions have a stronger influence on the next generation.

Adapting the Shape and Scale of the Search

The key advantage of CMA-ES is its dynamic adaptation to the objective function's topology. This is achieved through two mechanisms:

Updating the Covariance Matrix

Update formula:

C_new = (1 - c_μ) · C_old + c_μ · C_μ

where C_μ is the covariance matrix constructed from the normalized offsets of the best points relative to the old center. The parameter c_μ (learning rate, e.g., 0.9) controls the balance between historical and new data. If the best points align along a specific direction (e.g., along the "valley" of the Rosenbrock function), the C matrix deforms the search region into an ellipse elongated in that direction — speeding up convergence.

Adjusting the Global Step (σ)

The step is updated using the formula:

σ_new = σ_old · exp( (c_σ / d_σ) · (||p_σ|| / E[||N(0,I)||] - 1) )

Here:

• p_σ — evolution path that accumulates the direction of the center's movement over several iterations.
• E[||N(0,I)||] — reference length of a random step (≈√n for n-dimensional space).
• c_σ, d_σ — learning rate and damping parameters.

If the norm ||p_σ|| exceeds the reference, it indicates consistent movement in one direction — the step increases. If it's lower, movement is erratic, and the step decreases to refine the position.

Advantages and Limitations of CMA-ES in ML Practice

CMA-ES is particularly useful in these scenarios:

• Nondifferentiable, noisy, or discontinuous objective functions.
• Search spaces with many local minima.
• Hyperparameters with varying sensitivity (e.g., learning_rate vs. batch_size).

However, it has limitations:

• Computational complexity grows with dimensionality (O(n²) due to storing C).
• Requires more iterations than TPE on smooth functions.
• Ineffective with very small evaluation budgets (< 20).

Recommendations for use in Optuna:

• Use CmaEsSampler for tasks with >5 hyperparameters or complex landscapes.
• Set restart_strategy='ipop' for automatic restarts with increased σ when stuck.
• For discrete parameters, use CategoricalCmaEsSampler.
• Always compare with TPE and RandomSearch on a validation dataset.

Key Points

• CMA-ES doesn't use gradients — works with any black box.
• Covariance matrix adaptation enables efficient progress along "valleys" in the objective function.
• Dynamic step size prevents premature convergence and accelerates final refinement.
• Shines with medium to large iteration counts (>50) and high-dimensional spaces.
• In Optuna, it's enabled by simply swapping the sampler — no model code changes needed.

The algorithm is especially valuable for tasks where standard methods (e.g., grid search or Bayesian optimization) falter: unstable metrics, complex parameter interactions, lack of smoothness. Its evolutionary nature makes it a robust, versatile tool for researchers tackling real-world, "messy" ML problems.

— Editorial Team