A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks

Abstract

Verification of neural networks enables us to gauge their robustness against adversarial attacks. Verification algorithms fall into two categories: exact verifiers that run in exponential time and relaxed verifiers that are efficient but incomplete. In this paper, we unify all existing LP-relaxed verifiers, to the best of our knowledge, under a general convex relaxation framework. This framework works for neural networks with diverse architectures and nonlinearities and covers both primal and dual views of robustness verification. We further prove strong duality between the primal and dual problems under very mild conditions. Next, we perform large-scale experiments, amounting to more than 22 CPU-years, to obtain exact solution to the convex-relaxed problem that is optimal within our framework for ReLU networks. We find the exact solution does not significantly improve upon the gap between PGD and existing relaxed verifiers for various networks trained normally or robustly on MNIST and CIFAR datasets. Our results suggest there is an inherent barrier to tight verification for the large class of methods captured by our framework. We discuss possible causes of this barrier and potential future directions for bypassing it. Our code and trained models are available at http://github.com/Hadisalman/robust-verify-benchmark .

arXiv commentPoster at the 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada

Cited by in corpus (42)

• Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers
• Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond
• Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers
• Convergence of Adversarial Training in Overparametrized Neural Networks
• Robust Reinforcement Learning on State Observations with Learned Optimal Adversary
• Overfitting in adversarially robust deep learning
• The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification
• The Second International Verification of Neural Networks Competition (VNN-COMP 2021): Summary and Results
• Towards Stable and Efficient Training of Verifiably Robust Neural Networks
• Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observations
• Are Perceptually-Aligned Gradients a General Property of Robust Classifiers?
• Robustness Verification of Tree-based Models
• Denoised Smoothing: A Provable Defense for Pretrained Classifiers
• Algorithms for Verifying Deep Neural Networks
• Randomized Smoothing of All Shapes and Sizes
• Efficient Exact Verification of Binarized Neural Networks
• Learning Security Classifiers with Verified Global Robustness Properties
• Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes
• Verifying Individual Fairness in Machine Learning Models
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition
• ResNets Ensemble via the Feynman-Kac Formalism to Improve Natural and Robust Accuracies
• Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming
• Manifold Regularization for Locally Stable Deep Neural Networks
• Certification of embedded systems based on Machine Learning: A survey
• Improved Image Wasserstein Attacks and Defenses
• Lagrangian Decomposition for Neural Network Verification
• Boosting the Certified Robustness of L-infinity Distance Nets
• Data-Dependent Randomized Smoothing
• Enhancing Certified Robustness via Smoothed Weighted Ensembling
• Scaling the Convex Barrier with Sparse Dual Algorithms
• $n$-ML: Mitigating Adversarial Examples via Ensembles of Topologically Manipulated Classifiers
• An efficient nonconvex reformulation of stagewise convex optimization problems
• Bridging the Gap Between Adversarial Robustness and Optimization Bias
• GoTube: Scalable Stochastic Verification of Continuous-Depth Models
• Certifiable Robustness to Adversarial State Uncertainty in Deep Reinforcement Learning
• ANCER: Anisotropic Certification via Sample-wise Volume Maximization
• Towards Evaluating and Training Verifiably Robust Neural Networks
• Adaptive Verifiable Training Using Pairwise Class Similarity
• Deterministic Certification to Adversarial Attacks via Bernstein Polynomial Approximation
• Expected Tight Bounds for Robust Training
• A Primer on Multi-Neuron Relaxation-based Adversarial Robustness Certification
• Training Efficiency and Robustness in Deep Learning