Research map / Learning theory and algorithms / Sample complexity
Stopping Bayesian Optimization with Probabilistic Regret Bounds
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a Bayesian optimization stopping rule that stops once a point is probably (1-δ under the GP model) ε-optimal, estimated by Monte Carlo with sequential confidence-interval testing, and proves termination and correctness under the model.
Problem
Standard Bayesian optimization runs until a fixed budget is exhausted; model-based stopping rules are hard to interpret because they rely on quantities like the optimum that are difficult to work with.
Approach
Stop when a solution is (ε, δ)-optimal under the GP posterior, i.e. P(f* - f(x) ≤ ε) ≥ 1-δ; estimate this probability by jointly sampling f(x) and f* from approximate posterior draws (Matheron's rule with feature maps) and decide via sequential Clopper-Pearson-style tests with a union-bound risk schedule.
Key results
- On GP-prior problems with known models, PRB reached the (ε,δ) success rate using the fewest evaluations among non-oracle methods in most settings (e.g., 17 vs 28 for Acq on 2D GP with noise 1e-6).
- Under MAP hyperparameters on Hartmann-6, 33% of runs converged to a local minimum (-3.20 vs global -3.32), showing sensitivity to model mismatch.
- Theory: BO with PRB stopping almost surely terminates and returns an (ε,δ)-optimal point under the model, given dense query sequences.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PRB instead of ΔCB | Bayesian optimization on GP priors with noise 10^-2, D=2 · GP prior, noise 10^-2, D=2 | median stopping time: 128 -> 23 | Helped |
| Use PRB instead of ΔCB | Bayesian optimization on GP priors with noise 10^-6, D=4 · GP prior, noise 10^-6, D=4 | median stopping time: 51 -> 64 | Hurt |
| Use PRB instead of Acq | Bayesian optimization on GP priors with noise 10^-2, D=6 · GP prior, noise 10^-2, D=6 | median stopping time: 181 -> 235 | Hurt |
| Use PRB instead of Acq | Bayesian optimization on GP models with noise 10^-6, D=4 · GP, noise 10^-6, D=4 | success rate: 100 -> 88 | Hurt |
| Use PRB instead of ΔCB | Bayesian optimization on Branin · Branin | median stopping time: 36 -> 33 | Helped |
| Use PRB instead of Acq | Bayesian optimization on Hartmann-6 · Hartmann, D=6 | success rate: 67 -> 64 | Hurt |
| Use PRB instead of ΔCB | Bayesian optimization on Rosenbrock-4 · Rosenbrock, D=4 | median stopping time: 88 -> 84 | Helped |
| Use PRB instead of ΔCB | Bayesian optimization on CNN tuning · CNN, D=4 | median stopping time: 64 -> 17 | Helped |
| Use PRB instead of ΔES | Bayesian optimization on XGBoost tuning · XGBoost, D=3 | median stopping time: 51 -> 28 | Helped |
| Use PRB as the stopping rule on known GP prior draws | Bayesian optimization · GP prior benchmarks | success rate | Helped |
| Use PRB with a maximum a posteriori model under model mismatch | Bayesian optimization on Hartmann-6 · Hartmann, D=6 | success rate: 33% | Hurt |
Surprising findings
- Model mismatch from broad hyperpriors caused premature stopping in some runs, notably on Hartmann-6.
- The ΔCB baseline often failed to terminate under moderate noise (γ²=1e-2) even when tuned.
Limitations
- Guarantees hold only under the model; model misspecification can cause premature or late stopping.
- Approximate posterior sampling via feature maps and non-convex optimization introduces unquantified errors.
- Requires a conservative fixed budget and sample-size schedule in practice; the Monte Carlo test is not always narrow enough to give guarantees under the 1000-draw cap.
Experimental setup
Datasets: MNIST income prediction dataset (Adult)
Benchmarks: GP synthetic functions (2,4,6 dims) Branin Hartmann-3 Hartmann-6 Rosenbrock-4 CNN hyperparameter tuning on MNIST XGBoost tuning on income prediction
Metrics: median stopping time (function evaluations) success rate of epsilon-optimal returns
Baselines: Oracle Budget oracle Acq (expected improvement stopping) ΔCB ΔES
Builds on: Gaussian process regression Matheron's rule for GP sampling Borell-TIS inequality Clopper-Pearson intervals Bayesian optimization stopping rules (ΔCB, ΔES)
Closest papers by meaning
- Regret-Based $(\epsilon,\delta)$-optimal Stopping Criteria for Bayesian Optimization (NeurIPS 2026 · similarity 0.93)
- Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds (ICML 2024 · similarity 0.90)
- Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency (ICML 2024 · similarity 0.90)
- Principled Preferential Bayesian Optimization (ICML 2024 · similarity 0.89)
- Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal (NeurIPS 2024 · similarity 0.89)
- BONSAI: Bayesian Optimization with Natural Simplicity and Interpretability (NeurIPS 2026 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.