Optimistic Bayesian Optimization with Unknown Constraints

2. The result plot only shows the summation of regrets, which does not tell the found solution is feasible or not. Can you separately show the regret of the objective function and constrant functions?

• We have implemented the reviewer's recommendation by including regret plots for both the objective function and constraint functions separately in Appendix E.7 in our latest revision.

• It is important to highlight that the estimator $\tilde{x}^*$ of the optimal solution is typically a feasible input when there are no active constraints at the optimal solution, as shown in Figure 4a in the newly-added Appendix E.7. However, in cases where active constraints exist at the optimal solution, accurately estimating the boundary of the feasible region becomes challenging. Consequently, the estimator often becomes an infeasible input (the newly-added Figures 4b & 4c in Appendix E.7). Nevertheless, it is worth noting that the sum of regrets serves as an upper bound for the regrets associated with the objective function and constraint functions. Hence, even if the estimator is infeasible, the no-regret result in Lemma 3.5 shows that we can achieve arbitrarily small constraint violation at the expense of more BO iterations.

• Appendix A discusses the rationale underlying our selection of an estimator within the optimistic feasible region, even if it may be infeasible, particularly in the context of equality constraints. More generally, if the feasible region has an empty interior (e.g., due to equality constraints), pinpointing a feasible input accurately becomes impossible, regardless of the number of observations gathered. For example, if the feasible region is only a line in the space, then estimating the line without any error (to identify feasible inputs) using only noisy observations is not possible. Our strategy of utilizing the optimistic feasible region circumvents this challenge, albeit with a minor constraint violation if active constraints are present at the optimal solution. It is important to recall that in situations where there are no active constraints at the optimal solution, our estimator is often a feasible input, as illustrated in Figure 4a. Additionally, as the number of BO iterations increases, the amount of constraint violation approaches zero, allowing for arbitrarily small violations at the expense of a more lengthy BO procedure.

• When desiring a feasible solution and knowing that the interior of the feasible region is non-empty, there are several ways:

  • One approach involves tightening the constraints by adding a small positive value to $\lambda_c$ for all $c \in \mathcal{C}$. However, caution is warranted as this adjustment may render the optimization problem infeasible if the interior of the feasible region is empty.

  • Alternatively, instead of relying on an optimistic feasible region, a pessimistic feasible region can be utilized to ensure the feasibility of all inputs within it. It is important to note that this approach is not viable for optimization problems with equality constraints, as it would render the problem infeasible.

3. In Figure 2 (h), the standard error of UCB-D is much larger than other baselines. Can you give some insights of why this happens?

This is due to the logarithmic scale used in the plot, which accentuates small values. For example, on the log plot, the distance between 0.01 and 0.1 (a span of 0.09) is visually the same as the distance between 0.1 and 1.0 (a span of 0.9). Consequently, although the standard error of UCB-D appears larger in Figure 2h compared to other methods, it is indeed smaller than most of the methods. In Figure 2h, at the end of the line plot, the numerical value of the standard error for UCB-D is 0.015506. In comparison, the standard errors for ADMMBO, CMES-IBO, EIC, and UCB-C in Figure 2h are 0.37287908, 0.02479963, 0.01956778, and 0.01082636, respectively.

We sincerely wish that our motivation to the decoupled queries, and the additional plots of the regrets associated with the objective function and the constraints can improve your opinion on our paper.

We appreciate your valuable feedback and recognition of the clarity and ease of understanding in our idea, presentation, and experimental results. We will seriously consider your feedback during the revision of our paper.

We would like to address your questions below:

1. As mentioned in weakness part, my major concern lies in the motivation of decoupling the function queries, since in many real-world applications, the objective and constraint values are simultaneously evaluated after one trial, and decoupling the function query seems not save the cost. Can you explain the motivation and potential application of decoupling the function queries?

We would like to emphasize that our methodology and theoretical analysis are applicable to both coupled and decoupled queries, as mentioned in the final paragraph of Sec. 1: Introduction. Therefore, our research holds significance not only for the decoupled setting but also for the coupled setting of constrained BO. We will further enhance the motivation and potential application of decoupling the function queries in our revised paper as follows:

Motivation: In Remark 3.2, we elaborate on the motivation that decoupling the function queries results in a more query-efficient solution. Hence, leveraging the ability to evaluate the objective function and constraints independently becomes advantageous, particularly in situations where the evaluation of each component is resource-intensive. For instance, when there is a high probability that the input query is feasible, the evaluation of constraints at that input query becomes unnecessary (especially if the optimal solution is far from the boundary of the feasible region, as illustrated in Figure 2a). In such scenarios, significant cost savings can be realized in the decoupled setting compared to the coupled one.

Potential applications: Here are two potential applications that showcase the benefits of employing decoupled queries:

• A practical scenario of decoupled queries arises in the automotive industry. When designing the body of a car, various approaches are employed to assess its performance. For instance, computational fluid dynamics (CFD) is utilized to model the interaction between the car body and air flows. On the other hand, finite element analysis (FEA) is employed to simulate the car body's response to various loads, such as those encountered in collisions. One may construct a constrained optimization problem to maximize the aerodynamic performance of a car while adhering to safety constraints during collisions. CFD and FEA can be performed independently and performing each of them is expensive.

• Another situation arises when selecting an ML model for deployment across different edge devices. These devices have diverse hardware configurations, leading to variations in prediction times and battery consumption. The goal is to optimize the model's prediction accuracy while meeting constraints on prediction times and battery consumption for various edge devices. Evaluating the prediction time and battery consumption on different devices and the prediction accuracy of the ML model can be performed separately, and these evaluations are time-consuming.

Thank you for your response about the motivation of the problem setting and clarification of the experimental detail. I think I understand this paper clearer.

However, I still think the chosen real-world experiment does not utilize the advantage of decoupled evaluation. I encourage the authors to design more suitable real-world experiments based on the aforementioned potential applications to better demonstrate the advantage of UCB-D.

Overall, I've increased my score from 5 to 6.

We thank you for recognizing our efforts in presenting a solution that is adaptable to various situations and equipped with a theoretically proven performance guarantee. Your valuable feedback will be carefully considered as we revise our paper.

We would like to provide clarifications to your questions below:

1. In plotting the UCB-C's regret against the number of queries (e.g., Figure 2g), as evaluations are conducted at both the objective function and constraints in each BO iteration, how are they plotted? Does the plot advance by jumping every #constraints + 1?

You are correct in noting that for UCB-C (involving coupled queries), the plot advances by jumping every #constraints + 1 queries. For UCB-D (involving decoupled queries), the plot advances with a jump every single query.

2. Just curious, in cases where the query point is feasible, why don’t we evaluate the constraints together with the objective function? What are the advantages of strictly adhering to UCB-D?

As our objective is to minimize the number of queries, we aim to minimize unnecessary queries to either the objective function or the constraints. Consequently, if we know that a query point is feasible, querying the constraints does not provide additional information on its feasibility. Therefore, we propose to query only the objective function to determine whether the query point is suboptimal (i.e., indicated by a low objective function evaluation). However, when the cost of querying constraints is not prohibitive or the queries are coupled, we may choose to evaluate both the constraints and the objective function simultaneously, as proposed in the UCB-C algorithm.

We sincerely hope that the above clarifications will improve your favorable perspective of our paper.

We thank you for appreciating our contributions (i.e., tackling a problem seldom studied before, a well-organized paper with helpful illustrations, experiments on synthetic and real-world problems showing the effectiveness of our algorithm) and providing useful feedback which we would take into account seriously when revising our paper.

We would like to address your concerns below:

1. In Introduction, the motivation of studying decoupled constrained BO (CBO) is unclear to me. What are the real-world applications of decoupled CBO? In which case should we evaluate objective function and constraints at different inputs? In that case, can we run several independent standard BOs to solve all problems separately? Or can we run multi-objective BO to solve it?

Unified approach to both coupled and decoupled queries: We would like to highlight that our approach and theoretical analysis work for both coupled and decoupled queries (see last paragraph of Sec. 1: Introduction). Thus, our work is important to not only the decoupled setting but also the coupled setting of constrained BO.

In which case should we evaluate objective function and constraints at different inputs? We should evaluate objective function and constraints at different inputs when we can evaluate the objective function and constraints independently and the evaluation of each of them is expensive. In Remark 3.2, we also explored the circumstances under which employing decoupled queries could significantly improve efficiency in terms of the number of queries, as compared to coupled queries. For instance, when there is a high probability that the input query is feasible, the evaluation of constraints at that input query becomes unnecessary (especially if the optimal solution is far from the boundary of the feasible region, as illustrated in Figure 2a). In such scenarios, significant cost savings can be realized in the decoupled setting compared to the coupled one.

Real-world applications of decoupled queries:

• A practical scenario of decoupled queries arises in the automotive industry. When designing the body of a car, various approaches are employed to assess its performance. For instance, computational fluid dynamics (CFD) is utilized to model the interaction between the car body and air flows. On the other hand, finite element analysis (FEA) is employed to simulate the car body's response to various loads, such as those encountered in collisions. One may construct a constrained optimization problem to maximize the aerodynamic performance of a car while adhering to safety constraints during collisions. CFD and FEA can be performed independently and performing each of them is expensive.

• Another situation arises when selecting an ML model for deployment across different edge devices. These devices have diverse hardware configurations, leading to variations in prediction times and battery consumption. The goal is to optimize the model's prediction accuracy while meeting constraints on prediction times and battery consumption for various edge devices. Evaluating the prediction time and battery consumption on different devices and the prediction accuracy of the ML model can be performed separately, and these evaluations are time-consuming.

We will incorporate the above examples into Sec. 1: Introduction to further motivate the decoupled queries.

In that case, can we run several independent standard BOs to solve all problems separately? Or can we run multi-objective BO to solve it?

• We think that performing several independent standard BOs to solve a constrained BO problem with decoupled queries is a solution that is orthogonal to all existing constrained BO solutions. However, based on our current understanding, it is unclear (at least to us) how this can be accomplished effectively.

• Similarly, it is unclear to us how multi-objective BO can be used to solve constrained BO if the queries are decoupled. We would appreciate the reviewer's guidance in providing further elucidation on these two approaches.

Further, we would like to address your questions below:

1. How does the last equation hold in eq 8 by adding vertical exploration bonus?

Equation 8 is directly adopted (without any modification) from the work of Srinivas et al. (2010). The term in the argmax is just the definition of the upper confidence bound of $f(x)$. The introduction of the name "vertical exploration bonus" for a term in equation 8 aims to emphasize the analogous concept of horizontal exploration, which becomes relevant in the context of constrained BO later on.

2. In last paragraph of Section 3.1, how does Lemma 3.1 imply that $\mathcal{O}_t$ is non-empty with probability $> 1-\delta$?

If the optimization problem is feasible, then there exists at least $1$ feasible input $x_0 \in \mathcal{X}$, i.e., for all $c \in \mathcal{C}$, $c(x_0) \ge \lambda_c$. Lemma 3.1 says that $u_{c,t-1}(x) \ge c(x)$ for all $x \in \mathcal{X}$, $t \ge 1$, and $c \in \mathcal{C}$ with probability $\ge 1 - \delta$. Hence, if the optimization problem is feasible, $u_{c,t-1}(x_0) \ge c(x) \ge \lambda_c$ for all $c \in \mathcal{C}$ and $t \ge 1$ with probability $\ge 1 - \delta$. In other words, $\mathcal{O}_t$ is non-empty with probability $\ge 1 - \delta$ for all $t \ge 1$. We will include this argument in the revised paper.

We sincerely hope that our responses above have contributed positively to your opinion of our work in this paper. We are open to addressing any remaining concerns and providing further clarification.

2. I'm surprised to see definition of regret in eq (3) by combining objective function evaluation together with constraint violations. They may sit in totally different function ranges. Let $F$ denote the range of objective function and let $C$ denote the range of constraints. If $C$ is much greater than $F$, then regret has little information about convergence. Also, the optimal point $x^\ast$ is defined w.r.t. objective function and $r_c$ is independent to $x^\ast$. Why is $r_c$ part of the regret?

• Why $r_c$ is part of the regret:

  Also, the optimal point $x^\ast$ is defined w.r.t. objective function and $r_c$ is independent to $x^\ast$. Why is $r_c$ part of the regret?

  It is important to clarify that the determination of $x^\ast$ is not solely based on the objective function in our context, as we are dealing with a constrained optimization problem. Consequently, $x^\ast$ is defined by considering both the objective function and the constraints, seeking to maximize the former while adhering to the latter. Therefore, the incorporation of $r_c$ (which quantifies the degree of constraint violation for a given input) into the regret is crucial. The regret, in this context, serves to evaluate the performance of an estimator $\tilde{x}_t$ in approximating the optimal solution. As a result, this regret must account for both suboptimalities arising from the objective function and the violation of constraints. Hence, our proposed regret that addresses these aspects is a unique contribution of our work, particularly considering the limited existing literature on regret analysis in constrained BO.

• Different function ranges

  I'm surprised to see definition of regret in eq (3) by combining objective function evaluation together with constraint violations. They may sit in totally different function ranges. Let $F$ denote the range of objective function and let $C$ denote the range of constraints. If $C$ is much greater than $F$, then regret has little information about convergence.

  • From a theoretical analysis perspective, the no-regret definition exhibits asymptotic behavior, specifically, the simple regret tends to $0$ as the number of iterations $T$ approaches infinity. The impact on convergence as $T$ approaches infinity remains unaffected by the magnitude of the function range, provided that the function range is not unbounded. Our proposed regret serves as an upper bound for regrets arising from the objective function and constraints, as it represents the maximum or sum of these regrets. Consequently, if our proposed regret approaches $0$, it implies that both the regrets associated with the objective function and constraints must also approach $0$, even in cases where their function ranges may differ. This can be conceptualized as constraining the worst-case regret among all regrets incurred by the objective function and constraints. We would like to point out that in the classic GP-UCB work, the asymptotic convergence holds irrespective of the scale of the function range.

  • From a practical point of view, one can normalize the observations at every BO iteration so that the observations from the objective function and constraints belong to similar ranges.

3. How do you solve optimization problems in Line 3 and 4 in Algorithm 1? Definition of $\mathcal{O}_t$ seems like making solving Line 3 intractable.

• Line 3: This is a constrained optimization problem with a closed-form expression of the objective function and closed-form expressions of the constraints. Hence, it can be solved with any existing constrained optimization package.

  • Objective function: $u_{f,t-1}(x)$;
  • Constraints: $u_{c,t-1}(x) \ge \lambda_c \ \ \forall c \in \mathcal{C}$ (from the definition of $\mathcal{O}_t$ in equation 9);
  • As defined in equation 7, $u_{h,t-1}$ only consists of the GP posterior mean and GP posterior standard deviation, both of which have closed-form expressions for a Gaussian process model. The set $\mathcal{C}$ is a finite set of constraints.

• Line 4: We simply go through all constraints and find the one with the largest $\lambda_c - l_{c,t-1}(x_t)$.

We hope this message finds you well. We are following up on our recent response to your questions and reviews of our paper and would like to know whether our response adequately addressed all your concerns. Your feedback is crucial to us, so could you kindly take a moment to confirm if our rebuttal meets your expectations? We greatly appreciate the time and effort you have devoted to responding to us.

We appreciate your valuable reviews and thank you for appreciating the good interpretability of our key concepts and algorithm, our theoretical analysis of CBO, and our well-organized paper with illustrative figures. We will carefully incorporate your feedback and suggested related works into our revised paper.

We would like to address your concerns below:

1. Though the author highlights the connection of the proposed method to active learning (AL), it lacks a discussion on the link to the existing AL methods. For example, the concepts, including the uncharted area and $\nu_t$-relaxed feasible confidence region, resonate with the concepts in [1], and the analysis also bears connections.

We will include the discussion of [1] in the revised paper. The major differences with [1] are briefly discussed below.

• Our approach is not simply a combination of active learning for level set estimation and Bayesian optimization. As shown in Figs. 2a-c, our method adaptively allocates input queries based on specific scenarios, eliminating the necessity for performing level set estimation across the entire feasible region. In contrast, applying active learning for level set estimation typically involves uniformly exploring the complete feasible region.
• The work of [1] requires monotonically decreasing confidence region by intersecting successive confidence intervals. Practical applications may encounter challenges, particularly if the intersection results in an empty confidence region. In contrast, our approach aligns more closely with conventional GP-UCB method, omitting the requirement for such a monotonic decrease in the confidence region and thereby avoiding the issue of empty confidence regions.
• In [1], manually setting the value of $\epsilon$ is mainly for the theoretical analysis from our perspective. In our work, the value of $\nu_t$ is not manually set, but it is adaptively chosen by our algorithm. Furthermore, it is to balance between the vertical and horizontal exploration, a concept that does not exist in [1].

2. The definition of regret is unconventional and lacks sufficient discussion. Typically, in the CBO setting, the reward is only defined within the feasible region, as there is no reward incurred by querying the points that are infeasible. The regret here is defined on both the objective and constraints, which circumvent the problem of infinite instantaneous regret in cumulative regret analysis when querying points out of the feasible region.

The conventional viewpoint is that a constrained minimization problem with known constraints is often formulated as an unconstrained minimization problem with infinite values for infeasible inputs. The constraints in constrained BO are unknown, and so is its feasible region. Assigning infinite instantaneous regret to infeasible inputs is problematic. For example, when there are equality constraints, it is impossible to estimate the feasible region exactly (e.g., a line) given noisy observations. In such a case, we will never know if an input is feasible. Hence, without a finite measure of constraint violation, analyzing the regret is very challenging. As a result, we believe it is a natural approach to assign finite regret based on constraint violation. We have discussed the challenges of equality constraints in Appendix A. We will incorporate this discussion in the revised paper.

Additionally, the limited theoretical works on constrained BO (only 1 theoretical work with coupled queries and no theoretical work with decoupled queries) deprive us of a conventional regret definition capable of addressing both the unknown objective function and unknown constraints. Hence, we consider introducing this concept of regret as a distinctive contribution of our work.