Randomized Kiring Believer for Parallel Bayesian Optimization with Regret Bounds

• URL: http://arxiv.org/abs/2603.01470v1
• Date: Mon, 02 Mar 2026 05:32:59 GMT
• Title: Randomized Kiring Believer for Parallel Bayesian Optimization with Regret Bounds
• Authors: Shuhei Sugiura, Ichiro Takeuchi, Shion Takeno,
• Abstract summary: We consider an optimization problem of an expensive-to-evaluate black-box function, in which we can obtain noisy function values in parallel.<n>For this problem, parallel Bayesian optimization (PBO) is a promising approach, which aims to optimize with fewer function evaluations.<n>We propose a PBO method, called randomized kriging believer (KB), based on a well-known KB and inheriting the advantages of the original KB.
• Score: 16.5939154690948
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  This paper reveals a unified game-theoretic connection between iterative BOND and self-play alignment.<n>We establish a novel framework, WIN rate Dominance (WIND), with a series of efficient algorithms for regularized win rate dominance optimization.
  arXiv  Detail & Related papers  (2024-10-28T04:47:39Z)
• Sample-efficient Bayesian Optimisation Using Known Invariances [56.34916328814857]
  We show that vanilla and constrained BO algorithms are inefficient when optimising invariant objectives. We derive a bound on the maximum information gain of these invariant kernels. We use our method to design a current drive system for a nuclear fusion reactor, finding a high-performance solution.
  arXiv  Detail & Related papers  (2024-10-22T12:51:46Z)
• Poisson Process for Bayesian Optimization [126.51200593377739]
  We propose a ranking-based surrogate model based on the Poisson process and introduce an efficient BO framework, namely Poisson Process Bayesian Optimization (PoPBO) Compared to the classic GP-BO method, our PoPBO has lower costs and better robustness to noise, which is verified by abundant experiments.
  arXiv  Detail & Related papers  (2024-02-05T02:54:50Z)
• Provably Efficient Bayesian Optimization with Unknown Gaussian Process Hyperparameter Estimation [44.53678257757108]
  We propose a new BO method that can sub-linearly converge to the objective function's global optimum. Our method uses a multi-armed bandit technique (EXP3) to add random data points to the BO process. We demonstrate empirically that our method outperforms existing approaches on various synthetic and real-world problems.
  arXiv  Detail & Related papers  (2023-06-12T03:35:45Z)
• New Paradigms for Exploiting Parallel Experiments in Bayesian Optimization [0.0]
  We present new parallel BO paradigms that exploit the structure of the system to partition the design space. Specifically, we propose an approach that partitions the design space by following the level sets of the performance function. Our results show that our approaches significantly reduce the required search time and increase the probability of finding a global (rather than local) solution.
  arXiv  Detail & Related papers  (2022-10-03T16:45:23Z)
• Batch Bayesian Optimization via Particle Gradient Flows [0.5735035463793008]
  We show how to find global optima of objective functions which are only available as a black-box or are expensive to evaluate. We construct a new function based on multipoint expected probability which is over the space of probability measures.
  arXiv  Detail & Related papers  (2022-09-10T18:10:15Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• Bayesian Optimization under Stochastic Delayed Feedback [36.16843889404038]
  Existing BO methods assume that the function evaluation (feedback) is available to the learner immediately or after a fixed delay. We propose algorithms with sub-linear regret guarantees that efficiently address the dilemma of selecting new function queries while waiting for delayed feedback.
  arXiv  Detail & Related papers  (2022-06-19T07:34:08Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs) Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
  arXiv  Detail & Related papers  (2021-02-27T19:28:39Z)
• Simple and Scalable Parallelized Bayesian Optimization [2.512827436728378]
  We propose a simple and scalable BO method for asynchronous parallel settings. Experiments are carried out with a benchmark function and hyperparameter optimization of multi-layer perceptrons.
  arXiv  Detail & Related papers  (2020-06-24T10:25:27Z)
• Time-varying Gaussian Process Bandit Optimization with Non-constant Evaluation Time [93.6788993843846]
  We propose a novel time-varying Bayesian optimization algorithm that can effectively handle the non-constant evaluation time. Our bound elucidates that a pattern of the evaluation time sequence can hugely affect the difficulty of the problem.
  arXiv  Detail & Related papers  (2020-03-10T13:28:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.