mlsanityData to 7 Oct 2026

Sound and Complete Verification of Polynomial Networks

arXiv 2209.07235 ↗First posted 15 Sep 2022cs.LG cs.AI cs.CRcited by 4

Not on the map. Why?

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.

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

Builds on

29 of 61 references.

References · 29

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2013Intriguing properties of neural networkscited by 5,114
  4. 2016Towards Evaluating the Robustness of Neural Networkscited by 2,976
  5. 2017Non-local Neural Networkscited by 2,290
  6. 2019Theoretically Principled Trade-off between Robustness and Accuracycited by 1,510
  7. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 739
  8. 2017Formal Verification of Piece-Wise Linear Feed-Forward Neural Networkscited by 241
  9. 2021Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verificationcited by 224
  10. 2019Algorithms for Verifying Deep Neural Networkscited by 221
  11. 2018Formal Security Analysis of Neural Networks using Symbolic Intervalscited by 185
  12. 2019Efficient Decision-based Black-box Adversarial Attacks on Face Recognitioncited by 173
17 more
  1. 2020Understanding and Mitigating the Tradeoff Between Robustness and Accuracycited by 148
  2. 2019Branch and Bound for Piecewise Linear Neural Network Verificationcited by 138
  3. 2018Are adversarial examples inevitable?cited by 113
  4. 2022Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Boundcited by 92
  5. 2016Measuring Neural Net Robustness with Constraintscited by 90
  6. 2020Deep Polynomial Neural Networkscited by 63
  7. 2021Improved Branch and Bound for Neural Network Verification via Lagrangian Decompositioncited by 44
  8. 2019Optimization and Abstraction: A Synergistic Approach for Analyzing Neural Network Robustnesscited by 40
  9. 2020Lagrangian Decomposition for Neural Network Verificationcited by 35
  10. 2020Practical No-box Adversarial Attacks against DNNscited by 32
  11. 2018Universal Approximation with Quadratic Deep Networkscited by 29
  12. 2019Adversarial Learning with Margin-based Triplet Embedding Regularizationcited by 29
  13. 2021Augmenting Deep Classifiers with Polynomial Neural Networkscited by 21
  14. 2022The Spectral Bias of Polynomial Neural Networkscited by 19
  15. 2019Fast Neural Network Verification via Shadow Pricescited by 17
  16. 2022Controlling the Complexity and Lipschitz Constant improves polynomial netscited by 5
  17. 2018Mathematical Analysis of Adversarial Attackscited by 3

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 0; 2025: 2.

4 papers.

  1. 2025Hadamard product in deep learning: Introduction, Advances and Challengescited by 9
  2. 2023One Neuron Saved Is One Neuron Earned: On Parametric Efficiency of Quadratic Networkscited by 6
  3. 2023DeepBern-Nets: Taming the Complexity of Certifying Neural Networks using Bernstein Polynomial Activations and Precise Bound Propagationcited by 5
  4. 2025Stochastic Sample Approximations of (Local) Moduli of Continuitycited by 1