Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Bounds

Shuhei Sugiura, Ichiro Takeuchi, Shion Takeno

Abstract

We consider an optimization problem of an expensive-to-evaluate black-box function, in which we can obtain noisy function values in parallel. For this problem, parallel Bayesian optimization (PBO) is a promising approach, which aims to optimize with fewer function evaluations by selecting a diverse input set for parallel evaluation. However, existing PBO methods suffer from poor practical performance or lack theoretical guarantees. In this study, we propose a PBO method, called randomized kriging believer (KB), based on a well-known KB heuristic and inheriting the advantages of the original KB: low computational complexity, a simple implementation, versatility across various BO methods, and applicability to asynchronous parallelization. Furthermore, we show that our randomized KB achieves Bayesian expected regret guarantees. We demonstrate the effectiveness of the proposed method through experiments on synthetic and benchmark functions and emulators of real-world data.

Introduction

Bayesian Optimization (BO) is a powerful framework for global optimization of expensive black-box functions, such as hyperparameter tuning in deep learning or experimental design in chemistry. While standard BO is sequential, modern computational and experimental resources often allow for parallel evaluations. The primary challenge in Parallel Bayesian Optimization (PBO) is ensuring diversity among the selected points to avoid redundant evaluations in the same region of the search space.

Existing PBO strategies generally fall into two categories: fast heuristics that lack theoretical guarantees (e.g., Kriging Believer) and theoretically sound methods that may exhibit poor practical performance or high complexity (e.g., Parallel Thompson Sampling). This paper introduces Randomized Kriging Believer (RKB), a method that bridges this gap by providing both high practical efficiency and rigorous theoretical regret bounds.

Methodology: From Heuristics to Randomized Kriging Believer

The RKB method is an evolution of the classic Kriging Believer (KB) heuristic. In the original KB, when a point is selected for evaluation but the result is pending, the algorithm "fantasizes" that the outcome will be exactly the current posterior mean. This fantasized data point is added to the model to reduce uncertainty in that region, thereby encouraging the selection of diverse points for the rest of the parallel batch.

RKB replaces this deterministic fantasy with a random sample drawn from the posterior distribution at the pending points. This stochastic approach ensures that the fantasized dataset follows the same distribution as the true underlying function, conditioned on observed data.

Illustration of the RKB process across three iterations. The method uses "fantasized data" (cyan dots) sampled from the posterior to update the predictive mean (orange line) and uncertainty (orange shaded area) before selecting the next evaluation point (red line).

By utilizing posterior sampling, RKB allows for the application of Thompson Sampling analysis techniques. A key theoretical result of this work is that the Bayesian Simple Regret (BSR) bound for RKB is independent of the number of parallel workers ($Q$), indicating excellent scalability for large-scale parallelization. Furthermore, RKB is "acquisition function independent," meaning it can be used as a wrapper for various standard functions like Expected Improvement (EI) or Upper Confidence Bound (UCB).

Experimental Evaluation

The authors evaluated RKB against several baselines, including the original KB, Local Penalization (LP), Parallel Thompson Sampling (PTS), and Batched UCB (BUCB). The evaluation spanned three distinct tiers:

  1. Synthetic Functions: Testing under ideal Gaussian Process model conditions.
  2. Standard Benchmarks: Classic optimization problems such as Ackley, Hartmann6d, and Styblinski-Tang.
  3. Real-World Emulators: Nine emulators from the Olympus framework, representing real experimental data in chemistry and materials science.

Key Results

  • Performance: RKB consistently matched or exceeded the performance of the best-performing heuristics.
  • Efficiency: Unlike Parallel Thompson Sampling, which often over-explores, RKB maintains a better balance, leading to faster convergence on benchmark functions.
  • Synergy with PIMS: The combination of RKB with the PIMS (Probability of Improvement with Minimal Sampling) acquisition function proved particularly effective across complex real-world emulators.

Discussion and Conclusion

The introduction of randomization to the Kriging Believer heuristic provides the necessary mathematical foundation to prove convergence while maintaining the greedy efficiency that makes heuristics attractive. While the current theory assumes an initial "uncertainty sampling" phase, practical applications of RKB show robust performance even without it. Future work may extend this framework to frequentist regret analysis, multi-objective optimization, and constrained optimization scenarios. RKB stands as a versatile, simple-to-implement, and theoretically grounded solution for modern parallel optimization challenges.

Summary updated

Abstract

We consider an optimization problem of an expensive-to-evaluate black-box function, in which we can obtain noisy function values in parallel. For this problem, parallel Bayesian optimization (PBO) is a promising approach, which aims to optimize with fewer function evaluations by selecting a diverse input set for parallel evaluation. However, existing PBO methods suffer from poor practical performance or lack theoretical guarantees. In this study, we propose a PBO method, called randomized kriging believer (KB), based on a well-known KB heuristic and inheriting the advantages of the original KB: low computational complexity, a simple implementation, versatility across various BO methods, and applicability to asynchronous parallelization. Furthermore, we show that our randomized KB achieves Bayesian expected regret guarantees. We demonstrate the effectiveness of the proposed method through experiments on synthetic and benchmark functions and emulators of real-world data.
BibTeX
@misc{sugiura2026randomized,
  author = {Shuhei Sugiura and Ichiro Takeuchi and Shion Takeno},
  title = {{Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Bounds}},
  year = {2026},
  eprint = {2603.01470},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.01470},
}
Figure