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

Richard Y. Zhang

The Challenge of Certifying Robustness

Deep neural networks are notoriously vulnerable to adversarial examples—tiny, often invisible perturbations to an input that cause a model to make confident mistakes. To safely deploy these models in critical areas like autonomous driving, empirical "attacks" are not enough. We need mathematical robustness certificates proving that no perturbation within a certain size can alter the model's output.

Because finding the exact smallest adversarial perturbation (the robustness margin) is an NP-hard optimization problem, researchers often rely on convex relaxations, such as semidefinite programming (SDP), to find a lower bound on this margin. However, if the relaxation is "loose," the resulting lower bound might be too conservative to be practically useful. This paper provides a geometric explanation for when SDP relaxations are "tight" (exact), proving that while these certificates are often exact for single-layer networks, they inherently become loose as more layers are added.

A Geometric Perspective on SDP Relaxations

To analyze the tightness of these relaxations, the author introduces a geometric technique focused on the SDP relaxation of the ReLU activation function. Instead of the standard adversarial attack problem, the study analyzes a mathematically cleaner "least-squares" restriction that still captures the core difficulty.

The paper demonstrates that the SDP relaxation of a single ReLU neuron is equivalent to projecting a point onto a spherical cap. When scaled to an entire network, the problem transforms into projecting a point onto a nonconvex hyperboloid (a high-dimensional hyperbola).

The critical finding is the Major Axis Rule: the relaxation is exact if and only if the projection of the input point lies exactly on the major axis of this hyperbola. If the "target" adversarial output is well-aligned with the network's weights, the SDP relaxation is perfect; if it is off-axis, the relaxation becomes conservative.

Key Insights: The Multi-Layer Curse and Radius Sensitivity

The theoretical insights were validated using the MNIST dataset across different architectures, including single-layer dense networks, multi-layer dense networks, and Convolutional Neural Networks (CNNs). The results highlight a stark contrast between shallow and deep networks.

Success rate of the SDP relaxation across different architectures and layers.

For a single hidden layer, the SDP relaxation is almost always tight under mild assumptions. In experiments with a CNN, the SDP relaxation was 100% tight for a single layer. However, this success rate plummeted to 0% tight for two or more layers. This "multi-layer curse" occurs because, in deeper networks, the convex ball constraint of one layer is replaced by the nonconvex hyperbolic constraint of the previous layer. This complex hyperbolic geometry makes it significantly harder for the projection to land on the major axis.

Comparison of actual vs. relaxed bounds showing tightness across different perturbation radii.

Furthermore, the tightness of the relaxation is highly sensitive to the perturbation radius ($\rho$). For single-layer models, the relaxation tends to be tight when the radius is very small (local robustness) or very large (trivial cases), but it often becomes loose for intermediate values.

Importantly, a "failed" or loose certificate does not necessarily mean the model is vulnerable; it often just means the mathematical relaxation is too pessimistic. Even when not perfectly tight, these relaxations can still produce near-optimal adversarial attacks, offering better empirical bounds than standard gradient-based methods in certain scenarios.

Limitations and Future Directions

The primary limitation of the SDP relaxation approach is its looseness for deep networks. Because modern deep learning relies on architectures with many layers, current SDP certificates remain too conservative for large-scale applications.

To overcome this, future work must focus on:

  1. Algorithmic Efficiency: Developing faster algorithms to solve these SDPs, building on the custom rank-2 Burer-Monteiro algorithm utilized in this study.
  2. New Relaxations: Exploring new types of relaxations or constraints capable of maintaining tightness across multiple layers.
  3. Certified Training: Investigating whether training models specifically to satisfy these "major axis" conditions could make them inherently easier to certify.

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