  We improve the effectiveness of propagation- and linear-optimization-based
neural network verification algorithms with a new tightened convex relaxation
for ReLU neurons. Unlike previous single-neuron relaxations which focus only on
the univariate input space of the ReLU, our method considers the multivariate
input space of the affine pre-activation function preceding the ReLU. Using
results from submodularity and convex geometry, we derive an explicit
description of the tightest possible convex relaxation when this multivariate
input is over a box domain. We show that our convex relaxation is significantly
stronger than the commonly used univariate-input relaxation which has been
proposed as a natural convex relaxation barrier for verification. While our
description of the relaxation may require an exponential number of
inequalities, we show that they can be separated in linear time and hence can
be efficiently incorporated into optimization algorithms on an as-needed basis.
Based on this novel relaxation, we design two polynomial-time algorithms for
neural network verification: a linear-programming-based algorithm that
leverages the full power of our relaxation, and a fast propagation algorithm
that generalizes existing approaches. In both cases, we show that for a modest
increase in computational effort, our strengthened relaxation enables us to
verify a significantly larger number of instances compared to similar
algorithms.
