Lagrangian Decomposition for Neural Network Verification
This addresses the need for efficient and accurate verification methods in safety-critical AI applications, representing a novel method for a known bottleneck rather than a foundational breakthrough.
The paper tackles the problem of computing tight bounds for neural network verification by proposing a Lagrangian Decomposition approach, which yields bounds at least as tight as previous dual algorithms and achieves comparable results to off-the-shelf solvers in a fraction of the time, with empirical speed-ups for formal verification.
A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. Previous methods have either used off-the-shelf solvers, discarding the problem structure, or relaxed the problem even further, making the bounds unnecessarily loose. We propose a novel approach based on Lagrangian Decomposition. Our formulation admits an efficient supergradient ascent algorithm, as well as an improved proximal algorithm. Both the algorithms offer three advantages: (i) they yield bounds that are provably at least as tight as previous dual algorithms relying on Lagrangian relaxations; (ii) they are based on operations analogous to forward/backward pass of neural networks layers and are therefore easily parallelizable, amenable to GPU implementation and able to take advantage of the convolutional structure of problems; and (iii) they allow for anytime stopping while still providing valid bounds. Empirically, we show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time, and obtain tighter bounds in the same time as previous dual algorithms. This results in an overall speed-up when employing the bounds for formal verification. Code for our algorithms is available at https://github.com/oval-group/decomposition-plnn-bounds.