Finding Interior Optimum of Black-box Constrained Objective with Bayesian Optimization

Venue: NeurIPS_cc_2024_Workshop_BDU
Published: 2024-09-06 07:55:09

Abstract: Optimizing objectives under constraints, where both the objectives and constraints are black box functions, is a common scenario in real-world applications such as the design of medical therapies, industrial process optimization, and hyperparameter optimization. One popular approach to handle these complex scenarios is Bayesian Optimization (BO). However, when it comes to the theoretical understanding of constrained Bayesian optimization (CBO), the existing framework often relies on heuristics, approximations, or relaxation of objectives and, therefore, lacks the same level of theoretical guarantees as in canonical BO. In this paper, we exclude the boundary candidates that could be compromised by noise perturbation and aim to find the interior optimum of the black-box-constrained objective. We rely on the insight that optimizing the objective and learning the constraints can both help identify the high-confidence regions of interest (ROI) that potentially contain the interior optimum. We propose an efficient CBO framework that intersects the ROIs identified from each aspect on a discretized search space to determine the general ROI. Then, on the ROI, we optimize the acquisition functions, balancing the learning of the constraints and the optimization of the objective. We showcase the efficiency and robustness of our proposed CBO framework through the high probability regret bounds for the algorithm and extensive empirical evidence.

Main paper: 
 introduction: 
 Bayesian optimization (BO) has been extensively studied over the past few decades as a powerful framework for addressing expensive black-box optimization tasks in machine learning, engineering, and science. In many real-world applications, these optimization tasks often involve black-box constraints that are costly to evaluate Digabel and Wild [2015] . Examples include choosing from a plethora of untested medical therapies under safety constraints [Sui et al., 2015] ; determining optimal pumping rates in hydrology to minimize operational costs under constraints on plume boundaries [Gramacy et al., 2016] ; or tuning hyperparameters of a neural network under memory constraints [Gelbart et al., 2014] . It is common to model constraints analogously to the objectives via Gaussian processes (GP) and then utilize an acquisition function to trade off the learning and optimization to decide subsequent query points.Recently, significant advancements have been made in several directions to address constrained BO (CBO). For instance, extended Expected Improvement approaches [Bernardo et al., 2011 , Gelbart et al., 2014 , Gardner et al., 2014 , Zhang et al., 2021 , Bachoc et al., 2020] learn the constraints passively and calibrate the acquisition with feasibility. The augmented lagrangian (AL) methods [Gramacy et al., 2016 , Picheny et al., 2016 , Ariafar et al., 2019] convert constrained optimization into unconstrained optimization with additional hyperparameters. The entropy-based methods [Takeno et al., 2022] optimize the lower bound of the mutual information concerning the underlying optimum within the feasible region.In this paper, we propose a novel framework that integrates active learning for level-set estimation (AL-LSE) [Gotovos et al., 2013 , Nguyen et al., 2021] with BO for constrained Bayesian optimization. Our approach leverages the theoretical advantages of both paradigms, allowing for a rigorous performance analysis of the CBO method. A brief illustration of the framework design is shown in figure 2 . The subsequent sections of this paper are structured as follows. First, we formally state the CBO problem and discuss the definition of a probabilistic regret as a performance metric that enables rigorous performance analysis. Following the problem statement, we propose the novel CBO framework, offer the corresponding performance analysis, and provide empirical evidence for the efficacy of the proposed algorithm. Finally, we reflect on the key takeaways of our framework and discuss its potential implications for future work. 
problem statement: 
 This section introduces a few useful notations and formalizes the problem. Consider a compact search space X ⊆ R d . We aim to find a maximizer x * ∈ arg max x∈X f (x) of a black-box function f : X → R, subject to M black-box constraints C m (x) (m ∈ M = {1, 2, 3, ..., M }) such that each constraint is satisfied by staying above its corresponding threshold h m .For simplicity and without loss of generality, we let all h m = 0. Thus, formally, our goal can be formulated as finding the interior optimum:max x∈X f (x) s.t. C m (x) > 0, ∀m ∈ MWe maintain a Gaussian process (GP) as the surrogate model for each black-box function, pick a pointx t ∈ X at iteration t by maximizing the acquisition function α : X → R, and observe the function values perturbed by additive noise: y f,t = f (x t ) + ϵ and y Cm,t = C m (x t ) + ϵ, with ϵ ∼ N (0, σ 2 ) being i.i.d. Gaussian noise.The definition of reward plays an important role in analyzing online learning algorithms. Throughout the rest of the paper, we define the reward of CBO as the following and defer the detailed discussion of alternative reward choices to Appendix E.r(x t ) = y f,t if I(y Cm(xt) ≥ 0) ∀m ∈ M -inf o.w.(1)We want to locate the global maximizer efficiently x * = arg max x∈X,∀m∈M,Cm(x)>0f (x)3 The COBAR AlgorithmWe start by introducing necessary notions from active learning for level-set estimation, followed by a detailed description of our proposed algorithm. The pseudocode and additional discussion are available in Appendix H. 
active learning for level-set estimation: 
 We follow the common practice and assume the objective and each unknown constraint is sampled from a corresponding independent Gaussian process (GP) [Hernández-Lobato et al., 2015 , Gelbart et al., 2014 , Gotovos et al., 2013] to treat the epistemic uncertainty. We could derive pointwise confidence interval estimation with the GP for each black-box function. We define the upper confidence bound UCB t (x) ≜ µ t-1 (x) + β 1/2 t σ t-1 (x) and lower confidence boundLCB t (x) ≜ µ t-1 (x) -β 1/2 t σ t-1 (x), where σ t-1 (x) = k t-1 (x, x) 1/2 and β t acts as a scaling factor corresponding to certain confidence.For each unknown constraint C m , we follow the notations from Gotovos et al. [2013] and define the superlevel-set to be the areas that meet the constraint C m with high confidence S Cm,t ≜ {x ∈ X | LCB Cm,t (x) > 0}. We define the sublevel-set to be the areas that do not meet the constraint C m with high confidence L Cm,t ≜ {x ∈ X | UCB Cm,t (x) < 0}, and the undecided set is defined as U Cm,t ≜ {x ∈ X | UCB Cm,t (x) ≥ 0, LCB Cm,t (x) ≤ 0}, where the points remain to be classified.In the CBO setting, we only care about the superlevel-set S Cm,t and undecided-set U Cm,t , where the global optimum is likely to lie in. Hence, we define the region of interest for each constraint function C m as XCm,t ≜ S Cm,t ∪ U Cm,t = {x ∈ X | UCB Cm,t (x) ≥ 0}. Similarly, for the objective function, though there is no pre-specified threshold, we could use the maximum of LCB f (x) on theintersection of superlevel-set S C,t ≜ M m S Cm,t LCB f,t,max ≜ max x∈S C,t LCB f,t (x), if S C,t ̸ = ∅ -∞, o.w.as the high confidence threshold for the UCB f,t (x) to identify a region of interest for the optimization of the objective. Given that UCB f,t (x * ) ≥ f * ≥ f (x) ≥ LCB f,t (x)EQUATIONAcquisition function for optimizing the objective To optimize the unknown objective f when Xt is established, we can employ the following acquisition function1 EQUATIONAt given t, to efficiently optimize the black-box f we evaluate the pointx t = arg max x∈ Xt α f,t (x).Since at a given t, when LCB f,t,max is constant, the acquisition function is equivalent to UCB f,t (x).Acquisition function for learning the constraints When we merely focus on identifying the feasible region defined by a certain unknown constraint C k , we could apply the following active learning acquisition function.EQUATIONAt given t, we evaluate the point x t = arg max x∈U Cm,t ∩ Xt α Cm,t (x) to efficiently identify the feasible region defined by C m . Note that the acquisition function α Cm,t (x) is not maximized on the full XCm,t , but only on U Cm,t ∩ Xt . The active learning on the superlevel-set S Cm,t ∩ Xt doesn't contribute to identifying the corresponding feasible region. We also illustrate the detailed procedure on a 1D toy example in figure 3 of Appendix A.In the following, we show that we could bound the simple regret of COBAR after sufficient rounds.Concretely, in Theorem 1, we provide an upper bound on the width of the confidence interval for the global optimum f * = f (x * ). We defer additional results and proofs to Appendix B 2 . The input dimensionality, the number of constraints, and the approximate portion of the feasible region in the whole search space for each task are denoted on the titles. We run the algorithms on each task for at least 15 independent trials. The curves show the average simple regret after standardization, while the shaded area denotes the 95% confidence interval through the optimization.Theorem 1. Under the proper assumptions, with a constant β = 2 log( 2(M +1)| D|T δ) and the acquisition function from Algorithm 2, there exists anϵ f ≤ ϵ C , such that after at most T ≥ β γ T C1 ϵ 2 f iterations, we have P [|CI f * ,T | ≤ ϵ f , f * ∈ CI f * ,T ] ≥ 1 -δ Here, C 1 = 8/ log(1 + σ -2 ). 
experiments: 
 We empirically study the performance of COBAR against three baselines, including (1) cEI, the We abstain from comparison against Augmented-Lagrangian methods, following the practice of Takeno et al. [2022] , as past studies have illustrated its inferior performance against sampling methods [Eriksson and Poloczek, 2021] or information-based methods [Takeno et al., 2022 , Hernández-Lobato et al., 2014] . We defer the comparison against CONFIG Xu et al. [2023] to Appendix G, due to the difference in objective and a resulting instability on our benchmarks. We compare COBAR against the aforementioned baselines across six CBO tasks. The first two synthetic CBO tasks are constructed from conventional BO benchmark tasks [Balandat et al., 2020] . Among the other four real-world CBO tasks, the first three are extracted from Tanabe and Ishibuchi [2020] , offering a broad selection of multi-objective multi-constraints optimization tasks. The fourth one is a 32-dimensional optimization task extracted from the UCI Machine Learning repository [mis, 2019] . Further details about the datasets are available in Appendix F. 
conclusion: 
 Bayesian optimization with unknown constraints poses challenges in the adaptive tradeoff between optimizing the unknown objective and learning the constraints. We introduce COBAR, which is backed by rigorous theoretical guarantees, to efficiently address constrained Bayesian optimization.Our key insights include: (1) the ROIs determined through adaptive level-set estimation can congregate and contribute to the overall Bayesian optimization task; (2) acquisition functions based on independent GPs can be unified in a principled way. Through extensive experiments, we validate the efficacy and robustness of our proposed method across various tasks finding the interior optimum.  
 
 Appendix: We put the illustration of the pipeline of proposed algorithm COBAR here. Each time, the algorithm maintains the model, maximizes the general acquisition function to pick the candidate to evaluate, and then updates the model with the new observation. In the Algorithm section, we will elaborate on the filtered gray gap in the acquisition.We put the illustration of a 1D Toy Example in figure 3 . The following two rows show the GP for f , the region of interest Xf , and the corresponding acquisition function α f,t (x) defined in equation 3. We show that after identifying S C , we could define the threshold for ROI identification of f accordingly. The bottom row demonstrates that the general ROI X as defined in equation 2 is identified by taking the intersection ROI for f and C. The general acquisition function is defined as the maximum of the acquisition for f and C and is maximized on the X. The scaling and length scale of the GPs are learned via maximum likelihood estimation.We first state a few assumptions that provide insights into the convergence properties of COBAR.The first one follows Srinivas et al. [2009] as a standard assumption for BO.Assumption 1. The objective and constraints are sampled from independent Gaussian processes.Formally, for all t < T and x ∈ X, f (x) is a sample from GP f,t , and C m (x) is a sample from GP Cm,t , for all m ∈ M.Assumption 2. A global optimum exists within the feasible region. The distance between this global optimum and the boundaries of the feasible regions is uniformly bounded below by ϵ C . Morespecifically, for all m ∈ M, ∃ϵ m > 0 such that C m (x * ) > ϵ m , then it holds that C m (x * ) > ϵ C = min m∈M ϵ m .Assumption 3. Given a proper choice of β t that is non-increasing, the confidence intervals are consistent. Concretely,∀t 1 < t 2 < T and x ∈ X, if β t1 ≥ β t2 , then UCB t1 (x) ≥ UCB t2 (x) and LCB t1 (x) ≤ LCB t2 (x).This is a mild assumption as long as β t is non-increasing, given recent work by Koepernik and Pfaff [2021] showing that if the kernel is continuous and the sequence of sampling points lies sufficiently dense, the variance of the posterior GP converges to zero almost surely monotonically if the function is in metric space. If the assumption is violated, the technique of taking the intersection of all historical confidence intervals introduced by Gotovos et al. [2013] could similarly guarantee a monotonically shrinking confidence interval. That is, when∃t 1 < t 2 < T, x ∈ X, if we have UCB t1 (x) < UCB t2 (x) or LCB t1 (x) > LCB t2 (x), we let UCB t2 (x) = UCB t1 (x) or LCB t2 (x) = LCB t1 (x)to guarantee the monotonocity. To allow for a plug-in of the intersection technique, and without loss of accuracy, we keep using the notation UCB and LCB without further parsing the value in the following discussion of algorithm design and theoretical analysis. The cost of violating the Assumption 3 has been studied in corollary 3 by Zhang et al. [2023] . We refrain from repeating the analysis here.The following lemma justifies the definition of the regions(s) of interest Xt defined in equation 2. For clarity, we denote D Xt = D ∩ Xt , andCI f * ,t = [max x∈ D Xt LCB t (x), max x∈ D Xt UCB t (x)].Lemma 1. Under the assumptions above, the regions of interest Xt , as defined in equation 2, contain the global optimum with high probability. Formally, for all δ ∈ (0, 1), T ≥ t ≥ 1, and any finite discretization D of X that contains the optimumx * = arg max x∈X f (x) where C m (x * ) > ϵ C for all m ∈ M and β t = 2 log(2(M +1)| D|π t /δ) with T ≥t≥1 π -1 t = 1, we have P x * ∈ D Xt ≥ 1-δ.To guarantee β t to be non-increasing, we could let π t = T and thereforeβ = 2 log( 2(M +1)| D|T δ) is a constant. The lemma shows that with proper choice of prior and β, the Xf,t remains nonempty during optimization.Subsequently, let's define the maximum information gain about function f after T rounds:EQUATIONProof. With probability at least1 -1/2δ, ∀x ∈ D, ∀T ≥ t ≥ 1, ∀g ∈ {f } ∪ {C m } m∈M , |g(x) -µ g,t-1 (x)| ≤ β 1/2 t σ g,t-1 (x)Note that we also take the union bound on g ∈ {f } ∪ {C m } m∈M . This is similarly derived as lemma 5.1 of Srinivas et al. [2009] or lemma 1 of Zhang et al. [2023] .Different from previous proofs, we do not require the lemma to hold for ∀t ≥ 1. Instead, we require it to hold for ∀T ≥ t ≥ 1. This alleviates the need of the convergence of the series t≥1 π -1 t = 1 to T t≥1 π -1 t = 1 when taking the union bound. Specifically, we could set π t = T , which essentiallymakes β t = 2 log( 2(M +1)| D|T δ) a constant. Hence, we use the β in the following instead of β t as traditionally used to highlight this difference.First, by definitionS C,t ≜ M m S Cm,t , we have ∀t ≤ T, x ∈ D ∩ S C,t , ∀m ∈ M P [C m (x) ≥ LCB Cm,t (x) > 0] ≥ 1 -1/2δmeaning with probability at 1 -δ, x lies in the feasible region. At the same time, we have, ∀t ≤ T , ∀m ∈ M, given C m (x) > 0P [UCB f,t (x * ) ≥ f (x * ) ≥ f (x) ≥ LCB f,t (x) ] ≥ 1 -1/2δGiven the mutual independency between the objective f and the constraints C m , and by the definition of the threshold LCB f,t,max , we have ∀t ≤ T , when ∃x ∈ D ∩ S C,t ,P [UCB f,t (x * ) > LCB f,t,max ] ≥ 1 -δ Note when D ∩ S C,t = ∅, LCB f,t,max = -∞, we have P [UCB f,t (x * ) > LCB f,t,max ] = 1.In summary, we've shown that with probability at least 1 -δ,x * ∈ D ∩ Xf,t . Next, by the definition of x * = arg max x∈X f (x) s.t. C m (x * ) > ϵ C we have ∀t ≤ T, ∀m ∈ M P [UCB Cm,t (x * ) ≥ C m (x * ) > 0] ≥ 1 -1/2δ meaning with probability at least 1 -1/2δ, x * ∈ D ∩ XCm,t . And in general, we have ∀t ≤ T, ∀m ∈ M P x * ∈ D ∩ Xt ≥ 1 -δ B.3 Proof of Theorem 1The following lemmas show that the maximum of the acquisition functions equation 3 and 4 are both bounded after sufficient evaluations.Lemma 2. Under the conditions assumed in Theorem 1 except for Assumption 2, let α t = max g∈G α g,t (x g,t ) as in Algorithm 2, withβ = 2 log( 2(M +1)| D|T δ ) that is a constant, after at most T ≥ β γ T C1 ϵ 2 f iterations, α T ≤ ϵ f Here C 1 = 8/ log(1 + σ -2 ). The inequation T ≥ β γ T C1ϵ 2 f has T on both side, which follows the convention in Gotovos et al. [2013] .Proof. We first unify the notation in the acquisition functions.∀T ≥ t ≥ 1, ∀g ∈ {C m } m∈M , when D Xt ∩ U g,t ̸ = ∅, max x∈ D Xt ∩Ug,t UCB g,t (x) -LCB g,t (x) ≤ α t (6) ∀T ≥ t ≥ 1, ∀g ∈ {C m } m∈M , when D Xt ∩ U Cm,t = ∅, let max x∈ D Xt ∩Ug,t UCB g,t (x) -LCB g,t (x) = 0 ≤ α t (7) ∀T ≥ t ≥ 1, g = f , when S C,t = ∅, we have max x∈ D Xt UCB f,t (x) -LCB f,t (x) ≤ α t (8) ∀T ≥ t ≥ 1, g = f , when S C,t ̸ = ∅, we have max x∈ D Xt UCB f,t (x) -LCB f,t.max ≤ α t (9)By lemma 5.1, 5.2 and 5.4 of Srinivas et al. [2009] , withβ = 2 log( 2(M +1)| D|T δ ), ∀g ∈ {f } ∪ {C m } m∈M and ∀x t ∈ D Xt ⊆ D, we have T t=1 (2β 1/2 σ g,t-1 , (x t )) 2 ≤ C 1 βγ g,T .By definition of α t , we have the followingT t=1 α 2 t ≤ T t=1 max g∈{f }∪{Cm} m∈M (2β 1/2 σ g,t-1 (x g,t )) 2 ≤ T t=1 g∈{f }∪{Cm} m∈M (2β 1/2 σ g,t-1 (x t )) 2 ≤ g∈{f }∪{Cm} m∈M C 1 βγ g,T = C 1 β γ TThe last line holds due to the definition in equation 5. By Cauchy-Schwarz, we have1 T ( T t=1 α t ) 2 ≤ C 1 β γ T With Assumption 3, ∀g ∈ {C m } m∈M , ∀1 ≤ t 1 < t 2 ≤ T , ∀g ∈ {C m } m∈M , we have U g,t2 ⊆ U g,t1and Xt2 ⊆ Xt1 , and most importantly, α t2 ≤ α t1 . Thereforeα T ≤ 1 T T t=1 α t ≤ C 1 β γ T T As a result, after at most T ≥ β γ T C1 ϵ 2 f iterations, we have α T ≤ ϵ f .With Lemma 2, we could first prove that after adequately T rounds of evaluations such that ϵ f ≤ min m∈M ϵ m is sufficiently small, with certain probability, x * ∈ S C,T . Then LCB f,t,max ̸ = -∞, and therefore the width of[max x∈ D Xt LCB f,T (x), max x∈ D Xt UCB f,T (x)],which is a the high confidence interval of f * , is bounded by ϵ f .Proof. We first prove that after at mostT ≥ β γ T C1 ϵ 2 f iterations, P x * ∈ D Xt ∩ S C,T ≥ 1 -1/2δ.Given equation 6 and 7 and Lemma 2, we have ∀g ∈ {C m } m∈M ,max x∈ D XT ∩U g,T UCB g,T (x) -LCB g,T (x) ≤ ϵ f ≤ min m∈M ϵ m According to the definition of U g,T , ∀x ∈ D XT ∩ U g,T , ∀g ∈ {C m } m∈M UCB g,T (x) ≤ ϵ f + LCB g,T (x) ≤ ϵ f ≤ min m∈M ϵ mAccording to Assumption 2, and Lemma 1, ∀m ∈ M, we haveP UCB Cm,T (x * ) > max x∈ D Xt ∩U Cm,t UCB Cm,T (x) ≥ 1 -1/2δ Given = D XT ∩ S C,T = D Xt ∩ XC,T \ ∪ m∈M U Cm,T , when t = T , we have P x * ∈ D XT ∩ S C,T ≥ 1 -1/2δ (10) As a result P [LCB f,T,max ̸ = -∞] ≥ 1 -1/2δNext, we prove the upper bound for the width of the high-confidence interval of f * . Given that LCB f,T,max ̸ = -∞, we havemax x∈ D XT UCB f,T (x) -max x∈ D XT LCB f,T (x) ≤ max x∈ D XT UCB f,T (x) -LCB f,T,max ≤ α T ≤ ϵ fCombining it with the observation that with probability 1 -1/2δ, maxx∈ D XT LCB f,T (x) < f (x * ) ≤ max x∈ D XT UCB f,T (x)we attain the final result that afterT ≥ β γ T C1 ϵ 2 iterations, P [|CI f * ,T | ≤ ϵ, f * ∈ CI f * ,T ] ≥ 1 -δ B.4 Corollary 1One direct result of Theorem 1 is that if any point belongs to D that lies in the feasible set defined by the unknown constraints bears a suboptimal gap on the reward except for the global optimum, then after sufficient query, the algorithm will identify x * as the only point in the ROI. In that case, COBAR will only query x * and achieve zero regret afterward.Corollary 1. We assume the aforementioned conditions hold, and ∀x ∈ D, when ∀m ∈ M,C m (x) > 0, x ̸ = x * , it holds that ∃ϵ C ≥ 2ϵ f > 0, f * -f (x) > 2ϵ f .In addition, we useβ = 2 log( 2(M +1)| D|T δ) and the acquisition function from Algorithm 2. After at most t ≥ β γtC1 ϵ 2 f iterations, we haveP [R t = 0] ≥ 1 -δ.Here, C 1 = 8/ log(1 + σ -2 ) and t ≤ T .Proof. We simply need to show that after t ≥ β γtC1 ϵ 2 f iterations, with probability at least 1 -δ, x * is the only member in D Xt .Similar to Theorem 1, we haveP [|CI f * ,t | ≤ ϵ f , f * ∈ CI f * ,t ] ≥ 1 -δ. At the same time, given the proof of Lemma 2, we have ∀x ∈ D Xt , 2β 1/2 σ f,t-1 (x) ≤ ϵ f . Then if ∃x ̸ = x * and x ∈ D Xt , we have f * -f (x) > 2ϵ f , while P f * -f (x) ≤ |CI f * ,t | + UCB f,t (x) -LCB f,t (x) ≤ 2β 1/2 σ f,t-1 (x) + ϵ f ≤ 2ϵ f ≥ 1 -δThis contradiction means with probability at least 1 -δ, x * is the only member in D Xt , andx t = x * .As a result,P [R t = 0] ≥ 1 -δ, when T ≥ t ≥ β γtC1 ϵ 2 f .Similarly, if a group of suboptimal candidates lies in the feasible area and is sufficiently close to x * , then Assumption 2 also holds for those suboptimal points. In this condition, the algorithm achieves a sublinear cumulative regret after identifying this near-optimal region.Corollary 2. We assume the aforementioned conditions hold, and ∀x ∈ D, when ∀m ∈ M,C m (x) > 0, x ̸ = x * , ∃ϵ C ≥ ϵ f > 0, f * -f (x) ≤ 2ϵ f , it holds that ∀m ∈ M, C m (x) ≥ ϵ C . In addition, we use β = 2 log( 2(M +1)| D|T δ) and the acquisition function from Algorithm 2. After atmost t ′ ≥ β γ t ′ C1 ϵ 2 f iterations, we have, P T t=t ′ r(x * ) -r(x t ) ≤ (T -t ′ )βγ T C 1 ≥ 1 -δ.Here,C 1 = 8/ log(1 + σ -2 ) and t ′ ≤ T .Proof. We follow the same path as the proof of Corollary 1.Similar to Theorem 1, we haveP [|CI f * ,t | ≤ α t ≤ ϵ f , f * ∈ CI f * ,t ] ≥ 1 -δ. At the same time, given the proof of Lemma 2, we have ∀x ∈ D Xt , 2β 1/2 σ f,t-1 (x) ≤ α t ≤ ϵ f .Then ∀x ̸ = x * and x ∈ D Xt , we haveP [f * -f (x) ≤ |CI f * ,t | + UCB f,t (x) -LCB f,t (x) ≤ 2α t ≤ 2ϵ f ] ≥ 1 -δThen by assumption, ∀x ∈ D Xt , ∀m ∈ M, we have probability at least 1 -δ, C m (x) ≥ ϵ C , and hence x / ∈ U Cm,t . According to the algorithm, it regresses to GP-UCB by Srinivas et al. [2009] between t ′ and T .T t=t ′ (r(x * ) -r(x t )) 2 ≤ βC 1 (γ T -γ t ′ ) ≤ βC 1 γ T (1 -t ′ /T )By Cauchy-Schwarz, we haveT t=t ′ (r(x * ) -r(x t )) ≤ (T -t ′ ) T t=t ′ (r(x * ) -r(x t )) 2 ≤ (T -t ′ ) 2 T βC 1 γ T ≤ (T -t ′ )βC 1 γ T B.6 Corollary 3Following the path of proof for Theorem 1, with Lemma 2, we can show that the algorithm can identify infeasibility when all points in the search space violate at least one of the constraints at least Proof. We assume D XT ̸ = ∅ and prove by contradiction. Given equation 6 and 7 and Lemma 2, we have ∀g ∈ {C m } m∈M ,ϵ ′ C . Concretely, ∀x ∈ X, if it holds that ∃m ∈ M, C m (x) < -ϵ ′ C ,max x∈ D XT ∩U g,T UCB g,T (x) -LCB g,T (x) ≤ ϵ ′ CAccording to the definition of U g,T , ∀x ∈ D XT ∩ U g,T , ∀g ∈ {C m } m∈M , with probability at least 1 -1/2δ, we haveC m (x) ≤ UCB Cm,T (x) ≤ ϵ ′ C + LCB g,T (x) ≤ ϵ ′ C + C m (x) Then we have ∀x ∈ D XT ∩ U g,T , ∃m ∈ M P [C m (x) ≤ ϵ ′ C + C m (x) < 0] ≥ 1 -1/2δThis contradiction means ∀g ∈ {C m } m∈M , D XT ∩ U g,T = ∅ with probability as least 1 -1/2δ.According to the definition of S g,T , ∀x ∈D XT ∩ S g,T , ∀g ∈ {C m } m∈M LCB g,T (x) ≥ ϵ ′ C Then we have ∀x ∈ D XT ∩ S g,T , ∃g ∈ {C m } m∈M P [-ϵ ′ C ≥ C m (x) ≥ LCB g,T (x) ≥ ϵ ′ C ] ≥ 1 -1/2δ This contradiction means ∀g ∈ {C m } m∈M , D Xt ∩ S g,T = ∅ with probability as least 1 -1/2δ.Combining the above contradictions, we have at least when t = T ,P D XT = ∅ ≥ 1 -δ C Continuous Search Space C.1 Theoretical ResultsIn the following, we introduce the additional assumption that bounds the unknown functions' complexity when they are members of an RKHS space and enables the performance analysis when applying COBAR on continuous search space X instead of D.Assumption 4. The objective and constraints all lie in the RKHS H k corresponding to the kernel k(x, x ′ ), and the corresponding norm is bounded by B. Formally, f : X → R is a member of the RKHS of real-valued functions on X with kernel k, with RKHS norm ∥f ∥ k ≤ B. Similarly, C m : X → R is a member of the RKHS of real-valued functions on X with kernel k, with RKHS norm∥C m ∥ k ≤ B, for all m ∈ M.Then, we could derive similar results mapping from Lemma 1.Lemma 1. Under the assumptions above, the regions of interest Xt , as defined in equation 2, contain the global optimum with high probability. Formally, for all δ ∈ (0, 1), T ≥ t ≥ 1, and the search space X that contains the optimumx * = arg max x∈X f (x) where C m (x * ) > ϵ C for all m ∈ M and β 1/2 t = B + σ 2( γ T + 1 + ln(2(M + 1)/δ)), we have P x * ∈ Xt ≥ 1 -δ.Proof. Similar to theorem 2 of Chowdhury and Gopalan [2017] , with probability at least1 -1/2δ, ∀x ∈ D, ∀T ≥ t ≥ 1, ∀g ∈ {f } ∪ {C m } m∈M , |g(x) -µ g,t-1 (x)| ≤ β 1/2 t σ g,t-1 (x)Note that we also take the union bound on g ∈ {f } ∪ {C m } m∈M .C,t ≜ M m S Cm,t , we have ∀t ≤ T, x ∈ S C,t , ∀m ∈ M P [C m (x) ≥ LCB Cm,t (x) > 0] ≥ 1 -1/2δmeaning with probability at 1 -δ, x lies in the feasible region. At the same time, we have, ∀t ≤ T , ∀m ∈ M, given C m (x) > 0P [UCB f,t (x * ) ≥ f (x * ) ≥ f (x) ≥ LCB f,t (x) ] ≥ 1 -1/2δGiven the mutual independency between the objective f and the constraints C m , and by the definition of the threshold LCB f,t,max , we have ∀t ≤ T , when ∃x ∈ S C,t ,P [UCB f,t (x * ) > LCB f,t,max ] ≥ 1 -δ Note when S C,t = ∅, LCB f,t,max = -∞, we have P [UCB f,t (x * ) > LCB f,t,max ] = 1.In summary, we've shown that with probability at least 1 -δ, x * ∈ Xf,t .Next, by the definition ofx * = arg max x∈X f (x) s.t. C m (x * ) > ϵ C we have ∀t ≤ T, ∀m ∈ M P [UCB Cm,t (x * ) ≥ C m (x * ) > 0] ≥ 1 -1/2δmeaning with probability at least 1 -1/2δ, x * ∈ XCm,t . And in general, we have ∀t ≤ T, ∀m ∈ MP x * ∈ Xt ≥ 1 -δRemark 2. The proof of Lemma 1 substitutes the β in the proof of Lemma 1 and alleviates the need for a discretization D with the additional assumption on the complexity of the unknown functions in Assumption 4. Note the β 1/2 t = B + σ 2( γ T + 1 + ln(2(M + 1)/δ)), we have P x * ∈ Xt ≥ 1 -δ is larger than the original value in the theorem 2 of Chowdhury and Gopalan [2017] to make sure β t is the same for all ∀T ≥ t ≥ 1 and to guarantee a union bound on g ∈ {f } ∪ {C m } m∈M . In the following, since β t is constant, we substitute it with β.Then, we could trivially map the Theorem 1 when maximizing the acquisition functions on Xt instead of D Xt as in line 9 of Algorithm 2 and on Xt ∩ U Cm,t instead of D Xt ∩ U Cm,t as in line 8 of Algorithm 2. The proof would be identical to section B except for the different β and search space.Algorithm 1 COnstrained BO through Adaptive Region of Interest Acquisition on Continuous Space(COBAR-CS) 1: Input:Search space X, initial observation S 0 , horizon T , confidence factor δ, confidence coefficient β; 2: for t = 1 to T do 3:Update the posteriors of GP f,t and GP Cm,tIdentify ROIs Xt , and undecided sets U Cm,t 5:for m ∈ M do 6: if U Cm,t ̸ = ∅ then 7:Candidate for learning of each constraint:x Cm,t ← arg max x∈ Xt∩UC m,t α Cm,t (x) (4) 8: G ← G ∪ C m,t 9:Candidate for optimizing the objective:x f,t ← arg max x∈ Xt α f,t (x) as in equation 3 10: G ← G ∪ f 11:Maximize the acquisition from different aspects: g t ← arg max g∈G α g,t (x g,t )12:Pick the candidate to evaluate: x t ← x gt,tUpdate the observation set S t ← S t-1 ∪ {(x t , y f,t , {y Cm,t } m∈M )} Theorem 3. Under the aforementioned assumptions, with a constant β1/2 t ≜ β 1/2 = B + σ 2( γ T + 1 + ln(2(M + 1)/δ))and the acquisition function from Algorithm 1, there exists anϵ f ≤ ϵ C , such that after at most T ≥ β γ T C1 ϵ 2 f iterations, we have P [|CI f * ,T | ≤ ϵ f , f * ∈ CI f * ,T ] ≥ 1 -δ Here, C 1 = 8/ log(1 + σ -2 ).Aiming at a continuous search space demands additional consideration when implementing a practical ROI identification on the continuous search space or requires a better coverage by the discretization of the dense search space for COBAR in practice. This problem is more outstanding in high-dimensional tasks.Here, we briefly discuss potential remedies if we still resort to an efficient discretization. The random linear projection has been used for discretizing the search space to mitigate the dependency on the dimensionality while, with high probability, preserving the original geometry [Dasgupta, 1999 , Nayebi et al., 2019] . To efficiently discretize the dense search space for COBAR (in high-dimensional applications), one option is to apply the random projection and its reverse studied by Nayebi et al.[2019], which shows strong empirical performance when combined with other BO algorithms and offers the following theoretical guarantee.Definition 1. (ε-subspace embedding [Nayebi et al., 2019] ) Given a matrix V ∈ R D×d with orthonormal columns, an integer d ≤ D and an approximation parameter ε ∈ (0, 1), an ε-subspace ) Consider a Gaussian process that acts directly in the unknown active subspace of dimension d e with mean and variance functions µ(•), σ 2 (•). Let μ(•), σ2 (•) be their approximations using an ε-subspace embedding for the active subspace. Then we have for every x ∈ Xembedding for V is a map H : R d → R D such that ∀ x ∈ R d : (1 -ε)∥V x∥ 2 2 ≤ ∥HV x∥ 2 2 ≤ (1 + ε)∥V1. |µ(x) -μ(x)| ≤ 5ε∥x∥∥X -f ∥ 2. σ 2 (x) -σ2 (x) ≤ 12ε∥x∥ 2For a comprehensive survey on the treatments of high-dimensional search space for BO, we refer to the recent survey by Binois and Wycoff [2022] . Besides the random projection [Nayebi et al., 2019 , Wang et al., 2016 , Letham et al., 2020] , variable selection Hellsten et al. [2023] , tree-structure partition [Eriksson and Jankowiak, 2021] , and Markov Chain Monte Carlo sampling [Yi et al., 2024] on the search space could all be applied as plugins to improve the discretization efficiency for COBAR.We illustrate the effectiveness of integrating Hashing-enhanced Subspace BO (HeSBO) [Nayebi et al., 2019] into CBO algorithms. We construct the following 40-dimensional CBO task that makes any grid discretization containing a feasible candidate on the original embedding intractable.Ackley-40D-2C f (x) = 20 exp (-0.2 1/d d i x 2 i ) + exp (1/d d i cos(2πx i )) + 20 +exp(1), d = 5 where x ∈ [-5, 10] 40 . We construct two constraints to enforce a feasible area taking up less than 0.6% of the search space. The first constraint C 1 = 1 -(5 i x i ). The second constraint C 2 = 6 -( 5 i x 2 i ).We find that COBAR fails in the original search space [-5, 10] 40 due to the intractability of any discretization containing sufficient feasible candidates. We integrate HeSBO into all the tested CBO algorithms to allow the algorithms to process on a 5-dimensional embedding space [-1, 1] 5 . COBAR relies on a random sampling containing 200000 candidates. The simple regret curves are shown in figure 4 . Though the point-wise comparison of COBAR is not tractable in the original 40-dimensional search space, integrating HeSBO allows COBAR to optimize the high-dimensional CBO toy problem efficiently. Table 1 shows that COBAR could efficiently optimize the embedding space, benefited from the reduced dimensionality and the ROI identification that further reduces computation need dynamically.Here, we discuss the treatment and theoretical behavior when dealing with the boundary optimum.First, we extend the results in Theorem 1, when not assuming the Assumption 2 hold. We uniformly shift the constraints by a small amount ϵ C to satisfy Assumption 2 with the modified constraints. ) and the acquisition function from Algorithm 2, there exists anϵ f ≤ ϵ C , such that after at most T ≥ β γ T C1 ϵ 2 f iterations, we have P |CI f * ,T | ≤ ϵ f , f * ∈ CI f * ,T ≥ 1 -δ.Here, This Corollary 4 allows us to depict the width of the global optimum defined in the enlarged feasible region similarly. Since the optimum is defined in the enlarged area, it could be an upper bound of the global optimum defined in the original feasible region, including the feasible region boundaries. That isC 1 = 8/ log(1 + σ -2 ).f * ≥ arg max x∈X,∀m∈M,Cm(x)≥0 f (x)This allows us to extend further the Corollary 2 that depicts the partial cumulative regret after sufficient iterations and the upper bound of the violations.Corollary 5. Under the aforementioned assumptions and modifications, when ∀m ∈ M, C ′ m (x) > 0,x ̸ = x * , ∃ϵ C > ϵ ′ C ≥ ϵ f > 0, f * -f (x) ≤ 2ϵ f , it holds that ∀m ∈ M, C ′ m (x) ≥ ϵ ′ C . We use β = 2 log( 2(M +1)| D|T δ) and the acquisition function from Algorithm 2. After at most t′ ≥ β γ t ′ C1 ϵ ′2 f iterations, we have, P T t=t ′ r(x * ) -r(x t ) ≤ (T -t ′ )βγ T C 1 , ∀x ∈ D, C m (x t ) ≥ -ϵ C > 1 - δ. Here, C 1 = 8/ log(1 + σ -2 ) and t ′ ≤ T . Proof. First, we have ∀x ∈ D Xt , 2β 1/2 σ f,t-1 (x) ≤ α t ≤ ϵ f .Then ∀x ̸ = x * and x ∈ D Xt , we haveP f * -f (x) ≤ |CI f * ,t | + UCB f,t (x) -LCB f,t (x) ≤ 2α t ≤ 2ϵ f ≥ 1 -δThen by assumption, ∀x ∈ D Xt , ∀m ∈ M, we have probability at least1 -δ, C ′ m (x) ≥ ϵ ′ C . Hence we have both C m (x) ≥ ϵ C -ϵ ′ C and x / ∈ U C ′ m ,t .According to the algorithm, it regresses to GP-UCB by Srinivas et al. [2009] between t ′ and T . By Cauchy-Schwarz, we haveT t=t ′ (r(x * ) -r(x t )) ≤ T t=t ′ (r(x * ) -r(x t )) 2 ≤ βC 1 (γ T -γ t ′ ) ≤ βC 1 γ T (1 -t ′ /T )T t=t ′ (r(x * ) -r(x t )) ≤ (T -t ′ ) T t=t ′ (r(x * ) -r(x t )) 2 ≤ (T -t ′ ) 2 T βC 1 γ T ≤ (T -t ′ )βC 1 γ TNote that by enlarging the feasible region with ϵ C , we don't risk losing the feasible region to enable COBAR to identify both interior and boundary optimum. We don't change the definition of f * .Instead, we only leverage the modified running constraints and verify the feasibility with the original constraints. For the algorithms aiming at violation tolerant objectives like CONFIG [Xu et al., 2023] ,there is no similar guarantee with straightforward modification, e.g., adding small ϵ C to the threshold while not risking losing the feasible region. We denote the modified COBAR as COBAR-EPSILON.We include the corresponding comparison on the noise-free Ackley-10D-2C as exactly defined in Eriksson and Poloczek [2021] , where the feasible region is less than 2.2 * 10 -3 % of the whole search space, and the optimum lies on the boundary of feasible region by construction.As is shown in figure 5 , COBAR is initially outperformed by SCBO while converging to the nearoptimal area after the sufficient budget as SCBO. COBAR-EPSILON archives the best convergence throughout the optimization with the proposed minor tweak. In contrast, CONFIG fails to converge to the global optimum, possibly due to its tolerance of the constraints violation, and by definition, no reward is incurred for a point outside the feasible region.The definition of reward plays an important role in online machine learning performance analysis. In the CBO setting, one possible definition of constrained reward derived from the constraint nature is r(x) = f (x) m I Cm(x)≥hm when assuming the f (x) > 0. Considering both the aleatoric and epistemic uncertainty on the constraints, we could transform the problem into finding the maximizerarg max x∈X r(x) = arg max x∈X f (x) m P [Y Cm (x) ≥ h m ]Here Y Cm (x) denotes the observation of the constraint C m at x.The problem with this product reward, on the one hand, is that it is likely to incur a Pareto front if we regard the problem as a multi-objective optimization where the objectives are composed of f (x) andP [Y Cm (x) ≥ h m ].The multi-objective nature and resulting Pareto front indicate that the optimization could be more challenging to converge than the single-objective unconstrained BO problem, though the unique global optimum is not always expected there either. More critically, when the feasibility of reaching a certain threshold, we prefer to focus on optimizing the objective value rather than the product for the following reasons.Firstly, the marginal gain on improving feasibility by increasing the value of the constraint function drops after the feasibility reaches 0.5 assuming it follows a Gaussian. Especially in the tail region, improving the feasibility and then the product of feasibility and objective value by optimizing the constraint function is prohibitively difficult.Secondly, in most real-world scenarios except for certain applications that focus on feasibility (where the feasibility should be treated as another objective and make it in nature a multi-objective optimization), the actual marginal gain, in general, increases the feasibility decay faster than the increase of objective value. (e.g., when choosing between doubling the feasibility from 0.25 to 0.5 or doubling the objective value drop from 25 to 50, we probably favor the former as 0.25, meaning it is unlikely to happen. However, when choosing between increasing feasibility from .8 to .9 or increasing the objective drop from 80 to 90, there would be no such clear preference.) Then, the user would possibly favor the gain on the objective function after the feasibility reaches a certain level. Therefore, we propose the following reward for constrained optimization tasks according to this insight.Instead of defining the reward as the product of the objective value and feasibility, we have to look into the probabilistic constraints and distinguish the epistemic uncertainty and aleatoric uncertainty. EQUATIONNext, if the observation on the constraints is perturbed with a known Gaussian noise, namely Y Cm (x) ∼ N (C m (x), σ), we could deal with the aleatoric uncertainty with a user-specific confidence level for each constraint χ m ∈ (0, 1), ∀m ∈ M. Then we could turn I(Y Cm (x) ≥ h m ) into probabilistic constraints following the definiation proposed by Gelbart et al. [2014] andP [Y Cm (x) ≥ h m ] ≥ χ mto explicitly deal with the aleatoric uncertainty. With the percentage point function (PPF), we could transform the probabilistic constraints into a deterministic constraint I(C m (x) ≥ ĥm ) with ĥm = PPF(h m , σ, µ m ), meaning ĥ is the χ m percent point of a Gaussian distribution with h m and σ as its mean and standard deviation. Hence, we could unify the form of rewards of noise-free and noisy observation on the constraints with the user-specified confidence levels. For simplicity and without loss of generalization, we stick to the definition in equation 1 and let all ĥm = 0.In the benchmarks, we applied the deep Gaussian process [Wilson et al., 2016] . Here, we offer a more detailed discussion of the construction of the six CBO tasks studied in section 4.Converter-32D-3C This UCI dataset we use consists of positions and absorbed power outputs of wave energy converters (WECs) from the southern coast of Sydney. The applied converter model is a fully submerged three-tether converter called CETO. 16 WECs 2D-coordinates are placed and optimized in a size-constrained environment [mis, 2019] . The input is, therefore, 32 dimensional. We place three constraints on the tasks, including the absorbed power of the first two converters being above a certain threshold of 96000 and the general position being not too distant with the two-norm below 2000. The feasible region takes up approximately 27% of the whole search space.Here, we provide additional experiment results on COBAR.G.1 Different Portion of Feasible Region for Rastrigin-1D As is shown in figure 7 , the algorithm is robust to moderate values of β. Except from the Ackley β = 0.1 where the filtering of ROI is over-aggressive and traps the model on a certain locality when a very small number of candidates remain in ROI. We observe that certain β choices could be slightly better but don't impact the convergence and lack statistical significance. We believe the acquisitions in Eq. ( 4) and Eq. ( 3), together with the X identification when the models are well-fitted, contribute to this robustness. Different from conventional GP-UCB [Srinivas et al., 2009] , the acquisition functions are standardized with the (maximum) lower confidence bound. The search domains are filtered when historical observations suggest poor performance in nearby areas.We show the wall time of COBAR compared with the baselines in Though the objective is defined differently, we add additional baseline CONFIG from Xu et al. [2023] .The results are shown in figure 8 and figure 9 . We observe that COBAR outperforms or at least matches CONFIG in all the problems in our setting. Specifically, in the early stage of the Rastrigin-1D-1C task and through the Ackley-5D-2C, where the underlying objective is highly fluctuating, as is shown in figure 8 for Rastrigin-1D-1C, CONFIG fails to enter the feasible region consistently even after exhausting sufficient budget and gets stuck in learning the constraints passively.At the same time, we observe that on Converter-32D-3C, Vessel-4D-3C, and Spring-3D-6C, CONFIG generally matches the performance of COBAR. We hypothesize that in these applications, the constraint learning part of COBAR is not as beneficial as directly optimizing the underlying function is possibly feasible regions, as the unknown feasibility coincides with the optimality of the underlying objectives. Still, COBAR bears higher consistency in all the benchmarks, highlighting the efficiency and necessity of the adaptive trade-off of active learning and optimization in COBAR when assuming no reward is incurred outside the feasible region. This difference also highlights the necessity of actively learning the complex underlying constraints to guarantee a stable convergence to a feasible optimum.SVM-CBO [Antonio, 2021] offers a practicality-oriented solution. It uses the SVM to learn the feasibility bound to estimate the decision boundary efficiently. The challenge of analyzing the learning of SVM combined with the coverage-oriented first-phase acquisition function poses a challenge to regret analysis. In addition, SVM-CBO requires a specific split of feasibility identification and optimization within the feasible region and demands different performance metrics for evaluation.This split makes direct comparisons with COBAR, which is somewhat challenging and does not explicitly split the two processes. Nonetheless, we follow the practice in the paper that uses a 10:60:30 split for the random sampling, phase 1 and phase 2 of SVM-CBO, and report the simple regret. Table 3 shows the simple regret of the end of both phases of SVM-CBO. We emphasize the best simple regret achieved. The results demonstrate that COBAR ultimately outperforms or matches the best baseline in the end. for m ∈ M do 6: if U Cm,t ̸ = ∅ then 7:Candidate for learning of each constraint:x Cm,t ← arg max x∈ D Xt ∩U Cm,t α Cm,t (x) (4) 8: G ← G ∪ C m,t 9:Candidate for optimizing the objective: Maximize the acquisition from different aspects: g t ← arg max g∈G α g,t (x g,t )EQUATION12:Pick the candidate to evaluate: x t ← x gt,t 13:Update the observation set S t ← S t-1 ∪ {(x t , y f,t , {y Cm,t } m∈M )}For algorithm 2, {x gt,t } in line 11 are acquired in line 7 as x Cm,t or line 9 as x f,t , since G is composed of C m and f . Roughly speaking, we are taking arg max g,x , yet we avoid using such notation for two Here, we offer additional explanation and discussion over COBAR.Both the acquisition functions for optimizing the objective and active learning are confidence intervalbased, which reflects the uncertainty and is intrinsically comparable. With Assumption 1 that the black-box underlying functions are samples from the corresponding GPs specified by the kernels, we use the kernels to capture the scaling of the different unknowns. Our analysis does not assume that the kernels are the same, meaning that the theoretical results hold when the objective and constraints are of different scales. This analysis converts the algorithm's sensitivity to scale to the sensitivity to hyper-parameter misspecification. In our experiments, we report the results when following the standard practice of kernel learning [Rasmussen and Williams, 2006] for both the proposed algorithm and baselines, as is stated at the end of the caption of figure 6. In summary, the compatibility is guaranteed by the properly specified kernel. Recent advancements in self-correcting BO [Hvarfner et al., 2024] or BO with unknown hyperparameters [Berkenkamp et al., 2019] propose various methods to address the challenge.With regard to the practical concern over why the analysis does not require normalizing the different acquisition functions, the answer is threefold. First, since the correlation between the constraints and the objective is unknown, it is possible that the objective, in general, is of a smaller scale but bears the highest gradient near the boundary, meaning that the general scale of functions does not offer a guarantee to normalize the near-boundary uncertainties. Second, using the ROI to constrain the acquisition helps exclude the useless uncertainty reduction as the ROI considers both the objective and the constraints. If constraints dominate the COBAR acquisition, it suggests that the selected points remain likely to contain the global optimum as its objective does not have a high probability of being suboptimal. Such a query won't be wasted. A concrete example is illustrated in figure 3 .Third, since we are assuming a universal upper bound for each constraint, the scale difference could make certain constraints dominant in the ϵ m . This could be addressed through the normalization of observations given prior knowledge.I.2 Difference from Other Existing CBO Methods with No-regret GuaranteeWe briefly discuss the differences between COBAR and the previous theoretical results in CBO. Lu and Paulson [2022] addresses equality constraints for instantaneous penalty-based regret. However, the reward formulation is different. Lu and Paulson [2023] offers theoretical results on cumulative regret and violations. Yet, they assume querying points out of the feasible region still yields rewards and consider the violation separately.In general, we are unaware that the existing CBO analysis results lead to a similar guarantee as in our work when assuming querying infeasible points does not yield a reward. One key difference is that with the active learning component and feasibility assumption, we could guarantee to query a feasible point that bears a reward converging to optimal value with the desired confidence. In our specific reward formulation, we regard such a guarantee and, therefore, the contribution in algorithm design and analysis as sufficiently different from the previous work, even when only focusing on the coupled setting.It is possible that certain subsets discussed in section 3 could be empty at a certain t as a result of intersections. However, according to the assumptions in section 3.4 and Lemma 1, the properly chosen β does not result in over-aggressive filtering with high probability. From this perspective, ROI X is soundly defined. COBAR is also robust to empty U Cm,t . As shown in algorithm 2, the domain where the acquisition functions defined in equation 4 and equation 3 are maximized allow empty U Cm,t for COBAR to proceed.The limitation of COBAR includes (1) the inefficiency of identifying the ROIs due to the pointwise comparison in current implementation relying on discretization; (2) the lack of discussion over correlated unknowns, which are common in practice (e.g., two constraints are actually lower bound and upper bound of the same value). Though we briefly discuss and study corresponding scenarios, we expect the following work could improve the algorithm's effectiveness and the comprehensiveness of corresponding analysis accordingly.Same criterion has been studied under the unconstrained setting[Zhang et al.,2023].2 With additional assumptions on the regularization of the underlying function, we derive the analogous analysis on continuous search space in Appendix C. 



Reviews: review: title: title: Solid theoretical foundation, but the experimental results require further explanation and commentary.
main_review: main_review: This paper presents COBAR, a novel algorithm for Constrained Bayesian Optimization (CBO) that effectively identifies the interior optimum of a black-box objective function under multiple black-box constraints. The primary contribution of the paper is the introduction of a region of interest (ROI) identification framework that refines the search space using Gaussian Process (GP) models, which combine active learning for level-set estimation to handle constraints and optimize the objective. The authors provide a solid theoretical foundation with thorough proofs of their theorems, although some unusual trends in the experiments warrant further explanation.

**Questions for the Authors**

- Please correct the typos (e.g., lower/upper case issues) in the reference section.

- The Bayesian Optimization (BO) framework relies heavily on Gaussian Processes (GPs) for modeling both the objective and the constraints. How does the method perform when the GP is a poor fit for the problem, and what kernel was chosen for the GP (e.g., squared exponential, Matérn, gamma-exponential)? Could the performance vary significantly with different kernel choices?

- The authors emphasize estimating the superlevel-set and focusing on it for optimization. How does the algorithm ensure sufficient exploration of the undecided set (i.e., regions where constraint satisfaction is uncertain), and could this lack of exploration affect the discovery of the global optimum?

- The combined ROI is formed by intersecting the ROIs of the constraints and the objective. In high-dimensional problems or when constraints are very tight, does this approach risk overly narrowing the search space and potentially missing promising areas?

- The absence of a pre-specified threshold for the objective function could introduce subjectivity in superlevel-set identification. Could this lead to overconfidence in certain regions of the search space, particularly if the confidence bounds are inaccurate?

- Regarding Figure 3, could the authors clarify why the labels for the "General ROI" and the "ROI for f/c" are the same across all five rows? This repetition makes the figure a bit confusing to interpret.

- In Figure 7, for the Ackley-5D-2C-14% task, the simple regret remains almost unchanged over iterations for $\beta=4$. This behavior appears to be unique to this specific case. Could the authors provide some insight into why this occurs?

- In Figure 9, I have a few specific questions that need clarification:

(1) Why does cEI perform poorly and show high regret in tasks like Converter, but performs better in others like Ackley and Vessel?
(2) Why does CONFIG show no improvement (flatline) in tasks like Rastrigin-1D and Ackley-5D?
(3) What causes COBAR’s performance to plateau in the Spring task? Is this behavior tied to the small feasible region size or other  factors?
(4) Why does SCBO exhibit high variance in tasks like Vessel and Spring? Could this be due to sensitivity to initialization or the structure of the problem?
title: title: Review of "Finding Interior Optimum of Black-box Constrained Objective with Bayesian Optimization"
main_review: main_review: **Summary:**
This paper presents a novel constrained Bayesian optimization (CBO) framework aimed at efficiently finding interior optimum by leveraging active learning for level-set estimation.

**Pros:**
- The paper provides rigorous theoretical analysis, including high-probability simple regret bounds. 
- The experimental analysis is also relatively thorough, comparing the performance of the proposed COBAR algorithm against three baselines across six different CBO tasks -- two synthetic and four real-world -- with dimensions ranging from 1 to 32, number of constraints ranging from 1 to 8, and feasible region portion ranging from 0.38% to 78%.
- I like the additional illustrations in the appendix. They help understanding the proposed method. However, I would suggest increasing the font size in the plots to improve readability.

**Cons:**
- The paper briefly mentions that when max LCB is constant, the acquisition function is equivalent to UCB, but it does not explain why max LCB is used when there is a non-empty feasible region and why the regular LCB is used when there is no feasible region. Including such details can add clarity to the proposed COBAR algorithm.
- While the caption of Figure 1 explains the plot titles, there is a lack of clear correspondence between the shorthand task names used in the plots and the detailed descriptions in the experiment section (e.g., you can mention "Rastrigin and Ackley are synthetic", "Converter is the one extracted from UCI Machine Learning repository", etc.), particularly when the order of the tasks in the figure does not match the order in the experiment descriptions (e.g., Converter is mentioned last in the text but appears third in the plots). This inconsistency can confuse readers trying to map the tasks in the plots to the descriptions in the paper. Additionally, there appears to be a typo in one of the plot titles: 36D should be 32D, as indicated in the texts of the experiment section.