Bandit-based Estimation of Distribution Algorithms for Noisy Optimization: Rigorous Runtime Analysis

Philippe Rolet 1 Olivier Teytaud 1, 2, 3
2 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
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 show complexity bounds for noisy optimization, in frame- works in which noise is stronger than in previously published papers[19]. We also propose an algorithm based on bandits (variants of [16]) that reaches the bound within logarithmic factors. We emphasize the differ- ences with empirical derived published algorithms.
Type de document :
Communication dans un congrès
Lion4, 2010, Venice, Italy. 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00437140
Contributeur : Olivier Teytaud <>
Soumis le : dimanche 29 novembre 2009 - 15:36:30
Dernière modification le : jeudi 12 avril 2018 - 01:46:05
Document(s) archivé(s) le : jeudi 17 juin 2010 - 19:05:49

Fichier

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

Identifiants

  • HAL Id : inria-00437140, version 1

Collections

Citation

Philippe Rolet, Olivier Teytaud. Bandit-based Estimation of Distribution Algorithms for Noisy Optimization: Rigorous Runtime Analysis. Lion4, 2010, Venice, Italy. 2010. 〈inria-00437140〉

Partager

Métriques

Consultations de la notice

333

Téléchargements de fichiers

188