On the Tightness of Semidefinite Relaxations for Certifying Robustness to Adversarial Examples

The robustness of a neural network to adversarial examples can be provably\ncertified by solving a convex relaxation. If the relaxation is loose, however,\nthen the resulting certificate can be too conservative to be practically\nuseful. Recently, a less conservative robustness certificate was proposed,\nbased on a semidefinite programming (SDP) relaxation of the ReLU activation\nfunction. In this paper, we describe a geometric technique that determines\nwhether this SDP certificate is exact, meaning whether it provides both a\nlower-bound on the size of the smallest adversarial perturbation, as well as a\nglobally optimal perturbation that attains the lower-bound. Concretely, we\nshow, for a least-squares restriction of the usual adversarial attack problem,\nthat the SDP relaxation amounts to the nonconvex projection of a point onto a\nhyperbola. The resulting SDP certificate is exact if and only if the projection\nof the point lies on the major axis of the hyperbola. Using this geometric\ntechnique, we prove that the certificate is exact over a single hidden layer\nunder mild assumptions, and explain why it is usually conservative for several\nhidden layers. We experimentally confirm our theoretical insights using a\ngeneral-purpose interior-point method and a custom rank-2 Burer-Monteiro\nalgorithm.\n