Lower bounds for evolution strategies using VC-dimension

Olivier Teytaud 1, 2 Hervé Fournier 3
2 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 for comparison-based or selection-based algorithms, improving existing results in the continuous setting, and extending them to non-trivial results in the discrete case. We introduce for that the use of the VC-dimension of the level sets of the fitness functions; results are then obtained through the use of Sauer's lemma. In the special case of optmization of the sphere function, improved lower bounds are obtained by bounding the possible number of sign conditions realized by some systems of equations. The results include several applications to the parametrization of sequential or parallel algorithms of type $\mul$-ES.
Type de document :
Communication dans un congrès
Parallel Problem Solving from Nature, Sep 2008, Dortmund, Germany. 10 p., 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00287845
Contributeur : Olivier Teytaud <>
Soumis le : vendredi 13 juin 2008 - 10:09:57
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : vendredi 28 septembre 2012 - 15:52:45

Fichier

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

Identifiants

  • HAL Id : inria-00287845, version 1

Collections

Citation

Olivier Teytaud, Hervé Fournier. Lower bounds for evolution strategies using VC-dimension. Parallel Problem Solving from Nature, Sep 2008, Dortmund, Germany. 10 p., 2008. 〈inria-00287845〉

Partager

Métriques

Consultations de la notice

248

Téléchargements de fichiers

180