Search papers, labs, and topics across Lattice.
This paper introduces a novel approach, $(\text{DNN})^2$, that enhances the verification of rectified linear unit (ReLU) neural networks by addressing the overly-conservative safety guarantees of existing linear and semidefinite program relaxations. By employing an innovative eigenvalue maximization procedure to navigate the non-unique multiplier space, the method achieves significantly tighter bounds compared to standard semidefinite programming, often aligning with exact solutions. The findings represent a substantial advancement in providing scalable and certifiable verification guarantees essential for the deployment of neural networks in safety-critical applications.
Tighter verification bounds for neural networks could finally enable safe deployment in critical systems, challenging the limitations of current relaxation methods.
Existing linear program (LP) and semidefinite program (SDP) relaxations for rectified linear unit (ReLU) neural network (NN) verification yield overly-conservative safety guarantees due to significant relaxation gaps. While the completely positive program (CPP) formulation closes this gap, it is NP-hard to solve. Its cheapest tractable relaxation, the doubly non-negative program (DNN), retains critical constraints as an SDP, but one whose size exceeds the reach of interior-point methods at practical scale. While Burer-Monteiro (BM) factorization has been applied to make SDP-based verification scalable, no such result exists for the strictly tighter DNN formulation. A key obstacle is that additional non-negativity constraints in the DNN cause dual multipliers for optimality certification to be non-unique, making standard certification methods inapplicable. We propose a novel eigenvalue maximization procedure that searches the non-unique multiplier space for a valid certificate, i.e. a global optimality guarantee. Experiments demonstrate that our approach $(\text{DNN})^2$ produces bounds consistently tighter than the standard SDP method, often matching the exact solution, and that our certification procedure confirms global optimality when a valid certificate exists. These results are a key step toward providing tight, certifiable, and computationally scalable verification guarantees needed to deploy neural network controllers and perception modules in safety-critical autonomous systems.
