{"id":"afed19f9-e956-42a8-bd27-e24af20dd56a","arxiv_id":"2505.10830","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A discretization-based value function approximation plus penalty method solves bilevel programs with low-dimensional non-convex constrained lower-level problems, with convergence guarantees for the penalized reformulation.","lead":"This paper proposes a method for bilevel optimization problems where the inner (lower-level) problem is non-convex and constrained, by replacing the inner problem's value function with a discretized and smoothed approximation. The authors prove approximation, equivalence, and convergence results, and test the method on a scalar example and on ensemble learning.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Assumption 3.1 is genuinely load-bearing: without convex sublevel sets and the Hölderian error bound, discretization can miss the BLO-VF feasible set, so the δ-global equivalence in Theorem 3.1 would fail; the abstract should disclose this restriction.","rationale":"The reader correctly identifies Assumption 3.1 as the weakest load-bearing premise. My independent check of the proofs confirms that Lemma 3.1 and both directions of Theorem 3.1 are the only places where the discretized problem is connected to the value-function relaxation, and both rely on convex sublevel sets and the Hölderian error bound. The ring example shows a concrete, natural nonconvex lower-level problem where the theorem's conclusion would fail, establishing that the assumption does real work and is not merely technical. The secondary issues I found (the |V - Vλ| bound in the proof of Theorem 3.1 Part 1, and the one-directional nature of Proposition 3.1's equivalence) do not change the main verdict; they are fixable in a revision. Since the paper states Assumption 3.1 in the theorem but not in the abstract or contributions, and since the experimental section only validates problems that satisfy the assumption (or have convex lower levels), the appropriate verdict is CONDITIONAL on the authors disclosing and discussing the reach of Assumption 3.1, exactly as the reader concluded. Therefore I do not change the reader's verdict.","tokens_in":25860,"tokens_out":25445,"duration_ms":227975,"concrete_test":"Ring counterexample: X={0}, Y=unit disk, g(y)=(||y||²-1/4)², f(y)=||y||². With ε1 small and k satisfying Theorem 3.1, a 50-50 combination of opposite ring grid points is feasible for (BLO-DISC) and maps to y=0 with f=0; the (BLO-VF) optimum is 0.25-√ε1 and y=0 is infeasible for relaxation <0.0625. If the computed (BLO-DISC) optimum maps to an infeasible (BLO-VF) point with f below the (BLO-VF) optimum, then Theorem 3.1's conclusion fails without Assumption 3.1, confirming that the assumption is load-bearing.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central equivalence (BLO-DISC)–(BLO-VF) in Theorem 3.1 rests entirely on Assumption 3.1. Lemma 3.1 uses Assumption 3.1(1) to conclude that a convex combination of sampled points with g(x,y^(i))-V(x) ≤ √ε1 still lies in the ε-level set; this is exactly the step that the nonconvex counterexample in Figure 2 would break, since the convex hull of sampled points can leave the ε-sublevel set when that set is disconnected. Assumption 3.1(2) (a Hölderian distance-to-argmin bound) is needed in both parts of Theorem 3.1 to convert near-feasibility of a BLO-VF point into proximity to a grid point and thus to control the f-gap δ. Neither condition is mentioned in the abstract or in Contribution 2, which advertise handling 'non-convex lower-level' problems generally. The assumption is not generic: for example, g(y) = (||y||² - 1/4)² on the unit disk has disconnected sublevel sets and violates Assumption 3.1(1), yet is a natural nonconvex lower-level problem. A secondary, fixable issue: the proof of Theorem 3.1 Part 1 bounds |V - Vλ| only by λ/2, omitting the covering term from Proposition 2.1(b), though the desired feasibility of (x', y^(i)) can be recovered from Vλ ≥ V; this is a gap in the written proof but not the theorem. Additionally, Proposition 3.1 only maps (BLO-PEN) solutions to (BLO-DISC), so the 'same set of KKT/local/global minima' claim in Contribution 2 is one-directional.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a discretization approach for optimistic bilevel programs with possibly nonconvex and constrained lower-level problems. It approximates the lower-level value function V(x)=min_{y∈Y} g(x,y) by Vλ(x)=min_{p∈Δ} Σ_i p_i g(x,y^{(i)}) + (λ/2)||p||² over a covering set {y^{(i)}}, and studies three reformulations: the relaxed value-function problem (BLO-VF), the discretized problem (BLO-DISC), and a penalty problem (BLO-PEN). The central theoretical result is a δ-global solution equivalence between (BLO-VF) and (BLO-DISC) under Assumption 3.1, a one-directional KKT/local/global solution correspondence between (BLO-PEN) and (BLO-DISC), and a projected-gradient algorithm (DIVIDE-BLO) with a O(1/T) stationarity convergence guarantee. Numerical experiments on a one-dimensional nonconvex lower-level problem and on an ensemble-learning hyperparameter-selection problem illustrate the approach.","tokens_in":26295,"tokens_out":9891,"duration_ms":93097,"significance":"If the results hold, the paper offers a genuinely different surrogate for constrained nonconvex lower-level bilevel problems: the regularized discretized value function is smooth and easy to evaluate, in contrast to the nonsmooth original value function. The paper is largely self-contained, with complete proofs of Proposition 2.1, Lemma 3.2, Proposition 3.1, and Theorem 4.1, and the DIVIDE-BLO algorithm is clearly specified and reproducible in structure. The main limitation is that the equivalence between (BLO-DISC) and the relaxed problem (BLO-VF) depends on Assumption 3.1, which requires convex near-optimal sublevel sets and a Hölderian distance-to-argmin bound; this restriction is not disclosed in the abstract and substantially narrows the advertised 'non-convex' scope. The algorithm itself and Theorem 4.1 do not use Assumption 3.1, so the method may still be useful beyond the equivalence guarantee, but the paper should say so explicitly.","major_comments":[{"comment":"The abstract and Contributions 1–2 present the method as handling non-convex and constrained lower-level problems, but the only result connecting (BLO-DISC) to (BLO-VF), Theorem 3.1, relies on Assumption 3.1, which requires convex sublevel sets for all ε≤ε0 and a Hölderian distance-to-argmin bound. This is a substantial restriction: functions such as g(y)=(||y||²-1/4)² on the unit disk have disconnected sublevel sets and violate Assumption 3.1(1), and the paper's own Figure 2 shows that without the convexity, grid sampling can miss the feasible region. The abstract and contribution list should state this assumption explicitly, for example by saying the equivalence holds for nonconvex lower-level problems whose near-optimal sublevel sets are convex and which satisfy a Hölderian error bound, rather than implying general nonconvex lower levels.","section":"Abstract and Section 3.1, Assumption 3.1"},{"comment":"In the feasibility check for (x',p') in the proof of Theorem 3.1 Part 1, the chain of inequalities uses |V(x')-Vλ(x')| ≤ λ/2, but Proposition 2.1(b) gives |V(x')-Vλ(x')| ≤ 2LgD√m/k^{1/m} + λ/2, and the covering term is not negligible in general. The intended conclusion can be recovered because Vλ≥V, as shown in the proof of Proposition 2.1, so that g(x',y^{(i)})-Vλ(x') ≤ g(x',y^{(i)})-V(x') suffices. As written, however, the displayed absolute-value bound is not valid and the proof should be corrected.","section":"Appendix A.2, proof of Theorem 3.1 Part 1"},{"comment":"Contribution 2 states that (BLO-PEN) and (BLO-DISC) 'share the same set of local minima, global minima, and KKT points', but Proposition 3.1 only establishes the forward direction: a KKT/local/global solution of (BLO-PEN) is also a corresponding solution of (BLO-DISC) for an ε that depends on the point and on γ. No converse is proved. This one-directional statement is sufficient for using (BLO-PEN) as a surrogate, but the 'same set' phrasing overstates the result and should be revised to reflect the actual direction established.","section":"Section 3.2 / Contribution 2"},{"comment":"The proofs of Lemma 3.1 and Theorem 3.1 repeatedly use the step that a sample point y^{(i)} exists with ∥y^{(i)}-y*∥≤ε1/(2Lg), citing the condition k≥(4LgD√m/ε1)^m. However, Assumption 2.2 only says eY is a covering of some radius r; a set of k points does not automatically have radius ≤ε1/(2Lg merely because k meets the lower bound for the minimal covering number. The statements should either explicitly require r≤ε1/(2Lg) (or that eY is chosen with this radius), or the proofs should be revised to state this additional condition, otherwise the key covering step does not follow from the assumptions as written.","section":"Lemma 3.1 and Theorem 3.1"}],"minor_comments":[{"comment":"The sentence 'we will establish the ... global/local/KKT solution equivalence between (BLO-VF) and (BLO-DISC) in Section 3.2' appears to be a typo: Section 3.2 actually treats (BLO-DISC) and (BLO-PEN), and Figure 1 confirms this.","section":"Section 3, first paragraph"},{"comment":"The expression '(Lg+Lg)' in the formula for Lγ is confusing even though it is consistent with the proof; it would be clearer to write 2Lg or to define two different Lipschitz constants for ∇g and g.","section":"Lemma 4.1, Eq. (4.1)"},{"comment":"In the proof of part (b), the line 'The equality in (a)' refers to the inequality just derived in part (b), not to part (a); this cross-reference should be corrected.","section":"Proof of Proposition 2.1(b)"}],"recommendation":"major_revision","confidential_remarks":"The technical core appears sound, and the main issue is a mismatch between the paper's broad claims and the restrictive assumption under which the central equivalence holds. The authors should also verify whether the Section 5.1 experiment (g(x,y)=sin(10y)+2y²) satisfies Assumption 3.1 for a sufficiently large ε0; if it does, the experiment supports the equivalence theorem, but if not, the experiment should be presented only as evidence for the algorithm's practical behavior, not for the equivalence guarantee."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I'd want you to know this paper on two counts. First, the core mechanism is genuinely fresh: discretize the lower-level feasible set, replace the value function by a convex combination over sampled points plus a quadratic regularizer, and you get a smooth approximate value function with an error you can control. That is a real idea, and the paper works out its properties carefully. The equivalence theorems between the discretized problem and the relaxed value-function problem, and between the discretized problem and its penalty reformulation, are nontrivial and mostly sound. The Danskin-based gradient formula, the Lipschitz smoothness bounds, and the projected-gradient convergence proof are all standard but correctly executed.\n\nNow the soft spots, in proportion. The load-bearing assumption is Assumption 3.1: for every x, the lower-level sublevel sets must be convex for small sublevel thresholds, and a Hölderian distance-to-argmin bound must hold. This is exactly what makes the discretized feasible set capture the true relaxed feasible set. The paper does state the assumption in Section 3, but the abstract and the contribution list advertise handling non-convex lower-level problems generally, and Assumption 3.1 is not disclosed there. That is an overclaim, and it matters, because the assumption is not generic: simple non-convex lower-level objectives with disconnected sublevel sets violate it. The authors even include a figure showing what can go wrong without it, which is honest but also confirms the restriction is real.\n\nThere is also a small proof gap in Theorem 3.1 Part 1. The written bound on |V - Vλ| only uses the λ/2 term and omits the covering term from Proposition 2.1(b). The theorem can be rescued because Vλ ≥ V, so the feasibility of the constructed point still follows, but the line as written is wrong and needs fixing. Separately, Contribution 2 claims that the discretized problem and the penalty problem share the same set of KKT points and local/global minima, but Proposition 3.1 only shows one direction: solutions of the penalty problem map to solutions of the discretized problem. The reverse direction is not proven, so that claim is stronger than the results. Finally, the experiments are thin: the synthetic problem is one-dimensional in y, the ensemble-learning application is suggestive but lacks details on how the covering quality is ensured, and no code is released.\n\nThe paper is still worth a serious referee. The discretization idea deserves to be in the literature, and the theory around it is careful enough to be a useful reference even if the scope needs to be narrowed. My recommendation: send it to peer review, but require the authors to state Assumption 3.1 prominently in the abstract and to correct the one-directional equivalence claim. The proof gap is minor and fixable.","headline":"The discretization idea is genuinely new and worth engaging, but the advertised reach exceeds the proven results: Assumption 3.1 does a lot of work and should be front and center.","tokens_in":26786,"tokens_out":2736,"would_cite":true,"duration_ms":25402,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C30","90C46"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proposes replacing the lower-level value function of a bilevel problem with a convexified discretized surrogate, and proves that solving the resulting penalized problem yields approximate global solutions of the relaxed bilevel…","keywords":["bilevel optimization","value function approximation","discretization","non-convex lower-level","penalty method","projected gradient descent","low-dimensional","simplex reformulation"],"falsifier":"Construct a lower-level problem with two narrow wells of nearly equal depth where one well is smaller than the grid spacing, so Assumption 3.1 fails. Run DIVIDE-BLO with a grid that misses the small well; if the returned induced point is not a $\\delta$-global solution of the value-function relaxation because a better $f$-value exists inside the missed well, that observation would refute the equivalence claim outside its stated assumption.","tokens_in":25633,"feed_emoji":"🎯","tokens_out":12950,"duration_ms":106470,"temperature":0.7,"pith_summary":"Bilevel optimization usually becomes intractable when the lower-level problem is constrained and non-convex: the lower-level value function is then non-differentiable and effectively impossible to evaluate. The paper's approach is to discretize the lower-level feasible set, represent the lower-level solution as a probability vector over sampled points, and replace the value function by a strongly convex simplex minimization whose solution is a projection. It proves that, under a convexity-and-growth condition on lower-level sublevel sets, global solutions of the discretized problem are $\\delta$-global solutions of the standard value-function relaxation, with the approximation error controlled by the sampling radius and the regularization parameter. It then shows that a quadratic penalty reformulation shares global minima, local minima, and KKT points with the discretized problem, and gives a projected gradient algorithm with $O(1/T)$ convergence. A sympathetic reader would care because this is a route to constrained non-convex lower-level problems with provable approximation and convergence guarantees.","feed_headline":"A sampled value function makes non-convex bilevel problems tractable","feed_subtitle":"Provable guarantees link the discretized penalty problem to the relaxed bilevel problem.","key_machinery":"The load-bearing object is the pair $(\\tilde V_\\lambda, \\text{(BLO-DISC)})$: the approximate value function $\\tilde V_\\lambda$ converts a non-convex minimization over $y$ into a strongly convex minimization over the simplex, making the bilevel constraint smooth, and the discretized problem reparameterizes $y$ as $\\sum_i p_i y^{(i)}$. The argument runs through a chain of equivalences. Lemma 3.1 uses Assumption 3.1 and the covering condition to show that a feasible weighted combination of samples is feasible for the value-function relaxation; Theorem 3.1 converts that into $\\delta$-global solution equivalence in both directions. Lemma 3.2 bounds the penalty feasibility gap at KKT points by $5L_fD/(2\\gamma)$, and Proposition 3.1 transfers KKT, local, and global solution status from the penalty problem to the discretized problem. On the computational side, the identity that $p^*(x)$ is a Euclidean projection onto the unit simplex makes each iteration of DIVIDE-BLO cheap, and the derived Lipschitz constant drives the $O(1/T)$ projected-gradient convergence bound.","core_discovery":"At the center of the paper is the discretized value function $\\tilde V_\\lambda(x)=\\min_{p\\in\\Delta}\\sum_{i=1}^k p_i g(x,y^{(i)})+\\frac{\\lambda}{2}\\|p\\|^2$, where $\\{y^{(i)}\\}$ is a covering of the lower-level set $Y$ of radius $r$ and $\\Delta$ is the unit simplex. This function is differentiable and has a closed-form gradient through the argmin $p^*(x)$, which is the projection of $(-g(x,y^{(1)})/\\lambda,\\dots,-g(x,y^{(k)})/\\lambda)$ onto the simplex. The paper's main equivalence theorem states that if $(x^*,p^*)$ is a global solution of the discretized problem with relaxation coefficient $\\epsilon_1\\le[\\epsilon_0/(1+4DL_g)]^2$, then $(x^*, \\sum_i p_i^* y^{(i)})$ is a $\\delta$-global solution of the value-function relaxation with coefficient $(1+4DL_g)\\sqrt{\\epsilon_1}$, under Assumption 3.1; a converse direction holds as well. The same section proves that the penalty problem (BLO-PEN) and the discretized problem (BLO-DISC) have identical global minima, local minima, and KKT points, so solving the smooth penalized problem is a valid surrogate for the discretized problem.","pith_inferences":["The method's practical reach is governed by the covering number bound $k=O((D\\sqrt{m}/r)^m)$, so the low-dimensional lower-level assumption is doing real work; a fair extension would be an explicit sample-complexity statement linking $r$ to $\\epsilon_1$ and $\\delta$.","Because Assumption 3.1 is exactly what rules out the missed-region failure in the paper's own Figure 2, a cheap empirical diagnostic is to rerun DIVIDE-BLO with two independent grids of the same radius and compare the induced solutions; disagreement would signal that the convex-sublevel-set condition is close to failing.","The convex-hull-of-samples construction is a general template: any non-convex lower-level problem whose near-optimal sublevel sets are convex could be attacked by the same discretize-and-convexify scheme, and it suggests trying adaptive or random sampling schemes with variance-reduced estimators.","The $\\delta$ in the equivalence grows like $\\epsilon_1^{\\beta/2}$ through the growth exponent $\\beta$; testing problems with $\\beta=1$ versus $\\beta<1$ would show how the approximation guarantee degrades in practice."],"forward_implications":["For any prescribed accuracy, taking the sampling radius and $\\lambda$ small enough makes the discretized problem track the value-function relaxation at the $\\delta$-global level, so the approximation error is controllable by the number of sample points $k$ and by $\\lambda$.","Every KKT point obtained by the penalty method is a KKT point of the discretized problem for some relaxation coefficient $\\epsilon\\le 5L_fD/(2\\gamma)$; increasing the penalty parameter $\\gamma$ forces the solutions closer to feasibility.","Projected gradient descent on the penalized objective converges in finite time to a stationary point at rate $1/T$, and any convergent subsequence reaches a KKT point of both the penalized and discretized problems.","In the numerical study, on a non-convex synthetic lower-level problem the method consistently reached zero lower-level violation and zero total gap, while two comparison algorithms sometimes stalled at infeasible local optima; on the ensemble-learning application the weighted model outperformed every base model."],"supporting_citations":[{"why":"Supplies the covering-number bound $k\\le(2D\\sqrt{m}/r)^m$ used to turn the covering radius into the approximation error and into the sample-size conditions in Lemma 3.1 and Theorem 3.1.","marker":"[38]"},{"why":"Supplies Danskin's theorem, which gives differentiability and the gradient formula for the approximate value function.","marker":"[39]"},{"why":"Provides the penalty-based bilevel gradient descent method that is both a baseline in the experiments and the source of the penalty-feasibility comparison in Lemma 3.2.","marker":"[36]"},{"why":"Established value-function reformulations for simple bilevel problems with non-convex lower level and the relaxation convention used in (BLO-VF).","marker":"[35]"},{"why":"Documents that the value function of a non-convex lower-level problem is generally non-differentiable, motivating the convexified discretization.","marker":"[19]"}],"fun_headline_variants":["Sample then convexify: a new route for non-convex bilevel","Discretized value function yields tractable bilevel penalty","Equivalence guarantees for sampled bilevel optimization","Finite-time gradient method for constrained bilevel problems"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on Assumption 3.1: the lower-level sublevel sets just above the minimum must be convex for small gaps, and any near-optimal $y$ must lie within a power-law distance $C\\,|g(x,y)-V(x)|^\\beta$ of the optimal set; without this, a finite grid can miss the true feasible region and the claimed equivalence between the discretized and relaxed problems collapses.","fun_headline_variants_meta":{"raw":{"variants":["Sample then convexify: a new route for non-convex bilevel","Discretized value function yields tractable bilevel penalty","Equivalence guarantees for sampled bilevel optimization","Finite-time gradient method for constrained bilevel problems"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000215,"raw_usage":{"total_tokens":1487,"prompt_tokens":1064,"completion_tokens":423,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":680,"completion_tokens_details":{"reasoning_tokens":357}},"tokens_in":680,"tokens_out":423,"duration_ms":4958,"temperature":1.0,"reasoning_tokens":357,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:03:21.505759+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a lower-level problem with two narrow wells of nearly equal depth where one well is smaller than the grid spacing, so Assumption 3.1 fails. Run DIVIDE-BLO with a grid that misses the small well; if the returned induced point is not a $\\delta$-global solution of the value-function relaxation because a better $f$-value exists inside the missed well, that observation would refute the equivalence claim outside its stated assumption.","supporting_citations":[{"cited_title":"On a theorem of Danskin with an application to a theorem of von neumann-sion","cited_arxiv_id":null,"evidence_quote":"Supplies Danskin's theorem, which gives differentiability and the gradient formula for the approximate value function."},{"cited_title":"On penalty-based bilevel gradient descent method, 2023","cited_arxiv_id":null,"evidence_quote":"Provides the penalty-based bilevel gradient descent method that is both a baseline in the experiments and the source of the penalty-feasibility comparison in Lemma 3.2."},{"cited_title":"On solving simple bilevel programs with a nonconvex lower level program","cited_arxiv_id":null,"evidence_quote":"Established value-function reformulations for simple bilevel problems with non-convex lower level and the relaxation convention used in (BLO-VF)."}],"review_version":1}