Asymptotic Growth Rate of (μ+1)-ES Solved for Homogeneous Progress Model

For nearly half a century, the (μ+1)-ES has been a workhorse of black-box optimization, yet its expected fitness growth rate has resisted tight theoretical bounds—until a new model cuts through the landscape mess by assuming mutation outcomes follow a simple invariant distribution.

Bypassing the Fitness Landscape

The model drops the usual dependence on an explicit fitness function and instead assumes that any mutation produces an offspring whose fitness relative to its parent is drawn from a fixed distribution Z—for example, a Gaussian with mean -δ and unit variance. This isn't meant to be realistic for every problem; it captures the regime where the algorithm operates far from the global optimum and the local geometry is roughly stationary. The authors use this to approximate optimization in cases where exact fitness modeling is intractable, including hyperparameter tuning in ML pipelines.

Sandwiching the Steady-State Dynamics

Unlike comma-selection strategies that discard all parents each generation, the steady-state (μ+1)-ES keeps overlapping generations. That overlap creates complex dependencies among surviving parents, making standard drift analysis messy. The new work introduces a general technique: construct two modified processes whose expected growth rates provably sandwich the true rate. Each modified process is easier to analyze, yet close enough to the original to yield a tight bound. This approach sidesteps the tangled correlations without losing predictive power—a clean mathematical trick.

The Gaussian Case and the Asymptotic Result

When Z is a standard normal shifted by -δ (so offspring are on average worse by δ), and the parent population size μ satisfies μ ≤ e^δ, the bound collapses to a clean form:

$$\mathcal{R}_{\mu} = \frac{\log^{1 + o(1)} \mu}{\mu} \mathcal{R}_1$$

Here R_1 is the growth rate for a single parent (the (1+1)-ES). The logarithmic factor means that adding more parents slows the per-individual progress rate, but the slowdown is gentler than a pure 1/μ penalty. For practitioners, this quantifies the trade-off between population diversity and convergence speed in a way that doesn't depend on the fine details of the problem.

These results give theoreticians a concrete tool to reason about ES dynamics on hard problems, and they open the door to similar analysis for other steady-state EA variants. The sandwich technique alone is worth stealing for your next convergence proof.

Source: Runtime Analysis of the $(\mu + 1)$-ES in a Homogenous Progress Model
Domain: arxiv.org