Optimistic optimization of a Brownian

Jean-Bastien Grill 1, 2 Michal Valko 1 Rémi Munos 2, 1
1 SEQUEL - Sequential Learning
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01906601
Contributor : Michal Valko <>
Submitted on : Sunday, January 13, 2019 - 11:07:45 PM
Last modification on : Friday, March 22, 2019 - 1:37:15 AM
Long-term archiving on : Sunday, April 14, 2019 - 1:16:24 PM

File

grill2018optimistic.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01906601, version 2

Citation

Jean-Bastien Grill, Michal Valko, Rémi Munos. Optimistic optimization of a Brownian. NeurIPS 2018 - Thirty-second Conference on Neural Information Processing Systems, Dec 2018, Montréal, Canada. ⟨hal-01906601v2⟩

Share

Metrics

Record views

46

Files downloads

190