# On the convergence rate of noisy Bayesian Optimization with Expected Improvement

arXiv: https://arxiv.org/abs/2501.09262 · HTML: https://mlsanity.com/paper/2501.09262/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 33 references that are in the map.
- First posted on arXiv 16 Jan 2025.

## Builds on (most cited first, 11 of 11)

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Scalable Constrained Bayesian Optimization](https://mlsanity.com/paper/2002.08526/) (2020)
- [Recent Advances in Bayesian Optimization](https://mlsanity.com/paper/2206.03301/) (2022)
- [Uniform Error Bounds for Gaussian Process Regression with Application to Safe Control](https://mlsanity.com/paper/1906.01376/) (2019)
- [Theoretical Analysis of Bayesian Optimisation with Unknown Gaussian Process Hyper-Parameters](https://mlsanity.com/paper/1406.7758/) (2014)
- [Bayesian Optimization with Expensive Integrands](https://mlsanity.com/paper/1803.08661/) (2018)
- [A supermartingale approach to Gaussian process based sequential design of experiments](https://mlsanity.com/paper/1608.01118/) (2016)
- [Bayesian Distributionally Robust Optimization](https://mlsanity.com/paper/2112.08625/) (2021)
- [Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2203.07875/) (2022)
- [Adjusted Expected Improvement for Cumulative Regret Minimization in Noisy Bayesian Optimization](https://mlsanity.com/paper/2205.04901/) (2022)

## Built on by (most cited first, 4 of 4)

- [Regret Analysis of Posterior Sampling-Based Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2507.09828/) (2025)
- [Convergence Rates of Constrained Expected Improvement](https://mlsanity.com/paper/2505.11323/) (2025)
- [Simple-regret rates and minimax optimality of fixed-prior expected improvement in Mat'ern and squared-exponential RKHSs](https://mlsanity.com/paper/2607.29245/) (2026)
- [Nonparametric Bayesian Optimization for General Rewards](https://mlsanity.com/paper/2602.07411/) (2026)

## Abstract (arXiv)

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.