Research map / Adversarial robustness and security / Certified and empirical robustness
MIBP-Cert: Certified Training against Data Perturbations with Mixed-Integer Bilinear Programs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MIBP-Cert, a deterministic certified training method that encodes each training step (forward, loss, backward, update) as a mixed-integer bilinear program to bound parameters under data perturbations.
Problem
Certifying neural network training against training-time data perturbations and poisoning; existing deterministic bound-based methods (interval/polytope propagation) over-approximate heavily and can diverge over training iterations, and cannot express complex or categorical threat models.
Approach
Cast deterministic training certification as a per-step mixed-integer bilinear program that exactly encodes forward pass, hinge loss, backward pass and parameter update, solving min/max per parameter to get bounds that preserve operand dependencies and can shrink, enabling expressive constraints on real and categorical features.
Key results
- On Two Moons at epsilon=0.01, MIBP-Cert reaches 81.4% certified accuracy (±0.06) versus 71.5% for FullCert and 69.0% for Sosnin et al.
- On Iris 2-class at epsilon=0.1, MIBP-Cert certifies 100% of test points versus 88% for FullCert
- On NPHA with missing mental health values modeled, 98.6% of predictions are certifiable with 56.3% certified accuracy, while over-reporting leaves 91.5% certifiable
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MIBP-Cert instead of FullCert | certified training · Two Moons, ε=0.01 | certified accuracy: 71.5%±11.20 -> 81.4%±0.06 | Helped |
| Use MIBP-Cert instead of Sosnin et al. | certified training · Two Moons, ε=0.01 | certified accuracy: 69.0%±0.10 -> 81.4%±0.06 | Helped |
| Use MIBP-Cert instead of FullCert | certified training · Iris 2-class, ε=0.1 to ε=0.3 | certified accuracy: 88% -> 100%; 76% -> 92%; 20% -> 40% | Helped |
| Use MIBP-Cert instead of FullCert | certified training · Iris full, ε=0.00 to ε=0.02 | certified accuracy: 84% -> 84%; 68% -> 72%; 64% -> 68% | Mixed |
| Use MIBP-Cert instead of FullCert | certified training · Breast Cancer, ε=0.000 to ε=0.010 | certified accuracy: 95% -> 95%; 83% -> 94%; 38% -> 51% | Mixed |
| Allow missing mental health values to be any valid response | MIBP-Cert · NPHA | certified accuracy: 56.3% -> 56.3% | No clear effect |
| Allow missing values across all features to take any valid value | MIBP-Cert · NPHA | certified accuracy: 56.3% -> 53.5% | Hurt |
| Allow mental health over-reporting by one response value | MIBP-Cert · NPHA | certification rate: 100.0% -> 91.5% | Hurt |
| Increase width from 5 to 30 with 2 layers (ablation) | MIBP-Cert · Two Moons, ε=0.01, 1 epoch | training time: 0.75 s -> 27.7 s | Hurt |
| Increase depth from 2 to 6 layers at width 5 (ablation) | MIBP-Cert · Two Moons, ε=0.01, 1 epoch | training time: 0.75 s -> 22.1 s | Hurt |
Surprising findings
- Per-epoch runtime is much higher than baselines: about 19 s to 156 s per epoch versus about 0.01 to 0.05 s for FullCert and CROWN+IBP on Two Moons
- Branch counts grow sharply with batch size and epsilon (e.g., 4 branches at batch 10 and epsilon 0.01 versus 174,552 at batch 100 and epsilon 0.1)
Limitations
- Substantially higher computational cost than interval or polytope baselines, limiting scalability
- Evaluated only on small models (2-layer MLPs with 20 neurons per layer) and small tabular datasets
- Certified accuracy on Two Moons is slightly lower than baselines at very small epsilon (83.3% vs 83.9%)
Experimental setup
Datasets: Two Moons (synthetic) UCI Iris UCI Breast Cancer Wisconsin National Poll on Healthy Aging (NPHA)
Benchmarks: Two Moons UCI Iris UCI Breast Cancer Wisconsin NPHA
Metrics: certified accuracy certification rate runtime per epoch standard deviation across seeds
Baselines: FullCert Sosnin et al. (CROWN+IBP) BagFlip
Builds on: FullCert interval bound propagation BoundFlow Gurobi
Closest papers by meaning
- Halt Fast! Early Stopping for Certified Robustness (NeurIPS 2026 · similarity 0.84)
- Learning Better Certified Models from Empirically-Robust Teachers (NeurIPS 2026 · similarity 0.84)
- On the Scalability of Certified Adversarial Robustness with Generated Data (NeurIPS 2024 · similarity 0.84)
- Position: Exploring the Robustness of Pipeline-Parallelism-Based Decentralized Training (ICML 2024 · similarity 0.84)
- Position: Certified Robustness Does Not (Yet) Imply Model Security (ICML 2025 · similarity 0.83)
- Certified but Private: Scalable Zero-Knowledge Proofs for the Formal Verification of Neural Networks (NeurIPS 2026 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.