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

arXiv: https://arxiv.org/abs/2011.07633 · HTML: https://mlsanity.com/paper/2011.07633/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Nov 2020.

## Built on by (most cited first, 16 of 16)

- [PatchCleanser: Certifiably Robust Defense against Adversarial Patches for Any Image Classifier](https://mlsanity.com/paper/2108.09135/) (2021)
- [RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized Deletion](https://mlsanity.com/paper/2302.01757/) (2023)
- [UniCR: Universally Approximated Certified Robustness via Randomized Smoothing](https://mlsanity.com/paper/2207.02152/) (2022)
- [MultiGuard: Provably Robust Multi-label Classification against Adversarial Examples](https://mlsanity.com/paper/2210.01111/) (2022)
- [Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2312.03979/) (2023)
- [Reducing Certified Regression to Certified Classification for General Poisoning Attacks](https://mlsanity.com/paper/2208.13904/) (2022)
- [Multi-SpacePhish: Extending the Evasion-space of Adversarial Attacks against Phishing Website Detectors using Machine Learning](https://mlsanity.com/paper/2210.13660/) (2022)
- [10 Security and Privacy Problems in Large Foundation Models](https://mlsanity.com/paper/2110.15444/) (2021)
- [PointCert: Point Cloud Classification with Deterministic Certified Robustness Guarantees](https://mlsanity.com/paper/2303.01959/) (2023)
- [CluCERT: Certifying LLM Robustness via Clustering-Guided Denoising Smoothing](https://mlsanity.com/paper/2512.08967/) (2025)
- [A Certified Radius-Guided Attack Framework to Image Segmentation Models](https://mlsanity.com/paper/2304.02693/) (2023)
- [MMCert: Provable Defense against Adversarial Attacks to Multi-modal Models](https://mlsanity.com/paper/2403.19080/) (2024)
- [Collective Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2403.01423/) (2024)
- [Magmaw: Modality-Agnostic Adversarial Attacks on Machine Learning-Based Wireless Communication Systems](https://mlsanity.com/paper/2311.00207/) (2023)
- [Certified Robustness against Sparse Adversarial Perturbations via Data Localization](https://mlsanity.com/paper/2405.14176/) (2024)
- [Scalable and Precise Patch Robustness Certification for Deep Learning Models with Top-k Predictions](https://mlsanity.com/paper/2507.23335/) (2025)

## Abstract (arXiv)

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