BILBO: BILevel Bayesian Optimization

We sincerely appreciate your detailed feedback and we have incorporated all minor edits suggested into the updated paper. Thank you for recognizing our proposed algorithm as the first theoretically guaranteed approach for bilevel Bayesian optimization, our comprehensive proofs, the clarity of our paper, and the well-described practical behavior in our figures.

We would like to address the following concerns:

The confidence bound-based approach for complex structured optimization problems have already been extensively studied in the BO field (e.g., robust BO [1,2,3], constrained BO [4,5], and composite objectives [6, 7], etc.). Specifically, it seems that the proposed algorithm can be constructed by combining the extended regret definition of [4] and the sampling for potential solutions based on a confidence set. As far as I see, the non-trivial points of the proposed algorithm construction are the following:

1. The construction of $\mathcal{P}_t$ with $\bar{\mathbf{z}}$ (Eq. 3.4, 3.5)...
2. Reassignment of $\mathbf{z}_t$ based on Lemma 3.6.

Furthermore, uncertainty-based input selection by fixing one input, such as the procedures of point 2, is also commonly leveraged to upper bound the instantaneous regret in the BO field (e.g., [2,3]).

[2] Kirschner, Johannes, et al. "Distributionally robust Bayesian optimization." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.

[3] Iwazaki, Shogo, Yu Inatsu, and Ichiro Takeuchi. "Mean-variance analysis in Bayesian optimization under uncertainty." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.

[4] Nguyen, Quoc Phong, et al. "Optimistic Bayesian Optimization with Unknown Constraints." The Twelfth International Conference on Learning Representations. 2023

We appreciate your recognition of trusted set $\mathcal{P}^+_t$ and reassignment of $\mathbf{z}_t$ during function query selection as non-trivial components of our work. However, we would like to clarify that our proposed algorithm tackles challenges in bilevel Bayesian optimization that have not been studied in other BO field and is not a straightforward extension of [4].

Firstly, in bilevel optimization, the upper-level optimization is constrained by the unknown set of optimal lower-level solutions. This poses unique challenges not seen in robust BO, constrained BO or composite objectives BO, where they only tackle single level problems. Bilevel optimization algorithms have to consider the optimality of the estimated lower-level solutions, as querying upper-level functions at suboptimal lower-level solutions is likely largely uninformative.

The trusted set of optimal lower-level solutions $\mathcal{P}^+_t$ was carefully designed to bound lower-level objective regret $r_f$ for points in the set. The regret bound is important to ensure that points sampled from this set are useful for upper-level querying, without requiring separate global optimization of the lower-level problem. This is a novel approach to bilevel Bayesian optimization and significantly more sample efficient than existing bilevel Bayesian optimization works [8, 9] which require separate global optimization of the lower-level problem at every upper-level query point.

Secondly, the function query selection strategy which involves a conditional reassignment of lower-level query point $\mathbf{z}_t$ is another signification contribution of our work. The conditional reassignment of $\mathbf{z}_t$ to $\bar{\mathbf{z}}_t$ for lower-level objective function query is designed to manage uncertainty of estimated lower-level solutions. The need for reassignment arises because we do not carry out global optimization of lower-level problems at any upper-level point. This reassignment is used to bound the instantaneous regret of lower-level objective at the query point, and is specific to the challenge of bilevel optimization being constrained by optimal lower-level solutions.

It differs from [2, 3] which has an additional unknown/uncontrollable variable $\mathbf{w}$ represented by a probability distribution. We do not fix $\mathbf{z}_t$ or sample $\mathbf{z}_t$ from another distribution. Both $\mathbf{z}_t$ and $\bar{\mathbf{z}}_t$ are selected based on confidence bounds on the objective functions, and we aim to find the optimal bilevel solution $\mathbf{x}^*, \mathbf{z}^* \in \mathcal{X} \times \mathcal{Z}$ whereas the optimal solution in [2, 3] is $\mathbf{x}^*$ and obtained via an expectation over $\mathbf{w}$. Importantly, since the problem contexts are different, the proposed algorithms in [2, 3] cannot be used to solve our bilevel optimization problem. We would appreciate if you could clarify on perceived similarities of reassignment of $\mathbf{z}_t$ to [2, 3].

Thank you for your reply.

To my understanding, the existing robust BO problem setting [1] is a special case of this paper's setting Eq. (2,1)-(2.3) when the lower level objective function $f(x, z)$ is also defined based on the upper-level objective function ($f(x, z) := -F(x, z)$), and there is no-constraint functions.

While it is technically possible to formulate the robust BO problem setting [1] as a special case of bilevel optimization as you have stated, this formulation is not particularly meaningful. Solving the lower-level problem can directly contribute to the upper-level solution since the objective functions have the same blackbox component. This removes a challenge of bilevel optimization where suboptimal lower-level solutions are largely uninformative for the upper-level optimization. Also, many bilevel problems such as on toll setting and energy market optimization cannot be framed as this special case, and thus cannot be solved by robust BO but can be solved by our bilevel Bayesian optimization. Hence, our work on bilevel Bayesian optimization is a significant contribution.

(e.g., I believe that existing constraint BO [2] can easily adapt the decouple setting by considering the similar regret formulation as Eq. (2.4)). If my understanding is wrong, I would like the author to point out my misunderstanding and clarify any technical challenge that the author solves to adapt the decouple setting in a bi-level optimization setting.

Without the complications of the lower-level problem, constrained BO [2] can adapt the decoupled settings by considering the upper-level objective and constraint regret formulation as you have pointed out. Indeed, this has been done in [4].

However, a key technical challenge for the decoupled setting in bilevel optimization is in reducing the lower-level objective regret at the query point. We found out that simply selecting function queries based on estimated regrets at the query point is insufficient to reduce lower-level objective regret, as the query point is selected based on the upper-level objective function. Only observing the lower-level objective at these query points will not reduce the uncertainty of estimated lower-level solutions, since these query points were sampled from the trusted set $\mathcal{P}^+_t$ and may not be the estimated optimal lower-level solutions.

Thus, for the lower-level objective function query, we reassign $\mathbf{z}_t$ to be the estimated lower-level solution $\bar{\mathbf{z}}_t(\mathbf{x}_t)$ when $\sigma_{f,t-1}(\mathbf{x}_t, \bar{\mathbf{z}}_t(\mathbf{x}_t)) \geq \sigma_{f,t-1}(\mathbf{x}_t, \mathbf{z}_t)$ (as in Eq. (3.8), latex formatting not working well here). This is related to the presence of both uncertainty terms in the estimated lower-level objective regret (Def. (3.7)), and we showed that our conditional reassignment will lead to a query point that can lower the estimated lower-level objective regret more effectively and lead to an instantaneous regret bound on the query point (in proof of Lemma 3.8).

[4] Nguyen, Quoc Phong, et al. "Optimistic Bayesian Optimization with Unknown Constraints." The Twelfth International Conference on Learning Representations. 2023.

however, I recommend the author use a refined version of the upper bound of the maximum information gain in [3].

Thank you for your recommendation. We have revised the upper bound of the maximum information gain to that in [3] in the updated paper.

We hope these additional clarifications, especially on the technical challenges of bilevel optimization in the decoupled setting and our methods to tackle them, will improve your opinion of our paper.

Thank you for recognizing our novel approach to bilevel Bayesian optimization, the significance of the problem addressed, our infeasibility declaration, and theoretical sublinear regret bound. We appreciate your valuable review.

We would like to address the following concerns and questions:

This approach involves keeping track of a set of nearly optimal solutions for the lower-level problem. In low-dimensional cases, this can be managed through discretization. However, it likely becomes difficult to scale effectively to even moderately high-dimensional problems.

This is indeed a common challenge for existing works on Gaussian processes and Bayesian optimization which require maintenance of a set, where discretization is often used. The need to maintain a set of near-optimal lower-level solutions is integral to our approach as it enables joint optimization of upper- and lower-level problems and handles noisy observations of lower-level functions more effectively.

As we also pointed out in our future work section, possible approaches to scale to higher dimensions could be via sampling strategies like Latin Hypercube Sampling [1] for efficient point representation in high-dimensional spaces or using hyperrectangles to represent the trusted set efficiently [2].

[1] McKay, M. D., Beckman, R. J., & Conover, W. J. (2000). A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics, 42(1), 55-61.

[2] Eriksson, D., Pearce, M., Gardner, J., Turner, R. D., & Poloczek, M. (2019). Scalable global optimization via local Bayesian optimization. Advances in neural information processing systems, 32.

Have the authors considered a hybrid setting, where some parts of the bi-level problem are black-box while other parts are white-box with explicit expressions? I guess such problems also arise widely in practice.

White-box problems with explicit expressions are often inexpensive to compute. We can still apply our algorithm, evaluate white-box parts at every step and reduce the confidence interval to a point, since there will be no noisy observations.

We hope our responses have addressed your concerns and improve your opinion of our work.

I would like to thank the authors for the detailed responses. They addressed my concerns adequately. And I am happy to maintain my rating.

We appreciate your valuable review and thank you for recognizing BILBO’s simultaneous optimization of both levels, our theoretical analysis, our experiments demonstrating practical applicability of BILBO, and our clear and well-structured writing.

We would like to address the following concerns and questions:

While the algorithm is well-explained, the motivations for certain design choices, particularly the decoupled setting and the specific function query mechanisms ($\mathcal{F}$ and $h_t$), are not sufficiently discussed.

Can you explain more about the motivations for studying the decoupled setting? And the reasons to consider $\mathcal{F}$ and function query $h_t$ is the algorithm design and regret definition?

In a decoupled setting, only one function $h_t$ is selected from the set of functions $\mathcal{F}$ to query at each step. This can improve sample and cost efficiency by reducing evaluations on functions that are less informative or more expensive to query. In contrast, in a coupled setting, all functions are evaluated at every step, which can be unnecessary and expensive. Bilevel problems often have multiple objective and constraint functions which highlights the benefits of decoupled setting. Decoupled settings have been explored in some constrained Bayesian optimization works as well [1, 2, 3].

The function query selection is based on estimated regret comparison and a conditional reassignment for lower-level objective query. They were designed to lead to an instantaneous regret bound on the query point given by Lemma 3.8. In particular, the conditional reassignment is crucial to manage the uncertainty of the estimated lower-level optimal solution as we do not globally optimize the lower-level problem at any upper-level point unlike existing bilevel Bayesian optimization methods.

[1] Gelbart, M. A., Snoek, J., & Adams, R. P. (2014). Bayesian optimization with unknown constraints. arXiv preprint arXiv:1403.5607.

[2] Hern, J. M., Gelbart, M. A., Adams, R. P., Hoffman, M. W., & Ghahramani, Z. (2016). A general framework for constrained Bayesian optimization using information-based search. Journal of Machine Learning Research, 17(160), 1-53.

[3] Nguyen, Q. P., Chew, W. T. R., Song, L., Low, B. K. H., & Jaillet, P. (2023). Optimistic Bayesian Optimization with Unknown Constraints. In The Twelfth International Conference on Learning Representations.

A more detailed comparison with existing bilevel optimization methods, particularly those offering theoretical guarantees or practical performance benchmarks, would provide a clearer picture of BILBO’s relative strengths and weaknesses.

For regret bound in Theorem 3.9, the authors discussed the relationship to constrained Bayesian optimization in Nguyen et al. (2023), is there any existing bilevel BO regret result that can be compared with?

To the best of our knowledge, there are only two existing works on bilevel Bayesian optimization [4, 5], both of which do not provide theoretical guarantees, unlike BILBO. In addition, both existing works are not able to handle constraints while BILBO is able to. The performance benchmarks provided by both papers are based on the median converged fitness scores and median number of evaluations to convergence, with no indication on rate of convergence and confidence intervals, making it hard to compare directly.

[4] Kieffer, E., Danoy, G., Bouvry, P., & Nagih, A. (2017). Bayesian optimization approach of general bi-level problems. In Proc. Genetic and Evolutionary Computation Conf. Companion.

[5] Dogan, V., & Prestwich, S. (2023). Bilevel optimization by conditional Bayesian optimization. In Int. Conf. on Machine Learning, Optim., and Data Sci.

Including comparisons with state-of-the-art bilevel optimization algorithms, such as those from Kieffer et al. (2017) or Dogan & Prestwich (2023), would offer a more rigorous evaluation of BILBO’s performance.

In experiments, BILBO is compared with TrustedRandom and Nested. As described in Appendix C.1, the Nested baseline used a nested approach with SLSDP. But the related works mentioned, e.g. Kieffer et al. (2017); Dogan & Prestwich (2023) are not included. Can you compare it with the associated works directly? If not, can you explain the reasons that BILBO cannot compared with the related work?

We did not include direct comparisons with the two main related works [4, 5], as they did not provide sufficient implementation details or publicly available codes. We also found some potential errors in [5], where the calculation of mean conditional on optimal lower-level points seems to be incorrect. Both existing works use SLSQP for lower-level optimization, which we followed for our Nested baseline. Thus, the Nested algorithm in our experiments is a proxy to simulate the results of current methods to the best of our ability, and we believe this approach provides a reasonable benchmark given the constraints.

Thank you for appreciating our motivations for studying bilevel Bayesian optimization, the decoupled setting of our problem and our theoretical analysis and empirical experiments. We appreciate your valuable review and positive feedback on the clarity of our writing.

We would like to address the following concerns:

I have concerns on novelty of this submission ... I cannot find challenges that are unique to the bilevel Bayesian optimization, or I might have missed something. Please clarify this point.

The unique challenge in bilevel optimization is that the upper-level optimization is constrained by optimal lower-level solutions. The optimal lower-level solutions are unknown and requires optimization of a separate lower-level problem. A straightforward approach would be to globally optimize the lower-level problem at each upper-level query point, which is what existing Bayesian optimization-based approaches [1, 2] do. However, this is sample inefficient due to many unnecessary queries to the lower-level functions.

We proposed a trust-region-like approach that maintains trusted sets of feasible and optimal lower-level solutions with high probability, and queries upper-level points without having to globally optimize the lower-level problem at any step. To our knowledge, our work is also the first to provide theoretical analysis and bounds on bilevel Bayesian optimization of blackbox functions.

Our primary contributions include:

• Trusted set of optimal lower-level solution $\mathcal{P}^+_t$ to approximate unknown optimal lower-level solutions, a challenge unique to bilevel optimization. We showed that points sampled from the trusted set $\mathcal{P}^+_t$ have upper-bounded lower-level objective regret, meaning they are good candidates for upper-level querying without have to globally optimize the lower-level problem repeatedly.
• Function selection strategy involving comparison of estimated regrets and reassignment of lower-level query point given certain conditions. The reassignment is integral to manage uncertainties of the estimated lower-level solution, as we do not globally optimize the lower-level problem at any upper-level point. We showed that by following our function selection strategy at the query point, the instantaneous regret at the query point is upper bounded with high probability.

[1] Kieffer, E., Danoy, G., Bouvry, P., & Nagih, A. (2017). Bayesian optimization approach of general bi-level problems. In Proc. Genetic and Evolutionary Computation Conf. Companion.

[2] Dogan, V., & Prestwich, S. (2023). Bilevel optimization by conditional Bayesian optimization. In Int. Conf. on Machine Learning, Optim., and Data Sci.

First, functions in both levels are modelled by Gaussian process and then trusted regions are defined using confidence bounds. Then theoretical results are derived from Srinivas et al., 2010.

To clarify, our theoretical results are not derived directly from [3], but only utilizes an adapted confidence bound Lemma as stated in Corollary 3.2, and we had represented the cumulative regret bound in terms of maximum information gain following [3] to facilitate comparison. These are common approaches in Bayesian optimization and present in several works [4, 5].

The design of the trusted sets and derivation of regret bounds for these sets build on these confidence bounds, but are entirely original work to tackle bilevel challenges. In addition, many existing Bayesian optimization works do not consider the decoupled setting where one function is selected for querying, and [3]'s work was on a single-objective, unconstrained optimization. Our proposed function query selection strategy which includes a conditional reassignment, leads to an upper regret bound on the query point and is a novel approach that addresses challenges associated with lower-level optimization of bilevel problems.

[3] Srinivas, N., Krause, A., Kakade, S. M., & Seeger, M. (2009). Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995.

[4] Xu, W., Jiang, Y., Svetozarevic, B., & Jones, C. (2023, July). Constrained efficient global optimization of expensive black-box functions. In International Conference on Machine Learning (pp. 38485-38498). PMLR.

[5] Nguyen, Q. P., Chew, W. T. R., Song, L., Low, B. K. H., & Jaillet, P. (2023). Optimistic Bayesian Optimization with Unknown Constraints. In The Twelfth ICLR.

In Theorem 3.9, theoretical results are given based on $|\mathcal{F}|, |\mathcal{X}|, |\mathcal{Z}|$, so all of them must be finite, which put more restrictions on problem setting.

These are likely fair assumptions to make, especially in real-world problems, where $\mathcal{F}$ will be a set of known experiments or simulators to run, and domains of $\mathcal{X}$ and $\mathcal{Z}$ can be obtained from domain knowledge. We have also added the assumption of finite domains of $\mathcal{X}$ and $\mathcal{Z}$ in the preliminaries to be clear.

Thank you for finding our motivation of bilevel optimization clear and appreciating our extensive experiments. We appreciate your valuable review.

We would like to address the following concerns:

Unlike typical optimization studies focused on the computational complexity of local-search algorithms, this paper addresses statistical complexity, assuming exhaustive search over a function hypothesis space. Consequently, it diverges from the usual challenges associated with noisy, constrained, and derivative-free settings in continuous stochastic optimization, making direct comparisons with gradient-based methods inappropriate.

Line 68-69: why functions are modelled using Gaussian Process? And this assumption appears abrupt.

Gaussian process: notation is messy and discussion is hard to follow.

Our paper proposes bilevel optimization via Bayesian optimization, which is a global optimization algorithm commonly used in noisy and derivative-free settings. Gaussian processes are also commonly used to model functions in Bayesian optimization due to their probabilistic properties, and the Gaussian process notation and definition are standard and commonly found in Bayesian optimization literature [1, 2, 3]. Nevertheless, we shifted the closed-form posteriors to the appendix to enhance readability.

[1] Williams, C. K., & Rasmussen, C. E. (2006). Gaussian processes for machine learning (Vol. 2, No. 3, p. 4). Cambridge, MA: MIT press.

[2] Brochu, E., Cora, V. M., & De Freitas, N. (2010). A tutorial on Bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. arXiv preprint arXiv:1012.2599.

[3] Srinivas, N., Krause, A., Kakade, S. M., & Seeger, M. (2009). Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995.

At the beginning of Section 3, it is not clear what you exactly get from querying points.

Querying means to evaluate or observe a function at a specific point. This is also common terminology in Bayesian optimization [2].

Line 155 "trusted sets": in my first read, this was very confusing. I think the paper should have been much clearer about the interaction protocol, the fact that exhaustive search over hypothesis class is okay, and it is not going to be about convergence of local-search methods.

We do not do an exhaustive search over hypothesis class nor local-search methods. Our work is on Bayesian optimization with Gaussian processes as surrogate models, where we select a query point and function query at each step to efficiently find the optimal solution. We construct trusted sets using confidence bounds from Gaussian processes to iteratively reduce the search space.

Line 59-60: What is "information flow"? This is not a well-defined term.

In this context, we are using the term "information" informally. When optimization for each level is carried out separately, there is no information exchange (e.g. uncertainties) between upper- and lower-level problems.

Line 301-302: What is "information gain"? Define it precisely.

We have included the definition of maximum information gain in the preliminaries and its upper bound for commonly used kernels in the appendix of the updated paper.

We hope this clarifies and improves your opinion of our paper.