Constrained Bayesian Optimization with Adaptive Active Learning of Unknown Constraints

We sincerely appreciate the detailed comments by the reviewer and would like to respond in the following.

Weakness

The active learning component is oddly presented and is not novel.

We sincerely appreciate the reference pointed out by the reviewer, where the active data selection on the region of interest is thoroughly discussed. We acknowledge the similarities between our approach and the global variance reduction methods or ALM, as well as their roots in previous work. In the revision, we will clarify this connection and refrain from describing the active learning aspect of COBALT as entirely novel. However, we would like to highlight the difference between the active learning methods referred by the reviewer and the proposed algorithm for constrained BO tasks.

We aim to propose a principled tradeoff of active learning of multiple unknown constraints and the optimization of the objective in the feasible region. To achieve this, we choose to unify the two different aspects---namely variance reduction and UCB, by framing them under the same mathematical framework as elaborated in Eq (5) and Eq (6). This framing ensures the comparability of the acquisition function of the unknown objective and the acquisition function of the unknown constraints. Further, it serves as the foundation for defining our acquisition function tailored to both needs. The other reason we use the interval between UCB and LCB is to follow the convention in previous works (AL-LSE[5] and BALLET[6]).

Another significant difference between the proposed method and the global variance reduction is that we are doing combined variance reduction on adaptively identified intersected ROI, which leverages the UCB or LCB as the threshold. The shrinkage of the intersected ROI guarantees the exploitation perspective of the acquisition and avoids budget waste, as discussed with reviewer AopU. The variance reduction on ROI (as in eq (6)) and standardized GP-UCB on ROI (as in eq (6)) achieve the exploration for both active learning and optimization. With the combination of ROI intersection and variance reduction on both the objective and the constraints, the proposed method achieves an efficient and principled tradeoff between exploration and exploitation. This serves the purpose of constrained BO and resonates with the well-known tradeoff in conventional BO.

As pointed out by other reviewers, given the specific constrained BO reward discussed in this paper, this is the first theoretical result of the convergence of the constrained BO algorithm we are aware of.

Theoretical analysis constraints substantial flaws: assumption 3 seems trivial.

We’d like to point out that there is a subtle difference between a monotonically shrinking $2\beta_t^{1/2}(x)\sigma_{t-1}(x)$ and the consistency of confidence interval at different iterations, as discussed in assumption 3. The former is trivial given the monotonicity of $\\sigma_{t-1}(x)$, while the latter could possibly be violated even when $\beta_t$ is non-increasing. For example, if the observed $y_t$ actually lies on the confidence interval, the resulting posterior confidence interval at $x_t$ could disagree with the confidence interval of the prior. Assumption 3 actually assumes a consistency of prior and posterior confidence intervals, and it helps with the analysis by guaranteeing a consistently shrinking ROI.

If we only resort to the monotonicity of the pointwise $\sigma_{t-1}(x)$ when having a constant $\beta$ for $\forall 1 \geq t \geq T$ where T is the known total budget, we could revise the $\beta$ to be dependent only on $\tilde{D}$ rather than $\tilde{D}_{\hat{X}_t}$. In that case, the theoretical results still hold. We refer to the detailed discussion in Appendix A of the revised paper.

Non-increasing beta_t

We appreciate the detailed question here. The reason $\beta_t=2\log(2(K+1)\vert \tilde{D}\vert \pi_t/ \delta)$ needs to grow is the need to guarantee the convergence of the series, which allows an asymptotical sublinear regret. Specifically, the requirement is $\sum_t{\pi_t} = 1$. Yet, in our problem setup, since cumulative regret could not be bounded as instantaneous regret could be infinite when the evaluated candidate $x_t$ violates any of the constraints (cf. Equation (3)), we aim to guarantee that after a certain horizon T, the simple regret could be bounded. Therefore, there is no need to have a convergence series $\sum_t{\pi_t} = 1$. As shown in the proof, we only need $\sum_{t=1}^T{\pi_t} = 1$ for a given budget/horizon T, and setting $\pi_t = 1/T$ satisfies it. We made revisions in the analysis section and the proof part to highlight this.

The algorithm "Maximize the acquisition values from different aspects:" is informal, and line 11 is not well-defined. 

The figures are difficult to parse due to the odd color choices (bright grey and dark orange on orange in Fig. 1, tiny legends everywhere).

Competing methods are not properly implemented. SCBO (Eriksson and Poloczek, 2019) builds on TuRBO, one of the more robust BO methods around.

Minors

In addition to the weaknesses (which certainly pose a few questions), I am curious about the following:
The constraint functions are assumed to be continous-valued. Is this conventional, and is the method amenable to non-continuous (i.e., binary output) constraints?

Thank you for the swift response! We’d like to clarify the novelty further and answer the remaining question by the reviewer.

I am saying that ALM/global variance reduction is clearly equivalent to the proposed method. 

Thank you for your constructive comments! We want to add the following clarification.

We agree with the reviewer that the variance maximization defined in equation (6) exactly matches the discussion about maximum information gain in the ALM paper. In fact, equation (6) itself is an AL-LSE [1] acquisition function, and equation (5) is a slightly modified UCB acquisition function. And we don’t intend to claim novelty on either the UCB or the variance reduction part. Please note that in the previous revision, we admitted the root of the active learning part in ALM in paragraph 3 of section 2. We additionally clearly stated this inheritance in the latest revision in section 4.3. However, the domain the acquisition function is maximized on is adaptively identified in a way that is not the same as the ALM discussion.

We still want to reiterate our contribution here. The adaptive tradeoff of AL-LSE and GP-UCB to achieve an efficient constrained BO method that comes with theoretical justification on its convergence rate, given the specific reward form we discussed in equation (3), is non-trivial. As far as we are aware, the ALM paper and recent advances in CBO do not offer efficient, principled adaptive trade-offs between multiple acquisitions through the ROI intersection and acquisition function combination, as proposed in our work. We are not aware of the existing convergence guarantee to the reward corresponding to equation (3). Therefore, the proposed intersected ROI ($\hat{X}_t$ as defined in equation (4))-based method on top of the ALM differentiates it from the original ALM method, though the ALM paper uses ROI for different notions.

In addition, please note the acquisition function for AL-LSE[1] is defined as the intersection of confidence intervals: $\vert\cap_{i=1}^t Q_i \vert = \vert \max_{i=1,..,t} LCB_i, \min_{i=1,...,t}UCB_i\vert$ and is maximized on an adaptively identified set.

I do not see consistency mentioned in relation to that Assumption. Can the authors clarify further?

Sure! The notion of consistency is stated in assumption 3, $UCB_{t_1}(x) \geq UCB_{t_2}(x)$ and $LCB_{t_1}(x) \leq LCB_{t_2}(x)$. While the monotonical shrinking that naturally holds due to the monotonicity of $\sigma_t$ only guarantees that $UCB_{t_2}(x)-LCB_{t_2}(x) \leq UCB_{t_1}(x)-LCB_{t_1}(x)$, when $t_1 \leq t_2$. We wanted to highlight that the consistency doesn’t naturally hold, in contrast to the shrinkage of the pointwise confidence interval.

Looking at the paper, it is still difficult to assess if $\beta_t$ is increasing or decreasing. Lemma 1 has $\beta_t$ be a function of $\pi_t$, and Theorem 1 has $\beta_t$ not be a function of $t$ at all, but of $T$.

Please note that in addition to the previous clarification where we justify that, in $\beta_t = 2log(2(K+1)\vert \tilde{D} \vert \pi_t / \delta)$ could be non-increasing as long as we don’t want a convergent series $\sum_t\pi_t^{-1} = 1$ but instead we only need $\sum_{t=1}^T\pi_t ^{-1}= 1$, we set $\pi_t = T$ as $T$ is the preset constant horizon meeting requirement in theorem 1. Then $\beta=2log(\frac{2(K+1)\vert \tilde{D} \vert T}{ \delta})$. Here the number of constraints $K$, the size of the discretization $\vert \tilde{D} \vert$, the horizon $T$, and $\delta$ are all given numbers. Then, $\beta$ is a constant.

I would still encourage the authors to be more precise. Maximizing the acquisition values from different aspects is not precise enough to include in an algorithm, as the uninformed reader cannot devise what the algorithm does. Moreover, I think the authors need to expand on this specific line in the text.

We sincerely appreciate these constructive comments. We added additional discussion to clarify it in the revision.

Lastly, my question regarding the intersection between the data and the discretization has yet to be addressed.

We apologize for missing it in the previous response. In fact, we believe $\tilde{D}$ as defined in Lemma 1 is a preset discretization in contrast to the $D_t$, which is the growing collection of historical observations. And $\hat{X}_t$ is the subset of the search space $\mathbf{X}$. Therefore, we do not intend to describe $\tilde{D}\_{\hat{X}_t}$ as the intersection of discretization and data but the discretization of the subset of search space. And as described in the previous response, we make $\beta=2log(\frac{2(K+1)\vert \tilde{D} \vert}{ T \delta})$ instead of relying on $\tilde{D}\_{\hat{X}_t}$ now.

reference

[1] Gotovos, Alkis. "Active learning for level set estimation." Master's thesis, Eidgenössische Technische Hochschule Zürich, Department of Computer Science,, 2013.

We appreciate the detailed and constructive comments by the reviewer. We’d love to clarify the following.

Weakness

1. The high-level approach is inefficient for the following reasons:

a. Querying $L_{C_{k’}}$ for some $k’ \neq k$.

Yes, this motivates the design of the intersection of ROIs and different ROIs for objectives and constraints. We want to avoid inefficient queries. This is a very good point. Actually, the reviewer might refer to the code we provided (src/opt/constrained.py line 523-524); we are actually intersecting $U_{C_k,t}$ with $\hat{X_t}$ instead of maximizing on the full $U_{C_k,t}$ on line 7 in algorithm 1. This is actually a typo, and we apologize for the confusion. Also, please note that in the proof of theorem 1, we’ve been using the correct domain.

b. In equation (5), pick the most uncertain f(x).

Please note that we are picking the most uncertain $f(x)$ on ROI, where the $UCB_{f} (x)$ is guaranteed to be above a certain threshold. Intuitively, we are narrowing the confidence interval of $f(x^*)$. This serves as an efficient global optimization acquisition as the uncertainty maximization guarantees the exploration while the ROI shrinking guarantees the exploitation. When $LCB_{f,t,max}$ is infinity, it means there is no super level-set identified, and taking the maximum of UCB could be optimizing the objective function out of the feasible region, which doesn’t always contribute to the performance.

2. The arguments that might be incorrect.

a. With respect to the claim that Constrained Bayesian optimization lacks theoretical analysis, the work by Lu and Paulson provides theoretical analysis.

We’re grateful for the reference provided by the reviewer and would like to add additional discussion to the related work. We would like to highlight that regret is different, and we provide theoretical justification in the task following the constrained BO problem setup where the infeasible candidate doesn’t incur a reward.

b. $\beta_t$ cannot be defined in theorem 1. 

We appreciate the reviewer pointing out the typo here. Actually, the reason we introduce assumption is to guarantee a monotonically shrinking $\hat{X_t}$, meaning we could use $\hat{X}\_{t-1}$ as the conservative surrogate for $\hat{X_{t}}$. In the revision, we will avoid confusion by using $\tilde{D}$ instead.

c. In the proof of theorem 1 (proof Lemma A.1), Lemma 5.4 of Srinivas is not applied correctly applied.

We appreciate the reviewer pointing out the typo here. We correct the proof in the revision by replacing $x_{g,t}$ with $x_t$. Please note that the ultimate acquisition function is defined as the maximum of the multiple acquisition functions. Roughly speaking, though only one of the $x_{g, t}$ is picked as $x_t$, the upper bound holds for the other points that have not been picked, as is shown in the revised proof in section A.2.

3. There are several unclear points.

The paper may need more arguments to explain why the approach of Takeno et al. (2022) "violates the theoretical soundness."

We acknowledge that the criticism could be overstated. Yet, as admitted in Takeno et al. (2022), there is no regret guarantee for the entropy-based method. It proves that the link to the UCB method in previous work could be an error.

b. Theorem 1 does not address the feasibility. Furthermore, Srinivas et al. (2009) analyze the regret of some input. While this paper introduces a definition of regret (or reward) of inputs, it does not use this definition in the theoretical analysis. This raises questions about the significance of Theorem 1 in terms of the algorithm's achieved reward (or regret).

(1) In assumption 2, we assume the feasibility. Theorem 1 shows that if there are feasible points, we can identify them after sufficient query with a certain confidence. Otherwise, the empty super level-set would suggest that with a certain confidence, assumption 2 is violated. That is, there is no feasible area.

(2) With regards to actual reward, if the identified Superlevel set is non-empty, the acquisition function $acq_{f,t}$ on that would actually be $UCB_f(x)$, which shares the regret guarantee with Srinivas et al. (2009). If the user wants to guarantee a query on the argmax of $UCB_f(x)$, the user can enforce that at any time or afterward. Otherwise, the algorithm is likely to query at least the argmax of $UCB_f(x)$ once within a large interval. We also add an additional corollary of theorem 1 in the revision to show the guarantee of a simple regret.

c. The abstract highlights a setting where "the objective and constraints can be independently evaluated," yet the paper primarily focuses on the coupled setting where they are evaluated together. The decoupled setting is briefly explained in the appendix without any supporting experiments.

d. The $\epsilon_C=0$ makes the analysis lose its significance.

e. The fundamental challenge of deriving practical regret bounds for CBO algorithms. 

a. The chosen performance metric is simple regret. However, identifying the input with minimum regret is unknown in practical applications. Thus, the paper does not address what input Bayesian Optimization recommends as the optimal solution.

b. Surprisingly, in the Rastrigin-1D-1C, the discrete search space consists of 1000 points, but the proposed algorithm reaches the optimum with 2000 iterations. Furthermore, the noise is small (0,0.1) compared to the function range [−40,0]. This efficiency is questionable.

c. Assumption 2 does not hold for equality constraints.

We are glad that we have addressed some of the reviewer’s concerns and would like to clarify the following further.

(2b) Could the authors provide a concise explanation for the need to ensure a monotonically shrinking $\hat{X}_t$ and elaborate on how defining $\beta_t$ using $\tilde{D}$ still ensures this property?

Sure! As noted by the reviewer in the original 2.b comments, at $t$, we can not actually estimate $\beta_t =2\log(\frac{2(K+1)\vert \tilde{D} \cap \hat{X}\_t \vert T}{\delta})$ because $\hat{X}\_t$ relies on the $\beta_t$. However, if $\hat{X}\_t$ is monotonically shrinking, meaning $\vert \tilde{D} \cap \hat{X}\_t \vert \leq \vert\tilde{D} \cap \hat{X}\_{t-1}\vert$, we could define $\beta_t =2\log(\frac{2(K+1)\vert \tilde{D} \cap \hat{X}\_{t-1} \vert T}{\delta}) \geq 2\log(\frac{2(K+1)\vert \tilde{D} \cap \hat{X}\_t \vert T}{\delta})$, then the union bound taken in the proof of lemma 1 still hold.

Now, we avoid the confusion by simply letting $\beta_t =2\log(\frac{2(K+1)\vert \tilde{D} \_t \vert T}{\delta}) \geq 2\log(\frac{2(K+1)\vert \tilde{D} \cap \hat{X}\_{t-1} \vert T}{\delta})$ as in the revised theorem 1. Then $\beta_t$ is essentially a constant. Though it does not guarantee that $\hat{X}\_t$ is monotonically shrinking, the desired union bound in lemma 1 still holds. The loss here is that $\beta_t$ could have been smaller if being defined upon $\vert\tilde{D} \cap \hat{X}\_{t-1}\vert$ instead.

(2c) My understanding of the application of Lemma 5.4 remains unclear. Suppose $x_{g,t}$ is not selected as $x_t$ for iterations from 1 to 5 for a function $g$; how can we demonstrate that $\sum_{t=1}^5 (2 \beta^{1/2} \sigma_{g,t-1}(x_t))^2 \le C_1 \beta \gamma_{g,5}$?

We’d like to address the reviewer’s concern but are not sure if we fully understand the question here. In the original 2.c comments, the reviewer pointed out that Lemma 5.4 only applies to the actually selected sequence of $x_t$. We believe here $\sum_{t=1}^5 (2 \beta^{1/2} \sigma_{g,t-1}(x_t))^2 \le C_1 \beta \gamma_{g,5}$ exactly match Lemma 5.4. Please note that in the proof of lemma 5.4, the sum of the square of simple regret $\sum_t r^2_t$ is first transformed into $\sum_{t=1} (2 \beta^{1/2} \sigma_{t-1}(x_t))^2$ by lemma 5.1 and 5.2 of Srinivas et al. (2009).

In addition, we want to highlight that the bridge between $2 \beta^{1/2} \sigma_{g,t-1}(x_{g,t})$ and the usage of lemma 5.4 is $\sum_{t=1}^{T} \alpha_t^2 \leq \sum_{t=1}^{T} \sum_{g \in \{C_k\}\_{k\in\mathcal{K}} } (\alpha_{g,t}(x_{t}))^2$, which is currently in the proof of our lemma A.1. For the left-hand side we have $2 \beta^{1/2} \sigma_{g,t-1}(x_{g,t}) \leq \alpha_t$ in the scenarios we’ve discussed in formula (8)-(12) in the proof of lemma A.1. And for the right-hand side we have $\alpha_{g,t}(x_{t}) \leq 2 \beta^{1/2} \sigma_{g,t-1}(x_t)$ by definition of the acquisition functions $\alpha_{g,t}$.

(3b) I kind of understand (1) but I find (2) difficult to understand. Why "if the superlevel set is non-empty, ..., which shares the regret guarantee with Srinivas et al. (2009)"? Could you clarify what is meant by the superlevel set in this context? If it is either a strict superset or a strict subset of the feasible region, then could you provide the reasons why the regret is comparable with Srinivas et al. (2009) where the feasible region is X?

We apologize for the confusion here. First, the superlevel set we refer to in this context is $S_{C,t}$, which is defined in section 4.2. In practice, since we are working on the discretization, it should be $\tilde{D} \cap S_{C,t}$ in the implementation. As illustrated in equation (5) in section 4.3, when $S_{C,t}\neq \emptyset$, $\alpha_{f,t}$ is essentially $UCB_{f,t}$. Yet we find out that the originally claimed connection to the regret guarantee with Srinivas et al. (2009) might be indirect, as the results by Srinivas et al. (2009) are on cumulative regret when using UCB as an acquisition function, while we are aiming at a simple regret guarantee.

We would like to refer to the updated Corollary 2, where we now show that when picking the point maximizing $UCB_{f,t}$ on $\tilde{D} \cap S_{C,t}$, we could translate the theorem 1 into a simple regret bound.

(4a) Is the authors referring to Corollary 2 in the Appendix? This section lacks clarity, as it appears that $R_T$ is defined as $f^* - f(x_T)$ in this proof, which is not the same as the simple regret defined at the end of section 3. The use of both $t$ and $T$ in the same term within this proof seems to be typos and causes confusion.

Concerning item 3c, leaving the comprehensive study of decoupled settings for future research could potentially lessen the impact of the paper. This is due to the fact that Lu and Paulson have previously conducted theoretical work on CBO, specifically addressing equality constraints, which are not addressed in this paper.

In the proof of Theorem 2, where does $g$ come from? This proof needs to be proofread and elaborated carefully.

Minor points:

(3d) There might be a misunderstanding of my question. I am specifically asking about "The paper introduces $\epsilon_C$ for theoretical analysis but does not utilize it in the algorithm." It means why $\epsilon_C$ is absent from the algorithmic description and only surfaces in the theoretical analysis (with no prior mention before section 5). If the algorithm sets $\epsilon_C = 0$, it implies that the analysis loses its significance for the proposed algorithm.
This observation suggests ensuring consistency between the algorithmic description and the theoretical analysis with respect to $\epsilon_C$.

We appreciate the clarification by the reviewer, and we would address this inconsistency by explicitly including the estimation of $\epsilon_C$ as an input of the algorithm.

(3e) I am expecting the paper to discuss a fundamental challenge of deriving practical regret bounds for CBO algorithms, which prevents existing works from deriving a theoretical analysis. Then, the paper will propose an algorithm to resolve it. However, from the response, it seems to be a limitation that is not resolved in this work.

We believe it is fundamental because we regard the limitation that the active learning component can not identify the full boundary of a dense search space with confidence within the limited number of queries as fundamental. Yet, we agree with the reviewer that there is no proof that the problem of active learning is a necessity, even considering our definition of reward.

In lines 12 and 13 of Algorithm 2, the subscripts should be $g_t$ instead of $g,t$.

We are grateful for the correction and have revised it accordingly. We found it actually should be corrected to be $g_{t}, t$ instead of $g_t$. Here, $g_t$ denotes the function to be evaluated at $t$, while the other $t$ is needed to ensure the alignment with subscript $C_k, t$ in line 7 and $f, t$ in line 9.

Reference

[1] Lu, Congwen, and Joel A. Paulson. "No-regret Bayesian optimization with unknown equality and inequality constraints using exact penalty functions." IFAC-PapersOnLine 55, no. 7 (2022): 895-902.

[2] Lu, Congwen, and Joel A. Paulson. "No-regret constrained Bayesian optimization of noisy and expensive hybrid models using differentiable quantile function approximations." arXiv preprint arXiv:2305.03824 (2023).

Roughly speaking, though only one of the $x_{g,t}$ is picked as $x_t$, the upper bound holds for the other points that have not been picked, as is shown in the revised proof in section A.2.

In the proof of Theorem 2, we are not sure which one the reviewer is pointing to, but we believe should be taken according to algorithm 2.

We appreciate the further clarification of the previous discussion and constructive comments that help enhance the presentation of our paper. We’d like to add a tentative discussion over the difference from the existing no-regret CBO method in the appendix. In the following, we want to address the reviewer’s remaining concerns.

The proof of the simple regret in Corollary 2 is "after attaining 13". But the definition $\beta = 1/T$ is established based on the iteration T when 13 is attained. Consequently, "after attaining 13", the upper confidence bound and lower confidence bound (depending on $\beta$) may no longer be applicable. So, this is potentially an error in the proof of the simple regret.

We understand the concern raised by the reviewer here. Though we leverage the bounds and the acquisition function holds at $T$ for the $T+1$ query, the discrepancy on $\beta$ could be confusing and even erroneous.

We made the following revisions to the corollary 2.

(1) By enlarging $\beta$ from $\beta =2\log(\frac{2(K+1)\vert \tilde{D}\vert T}{\delta})$ to $\beta =2\log(\frac{2(K+1)\vert \tilde{D} \vert (T+1)}{\delta})$, we guarantee that the union bound used in the proof of theorem 1 before attaining 13 would still hold;

(2) we change the acquisition back to $LCB_{f,t}$, since we figured out $UCB_{f,t}$ actually incur an additional term we do not see a straightforward proof to guarantee that it can be bounded by $\alpha_T \leq \epsilon$.

Though we make the changes, the intended interpretation of Corollary 2 remains the same as the following. As long as $T$ is sufficiently large for a fixed $\epsilon$ so that it meets $T \geq \frac{\beta \widehat{\gamma_T} C_1}{\epsilon^2}$, and the algorithm picks the $arg\max_{x \in \tilde{D}\_{\hat{X}\_T} \cap S_{C, T}}LCB_{f,T}(x)$, the algorithm would translate the analysis in theorem 1 into a high probability bound by the simple regret.

Question

The assumption 2 needs \beta_t to be non-increasing. 

We appreciate the detailed question here. The reason $\pi_t$ needs to grow is the need to guarantee the convergence of the series, which allows an asymptotical sublinear regret. Specifically, the requirement is $\sum_t{\pi_t}^{-1} = 1$. Yet, in our problem setup, since cumulative regret could not be bounded as instantaneous regret could be infinite when the evaluated candidate $x_t$ violates any of the constraints (cf. Equation (3)), we aim to guarantee that after a certain horizon T, the simple regret could be bounded. Therefore, there is no need to have a convergence series $\sum_t{\pi_t}^{-1} = 1$. As shown in the proof, we only need $\sum_{t=1}^T{\pi_t}^{-1} = 1$ for a given budget/horizon T, and setting $\pi_t = T$ satisfies it. We made revisions in the analysis section and the proof part to highlight this.

The setting in which $\sum_{t=1}^T{\pi_t}^{-1} = 1$ is used instead of $\sum_t{\pi_t}^{-1} = 1$ can be found in [1] as they also aim at a simple regret after a sufficiently large $T$. Similarly, in a multi-fidelity BO setting [2], the total budget is assumed to be given to attain a theoretical guarantee on the cumulative regret.

Reference

[1] Wang, Zi, and Stefanie Jegelka. "Max-value entropy search for efficient Bayesian optimization." In International Conference on Machine Learning, pp. 3627-3635. PMLR, 2017.

[2] Song, Jialin, Yuxin Chen, and Yisong Yue. "A general framework for multi-fidelity bayesian optimization with gaussian processes." In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3158-3167. PMLR, 2019.

[3] Maus, Natalie, Haydn Jones, Juston Moore, Matt J. Kusner, John Bradshaw, and Jacob Gardner. "Local latent space Bayesian optimization over structured inputs." Advances in Neural Information Processing Systems 35 (2022): 34505-34518.

[4] Gardner, Jacob, Chuan Guo, Kilian Weinberger, Roman Garnett, and Roger Grosse. "Discovering and exploiting additive structure for Bayesian optimization." In Artificial Intelligence and Statistics, pp. 1311-1319. PMLR, 2017.

[5] Nayebi, Amin, Alexander Munteanu, and Matthias Poloczek. "A framework for Bayesian optimization in embedded subspaces." In International Conference on Machine Learning, pp. 4752-4761. PMLR, 2019.

We appreciate the detailed comments made by the reviewer. We would like to clarify the confusion raised by the reviewer in the following.

Weakness

The exact conditions of the discretization are unclear in the statement of lemma 1 and theorem 1.

We'd like first to clarify the discretization as it is related to the other concern raised by the reviewer. Throughout the design of the algorithm, we focus on dealing with the finite discretization $\tilde{D}$ of the original search space, which aligns with many engineering tasks where only the discretization is feasible or a known smoothness on locality alleviates the needs to scan the whole continuous space.

As noted by the reviewer, Srinivas et al. (2009) start by studying a search space of finite discretization and then introducing the smoothness assumption to extend the results to a multi-dimensional continuous search space where the regret bound relies on the search space. We do not further extend the discussion to a continuous search space for two reasons. (1) The motivating application for us does not deal with a continuous search space; (2) There are recent advancements introducing various treatments of continuous search space given different assumptions on the structure of the problem. For example, with regard to the high-dimensional BO task as concerned by the reviewer, except directly creating discretization, which incurs the curse of dimensionality, various principled treatments [3,4,5] have been studied. They could be incorporated into our constrained BO framework to address the concern that the construction of a finite search space could be troubled by high dimensionality. A comprehensive discussion of the construction of a finite search space might go beyond the scope of this work.

It is not clear how to numerically check if $LCB_{f, t, max}$ is finite or not. It is unclear from the paper how the intersection is computed.

Related to the previous question, we are focusing on a finite discrete search space $\tilde{D}$, where a simple strategy would be checking the membership to different sets using the point-wise LCB and UCB values.

The constant balances the exploration and exploitation and has a huge impact on the practical performance. It is unclear how it is set in practice.

We appreciate the constructive comment. We added additional results and corresponding scripts in the revision to demonstrate the robustness against different choices of $\beta$. In summary, among the choices of the theoretical results or constant values, including 0.1, 2, 4, and 8, we observe that only .1 could trap the algorithm in the sub-optimal area due to its lack of exploration.

The proof relies on an additional assumption that the confidence interval has to shrink monotonically, which is somewhat non-standard in the analysis of BO algorithms. However, the author claims they can apply a proof technique by Gotovos et al. (2013) even if this assumption is violated.

You are correct that our proof relies on the assumption, and as the reviewer pointed out, we can apply a proof technique by Gotovos et al. (2013) even if this assumption is violated. We can construct a new confidence interval by taking the maximum (minimum) of historical pointwise LCB (UCB). Then, the new confidence interval monotonically and consistently shrinks. Since we are aiming at a guarantee within a finite known $T$ iteration, the construction of this new confidence interval (taking union bound) would only incur a constant cost on the confidence level of the ultimate bound in theorem 1. Please note that such modification implies a slight change in the algorithm. However, we find in our empirical study that, even without these additional steps, our algorithm already exhibits compelling performance consistently across a variety of BO benchmarks.

Dear Reviewer vk7s,

Thank you for the swift reply and for clarifying the concerns about the discretization!

First of all, the search domain $\mathbf{X}$ is never assumed to be discrete in the paper. 

Before reaching algorithm 1, we do not discuss the discretization $\tilde D$. We define the region of interest $\hat{\mathbf{X}}$ in equation (4) to be a subset of $\mathbf{X}$, which is not assumed to be discrete.

Yet in practice, since we need to check the membership pointwise on the discretization $\tilde D$, we actually rely on the discrete set $\tilde{D}\_{\hat{X_t}}= \tilde D \cap \hat{X_t}$. As illustrated in lines 7-8 of the algorithm 1, we use $arg\max_{x\in \tilde{D}\_{\hat{X_t}} \cap U_{C_k, t}} \alpha_{C_k, t} (x)$ and $arg\max_{x\in \tilde{D}\_{\hat{X_t}}} \alpha_{f, t} (x)$ in contrast to the conceptual discussion in section 4.3 where we use $arg\max_{x\in \hat{X_t} \cap U_{C_k, t}} \alpha_{C_k, t} (x)$ and $arg\max_{x\in \hat{X_t}} \alpha_{f, t} (x)$. We just added additional clarification at the end of section 4.3 to clarify the implementation.

Second, the objective functions used in the experiments have a continuous domain (e.g., Rastrigin). If the experiments are conducted on a discretized search space $\tilde D$, the authors are required to provide the detail of the discretization $\tilde D$ (which, unfortunately, is not available).

We just added additional information about the construction of discrete space we used in the low-dimensional synthetic datasets. We fix the $\tilde D$ throughout the experiment on both Ratrigin and Ackley to reduce randomness and guarantee reproducibility. Please note that, as illustrated in the first row of Figure 3, we make the discretization dense to capture the geometry of the continuous functions.

This is also related to my original concern: the explicit expression of the discretization $\tilde D$ is missing in Lemma 1.

Yes, you are right! The result of Lemma 1 should actually be the probability bound for $x \in \tilde{D}\_{\hat{X_t}}$ instead of $x \in \hat{X_t}$. We just corrected it in both the lemma and proof in Appendix A.1. We apologize for the confusion. At some point, we decoupled the concepts of search space and ROI from the discretization, which is now separately denoted as $\tilde {D}$, and the notation is mistakenly left over.

---

Thank you again for the constructive comments, which we find helpful in enhancing the clarity of the paper! We hope our clarification and updated revision addresses your concern.

Hi authors,

I appreciate the effort of clarification. However, I still disagree the argument on discretization.

First of all, the search domain $\mathbf{X}$ is never assumed to be discrete in the paper. Second, the objective functions used in the experiments have continuous domain (e.g. Rastrigin). If the experiments are conducted on a discretized search space $\tilde D$, the authors are required to provide the detail of the discretization $\tilde D$ (which unfortunately is not available).

This is also related to my original concern: the explicit expression of the discretization $\tilde D$ is missing in Lemma 1. Based on Lemma 1, any discretization works. If I pick a singleton $\tilde D = \\{\mathbf{x}^*\\}$, does the high probability bound still work? It does not quite make sense as the region of interest $\hat{X}_t$ does not make use of the discretization at all..

We are glad the reviewer appreciates our contribution to the BO with unknown constraints, and we sincerely appreciate the constructive comments by the reviewer.

Weakness

Empirical evaluation is limited to 6 relatively low-dimensional tasks. Testing on more high-dimensional real-world problems would better showcase scalability.

1. Thank you for raising this in the comments. Please note that the water converter is a 36-dimensional task, which is reasonably high-dimensional (i.e., d>10).

2. As the reviewer noted in the questions, the performance actually depends on the quality of the GP models. We found tuning a large number of GPs in high-dimensional, large-scale tasks to be more challenging. Especially when the prior or kernel learning is not properly tuned, the misspecification of every single model accumulates in the ROI intersection. Then, it is possible to result in an empty intersected ROI, which is not expected when models offer satisfying uncertainty quantification.

3. We do see the potential of further integrating additional ROI-based HDBO treatments, such as BALLET[1], into the COBALT framework to further enhance the scalability through (deep) kernel learning [6]. We want to highlight that, as noted by the reviewer, this submission focused on the principled tradeoff between learning and optimization in the constrained BO setting within the limited pages. Advancements in modeling and efficiency for large-scale constrained BO tasks would definitely be of interest in the future.

The theoretical analysis relies on several assumptions that may not always hold in practice, such as the independence of the GPs and the existence of a feasible solution.

1. This is a good point (question). Thank you for raising this concern. For the dependency assumption, we follow the convention in the constrained Bayesian optimization literature [2, 3]. As discussed in section F.3 in the appendix, we acknowledge the limitation of the current assumption and believe it is an interesting future direction to explore different dependency assumptions, which could lead to potentially novel modeling and acquisition function choices.

2. We also appreciate the reviewer's concern about our assumption of the existence of a feasible solution, although it wasn't a primary consideration in our motivating applications. If this assumption does not hold, it implies two significant implications: (1) the task or application in question may encounter fundamental challenges; (2) as our analysis indicates, the algorithm is designed to identify a subset of the feasible region, should it exist. In the absence of such a region, the active learning component of our algorithm would converge to an empty intersected Region of Interest (ROI).

3. To provide further clarity on this aspect, we have extended our analysis in the appendix of the revised version. Our additional result further highlights the algorithm's capability to detect infeasibility and is presented as a corollary of our existing results.

The theoretical analysis relies on assumptions like GP independence and feasible solutions. Could these be relaxed? What are the barriers to deriving more general guarantees?

What is the computational complexity of COBALT? How does it scale with dimensionality and constraints?

Have you tested on any high-dimensional (D>10) or large-scale real-world problems? This could better showcase scalability.

Is there a principled way to set the β tradeoff parameter? Sensitivity analysis could elucidate its impact.

How does performance depend on the quality of the GP model of the constraints?

Dear Reviewers,

We sincerely appreciate your active engagement and valuable feedback. The ongoing discussion has been invaluable, especially during this concluding phase of the author-reviewer discussion. Despite the limited time for further deliberation, we want to express our openness to providing any additional clarifications necessary to thoroughly address the concerns raised by all reviewers.

Thank you for your time and consideration.