Convergence Rates of Constrained Expected Improvement
Authors: Haowei Wang
Jingyi Wang
Zhongxiang Dai
Nai-Yuan Chiang
Szu Hui Ng
Cosmin G. Petra
Venue: NeurIPS 2025 spotlight ()
Keywords: Bayesian optimization
constrained Bayesian optimization
constrained expected improvement
simple regret
convergence analysis
Primary area: theory
TL;DR: We present the first theoretical convergence rates for constrained expected improvement, one of the most popular constrained Bayesian optimization methods.

Abstract: 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 $\mathcal{O} \left(t^{-\frac{1}{2}}\log^{\frac{d+1}{2}}(t) \right) \ \text{and }\ \mathcal{O}\left(t^{\frac{-\nu}{2\nu+d}} \log^{\frac{\nu}{2\nu+d}}(t)\right)$ for the commonly used squared exponential and Matérn kernels, 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.

Convergence Rates of Constrained Expected Improvement
Haowei Wang
Jingyi Wang
National University of Singapore Singapore haowei_wangee mus. .us.dussuu edu
Lawrence Livermore National Laboratory Livermore, CA 94550 wang125@11n1. gov
Nai-Yuan Chiang
Zhongxiang Dai The Chinese University of Hong Kong, Shenzhen
Lawrence Livermore National Laboratory Livermore, CA 94550 chiang7011nl.gor
China
daizhongxzangg@oukk. edu. cn
Szu Hui Ng National University of Singapore Singapore isensh@nus. edu.sg
Cosmin G. Petra
Lawrence Livermore National Laboratory Livermore, CA 94550 petra10linl. gov
Abstract
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 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, 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 reproducing kernel Hilbert space (RKHS), CEI achieves
(t) and O (u log zoita (t) for the commonly used squared exponential and Matérn kernels (v 1)) respectively. Second, we show that when assumed be sampled from Gaussian processes (GPs), CEI achieves similar convergence rates with high probability. Numerical experiments are performed to validate the theoretical analysis.
the convergence rates of O t log 2+1
Introduction
Bayesian optimization (BO) is an efficient method for optimizing expensive black-box functions without derivatives. It leverages probabilistic surrogate models, most commonly Gaussian processes (GPs), to balance exploration and exploitation the search for optimal solutions [Frazier BO has found widespread success in diverse fields such structural design [Mathern al. 202
2018
machine learning hyperparameter tuning [Wu et al. 2019 robotics (Calandra et al.) 2016 fusion
design [Wang et al. 2024 etc.
While traditional BO typically applied to unconstrained settings, many real-world problems involve black-box constraints that must be satisfied. This has motivated growing interest in constrained
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Bayesian optimization (CBO), where surrogate models are also constructed for constraint func- tions [Bernardo et al., 2011] that are complex and expensive to evaluate, making CBO especially valuable in applications like engineering design [Song et al. 2024 and automated machine learning [Ungredda and Branke, 2024). One of the very key difference between unconstrained and constrained optimization is that the feasible region for constrained optimization problem consists of the search space where all constraints must be satisfied. A general form of the constrained BO problem is:
minimize #EC
f(x), subject to c(x)= S 0,
where f: IR + R is the objective function, and e - R" are the constraint functions. Both are defined on compact input space C C R The objective and the constraint functions are both expensive black-box functions, that can only be evaluated through expensive physical or computer experiments. Throughout this paper, we consider the noise-free setting for both the objective and the constraints, ie., the function evaluations are deterministic and the true function values can be observed (see Remark [3.4 for discussion on the noisy case). In addition, a single constraint is considered, i.e., m = I, for simplicity of presentation. We note that our analysis can be easily extended to multiple constraints (see Remark 3.13 for details).
Broadly, CBO methods can be categorized into implicit and explicit approaches [Amini et al., 2025]. Implicit methods modify standard acquisition functions to incorporate constraints via merit functions or feasibility weights. Explicit methods estimate the feasible region directly and restrict search
to this region. Among these, the constrained expected improvement (CEI) (Schonlau et al.) T 1998
Gelbart et al. 2014 Gardner et al., 2014) stands out as one of the most basic and widely adopted methods. CEI is a natural extension of the well-known expected improvement (EI) function (Jones) al. 1998). where the acquisition function is computed the product of El and the probability of feasibility. Thanks to this simple and interpretable formulation, CEI has been successfully applied across domains, and it remains one of the default choices in many constrained BO software packages Balandat et al. 2020].
Despite its empirical popularity, the theoretical understanding of CEI lags behind. In contrast, unconstrained El has been more extensively studied. Under frequentist assumption where the objective/ f lies in reproducing kemnel Hilbert space [Bll] established the convergence rate of EI by deriving the simple regret upper bound. Other works explored the density of sampled sequences VVazquez and Bect 2010) or connections between EI and optimal computing budget allocation [Ryzhov] (016). However, convergence rates (i.e., simple regret upper bound) for CEI have not been rigorously established-neilher under frequentist nor under Bayesian settings. Here, Bayesian setting means the objective f is a function sampled from GP.
Introducing constraints into EI significantly complicates the theoretical analysis. Unlike in the unconstrained case, the algorithm may need to explore infeasible regions to gain information on the constraint boundary. Furthermore, CEI's acquisition function is inherently more complex and non- convex, posing challenges for analysis. On the other hand, the presence of constraints in CEI leads to changes in the sampling procedure. As a result, the key challenge to study the convergence rate of CEI lies in analyzing the exploration (searching for feasible regions) and exploitation (optimizing within feasible areas) since the feasibility threshold is unknown in the input space.
In this paper, we provide the first theoretical convergence rates for CEI, focusing on simple regret upper bounds under both the frequentist and Bayesian settings. Our convergence rates provide practitioners theoretical assurance for the practical deployment of CEI. We explain the technical challenges and how we address them in Section 3 Our contributions are summarized as follows:
Under the frequentist setting, we derive simple regret upper bounds of O (t- log (t)
for the squared exponential (SE) kernel and (bbvfa log I (1) for Matérn kernels
(v > }) These bounds are improved upon the direct extension of Bull 2011] to the
constrained case for SE kernel with d 2 3 and Matérn kernels with d 2 3, 2 2-2 (see
Theorem 3.7).
Under the Bayesian setting for the objective, we achieve similar simple regret upper bounds with high probabilities. These bounds are established based on the newly derived bounds (see Theorem 3. on the difference between the improvement function and its corresponding
El in the Bayesian setting.
2

---

This paper is organized as follows. In Section 2 we describe the basics and preliminaries of BO, including the CEI algorithm. In Section the simple regret upper bounds of CEI are established in both settings. Numerical experiments to validate the theoretical results are given in Section Conclusions are made in Section 5
All proof details are presented in the appendix.
2
Background
CBO mainly consists of two components: the GP surrogates for the black-box objective function and constraint function c, and the constrained acquisition function as the sequential sampling rule guiding for the global optimum.
2.1 Gaussian process models for and
Without losing generality, let the mean function for the objective GP model prior be and the covariance function (kernel) be ky (zc, a²) IR" x IR + R. At sample point æt E C, we denote the objective function value fxx) and the observed constraint function value is c(x)). Given t sample points, denote æ1:t [1.....,2y) and fIa [f(x)...... f(z)),,,,,,,,,,, Moreover, denote the t x & covariance matrix K ()) at)i ky (22, #1),.... ky (Z), æt)]. The posterior distribution of (() ai fia ~ NN (at). (of (z)))) can then be inferred using Bayes' rule as follows
of (a) (kg (z)) (K!) ( f1:t:
(z)) = k, x) (xx)) k/)
where k:/ (x) (z) (x x.......................... (x), a² Similarly, denote the kernel for cas be R2" R IR and the covariance matrix K; [k. a. ..... (211, æz); ... hi (xt, 11),-..................))) (x ax)) The posterior distribution for is
(x(x) (x((2))) (K;) c1d,
(of) (x) lx, (z(()) (k)))))(()))..))))))))))()))>>))
where kz(a)) [ ....... ... ka x))², and (x)) and (x)) are the posterior mean and variance for respectively. Here we use the subscripts f. e and superscripts f to distinguish between GPs for if and c. Choices of the kernels k and &S include the SE and Matérn kernels, which follows.
among the most popular kernels for GP and BO. Their definitions
V2er
V2ur
ks x²) = exp
kMatérn (2e, x') T(v)2u-I
B.
212
1
where/ is the length hyper- eyper-parametent r= | x' 221122- the Matérn kernel, and B, is the modified Bessel function of the second kind.
222 v >> is the smoothness parameter of
2.2 Constrained Expected Improvement
Acquisition functions critical to the performances of BO algorithms. In the unconstrained setting, one of the most widely adopted acquisition functions is El [Jonss et al.) 1998). Given t samples, the improvement function of used in El is defined
of (z) max(fi f(x).0},
where ft
min fxx The expectation of conditioned existing samples is El, which has :
closed form Brochu et al. [2010]:
EI! (x) (f+t - (x)()) of =
where of (a:) = f (4) The functions á and & are the probability density function (PDF) and the cumulative distribution function (CDF) of the standard normal distribution, respectively. The t + 1th sample using EI is chosen by
of (x)
T141 argmaxEE EI! (x))
(5)
#EC
3

---

Taking into account the constraint, the constrained improvement function in CEI Gardner et al. 2014 is defined as
1 = (x))) m f(z).0),
where A E {0, 1) is the feasibility indicator function where (a:) if c(x)) S and Af(a: otherwise. The incumbent fi in CEI is augmented to be the best feasible observation. CEI assumes that f and c are conditionally independent (Gardner et al. 2014). Taking the conditional expectation of (6). the CEI function is
(- mi(x)) of(x))
- P( =
EI (æ),
where P.(-) is the probability of feasibility (POF) function for c(æ) s 0. CEI chooses the next sample via
argmaxP((z)EI
L++1
#EC
The CEI algorithm is given in Algorithm
Algorithm 1 CEI algorithm
1: Choose ky k-(-,), ke(-,-), and To initial samples 2;, i = =..:.,,... l,..., Observe fiT, and CI.T.
2: Train the GP surrogate models for f and respectively conditioned on the initial observations.
3: for t = To + 1, Tu + 2. do
4: Find 24+1 based (8) (CEI).
5: Observe f 1 and c(x++1).
6: Update the GP models with the addition of #1+1, ((x+11), and c(2x+11)
7: if Evaluation budget exhausted then
8: Exit
CEI can be extended multiple constraints assuming conditional independence among the con- straints [Gardner et al., 2014). Our derived convergence rates can also be readily extended to multiple constraints, explain in Remark 3.13
3 Convergence rates of CEI
We present our main results of convergence rates for CEI by establishing the simple regret upper bounds. Denote the optimal solution to the constrained optimization problem ( as x². In the unconstrained case, the simple regret of El is defined as ft+ - f(x") ) [Bull 2011]. In the constrained case, we use the current best feasible observation and compare to the optimal solution f((=") since one could have infeasible sample point with smaller objective than f(x).. Given that ft" already defined as the best feasible observation till iteration t in CEI, we continue to use
99) as the simple regret for CEI. In our analysis, make the same underlying assumption as CEI that ft* exists. In the following, we first establish the convergence rate under the frequentist assumptions in Section 3.1 including improved version of the rate under frequentist assumptions in Section 3.1.1 1.1.
Tt = ft f(x")
Then, we establish the convergence rate under Bayesian objective assumptions Section 3.2
3.1 Simple regret upper bound under frequentist assumptions
In this section, present the simple regret upper bound for CEI under the frequentist setting. More- over, by adopting the information theory-based bounds and techniques the noise-free cumulative regret bound of upper confidence bound (UCB) [Lyu et al. 2019], bound some cases compared to Bull 2011). The definition of RKHS is given below.
derive improved upper
Definition 3.1. Let & positive definite kernel measure supported on X. A Hilbert space H₃ of functions X' with an inner product (:.)) H, is
x
with respect to finite Borel

---

called a RKHS with kernel k if x) E H2 for all a E X, and (f), = f(x) for all X, Hg. The induced RKHS norm Il Vif. measures the smoothness of f with respect to k.
In this section, we assume the following assumptions on the functions f a'and c.
Assumption 3.2. The functions f and lie in the RKHS, denoted as (C)(C) and (C) associated with their respective bounded kernel ky and kes with the norm Il-llag and II- The kernels satisfy ky(æ, æ') < 1, (a, x²) S 1, (a x) 1, and ki, x) - 1. for Va. x' E C. The RKHS norms are bounded above by constants By and Be, respectively, i.., IIfll S By, //c.l|cllg I Be. Moreover, the bound constraints set C' is compact.
Technical Challenges under Frequentist Assumptions. The main challenge in establishing a simple regret upper bound for CEI is how to incorporate the constraint c(a:) S 0 and the probability of feasibility function (x))) into the analysis. Existing regret bounds analysis on CBO methods often focus on UCB-type methods [Lu and Paulson 2022 Zhou and Ji 2022], for which the acquisition
functions do not have the multiplicative structure between the objective and the constraint.
Under Assumption 3.2, both f andd e are bounded on C' by their RKHS norm bounds, as stated in Lemma B.I The simple regret upper bound is given in the following theorem.
Theorem 3.3. Under Assumption 3.2
the CEI algorithm leads the simple regret upper bound of
Br
4 Bi {
+ +0..4 ( (,)o(( (outt)
rt
Φ (-))
(10)
for some la E 1/ 1, 1, and CrB -(-Br))
=(B,)
Sketch of Proof for Theorem 3.3 We start by noticing that the sum of the difference between consecutive best feasible observations bounded, i.e., Σi= Jit - Stt S 2B,. Then, we adopt 2B,, k where k S t S 2k and 2k S t < 2(k + 1). Next, using the monotonicity of ft+ rr is bounded by rt. Using the inequality between If and EIÇ in Lemma B.4, we can bound rı, by the EI on objective: EI, (x*). Then, transform EI,, (x*) into Eli, (1) by inserting the term Pt, (x*), taking advantage of the multiplicative structure of CEI. The upper bound of Tr then consists of the term Pr.( E1, (1t++1). From the confidence interval [f()) - nz (z)) (Lemma B.2 and the fact that fit 1it++ 2 we can bound ET/ (1). The constraint term Pt, (=*) remains to be bounded. We use the confidence interval on Ic(x) - f(((z)) in Lemma at x= and the fact that x: is a feasible solution to obtain a lower bound for Pt, (x=)) ). This concludes the proof.
technique in Bull [2011] to find fg such that fit fit+1
Remark 3.4 (Constraint in the simple regret upper bound). The terms derived from the constraint function in (TO) is .(-B.j which emerges from the probability of feasibility function and (ī(x)) and (xx) of the GP model of c(xr). Thanks the multiplicative structure between the objective and constraint in 1f (6) and EIç (7). the simple regret upper bound maintains a similar form.
is clear from 10) that the convergence of r, relies on the posterior standard deviation of (#x+ 1)- Since 44 increases with f, as of (a++1) + 0, so does of (1), In the noise-fres free setting, the posterior variance can be bounded via the maximum distance between sample points and given point. To obtain the rate of simple regret bound, we use Assumptions (1)-(4) in Bull [001]] and focus on squared exponential (SE) and Matérn kernels. Recall that the smoothness parameter of the Matérn kernel is v > O. Both the SE and Matérn kernels satisfy Assumptions (1)-(4) in Bull (0011) with SE kernel obtained - co. Further, define
a, V
(11)
10 v 0.
where a = if E N. and otherwise. Then, for SE and Matérn kernels, of (2)++1 can be bounded with the following lemma.
5

---

Lemma 3.5 (Bull 2011)) ) For the SE kernel, there exists constant C' > 0 so that given Vt E N.
of (xi+1) 2 C'k
(12)
holds for at most k times, for vk E N, k and 1,..., 1. For Matérn kernels,
of (x1+11) 2 C*k minta.1) log"
(13)
holds most k times.
In the constrained setting, are able obtain the same rates as those in the unconstrained case Bull 2011] using Lemma 3.5
Corollary 3.6. Under Assumption 3.2 the CEI algorithm leads to the convergence rates of
O ( and O (t
min( log" log"(t)
(14)
for SE and Matérn kernels, respectively, where 1) is from 11
Corollary s.6ls that the CEI algorithm guaranteed to find the best feasible point asymptotically with the rates elaborated in (14.. Also, point out that the choice of kernels and their parameters affect the convergence rates. Since the SE kernel can be viewed as a Matérn kernel with / - oc. its convergence rate is better than Matérn kernels with < 1. However, due the limitations of the kernel analysis Bull 2011 (see Remark (.8) for v 2 1, SE and Matérn kernels have similar convergence rates in Corollary 3.6 As we present in the following section, improved rates for both kernels can be obtained in some cases.
3.1.1 Improved simple regret upper bound under frequentist assumptions
Next, we apply maximum information gain and the corresponding information theory to obtain improved simple regret upper bounds.
Theorem 3.7. Under Assumption
3.2 the CEI algorithm leads to the improved convergence rates of
o (1 log s+1 (1) and O (I logar4a zuta (1) (1)),
(15)
for SE and Matérn kernels, respectively.
The proof follows similar steps to that of Theorem 3.3 but further bounds of (1) using 7/- To do so, we first recognize that the bound using 7 (Lemma A.3 is established in the noisy case where the posterior standard deviation has different form as in (18). Using Lemma A.4] we can establish that the noise-free posterior standard deviation
Sketch of Proof for Theorem 3.7
also satisfies Ei= o (#141) S C,thl. Then, from Lemma A.5 we can find a small enough of (m.+1). Specifically, choose k = [t/3]. where [x)] denotes the largest integer smaller than x. Thus, 2B
we have 3/ < 3(k + 1). Then, there exists k S tş < 3k such that fit fitt s = and of, (1)
Vi The rest of the proof follows from that of Theorem 3.7
Remark 3.8 (Improved rate of convergence). As mentioned above, the rates in Corollary 3.6 are the same as the known convergence rates for El in Bull (20IT) Meanwhile, the rates Theorem 3.7 is an improvement over those of Bull [201]] for SE kernel with d 2 3 and Matérn kernels with 2 3, d- To achieve this, we applied techniques from regret bound analysis on noise-free
UCB Lyu et al. 2019) that allows us use maximum information gain bound the sum of of (2x,4)).
Then, we use our techniques in the proof of Theorem 3.3 to bound an individual of, (It, +11 ). In Bull
20 the of, (1)+++) is bounded by the Taylor expansion of the kernel functions. Therefore, the rates of decrease are limited to quadratic terms for both SE and Matérn kernels, since their Taylor expansions around 0 for ||= 22112 are quadratic best. On the other hand, maximum information
gain can lead to tight bounds on 7/. that take advantages of the spectral properties of the kernels [Vakili et al. 2021 Iwazaki 20255 Hence, using 7/. to bound of (#t,+1) 1) can produce a faster rate. As the open question raised Vakili [2022] gets answered, further improvement of the convergence rates
possible, e.g., using techniques from Iwazaki 20255

---

3.2 Simple regret upper bound under Bayesian objective assumption
In this section, we present the simple regret upper bound for CEI under the Bayesian objective assumptions. We again use the maximum information gain to derive the simple regret upper bound. Assumption 3.9. The bound constraint set C' C [0, r| is compact and convex. The objective function is sampled from GP(O, ky (ar, æ²)). Further, the objective function / is assumed to be Lipschitz continuous (of 1-norm) with Lipschitz constant L5 with probability > - daye////1 for some constants as > 0 and by O. The kernels satisfy k *f(2,,") x') S 1 and (x, x) = 1. The constraint function e remains in the RKHS of ke. similarly to the frequentist setting.
In the remaining of this section we will work under Assumption 3.9
Technical Challenges under Bayesian Assumptions. In addition to the challenges in the fre- quentist setting, the bounds on El in the Bayesian setting are not available in current literature, to the best of our knowledge. Starting from the confidence interval on [[(x) - uu (a=) we derive the bounds on ! (ax) (x)) with high probability, an important step towards the bound on rt- Noticeably, under the Bayesian setting, the bounds are satisfied with a given probability, e.g. 1 8, where ó E (0, 1).
The simple regret upper bound is given in the following theorem.
Theorem 3.10. Let = 2 log(6ca/0)) and Bg = 2 log(3 (6, where ca
1+2m and Te = x²p² 2x
6.
Under Assumption 3.9 the CEI algorithm leads to the simple regret upper bound
1
4M,
23
Vattd + (0.4 (3 (Best1)
Tt (3)
(16)
4 ((-Ba)
1-2
1-2
1(3113) 7(-Buray and constant M with probability 2 1-
for some tu E 1/4 1, cr (+
The constant My is from Lemma
The convergence rate is given in the next theorem.
Theorem 3.11. Let 2 log(6c,/ and Br log(3n,/8), where ca
1+2x
and ne
x²t²
2
6.
Under Assumption 3.9 the CEI algorithm leads to the convergence rates of
o ( log
d+2 (t) and O (t I log
2440.55 2044
(t)
(17)
for SE and Matérn kernels, respectively, with probability 2 1- 1 8.
Sketch of Proof for Theorem 3.10 Recall that f and are assumed conditionally independent in CEI. We start from the bound on the confidence interval for f: [f(z) - ou (=)] S 3//20! (x),, with probability 2 - 8, where / = 2 log(1/8), as in Lemma C.2 The confidence interval of remains the same as in the frequentist setting. These are well-known results (Srinivas et al., 2009]. Then, we derive the subsequent bounds | (z) - E1 (x) /Bo! (æ)) where = max 1.44, 2 (o)g(c//)).
and Co 22 with probability 2 1 (Lemma C.5 Then, we prove the relationship in Lemma C.6
that (((x)) IVFB)
EI (a)) with probability 2 2 8. We can now follow the general analysis
framework Section 3.J and Theorem 3.3 to obtain the simple regret upper bound under Bayesian objective assumptions, while choosing l with more defined criterion.
Remark 3.12 (Comparison to the frequentist setting). Comparing Theorem 3.7 to Theorem 3.11 the convergence rates in the frequentist and Bayesian settings the same except for a log'/2 (t) term.
This is partially because simple regret focuses on the best feasible solution fif and thus many of the parameters in Theorem 3.3 and 3.10 do not depend on t.
Remark 3.13 (Multiple constraints). As mentioned in Section I our results can be readily applied to CEI with multiple constraints for both frequentist and Bayesian settings. Consider m constraints e (x) < 0, = 1.... m. Assuming conditional independence of the constraints, the CEI function E (x) = mmm (x) (x) = mm
FT! (æz), where Pt is the probability of feasibility function of constraint (a()) S O. and 1e (a:) and of (æx) are the posterior mean and standard deviation for c; respectively. By making the assumption that each constraint function lies
7

---

in its corresponding RKHS of the kernel ke we have (cx(z) (x)] S of, where Bc, is the upper bound of RKHS norm associated with kemel kc, and function c₁. We can then apply the analysis framework in this paper to obtain an upper bound similar to that of Theorem 3.3 where the term x=) is replaced with T ) We note that in the Bayesian objective setting, to
ensure probability 1 - 6, the parameter (3 needs to increase with the number of constraints as well, egg. 3 = log((n) + 5)c./8).
Remark 3.14 (Extension to the noisy setting). Extending our analysis to the noisy setting is non-trivial, and we discuss the associated challenges for noisy objective and constraint functions separately. A noisy constraint function introduces additional complications in defining feasibility. If only noisy observations of the constraint values are available, the notion of feasible sample and the definition of Jif becomes ambiguous. As a result, major modifications to the CEI algorithm are required to appropriately handle the uncertainty introduced by noise.
For the noisy objective function, CEI can be adapted similarly to the noisy EI formulation by treating the best feasible noisy observation as the incumbent. However, to the best of our knowledge, a theoretical guarantee on the simple regret bound for the noisy unconstrained setting remains unavailable. Recent work by Wang al. [2025] provides framework for deriving noisy simple regret bounds based on the best observed value, r. = y," f which can be extended to CEI. Specifically, by defining rž as the simple regret for CEI with y," denoting the best feasible noisy observation, similar proof strategy in Theorem 3.10 yields analogous upper bound. In the Bayesian setting with i.i.d. Gaussian noise on the objective and noise-free constraint observations, the convergence rate of the upper bound on r& can be obtained. However, we note that given the noise, r is possibly negative.
Remark 3.15 (Infeasible initial sample). It is well known that CEI requires initial feasible sam- ple Gardner et al. 2014). That is, ft exists from the initial samples so that the CEI calculation can proceed. Methods proposed to address this issue typically employ separate strategies when no feasible samples are available and revert to the standard CEI formulation once feasibility is established (Lin) et al., 2024 Letham et al. 2019). In addition, introducing tolerance parameter in the constraint can further mitigate this problem by allowing near-feasible points when the degree of violation is small. Remark 3.16 (Tolerance in constraints). In gradient-based optimization methods, a tolerance for constraint violation is often used to improve the performance and flexibility of algorithms) SeerrittnssShhhhhhaaaa Wächter and Biegler [2006], Nocedal and Wright [2006]. Motivated by this, we introduce a tolerance parameter A 0, where a point æ is considered feasible if c(x) S À and infeasible otherwise. The corresponding CEI with tolerance is defined as EI A) = (2, (x) = Φ (x) the standard CEI formulation is recovered when X = O.
E1[ (z)). Clearly,
(x))
The simple regret bound is affected by À and should lead to क;- in place of 0T-B.. In fact,
can replace T(A-B.) with 1/4 1 (+)) B.). which is time-varying. One can follow the proof of Theorem 3.3 to obtain this term, which emerges from the confidence interval of c at tx. x and c(x*) <
As the sample iteration increases, the inclusion of of (x*) important in balancing -B, that can lead to a large simple regret upper bound. We explain the intuition below. As ( - xc, la + oo and & + co. We know of (x++1) simple regret upper bound of CEI with X > 0 converges. Thus, D, approaches at least one of the optimal solutions. Suppose without losing generality, x; - x². Then, by definition of, (x*) - O.
O, and hence of, (#t++1)
0 and re - 0. That is, the
Consequently, we should have
for À 0. Then, we have +b of (-.7 1. Therefore,
A
Fig (ar)
[
1/0( B.) + and B. does not affect the simple regret upper bound asymptotically. We note that the convergence rate of CEI with tolerance remains similar since is dominated by the maximum information gain of f.
4 Numerical experiments
Although this paper is primarily theoretical, we conduct numerical experiments to support the theoretical results. We apply the CEI algorithm to eight synthetic problems that are randomly generated from RKHS of kernels and GP priors, and five benchmark problems commonly used in the
8

---

CBO literature. These numerical experiments are not intended to demonstrate superior performance over the state-of-the-ar CBO algorithms. Instead, they serve as empirical evidence for the theoretical analysis presented in this work. All experiments are conducted on M1 (16GB memory
4.1 Synthetic problems
In this section, we study objective and constraint functions drawn from reproducing kernel Hilbert spaces (RKHSs) as well as from Gaussian process priors with Matérn (v 2.5) and squared exponential (SE) kernels, across imput dimensions E 2, 4. The domain the hypercube [0, 1ja.
For RKHS cases (the frequentist setting), the functions are generated with a similar approach to Chowdhury and Gopalan [2117]. Specifically, both objective (xx and constraint functions c(x) generated by sampling from the RKHS associated with a chosen kernel (Matérn/SE kernels with a length scale 0.2). Each function is constructed as a weighted sum of kernel evaluations at 100 randomly selected basis points, with weights drawn from a standard normal distribution. Formally, 2i=1 a;k(2æ, X;) where k is the kernel, X; are basis points, and a; are random coefficients; c(x)) is generated similarly. For the GP cases (the Bayesian setting),
the function takes the form ((x) >
the functions are generated with an approach similar to Srinivas et al.] [2009). Specifically, we uniformly choose 1000 points in the design space and sample randomly from multivariate Gaussian distribution defined by the GP prior with the chosen kernel.
For each synthetic problem, we conducted 100 independent trials. The number of initial design is set to 10d, and 50 optimization iterations were performed for all cases. We plotted the log-log curve of simple regret against the number of iterations in Figure [ In all cases, consistently observed sublinear convergence patterns, which align well with our theoretical guarantees.
(a) RKHS, Matérn, d (b) RKHS, Matérn, =
RKHS, SE, d
(d) RKHS, SE,
STACE
0.:00
(c) GP, Matérn, d d= 2
(f) GP, Matérn, d = 4
(g) GP, SE, 2
(h) GP, SE, d = 4
Figure I: The log-log plots for simple regret vs optimization iterations of CEI for the synthetic problems.
4.2 Test problems
Next, we evaluate simple regret of CEI on five commonly used test problems in the literature of CBO. Specifically, Problem 1 tests performance in a small feasible region, which was previously studied in Gardner et al. [2014). Ariafar al. [2019] Problem includes multiple constraints and local minimums, which has been used in Gramacy et al. [2016), (erodj),HHmnnee-LLLnnn Hermández-Lobato et al. [2015). Problem
3 is a four-dimensional problem, previously studied in Picheny et al. [2016), Ariafar et al. 2019
'Codes are available in https///ithub.com//aawwe htgp:/hhwbooootoooooeea//onnnnnn Sww.aaveerrnneeRRee-ee-eeee Rates-of -owo--ooooonn---aaaaeea Expected- Improvement.

---

Problem is the six-dimensional Hartmann problem, previously tested in Letham et al. [2019). Problem is the Rosenbrock function, where the global minimum lies in narrow region. The mathematical formulations of the five functions are presented in Appendix D For two-dimensional problems, we also include the contour plots of the objective and constraint functions Appendix [ The SE kernel is used for the GP modeling (similar performance is observed for the Matérn kernel) and the papee--prameters are estimated by standard maximum likelihood method.
For each test problem, we conducted 100 independent trials with different random initial designs. When CEI fails to identify feasible sample, we adopt the same heuristic strategy as in Letham et al. (2019). The numerical results are summarized in Figure 2 The solid line represents the median of the simple regret, and the dotted lines represent the 25th percentile and 75th percentile of the simple regret, respectively. From the figures, we observe that CEI consistently reduces simple regret, aligning with the asymptotic convergence theories established in this paper. Accross all problems, the simple regret converges to 0 quickly. The 25th percentile and 75th percentile results demonstrate the good statistical properties of CEI.
75th
75t
2202
opoimuation Baration
astimaadonn Benatore ora
(a) Problem a small feasible region problem
(b) Problem a multiple-constraimts problem
10500g B000le
75th
35m
25:
05
00
opombaation Banations
021 cntimtationn Breatone
(c) Problem a four-dimensional problem
(d) Problem Hartmann6 function
500g egger
medion
(e) Problem 5: Rosenbrock function (in log scale due
to large range of objective values.)
Figure 2: Simple regret of CEI for five test problems.
5 Conclusions
In this paper, we studied the simple regret upper bounds of the CEI algorithm, one of the most widely adopted CBO methods. Under both frequentist setting and Bayesian objective assumptions, establish for the first time the convergence rates for CEL. Our results provide theoretical support and validation for the empirical success of CEI.
10

---

References
[1] S. Amini, I. Vannieuwenhuyse, and A.
Constrained bayesian optimization:
A review. IEEE Access, 13:1581-1593, 2025. doi: 10. 10.110/AACCESSS.244552222
[2] S. Ariafar, J. Coll-Font, D. Brooks, and J. Dy. ADMMBO: Bayesian optimization with unknown constraints using ADMM. Journal of Machine Learning Research, 20(123):1-26, 2019.
[3] M. Balandat, B. Karrer, D. R. Jiang, S. Daulton, B. Letham, A. G. Wilson, and E. Bakshy. BoTorch: A Framework for Efficient Monte-Cario Bayesian Optimization. In Advances in Neu- ral Information Processing Systems 33, 2020. URL http:://txxiiiii www. abs//91b//9901...// 06403
[4] J. Bernardo, M. J. Bayarri, J. O. Berger, A. P. Dawid, D. Heckerman, A. F. Smith, and M. West. Optimization under unknown constraints. Bayesian Statistics, 9:229, October 2011.
[5] E. Brochu, V. M. Cora, and N. De Freitas. A tutorial on Bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. arXiv preprint arXiv: 2.12.,599, December 2010.
[6] A. Bull. Convergence rates of efficient global optimization algorithms. Journal of Machine Learning Research, 12(10), 2011.
[7] R. Calandra, A. Seyfarth, J. Peters, and M. P. Deisenroth. Bayesian optimization for learning gaits under uncertainty. Annals of Mathematics and Artificial Intelligence, 76:5-23, February 2016.
[8] S. R. Chowdhury and A. Gopalan. On kernelized multi-armed bandits. International Conference Machine Learning, pages 844-855 PMLR, 2017.
[9] I. Frazier. Bayesian optimization. In Recent advances in optimization and modeling of contemporary problems, pages 255-278 October 2018.
[10] R. Gardner,
Kusner, 7. Xu, K. Q. Weinberger, and P. Cunningham. Bayesian optimization with inequality constraints. In Proceedings of the 31st International Conference on International Conference on Machine Learning Volume 32, ICML 14, pages I1-957-I1-945. JMLR.org, 2014.
[11] M. Gelbart, Snoek, and R. P. Adams. Bayesian optimization with unknown constraints. arXiv preprint arXiv:1403.566 2014.
[12] R. B. Gramacy, G. A. Gray, S. L.. Digabel, H. K. lee, R. Ranjan, Wells, and S. M. Wild. Modeling an augmented lagrangian for blackbox constrained optimization. technometrics, 58 (1):1-11, 2016.
[13] J. M. Hernández-Lobato, M. Gelbart, M. Hoffman, R. Adams, and Z. Ghahramani. Predictive entropy search for Bayesian optimization with unknown constraints, In International conference on machine learning, pages 1707. PMLR, 2015.
[14] S. Iwazaki. Gaussian process upper confidence bound achieves nearly-optimal regret in noise- free gaussian process bandits. arXiv preprint arXiv:2502. 2025.
[15] Shogo Iwazaki. Improved regret bounds for gaussian process upper confidence bound in bayesian optimization. arXiv preprint arXiv:2506.01399; 2025.
[16] D. R. Jones, M. Schonlau, and W. J. Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13:455-492, 1998.
[17] B. Letham, B. Karrer, G. Ottoni, and E. Bakshy. Constrained Bayesian optimization with noisy experiments. Bayesian Anal., 14(2), 2019.
[18] Q Lin, J. Hu, Q. Zhou, L. Shu, and A. Zhang. A multi-fidelity bayesian optimization approach for constrained multi-objective optimization problems. Journal of Mechanical Design, 146(7): 07 1702, 2024.
11

---

[19] C. Lu and J. A Paulson. No-regret bayesian optimization with unknown equality and inequality constraints using exact penalty functions. IFAC-PapersOnLinee 55(7):895-902, 2022.
[20] Y. Lyu, Y. Yuan, and W. Tsang. Efficient batch black-box optimization with deterministic regret bounds. arXiv preprint arXiv:1905. 10041, 2019.
[21] A. Mathern, O. S. Steinholtz, A. Sjöberg, et al. Multi-objeetive constrained Bayesian optimiza- tion for structural design. Structural and Multidisciplinary Optimization, 63:689-701 February 2021.
[22] Nocedal and Wright, Numerical Optimization. Springer- Verlag, New York, 2006.
[23] V. Picheny, B. Gramacy, Wild, and Le Digabel. Bayesian optimization under mixed constraints with a vaaialvrriable augmented lagrangian. Advances in neural information processing systems, 29, 2016.
[24] I. Ryzhov. On the convergence rates of expected improvement methods. Operations Research, 1465:1115--158,, 2016.
[25] M. Schonlau, W. J. Welch, and D. R. Jones. Global versus local search in constrained optimiza- tion of computer models. Lecture notes-monograph series, pages 11-25, 1998.
[26] J. Song, Y. Cui, P. Wei, M. A. Valdebenito, and W. Zhang. Constrained bayesian optimization algorithms for estimating design points in structural reliability analysis. Reliability Engineering System Safety, 241:109613, 2024.
[27] N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3999 2009.
[28] Ungredda and Branke. Bayesian optimisation for constrained problems. ACM Trans. Model. Comput. Simul., 34(2), April 2024.
[29] S. Vakili. Open problem: Regret bounds for noise-free kernel-based bandits. In Conference Learning Theory, pages 5624-5629. PMLR, 2022.
[30] S. Vakili, K. Khezeli, and V. Picheny. On information gain and regret bounds in gaussian process bandits. In International Conference on Artificial Intelligence and Statistics, pages 82-90. PMLR, 2021.
[31] E. Vazquez and J. Bect. Convergence properties of the expected improvement algorithm with fixed mean and covariance functions. Journal of Statistical Planning and inference, 140(11): 5088-3095, 2010.
[32] J. Wang, N. Chiang, A. Gillette, and J. L. Peterson. A multifidelity bayesian optimization method for inertial confinement fusion design. Physics of Plasmas, 31(3), 2024.
[33] J. Wang, H. Wang, C. G. Petra, and N. Y. Chiang. On the convergence of noisy bayesian optimization with expected improvement. arXiv preprint arXiv:2501.09262. 2025.
[34] Wu, X. Chen, H. Zhang, Xiong, H. Lei, and Deng. Hyperparameter optimization for machine learning models based on bayesian optimization. Journal of Electronic Science and Technology, 17(1):26 40, 2019.
[35] A. Wächter and L. Biegler. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program., 106(1):25-27, 2006.
[36] X. Zhou and B. Ji. On kernelized multi-armed bandits with constraints. Advances in neural information processing systems, 35:14-26, 2022.
12

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The assumptions for our theorectical analysis are clearly stated.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification: NA
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide all the details and supplemental codes.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipp/.cc/pullc//uuuii wwwticccguie//eeieeeeeeii CoodeSubeiiie ssi ssionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
15

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp:://neuriipee http:///.ccc.uccccttttccttttteea
Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is theoretical paper focused existing algorithms.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
16

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not have such data.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee whworee.wthhhe....c.. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
17

---

Answer: [Yes]
Justification: NA
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: NA
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
18

---

Justification: NA
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy htteas////eerrpppoccc///o/rreerp for what should or should not be described.
19

---

A Background information and preliminary results
A.1 Information gain
To obtain ttateoo--he-an simple regret upper bound, we utilize the information theory results that are well-established in previous literature [27 g 30 Using I as the example, let A C denote set of sampling points. Assume that the observations are noisy at sample points with ул = f(xA) + ca at A, where CA ~ (0, o²) denotes the independent and identically distributed Gaussian noises. The maximum information gain is defined as follows.
Definition A.1. Given æ and YAa the mutual information between and Yı is T(yA; fa) (yy)) fa), where denotes the entropy. The maximum information gain 7 after T samples is , mAXACCAA/== 1 (yA fA).
The rate of increase for of' depends on the property of the kernel. For common kernels such as the SE kernel and the Matérn kernel, 7o has been studied in literature and the state-of-the-art rates of of are summarized in Lemma A.2 30 [5].
Lemma A.2. For GP with samples, the SE kernel has 7t with smoothness parameter v > 0.5 has "it = Ot (log a (t))).
(O)), and the Matérn kernel
2v
The maximum information gain % for the constraint function can be defined similarly.
While 7VC is defined in the noisy case, we can readily apply it to the noise-free case and bound of (II+1) using techniques similar that in [20]. To do so, note that given the Gaussian observation noise 4 ~ NN0, o²) in the GP model, the posterior prediction for becomes
(x) (x) o² - fia. (o. (x)) = k (x, - (A:) (z) ( (
(18)
Similarly, we can define the posterior predictions for e with noise in the GP model as ju{ (ax) and of (z). The sum of posterior variance for GP generated by 2 satisfy the next lemma, based on information theory (27
Lemma A.3. The sum of GP posterior variances given t samples satisfy
T
Σ
oo S VCTTH EoL((w)) S VC,TT
(19)
where C. Tog(1+a 2j and ohe and of are the maximum information gains for f and c, respectively.
We have the following lemma for of (x) and of (x).
Lemma A.4. The noise-free (GP) posterior standard deviation satisfies of (x) < of (x) Vo >
Proof. We first note that all the eigenvalues of K! smaller than those of K/ + 0 since K/ is
symmetric and positive definite. Thus,
k/ (k/)) (x) + 021) 1 (a) < (=))) k/ (z),
(20)
for Vo 0 and k! (æ). Therefore, by their definitions and 18) the proof is complete.
The posterior standard deviation under assumptions (1)-(4) in 6 in the frequentist and noise-free setting is given in Lemma 3.5 whose proof is given below.
Proof. By Lemma 7 in 6 there exists C' > 0 so that
( 2 C² min(
(k).
(21)
at most times, for vk E N, k < t, and = 1...., Therefore, for the SE kernel,
of ( -
(22)
at most times. For Matérn kernels, we have 21 at most & times.
20

---

If of (x:) < 0, or equivalently fit u (x) < 0. 30 leads to Bl((a) [=)) Using maximum information gain, tighter bound on the posterior standard deviation can be obtained in the next lemma.
Lemma A.5. Given Vt N and = 1,2, ..... - 1. for SE kernel, there exists constant C' > so that
d+1 (t) of (2++1) 2 C tā log holds for at most l times, for vk S I. Similarly, for Matérn kernels with v >> 0.5,
(23)
k
of (2++1) 2 C² 12rtu
log 2o
(24)
k
holds most l times.
Proof. From Lemma A.4 and Lemma A.3 we can write that
of (2x) S Vnl.
(25)
where we without losing generality C2 S 1. Therefore, for any N and & s t,
Vil
of (a++1) 2
(26)
at most times. Therefore, for SE kernel, by Lemma A.2
there exists C" > 0 such that
d+1 log 2 (t)
of (x(+1) 2 C
(27)
k
at most & times. For Matérn kernels with >> 0.5,
log To (1)
(x 2 C
(28)
k
most times.
Next, we state some basic properties of ó, O and lemma.
Lemma A.6. The PDF and CDF of standard normal distribution satisfy < Φ(x) S ((0) <
0.4, ((x) (0, 1), for any x E RR. Given a random variable & sampled from the standard normal distribution: 5 ~ (0, 1). we have P[f > clc > 0} < L 12/2 Similarly, for < O, PPf < dlc <
0} < Je 2/2 The function 7(-) is monotonically increasing.
The last statement in Lemma A.6 is a well-known result (e.g.. see proof of Lemma 5.1 in (7
The next lemma proves basic properties for EI{
Lemma A.7. For Va E C, EI (x) 2 0 and EIf (x) ft - (2). Moreover
+f(x)) < EI (x) [((x((z)), (x) 2f(()) +l
<<(x) <0 < 2 0.
(29)
Proof. From the definition of If and EI,, EI((x) 2 0 and EI(()) 2 vi nd (x) follow immediately. By 4
E1/(2) of (x) (x) + (x))
(30)
(x(
< ol2 (z)). If of (x) 2 0.
we can write (x) x((x)) + o (z)). The left inequality in 22 is an immediate result of
(=)
EId (x) 2 ft 1 (x).
21

---

B Proofs for simple regret upper bound under frequentist assumptions
We state the boundedness result as a Lemma for easy reference.
Lemma B.1. Under Assumption 3.2
[f()) & By and |c(x)] S for all a E C.
Proof. By Assumption 3.2 we can write
[s(=) S |1 ky( S By.
(31)
Similarly,
[c(x)] S ||cll ke (x S Be.
(32)
The following Lemma is well-established result (8) Lemma B.2. At any given C' and E I, the confidence intervals satisfy
lf(z) μ (=)) (())
S (x)
(33)
Next, present lemma the relationship between If and EI,, previously seen in (6].
Lemma B.3. At C,t N.
((z))EI((2)) < Bio (z).
(34)
Lemma B.4. The piuno 1/(z)) and EI (x) satisfy
(m) < r(B,) F.I (z),
(35)
r(-B,)
for Va E C and 2
Proof. If st f(x=) O, then (x( 0. Since EIg (a) 2 (.(35) is trivial. If ft f(x) > 0, by
Lemma B.2
ft (z() = = [() f(x) (x) f(w) md(ar) -Byo((
(36)
From the monotonicity of T, we have
Jit (x))
> x()B)),
(37)
of (x)
and therefore,
ft (/=1((z)
(1)( = (0()
> 7((-B))o{(
(38)
From Lemma B.3
1f(x) EIj (xx)))(((()) < (r)
(39)
Applying 39
38
leads
(I((x) > B, B 1x(x) T(-B₃) If (x)
r(-B,)
(40)
T(B,)
Proof of Theorem 3.3 is given next.
22

---

Proof. From Lemma B.1
- - 2B,
(41)
Since - 2 0. 1,+ J 2 2 at most k times for any k E N. Further, f(x,) 2 ft for
Vt E N. Choose = [t/2], where [x] is the largest integer smaller than x so that 2k St 2(k + 1).
Then, there exists & S lx s 2k so that lit Stt+1
2B1 and litt1 carss-faan f(rr++)) S 0.
From Lemma B.4
Ft -ī f(x²) S Jit -f(x)) S Ti, (2=")
+BB)) F.I (x*) = CrB P12 (x*)
Pr. (2r")
=CB
FT (x=)
7( (-BB)
(42)
Pte (x1++1)
EIi (xott)),
SGB Pie (x*)
where CBB
r(Br)
Using P((x) S (22
implies
B[-
Cr
[ p (mrt 1) (1),+1)) + ol (o Moleh, (on+t)))
5 Prn (x*)
(43)
Cr
[ u (1) 1)) (at, 0.40 (m1,+1)
Prn (a**)
where the last inequality uses o(.) 0.4. From Lemma B.2
fit M1, (I+++) =ftt fixt1 + sitt1 - f(x(+1) + f(x(+11) - Mig (Iea+1)
sint1 + Byo (at+1) S 2B Byot, (Dtut1).
(44)
Sit
Using 44 in 443
we have
To S C+B
2BB k
+ (B, (mm411)
(45)
Pi.. (xx)
Next, we consider the function Pts x². Using the fact that c(x²) S 0, we have by Lemma B.2
Mig (x=) < B.o (x*) cc(x)) S B.o (x*).
(46)
Thus,
1g (xx))
2 Be. ofe (x*)
(47)
From the monotonicity of t. we have
14 (1,) ofe (xx*)
Pr. (x0) Φb
2 (-Bo).
(48)
Applying 48 to 43
we have
2B, Tt 4 (-BB.
Cr
+ (By + 0.4)0 (004+1)
(49)
k
As t + oo, the + 0o and k + cc. Further, if of (2141) + 0, of, (211+1) + 0 and r; + 0.
Proof of Corollary 3.6 presented next.
Proof. We consider the convergence rate for r, under additional assumptions for the kernel. From Lemma 3.5 for both SE and Matérn kernels, of (#:+1) C' minru.11 log" (k) most is times for
any A E N and i I....,t. t.
Choose A = [1/3] that 3k < < 3(k + 1). Following the proof of Theorem 3.3 there exists k <
& < 3h where fit fit <
28; f(1 2 f and of, (Ix,+1) < C'
mintw.11 log)(k)) (k).
Similar to (49, we obtain
CB
[B
+ (By - 0.4)C' min(u.1)
log
(50)
(--B.)
k
The convergence rates follow.
23

---

B.1 Proofs for improved simple regret upper bound under frequentist assumptions
Proof of Theorem 3.7 is given below.
Proof. From the proof of Lemma A.5 we know of (2:+1) 2 Vtv at most & times for any & S
and ......t.
Choose k [t/3] so that 3k S t - 3(k + 1). Following the proof of Theorem 3.3 there exists
k S tx - 3k where fit fia+1 < 2B, f(z(+11) 2 flitD and of (Fe++1) < 3 v ml
Similar
to (50). we can obtain
tY
CBy
2B
-
3
+ +3(B, 0.4)
(51)
Φ B.)
3-3
The convergence rates of the simple regret upper bound follow from Lemma A.5
We provide the sample complexity of Theorem 3.7 below.
Corollary B.5. Under Assumption 3.2 the CEI algorithm achieves a sample complexity of
[og(1/e))(tt) and O(e- 20-4
log(1/6)),
(52)
for SE and Matérn kernels, respectively.
Proof. Using Theorem 3.7 to achieve simple regret of most for SE kernel, set
log - (t) =.
Solving asymptotically for gives the sample complexity
t(c) O
log [og(1 (()()/))
Similarly, for Matérn kernels, we have
2044 log 2047 (t),
(53)
which completes the proof.
C Proofs for simple regret upper bound under Bayesian objective assumption
We state the boundedness of f and Lemma for easy reference.
Lemma C.1. Under Assumption 3.9 there exists M, > 0 such that [f(x)) < M with probability > 1 8/3. The constraint function is bounded by its RKHS norm bound [c(x)] B
We recall a well-known result on confidence interval of [f(x) 1u (ar) under Assumption 3.9 Lemma C.2. Given å E (0, 1), let 3 2 log(1/0). For any given æ E C and E N,
27
If(x) μdf (x) S /Bo
(54)
holds with probability 2
Proof. We prove the inequalities for f. Under Assumption 3.9 Lemma A.6
f(x) ~ ((((()).(((1)) By
P ff((() (x()) (B 1- (VB)
(55)
Similarly,
P Pff(x) - (x( - /oo(((2))
- 2
1 5
(56)
Thus,
P((((0) - ul < (oo 2 -
(57)
Let - = 88an and 54 proven.
24

---

Lemma C.3. Given å E (0, let 3 2 loo((=16)) where = =f Then, for all E N,
[f(x)) - (x)) S (x),
(58)
holds with probability 2 11-6. 6.
The next lemma address !! under the Bayesian assumption.
Lemma C.4. Under Assumption 3.9 the probability distribution of I satisfies
00 -
a a<0,
P( (x) <a}
Φ ([(im=)
= a20
(59)
Proof. Under Assumption 3.9
given t. f(x) ~ ((( (x)) Since I (x) 2 for all
I, 559 follows immediately if < For a 2 0,
([I - a) = P( f(z) - = -1- - ft - a}.
Using basic properties of the standard normal CDF,
Jt (x)
( (a (a- si + mz 11(
P-((() S ft+ a} =1
of (x)
Next, we present the relationship between (x) and (x)
Lemma C.5. Given d E (0. 1). let B max max(1.44, 2 log(ca/8)) where constant ca Assumption 3.9 at given æ E C and E N,
1+22
Under
25
EI! (x)) S Bo! (2) 1- 8. P { 14 (z)
(60)
Proof. Given scalar w > 1, we consider the probabilities
p P(1(())> of (x) EIJ (x)) and p P(1((x) -o! EI( (x))
(61)
Consider the first probability in 61 From Lemma A.7 El((x) 2 for Vo and t. Therefore, (x(x) + (x) > O. From Lemma A.7 Lemma
C.4 and the monotonicity of 4, we have
oo (x) EI (x) ft + ul (xx
P ((( (x) [1)
=1 Φ
d((x)
(62)
<1 - & (ww) < _ 2
2
where the last inequality is from Lemma A.6
For the second probability in (61.. we further distinguish between two cases, First, consider -of (x) FT/ (a:) From Lemma C.4
PP r/ (m) < -o! (m) w + FI((ar)) = 0.
(63)
Second, consider the premise
of (x) + EI (x) 2 0. By Lemma C.4
we have
P [1(()) < -o! (x) EI (z) + (-w+ EI (x)
ftt + mz (x)
(64)
(x)
To proceed, we show that ft /f (x: 2 Suppose on the contrary, ftt /z/ (xx (4(x)) ={ (x:) < O. From Lemma A.7
and thus
El (x) of (x)
< <ll (x)) (0)) < 1 1 w,
(65)
25

---

which contradicts the premise of this case. Thus, we have ft ud (a) 2 (and 2x(2) 2 0). From the definition (4) since & (0, 1).
- St + mz (a)) of (2)
|el (x) (2(z) 11 + o(z (2))) < (()(
(66)
In addition, by the premise of this case and Lemma
[x)(a))
S (x)
S of (x) + olzf
(67)
Given that w > 1 and (()) 2 p (z)), we have
of (x) + x(0) > 2/ (z) + (x) w, 2x) w -- x(0) > 0.
(68)
As 24 (x) 2 0 increases, ((z( (x)) > 0 decreases. Thus, have
2 (x)
p(w (0)) o( (x)) < o(w (0))
w (0)
(0)) 2 (2).
(69)
0( (x))
Denote ei (w))
w- (00) Applying
wー (0)
69
67
obtain
C (w) < oे (x), (z ((((ww)))
(70)
Applying (70 and 66
64
obtain
IP
(x) < -o (x)) FT! (0)) < (-w 1-w-ob (
(71)
< (-w + s(c (w)w)).
Notice that ((c((w)w)) < (w)) < (w) due 1. By the definition of t and mean value theorem,
(- + (()((w)))) = ((-w) + (w))(((())))
1
t=² dx S (--
2t
V2T e (w- M(s-())())))) (cc((w)))) < <$(-w)
e (())))(( e (w))(()))))
(72)
+
2x
1
e fra(mm)
1 um?
1
5 $ +
2n
2
2n
where (w) = [1 - (w))) + |c {. The last inequality in (72) again uses Lemma A.6
Notice that (w) increases with and for w 2 1.2, c2(w) > 1. Thus, e l e [ex(w)) for w 2 1.2, which simplifies (72 to
$ o(-w+oler (w))))
(73)
where C²1
1t 2n
Therefore, by and 73 if w 2 1.2,
PP (T2(() < - (x)w + FI((x)) < Czle c Jmm
(74)
Combining 74 with 62 and 63 we have
P P((1((x)- -
EI)
> (z) < cae to tm?
(75)
where Co:
142a for 2 1.2. The probability in 75 monotonically decreases with Let
5 = Cave tno? Then, taking the logarithm of 8 leads to log( and the proof is complete.
1+2
= 2 2 Let B = max (w2 1.22).
2
The relationship between Tx( and F.f (a:) under the GP prior assumption is given the following lemma
26

---

Lemma C.6. Given d E (0,1), let 3 = 2 ( 66), where ca = 1t2x
At given a E C and t E N,
2x
v(-v3)
1/ (ar) & (x),
(76)
TVV3)
holds with probability 2 2
Proof. From Lemma C.2 with probability 2 1 8, (54) stands. If ft f(z) S 0, then 1((x) 0.
Since EI1(x) 2 0. 76 is trivial. If f¹ f(x)) 0, by Lemma C.2
5 (x) (x) ft- -x) + f(x) ud (a) > f(x) ut (a)
(77)
> -o (a:)
with probability greater than 2 1 - 0/2. From the monotonicity of r, we have
ft -1())(()) (z)
(x) {z)
> TT(-BB,
(78)
and therefore,
fit (1)
oz) (x)r
7(- (3)o (x),
(79)
dx(xx)
with probability greater than
8/2. Using 5/2 in Lemma C.5
1f (x) EI (x) /oo (z),
(80)
with probability 2 1- 5/2. Applying 880 to 79 with union bound leads to
VB+ (x(x) r(-v3) 1/ (xx)
T(-VB)
Elg (x)
(81)
T(VB)
with probability greater than 8.
We can now prove Theorem 3.10
Proof. From Lemma C.1
1-1 Et- =5t -st 2M,,
(82)
with probability 2 1--1-/1 8/3. Next, consider ft - mf (I)+1). Recall that 3, 1ogg(33)//)) From
Lemma C.3 Lemma and and Lemma A.3 we have
mf / (x141) Σ max - f(( + f(0111) o (x1+2),
(83)
t-1
ft fth + 2 of(41) < 2M, + 3/222 V C,,tt
with probability 25/3 via union bound. Given that max puf (2.+1). 0) 2 max
w/ (#1+1),0) 0, > 2M, + k Choose [t/2]. where [x]] is the largest integer smaller than x so that 2k t S 2(k + 1). Then, choose the first index tę where k S tx < 2k so that max - n/, (x1++1), 0} < 2M;
a//2 / C,,tyf at most k times for any ls E N with probability 2 1 - 1-26/3 28/3.
k
g//2 V C, As discussed above, such t exists with probability 2 28/3. We note that maximum information gain and its upper bound does not depend on the optimization path. Importantly, the choice of to does not depend random information after iteration t..
27

---

From Lemma C.6 and B = 2 log(66a,/ with probability 2 1 - -/33,
rt = f(x²) S Jit - f(x") )- _ 1 (x:)
7(8112) E.I (x*) (3) Ple (x)) T( --B1122)
EIi (x*) S cr(( Pex (2(+11 ET (Dt
Pse (x*)
Pie (x*)
=c (3) Pie (1t
(z(++1)) + o/, (1++))((2z) (21++1)) (84)
(fit - 1/,
Pos (x*)
(B) Pi. (112+1)
(Jit - 1/1 (x (2(++1)) + 0.4o! (ma7-1)
Po (2**
where the last inequality uses (b(.) 0.4. From the choice of lg. (84 leads to
Pte (It++1) Scr
2M, k
1112 _ VV,eet + (0.4 30 (moutt)
+
(85)
(x))
with probability 2 1 - 8. Next, consider the probability function Pa. at xx and +1++1- Using the fact that c(x*) S 0, we have by Lemma C.2 at xx and tx.
Mig (xx) & Boo (x') + c(xx) )xx==== S Boo (z*).
(86)
Thus, we can write
M4, (x')
- -B.
(87)
of (x*)
From the monotonicity of 4 we have
Mig (x*))
1 (-Be,
(88)
0 (x**)
Using 88
the P.,. functions have
Pie (11+t1)1) Pee (x*)
5 1 (o)
(89)
Applying 889 to 85
have
2M, +
32/2 Vint + +0.4+ (2 (BmAt))
Pt (3) Φ (B-B
(90)
with probability 2 1-5.
The proof of Theorem 3.11 is next.
o (0:41)= 2 Vale E where i 0, .,.....- most times for any k E N
Proof. From Lemma A.5
and k < f. Choose k = t/3] which leads to 3/ < t < 3(k +). Let tu be the first index in [k: 34]
so that o% (xu+1) < &
and max /ry (1+++1) 1), 2M, 2//2 CC,tt' which exists
with probablity 2 25/3. Notice that .3. /2 = O(log 1/2 (t)). Following the proof for 90 we have
2M, 1/22 k
re (B)
+
C,try + (0.4+ 8123)
(91)
( -B))
k
b
with probability 2 1 - 5. Using Lemma
A.2 the proof is complete.
28

---

D Test problems
The mathematical formulations of the testing problems in Section 4.2 are given in this section. The objective, constraint functions and the optimal f of Problem is given below.
f() = sin( (z1) 22,
c(æ) sin(x.) sin(w2) + 0.95 S 0,
(92)
2; E [0, 6]. = 1,2,
f 0.25.
The objective, constraint functions and the optimal f of Problem 2 is given below.
f(x) = 21 + 22
(x = -0.5
2x2)) - 21 2xz + 1.5 S
(x) = x + 1.5 5
(93)
3; [0, 1), 112
f = 0.6.
The objective, constraint functions and the optimal of Problem is given below.
f(x) = 2
+
x2 + I3
T4
6 1.1 Σ
E exp Σ
A,, - P2,)²²
E 10, 11.
E
1, 3,
0.131
0.232
0.234
0.404
(94)
0.169
0.413
0.145
0.882
P=
0.556
0.830
0.352
0.873
0.012
0.373
0.288
0.574
10
0.05
17
3
10
3.5
8
A
17
17
1.7
0.05
3.5
0.1
10
10.
8
=
0.
The objective, constraint functions and the optimal of Problem is given below.
f(x)
Σ a exp
Σ
Asylz, P())2
j=1
c(x)) Σ
Fj -
1=1
2 E [0, 1), = 1,...,6
1100,
3.2.
(95)
10
3.0
17
3.5
1.7
8.07
0.05
10
17
0.1
8.0
14
4
3.0
3.5
1.7
10
17
8.0
8.0
0.05
10
0.1
14
T0.131
0.170
0.557
0.012
0.828
0.587
0.233
0.414
0.831
0.374
0.100
0.999
P=
0.235
0.145
0.352
0.288
0.305
0.665
0.405
0.883
0.873
0.574
0.109
0.038
3.32.
29

---

826
Figure 3: Contour plots for the objective function (left) and constraint function (right) for Problem 1.
The infeasible region is marked the plots. The global optimum is marked with star sign.
10
400
0.
0.4 0.6
0.5
2.0
0.0
02
0.4
0.
3.5
02 86
3.6
Figure 4: Contour plots for the objective function (left) and the two constraint functions (middle and right) for Problem 2. The infeasible region is marked with black line on the objective contour. The global optimum is marked with star sign.
120
10
121
130
Figure 5: Contour plots for the objective function (left) and constraint function (right) for Problem 5, The infcasible region is marked on the plots. The global optimum is marked with star sign.
30

---

The objective, constraint functions and the optimal f of Problem 5 is given below.
f(x) 100(22 - z²)² + (1 -x1)
6 (2) <² + +
(96)
(2(2)) =1 + x2 1.5,
E [-5, 10), E [0, f -==0 0.
The contour plots of Problem 1, 2, and 5 are given in Figure
and 5
31


Reviews:
[{"review_id": "AssNRXx9vK", "reviewer": "Reviewer_QM2L", "summary": "This paper provides a theoretical convergence analysis of the Constrained Expected Improvement (CEI) algorithm in Constrained Bayesian Optimization. It establishes simple regret bounds under both frequentist and Bayesian settings, showing improved convergence rates for squared exponential and Matérn kernels. Using information-theoretic tools, the analysis overcomes challenges from CEI’s multiplicative structure. Results are supported by experiments, offering theoretical justification for CEI’s practical success.", "questions": "1. How does the analysis handle the non-convexity and potential multimodality of the CEI acquisition function in practice? The regret bounds assume exact maximization of CEI at each iteration, but the acquisition function is non-convex and often only approximately optimized in practice. How sensitive are the theoretical guarantees to optimization error in the acquisition step?\n\n2.  How valid is the assumption of conditional independence between the objective and constraint GPs in real applications? The CEI analysis assumes conditional independence, yet in practice, objective and constraint functions may be correlated. How would the theoretical results change if this assumption were relaxed or violated?\n\n3.  Can the authors clarify how the feasibility probability is controlled in the regret analysis? The bound includes inverse terms like $1 / \\Phi(-B_c)$, which can be large or unstable if the feasibility boundary is close to zero. How robust is the bound when $c(x^*) \\approx 0$, i.e., the optimal point lies near the constraint boundary?\n\n4. Is there a path to extending the current analysis to noisy or approximate observation settings? Given that real-world evaluations are often noisy, can the authors discuss how their framework could be generalized to include noise, possibly following techniques used in noisy GP-UCB or Thompson Sampling literature?\n\n5. How does the multiplicative acquisition function structure affect the exploration-exploitation trade-off compared to additive or penalty-based methods? The CEI acquisition function is the product of EI and feasibility probability. How does this structure influence the theoretical exploration behavior, especially in high-dimensional or narrow-feasibility domains?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "strengths:\n1. This is the first work to derive simple regret upper bounds for the CEI algorithm under both frequentist and Bayesian settings.\n2. Under frequentist assumptions (RKHS model), they derive improved rates for SE kernel $\\mathcal{O}(t^{-1/2} \\log^{(d+1)/2}(t))$ and for Matérn kernel  $\\mathcal{O}(t^{-\\nu/(2\\nu+d)} \\log^{\\nu/(2\\nu+d)}(t))$. These rates improve over the direct constrained extension of Bull (2011), which achieved $\\mathcal{O}(t^{-1/d})$.\n3. The authors show that, with high probability, the same convergence rates hold when f and c are samples from GPs. This complements prior work like Srinivas et al. (2009) for unconstrained GP-UCB, extending it to CEI.\n4. The paper leverages maximum information gain bounds to obtain tighter regret bounds, following approaches in recent literature on UCB (e.g., Lyu et al., 2019; Vakili et al., 2021).\n\nweaknesses:\n1. The analysis requires the existence of an initial feasible sample, which is not always easy to guarantee in practice. Without it, the CEI acquisition function is undefined because the improvement is computed over the best feasible value.\n2. The convergence analysis is conducted only under a noise-free setting, where evaluations of both the objective and constraint functions are assumed to be exact.\n3. The analysis assumes a single constraint (or extends to multiple constraints under independence assumptions). However, real-world CBO often involves correlated or conflicting constraints, which are not addressed.\n4. There’s no non-asymptotic regret bound (e.g., PAC-style guarantees) to quantify performance in small-budget settings.", "was_revised": true, "final_justification": "The authors provided a detailed response to my comments, which is fairly convincing. I am glad to raise my score to 5.", "rebuttal": "We sincerely thank the reviewer for taking the time and effort to review our paper. We greatly appreciate your valuable feedback and have made every effort to address your comments thoroughly in the detailed responses below.\n\n$\\textbf{weakness 1}$ $\\textit{The analysis requires the existence of an initial feasible sample, which is not always easy to guarantee in practice. }$\n\nR: We appreciate the reviewer’s insightful observation. As noted in Remark 3.1 of our paper, this indeed represents a fundamental limitation of the Constrained Expected Improvement (CEI) algorithm originally proposed in [1]. Our primary objective in this work is to provide theory to this widely used algorithm, rather than to introduce modifications or improvements. Accordingly, this limitation is not only acknowledged but also  incorporated into our theoretical framework.\n\nSome recent works have tried to address the issue of infeasible initial samples. One common strategy focuses on finding an initial feasible sample before switching back to CEI. For instance, in [2] the authors proposed using only the GP of the constraint function first, until a feasible initial sample is identified. In this case, our analysis still holds as the number of iterations increases and feasible samples become available. \n\n$\\textbf{weakness 2 and question 4}$ $\\textit{The result is in noise-free setting}$\n\nR: We hope to address this comment in two parts, corresponding to the objective and constraint functions, respectively.\n\n1) The assumption of noise-free observations on the objective function $f$ stems from the lack of theoretical understanding of Expected Improvement (EI) in the noisy setting. To the best of our knowledge, even in the unconstrained case, no simple regret bound for noisy EI has been established. This difficulty arises primarily from the non-convexity of the EI acquisition function and the use of the noisy best observation in its formulation, which introduces significant analytical challenges. Given this unresolved issue in the unconstrained setting, extending the analysis to constrained EI (CEI) with noisy objective observations is particularly nontrivial.\n\n  However, we have made an effort to partially address this challenge by allowing noise in the objective function observations while keeping constraint observations noise-free. Our analysis leverages a recent theoretical advancement that begins to bridge the gap for noisy EI in the unconstrained case. We would be pleased to include the resulting simple regret bounds for CEI under this setting (noisy $f$ noise-free $c$) in the revised manuscript. The convergence rates are $\\mathcal{O} (t^{-1/2}\\log^{(d+1)/2}(t))$ for SE kernels and $  \\mathcal{O}(t^{-\\nu/(2\\nu+d)} \\log^{\\nu/(2\\nu+d)}(t))$ for Matérn kernels.\n\n2. Regarding constraint observations, the requirement of noise-free evaluations is closely tied to the design of CEI itself. In the presence of noise on the constraint function $c$, it becomes fundamentally ambiguous whether a given sample satisfies the constraint. This ambiguity complicates the definition of feasibility, as well as the identification of the best feasible solution—both of which are central to the CEI framework. Since our work focuses on a theoretical analysis of CEI, we follow the standard assumption of noise-free constraint observations.\n\nNonetheless, to enhance the practical applicability of our results, we follow the suggestion of Reviewer 3QQu. We include a constraint tolerance  $\\epsilon>0$ so that practitioners can implement $c(x)\\leq \\epsilon$ to roughly account for small noise. This constraint formulation is commonly employed in the constrained Bayesian optimization literature [4] to accommodate small levels of noise. We have successfully extended our analysis to establish simple regret bounds under this relaxed feasibility definition and have included the new results in the revised manuscript. The convergence rates remain the same.\n\n3. In addition, GP-UCB and TS techniques do not apply to EI because EI has the noisy observation directly used in its formula (the best observation) and is highly nonlinear and nonconvex.\n\n$\\textbf{weakness 3 and question 2}$ $\\textit{Conditional independence of constraints}$\n\nR: We agree that correlated constraints are more realistic in real-world applications. However, we would like to point out that \nthis assumption is made by the CEI algorithm itself. Given its wide adoption and strong empirical performance, we anticipate CEI to work relatively well with a limited number of constraints that are not conditionally independent. In line with these established precedents, we have followed this assumption in our work. We plan to explore relaxing this assumption in future work.\n\nWe briefly provide some intuition below about how this assumption would impact the convergence of CEI. Consider two identical constraints $c_1(x)\\leq 0$ and $c_2(x)=c_1(x)\\leq 0$. Recall that the probability of feasibility (PoF) is $p_1(x)=\\Phi(\\frac{-\\mu_t^{c_1}(x)}{\\sigma_t^{c_1}(x)})<1$ multiplying $p_2(x)=\\Phi(\\frac{-\\mu_t^{c_2}(x)}{\\sigma_t^{c_2}(x)})<1$. Thus, at a feasible point $x$, CEI would underestimate its probability of feasibility, which if modeled correctly would just be $p_1(x)$ instead of $p_1(x)p_2(x)$, especially initially. However, as the GP surrogate models of the constraints become more accurate, $p_1(x)$ and $p_2(x)$ both approach $1$ at a feasible point and its CEI value increases. Therefore, we anticipate the regret bound to worsen but convergence continues to hold. Further, since the convergence rates are dominated by the maximum information gain of the objective, thanks to the multiplicative structure of CEI, it is possible that the convergence rate itself remains similar when the condition is violated. \n\n$\\textbf{weakness 4}$ $\\textit{No non-asymptotic bound}$\n\nThank you for this insightful comment. We are able to fully address this concern. To the best of our knowledge, there are very few existing results on non-asymptotic regret bounds in the BO literature. From our Theorem 3.8 and 3.12, we can derive a new result that establishes the iteration complexity—i.e., the number of iterations required to achieve a given simple regret error $\\epsilon$. For instance, to reach an error of $\\epsilon$ we need $\\epsilon^{-2} \\log^{-(d+1)}(1/\\epsilon)$ iterations. We have added this theorem along with its proof into the revised manuscript.\n\n$\\textbf{Question 1}$ $\\textit{Exact solution to EI}$\n\nThank you for this insightful question. We first answer how to find maximum of CEI in practice. A common technique is to use multiple starting points and gradient-based methods to find better solutions. For unconstrained EI, there has also been work that suggests a branch and bound approach can solve the maximization of EI relatively well [4]. As the reviewer stated, in practice often only an approximate maximum CEI can be found. We totally understand this point and it is in fact a general issue for the majority of BO algorithms. Therefore, resolving this issue is beyond the scope of our paper.\n\nAs for the sensitivity of regret bounds to the optimization error in the acquisition step, this itself is an active area of research (a recent paper on this is [5]). Although addressing this problem is beyond the scope of this paper, we would be happy to share our perspectives on this topic if the reviewer is interested.\n\n$\\textbf{Question 3}$ $\\textit{Robustness at boundary}$\n\nThe constant $B_c$ is the RKHS norm of function c and does not change because of $c(x^*) = 0$.  \n\nThe probability of feasibility is controlled via the confidence interval of the Gaussian process, i.e., $|\\mu_t(x)-c(x)|\\leq B_c \\sigma_t(x)$. If $c(x)=0$, we have  $|\\mu_t(x)|\\leq B_c \\sigma_t(x)$. Thus, as $\\sigma_t(x)$ decreases, $|\\mu_t(x)|$ decreases as well, making the probability of feasibility $\\Phi(\\frac{-\\mu_t(x)}{\\sigma_t(x)})$ controllable. The confidence interval and the regret bound holds for $c(x^*)=0$. \n\n$\\textbf{Question 5}$ $\\textit{Multiplicative structure of CEI}$\n\nIn our experience, the multiplicative structure forces more exploration around the feasible region predicted by the GP models due to the quick decaying of the PoF function $\\Phi(\\cdot)$. \nIt also mitigates the burden associated with hyperparameter tuning compared to penalty-based methods since one does not need to tune the penalty parameter. \nIn theory, an additive structure can induce an additive regret bound with contribution from both the objective and constraint and likely the penalty parameter. In contrast, the constraint affects our regret bound by an additional multiplicative factor.\n\nWe add our regret bounds hold for high-dimensional problems or narrow-feasibility domains and we do observe good CEI performance in our own experience for medium-dimensional problems and problems with small feasible regions.\n\n[1] J. R. Gardner, M. J. Kusner, Z. Xu, K. Q. Weinberger, and J. P. Cunningham. Bayesian optimization with inequality constraints. In Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32, ICML’14,b JMLR.org, 2014.   \n\n[2] Q. Lin, J. Hu, Q. Zhou, L. Shu, A. Zhang. A multi-fidelity Bayesian optimization approach for constrained multi-objective optimization problems, Journal of Mechanical Design, 2024\n\n[3] S. Ariafar, J. Coll-Font, D. Brooks, and J. Dy. ADMMBO: Bayesian optimization with unknown constraints using ADMM. Journal of Machine Learning Research, 20(123):1–26, 2019.\n\n[4] A. M. Schweidtmann, D. Bongartz,  D. Grothe, T. Kerkenhoff, X. Lin, J. Najman, and A. Mitsos, 2021. Deterministic global optimization with Gaussian processes embedded. Mathematical Programming Computation, 13(3), pp.553-581. \n\n[5] H. Kim, C. Liu, and Y. Chen. Bayesian Optimization with Inexact Acquisition: Is Random Grid Search Sufficient? rXiv:2506.11831, 2025."}, {"review_id": "ujYBPTm3vD", "reviewer": "Reviewer_DV68", "summary": "This paper derives the convergence rate of the constrained expected improvement (CEI) algorithm, a widely used method in constrained Bayesian optimization. \nThe analysis shows simple regret bounds for CEI on objective and constraint functions that lie in an RKHS and on those drawn from Gaussian processes.\nThe authors conducted experiments to confirm the results of the analysis.", "questions": "The analysis seems to assume that the number of constraint functions is one. However, I think there are several real-world problems that contain more than one constraint. Is it tedious work to extend the analysis result in such a situation?\n\nI could not confirm how close the derived result was to the actual behavior of CIE from the result of the numerical experiment. Could you plot the derived convergence rate in Figures 1.a and 1.b (if possible)? In addition, please conduct experiments with different dimensions to confirm how it changes the convergence rate.\n\nIn Figures 2 and 3, I think the \"infeasible\" region is marked.", "limitations": "The analysis with more than 1 constraint function is desired in future work.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\nThis paper is the first work to derive the convergence rate of the CEI algorithm. In addition, the key points of the proof are summarized as proof sketches. These points increase the originality and clarity of this paper.\n\nWeakness:\nThe numerical evaluation is not sufficient to check whether the derived convergence rate is reasonable.", "was_revised": true, "final_justification": "My concerns, including the limitation of the number of constraint functions and experimental validation of the derived results, have been resolved precisely. Therefore, I believe that the quality of the paper will be significantly improved in the revised version.", "rebuttal": "We want to first thank the reviewer for taking your time and effort to review our paper. We appreciate your valuable feedback and hope to sufficiently address them below. \n\n$\\textbf{Weakness 1}$ $\\textit{The numerical evaluation is not sufficient to check whether the derived convergence rate is reasonable.\n}$\n\nR: As the reviewer suggested, we have now performed additional numerical experiments to strengthen our results. Please see our response to question 2 for details. \n\n$\\textbf{Question 1}$ $\\textit{ Multiple constraints}$\n\nR: To clarify, we have already extended the results to problems with multiple constraints, as discussed in Remark 3.15. As noted there, this extension is possible under the assumption that the constraints are conditionally independent. This assumption is inherited from the original CEI method [1] and has been shown to yield strong empirical performance. In addition, we have empirically evaluated our algorithm on a problem with multiple constraints, and the results in Figure 1(d) demonstrate that it continues to perform well in such scenarios.\n\n\n$\\textbf{Question 2}$ $\\textit{Numerical experiment question and requests}$\n\n The derived theoretical convergence rates depend on unknown problem-specific constants -- the maximum information gain, which prevents us from expressing the upper bounds in a fully explicit form. Also,  our theoretical analysis is asymptotic in nature.  As a result, it is not feasible to directly overlay the theoretical rates on our empirical plots for quantitative comparison. Nevertheless, the empirical results clearly exhibit sublinear convergence behavior, which qualitatively aligns with our theoretical predictions. This observed trend provides strong supporting evidence for the validity of our theoretical analysis, even though a direct quantitative comparison is not feasible.\n\nAs the reviewer suggested, to further validate our theoretical findings,  we conducted additional experiments using objective and constraint functions sampled from both reproducing kernel Hilbert spaces (RKHSs) and Gaussian process priors defined by the squared exponential (SE) and Matérn kernels, across different input dimensions (specifically $d=2$ and $d=4$). The results are in Table 1 We plotted the log-log curve of simple regret against the number of iterations. In all cases, we consistently observed sublinear convergence patterns, which align well with our theoretical guarantees. These new empirical results have been included in the revised manuscript.\n\nFinally, we emphasize that our work provides the first theoretical convergence rate guarantee for CEI, establishing that its simple regret converges to zero. This is consistent with the results from our experiments. \n\n| Objective     | $t=0$              | $t=10$              |$t=20$              | $t=30$              |$t=40$              |$t=50$              |\n|-----------------|----------------|----------------|----------------|----------------|----------------|----------------|\n| RKSH, SE, $d=2$          | 0.170 | 0.008 | 0.003 | 0.003 | 0.003 |0.002     | \n| RKSH, SE, $d=4$          | 1.141 | 0.714 |0.116 | 0.034 | 0.026 | 0.024|\n| RKSH, Matern, $d=2$    | 0.192 | 0.006 | 0.005 | 0.004 | 0.001 | 0.001  |        \n|RKSH, Matern, $d=4$     | 1.100 | 0.751 | 0.350 | 0.103 | 0.022 | 0.021 |\n|GP, SE, $d = 2$              | 0.756 | 0.154 | 0.027 | 0.008 | 0.008 | 0.004 |\n|GP, SE, $d=4$                | 1.584 | 0.966 | 0.614 | 0.358 | 0.352 | 0.323 |\n|GP, Matern, $d=2$         | 0.755 | 0.148 | 0.111 | 0.032 | 0.014 | 0.013 |\n|GP, Matern, $d=4$         |1.584 | 1.057 | 0.581 | 0.438 | 0.437 | 0.349 |\n\nTable 1: The simple regret of different functions vs the number of iterations.\n\n\n$\\textbf{Question 3}$ $\\textit{Infeasible region marked wrong}$\n\nR: Thank you for pointing this out. We have made the necessary correction in the revised version of this paper.\n\n[1] J. R. Gardner, M. J. Kusner, Z. Xu, K. Q. Weinberger, and J. P. Cunningham. Bayesian optimization with inequality constraints. In Proceedings of the 31st International Conferenceon International Conference on Machine Learning - Volume 32, ICML’14, pages II–937–II–945."}, {"review_id": "t7Q45vlDl4", "reviewer": "Reviewer_xe4v", "summary": "This paper establishes the first theoretical convergence rates for the Constrained Expected Improvement (CEI) algorithm, a popular and widely used method for constrained Bayesian optimization (CBO), under both the frequentist and Bayesian settings. Despite its empirical success, the convergence rate of CEI had not been previously established. \n\nThe authors highlight that these results are not direct extensions from the unconstrained Expected Improvement (EI) analysis due to the complexities introduced by the constraints and the multiplicative nature of the CEI acquisition function. The paper also provides numerical experiments on both synthetic and benchmark problems to empirically validate the theoretical convergence results.", "questions": "1.  The analysis is performed in a noise-free setting. What new technical challenges would arise when extending this analysis to account for noisy observations of the objective and constraint functions, and how would you anticipate the convergence rates would be affected?\n2. The CEI algorithm and the analysis assume that the objective and constraint functions are conditionally independent. How robust do you expect these convergence rates to be to violations of this assumption, which may occur in many practical engineering problems?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. This work is the first to establish the theoretical convergence rate for the Constrained Expected Improvement (CEI) algorithm, a widely used method for which such an analysis was previously missing. \n2. The paper provides convergence rates under two different standard settings: a frequentist setting, where the functions are assumed to be in a Reproducing Kernel Hilbert Space (RKHS), and a Bayesian setting, where the functions are assumed to be sampled from Gaussian Processes (GPs).\n3. The authors explicitly identify and address the technical challenges unique to analyzing CEI, such as the multiplicative structure of the acquisition function and the need to balance exploration for feasibility with exploitation for optimality.\n\nWeaknesses:\n1. The analysis is conducted for a noise-free setting, meaning the function evaluations are deterministic. This may not hold in many real-world black-box optimization problems where observations are noisy.\n2. The CEI algorithm and the corresponding analysis assume that the objective and constraint functions are conditionally independent. For the extension to multiple constraints, it is also assumed that the constraints are conditionally independent of each other.", "was_revised": true, "final_justification": "The major weaknesses are addressed by the authors' responses.", "rebuttal": "We want to first thank the reviewer for taking your time and effort to review our paper. We appreciate your valuable feedback and hope we can sufficiently address them below. \n\n$\\textbf{weakness 1}$ $\\textit{Noise-free setting.}$\n\nR: We appreciate the reviewer’s comment regarding the assumption of noise-free observations and address it in two parts, corresponding to the objective and constraint functions, respectively.\n\n1. The assumption of noise-free observations on the objective function $f$ stems from the lack of theoretical understanding of Expected Improvement (EI) in the noisy setting. To the best of our knowledge, even in the unconstrained case, no simple regret upper bound for noisy EI has been established. This difficulty arises primarily from the non-convexity of the EI acquisition function and the use of the noisy best observation in its formulation, which introduces significant analytical challenges. Given this unresolved issue in the unconstrained setting, extending the analysis to constrained EI (CEI) with noisy objective observations is particularly nontrivial.\n\nHowever, we have made an effort to partially address this challenge by allowing noise in the objective function observations while keeping constraint observations noise-free. Our analysis leverages a recent theoretical advancement that begins to bridge the gap for noisy EI in the unconstrained case. We have added the resulting simple regret bounds for CEI under this setting (noisy $f$ noise-free $c$) in the revised manuscript.\nIn short, using a noisy simple regret definition, CEI achieves similar convergence rates in the Bayesian setting with i.i.d. Gaussian observation noise.\nThe convergence rates are $\\mathcal{O} (t^{-1/2}\\log^{(d+1)/2}(t))$ for SE kernels and $  \\mathcal{O}(t^{-\\nu/(2\\nu+d)} \\log^{\\nu/(2\\nu+d)}(t))$ for Matérn kernels.\n\n2. Regarding constraint observations, the requirement of noise-free evaluations is closely tied to the design of the CEI algorithm itself. In the presence of noise on the constraint function $c$, it becomes fundamentally ambiguous whether a given sample satisfies the constraint. This ambiguity complicates the definition of feasibility, as well as the identification of the best feasible solution—both of which are central to the CEI framework. Since our work focuses on a theoretical analysis of the original CEI algorithm, we follow the standard assumption of noise-free constraint observations.\n\nNonetheless, to enhance the practical applicability of our results, we follow the suggestion of Reviewer 3QQu. We have included a constraint tolerance parameter $\\epsilon>0$ so that practitioners can implement $c(x)\\leq \\epsilon$ to roughly account for small noise. This constraint formulation is commonly employed in the constrained Bayesian optimization literature [1] to accommodate small levels of noise. We have successfully extended our analysis to establish simple regret bounds under this relaxed feasibility definition and added it to the new results in the revised manuscript.\nWhile the upper bound of the simple regret changes with the inclusion of tolerance, the convergence rate remains the same. \n\n$\\textbf{weakness 2}$ $\\textit{Conditional independence of functions.}$\n\nR: The reviewer points out that the objective and constraints are required to be conditionally independent [2]. We would like to highlight that constrained Bayesian optimization methods often treat constraints independently by modeling each constraint with a separate surrogate (e.g., GP). When constraints are correlated, this assumption breaks down and tackling challenges in modeling joint constraint behavior is out of the scope of this paper. Since our focus is on providing a theoretical analysis of the original CEI algorithm [2], which inherently assumes independent objective and constraints, we have followed this assumption in our work. We plan to explore relaxing this assumption in future work. \n\n$\\textbf{question 1}$ $\\textit{Challenges for analysis in noisy setting.}$\n\nR: We appreciate this question. As we explained in our response to weakness 1, the extension to the noisy case is not accomplished even in the unconstrained case. The technical challenges are multiple. First, the current version of EI or CEI uses the best (feasible) observation as incumbent, which inherits the noise associated with that observation. This makes it very challenging to achieve a desirable convergence rate in the noisy case. \nSecond, the EI function is nonlinear and non-convex, thus making its analysis more complicated. \n\nAs we mentioned in weakness 1, we have newly derived convergence rates results under the noisy Bayesian setting and have updated the new results in the paper. \nHowever, the result is limited to noisy objective observations and the constraint observations are still required to be noise-free. The convergence rate on the noisy simple regret remains the same since we continue to use maximum information gain to establish the rates. \n\nIf we hope to further analyze noisy constraint functions, we first need to define what counts as feasible in such a case. Since a point with $c(x)> 0$ can still be observed as feasible in the noisy case, we perhaps need a modification to the CEI algorithm to account for this noise. \nAs an intermediate step, we have included a tolerance for the constraint, as we explained above in our response to weakness 1. \n\n$\\textbf{question 2}$ $\\textit{Convergence rate when constraints are correlated.}$\n\nR: Given its wide adoption in engineering publications, we would expect solid practical performance for CEI even when the conditional independence is violated.\nIn terms of theoretical properties, we share some of our current understanding. \n\nWe expect the simple regret bound to worsen given that the assumption does not accurately capture the relationship between constraints. \nMoreover, we speculate that a different simple regret bound is possible if we can quantify the correlation mathematically. \n\nWe provide an intuitive example below. \nConsider two identical constraints $c_1(x)\\leq 0$ and $c_2(x)=c_1(x)\\leq 0$. \nRecall that the probability of feasibility (PoF) is $p_1(x)=\\Phi(\\frac{-\\mu_t^{c_1}(x)}{\\sigma_t^{c_1}(x)})<1$\nmultiplying $p_2(x)=\\Phi(\\frac{-\\mu_t^{c_2}(x)}{\\sigma_t^{c_2}(x)})<1$. Thus, at a feasible point $x$, CEI would underestimate its probability of feasibility, which if modeled correctly would just be $p_1(x)$ instead of $p_1(x)p_2(x)$, especially initially. However, as the GP surrogate models of the constraints become more accurate, $p_1(x)$ and $p_2(x)$ both approach $1$ at a feasible point and its CEI value increases.\nTherefore, we anticipate the convergence of simple regret to hold but the upper bound to be worse. \n\nFinally, since the convergence rates are dominated by the maximum information gain of the objective, thanks to the multiplicative structure of CEI, it is possible that the convergernce rate itself could remain similar. \n\n[1] S. Ariafar, J. Coll-Font, D. Brooks, and J. Dy. ADMMBO: Bayesian optimization with unknown constraints using ADMM. Journal of Machine Learning Research, 20(123):1–26, 2019.\n\n[2] J. R. Gardner, M. J. Kusner, Z. Xu, K. Q. Weinberger, and J. P. Cunningham. Bayesian optimization with inequality constraints. In Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32, ICML’14, pages II–937–II–945."}, {"review_id": "Dl6eLvkqIP", "reviewer": "Reviewer_3QQu", "summary": "This paper considers the constrained Bayesian optimization framework where one desires to minimize the function $f(x)$ is subject to the constraint $c(x) \\leq 0$, where both are black box functions. The expected improvement algorithm, based on a Gaussian process model, is a celebrated algorithm in the unconstrained setting. The constrained expected improvement (CEI) algorithm extends this by including a term in the expected improvement that accounts for the feasibility $c(x) \\leq 0$. This paper presents, to my knowledge, first convergence guarantees or regret bounds for the CEI algorithm. Pacifically, in both a frequency setting where are the functions are assumed to come from an RKHS, and also an amazing setting where they are assumes sampled from the Gaussen process, the authors prove appropriate convergence rates of the regret, which extends the results in the unconstrained case. The authors also specialize these results to the commonly used squared exponential and Matérn kernels, and present some numerics to show convergence of the regret.", "questions": "1. Please see my question/comment on Weakness 1 above.\n2. Please see my question/comment on Weakness 2 above.\n3. Starting at the beginning of Section 2.1, there are a few instances of subscript $k_f$. Is this a typo? Should it be $k^f$?\n4. Why do you refer to the regret as \"simple\"?\n5. Theorem 3.7 seems more like a Corollary of Theorem 3.4 or is my understanding wrong? I guess Thm 3.4 is a generic result for all kernels, Thm 3.7 is its specialization to SE and Matérn kernels, and Thm 3.8 is a strengthening that uses the special structure of SE and Matérn kernels. \n6. Line 217:  Should Theorem 3.8 be Theorem 3.4?\n7. In Section 3.2, is the probability $\\delta$ over both sampling of $f$ and $c$? Is this probability affected or does it somehow affect the results more when you have more than 1 constraint?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Assessment:\nIn my view this is a moderately high quality submission in its current state. The results are technically sound. However, there are perhaps a few gaps in the results that make the paper a bit less mature than ideal (please see my detailed comments/questions below) in its current form. These might be able to be addressed in the rebuttal period. Although I did not read the appendix in detail, the claims appear well supported by extensive proofs. The paper is also written and organized OK; it clearly articulates the main ideas and results but the grammar and style could be improved somewhat throughout.\n\nStrengths:\n1. The results of this paper are significant, interesting, and have potential for impact. I like the topic, as I think Bayesian optimization is becoming more and more popular and important, both in theory and practice. Convergence rates for important Bayesian optimization algorithms, like CEI, is therefore fundamental and important.\n2. It is very good that this paper provides precise convergence rates for the regret, that all of the constants are explicitly spelled out, and that the arguments are outlined. I quite appreciate these level of transparency in the results.\n3. I am not the most well versed in the closely related recent literature. However, to the best of my knowledge, there are no overlapping works in the literature and this work appears to present original new insights, which I think will be valuable.\n\nWeaknesses:\nTo me the weaknesses concern two aspects of the bounds. These weaknesses are the main reasons for my current values of the Quality and Overall Score below, both of which could possibly be improved in the rebuttal. I list them below in my view on order of importance.\n\n1. I understand your rationale for defining regret as you do, but I wonder if by doing so you are being ``overly strict\" in the requirements of feasibility, leading to perhaps overly conservative bounds. What I mean is that, while the CEI expected improvement criteria is somewhat symmetric in how it multiples the constraint and objective criteria, your analysis is not. Instead, you require to only consider those points $x_t$ that actually are feasible with $c(x_t)$. As a result, many points may be thrown away. Furthermore, I think this manifests in the bound in the term $1/\\Phi(-B_c)$, which only gets worse as a product of multiple terms with multiple constraints (Remark 3.15). Is it possible to have a more \"parameterized\" version of a bound that might allow small violations in constraints $c(x_t) \\leq \\epsilon$ at the benefit of rejecting less points? I can imagine scenarios where decision-makers might be OK with this. And you can also recover your original bound by setting $\\epsilon = 0$. I am very curious to know your thoughts and if this approach is feasible, as I think it would improve the bounds a lot.\n2. To my understanding, your bounds implicitly involve a well-specified assumption where the kernel in Assumption 3.3/3.10 is the same as the kernel in the GP model in the algorithm; is this correct? If so, at the very least I think this must be acknowledged up front as a limitation of the current analysis. It is also of course interesting to see if such assumptions can be relaxed, but that might be beyond the scope of this current submission.\n3. I furthermore have several other questions below, which I don't inherently view as weaknesses per se, but I would appreciate to see addressed.", "was_revised": true, "final_justification": "The authors have strongly addressed my major weaknesses from the initial review. In particular, new theoretical bounds that allow for constraint violations are an excellent addition to the paper. As such, I have raised my score from 3 to 5.", "rebuttal": "We first want to thank the reviewer for the insightful comments and suggestions. We hope to address these concerns below.\n\n$\\textbf{weakness 1}$ $\\textit{Strict point selection and constraint tolerance.}$\n\nR: We greatly appreciate the reviewer's suggestion and we are happy to report that we have performed the analysis that includes constraint tolerance $\\epsilon$. The simple regret bound is affected by $\\epsilon$ and should lead to \n $1/\\Phi(\\epsilon-B_c)$ in place of $1/\\Phi(-B_c)$, which is an improvement.  The convergence rate remains similar since it is dominated by the maximum information gain of $f$.  \n\nMoreover, we can proceed further regarding the term $1/\\Phi(\\epsilon-B_c)$, which strongly relates to reviewer's thought that the bounds are too conservative. In our analysis, with the inclusion of $\\epsilon$, we in fact are able to reach the bound with $1/\\Phi(\\frac{\\epsilon}{\\sigma_{t_k}^c(x^*)}-B_c)$. \n\nThis comes from the confidence interval of $c$ at $t_k$ and $x^* $ and $c(x^* )\\leq 0$.\n\nRecall that $x^* $ is an optimal solution. As CEI gets closer to a solution $x^* $, we should have $\\frac{\\epsilon}{\\sigma_{t_k}^c(x^* )}\\to \\infty$ for $\\epsilon>0$. That is, this coefficient $1/\\Phi(\\frac{\\epsilon}{\\sigma_{t_k}^c(x^*)}-B_c)$ is time varying and tends to 1, thereby resolving the reviewer's concern about how large $1/\\Phi(-B_c)$ can become. From here, we use $\\sigma_{t_k}(x)\\leq 1$ to get $1/\\Phi(\\epsilon-B_c)$. \n\nWe can opt to keep  $1/\\Phi(\\frac{\\epsilon}{\\sigma_{t_k}^c(x^* )}-B_c)$ in the bound, but $\\sigma_{t_k}^c(x^* )$ is uncommon in a regret bound. \nIdeally, we can write an upper bound for $\\sigma_{t_k}^c(x^* )$ and use it in the simple regret bound. However, providing a bound or a rate for $\\sigma_{t_k}^c(x^* )$ is very challenging. To our best knowledge, such an upper bound for $\\sigma_{t_k} (x^* )$ in unconstrained EI is not available. Therefore, we use the rather relaxed bound $\\sigma_{t_k}^c(x^* ) \\leq 1$ and $1/\\Phi(\\epsilon-B_c)$. We have added a remark how this term in fact decreases with $t$. An upper bound bound on $\\sigma_{t_k}^c(x^* )$ is a technical challenge we can purse in the future.\n\nWe have added the newly derived results to the revised paper. Indeed, a constraint tolerance is standard in both constrained BO algorithms [1] and general gradient-based optimization, $\\textit{e.g.}$, Ipopt [2]. \nWe believe this added tolerance could also help make the CEI algorithm more robust when there is small noise in the observation of the constraints. \n\n$\\textbf{weakness 2}$ $\\textit{Smoothness assumption.}$\n\nR:Yes, the kernel in Assumption 3.3/3.10 is the same as the kernel in the GP model in the algorithm. We acknowledge this as a limitation of our analysis and have clarified it more explicitly in the paper. To the best of our knowledge, this is a standard assumption in the existing literature.\n\nRelaxing these assumptions has been a topic of interest to us, where relevant papers include [3].  To maintain the confidence intervals between the GP models and the functions $f$ and $c$, we think some kind of quantification of distance is needed between the RKHS spaces of these functions and the models. One premature thought we have had is to connect the smoothness assumptions of $f$ with the common assumptions used in the gradient-based optimization literature. For instance, growth conditions have led to improvement of regret bounds [4]. \n\n$\\textbf{Question 3}$ $\\textit{A typo.}$\n\nR: Yes. Thank you for pointing out the typos and we have fixed them all.\n\n$\\textbf{Question 4}$ $\\textit{Simple regret name.}$\n\nR: We called it simple because in the unconstrained case where every sample is feasible, the regret would reduce to the standard simple regret that is widely adopted in the BO literature.\n\n$\\textbf{Question 5}$ $\\textit{Theorem should be corollary.}$\n\nR:Yes the reviewer is correct. We use theorem for both 3.4 and 3.7 because 3.4 is an upper bound and 3.7 is the convergence rate. Both can be considered theorem-level results and they are often presented together in one theorem. However, in our case, we deliver two different rates in Theorem 3.7 and 3.8 using different techniques. That is the reason why 3.4 is separated from 3.7 and 3.8 for clarity of presentation. Following your suggestion, we have changed Theorem 3.7 to a Corollary.\n\n\n$\\textbf{Question 6}$ $\\textit{Another typo.}$\n\nR: Yes the reviewer is correct. We have corrected it.\n\n$\\textbf{Question 7}$ $\\textit{Probability of multiple constraints.}$\n\nR: Yes it is the probability concerning both $f$ and $c$. And yes increasing the number of constraints would change the constant $6$ in $\\beta$. For instance, if we have $2$ constraints and want to maintain equal probability of confidence intervals on $f$, $c_1$ and $c_2$, then we should set $\\beta=2\\log(8c_{\\alpha}/\\delta)$. Consequently, this would not change the convergence rate. \n\n[1] S. Ariafar, J. Coll-Font, D. Brooks, and J. Dy. ADMMBO: Bayesian optimization with unknown\nconstraints using ADMM. Journal of Machine Learning Research, 20(123):1–26, 2019.\n\n[2] A. Wächter and L.T. Biegler. On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Mathematical Programming, 106(1):25–57, 2006\n\n[3] I. Bogunovic, A. Krause  Misspecified gaussian process bandit optimization. Advances in neural information processing systems. 2021;34:3004-15.\n\n[4] S Iwazaki, Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization, arXiv:2506.01393, 2025•arxiv.org"}]

Author rebuttal:

Meta-review: [DRAFT NOTES]

Shows convergence rates for constrained expected improvement when the objective function is in an RKHS and with high probability when the objective function is drawn from a Gaussian process.

Strengths
- Significance and novelty --- this the first theoretical convergence rate for an important algorithm
- Difficulty of proving the result
- Clarity

Weakness
- Only handles noise-free
- Assumes first point is feasible

I recommend acceptance and a highlight poster because of the significance of this work. This is an old problem that many people have tried to solve.
Decision: Accept (spotlight)