Discussing the article: "Covariance Matrix Adaptation Evolution Strategy (CMA-ES)"

[MetaQuotes]

Check out the new article: Covariance Matrix Adaptation Evolution Strategy (CMA-ES).

The article explores one of the most interesting non-gradient optimization algorithms, which learns to understand the geometry of the objective function. We will focus on the classical implementation of CMA-ES with a slight modification - replacing the normal distribution with the power one. We will thoroughly examine the math behind the algorithm, as well as practical implementation, and check where CMA-ES is unbeatable and where it should be avoided.

CMA-ES is based on a deceptively simple equation: x_k ~ N(m, σ²C). But behind this simplicity lies a deep mathematical structure. Each symbol here carries important information about the state of the search: m is the current best guess about the location of the optimum, σ is a measure of how far we are willing to risk moving away from the known, while C is a covariance matrix that encodes our understanding of the function geometry. The only change we can justify is replacing the normal distribution with a power distribution, which means that the implementation will follow a modified equation: x_k ~ PowerDist(m, σ²C). This modification changes the nature of the space exploration (wider "jumps"), but preserves the fundamental adaptive nature of the algorithm.

The covariance matrix C is the true heart of the algorithm. It begins its life as a humble identity matrix representing a spherical distribution. But with each iteration it evolves, stretching along directions of rapid improvement and shrinking where progress is slow. Gradually, the sphere turns into an ellipse, then into an elongated ellipsoid, ideally oriented along the contours of the function being optimized.

Author: Andrey Dik