Pith. sign in

REVIEW 4 major objections 5 minor 2 cited by

Bayesian Optimization of Bilevel Problems

T0 review · 4 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Bilevel black-box optimization can be much more sample-efficient by modeling both levels with one shared Gaussian process and learning a single lower-level response map instead of re-solving the lower level for every upper-level candidate.

desk verdict Solid incremental BO-for-bilevel work with an honest appendix, but the headline efficiency claim is weakened by a closed-loop response-map assumption and missing baselines. read the letter →

arxiv 2412.18518 v1 pith:74GYG5BX submitted 2024-12-24 cs.LG math.OC

Omer Ekmekcioglu , Nursen Aydin , Juergen Branke This is my paper · ORCID
classification cs.LGmath.OC
keywords bileveloptimizationBayesianGaussianprocessesmulti-tasklearningknowledgegradientresponsemapblack-boxsampleefficiency
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes BILBAO, a Bayesian optimization framework for bilevel problems in which both the upper- and lower-level objective functions are black boxes and expensive to evaluate. Instead of re-solving the lower-level problem from scratch for every candidate upper-level action, BILBAO models both functions as Gaussian processes over the joint space of upper- and lower-level decisions and learns the lower-level response map once, transferring information across sub-problems. A new acquisition function, REVI, targets lower-level queries at regions that matter for the upper level. If the framework works as reported, it would cut the total number of expensive evaluations needed to find high-quality bilevel solutions.

What carries the argument

The machinery is the estimated lower-level response map $\Phi^n(x_u) = \arg\max_{x_l} \mu_l^n(x_u, x_l)$, computed by optimizing the lower-level GP posterior mean with L-BFGS-B restarts, together with the REVI acquisition function (a task-weighted knowledge gradient) that selects lower-level queries by averaging KG over a Thompson-sampled set of promising upper-level actions. The response map couples the two GPs: the upper level is optimized over the restricted surface $F^n_\Phi(x_u) = F^n(x_u, \Phi^n(x_u))$, and REVI steers lower-level evaluations to shrink the map where the upper level cares most.

What would settle it

Run BILBAO on a synthetic bilevel problem with a known, strongly multimodal lower-level response map, such as two crossing modes whose heights swap as $x_u$ varies, and compare the final returned upper-level solution against the true bilevel optimum; if the surrogate-smoothed map misses the true mode at the returned $x_u$, the algorithm fails despite a large budget.

Watch

Extended reading notes

Core claim

The core claim is that a bilevel problem with two expensive black-box functions can be solved far more sample-efficiently by treating it as a coupled pair of Gaussian-process learning tasks rather than as a sequence of independent lower-level optimizations. BILBAO maintains $\mathrm{GP}_U$ over $F(x_u, x_l)$ and $\mathrm{GP}_L$ over $f(x_u, x_l)$, derives an estimated response map $\Phi^n(x_u) = \arg\max_{x_l} \mu_l^n(x_u, x_l)$, and then optimizes the upper-level objective restricted to that map. Lower-level sampling is driven by REVI, which weights knowledge-gradient gains at upper-level points that Thompson sampling identifies as promising. The experiments report faster decline of optimality and action gaps than the benchmark that solves the lower level fresh for each upper-level point.

Load-bearing premise

The load-bearing premise is that maximizing the lower-level Gaussian process's posterior mean gives a lower-level response map close enough to the true optimal response that the upper-level search is not misled.

Editorial extensions

If this is right

  • If BILBAO's empirical claims hold, expensive bilevel applications such as gas-market modeling and adversarial network design become tractable with far fewer function evaluations than per-candidate lower-level solving.
  • The joint-space GP design means lower-level data collected for one upper-level action improves the response estimate for nearby actions, so the total evaluation budget no longer grows multiplicatively with the number of lower-level iterations per upper-level point.
  • REVI gives a principled rule for spending lower-level budget where the upper level is most likely to act, which should be useful in any bilevel problem where the response map is expensive and only partially learnable.
  • The reported sensitivity of the benchmark to its lower-level budget, contrasted with BILBAO's stable performance, implies that users can rely on a single configuration rather than hand-tuning the inner-loop budget.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper does not analyze what happens when the lower level is multimodal or discontinuous; a natural extension is a response-map estimator that keeps multiple modes rather than a single posterior-mean maximizer.
  • Casting bilevel optimization as multi-task BO suggests a transfer-learning extension: one lower-level function shared across several upper-level objectives could be solved jointly with a single $\mathrm{GP}_L$, amortizing the cost of learning the response map.
  • A testable extension is to compare BILBAO against semi-black-box baselines where the lower level is known and solvable; if BILBAO remains competitive, joint GP modeling could substitute for exact lower-level solvers in some applications.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper proposes BILBAO, a Bayesian optimization framework for bilevel problems where both upper- and lower-level objectives are black-box and expensive. Upper and lower-level functions are modeled with separate GPs over the joint decision space, and the lower-level response map Phi(x_u) is estimated by maximizing the lower-level GP posterior mean. The upper-level is optimized by Thompson sampling of the restricted posterior mean F(x_u, Phi(x_u)). The paper introduces REVI and REVITS acquisition functions for lower-level sampling, which weight the lower-level query by a set of Thompson-sampled important upper-level points. The algorithm is compared against a from-scratch lower-level BO benchmark on two 2D and four 4D synthetic problems, and the paper reports optimality gaps over evaluation budget.

Significance. If the empirical claims hold, BILBAO addresses a real gap: existing BO bilevel methods either assume a known lower level or solve the lower level from scratch, which is sample-inefficient. The joint GP modeling and the REVI/REVITS acquisition functions are a reasonable instantiation of multi-task BO for this problem, and the authors are commendably transparent in the appendix about the non-convergence of action-gap metrics. The absence of theoretical guarantees and the lack of released code are not fatal for an empirical paper, but the evidence as presented does not yet fully support the claim of 'highly sample-efficient and outperforms existing methods' because of the oracle-based evaluation and limited benchmark budgets.

major comments (4)
  1. [Section 4, optimality gap definition] The reported optimality gap is computed with the true lower-level response Phi*(x_u), while all internal decisions (Algorithm 2, lines 8-9 and 20, and Equation 5) use the estimated response Phi_n(x_u). The appendix (Figures 5-6) explicitly shows that the action gap over the domain does not converge and that the action gap at the optimal upper-level solution 'seems not fully confirmed' to decrease. This means the headline curves can look good even when the algorithm's internal model at the returned point is inaccurate. Please report the optimality gap evaluated with the internal estimate F(x_u^n, Phi_n(x_u^n)) and track the action gap at the returned solution; this would directly test whether BILBAO actually knows the returned solution is good.
  2. [Sections 4.1-4.2, benchmark comparison] The benchmark algorithm is allocated only M=4 or M=2 lower-level BO iterations per upper-level point in the 2D tests and M=10 or M=5 in the 4D tests, and the paper explicitly does not implement the re-optimization step recommended by Wang et al. (2021). These budgets are very small for a from-scratch lower-level solver, so the comparison may be systematically handicapped. Please also run the benchmark with a larger lower-level budget (e.g., comparable to BILBAO's lower-level evaluations) or with the final re-optimization, and report those results.
  3. [Section 4, statistical analysis] The comparison reports means and standard errors over only 10 runs and no significance tests. The claim that BILBAO 'outperforms existing methods' and 'converges faster' is load-bearing; please provide paired statistical tests (e.g., Wilcoxon signed-rank tests or bootstrap confidence intervals) at representative evaluation budgets, especially where the standard-error bands overlap as in the early iterations of Figures 4a and 4b.
  4. [Section 3, Equation (5), and Appendix] The acquisition function in Equation (5) weights lower-level queries by the set X_TS of Thompson-sampled upper-level points, which is itself derived from the upper-level GP that uses Phi_n. This closed loop means that if Phi_n is inaccurate near the true optimum, X_TS will tend to miss that region and lower-level evaluations will not be placed there, allowing the error to persist. The paper does not analyze this risk, and the non-converging action gap in the appendix is consistent with it. Please add a diagnostic experiment that breaks this loop, for example by seeding the lower-level GP with a few evaluations near the true response at x_u^*, and show whether the optimality gap or action gap improves.
minor comments (5)
  1. [Equation (6) and Appendix] The action-gap formula in Equation (6) and the similar expression in the appendix have unbalanced absolute-value brackets (e.g., |F(x_u^*, Phi^*(x_u^*) - F(x_u^*, Phi_n(x_u^*)|) and an inconsistent use of f versus F. Please correct these expressions.
  2. [Section 4] The GP kernel family, hyperparameter priors, and fitting details (e.g., Matern 5/2 with automatic relevance determination, length-scale bounds) are not specified; please state them for reproducibility.
  3. [Section 4.1] The test functions are said to be normalized to unit bounds, but the direction of optimization (maximization vs minimization) for Six-Hump Camel, Branin, and Dixon-Price is not stated. Since the optimality gap is an absolute value, please clarify whether the functions are negated to formulate a maximization problem.
  4. [Algorithm 2] Line 13 of Algorithm 2 uses the notation F^{n+1}_Phi before it is defined; earlier in the text and in line 7 the restricted sample path is denoted F^n_Phi. Please align the notation or define the superscripted version.
  5. [Figure 2] Figure 2 is discussed only globally; the individual subplots (a)-(f) and the markers (red cross, yellow star, red star) are not systematically described. Please annotate the subplots or refer to them individually in the text.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the GPs are fitted to direct function evaluations and the lower-level response map is an estimated surrogate, not a fitted input; self-citations are prior-work references and not load-bearing.

full rationale

BILBAO's derivation chain is self-contained in the sense that no target result is used to fit a parameter and then renamed as a prediction. The upper-level GP is updated with direct evaluations of F at (x_u, Phi(x_u)) and the lower-level GP with direct evaluations of f at (x_u, x_l), as stated in Algorithm 2 (lines 10-11 and 16-17). The response map Phi is computed by optimizing the lower-level posterior mean ('for a given point x_u, we solve the optimization problem x*_l(x_u) = arg max_{x_l} mu_n(x_u, x_l) using L-BFGS-B with 30 restarts'), which is a surrogate estimate, not an input that already encodes the final objective value. REVI and REVITS use the upper-level model only to prioritize lower-level locations; Equation 5 weights KG terms by Thompson-sampled upper-level candidates, and no fitted constant is later reported as a prediction. The paper's optimality-gap metric evaluates proposed points with the true best response Phi*, which is the correct leader's objective and is not circular. The authors cite prior work by co-author Branke (Pearce & Branke 2018 for REVI; Ungredda et al. 2022 for KG variants), but these are published methods used as components, and the central contribution does not reduce to them. The appendix admits that the action gap at the optimum 'seems not fully confirmed' to decrease (Figures 5-6); this is a convergence/accuracy limitation, not circularity, because the reported success curves are not fed back into the model. Overall, no equation or fitted parameter reduces to its own input, so the paper is not circular. The score reflects only the presence of minor self-citations and the appendix's acknowledged caveat about response-map accuracy, neither of which is load-bearing circularity.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The method introduces no invented physical entities. It relies on standard GP machinery, on REVI and KG theory from prior work, and on two load-bearing heuristics: the response map is the maximizer of a GP posterior mean found by L-BFGS-B, and the interest set comes from upper-level Thompson sampling. Several hyperparameters, including k, discretization sizes, restarts, and budget splits, are set by hand and affect the reported performance.

free parameters (5)
  • k (number of interest points) = 10
    Set by hand for all experiments; controls the size of X_TS used in REVI and REVITS acquisitions (Section 4).
  • Lower-level discretization size |X_L^MC| = 150 (2D), 250 (4D)
    Used in the discrete KG computation of REVI (Equation 3, Section 4).
  • L-BFGS-B restarts for response map = 30
    Used to optimize the lower-level posterior mean when computing Phi(x_u) (Section 4).
  • Sobol sample counts for Thompson sampling = 1024 (2D), 2048 (4D)
    Used for the upper-level Thompson sampling (Section 4).
  • Budget allocation = 2D: 10 init each, 80 upper, 80 lower; 4D: 20 init each, 100 upper, 100 lower
    Experimental budget split; the performance comparison depends on it.
assumptions (5)
  • domain assumption Both upper and lower objective functions are expensive black boxes; only box constraints are considered.
    Section 2.1 simplifies the general bilevel problem to box-constrained problems, which limits the scope.
  • domain assumption Gaussian process priors and their fitted hyperparameters provide calibrated uncertainty estimates.
    Kernel hyperparameters are fit by maximum likelihood in BoTorch; no validation of calibration is given.
  • standard math REVI and KG theory from Pearce and Branke (2018) is correct and its Monte Carlo discretization converges.
    Equation 3 uses discrete KG; the paper relies on prior work for its validity.
  • ad hoc to paper The maximizer of the lower-level GP posterior mean, found by L-BFGS-B with 30 restarts, is a good estimate of the true lower-level response.
    Section 3 computation of Phi; no error bound or consistency guarantee is provided.
  • ad hoc to paper The set X_TS of upper-level Thompson-sampled maxima represents the important regions of the upper-level problem.
    Used to weight REVI and REVITS; no theoretical justification.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Bayesian Optimization of Bilevel Problems." pith.science (2026). https://pith.science/paper/74GYG5BX

@misc{pith2026241218518,
  author       = {Pith},
  title        = {Pith review of: Bayesian Optimization of Bilevel Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/74GYG5BX}},
  note         = {Machine review of arXiv:2412.18518}
}
read the original abstract

Bilevel optimization, a hierarchical mathematical framework where one optimization problem is nested within another, has emerged as a powerful tool for modeling complex decision-making processes in various fields such as economics, engineering, and machine learning. This paper focuses on bilevel optimization where both upper-level and lower-level functions are black boxes and expensive to evaluate. We propose a Bayesian Optimization framework that models the upper and lower-level functions as Gaussian processes over the combined space of upper and lower-level decisions, allowing us to exploit knowledge transfer between different sub-problems. Additionally, we propose a novel acquisition function for this model. Our experimental results demonstrate that the proposed algorithm is highly sample-efficient and outperforms existing methods in finding high-quality solutions.

Figures

Figures reproduced from arXiv: 2412.18518 by the authors.

Figure 1
Figure 1. Camel-Branin Tests fails to provide accurate solutions, the resulting suggested solutions can be quite poor, as demonstrated in Benchmark 2. Figures 1b and 3b display the decrease in action gap over evaluations. The action gap stabilizes at some point for both algorithms as they only focus on the points that improve the region of interest. Rather than learning the entire map, the algorithms concentrate on a fraction… view at source ↗
Figure 2
Figure 2. Upper-level restricted posterior mean, µ n(xu, Φ n(x)), for the Camel-Branin test in different iterations. 11 [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Dixon-Branin Tests In the calculation of REVI and REVITS, similar to the 2D tests, we construct the set XT S from 10 upper-level decision points and use 250 points to discretize the lower-level action space. The test results for SMD1 through SMD4 are shown in Figures 4a to 4d. For all functions, both BILBAO and BILBAO-TS converge faster than the benchmarks. In Figure 4d, we observe that the benchmark becomes stuck a… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: SMD optimality gap logscaled 12 [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: Action gaps for the SMD functions 19 [PITH_FULL_IMAGE:figures/full_fig_p019_5.png]
Figure 6
Figure 6. Figure 6: Action gaps for the SMD functions only at the optimum [PITH_FULL_IMAGE:figures/full_fig_p020_6.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. BILBO: BILevel Bayesian Optimization

    cs.LG 2025-02 reject novelty 7.0 of 10

    BILBO is a single-query-per-round Bayesian optimization method for bilevel problems that uses confidence-bound trusted sets to bound lower-level suboptimality.

  2. Exploiting Separability in Multi-Scale Grey-Box Bayesian Optimization

    cs.LG 2026-08 conditional novelty 5.0 of 10

    Bilevel Bayesian optimization that optimizes only black-box variables and solves the known white-box subproblem exactly reports 11x to 10^8x lower regret than full-space BO on 13 separable grey-box benchmarks.

Reference graph

Works this paper leans on

3 extracted references · 1 canonical work pages · cited by 2 Pith papers

  1. [1]

    S., Krempser, E

    Angelo, J. S., Krempser, E. & Barbosa, H. J. (2013), Differential evolution for bilevel programming, in ‘IEEE Congress on Evolutionary Computation’, pp. 470–477. Angelo, J. S., Krempser, E. & Barbosa, H. J. (2014), Differential evolution assisted by a surrogate model for bilevel programming problems, in ‘IEEE Congress on Evolutionary Computation’, pp. 178...

    arXiv 2013

  2. [32]

    URL: https://proceedings.neurips.cc/paper_files/paper/2019/file/7876acb66640bad41f1e1371ef30c180- Paper.pdf Chen, L., Liu, H.-L., Tan, K. C. & Li, K. (2022), ‘Transfer learning-based parallel evolutionary algorithm framework for bilevel optimization’, IEEE Transactions on Evolutionary Computation 26(1), 115–129. Colliandre, L. & Muller, C. (2023), ‘Bayesi...

    work page arXiv 2022

  3. [48]

    J., Funcke, L., Hartung, T., Jansen, K., Kühn, S., Müller, K.-R., Stornati, P., Kessel, P

    Nicoli, K., Anders, C. J., Funcke, L., Hartung, T., Jansen, K., Kühn, S., Müller, K.-R., Stornati, P., Kessel, P. & Nakajima, S. (2023), Physics-informed bayesian optimization of variational quantum circuits, in A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt & S. Levine, eds, ‘Advances in Neural Information Processing Systems’, V ol. 36, Curran Asso...

    arXiv 2023

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.