  Bayesian optimization is a popular formalism for global optimization, but its
computational costs limit it to expensive-to-evaluate functions. A competing,
computationally more efficient, global optimization framework is optimistic
optimization, which exploits prior knowledge about the geometry of the search
space in form of a dissimilarity function. We investigate to which degree the
conceptual advantages of Bayesian Optimization can be combined with the
computational efficiency of optimistic optimization. By mapping the kernel to a
dissimilarity, we obtain an optimistic optimization algorithm for the Bayesian
Optimization setting with a run-time of up to $\mathcal{O}(N \log N)$. As a
high-level take-away we find that, when using stationary kernels on objectives
of relatively low evaluation cost, optimistic optimization can be strongly
preferable over Bayesian optimization, while for strongly coupled and
parametric models, good implementations of Bayesian optimization can perform
much better, even at low evaluation cost. We argue that there is a new research
domain between geometric and probabilistic search, i.e. methods that run
drastically faster than traditional Bayesian optimization, while retaining some
of the crucial functionality of Bayesian optimization.
