Optimistic optimization of a Brownian
Type de document :
Communication dans un congrès avec actes
Titre :
Optimistic optimization of a Brownian
Auteur(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]
DeepMind [Paris]
Sequential Learning [SEQUEL]
Valko, Michal [Auteur]
Sequential Learning [SEQUEL]
Munos, Rémi [Auteur]
Sequential Learning [SEQUEL]
DeepMind [Paris]
Titre de la manifestation scientifique :
NeurIPS 2018 - Thirty-second Conference on Neural Information Processing Systems
Ville :
Montréal
Pays :
Canada
Date de début de la manifestation scientifique :
2018-12-02
Discipline(s) HAL :
Statistiques [stat]/Machine Learning [stat.ML]
Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-01906601v2/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-01906601v2/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-01906601v2/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- grill2018optimistic.pdf
- Accès libre
- Accéder au document