  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.
