GP Upper Bounds for ReLU Verification
Implementation & benchmark of arXiv:2608.27707 — Solution Methods for Infinite-Dimensional Generalized Disjunctive Programming
Source paper: Solution Methods for Infinite-Dimensional Generalized Disjunctive Programming arXiv:2608.27707 ⓘ · analyzed Sep 1, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Use the paper's MBM-GP construction to predict input-dependent big-M constants for ReLU disjunctions during neural-network verification. Exact activation-bound optimization is performed only at a small subset of input points, while a Gaussian-process upper confidence bound supplies conservative bounds elsewhere, reducing verifier preprocessing and potentially tightening the MILP compared with one global worst-case constant.
Formulas
Mathematical statement
The paper's multiple-big-M constraint is $r_{ij}(y(d))\leq\sum_{i'\neq i}M_{ii'}(d)w_{i'j}(d)$, where $d$ is a domain point, $r_{ij}$ is the constraint residual for disjunct $i$, $w_{i'j}(d)\in\{0,1\}$ indicates an alternative disjunct, and $M_{ii'}(d)$ is a valid relaxation bound. The exact pointwise bound is computed by $M_{ii',k}=\max_{y_k}r_{ij}(y_k)$ subject to $r_{i'j}(y_k)\leq0$ and box bounds $y^L\leq y_k\leq y^U$. For a ReLU unit with preactivation $a(x)$ and output $h(x)=\max(0,a(x))$, use the disjunction $[h=0,\ a\leq0]\vee[h=a,\ a\geq0]$ and learn the pointwise upper bound $U(x)=\max_{x'\in\mathcal X_x}a(x')$. Fit a GP to exact values $M(x_s)$ at sampled locations $x_s$, with posterior mean $\mu(x)$ and standard deviation $\sigma(x)$, and set the conservative bound $\widehat M(x)=\mu(x)+\kappa\sigma(x)$. Here $\kappa\geq0$ is a confidence factor. Since GP coverage is not automatically a proof, calibrate $\kappa$ on held-out exact solves and fall back to the analytic or global bound whenever the envelope fails.
Implementation notes
Integrate this into the preprocessing stage of a MILP-based verifier such as a custom ReLU verification model. For every ReLU whose preactivation bound is currently obtained by an expensive LP, identify a low-dimensional domain coordinate: the scalar verification parameter, a one-dimensional perturbation radius, or a projected input coordinate. First choose support points $x_s$ spanning the verification domain and solve the exact LP at each support to obtain $U_s=\max a(x)$ under the verifier's input constraints. Fit a GP with an RBF or Matérn kernel to $(x_s,U_s)$. At unsolved points, predict the mean and standard deviation and insert $\widehat U(x)=\mu_U(x)+\kappa\sigma_U(x)$ into the ReLU big-M constraints. Apply the same procedure to $-a$ for lower bounds. Periodically audit random predicted points with exact LPs; if an exact value exceeds the prediction, add that point to the training set and increase $\kappa$. Pseudocode: S=initial_supports(); U=exact_LP_bounds(S); gp=fit_gp(S,U); for x in required_points: M[x]=gp.mean(x)+kappa*gp.std(x); if audit and exact_LP(x)>M[x]: S.append(x); U.append(exact_LP(x)); refit(gp); kappa*=1.1; build_relu_MILP(M). The mathematical quantities are the exact pointwise bound and GP upper-confidence envelope; kernel choice, support selection, and calibration are empirical. Test first on MNIST or ACAS-X with a 3- to 6-layer ReLU MLP, comparing global interval bounds, exact LP bounds everywhere, and MBM-GP with 5%, 10%, and 20% support coverage. Success requires lower preprocessing or MILP solve time at identical verified accuracy and zero false-safe certificates on a large held-out audit set.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.