BILBO: BILevel Bayesian Optimization

Thank you for the detailed review, and for appreciating our novel approach to a significant problem, sample efficiency of our method, sublinear regret bound, and effective experimental results. We would like to clarify the following points.

One issue is that some of the results shown in the experimental section seem to be non-complete, such as the green curves in the Fig. 4 (a, b, c).

The green curves represent Nested's number of queries over regret. There is an obvious gap at the start of each green curve as the Nested method requires more initial observations of lower-level functions to optimize the lower-level problems separately before estimations begin, compared to BILBO and TrustedRand.

What if the lower-level problem is a white-box problem that can be solved via a nonlinear programming solver? Can similar idea work for this case?

White-box problems are often inexpensive to compute. We can still apply our algorithm, evaluate the white-box problem at every step and reduce the confidence interval to a point, since there are no noisy observations. If the nonlinear programming solver for the lower-level is preferred (e.g. for computational efficiency), we can also reduce BILBO to a special case where Bayesian optimization is carried out only on the upper-level. However, we would also like to point out that BILBO's advantages are in settings with expensive blackbox evaluations and noisy observations, both of which are not present in this scenario.

We hope these clarifications answer your questions and improve your opinion of our paper.

Thank you for your insightful review, and for recognizing our sublinear cumulative regret and sample efficiency when both upper- and lower-level objectives are expensive blackboxes.

1. Have you studied the performance of BILBO when the trusted spaces are built on discretized versions of continuous search spaces? If yes, what additional assumption do you need to ensure a sublinear regret bound? If no, do you have any intuition about it?

This is an interesting future research direction that we have not studied. One possible factor on the performance of discretized problems will be the difference between the best discretized point and the optimal point in the continuous domain. This difference may be bounded with respect to the granularity of the discretization, with Lipschitz continuity assumptions. As discretization becomes finer, the performance should converge to that of continuous search spaces.

3. What is the computational complexity of BILBO as a function of the dimensionality of the search spaces? As a function of the cardinality of the uniform grid used for discretization?

For a discretized implementation, the computational complexity of BILBO is affected by computational complexity of :

• Gaussian processes $\mathcal{O}(n^3)$
• Updating trusted sets $\mathcal{O}(|\mathcal{F}|c)$
• Selecting function query $\mathcal{O}(|\mathcal{F}|c)$
• Optimizing the acquisition function $\mathcal{O}(c)$,

where $n$ is the number of observations at an iteration, $c$ is the number of discrete points, and $|\mathcal{F}|$ is the number of blackbox functions. In uniform grid discretization, if each dimension is divided into $m$ points, then the cardinality is $c=m^d$, where $d$ is the number of dimensions. Thus, dimensionality $d$ exponentially affects computational complexity when using uniform grid discretization.

Adaptive discretization may be able to mitigate the exponential factor of dimensionality, where effective dimension $d_\text{eff}\ll d$. However, high dimensionality leads to common challenges that go beyond computational complexity (of BILBO). For example, it is also known to reduce the effectiveness of Gaussian processes as observations become increasingly sparse.

4. How would you integrate unknown hard constraints in your framework? How would they impact the performance of BILBO?

We can use variational inference to approximate the Gaussian process posteriors while accounting for infeasible observations, e.g. approximating $p(c(x^*)\mid y(\mathbf{x}_1),c(\mathbf{x}_2)<0)$, where $y(\mathbf{x}_1)$ are noisy feasible observations and $\mathbf{x}_2$ are the observed infeasible points. While $c(\mathbf{x}_2)$ is not observed directly, we can condition on the information that $c(\mathbf{x}_2)<0$ since $\mathbf{x}_2$ is infeasible.

More observations might be required to model constraint boundaries accurately as infeasible observations become less informative. Nevertheless, we can still apply BILBO with the primary adaptation being in the estimation of the posterior belief, while further investigation is needed to assess the effectiveness for hard constraints in practice.

5. Do you agree that BILBO could be less efficient than other bilevel BO solutions such as [1, 2] if the lower objective is inexpensive to evaluate? If yes, can you comment on that? If no, can you justify?

The efficiency (in terms of wall-clock time) would depend on the computational cost of each iteration of BILBO versus the cost of evaluating the lower objective, as well as the optimality of lower-level estimates for nested methods such as [1, 2].

While it is possible for BILBO's computational cost to outweigh an inexpensive lower-level objective evaluation, BILBO still has advantages in scenarios with noisy observations or multiple lower-level solutions, which may be more common. Nested methods only solve for one solution for each lower-level optimization, and it can be suboptimal in these scenarios. On the other hand, BILBO manages the uncertainty of lower-level estimates in a principled way and allows for multiple lower-level estimates, possibly providing better lower-level estimates to reduce regret more effectively even if each iteration takes more time.

2. How does the immediate regret of BILBO evolves as a function of the wall-clock time?

On a Mac Studio with M2 Ultra, for the 2D BraninHoo+GoldsteinPrice experiment, the average time per BILBO iteration is 0.132s, which is 2x slower than TrustedRand and ~50x slower than Nested.

However, while the regret for Nested decreases faster than BILBO in the initial (~5) seconds, Nested's regret quickly plateaus due to suboptimal lower-level estimates of the multimodal lower-level objective. BILBO outperforms Nested subsequently as BILBO converges to a more optimal solution, supporting our point in the previous question above.

We hope these discussions on the efficiency, complexity and possible extensions of BILBO addressed your questions and will improve your opinion of our work.

Thank you for your detailed review and for appreciating the potential of our problem. We would like to address some questions and concerns raised.

1. Many lemmas (e.g., Lemma 4.4 and 4.6) should be a probabilistic bound because most of them depend on Corollary 4.2, but is often shown as a deterministic bound. Why? Just omitted?

The lemmas are all probabilistic bounds, which were omitted for brevity. We will clarify this in the next version of the paper.

2. Corollary 4.2 is for simultaneously holding on all possible x, z, h, and t? If so, it should be explicitly written.

Yes, we omitted it for brevity as it was already stated in the directly preceding Definition 4.1. We can add this in the next version of the paper.

3. In the experiments, \sum_h \in F r_h,t is used for the evaluation, but r_F,t can be negative according to (3.5). Is it correct?

Your interpretation is correct and (3.5) should be $r_F(\mathbf{x}_t, \mathbf{z}_t) ≜ \max(0, F(\mathbf{x}^*, \mathbf{z}^*) - F(\mathbf{x}_t, \mathbf{z}_t))$, which is what we had implemented in our experiments to avoid negating other regret components. Thank you for pointing this out, and we will update (3.5) in the next version of the paper. Lemma C.3. will still hold with minor edits to the proof.

4. How is the maximization of (4.6) solved?

In our experiments, we discretized the search space so the arg max over all the discrete points can be easily found.

For continuous domains, we can use a continuous representation for the trusted sets, e.g. with hyperrectangles, and use L-BFGS or SLSQP to optimize the acquisition function, similar to TorchBO.

The paper seems only discusses the discrete input setting. It should have been explicitly stated in the main text.

While we discretized the inputs in our experiments implementation, our theoretical analysis holds for continuous inputs, and it is possible to implement BILBO for continuous inputs in practical settings as discussed above.

W: Most of theoretical techniques are directly from well-known Srinivas et al (2010).

We would like to clarify that our theoretical techniques are not derived directly from Srinivas et al (2010), but only utilizes an adapted confidence bound in Corollary 4.2. We tackle bilevel challenges that differ from the single-objective, unconstrained optimization in Srinivas et al (2010).

In particular, we introduced a function query selection strategy with conditional reassignment, to select a function query for the decoupled setting, while accounting for the uncertainty of lower-level estimates. The conditional reassignment is also crucial for the exploration of the lower-level objective without repeated lower-level optimizations. These novel components address challenges associated with the lower-level optimization of bilevel problems, and are integral to the derivation of a sublinear regret bound for BILBO.

The abbreviation 'LL' is used in some figures, but not defined.

'LL' refers to lower-level. We will define this in the next version of the paper.

We hope our clarifications have addressed your questions and improved your opinion of our paper.

Thank you for your detailed review, and for recognizing the importance and practicality of our bilevel problem, clear and first theoretical guarantees in this setting, and good empirical support. We would like to address the questions raised.

Could you concisely highlight which specific aspects of BILBO are technically novel, beyond standard Bayesian optimization techniques (GP, confidence bounds)?

BILBO contains the following novel contributions to tackle unique challenges in bilevel Bayesian optimization where the upper-level optimization is constrained by lower-level solutions:

1. Formulation of the trusted set of optimal lower-level solutions $\mathcal{P}^+_t$ based on lower-level estimates, where we showed that points in the set have lower-level objective regret bound. This reduces the search space and is a key step towards the derivation of regret bound for BILBO.

2. Function query selection strategy with conditional reassignment of query point. Our function query strategy includes a term for the uncertainty of lower-level estimates, which corresponds to the additional difficulty from lower-level optimization that is not present in standard optimization. We also introduced the conditional reassignment as a way to explore the lower-level objective without the repeated lower-level optimization found in many bilevel Bayesian optimization methods.

How does BILBO practically handle scalability to higher-dimensional problems, given the reliance on discretization?

One way is via adaptive discretization, which can reduce the effective dimension.

Also, while we had discretized the problems in our experiments, BILBO does not require discretization of continuous inputs. A scalable BILBO implementation for continuous problems could contain a continuous representation of the trusted sets, e.g. with hyperrectangles, and use L-BFGS or SLSQP to optimize the acquisition function, similar to TorchBO.

We hope our clarifications on the novel aspects of our work and scalability discussions addressed your questions and will improve your opinion of our paper.