Iteratively Enhanced Semidefinite Relaxations for Efficient Neural Network Verification

Jianglin Lan, Yang Zheng, Alessio Lomuscio

Introduction: The Robustness Challenge

Ensuring neural network (NN) robustness against adversarial attacks is critical for safety-critical applications like autonomous driving and medical diagnostics. Verification tools typically face a trade-off: complete verifiers provide perfect accuracy but are computationally prohibitive, while incomplete verifiers are fast but often yield "false negatives"—failing to prove properties that are actually true due to loose approximations.

The Convex Relaxation Barrier

The primary obstacle in NN verification is the non-convexity of activation functions like the Rectified Linear Unit (ReLU). To make verification tractable, researchers often "relax" these functions into convex shapes. However, these relaxations lose information. In deep networks, these errors compound, resulting in a "loose" approximation that cannot prove robustness even for safe models. While Semidefinite Programming (SDP) offers tighter bounds than Linear Programming (LP), standard SDPs either fail to scale or remain insufficiently tight for complex architectures.

Methodology: The IterSDP Approach

This paper introduces IterSDP, a novel verification framework that bridges the gap between efficiency and tightness by incorporating a nonlinear constraint into SDP relaxations.

1. Nonlinear Rank-One Constraint

The authors introduce a specific nonlinear constraint—$v_i^T(P_i - x_i x_i^T)v_i = 0$—to the existing LayerSDP framework. This constraint enforces the "rank-one" property of semidefinite matrices, ensuring the relaxation more closely mirrors the actual behavior of the neural network.

2. Iterative Optimization

Since adding nonlinear constraints makes the optimization problem non-convex, the authors propose an iterative algorithm. Instead of solving the non-convex problem directly, IterSDP solves a sequence of auxiliary convex SDPs. This approach is mathematically proven to produce solutions that are strictly tighter than previous methods, converging toward the optimal solution of the enhanced model.

The IterSDP algorithm starts with a base LayerSDP and iteratively refines the result using auxiliary SDPs until convergence or a robustness proof is found.

The "layer-based" structure is essential for scalability. By utilizing smaller matrices for each layer rather than a single global matrix, IterSDP significantly reduces memory requirements and computational time.

Experimental Evaluation

The researchers evaluated IterSDP on standard robustness benchmarks using MNIST and CIFAR-10 across various architectures, including small-to-large MLPs and adversarially trained networks.

Key Results

IterSDP demonstrated substantial improvements in verified robustness—the percentage of inputs proven safe from attacks.

  • Enhanced Precision: On the MLP-9×100 benchmark, IterSDP achieved 47% verified robustness, significantly outperforming LayerSDP (35%) and global SDP (22%).
  • Closing the Gap: In several instances, IterSDP reached the "PGD bound," the theoretical upper limit of robustness identified by the strongest known attacks.
  • Computational Efficiency: While IterSDP is approximately 2x slower than the basic LayerSDP, it is far more scalable than global SDP methods (SDP-IP), which often fail to process larger models.
Comprehensive comparison of IterSDP against state-of-the-art verifiers across multiple MLP architectures. Bold values indicate the highest verified robustness achieved by an incomplete verifier.

Discussion and Future Work

IterSDP represents a significant advancement in the "middle ground" of verification, offering high tightness with moderate computational overhead. However, challenges remain. While it is more efficient than global SDPs, it is slower than linear relaxation methods like $\beta$-CROWN. Furthermore, while convergence is fast in practice, analytical upper bounds on iteration counts are yet to be established. Future research will focus on extending this iterative approach to Convolutional Neural Networks (CNNs) to broaden its applicability to modern computer vision tasks.

Summary updated

Abstract

We propose an enhanced semidefinite program (SDP) relaxation to enable the tight and efficient verification of neural networks (NNs). The tightness improvement is achieved by introducing a nonlinear constraint to existing SDP relaxations previously proposed for NN verification. The efficiency of the proposal stems from the iterative nature of the proposed algorithm in that it solves the resulting non-convex SDP by recursively solving auxiliary convex layer-based SDP problems. We show formally that the solution generated by our algorithm is tighter than state-of-the-art SDP-based solutions for the problem. We also show that the solution sequence converges to the optimal solution of the non-convex enhanced SDP relaxation. The experimental results on standard benchmarks in the area show that our algorithm achieves the state-of-the-art performance whilst maintaining an acceptable computational cost.
BibTeX
@inproceedings{lan2023iteratively,
  author = {Jianglin Lan and Yang Zheng and Alessio Lomuscio},
  title = {{Iteratively Enhanced Semidefinite Relaxations for Efficient Neural Network Verification}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i12.26744},
}
Figure