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
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 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.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00452791
Contributeur : Olivier Teytaud <>
Soumis le : mercredi 3 février 2010 - 09:46:06
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : vendredi 18 juin 2010 - 18:35:07

Fichier

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

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

737

Téléchargements de fichiers

251