[2603.01470] Randomized Kiring Believer for Parallel Bayesian Optimization with Regret Bounds

Computer Science > Machine Learning arXiv:2603.01470 (cs) [Submitted on 2 Mar 2026] Title:Randomized Kiring Believer for Parallel Bayesian Optimization with Regret Bounds Authors:Shuhei Sugiura, Ichiro Takeuchi, Shion Takeno View a PDF of the paper titled Randomized Kiring Believer for Parallel Bayesian Optimization with Regret Bounds, by Shuhei Sugiura and 2 other authors View PDF HTML (experimental) 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. Subjects: Machine Learning (cs.LG); Machine Learning (stat.ML) Cite as: arXiv:2603.01470 [cs.LG]   ...