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
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.
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 : Wednesday, March 27, 2019 - 4:41:29 PM
Long-term archiving on : 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

564

Files downloads

309