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, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
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 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 11 janvier 2018 - 06:22:14
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

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

261

Téléchargements de fichiers

171