Research map / Learning theory and algorithms / Combinatorial and search optimization
BILBO: BILevel Bayesian Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BILBO, a Bayesian optimization method that jointly optimizes upper and lower bilevel levels via confidence-bound trusted sets and a conditional query reassignment, with sublinear regret bounds and experiments on synthetic and real-world bilevel problems.
Problem
Bilevel optimization with noisy, constrained, derivative-free blackbox functions at both levels, where repeated lower-level optimization in nested BO is sample inefficient and predicted lower-level solutions may be suboptimal.
Approach
Optimizes both levels simultaneously without nested lower-level optimization by sampling from GP upper-confidence-bound trusted sets of feasible and (estimated) optimal lower-level solutions, selecting one function per iteration, and conditionally reassigning the lower-level query point to the estimated optimum when its uncertainty is larger.
Key results
- On BraninHoo+GoldsteinPrice, BILBO converges to the optimal bilevel solution within 150 queries while Nested and TrustedRand converge much more slowly.
- On SMD2 BILBO outperforms both TrustedRand and Nested; on SMD6 BILBO has the smallest regret after around 250 steps; on SMD12 it converges faster than TrustedRand.
- Theory: sublinear cumulative regret bound R_T <= sqrt(4T|F| beta_T max C_h gamma_{h,T}) for SE and Matern kernels; results averaged over 5 runs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BILBO instead of TrustedRand or Nested | Bilevel optimization · BraninHoo+GoldsteinPrice | instantaneous regret | Helped |
| Use BILBO instead of TrustedRand or Nested | Bilevel optimization · SMD2 | instantaneous regret | Helped |
| Use BILBO rather than Nested or TrustedRand | Bilevel optimization · SMD6 | instantaneous regret | Helped |
| Use BILBO instead of TrustedRand | Bilevel optimization · SMD12 | instantaneous regret | Helped |
| Use BILBO instead of TrustedRand or Nested | Bilevel optimization · Energy | instantaneous regret | Helped |
| Use BILBO instead of TrustedRand | Bilevel optimization · Chemical | instantaneous regret | Helped |
| Use Nested with a lower-level solver that predicts one solution per upper-level point | Bilevel optimization · SMD6 | instantaneous regret | Hurt |
| Use Nested with a lower-level solver on multimodal objectives and noisy observations | Bilevel optimization · BraninHoo+GoldsteinPrice | instantaneous regret | Hurt |
| Use BILBO on the Energy problem | BILBO · Energy | instantaneous regret | Mixed |
| Sample randomly from trusted sets rather than using BILBO's query strategy | TrustedRand · BraninHoo+GoldsteinPrice | instantaneous regret | Hurt |
Surprising findings
- Nested is unable to handle multiple lower-level optimal solutions on SMD6 because it predicts only one lower-level solution per upper-level point.
- On the energy problem the surrogate failed to model a large discontinuity in the lower-level objective, leading to a suboptimal lower-level prediction.
Limitations
- Discretized search space; scalability to high-dimensional and continuous domains is not addressed.
- Models upper-level objective over the joint space X x Z, which is memory-inefficient; the Nested baseline cannot handle constraints so is not compared on constrained problems.
- Energy experiment shows regret inflated by lower-level discontinuities and noise.
Experimental setup
Datasets: BraninHoo GoldsteinPrice SMD2 SMD6 SMD12 Energy market (PyPSA simulation) Chemical process simulator (DME carbonylation)
Benchmarks: BraninHoo+GoldsteinPrice SMD2 SMD6 SMD12 Energy Chemical
Metrics: instantaneous regret (sum over functions) cumulative regret simple regret
Baselines: TrustedRand Nested
Builds on: GP-UCB constrained Bayesian optimization with confidence-bound feasible sets BLEAQ
Closest papers by meaning
- qNBO: quasi-Newton Meets Bilevel Optimization (ICLR 2025 · similarity 0.87)
- TSP: A Two-Sided Smoothed Primal-Dual Method for Nonconvex Bilevel Optimization (ICML 2025 · similarity 0.87)
- Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems (NeurIPS 2026 · similarity 0.87)
- A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness (ICML 2024 · similarity 0.87)
- A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization (NeurIPS 2025 · similarity 0.86)
- Double Momentum Method for Lower-Level Constrained Bilevel Optimization (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.