Bayesian multi-scale optimistic optimization

Bayesian optimization is a powerful global op-timization technique for expensive black-box functions. One of its shortcomings is that it re-quires auxiliary optimization of an acquisition function at each iteration. This auxiliary opti-mization can be costly and very hard to carry out in practice. Moreover, it creates serious theoret-ical concerns, as most of the convergence results assume that the exact optimum of the acquisition function can be found. In this paper, we intro-duce a new technique for efficient global opti-mization that combines Gaussian process confi-dence bounds and treed simultaneous optimistic optimization to eliminate the need for auxiliary optimization of acquisition functions. The exper-iments with global optimization benchmarks and a novel application to automatic information ex-traction demonstrate that the resulting technique is more efficient than the two approaches from which it draws inspiration. Unlike most theo-retical analyses of Bayesian optimization with Gaussian processes, our finite-time convergence rate proofs do not require exact optimization of an acquisition function. That is, our approach eliminates the unsatisfactory assumption that a difficult, potentially NP-hard, problem has to be solved in order to obtain vanishing regret rates.