Abstract
Remarkable progress has been made on verification of neural networks, i.e., showing that neural networks are provably consistent with specifications encoding properties like adversarial robustness. Recent methods developed for scalable neural network verification are based on computing an upper bound on the worst-case violation of the specification. Semidefinite programming (SDP) has been proposed as a means to obtain tight upper bounds. However, SDP solvers do not scale to large neural networks. We introduce a Lagrangian relaxation based on the SDP formulation and a novel algorithm to solve the relaxation that scales to networks that are two orders of magnitude larger than the off-the-shelf SDP solvers. Although verification of neural networks is known to be NP-hard in general, we develop the first known sufficient conditions under which a polynomial time verification algorithm (based on the above relaxation) is guaranteed to perform exact verification (i.e., either verify a property or establish it is untrue). The algorithm can be implemented using primitives available readily in common deep learning frameworks. Experiments show that the algorithm is fast, and is able to compute tight upper bounds on the error rates under adversarial attacks of convolutional networks trained on MNIST and CIFAR-10.
Introduction
Neural networks are notoriously vulnerable to adversarial examples—tiny, imperceptible perturbations to an input that cause the model to misclassify it. To deploy these models in safety-critical systems, we need more than just empirical testing; we need formal verification (or certification) that proves a network is robust against all possible perturbations within a certain range.
The challenge is a classic computational trade-off: complete verification is exact but NP-hard, while Linear Programming (LP) relaxations are fast but often produce "loose" bounds. Semidefinite Programming (SDP) relaxations offer much tighter bounds than LP, but standard solvers are computationally expensive and fail on modern, large-scale convolutional networks. This paper introduces a scalable Lagrangian relaxation for neural network verification that bridges this gap, providing a novel algorithm (PGD-SDP) that is two orders of magnitude faster than traditional SDP solvers.
Methodology: Scalable SDP Relaxation
The authors develop a Lagrangian relaxation of the SDP formulation for neural network verification. Their approach involves several key technical innovations:
- PGD-SDP Algorithm: Instead of using off-the-shelf SDP solvers, they reformulate the dual problem into a form that can be solved using a projected subgradient method. This allows the verification process to use standard deep learning primitives like convolutions and backpropagation, making it highly efficient on GPUs.
- Decomposing Constraints: They break down a massive, global Positive Semidefinite (PSD) constraint into a series of smaller, layer-wise constraints.
- Diagonal Dominance: To further speed up computation, they simplify these layer-wise PSD constraints using the concept of "diagonal dominance," reducing complex matrix requirements into simpler, element-wise operations.
Exactness Characterization
A primary contribution of this work is the mathematical characterization of "exactness." The authors prove that if a network is "locally linear" in a sufficiently large region around an adversarial example, their relaxation is tight (meaning the bound it finds is the true worst-case error).
The paper identifies that adversarial training actually promotes local linearity. Because their verifier is proven to be exact for locally linear regions, this explains why the relaxation works so well on robustly trained networks.
Experimental Evaluation
The researchers evaluated their algorithm on standard image classification benchmarks, including MNIST and CIFAR-10. They specifically tested on "foreign" networks that were not trained to be easily verifiable, which is a much harder task for most verifiers.
Key Results
- Massive Speedup: On the PGD-NN model, the PGD-SDP algorithm took an average of 130 seconds per example, compared to 8,100 seconds for previous SDP-based methods—a roughly 60x improvement.
- Superior Tightness: On models where LP methods often fail (e.g., Grad-NN), PGD-SDP achieved a verified error rate of 16.32%, while LP-based methods were stuck at a useless 97%.
- Scalability: They successfully verified networks two orders of magnitude larger than those handled by previous SDP solvers, showing linear scaling with respect to the size of the network.
Discussion and Future Work
While PGD-SDP represents a significant leap in scalability and tightness, some limitations remain. The subgradient method can still require thousands of iterations to converge for some examples, which may be slow for real-time applications. Furthermore, the current work focuses on feedforward and convolutional networks with ReLU activations. Extending this to more complex architectures like Transformers or different activation functions remains a future challenge. Finally, on some models, a gap remains between the verified bound and empirical attack error, suggesting room for even tighter scalable relaxations.
Summary updated