mlsanityData to 13 Oct 2026

Stopping Bayesian Optimization with Probabilistic Regret Bounds

arXiv 2402.16811 ↗First posted 26 Feb 2024stat.ML cs.LGcited by 11

Not on the map. Why?

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.

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

Builds on

18 of 59 references.

References · 18

  1. 2016XGBoost: A Scalable Tree Boosting Systemcited by 5,143
  2. 2016The CMA Evolution Strategy: A Tutorialcited by 368
  3. 2017Max-value Entropy Search for Efficient Bayesian Optimizationcited by 203
  4. 2014Predictive Entropy Search for Efficient Global Optimization of Black-box Functionscited by 202
  5. 2017Doubly Stochastic Variational Inference for Deep Gaussian Processescited by 143
  6. 2016GPflow: A Gaussian process library using TensorFlowcited by 139
  7. 2020Efficiently Sampling Functions from Gaussian Process Posteriorscited by 126
  8. 2018Maximizing acquisition functions for Bayesian optimizationcited by 113
  9. 2019Uniform Error Bounds for Gaussian Process Regression with Application to Safe Controlcited by 64
  10. 2020Pathwise Conditioning of Gaussian Processescited by 64
  11. 2023A Study of Bayesian Neural Network Surrogates for Bayesian Optimizationcited by 50
  12. 2018Optimization, fast and slow: optimally switching between local and Bayesian optimizationcited by 22
6 more
  1. 2021Automatic Termination for Hyperparameter Optimizationcited by 21
  2. 2019Optimal experimental design via Bayesian optimization: active causal structure learning for Gaussian process networkscited by 18
  3. 2019Posterior Variance Analysis of Gaussian Processes with Application to Average Learning Curvescited by 12
  4. 2021Lenient Regret and Good-Action Identification in Gaussian Process Banditscited by 12
  5. 2023Trieste: Efficiently Exploring The Depths of Black-box Functions with TensorFlowcited by 11
  6. 2020Marginalised Gaussian Processes with Nested Samplingcited by 7

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2024: 2; 2025: 6; 2026: 3.

11 papers.

  1. 2024Generalists vs. Specialists: Evaluating LLMs on Highly-Constrained Biophysical Sequence Optimization Taskscited by 8
  2. 2025Overtuning in Hyperparameter Optimizationcited by 5
  3. 2026BayeSQP: Bayesian Optimization through Sequential Quadratic Programmingcited by 5
  4. 2025Cost-aware Stopping for Bayesian Optimizationcited by 4
  5. 2024A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Liftingcited by 3
  6. 2025Deterministic Global Optimization of the Acquisition Function in Bayesian Optimization: To Do or Not To Do?cited by 3
  7. 2025Cost-Sensitive Freeze-thaw Bayesian Optimization for Efficient Hyperparameter Tuningcited by 2
  8. 2025Local Entropy Search over Descent Sequences for Bayesian Optimizationcited by 1
  9. 2025An (ε,δ)-accurate level set estimation with a stopping criterioncited by 0
  10. 2026Regret-Based (ε,δ)-optimal Stopping Criteria for Bayesian Optimizationcited by 0
  11. 2026Converge Then Diversify: Decoupling Convergence and Diversity in Multi-Objective Bayesian Optimisationcited by 0