# Sound and Complete Verification of Polynomial Networks

arXiv: https://arxiv.org/abs/2209.07235 · HTML: https://mlsanity.com/paper/2209.07235/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 61 references that are in the map.
- First posted on arXiv 15 Sep 2022.

## Builds on (most cited first, 29 of 29)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [Non-local Neural Networks](https://mlsanity.com/paper/1711.07971/) (2017)
- [Theoretically Principled Trade-off between Robustness and Accuracy](https://mlsanity.com/paper/1901.08573/) (2019)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks](https://mlsanity.com/paper/1705.01320/) (2017)
- [Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verification](https://mlsanity.com/paper/2103.06624/) (2021)
- [Algorithms for Verifying Deep Neural Networks](https://mlsanity.com/paper/1903.06758/) (2019)
- [Formal Security Analysis of Neural Networks using Symbolic Intervals](https://mlsanity.com/paper/1804.10829/) (2018)
- [Efficient Decision-based Black-box Adversarial Attacks on Face Recognition](https://mlsanity.com/paper/1904.04433/) (2019)
- [Understanding and Mitigating the Tradeoff Between Robustness and Accuracy](https://mlsanity.com/paper/2002.10716/) (2020)
- [Branch and Bound for Piecewise Linear Neural Network Verification](https://mlsanity.com/paper/1909.06588/) (2019)
- [Are adversarial examples inevitable?](https://mlsanity.com/paper/1809.02104/) (2018)
- [Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Bound](https://mlsanity.com/paper/2205.00263/) (2022)
- [Measuring Neural Net Robustness with Constraints](https://mlsanity.com/paper/1605.07262/) (2016)
- [Deep Polynomial Neural Networks](https://mlsanity.com/paper/2006.13026/) (2020)
- [Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition](https://mlsanity.com/paper/2104.06718/) (2021)
- [Optimization and Abstraction: A Synergistic Approach for Analyzing Neural Network Robustness](https://mlsanity.com/paper/1904.09959/) (2019)
- [Lagrangian Decomposition for Neural Network Verification](https://mlsanity.com/paper/2002.10410/) (2020)
- [Practical No-box Adversarial Attacks against DNNs](https://mlsanity.com/paper/2012.02525/) (2020)
- [Universal Approximation with Quadratic Deep Networks](https://mlsanity.com/paper/1808.00098/) (2018)
- [Adversarial Learning with Margin-based Triplet Embedding Regularization](https://mlsanity.com/paper/1909.09481/) (2019)
- [Augmenting Deep Classifiers with Polynomial Neural Networks](https://mlsanity.com/paper/2104.07916/) (2021)
- [The Spectral Bias of Polynomial Neural Networks](https://mlsanity.com/paper/2202.13473/) (2022)
- [Fast Neural Network Verification via Shadow Prices](https://mlsanity.com/paper/1902.07247/) (2019)
- [Controlling the Complexity and Lipschitz Constant improves polynomial nets](https://mlsanity.com/paper/2202.05068/) (2022)
- [Mathematical Analysis of Adversarial Attacks](https://mlsanity.com/paper/1811.06492/) (2018)

## Built on by (most cited first, 4 of 4)

- [Hadamard product in deep learning: Introduction, Advances and Challenges](https://mlsanity.com/paper/2504.13112/) (2025)
- [One Neuron Saved Is One Neuron Earned: On Parametric Efficiency of Quadratic Networks](https://mlsanity.com/paper/2303.06316/) (2023)
- [DeepBern-Nets: Taming the Complexity of Certifying Neural Networks using Bernstein Polynomial Activations and Precise Bound Propagation](https://mlsanity.com/paper/2305.13508/) (2023)
- [Stochastic Sample Approximations of (Local) Moduli of Continuity](https://mlsanity.com/paper/2509.15368/) (2025)

## Abstract (arXiv)

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.