# Primal-Dual Gap Training Certificate

- ID: 847
- Canonical URL: https://synthcore.org/idea/847/primal-dual-gap-training-certificate
- API JSON: https://synthcore.org/api/idea/847.json
- API Markdown: https://synthcore.org/api/idea/847.md
- Verification status: unverified
- Source: [arXiv:2607.13256](https://arxiv.org/abs/2607.13256)
- Category: regularization
- Solves: stability, accuracy, generalization
- ML areas: loss, regularization, optimizer
- Math tags: convex-analysis, optimization, duality
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Train a neural predictor using an explicit primal-dual gap instead of only a constraint residual. The gap measures objective suboptimality and constraint violation together, and can provide a principled per-example stopping rule for inner optimization or test-time refinement.

## Mathematical statement

The paper uses the computable certificate \(\eta_{\mathrm{gap},h}^{2}(\widehat{p}_{h},\bm{u}_{h})=I_{h}^{cr}(\widehat{p}_{h})-D_{h}^{rt}(\bm{u}_{h})\), where \(I_h^{cr}\) is the discrete primal energy evaluated at a pressure-like variable \(\widehat p_h\), \(D_h^{rt}\) is the discrete dual energy evaluated at a flux-like variable \(\bm u_h\), and weak duality implies \(I_h^{cr}-D_h^{rt}\geq0\). For an ML adaptation, let \(z_\theta(x)\) be the predicted primal vector, \(y_\phi(x)\) equality multipliers, \(A z=b\) equality constraints, and \(\ell\leq Cz\leq r\) bilateral inequalities. Let \(Q\succ0\), and define \(P(z)=\frac12z^TQz-c^Tz+I_{\{Az=b,\,\ell\leq Cz\leq r\}}(z)\). With nonnegative lower and upper multipliers \(\lambda_+,\lambda_-\), use \(\lambda=\lambda_+-\lambda_-\) and \(D(y,\lambda)=-\frac12(A^Ty+C^T\lambda+c)^TQ^{-1}(A^Ty+C^T\lambda+c)-b^Ty-r^T\lambda_++\ell^T\lambda_-\). The training gap is \(G=P-D\), which is nonnegative for primal-dual feasible pairs.

## Key formulas

- $$\eta_{\mathrm{gap},h}^{2}(\widehat{p}_{h},\bm{u}_{h})=I_{h}^{cr}(\widehat{p}_{h})-D_{h}^{rt}(\bm{u}_{h})$$
- $$P(z)=\frac12z^TQz-c^Tz+I_{\{Az=b,\;\ell\leq Cz\leq r\}}(z)$$
- $$D(y,\lambda)=-\frac12(A^Ty+C^T\lambda+c)^TQ^{-1}(A^Ty+C^T\lambda+c)-b^Ty-r^T\lambda_++\ell^T\lambda_-$$
- $$\mathcal{L}_{\mathrm{train}}=\mathcal{L}_{\mathrm{task}}(z_\theta,z^*)+\gamma\frac{G(z_\theta,y_\phi,\lambda)}{1+|P(z_\theta)|+|D(y_\phi,\lambda)|}$$

## Implementation notes

Integrate the method into a network that predicts structured outputs such as flows, allocations, graph states, or controls. The predictor produces a primal vector z_theta(x); a second head produces equality multipliers y_phi(x) and two unconstrained multiplier logits. Convert the logits to nonnegative multipliers with lambda_plus=softplus(s_plus) and lambda_minus=softplus(s_minus), then set lambda=lambda_plus-lambda_minus. Choose a positive-definite Q, preferably diagonal for the first experiment, and fixed matrices A and C describing equality and inequality constraints. Compute P from the quadratic objective and compute D from the displayed Fenchel-style formula. During early training, replace the hard indicator in P with a squared violation penalty, or project z before evaluating P. Use G=P-D as an auxiliary loss, clipping or applying softplus(G) only to handle floating-point negativity. Pseudocode is: z,y,sp,sm=net(x); lp=softplus(sp); lm=softplus(sm); lam=lp-lm; q=A.T@y+C.T@lam+c; P=.5*z.T@Q@z-c.T@z+penalty(A@z-b,C@z); D=-.5*q.T@Qinv@q-b.T@y-r.T@lp+l.T@lm; loss=task_loss+gamma*G/(1+abs(P)+abs(D)). The mathematical component is the primal-dual gap; estimate Q inverse with a diagonal inverse or conjugate-gradient solve. First test a two-layer MLP predicting 100-dimensional allocations with one sum constraint and box bounds. Compare MSE plus residual penalty against MSE plus the gap, measuring violation rate, objective suboptimality against a quadratic-program solver, gap calibration, and loss descent at equal FLOPs.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.