SL-SDP: A Scalable Layer-by-Layer SDP Approach for Robustness Analysis of Deep Neural Networks

Ensuring the robustness of neural networks against small input perturbations is essential for their safe deployment in safety-sensitive applications. While semidefinite programming (SDP) provides a principled route to certified robustness, monolithic end-to-end formulations scale poorly due to the global coupling of decision variables across all layers. To overcome this computational bottleneck, this paper develops a scalable layer-by-layer SDP (SL-SDP) scheme that decomposes the monolithic verification problem into a sequence of smaller, tractable SDPs linked through propagated quadratic constraints. Crucially, our recursive approach leverages Schur complement to derive tight, adaptive intermediate bounds with an explicit ellipsoidal interpretation, which in turn yield inexpensive neuron-wise pre-activation intervals and enable more precise abstraction of activation functions. We show how such bounds can be effectively used to tighten the relaxations of ReLU layers. Empirical results demonstrate that SL-SDP significantly improves scalability over end-to-end SDP approaches while preserving accuracy.