Provably Adversarially Robust Nearest Prototype Classifiers
This work addresses the need for interpretable and provably robust classifiers in machine learning, offering incremental improvements in certification methods for adversarial threats.
The paper tackles the problem of certifying adversarial robustness for nearest prototype classifiers (NPCs) by providing exact computation algorithms for minimal adversarial perturbations under ℓ₂-distance and improved lower bounds for other ℓ_p/ℓ_q combinations, resulting in better ℓ₂-robustness guarantees on MNIST and higher certified robust accuracy on CIFAR10 compared to prior work.
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.