(DNN)²: Tighter, Certifiable Relaxations for ReLU Network Verification
zhenjun_zhao · x · 2026-08-26
Researchers from MIT et al. propose (DNN)², a doubly non-negative relaxation method for ReLU network verification.
- Background: existing LP/SDP relaxations are overly conservative due to relaxation gaps; the completely positive program (CPP) closes the gap but is NP-hard, and its cheapest tractable relaxation, the doubly non-negative program (DNN), exceeds the reach of interior-point methods at scale.
- Method: the authors extend Burer-Monteiro (BM) factorization to the strictly tighter DNN formulation, and address the non-uniqueness of dual multipliers caused by non-negativity constraints with a novel eigenvalue maximization procedure that searches for a valid global optimality certificate.
- Results: bounds are consistently tighter than standard SDP, often matching the exact solution, and the certification procedure confirms global optimality when a valid certificate exists.
More from Research
- LightNav-0: A Generalist Navigation Brain for Any Robot — teortaxesTex · 2026-08-26
- New research on testing causal graphs with measurement errors — yudapearl · 2026-08-26
- CoRL 2026 Agentic Robotics Workshop Calls for Demos and Papers — GuanyaShi · 2026-08-26
- Prime Intellect proposes 4-tier memory hierarchy for agents — ChrisGPT · 2026-08-26
- NTU to host IAS Frontiers Conference on Geometry, Dynamics, and Learning (GDL'26) — FrnkNlsn · 2026-08-26
- DeepSeek V4 Review: Frontier at CVE Finding, Weak on Hallucination — teortaxesTex · 2026-08-26