On the codimension of the set of optima: large scale optimisation with few relevant variables

Vincent Berthier 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 : The complexity of continuous optimisation by comparison-based algorithms has been developed in several recent papers.Roughly speaking, these papers conclude that a precision can be reached with cost Θ(n log(1//)) in dimension n within polylogarithmic factors for the sphere function. Compared to other (non comparison-based) algorithms, this rate is not excellent; on the other hand, it is classically considered that comparison-based algorithms have some robustness advantages, as well as scalability on parallel machines and simplicity. In the present paper we show another advantage, namely resilience to useless variables, thanks to a complexity bound Θ(m log(1//)) where m is the codimension of the set of optima, possibly m << n. In addition, experiments show that some evolutionary algorithms have a negligible computational complexity even in high dimension, making them practical for huge problems with many useless variables.
Type de document :
Communication dans un congrès
Artificial Evolution 2015, 2015, Lyon, France. To appear, Proceedings of Artificial Evolution 2015 (EA2015)
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01194519
Contributeur : Olivier Teytaud <>
Soumis le : lundi 7 septembre 2015 - 10:44:39
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : mardi 8 décembre 2015 - 11:08:30

Fichier

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

Identifiants

  • HAL Id : hal-01194519, version 1

Citation

Vincent Berthier, Olivier Teytaud. On the codimension of the set of optima: large scale optimisation with few relevant variables. Artificial Evolution 2015, 2015, Lyon, France. To appear, Proceedings of Artificial Evolution 2015 (EA2015). 〈hal-01194519〉

Partager

Métriques

Consultations de la notice

335

Téléchargements de fichiers

139