# PROVEN: Certifying Robustness of Neural Networks with a Probabilistic Approach

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Dec 2018.

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

- [Achieving Efficiency in Black Box Simulation of Distribution Tails with Self-structuring Importance Samplers](https://mlsanity.com/paper/2102.07060/) (2021)
- [Probabilistic Verification of ReLU Neural Networks via Characteristic Functions](https://mlsanity.com/paper/2212.01544/) (2022)
- [Towards Optimal Branching of Linear and Semidefinite Relaxations for Neural Network Robustness Certification](https://mlsanity.com/paper/2101.09306/) (2021)
- [Certifying Ensembles: A General Certification Theory with S-Lipschitzness](https://mlsanity.com/paper/2304.13019/) (2023)
- [SimCert: Probabilistic Certification for Behavioral Similarity in Deep Neural Network Compression](https://mlsanity.com/paper/2603.14818/) (2026)
- [Propagation of~Interval Belief Structures and~Imprecise Copulas for~Neural Network Verification](https://mlsanity.com/paper/2606.30105/) (2026)
- [Quantifying probabilistic robustness of tree-based classifiers against natural distortions](https://mlsanity.com/paper/2208.10354/) (2022)
- [Threats, Vulnerabilities, and Controls of Machine Learning Based Systems: A Survey and Taxonomy](https://mlsanity.com/paper/2301.07474/) (2023)
- [Tightening the Evaluation of PAC Bounds Using Formal Verification Results](https://mlsanity.com/paper/2407.20122/) (2024)
- [Probabilistic Verification of Neural Networks via Efficient Probabilistic Hull Generation](https://mlsanity.com/paper/2604.21556/) (2026)

## Abstract (arXiv)

With deep neural networks providing state-of-the-art machine learning models for numerous machine learning tasks, quantifying the robustness of these models has become an important area of research. However, most of the research literature merely focuses on the textitworst-case setting where the input of the neural network is perturbed with noises that are constrained within an ℓp ball; and several algorithms have been proposed to compute certified lower bounds of minimum adversarial distortion based on such worst-case analysis. In this paper, we address these limitations and extend the approach to a textitprobabilistic setting where the additive noises can follow a given distributional characterization. We propose a novel probabilistic framework PROVEN to PRObabilistically VErify Neural networks with statistical guarantees -- i.e., PROVEN certifies the probability that the classifier's top-1 prediction cannot be altered under any constrained ℓp norm perturbation to a given input. Importantly, we show that it is possible to derive closed-form probabilistic certificates based on current state-of-the-art neural network robustness verification frameworks. Hence, the probabilistic certificates provided by PROVEN come naturally and with almost no overhead when obtaining the worst-case certified lower bounds from existing methods such as Fast-Lin, CROWN and CNN-Cert. Experiments on small and large MNIST and CIFAR neural network models demonstrate our probabilistic approach can achieve up to around 75% improvement in the robustness certification with at least a 99.99% confidence compared with the worst-case robustness certificate delivered by CROWN.