Skip to Main content Skip to Navigation
Conference papers

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
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [27 references]  Display  Hide  Download

https://hal.inria.fr/inria-00437140
Contributor : Olivier Teytaud <>
Submitted on : Sunday, November 29, 2009 - 3:36:30 PM
Last modification on : Tuesday, April 21, 2020 - 1:07:07 AM
Document(s) archivé(s) le : Thursday, June 17, 2010 - 7:05:49 PM

File

lion4long.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨inria-00437140⟩

Share

Metrics

Record views

601

Files downloads

393