Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations. (arXiv:2011.07633v2 [cs.CR] UPDATED)

Top-k predictions are used in many real-world applications such as machine
learning as a service, recommender systems, and web searches. $\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. $\ell_0$-norm adversarial perturbation is easy to
interpret and can be implemented in the physical world. Therefore, certifying
robustness of top-$k$ predictions against $\ell_0$-norm adversarial
perturbation is important. However, existing studies either focused on
certifying …

adversarial certified predictions