Anytime Primal-Dual Neural Robustness Radius

Integrate this into a verifier for a trained ReLU MLP or CNN whose local robustness problem can be expressed as an LP relaxation. For input x and a target class margin, build a sound linear relaxation: input variables satisfy perturbation constraints, affine layers contribute equality constraints, and each ReLU contributes convex-hull inequalities using preactivation bounds. Put all variables and the radius r into v, construct A, b, and c, and initialize S0 from nominal forward-path variables and T0 from dual multipliers associated with input and output-margin constraints. Pseudocode is: build (A,b,c); initialize S,T; repeat solve max c^T S theta subject to AS theta<=b; solve min b^T T alpha subject to A^T T alpha=c and alpha>=0; record [L,U]; if U-L<=tau*max(1,abs(U)), stop; otherwise add variables with largest primal reduced-cost or constraint-violation score and dual directions with largest residual, then expand S and T. The neural LP relaxation is standard; the transferred mechanism is the independently valid, monotone primal-dual hierarchy. Compute all certificate inequalities in the reduced solver and directly check their residuals in the full space. Test first on small MNIST ReLU networks against a full LP verifier and a warm-started full solve under equal time budgets. Include primal-only and dual-only ablations. The preregistered signature is monotone L_j and U_j with nonincreasing W_j at every expansion, at least 99.9% interval coverage of the full LP optimum, and at least 2x median speedup to a 2% relative width. Reject the transfer if any certificate excludes the full optimum, if W_j increases on more than 1% of expansions, or if target-width time is not lower than the warm-started baseline.