# Voronoi Candidates for Bayesian Optimization

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 53 references that are in the map.
- First posted on arXiv 7 Feb 2024.

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

- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Unexpected Improvements to Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2310.20708/) (2023)
- [Batched Large-scale Bayesian Optimization in High-dimensional Spaces](https://mlsanity.com/paper/1706.01445/) (2017)
- [Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search](https://mlsanity.com/paper/2007.00708/) (2020)
- [Multi-Objective Bayesian Optimization over High-Dimensional Search Spaces](https://mlsanity.com/paper/2109.10964/) (2021)
- [Scalable Constrained Bayesian Optimization](https://mlsanity.com/paper/2002.08526/) (2020)
- [Local Gaussian process approximation for large computer experiments](https://mlsanity.com/paper/1303.0383/) (2013)
- [Batched High-dimensional Bayesian Optimization via Structural Kernel Learning](https://mlsanity.com/paper/1703.01973/) (2017)
- [Active Learning for Deep Gaussian Process Surrogates](https://mlsanity.com/paper/2012.08015/) (2020)
- [Vecchia approximations of Gaussian-process predictions](https://mlsanity.com/paper/1805.03309/) (2018)
- [Triangulation candidates for Bayesian optimization](https://mlsanity.com/paper/2112.07457/) (2021)
- [Enhancing Gaussian Process Surrogates for Optimization and Posterior Approximation via Random Exploration](https://mlsanity.com/paper/2401.17037/) (2024)
- [Latin Hypercubes and Space-filling Designs](https://mlsanity.com/paper/2203.06334/) (2022)

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

- [Improving LLM-based Global Optimization with Search Space Partitioning](https://mlsanity.com/paper/2505.21372/) (2025)
- [Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient?](https://mlsanity.com/paper/2506.11831/) (2025)
- [Accelerated Inference for Partially Observed Markov Processes using Automatic Differentiation](https://mlsanity.com/paper/2407.03085/) (2024)
- [Scalable Batch Bayesian Optimization Via Subspace Acquisition Functions](https://mlsanity.com/paper/2411.16206/) (2024)
- [Actively Learning Joint Contours of Multiple Computer Experiments](https://mlsanity.com/paper/2512.13530/) (2025)

## Abstract (arXiv)

Bayesian optimization (BO) offers an elegant approach for efficiently optimizing black-box functions. However, acquisition criteria demand their own challenging inner-optimization, which can induce significant overhead. Many practical BO methods, particularly in high dimension, eschew a formal, continuous optimization of the acquisition function and instead search discretely over a finite set of space-filling candidates. Here, we propose to use candidates which lie on the boundary of the Voronoi tessellation of the current design points, so they are equidistant to two or more of them. We discuss strategies for efficient implementation by directly sampling the Voronoi boundary without explicitly generating the tessellation, thus accommodating large designs in high dimension. On a battery of test problems optimized via Gaussian processes with expected improvement, our proposed approach significantly improves the execution time of a multi-start continuous search without a loss in accuracy.