Research map / Probabilistic and scientific modeling / Bayesian optimization
Randomized Kriging Believer For Parallel Bayesian Optimization With 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 randomized kriging believer (RKB), which fills in pending evaluations with a single posterior sample rather than the posterior mean, and proves Bayesian cumulative and simple regret bounds for greedy parallel BO.
Problem
Parallel Bayesian optimization of expensive black-box functions with noisy observations, where greedy heuristics like kriging believer are practical but lack theoretical regret guarantees, while theory-backed methods perform poorly or are complex.
Approach
Replace the kriging believer's posterior-mean imputation for pending inputs with one posterior sample path, so the fantasized dataset has the same distribution as the true data conditioned on completed observations; this enables Bayesian regret analysis via a decomposition into fantasized regret plus sample error, with BSR independent of the number of workers Q.
Key results
- RKB is comparable to KB and LP across AF combinations, and RKB-PIMS and RKB-UCB perform at least as well as PTS, BUCB, and US in all reported cases (Q=8).
- RKB-PIMS performs comparably to or better than qEI across the reported experiments, while qEI underperformed significantly on the Shekel function.
- Theory: BCR bound O~(sqrt(Q T gamma_{T/Q})) for RKB, improving Q-dependence over the known O~(sqrt(QT gamma_T)); BSR bound B_T/T independent of Q.
Surprising findings
- qEI underperformed RKB-PIMS significantly on the Shekel function, though the paper reports no contrary example elsewhere.
Limitations
- BCR analysis requires uncertainty sampling in the initial phase to avoid an additional O(sqrt(Q)) term.
- BSR bound may be loose when Q is small.
- Regret analysis applies only to the single-sample case of RKB, not multi-sample MC averaging.
Experimental setup
Datasets: Ackley Hartmann6d Shekel Styblinski-Tang Olympus emulators
Benchmarks: Ackley Hartmann6d Shekel Styblinski-Tang Olympus emulators synthetic GP functions
Metrics: simple regret best objective value
Baselines: KB LP BUCB PTS uncertainty sampling qEI (qLEI/qLNEI) random search
Builds on: kriging believer GP-UCB PIMS batched UCB parallel Thompson sampling
Closest papers by meaning
- Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal (NeurIPS 2024 · similarity 0.86)
- Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency (ICML 2024 · similarity 0.86)
- A General Framework for User-Guided Bayesian Optimization (ICLR 2024 · similarity 0.86)
- Batched Energy-Entropy acquisition for Bayesian Optimization (NeurIPS 2024 · similarity 0.85)
- Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization (ICLR 2024 · similarity 0.85)
- Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds (ICML 2024 · similarity 0.85)
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.