# Stopping Bayesian Optimization with Probabilistic Regret Bounds

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 59 references that are in the map.
- First posted on arXiv 26 Feb 2024.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Doubly Stochastic Variational Inference for Deep Gaussian Processes](https://mlsanity.com/paper/1705.08933/) (2017)
- [GPflow: A Gaussian process library using TensorFlow](https://mlsanity.com/paper/1610.08733/) (2016)
- [Efficiently Sampling Functions from Gaussian Process Posteriors](https://mlsanity.com/paper/2002.09309/) (2020)
- [Maximizing acquisition functions for Bayesian optimization](https://mlsanity.com/paper/1805.10196/) (2018)
- [Uniform Error Bounds for Gaussian Process Regression with Application to Safe Control](https://mlsanity.com/paper/1906.01376/) (2019)
- [Pathwise Conditioning of Gaussian Processes](https://mlsanity.com/paper/2011.04026/) (2020)
- [A Study of Bayesian Neural Network Surrogates for Bayesian Optimization](https://mlsanity.com/paper/2305.20028/) (2023)
- [Optimization, fast and slow: optimally switching between local and Bayesian optimization](https://mlsanity.com/paper/1805.08610/) (2018)
- [Automatic Termination for Hyperparameter Optimization](https://mlsanity.com/paper/2104.08166/) (2021)
- [Optimal experimental design via Bayesian optimization: active causal structure learning for Gaussian process networks](https://mlsanity.com/paper/1910.03962/) (2019)
- [Posterior Variance Analysis of Gaussian Processes with Application to Average Learning Curves](https://mlsanity.com/paper/1906.01404/) (2019)
- [Lenient Regret and Good-Action Identification in Gaussian Process Bandits](https://mlsanity.com/paper/2102.05793/) (2021)
- [Trieste: Efficiently Exploring The Depths of Black-box Functions with TensorFlow](https://mlsanity.com/paper/2302.08436/) (2023)
- [Marginalised Gaussian Processes with Nested Sampling](https://mlsanity.com/paper/2010.16344/) (2020)

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

- [Generalists vs. Specialists: Evaluating LLMs on Highly-Constrained Biophysical Sequence Optimization Tasks](https://mlsanity.com/paper/2410.22296/) (2024)
- [Overtuning in Hyperparameter Optimization](https://mlsanity.com/paper/2506.19540/) (2025)
- [BayeSQP: Bayesian Optimization through Sequential Quadratic Programming](https://mlsanity.com/paper/2602.03232/) (2026)
- [Cost-aware Stopping for Bayesian Optimization](https://mlsanity.com/paper/2507.12453/) (2025)
- [A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Lifting](https://mlsanity.com/paper/2404.12219/) (2024)
- [Deterministic Global Optimization of the Acquisition Function in Bayesian Optimization: To Do or Not To Do?](https://mlsanity.com/paper/2503.03625/) (2025)
- [Cost-Sensitive Freeze-thaw Bayesian Optimization for Efficient Hyperparameter Tuning](https://mlsanity.com/paper/2510.21379/) (2025)
- [Local Entropy Search over Descent Sequences for Bayesian Optimization](https://mlsanity.com/paper/2511.19241/) (2025)
- [An (ε,δ)-accurate level set estimation with a stopping criterion](https://mlsanity.com/paper/2503.20272/) (2025)
- [Regret-Based (ε,δ)-optimal Stopping Criteria for Bayesian Optimization](https://mlsanity.com/paper/2605.22561/) (2026)
- [Converge Then Diversify: Decoupling Convergence and Diversity in Multi-Objective Bayesian Optimisation](https://mlsanity.com/paper/2609.13396/) (2026)

## Abstract (arXiv)

Bayesian optimization is a popular framework for efficiently tackling black-box search problems. As a rule, these algorithms operate by iteratively choosing what to evaluate next until some predefined budget has been exhausted. We investigate replacing this de facto stopping rule with criteria based on the probability that a point satisfies a given set of conditions. We focus on the prototypical example of an (ε, δ)-criterion: stop when a solution has been found whose value is within ε > 0 of the optimum with probability at least 1 - δ under the model. For Gaussian process priors, we show that Bayesian optimization satisfies this criterion under mild technical assumptions. Further, we give a practical algorithm for evaluating Monte Carlo stopping rules in a manner that is both sample efficient and robust to estimation error. These findings are accompanied by empirical results which demonstrate the strengths and weaknesses of the proposed approach.