Optimistic optimization of a Brownian

Grill, Jean-Bastien; Valko, Michal; Munos, Rémi

Document type :

Communication dans un congrès avec actes

Title :

Optimistic optimization of a Brownian

Author(s) :

Grill, Jean-Bastien [Auteur]
DeepMind [Paris]
Sequential Learning [SEQUEL]
Valko, Michal [Auteur]

Sequential Learning [SEQUEL]
Munos, Rémi [Auteur]
Sequential Learning [SEQUEL]
DeepMind [Paris]

Conference title :

NeurIPS 2018 - Thirty-second Conference on Neural Information Processing Systems

City :

Montréal

Country :

Canada

Start date of the conference :

2018-12-02

HAL domain(s) :

Statistiques [stat]/Machine Learning [stat.ML]

English abstract : [en]

We address the problem of optimizing a Brownian motion. We consider a (random) realization W of a Brownian motion with input space in [0, 1]. Given W, our goal is to return an ε-approximation of its maximum using the ...
Show more >We address the problem of optimizing a Brownian motion. We consider a (random) realization W of a Brownian motion with input space in [0, 1]. Given W, our goal is to return an ε-approximation of its maximum using the smallest possible number of function evaluations, the sample complexity of the algorithm. We provide an algorithm with sample complexity of order log 2 (1/ε). This improves over previous results of Al-Mharmah and Calvin (1996) and Calvin et al. (2017) which provided only polynomial rates. Our algorithm is adaptive-each query depends on previous values-and is an instance of the optimism-in-the-face-of-uncertainty principle.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

ANR Project :

Inférence bayésienne à ressources limitées - données massives et modèles coûteux

Collections :