Evolution Strategies with Additive Noise: A Convergence Rate Lower Bound

Sandra Astete-Morales 1, 2 Marie-Liesse Cauwet 1, 2 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 : We consider the problem of optimizing functions corrupted with additive noise. It is known that evolutionary algo-rithms can reach a simple regret O(1/ √ n) within logarith-mic factors, when n is the number of function evaluations. We show mathematically that this bound is tight, at least for a wide family of evolution strategies without large mutations.
Type de document :
Communication dans un congrès
Foundations of Genetic Algorithms, 2015, Aberythswyth, United Kingdom. ACM, pp.76--84, 2015, Foundations of Genetic Algorithms
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01077625
Contributeur : Olivier Teytaud <>
Soumis le : mardi 14 avril 2015 - 16:29:48
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : lundi 14 septembre 2015 - 08:35:59

Fichier

foga10.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01077625, version 2

Citation

Sandra Astete-Morales, Marie-Liesse Cauwet, Olivier Teytaud. Evolution Strategies with Additive Noise: A Convergence Rate Lower Bound. Foundations of Genetic Algorithms, 2015, Aberythswyth, United Kingdom. ACM, pp.76--84, 2015, Foundations of Genetic Algorithms. 〈hal-01077625v2〉

Partager

Métriques

Consultations de la notice

482

Téléchargements de fichiers

422