Skip to main content
Assured Autonomy Tools Portal
Continual Assurance of Learning-Enabled, Cyber-Physical Systems (LE-CPS)

Efficient Neural Network Verification via Layer-based Semidefinite Relaxations and Linear Cuts

Abstract

We introduce an efficient and tight layer-based semidefinite relaxation for verifying local robustness of neural networks. The improved tightness comes from the combination of semidefinite relaxations and linear cuts. We obtain a computationally efficient method by decomposing the semidefinite formulation into layerwise constraints. By leveraging on chordal graph decompositions, we show that the formulation here presented is provably tighter than the state of the art. Experiments on a set of benchmark networks show that our relaxation enables us to verify more instances compared to other relaxation methods. The results also demonstrate that our SDP relaxation is one order of magnitude faster to solve than previous SDP methods

Year of Conference
2021
Conference Name
International Joint Conference on Artificial Intelligence
Edition
30th
Publisher
IJCAI Organization