Research map / Learning theory and algorithms / Combinatorial and search optimization
DeepSaDe: Learning Neural Networks That Guarantee Domain Constraint Satisfaction
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 DeepSaDe, which trains feedforward neural networks with domain constraints guaranteed for all inputs by combining interval-bound propagation to the last layer, MaxSMT (Z3, Fu-Malik) updates for the output layer, and gradient descent for earlier layers.
Problem
Training neural networks whose predictions provably satisfy universally quantified domain constraints over the entire bounded input space, not just the training data, for arbitrary feedforward architectures.
Approach
Extends SaDe (MaxSMT-based linear model training) to deep networks: bounds are propagated through earlier layers via interval arithmetic so the constraint can be encoded on the last linear layer; skip connections feed input features relevant to the constraint to the penultimate layer; the last layer is updated by MaxSMT while earlier layers use gradient descent.
Key results
- DeepSaDe achieves 100% constraint accuracy and AdI = 0 on UC1-UC3, while regularization baselines reach at most 93.5% constraint accuracy (REG on UC1, AdI 0.97).
- On UC1, DeepSaDe MSE is 38.36 versus 30.50 for REG; on UC2 and UC3 differences vs. SL/SBR are not significant.
- DeepSaDe requires roughly 10 to 500 times more training time than baselines across use cases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DeepSaDe instead of REG | UC1 household expense prediction · UC1 household expenses | MSE: 30.50_{\pm 6.49} -> 38.36_{\pm 4.59} | Hurt |
| Use DeepSaDe instead of REG | UC1 household expense prediction · UC1 household expenses | constraint accuracy: 93.50_{\pm 2.01} -> 100_{\pm 0} | Helped |
| Use DeepSaDe instead of SL | UC2 loan prediction · UC2 loan prediction | accuracy: 80.17_{\pm 3.88} -> 80.04_{\pm 4.29} | No clear effect |
| Use DeepSaDe instead of SL | UC3 music genre classification · UC3 music genre | accuracy: 82.53_{\pm 3.58} -> 80.11_{\pm 4.99} | No clear effect |
| Use DeepSaDe instead of SL | UC3 music genre classification · UC3 music genre | constraint accuracy: 99.97_{\pm 0.03} -> 100_{\pm 0} | Helped |
| Use DeepSaDe instead of FFN | UC4 MNIST image-sequence classification · UC4 MNIST image sequence | coherent accuracy: 23.94_{\pm 4.25} -> 6.62_{\pm 1.72} | Hurt |
| Use DeepSaDe instead of FFN | UC4 MNIST image-sequence classification · UC4 MNIST image sequence | constraint accuracy: 88.00_{\pm 3.26} -> 100_{\pm 0} | Helped |
| Use DeepSaDe instead of SL | UC5 sushi preference prediction · UC5 sushi preference | coherent accuracy: 4.06_{\pm 3.33} -> 11.08_{\pm 2.61} | Helped |
| Use DeepSaDe instead of SL | UC5 sushi preference prediction · UC5 sushi preference | constraint accuracy: 100_{\pm 0} -> 100_{\pm 0} | No clear effect |
Surprising findings
- The FFN baseline satisfies the UC5 coherence constraint only 0.04% of the time on test data, showing unconstrained networks essentially never produce coherent preference orders.
- DeepSaDe's predictive performance is worse than FFN on UC4 across all metrics, the cost of hard constraint enforcement.
Limitations
- Training time is 10 to 500 times higher than baselines because MaxSMT is solved at each iteration.
- Hard constraints can reduce predictive performance relative to regularization baselines (e.g., UC1 MSE, UC4 accuracy).
- Interval bound propagation yields very wide latent bounds, and only feedforward networks are handled; CNNs are left for future work.
Experimental setup
Datasets: household expense dataset (UC1) loan prediction dataset (UC2) music genre dataset (UC3) MNIST (UC4) sushi preference dataset (UC5)
Benchmarks: UC1 household expenses UC2 loan prediction UC3 music genre UC4 multi-MNIST sum constraint UC5 sushi preference
Metrics: constraint accuracy Adversity Index (AdI) MSE accuracy coherent accuracy flattened accuracy Jaccard accuracy training time
Baselines: REG SL SBR FFN
Builds on: SaDe Z3 interval arithmetic Adversity Index
Closest papers by meaning
- Enforcing Hard Linear Constraints in Deep Learning Models with Decision Rules (NeurIPS 2025 · similarity 0.88)
- Sample-Specific Output Constraints for Neural Networks (AAAI 2021 · similarity 0.86)
- Teaching the Old Dog New Tricks: Supervised Learning with Constraints (AAAI 2021 · similarity 0.86)
- Position: Adopt Constraints Over Fixed Penalties in Deep Learning (NeurIPS 2026 · similarity 0.83)
- Understanding Certified Training with Interval Bound Propagation (ICLR 2024 · similarity 0.83)
- Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification (NeurIPS 2025 · 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.