Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Bounds

Shuhei Sugiura; Ichiro Takeuchi; Shion Takeno

cs.LGMar 2, 2026

Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Bounds

Authors: Shuhei Sugiura, Ichiro Takeuchi, Shion Takeno

Organizations: Department of Engineering, Nagoya University, Aichi, Japan · RIKEN AIP, Tokyo, Japan

Abstract

We consider the 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, including those on real-data emulators.

Explore similar work

Local Preferential Bayesian Optimization
Jun 1, 2026Johanna Menn, Miriam Kober, Paul Brunzema +2Bayesian Optimization Parallel Continuous Local Search
B3O: Scalable Boltzmann Batch Bayesian Optimization
Jun 29, 2026Maximilian Bloor, Liyuan Xu, Hrvoje Stojic +1Bayesian Optimization
Optimal-Point Variance Reduction For Bayesian Optimization With Regret Guarantee
May 31, 2026Shion TakenoBayesian Optimization Variance Reduction

Jun 1, 2026 · cs.LGJ/K move · Enter open · S save

Local Preferential Bayesian Optimization

Johanna Menn, Miriam Kober, Paul Brunzema, David Stenger+1

Institute for Data Science in Mechanical Engineering, RWTH Aachen University, Aachen, Germany · Department of Clinical Research, University of Bern, Bern, Switzerland · Center for Reproducible Science and Research Synthesis, University of Zurich, Zurich, Switzerland · aiXopt GmbH, Aachen, Germany

Bayesian optimization (BO) is a popular and effective approach for tuning expensive, noisy experiments, but requires the formulation of an explicit objective function. Preferential BO (PBO) removes this requirement by learning from pairwise human feedback, yet existing methods struggle to efficiently optimize beyond low- and medium-dimensional problems due to their global search approaches. We address this limitation by developing a family of local PBO methods that transfer key ideas from high-dimensional BO to the preferential setting. In particular, we introduce local PBO methods which adapt trust-region and derivative-informed local search to pairwise preference feedback, where the latter exploits first- and second-order derivatives of the Laplace-approximated GP posterior. Our benchmark on GP sample paths, standard optimization benchmark functions, and policy-search tasks shows that local PBO methods are especially effective in high-dimensional and complex landscapes with steep optima. Compared with global preference-based baselines, they can substantially reduce cumulative regret, making them particularly useful for real-world preference-based optimization tasks such as policy search.

Bayesian Optimization Parallel Continuous Local Search Robust Preference Optimization Bayesian

Open paper Ask about it PDF

Abstract

Explore similar work

Local Preferential Bayesian Optimization

B3O: Scalable Boltzmann Batch Bayesian Optimization

Optimal-Point Variance Reduction For Bayesian Optimization With Regret Guarantee