Optimistic Optimization of a Brownian
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.
This paper considers a classic problem in Bayesian optimization, where we seek to maximize a one-dimensional function evaluated without noise with a Brownian motion prior.  Using a novel algorithm and analysis that builds on Munos 2011 but goes substantially beyond it, it shows that an epsilon-optimal point can be found using log^2(1/epsilon) samples.  This provides over the previous best-known rate for this problem.  The results are quite nice from the point of view of the theoretical foundations of Bayesian optimization.  Indeed, optimizing with a Brownian motion prior has been studied since the 1970s by Calvin and Zilinskas especially, and this result improves on all of those results.  Thus, I feel the work is of high quality.  The work is also original --- although the paper builds on work by Munos and Calvin, there is a lot that is new.  The paper is also quite clear.  The only problem is with the paper's significance for the NIPS community, which often wants to see meaningful empirical results and practical applicability.  Unfortunately one-dimensional problems are much less common in practice than multi-dimensional ones, and Wiener process priors often don't fit the functions we optimize very well.  I feel that this work *is* significant from a theory perspective, given the dearth of results on convergence rates for Bayesian optimization, and is a stepping stone to understanding rates for more practical settings.  Beyond this, I only have some minor advice on clarity:  Lipschitz discussion: When I read the initial parts of the paper, I found the discussion of Lipschitz continuity confusing, since the path of a Brownian motion is not differentiable, and I believe is not Lipschitz continuous in the classical sense.  Here we are looking at finite meshes of decreasing size, and so after reading into the body of the paper I understood what was meant, but perhaps there is a way to write the initial discussion in a way that does not confuse readers familiar with the infinite roughness of Brownian motion's paths.   Throughout, I find the word "Brownian" without "motion" or "bridge" strange.  I recommend talking about a "Brownian motion" rather than a "Brownian".  If you like, you could abbreviate this at BM.  Typos: line 117 typo: "The full proofs the auxiliary lemmas" line 139 typo: "achieving such PAC guarantee is low." line 150 and 151: it would be more clear to write the necessary condition for splitting as max(W(a),W(b)) >= M - eta*(b-a).