# Optimistic optimization of a Brownian

arXiv: https://arxiv.org/abs/1901.04884 · HTML: https://mlsanity.com/paper/1901.04884/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2019.

## Built on by (most cited first, 2 of 2)

- [Power of human-algorithm collaboration in solving combinatorial optimization problems](https://mlsanity.com/paper/2107.11784/) (2021)
- [Optimistic Optimization of Gaussian Process Samples](https://mlsanity.com/paper/2209.00895/) (2022)

## Abstract (arXiv)

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 log2(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.