  Adversarial training is well-known to produce high-quality neural network
models that are empirically robust against adversarial perturbations.
Nevertheless, once a model has been adversarially trained, one often desires a
certification that the model is truly robust against all future attacks.
Unfortunately, when faced with adversarially trained models, all existing
approaches have significant trouble making certifications that are strong
enough to be practically useful. Linear programming (LP) techniques in
particular face a "convex relaxation barrier" that prevent them from making
high-quality certifications, even after refinement with mixed-integer linear
programming (MILP) and branch-and-bound (BnB) techniques. In this paper, we
propose a nonconvex certification technique, based on a low-rank restriction of
a semidefinite programming (SDP) relaxation. The nonconvex relaxation makes
strong certifications comparable to much more expensive SDP methods, while
optimizing over dramatically fewer variables comparable to much weaker LP
methods. Despite nonconvexity, we show how off-the-shelf local optimization
algorithms can be used to achieve and to certify global optimality in
polynomial time. Our experiments find that the nonconvex relaxation almost
completely closes the gap towards exact certification of adversarially trained
models.
