Lower Bounds for Evolution Strategies

Olivier Teytaud 1, 2
2 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
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.
Type de document :
Chapitre d'ouvrage
Anne Auger, Benjamin Doerr. Theory of Randomized Search Heuristics, 1, World Scientific, pp.327-354, 2011, Series on Theoretical Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00593179
Contributeur : Olivier Teytaud <>
Soumis le : vendredi 22 juillet 2011 - 22:15:20
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : vendredi 4 novembre 2011 - 15:16:03

Fichier

ws-book9x6.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00593179, version 2

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

217

Téléchargements de fichiers

114