Optimistic optimization of a Brownian - Archive ouverte HAL Access content directly
Conference Papers Year :

Optimistic optimization of a Brownian

(1, 2) , (1) , (2, 1)
1
2
Jean-Bastien Grill
  • Function : Author
  • PersonId : 972490
Michal Valko
Rémi Munos
  • Function : Author
  • PersonId : 836863

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.
Fichier principal
Vignette du fichier
grill2018optimistic.pdf (1.21 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01906601 , version 1 (27-10-2018)
hal-01906601 , version 2 (13-01-2019)

Identifiers

  • HAL Id : hal-01906601 , version 2

Cite

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⟩
139 View
117 Download

Share

Gmail Facebook Twitter LinkedIn More