Runtime Analysis of the $(μ+ 1)$-ES in a Homogenous Progress Model
This provides a theoretical foundation for understanding the runtime of ES in complex optimization landscapes, particularly for hyperparameter tuning in machine learning.
The paper introduces a simple model to study the fitness progress of Evolution Strategies (ES) in generic problems, bypassing the underlying fitness landscape. It rigorously analyzes the expected growth rate of the $(μ+1)$-ES, showing that for Gaussian mutations with mean shift -δ, the growth rate scales as $ rac{\log^{1 + o(1)} μ}μ \mathcal{R}_1$ when $μ ≤ e^δ$.
We introduce a new simple model to study the fitness progress of Evolution Strategies (ES) in generic problems. In this model, we bypass the underlying fitness landscape and assume that the mutation of any individual produces an offspring whose fitness relative to the parent is given by an invariant distribution $Z$, such as a mean-shifted Gaussian. This serves as a prototypical model for the optimisation landscape when an evolution algorithm operates far from the global optimum. This simple model can be used to approximate the optimisation process for problems where it is intractable to model the exact fitness function, including tasks such as hyperparameter tuning in machine learning models. We rigorously analyse the expected growth rate $\mathcal{R}_μ$ of the continuous steady-state $(μ+1)$-ES in this model. Unlike comma-selection strategies, the steady-state $(μ+1)$-ES maintains overlapping generations, introducing complex mathematical dependencies among surviving parents that make it harder to analyse. We give a general technique to analyse the the $(μ+ 1)$-ES by constructing modified processes whose growth rates provably sandwich that of the original process. These modified processes are then easier to analyse but still close enough to the true process to give a tight bound on the expected growth rate. When $Z = \mathcal{N}(-δ, 1)$ and $μ\le e^δ$, we show that $\mathcal{R}_μ = \frac{\log^{1 + o(1)} μ}μ \mathcal{R}_1$.