{"id":"91ce529e-d40e-49b3-87f2-23a4ad5299ba","arxiv_id":"2502.02121","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"BILBO is a single-query-per-round Bayesian optimization method for bilevel problems that uses confidence-bound trusted sets to bound lower-level suboptimality.","lead":"This paper introduces BILBO, a Bayesian optimization algorithm that solves bilevel problems by optimizing the upper and lower levels together instead of running repeated lower-level optimizations. It promises sublinear regret bounds in noisy, constrained, derivative-free settings, with experiments on synthetic and real-world problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma C.2's proof that (x*,z*) lies in P+_t relies on f(x*,z*(x*)) ≥ f(x*,\\bar z_t(x*)), but \\bar z_t(x*) may be infeasible and have larger true lower-level value, so the upper-level regret bound behind Theorem 4.9 is unsupported.","rationale":"The reader's weakest_assumption identifies the same load-bearing flaw: Lemma C.2's proof implicitly assumes the true optimal lower-level value dominates the value at the estimated UCB maximizer, yet that maximizer need not be feasible. I agree this is the central gap. The theorem's proof explicitly depends on (x*,z*) being in S+_t ∩ P+_t; without it, the argmax step in Lemma C.3 cannot bound the upper-level regret, and the chain leading to Theorem 4.9 breaks. The conditional reassignment issue is also real: after Eq. 4.8 the queried point may leave S+_t, so Lemmas 4.4 and C.3 no longer apply at the point whose regret Lemma 4.8 claims to bound. However, the Lemma C.2 failure is sufficient by itself to invalidate the central claim, so it is the most load-bearing concern. I am not raising a consensus-based objection; the issue is internal to the proof, and the empirical results and released code do not change this. I also do not think the empirical comparison ambiguity alone would warrant rejection absent the proof gap. Since the reader's rejection is based on the same unsupported central guarantee, I recommend no change to the verdict; a repaired proof would be needed for acceptance.","tokens_in":19376,"tokens_out":10477,"duration_ms":94319,"concrete_test":"Construct the finite instance X={x0}, Z={0,0.5,1}, lower constraint c(z)=z-0.5 ≥ 0, lower objective f(z)=-z, and any upper objective. Give the GP for c prior mean 0 and enough width that u_c,t(x0,0) > 0; give the GP for f prior mean 0, one noisy observation at z=0.5, and choose kernel hyperparameters so u_f,t(x0,0) > u_f,t(x0,0.5) while l_f,t(x0,0) > u_f,t(x0,0.5). Then z*(x0)=0.5, \\bar z_t(x0)=0, and f(x0,0)=0 > f(x0,0.5)=-0.5, so the inequality f(x*,z*) ≥ f(x*,\\bar z_t) in Lemma C.2 is false and (x0,0.5) ∉ P+_t. Recompute the proof of Lemma C.3 on this configuration: the step max over S+_t ∩ P+_t u_F ≥ u_F(x*,z*) fails, so the claimed upper-level regret bound is not established. Separately, test Eq. 4.8 by querying f at (x0,0) and checking whether upper-level constraint regret at that point is bounded by σ_f,t-1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The cumulative regret bound in Theorem 4.9 is derived from Lemma 4.8, which in turn uses Lemma C.3. Lemma C.3's only route to bounding r_F(xt,zt) is Lemma C.2, which claims the bilevel optimum (x*,z*) is in the candidate set S+_t ∩ P+_t. The proof of Lemma C.2 asserts u_f,t(x*,z*) ≥ f(x*,z*) ≥ f(x*,\\bar z_t(x*)) ≥ l_f,t(x*,\\bar z_t(x*)). The middle inequality requires the true optimal lower-level value at x* to dominate f at the UCB maximizer \\bar z_t(x*). But \\bar z_t(x*) is only required to satisfy u_c,t(x*,\\bar z_t) ≥ 0 for lower-level constraints; the point can be genuinely infeasible. Since the lower-level problem maximizes f over feasible z only, an infeasible point can have f(x*,\\bar z_t) larger than the feasible optimum f(x*,z*(x*)). Corollary 4.2 gives z*(x*) ∈ S+_lo,t and hence u_f(x*,\\bar z_t) ≥ u_f(x*,z*), but it gives no ordering of the true values. Consequently the inference (x*,z*) ∈ P+_t is invalid. For example, with f(x,z) = -z and lower-level constraint z ≥ 0.5, an unobserved infeasible point z = 0 has f = 0 > f(x,0.5) = -0.5 and can be the UCB maximizer. When this happens, max over S+_t ∩ P+_t of u_F may be below u_F(x*,z*), so Lemma C.3's bound r_F(xt,zt) ≤ 2β_t^{1/2}σ_F,t-1(xt,zt) does not follow. This gap is already present when no reassignment occurs, so the conditional reassignment is not the root cause. A separate gap is that Eq. 4.8 can move the query to \\bar z_t ∈ S+_lo,t \\ S+_t, where Lemma 4.4's constraint-regret bound and Lemma C.3's argmax identity no longer hold at the actually queried point; the proof of Lemma 4.8 silently applies those lemmas after reassignment. Both gaps sit in the proof chain of the headline regret claim; the first is the more fundamental one.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"BILBO proposes a Bayesian optimization algorithm for constrained bilevel problems in which both upper- and lower-level functions are black-box, noisy, and derivative-free. The algorithm builds two confidence-bound trusted sets, one for feasible points and one for approximately optimal lower-level solutions, selects a query by maximizing the upper-level UCB over their intersection, chooses a single function to observe in a decoupled manner, and may conditionally reassign the lower-level coordinate to the estimated lower-level maximizer. The paper claims an instantaneous regret bound, a sublinear cumulative regret bound (Theorem 4.9), and a simple regret bound (Lemma 4.10), and reports experiments on synthetic and real-world problems. The central theoretical claim is a no-regret guarantee with only one function query per round.","tokens_in":19854,"tokens_out":7623,"duration_ms":71011,"significance":"If the regret bound were valid, BILBO would be a meaningful contribution: it avoids repeated lower-level optimization, handles constraints and noise, works without gradients, and would provide sublinear cumulative regret for standard kernels. The empirical study covers varied problems, the code is released, and the paper identifies an interesting method for decoupled query selection. However, the proof of the central theorem contains a substantive gap in Lemma C.2, and a second gap arises from the conditional reassignment in Eq. (4.8). As written, the theoretical contribution is not established.","major_comments":[{"comment":"The proof asserts u_f,t(x*,z*) ≥ f(x*,z*) ≥ f(x*,\\bar z_t(x*)) ≥ l_f,t(x*,\\bar z_t(x*)), and uses this chain to conclude (x*,z*) ∈ P+t. The middle inequality is not justified. By Definition 4.5, \\bar z_t(x*) is the maximizer of u_f,t over the optimistic feasible set S+_lo,t(x*), which only requires u_c,t(x*,z) ≥ 0 for lower-level constraints. A point in S+_lo,t can be genuinely infeasible, and for such a point the true value f(x*,\\bar z_t(x*)) can exceed the true constrained optimum f(x*,z*(x*)). For example, with f(x,z) = -z and lower-level constraint z ≥ 0.5, an unobserved infeasible point z = 0 has f(x,0) = 0 > f(x,0.5) = -0.5 and can be the UCB maximizer. Consequently the inference (x*,z*) ∈ S+t ∩ P+t does not follow. This invalidates Lemma C.3's replacement of u_F,t(x*,z*) by max over S+t ∩ P+t, and therefore Theorem 4.9 and Lemma 4.10, both of which rely on Lemma C.3, are unsupported.","section":"Appendix C.3, Lemma C.2"},{"comment":"The conditional reassignment zt ← \\bar z_t(xt) can move the query outside S+t ∩ P+t. Lemma 4.4 bounds constraint regret only for points in S+t, and Lemma C.3 bounds the upper-level objective regret using the equality u_F,t(xt,zt) - l_F,t(xt,zt), which is only valid when (xt,zt) is the argmax in Eq. (4.6). After reassignment, neither premise holds: \\bar z_t(xt) need not satisfy the upper-level constraints, and the queried point is no longer the UCB maximizer over the trusted set. Thus even if Lemma C.2 were repaired, Lemma 4.8's instantaneous regret bound and Theorem 4.9 would still fail on rounds in which the reassignment occurs. The condition in Eq. (4.8) compares posterior standard deviations and gives no feasibility guarantee for the reassigned point.","section":"Section 4.3, Eq. (4.8) and Lemma C.3"}],"minor_comments":[{"comment":"The displayed definition of P+t has an unbalanced parenthesis: 'lf,t(x, ¯zt(x)}' should close with ')'.","section":"Definition 4.5"},{"comment":"The estimated lower-level solution \\bar z_t(x) is defined as an argmax over S+_lo,t(x); when S+_lo,t(x) is empty, this argmax is undefined. The paper should state how such upper-level points are handled, even though they cannot belong to P+t.","section":"Definition 4.5"},{"comment":"The comparison against TrustedRand is on a per-query basis even though BILBO queries one function per round while TrustedRand queries all functions. This is a reasonable sample-efficiency comparison, but it should be stated more explicitly, since wall-clock efficiency is only discussed in Appendix E.2.","section":"Section 5"}],"recommendation":"reject","confidential_remarks":"The gap in Lemma C.2 is load-bearing and does not appear to be a local fix: it undermines the no-regret claim that is the paper's main theoretical contribution. The empirical results and code are useful, but I do not think the manuscript can be accepted without a substantially different argument or additional assumptions. A resubmission that repairs or replaces the theoretical analysis would be worth considering."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this is a genuinely new algorithm for derivative-free bilevel Bayesian optimization, but the headline regret guarantee is not supported by the proof as written. I agree with the reader's REJECT, and the stress-test note correctly pinpoints the load-bearing break.\n\nWhat the paper does well: it optimizes both levels simultaneously without nested lower-level loops, builds trusted sets from confidence bounds to bound lower-level suboptimality, and queries only one function per iteration with a conditional reassignment rule. That is a real departure from the existing nested frameworks, and the experimental setup is reasonable, with code provided. The writing is clear and the authors are honest about limitations.\n\nThe soft spot is in the proof of Lemma C.2. It asserts f(x*, z*(x*)) ≥ f(x*, \\bar z_t(x*)), but \\bar z_t is the UCB maximizer over S+_lo,t, which can contain points that are infeasible for the true lower-level constraints. An infeasible point can have larger true f than the feasible optimum, so the inequality does not hold. The example with f(x,z) = -z and constraint z ≥ 0.5 is enough to show the mechanism. Because (x*, z*) may not lie in S+_t ∩ P+_t, the argmax step in Lemma C.3 cannot bound the upper-level regret, and Theorem 4.9 falls apart. This is not a minor technicality; it is the central justification for no-regret convergence.\n\nThere is a second, smaller gap: the reassignment in Eq. 4.8 can move the query outside S+_t, so the constraint-regret bound and the argmax identity no longer apply to the actually queried point. That one is easier to patch.\n\nNeither gap looks unfixable. You could restrict \\bar z_t to high-probability feasible points, add a violation term to the trusted-set condition, or constrain the reassignment to stay in S+_t. But as it stands, the proof does not go through.\n\nWho should read this: anyone working on bilevel BO or constrained BO. The algorithm is plausible and the experiments suggest it works, but the theory needs repair. I would send it to peer review rather than desk reject; the core idea deserves referee time, with the expectation of major revision.","headline":"New simultaneous bilevel BO algorithm with a real but repairable proof gap; the regret guarantee as written doesn't follow.","tokens_in":20526,"tokens_out":2218,"would_cite":false,"duration_ms":21041,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that BILBO, a Bayesian optimization algorithm for bilevel problems with black-box, noisy, constrained, derivative-free functions, has sublinear cumulative regret while querying only one function per iteration.","keywords":["bilevel optimization","Bayesian optimization","Gaussian processes","regret bounds","black-box optimization","trusted sets","constrained optimization","decoupled function queries"],"falsifier":"One concrete check: on a domain with a single upper-level point $x_0$ and two lower-level points $z_1,z_2$, set lower-level constraints and initial data so that $z_2$ is actually infeasible but has the higher upper confidence bound, making $\\bar{z}_t(x_0)=z_2$. If the algorithm's conditional reassignment ever queries $f$ or another function at $(x_0,z_2)$ and the observed value of $f$ there exceeds $f(x_0,z^*)$, then the trusted-set membership claim in Lemma C.2 fails at that round, and the finite-$T$ cumulative regret bound cannot hold for that instance.","tokens_in":19050,"feed_emoji":"🎯","tokens_out":9267,"duration_ms":80634,"temperature":0.7,"pith_summary":"BILBO tackles bilevel optimization problems in which the upper-level objective can only be evaluated at points that are optimal for a separate lower-level problem, with both functions black box, noisy, derivative free, and constrained. The paper's central claim is that both levels can be optimized simultaneously, with one function query per iteration, while still achieving sublinear cumulative regret: Theorem 4.9 bounds $R_T \\leq \\sqrt{4T|\\mathcal{F}|\\beta_T \\max_{h\\in\\mathcal{F}} C_h \\gamma_{h,T}}$ with high probability. The method works by building \"trusted sets\" from Gaussian process confidence bounds—points that are probably feasible and probably lower-level optimal—and by a conditional reassignment that queries the lower-level objective at its estimated optimum when that estimate is uncertain. If the claim holds, BILBO removes the repeated lower-level optimization that makes existing nested bilevel Bayesian optimization sample inefficient, and gives a no-regret algorithm for a class of problems where gradients and cheap lower-level solves are unavailable. The paper supports the claim with regret proofs and with experiments on synthetic and real-world energy and chemical process problems.","feed_headline":"One query per round makes bilevel black-box optimization no-regret","feed_subtitle":"The algorithm replaces repeated lower-level solves with trusted-set sampling, so noisy constrained problems converge.","key_machinery":"The central object is the trusted set, defined for functions $h$ using Gaussian process upper and lower confidence bounds $u_{h,t}, l_{h,t}$. The feasible trusted set $S^+_t$ keeps points whose upper confidence bound on every constraint is nonnegative, so every point in it has constraint regret bounded by $2\\beta_t^{1/2}\\sigma_{c,t-1}(x,z)$. The lower-level trusted set $P^+_t$ keeps points $(x,z)$ for which the upper confidence bound of the lower-level objective at $z$ reaches the lower confidence bound at the estimated lower-level solution $\\bar{z}_t(x)=\\arg\\max_{z\\in S^+_{\\mathrm{lo},t}(x)} u_{f,t}(x,z)$, making their lower-level regret bounded by $2\\beta_t^{1/2}(\\sigma_{f,t-1}(x,\\bar{z}_t(x))+\\sigma_{f,t-1}(x,z))$. The query point is the maximizer of $u_{F,t}$ over $S^+_t\\cap P^+_t$; the function queried is the one with largest estimated regret; and if the lower-level function is queried while $\\bar{z}_t(x_t)$ is more uncertain than $z_t$, the query is reassigned to $\\bar{z}_t(x_t)$. That reassignment is what converts the estimated lower-level regret into the factor $4\\beta_t^{1/2}\\sigma_{f,t-1}(x_t,z_t)$ in Lemma 4.8 and makes the one-query-per-round scheme no regret.","core_discovery":"Stated on its own terms, the paper establishes that general black-box bilevel optimization—where $F$ and $f$ are modelled by Gaussian processes, observations are noisy, constraints appear at both levels, and the domains are finite—admits a simultaneous, decoupled-query algorithm with a sublinear cumulative regret bound. The key bound is Theorem 4.9: with probability at least $1-\\delta$, Algorithm 1 satisfies $R_T \\leq \\sqrt{4T|\\mathcal{F}|\\beta_T \\max_{h\\in\\mathcal{F}} C_h \\gamma_{h,T}}$, and because $\\gamma_{h,T}$ is sublinear for squared-exponential and Mat\\'ern kernels, $R_T/T \\to 0$. The derivation rests on Lemma 4.8, which bounds the instantaneous regret of the queried point by $4\\beta_t^{1/2} \\max_{h} \\sigma_{h,t-1}(x_t,z_t)$, and on the construction of trusted sets in which every sampled point has bounded constraint regret and bounded lower-level objective regret. Empirically, BILBO is reported to converge faster than random trusted-set sampling and a nested Bayesian optimization baseline on multimodal synthetic problems and on two real-world problems.","pith_inferences":["The same trusted-set construction could be adapted to continuous domains, where the paper notes $\\beta_t$ would require modification; in that setting the bottleneck would likely shift from grid cardinality to the maximum information gain of the kernels, the same quantity that already controls the regret bound.","The conditional reassignment is essentially an explore step for the lower-level optimum; a natural and testable variant would trigger reassignment based on the estimated regret $\\bar{r}_{f,t}$ rather than only on the raw variance comparison, which may improve exploration when the estimated lower-level solution is far from the queried point.","For applications where lower-level evaluations are cheap, the per-iteration overhead of updating trusted sets could outweigh the sample savings—the paper itself notes BILBO is about 26 times slower per iteration than its nested baseline in wall-clock time—so the practical win is largest when evaluations are expensive, noisy, or multimodal.","If the gap in Lemma C.2 is closed by using a conservative estimate of the true lower-level optimum instead of the confidence-bound maximizer, the same framework might extend to robust or adversarial lower-level problems where the lower level is not a rational optimizer."],"forward_implications":["If Theorem 4.9 is correct, BILBO is a no-regret algorithm for noisy, constrained, derivative-free bilevel problems: for squared-exponential and Mat\\'ern kernels with $\\nu>1/2$, $R_T/T\\to 0$, so the average instantaneous bilevel regret vanishes.","The decoupled query rule means only one function—upper objective, lower objective, or one constraint—is evaluated per iteration, so the total query budget scales with the number of iterations rather than with repeated lower-level solves at each upper-level point.","The simple-regret estimator of Lemma 4.10 gives a point recommendation with regret $O(\\sqrt{|\\mathcal{F}|\\beta_T \\max_h C_h\\gamma_{h,T}/T})$, so the same algorithm can be used for final-solution selection, not only for minimizing cumulative regret.","Because the trusted feasible set certifies every point in it, active constraints on the boundary of the feasible region do not require special handling, and upper-level points whose lower-level problem is infeasible are filtered out through $S^+_{\\mathrm{lo},t}$.","Multiple lower-level optima for the same upper-level point are represented simultaneously inside $P^+_t$, which is a capability single-solution nested solvers lack."],"supporting_citations":[{"why":"Supplies the GP confidence-bound construction and the maximum-information-gain regret analysis that Corollary 4.2 and Theorem 4.9 build on.","marker":"Srinivas et al. 2010"},{"why":"Provides the optimistic confidence-bound feasible-set idea that the trusted set $S^+_t$ extends, and the regret-bound constant BILBO compares against.","marker":"Nguyen et al. 2023"},{"why":"Establishes confidence-bound-based optimistic feasible set estimation in constrained BO, the template for the feasible trusted set.","marker":"Xu et al. 2023"},{"why":"Introduces the nested bilevel BO framework that BILBO replaces, motivating the one-query-per-round design and the empirical Nested baseline.","marker":"Kieffer et al. 2017"},{"why":"Gives the information-gain rates for squared-exponential and Mat\\'ern kernels used to conclude that the regret bound is sublinear.","marker":"Vakili et al. 2021"}],"fun_headline_variants":["One query per round for bilevel black-box optimization","BILBO turns bilevel optimization into a no-regret Bayesian game","Trusted-set sampling cuts bilevel regret to sublinear","Simultaneous bilevel Bayesian optimization with one query each round"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing assumption is that the true optimal lower-level response lies inside the trusted set the algorithm builds; the proof needs the true optimum to dominate the confidence-bound maximizer $\\bar{z}_t(x^*)$, and it also needs the conditional reassignment to keep the query inside the trusted set, so if either fails the instantaneous and cumulative regret bounds do not cover the point actually evaluated.","fun_headline_variants_meta":{"raw":{"variants":["One query per round for bilevel black-box optimization","BILBO turns bilevel optimization into a no-regret Bayesian game","Trusted-set sampling cuts bilevel regret to sublinear","Simultaneous bilevel Bayesian optimization with one query each round"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000592,"raw_usage":{"total_tokens":2795,"prompt_tokens":984,"completion_tokens":1811,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":600,"completion_tokens_details":{"reasoning_tokens":1741}},"tokens_in":600,"tokens_out":1811,"duration_ms":11031,"temperature":1.0,"reasoning_tokens":1741,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T13:16:19.105033+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"One concrete check: on a domain with a single upper-level point $x_0$ and two lower-level points $z_1,z_2$, set lower-level constraints and initial data so that $z_2$ is actually infeasible but has the higher upper confidence bound, making $\\bar{z}_t(x_0)=z_2$. If the algorithm's conditional reassignment ever queries $f$ or another function at $(x_0,z_2)$ and the observed value of $f$ there exceeds $f(x_0,z^*)$, then the trusted-set membership claim in Lemma C.2 fails at that round, and the finite-$T$ cumulative regret bound cannot hold for that instance.","supporting_citations":[],"review_version":1}