A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks

By Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, Pengchuan Zhang. Neural Information Processing Systems, 2019

299 citations recorded by the source corpus.

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 this http URL .

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Emergency Medicine

View Paper: https://www.semanticscholar.org/paper/5473175211aff4a8a099c44d1a57802d1b7ecf9e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Emergency Medicine

Citations in the corpus

Adversarial Examples on Object Recognition (2020, background): “More details about each defense strategy follow in Section 7.”
Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond (2020, methodology): “[35] unified these algorithms under the framework of convex relaxation.”
Towards Stable and Efficient Training of Verifiably Robust Neural Networks (2019, methodology): “Besides these deterministic verification approaches, randomized smoothing can be used to certify the robustness of any model in a probabilistic manner (Cohen et al., 2019; Salman et al., 2019a; Lecuyer et al., 2018; Li et al., 2018).”
Algorithms for Verifying Deep Neural Networks (2019, background): “Salman, Yang, Zhang, et al. review and compare methods that use convex relaxations to compute robustness bounds of ReLU networks [43].”
Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observations (2020, background): “Convex relaxation of non-linear units in neural networks enables an efficient analysis of the outer bounds for a neural network [79, 86, 66, 13, 78, 76, 57, 67].”
Provably Robust Deep Learning via Adversarially Trained Smoothed Classifiers (2019, background): “[30] Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang.”
Convergence of Adversarial Training in Overparametrized Neural Networks (2019, background): “[38] Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang.”
Overfitting in adversarially robust deep learning (2020, methodology): “…Dvijotham et al.; Wong et al., 2018; Salman et al., 2019b; Zhang et al., 2019b), randomized smoothing (Cohen et al., 2019; Lecuyer et al., 2019; Salman et al., 2019a), distributional robustness (Sinha et al., 2017), abstract interpretations (Gehr et al., 2018; Mirman et al., 2018; Singh et…”