SOURCE-LINKED INTELLIGENCE

$(\text{DNN})^2$: Doubly Non-Negative Relaxations for Deep Neural Networks

arXiv · AI, language, vision and robotics · article · Aug 25, 2026 · UTC

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

Read original source ↗ Open in workspace

recordType

paper

region

Global