Theory of Evolution Strategies: A New Perspective

Evolution Strategies (ESs) are stochastic optimization algorithms rec-ognized as powerful algorithms for difficult optimization problems in a black-box scenario. Together with other stochastic search algorithms for continuous domain (like Differential Evolution, Estimation of Distribution Algorithms, Particle Swarm Optimization, Simulated Annealing.) they are so-called global optimization algorithms, as opposed to gradient- based algorithms usually referred to as local search algorithms. Many theoretical works on stochastic optimization algorithms focus on investigating convergence to the global optimum with probability one, under very mild assumptions on the objective functions. On the other hand, the theory of Evolution Strategies has been restricted for a long time to the so-called progress rate theory, analyzing the one-step progress of ESs on unimodal, possibly noisy functions. This chapter covers global convergence results, revealing slow convergence rates on a wide class of functions, and fast convergence results on more restricted function classes. After reviewing the important components of ESs algorithms, we illustrate how global convergence with probability one can be proven easily. We recall two important classes of convergence, namely sub-linear and linear convergence, corresponding to the convergence class of the pure random search and to the optimal convergence class for rank-based algorithms respectively. We review different lower and upper bounds for adaptive ESs, and explain the link between lower bounds and the progress rate theory. In the last part, we focus on recent results on linear convergence of adaptive ESs for the class of spherical and ellipsoidal functions, we explain how almost sure linear convergence can be proven using different laws of large numbers (LLN).