Skip to Main content Skip to Navigation
Book sections

Lower Bounds for Evolution Strategies

Olivier Teytaud 1, 2 
2 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : The mathematical analysis of optimization algorithms involves upper and lower bounds; we here focus on the second case. Whereas other chap- ters will consider black box complexity, we will here consider complexity based on the key assumption that the only information available on the fitness values is the rank of individuals - we will not make use of the exact fitness values. Such a reduced information is known efficient in terms of ro- bustness (Gelly et al., 2007), what gives a solid theoretical foundation to the robustness of evolution strategies, which is often argued without mathemat- ical rigor - and we here show the implications of this reduced information on convergence rates. In particular, our bounds are proved without infi- nite dimension assumption, and they have been used since that time for designing algorithms with better performance in the parallel setting.
Document type :
Book sections
Complete list of metadata
Contributor : Olivier Teytaud Connect in order to contact the contributor
Submitted on : Friday, July 22, 2011 - 10:15:20 PM
Last modification on : Sunday, June 26, 2022 - 11:54:08 AM
Long-term archiving on: : Friday, November 4, 2011 - 3:16:03 PM


Files produced by the author(s)


  • HAL Id : inria-00593179, version 2



Olivier Teytaud. Lower Bounds for Evolution Strategies. Anne Auger, Benjamin Doerr. Theory of Randomized Search Heuristics, 1, World Scientific, pp.327-354, 2011, Series on Theoretical Computer Science. ⟨inria-00593179v2⟩



Record views


Files downloads