Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes

By Matt Jordan, Justin Lewis, A. Dimakis. 2019

61 citations recorded by the source corpus.

We propose a novel method for computing exact pointwise robustness of deep neural networks for all convex $\ell_p$ norms. Our algorithm, GeoCert, finds the largest $\ell_p$ ball centered at an input point $x_0$, within which the output class of a given neural network with ReLU nonlinearities remains unchanged. We relate the problem of computing pointwise robustness of these networks to that of computing the maximum norm ball with a fixed center that can be contained in a non-convex polytope. This is a challenging problem in general, however we show that there exists an efficient algorithm to compute this for polyhedral complices. Further we show that piecewise linear neural networks partition the input space into a polyhedral complex. Our algorithm has the ability to almost immediately output a nontrivial lower bound to the pointwise robustness which is iteratively improved until it ultimately becomes tight. We empirically show that our approach generates distance lower bounds that are tighter compared to prior work, under moderate time constraints.

Subfields: Artificial Intelligence, Signal Processing

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 Signal Processing

Citations in the corpus

Why ReLU Networks Yield High-Confidence Predictions Far Away From the Training Data and How to Mitigate the Problem (2018, background): “The picture is produced with the code of [17].”
Globally-Robust Neural Networks (2021, background): “L G ] 11 J un 2021 small models (Fischetti & Jo, 2018; Fromherz et al., 2021; Gehr et al., 2018; Jordan et al., 2019; Tjeng & Tedrake, 2017), requiring several orders of magnitude more time than a typical forward pass of a network; on moderately-large CNNs, these techniques either time out after…”
Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks (2019, background): “This can be done either locally around a specific input [7, 35, 15, 33, 12, 29, 30, 13, 40, 21, 41, 42], or globally by bounding the sensitivity of the function to input perturbations, i.”