New model for evolution strategies yields tight growth rate bounds
Researchers bypass fitness landscapes with invariant distribution model for ES analysis.
A new paper by Johannes Lengler and Raghu Raman Ravi (arXiv:2606.13323) introduces a simplified model for analyzing Evolution Strategies (ES), a class of optimization algorithms inspired by natural selection. The homogenous progress model bypasses detailed fitness landscapes by assuming that the relative fitness of an offspring compared to its parent follows an invariant distribution Z (e.g., a mean-shifted Gaussian). This abstraction allows rigorous analysis of ES behavior when operating far from the global optimum, common in real-world tasks like hyperparameter tuning or neural architecture search.
The authors focus on the continuous steady-state (μ+1)-ES, where overlapping generations create complex dependencies. They develop a general technique using modified processes that 'sandwich' the true process's growth rate, yielding tight bounds. For Gaussian noise Z = N(-δ, 1) and μ ≤ e^δ, they prove the expected growth rate R_μ = (log^{1+o(1)} μ)/μ * R_1. This result shows how population size μ scales performance, with implications for designing more efficient ES variants. The work bridges theory and practice, offering a tractable way to predict optimization progress in black-box settings.
- Homogenous progress model uses invariant distribution Z to model offspring fitness relative to parent.
- Sandwiching technique provides tight bounds on expected growth rate R_μ for (μ+1)-ES.
- For Gaussian Z and μ ≤ e^δ, growth rate scales as (log^{1+o(1)} μ)/μ * R_1.
Why It Matters
A theoretical lens for tuning ES hyperparameters, applicable to hard optimization problems like ML model tuning.