Provably Adversarially Robust Nearest Prototype Classifiers
Not on the map. Why?
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 32 of its 41 references that are in the map. First posted on arXiv 14 Jul 2022.
Builds on
32 of 41 references.
References · 32
- 2018The Unreasonable Effectiveness of Deep Features as a Perceptual Metriccited by 11,029
- 2014Explaining and Harnessing Adversarial Examplescited by 7,287
- 2013Intriguing properties of neural networkscited by 5,114
- 2020Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attackscited by 1,442
- 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
- 2018Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examplescited by 1,259
- 2017Evasion Attacks against Machine Learning at Test Timecited by 686
- 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
- 2020On Adaptive Attacks to Adversarial Example Defensescited by 547
- 2019On Evaluating Adversarial Robustnesscited by 442
- 2016Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samplescited by 439
- 2018On the Effectiveness of Interval Bound Propagation for Training Verifiably Robust Modelscited by 322
20 more
- 2019Towards Stable and Efficient Training of Verifiably Robust Neural Networkscited by 204
- 2017Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulationcited by 182
- 2018Scaling provable adversarial defensescited by 141
- 2020Perceptual Adversarial Robustness: Defense Against Unseen Threat Modelscited by 137
- 2021Globally-Robust Neural Networkscited by 106
- 2021Orthogonalizing Convolutional Layers with the Cayley Transformcited by 105
- 2019Preventing Gradient Attenuation in Lipschitz Constrained Convolutional Networkscited by 86
- 2021On the effectiveness of adversarial training against common corruptionscited by 71
- 2018Training for Faster Adversarial Robustness Verification via Inducing ReLU Stabilitycited by 67
- 2021Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Boundscited by 64
- 2021SmoothMix: Training Confidence-calibrated Smoothed Classifiers for Certified Robustnesscited by 49
- 2021Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100cited by 47
- 2015Evasion and Hardening of Tree Ensemble Classifierscited by 44
- 2019Robust Decision Trees Against Adversarial Examplescited by 40
- 2021Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neuronscited by 40
- 2019Provable robustness against all adversarial lp-perturbations for p≥ 1cited by 39
- 2017Analyzing the Robustness of Nearest Neighbors to Adversarial Examplescited by 36
- 2019Provably Robust Boosted Decision Stumps and Trees against Adversarial Attackscited by 26
- 2017Evaluating Robustness of Neural Networks with Mixed Integer Programmingcited by 14
- 2019Evaluating the Robustness of Nearest Neighbor Classifiers: A Primal-Dual Perspectivecited by 1
Built on by
Citing papers per year: 2023: 2.
2 papers.