Short-Term Scientific Mission

Analyzing a Non-Elitist Evolution Strategy Underlying Multiplicative Noise in the Objective Function Through Markov Chains

Main theme: Optimisation Under Uncertainty
Grantee: Alexander Jungeilges, Ruhr University Bochum, Bochum, Germany
Host: Anne Auger, Inria Saclay, Palaiseau, France

Start date: 2025-06-02
End date: 2025-06-20
Awarded: 2025-05-02
Report approved: 2025-07-22

Description

Convergence proofs for evolution strategies (ES) are restricted to noise-free settings, while state-of-the-art ES like CMA-ES perform well in noisy settings and are widely used in practice. The goal of this STSM is to fill this gap by developing the theoretical understanding of ES in the presence of multiplicative noise in the objective function. Specifically, a cumulative step-size adaptation (CSA) ES using Gaussian mutations will be analyzed with the well-established framework of Markov chains. Ideally, this leads to a linear convergence guarantee in expectation on noisy scaling-invariant functions and comparable results to those of classical stochastic approximation algorithms.

Achievements

The STSM contributed to a better theoretical understanding of evolution strategies affected by multiplicative noise in the objective function. The focus was on establishing an upper bound on the convergence rate, implying linear convergence, and estimating this bound in the asymptotic setting for the dimension going to infinity, thereby extending results from the noise-free case. Although the full objectives could not be achieved during the visit, key theoretical foundations were laid, and missing results were sketched, requiring further refinement. A continued collaboration was established to complete the work with the aim of a submitting a publication to GECCO 2026.