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.

该研究提出了一种计算具有凸性 $p$- 范数的深度神经网络的点对点鲁棒性的新方法，算法 GeoCert 可以在复杂的神经网络中输出距离下界，且该方法比以前的方法更紧凑。