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

Richard Y. Zhang

Abstract

The robustness of a neural network to adversarial examples can be provably certified by solving a convex relaxation. If the relaxation is loose, however, then the resulting certificate can be too conservative to be practically useful. Recently, a less conservative robustness certificate was proposed, based on a semidefinite programming (SDP) relaxation of the ReLU activation function. In this paper, we describe a geometric technique that determines whether this SDP certificate is exact, meaning whether it provides both a lower-bound on the size of the smallest adversarial perturbation, as well as a globally optimal perturbation that attains the lower-bound. Concretely, we show, for a least-squares restriction of the usual adversarial attack problem, that the SDP relaxation amounts to the nonconvex projection of a point onto a hyperbola. The resulting SDP certificate is exact if and only if the projection of the point lies on the major axis of the hyperbola. Using this geometric technique, we prove that the certificate is exact over a single hidden layer under mild assumptions, and explain why it is usually conservative for several hidden layers. We experimentally confirm our theoretical insights using a general-purpose interior-point method and a custom rank-2 Burer-Monteiro algorithm.

Introduction

Deep neural networks are notoriously vulnerable to adversarial examples: small, imperceptible perturbations to an input that cause the model to misclassify it. To deploy these models in safety-critical systems, such as autonomous vehicles, mathematical certification is required to guarantee that no perturbation within a certain margin can change the model's output.

Computing this "robustness margin" exactly is an NP-hard optimization problem. Consequently, researchers often employ convex relaxations (such as Linear Programming or Semidefinite Programming) to find a provable lower bound. However, if the relaxation is "loose," the certificate becomes overly conservative, potentially rejecting safe models. This paper investigates the gap between these relaxations and reality, specifically focusing on the SDP relaxation of the ReLU activation function.

Geometric Methodology

The authors introduce a novel geometric technique to analyze the tightness of SDP relaxations. By reformulating the standard adversarial attack problem into a "least-squares" version, they demonstrate that the SDP relaxation of a ReLU layer is mathematically equivalent to projecting a point onto a nonconvex hyperboloid.

Geometric interpretation of the SDP relaxation as a projection onto a hyperboloid.

A key theoretical contribution is the "Major Axis" Condition: the relaxation is proven to be exact if and only if the projection of the input point lies on the major axis of this hyperbola. This provides a clear geometric criterion for when the SDP certificate is perfectly accurate.

Experimental Validation

The theoretical insights were verified using the MNIST dataset across several model architectures, including single-layer ("dense-1"), multi-layer ("dense-3"), and convolutional neural networks (CNNs). To handle the computational complexity of SDP at scale, the authors implemented a custom rank-2 Burer-Monteiro algorithm (BM2), which is more efficient than standard general-purpose solvers.

Key Results

The study reveals a significant "depth penalty" regarding the tightness of SDP relaxations. While the relaxations are often perfectly accurate for shallow networks, they inherently become conservative as depth increases.

  • Single-Layer Success: For single-hidden-layer architectures, the SDP relaxation achieved a 100% success rate in being tight, providing perfectly accurate certificates.
  • Multi-Layer Failure: As depth increased to two or more layers, the success rate for tightness dropped to 0% for many configurations.
Success rate of the SDP relaxation tightness as a function of perturbation radius and network depth.

As illustrated in the figure above, the CNN with one layer ($\\ell=1$) maintains high success across various perturbation radii, whereas the success rate for the two-layer version ($\\ell=2$) is negligible. This occurs because multi-layer networks require projecting onto the intersection of multiple hyperboloids, which rarely aligns in a way that allows for a rank-1 (exact) solution.

Conclusion

While SDP relaxations are less conservative than Linear Programming alternatives, they remain inherently limited for deep networks due to the underlying hyperbolic geometry of the relaxed constraints. Future work must focus on developing relaxation techniques that better account for the interactions between layers and improving the scalability of SDP solvers to make these certificates practical for modern, deep architectures.

Summary updated

Abstract

The robustness of a neural network to adversarial examples can be provably certified by solving a convex relaxation. If the relaxation is loose, however, then the resulting certificate can be too conservative to be practically useful. Recently, a less conservative robustness certificate was proposed, based on a semidefinite programming (SDP) relaxation of the ReLU activation function. In this paper, we describe a geometric technique that determines whether this SDP certificate is exact, meaning whether it provides both a lower-bound on the size of the smallest adversarial perturbation, as well as a globally optimal perturbation that attains the lower-bound. Concretely, we show, for a least-squares restriction of the usual adversarial attack problem, that the SDP relaxation amounts to the nonconvex projection of a point onto a hyperbola. The resulting SDP certificate is exact if and only if the projection of the point lies on the major axis of the hyperbola. Using this geometric technique, we prove that the certificate is exact over a single hidden layer under mild assumptions, and explain why it is usually conservative for several hidden layers. We experimentally confirm our theoretical insights using a general-purpose interior-point method and a custom rank-2 Burer-Monteiro algorithm.
BibTeX
@inproceedings{zhang2020tightness,
  author = {Richard Y. Zhang},
  title = {{On the Tightness of Semidefinite Relaxations for Certifying Robustness to Adversarial Examples}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=YDuPvo3-IXX},
}
Figure