Noisy Optimization: Convergence with a Fixed Number of Resamplings
This work addresses convergence issues in noisy optimization for evolutionary algorithm practitioners, but it is incremental as it builds on prior theoretical results.
The paper tackles the problem of ensuring convergence in noisy optimization with evolutionary algorithms by establishing new sufficient conditions for convergence using a constant number of resamplings, achieving fast log-linear convergence rates when variance decreases faster than in multiplicative noise models.
It is known that evolution strategies in continuous domains might not converge in the presence of noise. It is also known that, under mild assumptions, and using an increasing number of resamplings, one can mitigate the effect of additive noise and recover convergence. We show new sufficient conditions for the convergence of an evolutionary algorithm with constant number of resamplings; in particular, we get fast rates (log-linear convergence) provided that the variance decreases around the optimum slightly faster than in the so-called multiplicative noise model. Keywords: Noisy optimization, evolutionary algorithm, theory.