# Sparse Polynomial Optimisation for Neural Network Verification

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Feb 2022.

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

- [Novel Quadratic Constraints for Extending LipSDP beyond Slope-Restricted Activations](https://mlsanity.com/paper/2401.14033/) (2024)
- [Chordal Sparsity for SDP-based Neural Network Verification](https://mlsanity.com/paper/2206.03482/) (2022)
- [State space representations of the Roesser type for convolutional layers](https://mlsanity.com/paper/2403.11938/) (2024)
- [A Complete Set of Quadratic Constraints for Repeated ReLU and Generalizations](https://mlsanity.com/paper/2407.06888/) (2024)
- [Verifying Properties of Binary Neural Networks Using Sparse Polynomial Optimization](https://mlsanity.com/paper/2405.17049/) (2024)
- [Sparse Polynomial Optimization: Theory and Practice](https://mlsanity.com/paper/2208.11158/) (2022)
- [Convex neural network synthesis for robustness in the 1-norm](https://mlsanity.com/paper/2405.19029/) (2024)
- [Training Safe Neural Networks with Global SDP Bounds](https://mlsanity.com/paper/2409.09687/) (2024)

## Abstract (arXiv)

The prevalence of neural networks in society is expanding at an increasing rate. It is becoming clear that providing robust guarantees on systems that use neural networks is very important, especially in safety-critical applications. A trained neural network's sensitivity to adversarial attacks is one of its greatest shortcomings. To provide robust guarantees, one popular method that has seen success is to bound the activation functions using equality and inequality constraints. However, there are numerous ways to form these bounds, providing a trade-off between conservativeness and complexity. Depending on the complexity of these bounds, the computational time of the optimisation problem varies, with longer solve times often leading to tighter bounds. We approach the problem from a different perspective, using sparse polynomial optimisation theory and the Positivstellensatz, which derives from the field of real algebraic geometry. The former exploits the natural cascading structure of the neural network using ideas from chordal sparsity while the later asserts the emptiness of a semi-algebraic set with a nested family of tests of non-decreasing accuracy to provide tight bounds. We show that bounds can be tightened significantly, whilst the computational time remains reasonable. We compare the solve times of different solvers and show how the accuracy can be improved at the expense of increased computation time. We show that by using this sparse polynomial framework the solve time and accuracy can be improved over other methods for neural network verification with ReLU, sigmoid and tanh activation functions.