Towards Verification of General Neural Networks: A Dual Approach
summary
Poses verification as an optimization and uses a dual Lagrangian relaxation to upper‑bound worst‑case adversarial scores; proves NP‑hardness for even one hidden layer but gives exact/approximate guarantees for two‑layer nets and tight bounds on MNIST up to epsilon ≈ 30 (about 10% grayscale). Implements a learned verifier network to predict dual variables, folding verification into training; same architecture yields better verified accuracy and drops wall‑clock training from ~5 hours to ~20 minutes.
AI-written summary · about
chapters (18)
- 0:00Start
- 2:52Specifying tasks
- 3:35What is supervised learning? Training Data
- 5:52Algorithmic bias and fairness
- 6:20We need richer specifications for ML models
- 9:56Defenses against adversarial examples
- 11:01Worst-case guarantees: Verification Module level verification
- 13:23Hardness of verification in general
- 15:35Comparison to prior work on verification of NNS
- 21:29Verification as optimization
- 23:06Layers as constraints
- 24:41Lagrangian relaxation
- 26:30Verification using duality: advantages
- 27:43Results: Adversarial attacks
- 29:30Results: Classifier stability
- 31:25Learning verifiers
- 32:40Open questions and challenges Tractable verification: Under what conditions can verification be done tractably? Results for single hidden layer networks. can be extended beyond?
- 33:16Open questions and challenges Tractable verification: Under what conditions can verification be done tractably? Results for single hidden layer networks - can be extended beyond?
related talks
16mVerification of Neural Networks' Global Robustness
20mIncremental Verification of Neural Networks
55mTowards Verified Deep Learning
17mInput-Relational Verification of Deep Neural Networks
11mExploiting Verified Neural Networks via Floating Point Numerical Error
27mProof Minimization in Neural Network Verification
59mDifferential Verification of Deep Neural Networks
26mTowards a Certified Proof Checker for Deep Neural Network Verification