Reconsidering the Progress Rate Theory for Evolution Strategies in Finite Dimensions

Auger, A. and Hansen N. (2006). In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2006), pp.445-452, ACM Press

This paper investigates the limits of the predictions based on the classical progress rate theory for Evolution Strategies. We explain on the sphere function why positive progress rates give convergence in mean, negative progress rates divergence in mean and show that almost sure convergence can take place despite divergence in mean. Hence step-sizes associated to negative progress can actually lead to almost sure convergence. Based on these results we provide an alternative progress rate definition related to almost sure convergence. We present Monte Carlo simulations to investigate the discrepancy between both progress rates and therefore both types of convergence. This discrepancy vanishes when dimension increases. The observation is supported by an asymptotic estimation of the new progress rate definition.