Bayesian Optimization with Expected Improvement: No Regret and the Choice of Incumbent

• URL: http://arxiv.org/abs/2508.15674v1
• Date: Thu, 21 Aug 2025 15:55:16 GMT
• Title: Bayesian Optimization with Expected Improvement: No Regret and the Choice of Incumbent
• Abstract summary: We analyze the classic noisy Gaussian process expected improvement (GP-EI) algorithm.<n>We present for the first time the cumulative regret upper bounds of GP-EI with BPMI and BSPMI.<n>Our results provide theoretical guidance to the choice of incumbent when practitioners apply GP-EI in the noisy setting.
• Score: 2.6552364931990926
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Expected improvement (EI) is one of the most widely used acquisition functions in Bayesian optimization (BO). Despite its proven empirical success in applications, the cumulative regret upper bound of EI remains an open question. In this paper, we analyze the classic noisy Gaussian process expected improvement (GP-EI) algorithm. We consider the Bayesian setting, where the objective is a sample from a GP. Three commonly used incumbents, namely the best posterior mean incumbent (BPMI), the best sampled posterior mean incumbent (BSPMI), and the best observation incumbent (BOI) are considered as the choices of the current best value in GP-EI. We present for the first time the cumulative regret upper bounds of GP-EI with BPMI and BSPMI. Importantly, we show that in both cases, GP-EI is a no-regret algorithm for both squared exponential (SE) and Mat\'ern kernels. Further, we present for the first time that GP-EI with BOI either achieves a sublinear cumulative regret upper bound or has a fast converging noisy simple regret bound for SE and Mat\'ern kernels. Our results provide theoretical guidance to the choice of incumbent when practitioners apply GP-EI in the noisy setting. Numerical experiments are conducted to validate our findings.

Related papers

• Practical Efficient Global Optimization is No-regret [4.457235444806696]
  We present for the first time the cumulative regret upper bound of practical EGO.<n>We show that practical EGO has sublinear cumulative regret bounds and thus is a no-regret algorithm for commonly used kernels.
  arXiv  Detail & Related papers  (2026-03-26T10:58:17Z)
• Efficient Prior Selection in Gaussian Process Bandits with Thompson Sampling [6.466505075075075]
  We propose two algorithms for joint prior selection and regret minimization in GP bandits.<n>We theoretically analyze the algorithms and establish upper bounds for their respective regret.
  arXiv  Detail & Related papers  (2025-02-03T10:29:35Z)
• On the convergence rate of noisy Bayesian Optimization with Expected Improvement [2.250251490529229]
  Expected improvement (EI) is one of the most widely used acquisition functions in Bayesian optimization.<n>We contribute to the convergence theory process EI in three novel and critical areas.
  arXiv  Detail & Related papers  (2025-01-16T03:11:50Z)
• On Improved Regret Bounds In Bayesian Optimization with Gaussian Noise [2.250251490529229]
  convergence analysis of BO algorithms has focused on the cumulative regret under both the Bayesian and frequentist settings for the objective.<n>We establish new pointwise on the prediction error of GP under the frequentist setting with Gaussian noise.<n>We prove improved convergence rates of cumulative regret bound for both GP-UCB and GP-TS.
  arXiv  Detail & Related papers  (2024-12-25T05:57:27Z)
• Regret Analysis for Randomized Gaussian Process Upper Confidence Bound [9.967062483758632]
  This paper analyzes the randomized variant of GP-UCB called improved randomized GP-UCB.<n>We show that GP-UCB using a constant confidence parameter can incur linearly growing expected cumulative regret.
  arXiv  Detail & Related papers  (2024-09-02T06:49:29Z)
• On the Sublinear Regret of GP-UCB [58.25014663727544]
  We show that the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm enjoys nearly optimal regret rates. Our improvements rely on a key technical contribution -- regularizing kernel ridge estimators in proportion to the smoothness of the underlying kernel.
  arXiv  Detail & Related papers  (2023-07-14T13:56:11Z)
• Surrogate modeling for Bayesian optimization beyond a single Gaussian process [62.294228304646516]
  We propose a novel Bayesian surrogate model to balance exploration with exploitation of the search space. To endow function sampling with scalability, random feature-based kernel approximation is leveraged per GP model. To further establish convergence of the proposed EGP-TS to the global optimum, analysis is conducted based on the notion of Bayesian regret.
  arXiv  Detail & Related papers  (2022-05-27T16:43:10Z)
• Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization [63.8557841188626]
  The expected improvement (EI) algorithm is one of the most popular strategies for optimization under uncertainty. We propose a variant of EI with a standard incumbent defined via the GP predictive mean. We show that our algorithm converges, and achieves a cumulative regret bound of $mathcal O(gamma_TsqrtT)$.
  arXiv  Detail & Related papers  (2022-03-15T13:17:53Z)
• Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times [119.41129787351092]
  We show that sequential black-box optimization based on GPs can be made efficient by sticking to a candidate solution for multiple evaluation steps. We modify two well-established GP-Opt algorithms, GP-UCB and GP-EI to adapt rules from batched GP-Opt.
  arXiv  Detail & Related papers  (2022-01-30T20:42:14Z)
• Robust and Adaptive Temporal-Difference Learning Using An Ensemble of Gaussian Processes [70.80716221080118]
  The paper takes a generative perspective on policy evaluation via temporal-difference (TD) learning. The OS-GPTD approach is developed to estimate the value function for a given policy by observing a sequence of state-reward pairs. To alleviate the limited expressiveness associated with a single fixed kernel, a weighted ensemble (E) of GP priors is employed to yield an alternative scheme.
  arXiv  Detail & Related papers  (2021-12-01T23:15:09Z)
• Accounting for Gaussian Process Imprecision in Bayesian Optimization [0.0]
  We study the effect of the Gaussian processes' prior specifications on classical BO's convergence. We introduce PROBO as a generalization of BO that aims at rendering the method more robust towards prior mean parameter misspecification. We test our approach against classical BO on a real-world problem from material science and observe PROBO to converge faster.
  arXiv  Detail & Related papers  (2021-11-16T08:45:39Z)
• Uncertainty quantification using martingales for misspecified Gaussian processes [52.22233158357913]
  We address uncertainty quantification for Gaussian processes (GPs) under misspecified priors. We construct a confidence sequence (CS) for the unknown function using martingale techniques. Our CS is statistically valid and empirically outperforms standard GP methods.
  arXiv  Detail & Related papers  (2020-06-12T17:58:59Z)
• Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsification [119.41129787351092]
  We introduce BBKB, the first no-regret GP optimization algorithm that provably runs in near-linear time and selects candidates in batches. We show that the same bound can be used to adaptively delay costly updates to the sparse GP approximation, achieving a near-constant per-step amortized cost.
  arXiv  Detail & Related papers  (2020-02-23T17:43:29Z)

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.