acceptodds
Under review as a conference paper at ICLR 2027

Bilevel Optimization with Discrete Submodular Lower Levels

Abstract

Bilevel optimization (BLO) models hierarchical decision-making in applications such as electronic design automation, network planning, and learning systems. While recent advances in continuous settings have substantially expanded the scale and scope of solvable problems, many practical discrete BLO problems remain computationally difficult. This work studies BLO problems with discrete submodular lower levels (LLs) and coupled constraints, and introduces BiGAP, a randomized-smoothed value-function formulation that regularizes discrete response switches while preserving exact discrete oracles. We establish finite penalty exactness and show that the smoothed formulation agrees locally with the smoothed optimistic objective on positive-gap neighborhoods. The resulting first-order algorithms reduce all discrete computations to tractable unconstrained submodular function minimization (SFM), with SFM complexity without coupled constraints and with coupled constraints under exact dual support and uniform saddle-system conditioning. Experiments on challenging large-scale discrete optimization problems demonstrate the effectiveness and scalability of the proposed approach.

Primary area:
optimization
Keywords:
bilevel optimization, discrete optimization, submodular optimization, submodular function minimization, constrained optimization, combinatorial optimization, randomized smoothing, electronic design automation

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_x9yyOpenReview ↗
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 ϕ\phi 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 ϕ\phi. 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 XX, 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 yFy_F, while the primary experimental results use ygy_g? What are the feasibility and lower-level optimality guarantees for the reported ygy_g?

  • Error measure. What exactly is certified by Errcert\mathrm{Err}_{\mathrm{cert}}? Is it an upper bound on any error measure associated with problem (1)?

4 comments

We thank the reviewer forrecognizing 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 ϕ\phi: (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γϱp_\gamma^\varrho, while Cors. 1–2 give sufficient cconditions for transfer to ϕ\phi. Specifically, Cor. 2 requires the interior-ball condition B(xˉ,ϱ)⊂int⁡XB(\bar x,\varrho)\subset\operatorname{int}\mathcal X and ηLγ≤ϱ\eta L_\gamma\leq\varrho. Cor. 1 ensures pγ=ϕp_\gamma=\phi on the smoothing neighborhood if, for some r>ϱr>\varrho,

\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.
AuthorsOpenReview ↗

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 xx can switch y⋆(x)y^\star(x), 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 E[∥Gη,ϱ(xtout)∥22]≤ϵ2\mathbb E[\|\mathcal G_{\eta,\varrho}(x^{t_{\mathrm{out}}})\|2^2]\leq\epsilon^2, where M,TM,T, and Kλ,KμK_\lambda,K_\mu denote the smoothing batch size, outer iterations, and inner dual budgets.

  • Thm. 1 (unconstrained): M,T=O(ϵ−2)M, T=\mathcal O(\epsilon^{-2}), requiring exactly 2MT+1=O(ϵ−4)2MT+1=\mathcal O(\epsilon^{-4}) SFM calls.
  • Thm. 2 (coupled): M,Kλ,Kμ,T=O(ϵ−2)M,K_\lambda,K_\mu,T=\mathcal O(\epsilon^{-2}), requiring exactly TM(Kλ+Kμ)+Kλ=O(ϵ−6)TM(K_\lambda+K_\mu)+K_\lambda=\mathcal O(\epsilon^{-6}) SFM calls.

Cor. 3 retains O(ϵ−6)\mathcal O(\epsilon^{-6}) with M=1M=1, η=Θ(ϵ2)\eta=\Theta(\epsilon^2), T=O(ϵ−4)T=\mathcal O(\epsilon^{-4}), and Kλ=Kμ=O(ϵ−2)K_\lambda=K_\mu=\mathcal O(\epsilon^{-2}). The Smaller Inner Budget remark gives inner–outer iteration tradeoff.

Dimension dependence The UL dimension pp enters through H=O(Lγp/ϱ)H=\mathcal O(L_\gamma\sqrt p/\varrho) and the O(p)\mathcal O(p) update; the LL dimension dd enters through SFM. For graph-representable objectives, an exact O(d∣E∣)\mathcal O(d|E|) minimum-cut implementation costs O(d2)\mathcal O(d^2) on sparse graphs. Thus, the per-query arithmetic cost is O(d2+p)\mathcal O(d^2+p) when UL gradient assembly is linear in pp. By comparison, a continous GD/Adam update costs O(d+p)\mathcal O(d+p) after gradient evaluation, while each BiGAP SFM exactly minimizes over 2d2^d binary responses. Thms. 1–2 also provide dependence on LγL_\gamma, ϱ\varrho, 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 2.444782.44478 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 ygy_g and yFy_F from the gg- and (f+γg)(f+\gamma g)-supported dual chains and returns yFy_F. Sec. 5.2 evaluates ygy_g 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 yFy_F performance, and App. G.3 reports the paired yFy_F for DREAMPlace.

Constraint violation and the dual-based LL residual assess feasibility and LL optimality; feasible yy with zero certified residual is LL-optimal at xx

For Q5. Sec. 5.2 defines the certified-error metric Err⁡cert(x,y)=f(y)+[g(x,y)−v^(x)]++[c(y)]+\operatorname{Err}_{\rm cert}(x,y)=f(y)+[g(x,y)-\widehat v(x)]_+ +[c(y)]_+ where v^(x)≤v(x)\widehat v(x)\leq v(x) 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

[g(x,y)−v(x)]+≤[g(x,y)−v^(x)]+[g(x,y)-v(x)]_+\leq[g(x,y)-\widehat v(x)]_+ Err⁡cert\operatorname{Err}_{\rm cert} upper-bounds the corresponding residual-based score for Problem (1). For feasible yy, 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 yFy_F 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.

Reviewer_Yp7DOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies bilevel optimization with discrete submodular lower-level problems, extending bilevel optimization techniques beyond the continuous lower-level settings considered in much of the existing literature. The authors propose BiGAP, a framework combining a value-function penalty formulation, randomized smoothing, and submodular function minimization (SFM) to address the challenges arising from discrete lower-level decisions.

The paper establishes first-order properties and develops convergence guarantees for both unconstrained and constrained submodular lower-level problems. In particular, Proposition 3 establishes the first-order oracle and subgradient properties for the unconstrained discrete setting, while Proposition 5 characterizes the accuracy of approximate first-order information in the presence of coupled lower-level constraints.

The proposed algorithms achieve SFM oracle complexities of O(ϵ−4)O(\epsilon^{-4}) for the unconstrained setting and $O(\epsilon^{-6}) for the constrained setting. This to my knowledge is a new result to the bilevel optimization community. In the past, the continuous bilevel optimization has a gradient complexity with O(ϵ−2)O(\epsilon^{-2}) for the unconstrained setting (without acceleration) and O(ϵ−3)O(\epsilon^{-3}) for the constrained setting (if ignoring the Goldstein stationarity radius δ\delta). I think it is a little hard to have a fair comparison for SFM oracles and gradient oracles, but I found the results in this paper very interesting.

Empirically, the authors further evaluate the proposed algorithms on a toy inverse cut-design problem and a large-scale electronic design automation (EDA) problem, demonstrating promising optimization performance. I believe discrete lower-level optimization has a significant amount of applications. This paper largely extends the applicability of bilevel optimization algorithms to a broader range of real-world applications. These bilevel optimization with discrete variables can be solved more efficiently by the algorithms proposed in this paper.

Critical strengths
  1. Novel theoretical contribution to bilevel optimization with discrete lower-level problems.

I consider this paper an important extension of the bilevel optimization literature. Most existing first-order analyses focus on continuous lower-level problems, whereas this paper accommodates discrete lower-level decisions by exploiting submodularity. This is a nontrivial and theoretically interesting advancement.

In particular, I view Propositions 3 and 5 as the most important theoretical contributions. Proposition 3 establishes how first-order information can be obtained from exact discrete submodular minimization oracles. Proposition 5 extends the first-order analysis to the constrained setting and provides an approximation guarantee for the resulting gradient estimator. These results provide essential foundations for applying first-order optimization methods to bilevel problems with discrete lower-level decisions.


  1. Broad potential applicability and promising experimental results.

Discrete lower-level optimization arises in many important applications, including combinatorial decision-making and electronic design automation. By avoiding continuous relaxations of the discrete lower-level decisions and exploiting submodular structure, this work substantially expands the class of bilevel optimization problems that can be addressed through first-order algorithms.

Critical weaknesses

One weakness is that the algorithm still relies on the SFM oracle to find the optimal solution. In the unconstrained case, this is polynomial time solvable for submodular minimization. But in the constrained setting, this oracle cost can become very expensive.

I understand optimality of the solution is needed to get gradient approximation in bilevel optimization and in your Proposition 3 and 5. Is there any chance to bypass the optimality of the lower-level solutions or is there any impossibility result?

Questions for authors

Proof sketch and intuition for Proposition 5

I consider Proposition 5 one of the most important and technically challenging results in this paper, as it establishes the accuracy of the approximate first-order information in the constrained discrete submodular setting.

Although the complete proof is provided in Appendix E.3, I would appreciate a concise proof sketch during the rebuttal, highlighting the main technical steps and explaining the role of Assumptions 3 and 4. In particular, it would be helpful to clarify how the approximate primal-dual solutions yield the gradient approximation bound and how the saddle-point error bound is used to control the approximation error.

Such an explanation would help readers better understand the key theoretical insight underlying the constrained algorithm. Thank you!

2 comments

We thank the reviewer for the detailed and encouraging assessment, particularly for recognizing the novel theoretical contributions of Propositions 3 and 5 and BiGAP's potential to substantially broaden the applicability of bilevel optimization to discrete problems. We provide additional clarification to the remaining concerns as below.

W1. Can BiGAP-PD avoid an exact lower-level solve? What if the SFM oracle itself is approximate?

We thank the reviewer for highlighting Prop. 5. Its main implication is that BiGAP-PD can update xtx^t without computing an exact solution y⋆(xt)y^\star(x^t) of the constrained lower-level (LL) problem. The finite-time guarantee uses exact SFM calls on unconstrained subproblems.

1. What must be solved exactly? At each perturbed query z=xt+ϱwz=x^t+\varrho w, Alg. 2 runs dual ascent separately for h=gh=g and h=F:=f+γgh=F:=f+\gamma g. At inner step kk, the SFM oracle returns yk∈arg⁡min⁡y∈Y{h(z,y)+(νk)⊤c(z,y)}.y^k\in\arg\min_{y\in\mathcal Y}\{h(z,y)+(\nu^k)^\top c(z,y)\}. Assumption 2 makes this subproblem submodular for the nonnegative multiplier νk\nu^k. The returned label can violate the original coupled constraints. Its role is to update the multiplier and contribute to the gradient estimate. Alg. 3 uses the directions from the two inner runs to update xtx^t. Prop. 5 bounds the error after finitely many inner steps. The cost per query is Kλ+KμK_\lambda+K_\mu unconstrained SFM calls.

2. Can an approximately optimal label replace an exact SFM response? A small objective error alone cannot guarantee a small pointwise gradient error in Prop. 3. For example, take γ=1\gamma=1, y∈{0,1}y\in\{0,1\}, g(z,y)=0g(z,y)=0, and f(z,y)=zyf(z,y)=zy. Then p1(z)=min⁡{0,z}p_1(z)=\min\{0,z\}. At z=η>0z=\eta>0, the exact FF-response is y=0y=0, and the penalty gradient is zero. The label y=1y=1 is η\eta-optimal, but using it in the same formula gives a gradient of one. This holds for arbitrarily small η\eta. A guarantee for an inexact oracle would require control of its contribution to the smoothed gradient bias. App. G.1 also tests inexact SFM on OpenROAD. Warm-started two-block cuts reached the same median exact-audited score as exact SFM (2.444782.44478), with median times of 148 s and 187 s, respectively.

Q1. How do approximate primal-dual solutions give the gradient bound in Prop. 5?

Fix xtx^t and condition on the incoming solver states. Let z=xt+ϱwz=x^t+\varrho w. For each h∈{F,g}h\in\{F,g\}, write Vh(z)V_h(z) for the constrained value and Sh(z)S_h(z) for the exact saddle set. Assumption 3 gives exact Lagrangian support with bounded supporting multipliers, so the saddle value equals Vh(z)V_h(z) (Prop. 4). We provide the proof outline as bellow.

Proof Sketch for Proposition 5: After KK inner iterations, the proof proceeds as follows (App. E.3).

KK exact SFM calls in dual ascent (A2, Alg. 2)
→ Averaged primal-dual pair sK=(νˉK,aˉK)s_K=(\bar\nu_K,\bar a_K)
→ Small saddle gap Gap⁡h(z,aˉK,νˉK)≤Γh/K\operatorname{Gap}_h(z,\bar a_K,\bar\nu_K)\leq\Gamma_h/\sqrt K (A1–A3, Prop. 10)
→ Small expected distance to the saddle set Ew[dist⁡(sK,Sh(z))]≤κˉhΓh/K\mathbb E_w[\operatorname{dist}(s_K,S_h(z))]\leq\bar\kappa_h\Gamma_h/\sqrt K (averaged A4)
→ Small expected gradient error Ew∥G^h(z)−∇Vh(z)∥2=O(K−1/2)\mathbb E_w\|\widehat G_h(z)-\nabla V_h(z)\|_2=\mathcal O(K^{-1/2}) (A1, A3, Lem. 6 and Eqs. (42)–(44))
→ Small bias in the smoothed gradient estimate (averaged bound, Eq. (44), and smoothing identity, Eq. (45), Prop. 5).

Applying the per-objective bound to the two inner runs and using the triangle inequality gives Eq. (14),

\leq \frac{C_F}{\sqrt{K_\lambda}}+\frac{C_g}{\sqrt{K_\mu}}.$$ Here $K_\lambda$ and $K_\mu$ are the inner budgets for $F$ and $g$, respectively, and $C_g$ includes the factor $\gamma$. For the question on Assumption 3-4, we provide detailed explanation in **General Response G2** at the top of thi discussion page. For the question on **how do the inner iterates give a gradient estimate**, we clarify that the empirical distribution $\bar a_K$ records how often each label $y^k$ occurs and Alg. 2 uses these frequencies to average the objective gradients and constraint Jacobians. It then weights the averaged Jacobian by the mean multiplier $\bar\nu_K$. This gives $\widehat G_h(z)=G_h(z,\bar\nu_K,\bar a_K)$ (Eq. (41)). For the question on **why does distance to the saddle set control gradient error**, we clarify as the following. For almost every $z$, Lem. 6 gives $G_h(z,s^\star)=\nabla V_h(z)$ for every $s^\star\in S_h(z)$. Choose a saddle pair nearest to $s_K$. Eq. (42) bounds the change from $G_h(z,s^\star)$ to $G_h(z,s_K)$ by a constant times that distance. This is why the saddle-gap estimate from Prop. 10 and averaged A4 suffice. Even if individual queries are poorly conditioned, their expected distance bounds the expected gradient error in Eq. (43).

Thank you for the detailed response. I will maintain my positive assessment.

Reviewer_XfVZOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies bilevel optimization with continuous upper-level variables and discrete submodular lower-level problems. The authors propose BiGAP, which combines value-gap penalization, randomized smoothing, and submodular function minimization (SFM) to avoid differentiating or relaxing the discrete lower-level responses. For unconstrained lower-level problems, the proposed method achieves an O(ε−4)O(\varepsilon^{-4}) SFM-call complexity. The framework is further extended to coupled constraints through Lagrangian duality, with an O(ε−6)O(\varepsilon^{-6}) complexity guarantee under additional regularity assumptions. Experiments on graph-cut and electronic design automation problems demonstrate promising numerical performance. The paper provides a meaningful structured approach to discrete bilevel optimization, although the applicability of its constrained convergence theory remains insufficiently established.

Critical strengths

The paper addresses a meaningful problem involving discrete lower-level responses, for which conventional differentiation-based bilevel methods are difficult to apply. By exploiting submodularity, the proposed framework preserves the discrete structure and reduces the required lower-level computations to tractable SFM problems. The extension to coupled constraints, including the analysis of exact Lagrangian support and saddle-system sensitivity, provides a nontrivial theoretical contribution. The large-scale EDA experiment also demonstrates promising computational performance.

Critical weaknesses

The convergence guarantees for BiGAP-PD rely on Assumptions 3–4, but these conditions are not verified for the main EDA experiment, leaving their practical applicability unclear. Moreover, the stated complexity guarantees apply to the smoothed penalized objective, but the paper does not establish a corresponding complexity guarantee for approximate stationarity of the original bilevel objective.

Questions for authors

1.Can the authors justify the applicability of Assumptions 3–4 to the EDA experiment and identify practical problem classes where these assumptions hold?

  1. Under what conditions can the stated complexity guarantees be extended to approximate stationarity of the original bilevel objective?
3 comments

We thank the reviewer for recognizing the importance of discrete BLO, the nontrivial theoretical contribution of our coupled-constraint analysis, and the promising computational performance on large-scale EDA problems. We provide clarification for the questions as below.

W1. Applicability of the constrained convergence guarantees and their connection to the original BLO problem.

We clarify that the original EDA experiment illustrates BiGAP-PD's practical effectiveness beyond the analytically verified assumptions, while the original manuscript already provides structured problem classes and sufficient conditions for the theoretical guarantees (Apps. C–E). We further strengthen applicability through weaker regularity conditions and additional EDA experiments. General Response G1 explains how the penalty relates to the original BLO problem. Q2 below gives the conditions for stationarity transfer to ϕ\phi (Corollaries 1–2).

Q1. Can the authors justify the applicability of Assumptions 3–4 to the EDA experiment and identify practical problem classes?

We address this concern from two perspectives:

  • (i) Weaker theoretical assumptions. The main role of Assumption 4 is to transfer the O(K−1/2)\mathcal O(K^{-1/2}) saddle-gap convergence obtained from SFM and dual ascent to saddle accuracy, thereby establishing an O(K−1/2)\mathcal O(K^{-1/2}) gradient-error bound. Since the outer algorithm optimizes a smoothed objective, we can relax the pointwise gradient-error bound to an averaged one while preserving the same convergence rate. This substantially weakens Assumption 4 to averaged saddle regularity, allowing potentially ill-conditioned individual query points without requiring uniform pointwise control. Importantly, the saddle-gap convergence already holds under Assumptions 1–3 (Prop. 10, App. E).

  • (ii) Practical verification and new experiments. The original manuscript already provides explicit sufficient conditions for Assumption 3, including threshold-preserving constraints and exact Lagrangian support (Props. 8–9, App. D). We further introduce a DREAMPlace-derived macro-anchored tier-assignment benchmark with over 210k binary variables (App. G.3). Assumption 3 is verified by construction: the implication constraints ci(y)=yi−yM(i)≤0c_i(y)=y_i-y_{M(i)}\leq0 in Eq. (49b) admit a uniformly strictly feasible binary assignment with margin σ=1\sigma=1. They also preserve feasibility under threshold rounding of the Lovász relaxation, so Proposition 9 gives exact Lagrangian duality for both gg and f+γgf+\gamma g. For Assumption 4, we examine the averaged saddle-error bound along the optimization trajectory to assess the weaker regularity condition in practice. BiGAP-PD achieves a mean certified error of 63.1, compared with 161.8 for CMA-ES, under the same computational budget.

The original ISPD98 experiment complements these results by demonstrating BiGAP-PD's practical effectiveness on a large-scale EDA problem where Assumptions 3–4 have not been certified instance-wide. For details on the problem classes covered by Assumption 3 and the averaged regularity condition in Assumption 4, see General Response G2.

Q2. Under what conditions can the stated complexity guarantees be extended to approximate stationarity of the original bilevel objective?

We clarify that complexity bounds extend to approximate Goldstein stationarity of the original optimistic objective ϕ\phi under two local conditions at the returned xtoutx^{t_{\mathrm{out}}}:

  1. The smoothing ball lies inside the feasible set. Assume B(xtout,ϱ)⊂int⁡XB(x^{t_{\mathrm{out}}},\varrho)\subset\operatorname{int}\mathcal X and ηLγ≤ϱ\eta L_\gamma\leq\varrho. Then the smoothed gradient step stays in X\mathcal X, so the projection is inactive. By Corollary 2, \leq \left\|\mathcal G_{\eta,\varrho}(x^{t_{\mathrm{out}}})\right\|_2$$
  2. The penalty agrees with ϕ\phi on a neighborhood of the smoothing ball. By Corollary 1, a sufficient condition is that, for some r>ϱr>\varrho, \qquad \gamma\delta_r>\Delta_f$$ This ensures $p_\gamma=\phi$ throughout the neighborhood, so their radius-$\varrho$ Goldstein subdifferentials agree at $x^{t_{\mathrm{out}}}$. Cor. 4 (App. B.3) further establishes **explicit sufficient conditions for stationarity equivalence across regular LL response switches**, even when the uniform positive-gap condition fails.

If these conditions hold almost surely at the returned iterate, the complexity bounds yield E[dist⁡(0,∂ϱϕ(xtout))]≤ε.\mathbb E \left[\operatorname{dist}\left(0,\partial_\varrho\phi(x^{t_{\mathrm{out}}})\right)\right]\leq\varepsilon. Thus, the same O(ε−4)\mathcal O(\varepsilon^{-4}) and O(ε−6)\mathcal O(\varepsilon^{-6}) SFM-call complexities guarantee approximate Goldstein stationarity of ϕ\phi under the additional local conditions and the respective assumptions of Theorems 1–2.

Thank you for the detailed response and additional theoretical and experimental results. These additions help clarify the applicability of the proposed framework. I know that the complexity guarantees can be transferred to Goldstein stationarity of the original bilevel objective under the stated additional conditions. However, the analysis does not establish whether these conditions hold at the algorithmic output. Therefore, my concern regarding the complexity guarantees for the original problem remains, and I will maintain my original rating.

AuthorsOpenReview ↗

Further Clarification and Analysis for Stationarity Transfer

We thank the reviewer for the follow-up and for acknowledging the additional theoretical and experimental results. We provide further clarification regarding stationarity transfer to the original bilevel objective.

As the reviewer has acknowledged, Theorems 1–2 establish finite-time convergence to approximate stationarity of the smoothed penalty, with E∣Gη,ϱ(xtout)∣22≤ε2\mathbb E\\|\mathcal G_{\eta,\varrho}(x^{t_{\mathrm{out}}})\\|_2^2\leq\varepsilon^2. Corollaries 1–2 further establish the corresponding Goldstein stationarity guarantee for the original optimistic objective ϕ\phi under explicit sufficient conditions. These additional conditions reflect the intrinsic difficulty of discrete BLO, where LL response switches can make ϕ\phi discontinuous. Importantly, BiGAP addresses such discontinuities through its penalty formulation and randomized smoothing, enabling provable first-order optimization without differentiating discrete LL responses. Beyond conditional stationarity transfer, the revised manuscript (Corollary 5, App. B.6) establishes an additional original-problem consistency guarantee without requiring the local stationarity-transfer conditions: minimizers of the smoothed penalty recover the original BLO solution set X⋆\mathcal X^\star: dist⁡(xjtout,X⋆)→0\operatorname{dist}(x_j^{t_{\mathrm{out}}},\mathcal X^\star)\to 0 as γj→∞\gamma_j\to\infty, ϱj→0\varrho_j\to0, and γjϱj→0\gamma_j\varrho_j\to0. This complements our finite-time stationarity guarantees and rigorously establishes global solution recovery in the large-penalty, vanishing-smoothing regime.

Moreover, to further address the reviewer's concern at the algorithmic output, we provide an additional probabilistic stationarity-transfer guarantee. Under Hölder-type localization condition that can be verified in our EDA experiment, we establish, for some constants C,C1,C2>0C,C_1,C_2>0: Pr(dist⁡(0,∂ϱϕ(xtout))≤τ)≥1−ε2τ2−C(γ−C1+ρC2).Pr\Big( \operatorname{dist}(0,\partial_\varrho\phi(x^{t_{\mathrm{out}}}))\leq\tau\Big) \geq 1-\frac{\varepsilon^2}{\tau^2} -C(\gamma^{-C_1}+\rho^{C_2}). Here, τ\tau denotes the desired Goldstein stationarity tolerance. For the experiment in Section 5.2, for example, we have C1=C2=1C_1=C_2=1. This result quantitatively connects the finite-time convergence guarantees of Theorems 1–2 to the probability of achieving stationarity of the original BLO objective at the algorithmic output. The details are provided in revised Appendix B.6.

Together, these results establish complementary guarantees at the algorithmic convergence, original-solution recovery, and probabilistic stationarity-transfer levels, further strengthening the theoretical foundation of BiGAP for discrete BLO with discontinuous LL responses.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank all reviewers for their feedback and for recognizing BiGAP's novel theoretical contributions to discrete BLO, its ability to preserve discrete LL decisions without relaxation, and its promising performance on large-scale EDA problems. We provide general responses to common questions as below.

General Response G1. Convergence to the original BLO problem.

For the concern about the connection between convergence of the smoothed penalty and the original BLO objective ϕ\phi, we clarify that our theory establishes several levels of connections between the penalty and ϕ\phi, independently of the additional stationarity-transfer conditions. At the function-value level, Proposition 1 establishes pγ(x)↑ϕ(x)p_\gamma(x)\uparrow\phi(x) and pointwise finite-penalty exactness. Figure 2 illustrates their relationship: ϕ\phi can be discontinuous at LL response switches, while pγp_\gamma connects the jumps through continuous transition regions that narrow as γ\gamma increases. Randomized smoothing further regularizes the kinks in pγp_\gamma, enabling gradient-based optimization. At the solution level, Proposition 7 establishes global-minimizer recovery as γ→∞\gamma\to\infty.

Moreover, local minimizer and stationarity equivalence are inherently challenging due to discontinuous LL response switches (Ye, 1995; Ye and Zhu, 2010; Shen et al., 2025). Theorem 1 establishes convergence to stationarity of the smoothed penalty under fixed choices of ϱ\varrho and γ\gamma. Corollary 1 additionally establishes local minimizer equivalence, while Corollary 2 transfers stationarity to the nonsmooth penalty. The additional local conditions establish the final stationarity level transfer to ϕ\phi. Cor. 4 (App. B.3) further provides checkable sufficient conditions for this transfer even at regular LL response switches.

General Response G2. Applicability and verification of Assumptions 3–4.

For Assumption 3, Appendix D establishes an exact characterization of Lagrangian support (Prop. 8) and checkable sufficient conditions (Prop. 9). In particular, threshold-preserving constraints, including implication and closure constraints, admit exact discrete Lagrangian support. Uniform strict feasibility additionally bounds the supporting multipliers. Together with the regularity and submodularity checks for structured graph-cut applications in Appendix C, these results provide concrete classes of constrained discrete problems satisfying Assumption 3.

For Assumption 4, the O(K−1/2)\mathcal O(K^{-1/2}) saddle-gap convergence and asymptotic smoothed-oracle consistency already hold under Assumptions 1–3 (Prop. 10, App. E). Assumption 4 provides the quantitative saddle-distance control required for the O(K−1/2)\mathcal O(K^{-1/2}) gradient-error rate. We further weaken Assumption 4 from uniform conditioning to averaged saddle regularity, accommodating individual ill-conditioned query points while retaining the stated finite-time convergence guarantee.

We also clarify the different purposes of the original experiments. Section 5.1 illustrates BiGAP's ability to approach a solution at an LL response switch. Section 5.2 evaluates BiGAP-PD's practical effectiveness beyond the analytically verified Assumptions 3–4, using the ISPD98 ibm01 benchmark with 12,752 binary variables. BiGAP-PD substantially outperforms the existing BLO baselines under the same 300-second budget.

We further corroborate practical effectiveness through two new EDA benchmarks. In Appendix G.1, unconstrained OpenROAD GCD verifies Assumption1-2. In Appendix G.3, the DREAMPlace benchmark structurally verifies Assumption 3 for a constrained problem with 210,967 binary LL variables. Its constraints admit uniform strict feasibility with margin σ=1\sigma=1 and preserve feasibility under threshold rounding, guaranteeing exact Lagrangian support for both gg and f+γgf+\gamma g (Prop. 9). We further assess the weakened Assumption 4 empirically along the optimization trajectory and verified the averaged bound. Under the same 50-second budget. Under matched wall-clock budgets, BiGAP achieves the lowest mean error among the compared methods on each benchmark:

BenchmarkBudgetBiGAPBest baseline
OpenROAD GCD300 s2.44482.4578 (CMA-ES)
DREAMPlace adaptec150 s63.1161.8 (CMA-ES)
ISPD98 ibm01300 s445.0813.6 (random search)

The results report means over eight runs, with lower values being better. OpenROAD evaluates penalized design cost and LL optimality, while DREAMPlace and ISPD98 evaluate partition accuracy, LL optimality, and feasibility. The metrics are benchmark-specific. These experiments complement the original theoretical application checks, demonstrating practical effectiveness both in structurally supported settings and beyond instance-wide verified assumptions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.