On the convergence rate of noisy Bayesian Optimization with Expected Improvement

• URL: http://arxiv.org/abs/2501.09262v2
• Date: Wed, 12 Feb 2025 16:07:40 GMT
• Title: On the convergence rate of noisy Bayesian Optimization with Expected Improvement
• Abstract summary: 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.
• Score: 2.250251490529229
• 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 success in applications for decades, important open questions remain on the theoretical convergence behaviors and rates for EI. In this paper, we contribute to the convergence theory of EI in three novel and critical areas. First, we consider objective functions that fit under the Gaussian process (GP) prior assumption, whereas existing works mostly focus on functions in the reproducing kernel Hilbert space (RKHS). Second, we establish for the first time the asymptotic error bound and its corresponding rate for GP-EI with noisy observations under the GP prior assumption. Third, by investigating the exploration and exploitation properties of the non-convex EI function, we establish improved error bounds of GP-EI for both the noise-free and noisy cases.

Related papers

• Expected Improvement via Gradient Norms [2.542957206389996]
  Expected Improvement (EI) is known to be overly exploitative and can converge to suboptimal stationary points.<n>We propose Expected Improvement via Gradient Norms (EI-GN), a novel acquisition function that applies the improvement principle to a gradient-aware auxiliary objective.<n>EI-GN relies on gradient observations used to learn gradient-enhanced surrogate models that enable principled gradient inference from function evaluations.
  arXiv  Detail & Related papers  (2026-01-29T07:37:13Z)
• Bayesian Optimization with Expected Improvement: No Regret and the Choice of Incumbent [2.6552364931990926]
  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.
  arXiv  Detail & Related papers  (2025-08-21T15:55:16Z)
• A Unified Framework for Entropy Search and Expected Improvement in Bayesian Optimization [6.745285924097932]
  We introduce a unified theoretical framework, Variational Entropy Search, which reveals that EI and information-theoretic acquisition functions are more closely related than previously recognized. We propose VES-Gamma, a novel acquisition function that balances the strengths of EI and MES.
  arXiv  Detail & Related papers  (2025-01-30T21:15:00Z)
• Physics-Informed Bayesian Optimization of Variational Quantum Circuits [13.530592183149661]
  We propose a novel and powerful method to harness Bayesian optimization for Variational Quantum Eigensolvers (VQEs) We derive a VQE- Kernel which incorporates important prior information about quantum circuits. We also propose a novel acquisition function for Bayesian optimization called Maximum Improvement over Confident Regions (EMICoRe)
  arXiv  Detail & Related papers  (2024-06-10T10:17:06Z)
• Improving Kernel-Based Nonasymptotic Simultaneous Confidence Bands [0.0]
  The paper studies the problem of constructing nonparametric simultaneous confidence bands with nonasymptotic and distribition-free guarantees. The approach is based on the theory of Paley-Wiener kernel reproducing Hilbert spaces.
  arXiv  Detail & Related papers  (2024-01-28T22:43:33Z)
• A Corrected Expected Improvement Acquisition Function Under Noisy Observations [22.63212972670109]
  Sequential of expected improvement (EI) is one of the most widely used policies in Bayesian optimization. The uncertainty associated with the incumbent solution is often neglected in many analytic EI-type methods. We propose a modification of EI that corrects its closed-form expression by incorporating the covariance information provided by the Gaussian Process (GP) model.
  arXiv  Detail & Related papers  (2023-10-08T13:50:39Z)
• 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)
• Rectified Max-Value Entropy Search for Bayesian Optimization [54.26984662139516]
  We develop a rectified MES acquisition function based on the notion of mutual information. As a result, RMES shows a consistent improvement over MES in several synthetic function benchmarks and real-world optimization problems.
  arXiv  Detail & Related papers  (2022-02-28T08:11:02Z)
• 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)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)
• Randomised Gaussian Process Upper Confidence Bound for Bayesian Optimisation [60.93091603232817]
  We develop a modified Gaussian process upper confidence bound (GP-UCB) acquisition function. This is done by sampling the exploration-exploitation trade-off parameter from a distribution. We prove that this allows the expected trade-off parameter to be altered to better suit the problem without compromising a bound on the function's Bayesian regret.
  arXiv  Detail & Related papers  (2020-06-08T00:28:41Z)

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.