Randomized Kriging Believer for Parallel Bayesian Optimization with Regret Bounds
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 39 of its 62 references that are in the map. First posted on arXiv 2 Mar 2026.
Builds on
39 of 62 references.
References · 39
- 2018A Tutorial on Bayesian Optimizationcited by 744
- 2017On Kernelized Multi-armed Banditscited by 352
- 2013Learning to Optimize Via Posterior Samplingcited by 256
- 2017Max-value Entropy Search for Efficient Bayesian Optimizationcited by 206
- 2014Predictive Entropy Search for Efficient Global Optimization of Black-box Functionscited by 204
- 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
- 2015High Dimensional Bayesian Optimisation and Bandits via Additive Modelscited by 139
- 2016Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Roboticscited by 134
- 2020Efficiently Sampling Functions from Gaussian Process Posteriorscited by 127
- 2017Multi-fidelity Bayesian Optimisation with Continuous Approximationscited by 121
- 2018Maximizing acquisition functions for Bayesian optimizationcited by 114
- 2015Batch Bayesian Optimization via Local Penalizationcited by 104
27 more
- 2018A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizationscited by 99
- 2017Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Spacecited by 76
- 2016The Parallel Knowledge Gradient Method for Batch Bayesian Optimizationcited by 74
- 2020Pathwise Conditioning of Gaussian Processescited by 64
- 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
- 2013Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Explorationcited by 50
- 2016Parallel Bayesian Global Optimization of Expensive Functionscited by 44
- 2020Scalable Thompson Sampling using Sparse Gaussian Process Modelscited by 39
- 2016Batched Gaussian Process Bandit Optimization via Determinantal Point Processescited by 33
- 2015Parallel Predictive Entropy Search for Batch Global Optimization of Expensive Objective Functionscited by 31
- 2020Olympus: a benchmarking framework for noisy optimization and experiment planningcited by 29
- 2021Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processescited by 24
- 2021Sequential- and Parallel- Constrained Max-value Entropy Search via Information Lower Boundcited by 23
- 2018Tight Regret Bounds for Bayesian Optimization in One Dimensioncited by 20
- 2023Towards Practical Preferential Bayesian Optimization with Skew Gaussian Processescited by 19
- 2021Bayesian Optimization for Cascade-type Multi-stage Processescited by 17
- 2023Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Boundscited by 16
- 2023Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Boundscited by 16
- 2025Improved Regret Analysis in Gaussian Process Bandits: Optimality for Noiseless Reward, RKHS norm, and Non-Stationary Variancecited by 15
- 2015Differentiating the multipoint Expected Improvement for optimal batch designcited by 13
- 2025Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimizationcited by 13
- 2019On Batch Bayesian Optimizationcited by 12
- 2019Fully Distributed Bayesian Optimization with Stochastic Policiescited by 9
- 2025Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Banditscited by 9
- 2023Bounding Box-based Multi-objective Bayesian Optimization of Risk Measures under Input Uncertaintycited by 5
- 2024Regret Analysis for Randomized Gaussian Process Upper Confidence Boundcited by 4
- 2025Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimizationcited by 4
Built on by
Citing papers per year: 2026: 2.
2 papers.