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

We propose a novel method for computing exact pointwise robustness of deep neural networks for all convex lp norms. Our algorithm, GeoCert, finds the largest lp ball centered at an input point x0, 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.