- Rating
- 2(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This work considers bilevel optimization problems with the lower-level problem is a kind discrete submodular problem with coupled constraints. First-order SFM-based algorithms are proposed by using randomized-smoothed value-function formulation for uncoupled and coupled cases, respectively. The convergence analysis is provided for the proposed algorithms and numerical experiment are conducted to verify the performance.
Critical strengths
-
The presentation is clear and easy to follow.
-
The proposed two-SFM algorithms solve the discrete bilevel optimization without suboptimality of relaxations.
-
The convergence analysis is provided.
Critical weaknesses
-
The convergence to original problem (1) can not be guaranteed. Note that Theorem 1 only establishes expected stationarity of the smoothed penalty problem, and Corollary 2 transfers this to finite-radius Goldstein stationarity of $p_\gamma$ only under an interior-ball condition. However, transferring to the original optimistic objective additionally requires neighborhood-wise exactness from Corollary 1. These conditions are not guaranteed by the algorithm.
-
The assumptions required for the constrained guarantees are very restrictive. In particular, the exact Lagrangian support in Assumption 3 is non-generic for constrained discrete optimization, while Assumption 4 imposes uniform nondegeneracy of all supported saddle systems and may fail at ordinary discrete-response switches. These conditions substantially limit the scope of Theorem 2. Also, note that these assumptions are not verified for the main EDA experiment.
-
The toy example in numerical does not satisfy the conditions needed for transfer to . Note that the solution of the toy example lies at a lower-level response switch. Thus, the lower-level gap has zero infimum in every neighborhood. It also lies on the boundary of , which violates the interior-ball condition in Corollary 2.
-
The algorithm design is general to first-order bilevel optimization and submodular optimization, where penalty method and SFM method are based on existing works.
-
The provided complexity is not very clear, which does not shows the important dependencies of problem on the complexity.
Questions for authors
-
Convergence to original problem. How do Theorem 1 and Corollary 2 guarantee convergence to a solution of the original Problem (1), given that the required neighborhood-wise exactness condition is not ensured a priori and appears to be verified only after observing the output?
-
Corollary 1. How can the local gap condition in Corollary 1 hold near the response-switching solutions that appear central to the intended applications?
-
Assumption. Can Assumptions 3 and 4 be verified for the EDA experiment?
-
Numerical experiment. Why does Algorithm 3 return , while the primary experimental results use ? What are the feasibility and lower-level optimality guarantees for the reported ?
-
Error measure. What exactly is certified by ? Is it an upper bound on any error measure associated with problem (1)?
4 comments
Continued Response
W4. Methodological novelty
As clarified in R2-3, BiGAP establishes a new connection between discrete LL optimization and gradient-based UL optimization. We addressing two challenges.
-
The discrete LL response can jump. Changes in can switch , precluding differentiation through the LL solution map.
-
Relaxing can change the bilevel problem. Under the finite-penalty condition, BiGAP preserves binary decisions and optimistic tie-breaking, using exact SFM solvers such as graph cuts without solver differentiation or rounding.
Existing methods differ in formulations and guarantees (Tab. 1, App. A):
- Specialized formulations: modular incentives (Fanghänel, 2013), mixed-integer cuts and decision diagrams (Mattia, 2023; Vásquez et al., 2025)
- Relaxed submodular layers: differentiation via continuous relaxations (Djolonga and Krause, 2017)
- Continuous LL: F²SA (Kwon et al., 2023), BLOCC (Jiang et al., 2024), (FG)²U (Shen et al., 2024), and MA-SOBA (Chen et al., 2024); DIVIDE-BLO (Jiang et al., 2025) discretizes the LL domain with exponentially growing size
- Value-function: neural approximations with binary linking variables (Zhou et al., 2024); submodularity in binary leader decisions (Zhou et al., 2025, 2026)
BiGAP exploits submodularity in binary follower decisions with a continuous leader, giving a discrete-oracle gradient characterization and convergence guarantees for the coupled optimistic problem in Eq. (1).
W5. Complexity and costs.
Thms. 1–2, Cor. 3, and the subsequent remark specify BiGAP's stationarity metric, parameters, and complexity dependencies
The target is , where , and denote the smoothing batch size, outer iterations, and inner dual budgets.
- Thm. 1 (unconstrained): , requiring exactly SFM calls.
- Thm. 2 (coupled): , requiring exactly SFM calls.
Cor. 3 retains with , , , and . The Smaller Inner Budget remark gives inner–outer iteration tradeoff.
Dimension dependence The UL dimension enters through and the update; the LL dimension enters through SFM. For graph-representable objectives, an exact minimum-cut implementation costs on sparse graphs. Thus, the per-query arithmetic cost is when UL gradient assembly is linear in . By comparison, a continous GD/Adam update costs after gradient evaluation, while each BiGAP SFM exactly minimizes over binary responses. Thms. 1–2 also provide dependence on , , the initial objective gap, and dual and saddle-regularity constants.
With identical outer settings, warm-started two-block cuts match exact SFM's median exact-audited objective in 148 versus 187 seconds. DREAMPlace further supports scalability with over 210k binary LL variables
Q4 & Q5. Reported LL responses and certified-error metric.
The two responses have distinct purposes, and certified-error metric separately assesses LL optimality and feasibility.
For Q4. Alg. 3 computes and from the - and -supported dual chains and returns . Sec. 5.2 evaluates at the checkpoint minimizing audited certified error to assess practical follower quality under a fixed budget; the theory uses randomized output selection. App. G.2 reports performance, and App. G.3 reports the paired for DREAMPlace.
Constraint violation and the dual-based LL residual assess feasibility and LL optimality; feasible with zero certified residual is LL-optimal at
For Q5. Sec. 5.2 defines the certified-error metric where is a supported-dual lower bound on the constrained LL optimum. The terms measure Hamming error, a certified LL residual bound, and constraint violation. Since
upper-bounds the corresponding residual-based score for Problem (1). For feasible , the second term bounds the LL optimality gap. The certificate assesses follower optimality and feasibility; Prop. 7 and Cor. 5 separately characterize global-minimizer recovery (App. B.6). On ibm01, mean Hamming and certified errors are 442.6 and 445.0, so the LL residual bound and feasibility penalty contribute 2.4 on average (Tab. 2, App. G.2). New DREAMPlace reports the paired using exact LL audits (App. G.3).
I thank the authors for the responses. Some of my concerns have been addressed, and I have therefore decided to increase my score by one point.
We thank the reviewer for their thoughtful consideration of our responses and for increasing the score. We appreciate their constructive feedback and are glad that our clarifications have addressed several of their concerns. We remain happy to discuss any outstanding questions.
We thank the reviewer for
recognizing the clarity of our presentation, the discrete two-SFM algorithm, and the convergence analysis. R1-3 below clarify the challenges, novelty, and guarantees, then we address W1–W5 and Q1–Q5.R1) Algorithmic challenges Discrete bilevel optimization (BLO) arises in applications such as network interdiction and EDA. Yet effective large-scale solvers remain limited, often relying on expensive combinatorial search or reformulations (App. A, Sec. 5). BiGAP addresses discontinuous LL response switches and coupled constraints while preserving binary LL decisions in large-scale discrete BLO
R2) Methodological novelty BiGAP establishes a new connection between discrete LL optimization and gradient-based UL optimization through a value-gap penalty and SFM-based gradient estimates, with nonasymptotic stationarity guarantees for the smoothed penalty (see Props. 1, 3, and 5 and Thms. 1–2 for details)
R3) Connection to the original problem Our theory establishes rigorous connections between the penalty and the original optimistic BLO objective ϕ: (i) pointwise convergence and finite-penalty exactness (Prop. 1), (ii) local minimizer equivalence (Cor. 1), (iii) global-minimizer recovery (Prop. 7), and (iv) conditional stationarity transfer (Cors. 1–2).
W1, Q1, & Q2. Convergence to the original BLO problem.
For W1, see General Response G.1: the penalty's connection to the original BLO problem is established independently of Thm. 1 and Cors. 1–2. For Q1, Thm. 1 gives stationarity of pγϱ, while Cors. 1–2 give sufficient cconditions for transfer to ϕ. Specifically, Cor. 2 requires the interior-ball condition B(xˉ,ϱ)⊂intX and ηLγ≤ϱ. Cor. 1 ensures pγ=ϕ on the smoothing neighborhood if, for some r>ϱ,
\gamma\inf_{z\in B(\bar x,r)}\delta(z)>\Delta_f.$$ Prop. 3(i) gives local Lipschitzness of the unconstrained penalty, and the prescribed stepsize satisfies $\eta L_\gamma\leq\varrho$. **when the local conditions hold at the returned iterate, the stationarity bound transfers to $\phi$**. If they hold almost surely, the expected stationarity guarantee inherits the same SFM-call complexity. Importantly, **these conditions can hold without relying on verification after convergence**. Cor. 4 (App. B.3) provides explicit, checkable sufficient conditions for stationarity equivalence across regular LL response switches: agreement of UL objective values at a switch and sufficient growth of the LL optimality gap ensure local exactness for sufficiently large finite $\gamma$. For Q2, Cor 1 establishes **local minimizer equivalence under an explicit finite-penalty threshold**. For a local neighborhood $K$ of $\bar x$, it suffices that $$\gamma> \sup_{\substack{x\in K,y\in\mathcal Y(x)\setminus\mathcal Y^\star(x)}} \frac{[\inf_{z\in K}\phi(z)-f(x,y)]_+} {g(x,y)-v(x)}.$$ Discreteness makes the ratio finite for each suboptimal label at fixed $x$. **Its supremum must also remain finite**, which can hold when UL improvement decreases at least as fast as the LL optimality gap. Thus, **the condition allows LL response switches and vanishing LL gaps**. Example 1 in App. B.3 shows the penalty and original objectives share the same local minimizers at switches. For stationarity equivalence, Cor. 1 provides the sufficient condition stated in Q1. Prop. 6 characterizes its scope: in the unconstrained setting, a uniform positive LL gap on a connected domain is equivalent to a constant LL optimal-response set. Cor. 4 (App. B.3) extends stationarity equivalence to regular response switches. Importantly, **BiGAP handles response switches through its penalty formulation and randomized smoothing**. **W2 & Q3. Applicability and verification of Assumptions 3–4.** See **General Response G.2**. **Assumptions 3–4 DO NOT substantially limit the applicability of Thm. 2**, as original submission identifies classes for Assumption 3 and sufficient conditions for Assumption 4. We also clarify that `ibm01` experiment is intended to show BiGAP's practical effectiveness beyond analytically verified Assumptions 3-4. To test BiGAP with verified assumptions, **we conduct two additional EDA experiments** (Apps. G.1 and G.3). **W3. Numerical example at an LL response switch.** We clarify that the purpose of Sec.5.1 **is to show BiGAP optimizing toward an LL response-switching solution**, with discontinous optimistic objective. Fig. 3 reports the distance between the iterates and $x^\star$. The solution lies on the boundary of $\mathcal X$, outside the interior-ball setting of Cor. 2. The experiment **demonstrates convergence toward the known solution via direct evaluation**. For stationarity-transfer conditions at regular switches, see W1, Q1, and Q2.