Additive drift is all you need - if you are an evolution strategy

Drift analysis is a great tool for proving that optimization algorithms work the way we think they do, and for analyzing them, potentially in great detail. In this talk, I will discuss drift analysis for evolution strategies. These algorithms exhibit linear convergence on a wide range of problems, which corresponds to a linear decrease of the logarithmic distance of the best-so-far sample from the optimum, giving rise to simple additive drift. That behavior is enabled by online adaptation of the step size, which decays at the same rate as the distance to the optimum. Moreover, modern evolution strategies like CMA-ES adapt not only the step size, but rather the full covariance matrix of their sampling distribution. The mechanism enables convergence at a problem-independent rate that depends only on the dimension of the search space. The primary challenge of proving the convergence of CMA-ES lies in establishing the stability of the adaptation process, which was recently achieved by analyzing the invariant Markov chain that describes the parameter adaptation process. Yet, a drift-based analysis is still desirable because it can yield much more fine-grained results. For instance, it can provide details about the transient adaptation phase, which often takes up the lion's share of the time for solving the problem. To achieve this, we need a potential function that appropriately penalizes unsuitable parameter configurations, or more precisely, configurations the algorithm tends to move away from. Designing a potential function that captures the dynamics of covariance matrix adaptation is an ongoing challenge. I will present our recent research efforts towards this goal and emphasize why relatively simple additive drift offers a powerful framework for achieving it.