# Provably Adversarially Robust Nearest Prototype Classifiers

Source: [Provably Adversarially Robust Nearest Prototype Classifiers](<https://www.sota2.com/research/paper/68fa6d041e209131cea375ef>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-26T00:24:36.116Z

Authors: V\\'aclav Vor\\'a\\v{c}ek, Matthias Hein

Published: 2022-07-14T21:22:30.000Z

## Abstract

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 $\\ell\_p$-threat model when using the same $\\ell\_p$-distance for the NPCs. In this paper we provide a complete discussion on the complexity when using $\\ell\_p$-distances for decision and $\\ell\_q$-threat models for certification for $p,q \\in \\{1,2,\\infty\\}$. In particular we provide scalable algorithms for the \\emph{exact} computation of the minimal adversarial perturbation when using $\\ell\_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 $\\ell\_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 $\\ell\_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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2207.07208>)

[PDF](<https://arxiv.org/pdf/2207.07208.pdf>)
