Deep neural networks are notoriously fragile; small, imperceptible perturbations to an input—known as adversarial attacks—can cause them to make confident, incorrect predictions. To deploy these networks in safety-critical domains like aviation or autonomous driving, we require formal verification: a mathematical guarantee that for a given input, no small change can flip the output label.
Verification methods generally fall into two categories. Complete methods provide exact answers but are NP-hard and fail to scale. Incomplete methods use convex relaxations to approximate network behavior; while faster, they are often too imprecise (loose), failing to prove robustness even when a network is actually safe. This paper introduces RLT-SDP, a method that significantly tightens this "relaxation gap" by combining Semidefinite Programming (SDP) with the Reformulation-Linearisation Technique (RLT).
Methods: The RLT-SDP Framework
The proposed Layer RLT-SDP builds on two mathematical pillars. First, Semidefinite Programming (SDP) handles quadratic constraints, making it a natural fit for modeling the ReLU function ($y = \max(0, x)$). Second, the Reformulation-Linearisation Technique (RLT) generates new, valid linear constraints (cuts) by multiplying existing linear constraints together.
These RLT cuts capture complex inter-layer and intra-layer dependencies between neurons that standard methods ignore. To maintain computational tractability, the authors utilize a layerwise formulation and an iterative algorithm that prioritizes cuts based on the magnitude of the network's weights.
Key Insights: The Power of Selective Cuts
A critical finding of this research is that capturing hidden dependencies does not require adding every possible RLT cut. The authors demonstrate that adding just a fraction of the most influential cuts provides the bulk of the tightening improvement. This creates a "sweet spot" between precision and speed.
By using RLT, the method effectively "shrinks" the space of possible adversarial errors. The authors mathematically prove that their RLT-SDP relaxation is strictly tighter than previous state-of-the-art SDP and Linear Programming (LP) relaxations.
Experimental Results
The method was evaluated on randomly generated ReLU networks and standard MNIST benchmarks. The results show a dramatic jump in certified robustness—the percentage of images for which the method can prove no adversarial attack exists. For a specific MNIST network with 10,000 nodes, previous methods certified 0% of cases, while RLT-SDP certified 82%. RLT-SDP consistently outperformed other high-performance tools like $\beta$-CROWN, PRIMA, and DeepPoly across various benchmarks.
Limitations and Future Work
While more efficient than previous "Global SDP" approaches, RLT-SDP remains more computationally intensive than simple LP methods. It is best suited for scenarios where high precision is paramount. Future work involves integrating these RLT cuts into faster dual-optimization frameworks to combine the tightness of SDP with the speed of bound propagation, potentially scaling these guarantees to even larger models.
Summary updated