# Provable Certificates for Adversarial Examples: Fitting a Ball in the Union of Polytopes

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Mar 2019.

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

- [Globally-Robust Neural Networks](https://mlsanity.com/paper/2102.08452/) (2021)
- [A Survey of Robust Adversarial Training in Pattern Recognition: Fundamental, Theory, and Methodologies](https://mlsanity.com/paper/2203.14046/) (2022)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Consistent Counterfactuals for Deep Models](https://mlsanity.com/paper/2110.03109/) (2021)
- [SplineCam: Exact Visualization and Characterization of Deep Network Geometry and Decision Boundaries](https://mlsanity.com/paper/2302.12828/) (2023)
- [Robust Models Are More Interpretable Because Attributions Look Normal](https://mlsanity.com/paper/2103.11257/) (2021)
- [NLP Verification: Towards a General Methodology for Certifying Robustness](https://mlsanity.com/paper/2403.10144/) (2024)
- [Polyhedral Complex Extraction from ReLU Networks using Edge Subdivision](https://mlsanity.com/paper/2306.07212/) (2023)
- [Unlocking Deterministic Robustness Certification on ImageNet](https://mlsanity.com/paper/2301.12549/) (2023)
- [FairProof : Confidential and Certifiable Fairness for Neural Networks](https://mlsanity.com/paper/2402.12572/) (2024)
- [Provable Lipschitz Certification for Generative Models](https://mlsanity.com/paper/2107.02732/) (2021)
- [Relaxing Local Robustness](https://mlsanity.com/paper/2106.06624/) (2021)
- [A Novel Data Augmentation Technique for Out-of-Distribution Sample Detection using Compounded Corruptions](https://mlsanity.com/paper/2207.13916/) (2022)
- [Zonotope Domains for Lagrangian Neural Network Verification](https://mlsanity.com/paper/2210.08069/) (2022)
- [Adversarial Attacks and Defenses in Machine Learning-Powered Networks: A Contemporary Survey](https://mlsanity.com/paper/2303.06302/) (2023)
- [Limitations of Piecewise Linearity for Efficient Robustness Certification](https://mlsanity.com/paper/2301.08842/) (2023)
- [Precise and Generalized Robustness Certification for Neural Networks](https://mlsanity.com/paper/2306.06747/) (2023)
- [Faithful Explanations for Deep Graph Models](https://mlsanity.com/paper/2205.11850/) (2022)
- [ExpProof : Operationalizing Explanations for Confidential Models with ZKPs](https://mlsanity.com/paper/2502.03773/) (2025)
- [On the Perils of Cascading Robust Classifiers](https://mlsanity.com/paper/2206.00278/) (2022)
- [Verifying Attention Robustness of Deep Neural Networks against Semantic Perturbations](https://mlsanity.com/paper/2207.05902/) (2022)
- [Master's Thesis: Out-of-distribution Detection with Energy-based Models](https://mlsanity.com/paper/2302.12002/) (2023)
- [Adversarial Examples in Environment Perception for Automated Driving (Review)](https://mlsanity.com/paper/2504.08414/) (2025)
- [Combinatorial Regularity for Relatively Perfect Discrete Morse Gradient Vector Fields of ReLU Neural Networks](https://mlsanity.com/paper/2412.18005/) (2024)
- [Certification of Machine Learning Models via Directional Sharpness](https://mlsanity.com/paper/2606.25004/) (2026)

## Abstract (arXiv)

We propose a novel method for computing exact pointwise robustness of deep neural networks for all convex ℓp norms. Our algorithm, GeoCert, finds the largest ℓp ball centered at an input point x0, within which the output class of a given neural network with ReLU nonlinearities remains unchanged. We relate the problem of computing pointwise robustness of these networks to that of computing the maximum norm ball with a fixed center that can be contained in a non-convex polytope. This is a challenging problem in general, however we show that there exists an efficient algorithm to compute this for polyhedral complices. Further we show that piecewise linear neural networks partition the input space into a polyhedral complex. Our algorithm has the ability to almost immediately output a nontrivial lower bound to the pointwise robustness which is iteratively improved until it ultimately becomes tight. We empirically show that our approach generates distance lower bounds that are tighter compared to prior work, under moderate time constraints.