Lower Bounds for Comparison Based Evolution Strategies using VC-dimension and Sign Patterns

Hervé Fournier 1 Olivier Teytaud 2, 3
3 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 : We derive lower bounds on the convergence rate of comparison based or selection based algorithms, improving existing results in the continuous setting, and extending them to non-trivial results in the discrete case. This is achieved by considering the VC-dimension of the level sets of the fitness functions; results are then obtained through the use of the shatter function lemma. In the special case of optimization of the sphere function, improved lower bounds are obtained by an argument based on the number of sign patterns.
Document type :
Journal articles
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download

https://hal.inria.fr/inria-00452791
Contributor : Olivier Teytaud <>
Submitted on : Wednesday, February 3, 2010 - 9:46:06 AM
Last modification on : Thursday, April 5, 2018 - 12:30:12 PM
Long-term archiving on : Friday, June 18, 2010 - 6:35:07 PM

File

evolution.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00452791, version 1

Collections

Citation

Hervé Fournier, Olivier Teytaud. Lower Bounds for Comparison Based Evolution Strategies using VC-dimension and Sign Patterns. Algorithmica, Springer Verlag, 2010. ⟨inria-00452791⟩

Share

Metrics

Record views

786

Files downloads

313