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

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 isachallenging problem ingeneral, howeverweshowthat 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 polyhedralcomplex.