# Bayesian Multi-Scale Optimistic Optimization

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2014.

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

- [Multi-objective Optimization by Learning Space Partitions](https://mlsanity.com/paper/2110.03173/) (2021)
- [Self-focusing virtual screening with active design space pruning](https://mlsanity.com/paper/2205.01753/) (2022)
- [Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretization](https://mlsanity.com/paper/2106.08598/) (2021)
- [High-dimensional Bayesian Optimization via Covariance Matrix Adaptation Strategy](https://mlsanity.com/paper/2402.03104/) (2024)
- [Instance-Dependent Regret Analysis of Kernelized Bandits](https://mlsanity.com/paper/2203.06297/) (2022)
- [Bayesian Optimistic Optimisation with Exponentially Decaying Regret](https://mlsanity.com/paper/2105.04332/) (2021)
- [Robust Bayesian Target Value Optimization](https://mlsanity.com/paper/2301.04344/) (2023)
- [LABCAT: Locally adaptive Bayesian optimization using principal-component-aligned trust regions](https://mlsanity.com/paper/2311.11328/) (2023)
- [Time-Varying Bayesian Optimization Without a Metronome](https://mlsanity.com/paper/2501.18963/) (2025)
- [Searching in the Forest for Local Bayesian Optimization](https://mlsanity.com/paper/2111.05834/) (2021)
- [Optimistic Optimization of Gaussian Process Samples](https://mlsanity.com/paper/2209.00895/) (2022)

## Abstract (arXiv)

Bayesian optimization is a powerful global optimization technique for expensive black-box functions. One of its shortcomings is that it requires auxiliary optimization of an acquisition function at each iteration. This auxiliary optimization can be costly and very hard to carry out in practice. Moreover, it creates serious theoretical concerns, as most of the convergence results assume that the exact optimum of the acquisition function can be found. In this paper, we introduce a new technique for efficient global optimization that combines Gaussian process confidence bounds and treed simultaneous optimistic optimization to eliminate the need for auxiliary optimization of acquisition functions. The experiments with global optimization benchmarks and a novel application to automatic information extraction demonstrate that the resulting technique is more efficient than the two approaches from which it draws inspiration. Unlike most theoretical 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.