# Convergence Rates of Constrained Expected Improvement

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 44 references that are in the map.
- First posted on arXiv 16 May 2025.

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

- [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)
- [Bayesian Optimization with Unknown Constraints](https://mlsanity.com/paper/1403.5607/) (2014)
- [Constrained Bayesian Optimization with Noisy Experiments](https://mlsanity.com/paper/1706.07094/) (2017)
- [Uniform Error Bounds for Gaussian Process Regression with Application to Safe Control](https://mlsanity.com/paper/1906.01376/) (2019)
- [Predictive Entropy Search for Bayesian Optimization with Unknown Constraints](https://mlsanity.com/paper/1502.05312/) (2015)
- [Bayesian optimization under mixed constraints with a slack-variable augmented Lagrangian](https://mlsanity.com/paper/1605.09466/) (2016)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Regret Bounds for Noise-Free Kernel-Based Bandits](https://mlsanity.com/paper/2002.05096/) (2020)
- [Bayesian Optimisation for Constrained Problems](https://mlsanity.com/paper/2105.13245/) (2021)
- [Gaussian Process Upper Confidence Bound Achieves Nearly-Optimal Regret in Noise-Free Gaussian Process Bandits](https://mlsanity.com/paper/2502.19006/) (2025)
- [Efficient Batch Black-box Optimization with Deterministic Regret Bounds](https://mlsanity.com/paper/1905.10041/) (2019)
- [On the convergence rate of noisy Bayesian Optimization with Expected Improvement](https://mlsanity.com/paper/2501.09262/) (2025)

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

- [Counterfactual Credit Guided Bayesian Optimization](https://mlsanity.com/paper/2510.04676/) (2025)
- [Local Constrained Bayesian Optimization](https://mlsanity.com/paper/2603.07965/) (2026)

## Abstract (arXiv)

Constrained Bayesian optimization (CBO) methods have seen significant success in black-box optimization with constraints. One of the most commonly used CBO methods is the constrained expected improvement (CEI) algorithm. CEI is a natural extension of expected improvement (EI) when constraints are incorporated. However, the theoretical convergence rate of CEI has not been established. In this work, we study the convergence rate of CEI by analyzing its simple regret upper bound. First, we show that when the objective function f and constraint function c are assumed to each lie in a reproducing kernel Hilbert space (RKHS), CEI achieves the convergence rates of O left(t^-frac12log^fracd+12(t) right)  and  Oleft(t^frac-nu2nu+d log^fracnu2nu+d(t)right) for the commonly used squared exponential and Mat'ern kernels (nu>frac12), respectively. Second, we show that when f is assumed to be sampled from Gaussian processes (GPs), CEI achieves similar convergence rates with a high probability. Numerical experiments are performed to validate the theoretical analysis.