# Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations Source: [Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations]() Collection index: [llms.txt]() Data updated: 2025-10-26T00:17:38.470Z Authors: Jinyuan Jia, Binghui Wang, Xiaoyu Cao, Hongbin Liu, Neil Zhenqiang Gong Published: 2020-11-15T21:34:44.000Z ## Abstract 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 $\\ell\_0$-norm robustness of top-$1$ predictions or $\\ell\_2$-norm robustness of top-$k$ 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 $\\ell\_0$-norm certified robustness guarantee for top-$k$ 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. ## 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]() [PDF]()