Sound and Complete Verification of Polynomial Networks
This work addresses the robustness verification problem for PNs, which is crucial for their adoption in safety-critical domains, representing an incremental advancement in neural network verification methods.
The paper tackles the problem of verifying the robustness of Polynomial Networks (PNs) for real-world applications by developing a new verification method called VPN, which achieves sound and complete verification with tighter bounds than existing baselines, empirically validated on datasets like MNIST, CIFAR10, and STL10.
Polynomial Networks (PNs) have demonstrated promising performance on face and image recognition recently. However, robustness of PNs is unclear and thus obtaining certificates becomes imperative for enabling their adoption in real-world applications. Existing verification algorithms on ReLU neural networks (NNs) based on classical branch and bound (BaB) techniques cannot be trivially applied to PN verification. In this work, we devise a new bounding method, equipped with BaB for global convergence guarantees, called Verification of Polynomial Networks or VPN for short. One key insight is that we obtain much tighter bounds than the interval bound propagation (IBP) and DeepT-Fast [Bonaert et al., 2021] baselines. This enables sound and complete PN verification with empirical validation on MNIST, CIFAR10 and STL10 datasets. We believe our method has its own interest to NN verification. The source code is publicly available at https://github.com/megaelius/PNVerification.