Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations

preprint2022arXivOpen access

Abstract

Top-k predictions are used in many real-world applications such as machine learning as a service, recommender systems, and web searches. ℓ0\ell_0-norm adversarial perturbation characterizes an attack that arbitrarily modifies some features of an input such that a classifier makes an incorrect prediction for the perturbed input. ℓ0\ell_0-norm adversarial perturbation is easy to interpret and can be implemented in the physical world. Therefore, certifying robustness of top-kk predictions against ℓ0\ell_0-norm adversarial perturbation is important. However, existing studies either focused on certifying ℓ0\ell_0-norm robustness of top-11 predictions or ℓ2\ell_2-norm robustness of top-kk predictions. In this work, we aim to bridge the gap. Our approach is based on randomized smoothing, which builds a provably robust classifier from an arbitrary classifier via randomizing an input. Our major theoretical contribution is an almost tight ℓ0\ell_0-norm certified robustness guarantee for top-kk predictions. We empirically evaluate our method on CIFAR10 and ImageNet. For instance, our method can build a classifier that achieves a certified top-3 accuracy of 69.2\% on ImageNet when an attacker can arbitrarily perturb 5 pixels of a testing image.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.