# Provably Adversarially Robust Nearest Prototype Classifiers

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 41 references that are in the map.
- First posted on arXiv 14 Jul 2022.

## Builds on (most cited first, 30 of 32)

- [The Unreasonable Effectiveness of Deep Features as a Perceptual Metric](https://mlsanity.com/paper/1801.03924/) (2018)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks](https://mlsanity.com/paper/2003.01690/) (2020)
- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Evasion Attacks against Machine Learning at Test Time](https://mlsanity.com/paper/1708.06131/) (2017)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [On Adaptive Attacks to Adversarial Example Defenses](https://mlsanity.com/paper/2002.08347/) (2020)
- [On Evaluating Adversarial Robustness](https://mlsanity.com/paper/1902.06705/) (2019)
- [Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples](https://mlsanity.com/paper/1605.07277/) (2016)
- [On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Models](https://mlsanity.com/paper/1810.12715/) (2018)
- [Towards Stable and Efficient Training of Verifiably Robust Neural Networks](https://mlsanity.com/paper/1906.06316/) (2019)
- [Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulation](https://mlsanity.com/paper/1705.08475/) (2017)
- [Scaling provable adversarial defenses](https://mlsanity.com/paper/1805.12514/) (2018)
- [Perceptual Adversarial Robustness: Defense Against Unseen Threat Models](https://mlsanity.com/paper/2006.12655/) (2020)
- [Globally-Robust Neural Networks](https://mlsanity.com/paper/2102.08452/) (2021)
- [Orthogonalizing Convolutional Layers with the Cayley Transform](https://mlsanity.com/paper/2104.07167/) (2021)
- [Preventing Gradient Attenuation in Lipschitz Constrained Convolutional Networks](https://mlsanity.com/paper/1911.00937/) (2019)
- [On the effectiveness of adversarial training against common corruptions](https://mlsanity.com/paper/2103.02325/) (2021)
- [Training for Faster Adversarial Robustness Verification via Inducing ReLU Stability](https://mlsanity.com/paper/1809.03008/) (2018)
- [Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Bounds](https://mlsanity.com/paper/2111.01395/) (2021)
- [SmoothMix: Training Confidence-calibrated Smoothed Classifiers for Certified Robustness](https://mlsanity.com/paper/2111.09277/) (2021)
- [Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100](https://mlsanity.com/paper/2108.04062/) (2021)
- [Evasion and Hardening of Tree Ensemble Classifiers](https://mlsanity.com/paper/1509.07892/) (2015)
- [Robust Decision Trees Against Adversarial Examples](https://mlsanity.com/paper/1902.10660/) (2019)
- [Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neurons](https://mlsanity.com/paper/2102.05363/) (2021)
- [Provable robustness against all adversarial lp-perturbations for p≥ 1](https://mlsanity.com/paper/1905.11213/) (2019)
- [Analyzing the Robustness of Nearest Neighbors to Adversarial Examples](https://mlsanity.com/paper/1706.03922/) (2017)
- [Provably Robust Boosted Decision Stumps and Trees against Adversarial Attacks](https://mlsanity.com/paper/1906.03526/) (2019)

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

- [Adversarial Examples Might be Avoidable: The Role of Data Concentration in Adversarial Robustness](https://mlsanity.com/paper/2309.16096/) (2023)
- [Robust Text Classification: Analyzing Prototype-Based Networks](https://mlsanity.com/paper/2311.06647/) (2023)

## Abstract (arXiv)

Nearest prototype classifiers (NPCs) assign to each input point the label of the nearest prototype with respect to a chosen distance metric. A direct advantage of NPCs is that the decisions are interpretable. Previous work could provide lower bounds on the minimal adversarial perturbation in the ℓp-threat model when using the same ℓp-distance for the NPCs. In this paper we provide a complete discussion on the complexity when using ℓp-distances for decision and ℓq-threat models for certification for p,q ∈ 1,2,∞. In particular we provide scalable algorithms for the exact computation of the minimal adversarial perturbation when using ℓ2-distance and improved lower bounds in other cases. Using efficient improved lower bounds we train our Provably adversarially robust NPC (PNPC), for MNIST which have better ℓ2-robustness guarantees than neural networks. Additionally, we show up to our knowledge the first certification results w.r.t. to the LPIPS perceptual metric which has been argued to be a more realistic threat model for image classification than ℓp-balls. Our PNPC has on CIFAR10 higher certified robust accuracy than the empirical robust accuracy reported in (Laidlaw et al., 2021). The code is available in our repository.