Hal will be stopped for maintenance from friday on june 10 at 4pm until monday june 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Tuesday, April 14, 2015 - 4:29:48 PM
Last modification on : Thursday, July 8, 2021 - 3:49:50 AM
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

340

Files downloads

622