Comparison-based algorithms: worst-case optimality, optimality w.r.t a bayesian prior, the intraclass-variance minimization in EDA, and implementations with billiards

Sylvain Gelly 1 Sylvie Ruette 2 Olivier Teytaud 1
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : This paper is centered on the analysis of comparison-based algorithms. It has been shown recently that these algorithms are at most linearly convergent with a constant 1 − O(1/d); we here show that these algorithms are however optimal for robust optimization w.r.t increasing transformations of the fitness. We then turn our attention to the design of optimal comparison-based algorithms. No-Free-Lunch theorems have shown that introducing priors is necessary in order to design algorithms better than others; therefore, we include a bayesian prior in the spirit of learning theory. We show that these algorithms have a nice interpretation in terms of Estimation-Of-Distribution algorithms, and provide tools for the optimal design of generations of lambda-points by the way of billiard algorithms.
Type de document :
Communication dans un congrès
Parallel Problem Solving from Nature BTP-Workshop, Sep 2006, Reykjavik, 2006
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-00112813
Contributeur : Sylvain Gelly <>
Soumis le : jeudi 9 novembre 2006 - 17:10:26
Dernière modification le : jeudi 12 avril 2018 - 01:49:44
Document(s) archivé(s) le : mardi 6 avril 2010 - 18:40:13

Fichier

Identifiants

  • HAL Id : inria-00112813, version 1

Collections

Citation

Sylvain Gelly, Sylvie Ruette, Olivier Teytaud. Comparison-based algorithms: worst-case optimality, optimality w.r.t a bayesian prior, the intraclass-variance minimization in EDA, and implementations with billiards. Parallel Problem Solving from Nature BTP-Workshop, Sep 2006, Reykjavik, 2006. 〈inria-00112813〉

Partager

Métriques

Consultations de la notice

532

Téléchargements de fichiers

148