Sharp Singularity-Degree Bounds for Equality-Generated SDP-RLT Relaxations of Binary Programs

What the math gives to ML

The paper gives an explicit rank–nullity bound on the singularity degree of an SDP relaxation built from binary variables and equality-generated RLT constraints: for A of rank r, at most min(r,n-r) facial-reduction rounds are needed, and this is sharp. This is transferable to neural systems that contain SDP-based differentiable layers for structured binary decisions, such as exact-cardinality selection, matching, routing, or discrete latent-variable inference. The practical asset is not the binary modeling itself but an a priori degeneracy budget that can control facial-reduction depth, solver tolerances, and numerical safeguards before expensive training begins. The idea is moderately narrow because it applies when a neural module genuinely solves an SDP relaxation rather than ordinary unconstrained network training.