# Optimistic Optimization of Gaussian Process Samples

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 36 references that are in the map.
- First posted on arXiv 2 Sep 2022.

## Builds on (most cited first, 18 of 18)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Scalable Bayesian Optimization Using Deep Neural Networks](https://mlsanity.com/paper/1502.05700/) (2015)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance](https://mlsanity.com/paper/2010.13997/) (2020)
- [Emulation of physical processes with Emukit](https://mlsanity.com/paper/2110.13293/) (2021)
- [High-Dimensional Bayesian Optimization via Tree-Structured Additive Models](https://mlsanity.com/paper/2012.13088/) (2020)
- [Gaussian Process bandits with adaptive discretization](https://mlsanity.com/paper/1712.01447/) (2017)
- [Bayesian Multi-Scale Optimistic Optimization](https://mlsanity.com/paper/1402.7005/) (2014)
- [Scalable Bayesian Optimization Using Vecchia Approximations of Gaussian Processes](https://mlsanity.com/paper/2203.01459/) (2022)
- [Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretization](https://mlsanity.com/paper/2106.08598/) (2021)
- [Majorizing Measures for the Optimizer](https://mlsanity.com/paper/2012.13306/) (2020)
- [Probabilistic DAG Search](https://mlsanity.com/paper/2106.08717/) (2021)
- [Bayesian Optimistic Optimisation with Exponentially Decaying Regret](https://mlsanity.com/paper/2105.04332/) (2021)
- [Optimization for Gaussian Processes via Chaining](https://mlsanity.com/paper/1510.05576/) (2015)
- [Optimistic optimization of a Brownian](https://mlsanity.com/paper/1901.04884/) (2019)

## Abstract (arXiv)

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