Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-01077625
Contributor : Olivier Teytaud <>
Submitted on : Tuesday, April 14, 2015 - 4:29:48 PM
Last modification on : Wednesday, September 16, 2020 - 5:09:24 PM
Long-term archiving on: : Monday, September 14, 2015 - 8:35:59 AM

File

foga10.pdf
Files produced by the author(s)

Identifiers

  • 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. pp.76--84. ⟨hal-01077625v2⟩

Share

Metrics

Record views

589

Files downloads

798