BILBO: BILevel Bayesian Optimization
Ruth Wan Theng Chew, Quoc Phong Nguyen, Bryan Kian Hsiang Low · 2025
Read BILBO: BILevel Bayesian Optimization by Ruth Wan Theng Chew, Quoc Phong Nguyen, Bryan Kian Hsiang Low (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-02121.txt.
Introduction
Ruth Wan Theng Chew, Quoc Phong Nguyen, and Bryan Kian Hsiang Low present BILBO, a Bayesian optimizer for two-level problems with black-box parts. Their paper from twenty twenty-five explains the shape: an upper problem whose feasible set is set by the lower problem's best replies. Such stacks fill real design work. Re-solving the lower level at each probe wastes samples, and guessed replies can mislead.
BILBO tunes both levels in one pass. Trusted sets from confidence bounds cap how far the lower reply can stray. One query per round is chosen with the lower level's doubt in mind. A conditional reassignment of the query stirs exploration where needed. Regret bounds hold for standard kernels. Tests on synthetic and real tasks back the design.
Catalog record
| CREATOR | Ruth Wan Theng Chew, Quoc Phong Nguyen, Bryan Kian Hsiang Low |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-02121
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
BILBO: BILevel Bayesian Optimization Ruth Wan Theng Chew, Quoc Phong Nguyen, Bryan Kian Hsiang Low Abstract Bilevel optimization is characterized by a two-level optimization structure, where the upper-level problem is constrained by optimal lower-level solutions, and such structures are prevalent in real-world problems. The constraint by optimal lower-level solutions poses significant challenges, especially in noisy, constrained, and derivative-free settings, as repeating lower-level optimizations is sample inefficient and predicted lower-level solutions may be suboptimal. We present BILevel Bayesian Optimization (BILBO), a novel Bayesian optimization algorithm for general bilevel problems with blackbox functions, which optimizes both upper- and lower-level problems simultaneously, without the repeated lower-level optimization required by existing methods. BILBO samples from confidence-bounds based trusted sets, which bounds the suboptimality on the lower level. Moreover, BILBO selects only one function query per iteration, where the function query selection strategy incorporates the uncertainty of estimated lower-level solutions and includes a conditional reassignment of the query to encourage exploration of the lower-level objective. The performance of BILBO is theoretically guaranteed with a sublinear regret bound for commonly used kernels and is empirically evaluated on several synthetic and real-world problems. 1 Introduction Many real-world problems involve hierarchical decision-making with two levels of optimization. Decisions made at the upper level affect lower-level optimization, while optimal lower-level solutions constrain decisions at the upper level. Bilevel optimization effectively models such hierarchical structures, enabling analysis of these interdependent problems. A simple example of bilevel optimization is in Figure 1 . Applications of bilevel optimization range from machine learning (e.g., hyperparameter optimization, meta-learning) to economic problems (e.g., pricing strategies, toll setting) ( Beck & Schmidt, 2021 ) . In energy management, energy providers determine optimal pricing strategies for electricity (upper level) while consumers optimize their electricity demands based on the pricing (lower level). Similarly, in investment, brokers set fees on different asset classes to maximize their revenues (upper level), while investors optimize their portfolios for expected returns and risk (lower level). Bilevel optimization has been applied in both cases ( Shu et al., 2018 ; Leal et al., 2020 ) , typically using a nested framework with linear solvers at the lower level. This approach may limit practical effectiveness but it is due to the inherent complexity of bilevel optimization. Even with only linear constraints and objective functions, the set of feasible solutions can be non-convex and non-continuous ( Kleinert et al., 2021 ) . Lower-level solutions that are \epsilon -feasible w.r.t. non-linear constraints may also lead to a solution arbitrarily far from the bilevel solution ( Beck et al., 2023 ) . (a) Upper-level objective (b) Lower-level objective Figure 1 : Example of bilevel optimization with upper-level variable \mathbf{x} and lower-level variable \mathbf{z} . The bilevel solution (blue cross) is constrained by lower-level (LL) solutions (yellow line) and differs from the non-bilevel solution (red cross). Classical approaches ( Bard & Falk, 1982 ; Bard & Moore, 1990 ) rely on simplifying linear or convex assumptions. More recently, meta-modeling methods employ surrogate models, such as BLEAQ ( Sinha et al., 2013 ) which uses quadratic approximations to map upper-level points to lower-level solutions. We focus on meta-modeling methods over gradient-based ones to tackle general bilevel problems which may contain noisy observations, derivative-free functions at both levels, constraints and discrete variables. Bayesian optimization (BO), a popular meta-modeling method, has been employed in a nested framework for bilevel optimization ( Kieffer et al., 2017 ) . The nested framework optimizes the upper level via BO while separately optimizing the lower level at each upper-level query point. However, these repeated lower-level optimizations are sample inefficient and often assume the presence of gradients. Contributions. We propose BILevel Bayesian Optimization (BILBO), a novel BO algorithm for general bilevel problems with blackbox functions and constraints, where both levels are optimized simultaneously unlike existing nested bilevel BO frameworks. This adds new complexities, such as the potential lower-level suboptimality of the query and the uncertainty of estimated lower-level solutions. To tackle these challenges, we introduce key components of BILBO: • Confidence-bounds based trusted sets to reduce search space with theoretical guarantees. In particular, sampling our trusted set of lower-level solutions bounds lower-level objective regret, effectively bounding lower-level suboptimality for upper-level optimization. • Function query strategy that includes the uncertainty of the estimated lower-level solution and a conditional reassignment of the query point for more effective lower-level objective evaluation. This balances exploiting estimated lower-level solutions with exploring to refine these estimates. We show that our strategy leads to an instantaneous regret bound on the query. We further show that BILBO has sublinear cumulative and simple regret bounds for commonly used kernels, and demonstrate its effectiveness empirically on several synthetic and real-world problems. The code is provided in https://github.com/chewwt/bilbo/ , and a notation table is in Appendix A . 2 Related Work Bilevel Bayesian optimization. Most existing bilevel Bayesian optimization methods, as mentioned in the introduction, apply BO only to the upper-level problem and rely on repeated lower-level optimizations at each upper-level query ( Kieffer et al., 2017 ; Islam et al., 2018 ; Wang et al., 2021 ) . Dogan & Prestwich (2023) introduced an acquisition function that conditions on lower-level solutions during upper-level optimization for information flow between both levels. However, these nested methods require gradient information to estimate or refine lower-level solutions, making them unsuitable for derivative-free bilevel problems. Fu et al. (2024) provided theoretical guarantees for a nested bilevel framework with stochastic gradient descent at the lower level and BO at the upper level. The reliance on lower-level gradients means the analysis does not extend to general derivative-free bilevel problems as well. In contrast, our proposed method is capable of handling blackbox, derivative-free bilevel problems, and our theoretical analysis is applicable to these settings. An exception to the nested framework is a very recent parallel work by Ekmekcioglu et al. (2024) on arXiv. However, it has no theoretical guarantees and cannot handle constraints, unlike our proposed algorithm. Constrained Bayesian optimization. Several constrained BO algorithms have been proposed ( Gardner et al., 2014 ; Gelbart et al., 2014 ; Hernández-Lobato et al., 2016 ; Eriksson & Poloczek, 2021 ; Takeno et al., 2022 ) . In particular, Xu et al. (2023) and Nguyen et al. (2023) both introduced confidence-bound based optimistic estimations of the feasible set, with the former providing an infeasibility declaration scheme and the latter including a function query strategy for decoupled settings. These feasible set estimations guide sampling toward probable feasible points, improving sample efficiency. Compared to constrained optimization, bilevel optimization presents additional challenges due to the need to optimize a separate lower-level problem, where the optimal solutions are unknown and often estimated suboptimally. Comparison to other optimization problems. While some optimization problems, such as robust optimization ( Bogunovic et al., 2018 ; Kirschner et al., 2020 ) and composite objectives optimization ( Astudillo & Frazier, 2019 ; Li & Scarlett, 2024 ) , respectively involve an additional random variable and composite objective function, they remain single-level problems. In contrast, bilevel optimization involves a two-level hierarchical structure, where the upper-level is constrained by lower-level solutions, making it fundamentally different from these other settings. 3 Preliminaries Bilevel optimization. Let F and f , respectively be the upper- and lower-level black-box objective function, where F,f:\mathcal{X}\times\mathcal{Z}\rightarrow\mathbb{R}