# Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablation

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

## Key facts

- Cited by 60 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Nov 2019.

## Built on by (most cited first, 30 of 60)

- [How Does Information Bottleneck Help Deep Learning?](https://mlsanity.com/paper/2305.18887/) (2023)
- [PatchCleanser: Certifiably Robust Defense against Adversarial Patches for Any Image Classifier](https://mlsanity.com/paper/2108.09135/) (2021)
- [Certified Robustness to Text Adversarial Attacks by Randomized [MASK]](https://mlsanity.com/paper/2105.03743/) (2021)
- [PointGuard: Provably Robust 3D Point Cloud Classification](https://mlsanity.com/paper/2103.03046/) (2021)
- [Boosting Randomized Smoothing with Variance Reduced Classifiers](https://mlsanity.com/paper/2106.06946/) (2021)
- [Certified Patch Robustness via Smoothed Vision Transformers](https://mlsanity.com/paper/2110.07719/) (2021)
- [Certified Neural Network Watermarks with Randomized Smoothing](https://mlsanity.com/paper/2207.07972/) (2022)
- [Improved, Deterministic Smoothing for L_1 Certified Robustness](https://mlsanity.com/paper/2103.10834/) (2021)
- [ANCER: Anisotropic Certification via Sample-wise Volume Maximization](https://mlsanity.com/paper/2107.04570/) (2021)
- [A Survey of Adversarial Defences and Robustness in NLP](https://mlsanity.com/paper/2203.06414/) (2022)
- [Certified Robustness for Large Language Models with Self-Denoising](https://mlsanity.com/paper/2307.07171/) (2023)
- [CC-Cert: A Probabilistic Approach to Certify General Robustness of Neural Networks](https://mlsanity.com/paper/2109.10696/) (2021)
- [Center Smoothing: Certified Robustness for Networks with Structured Outputs](https://mlsanity.com/paper/2102.09701/) (2021)
- [Adversarial Patch Attacks and Defences in Vision-Based Tasks: A Survey](https://mlsanity.com/paper/2206.08304/) (2022)
- [RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized Deletion](https://mlsanity.com/paper/2302.01757/) (2023)
- [From Robustness to Explainability and Back Again](https://mlsanity.com/paper/2306.03048/) (2023)
- [Input-Specific Robustness Certification for Randomized Smoothing](https://mlsanity.com/paper/2112.12084/) (2021)
- [Input-agnostic Certified Group Fairness via Gaussian Parameter Smoothing](https://mlsanity.com/paper/2206.11423/) (2022)
- [Interpolated Joint Space Adversarial Training for Robust and Generalizable Defenses](https://mlsanity.com/paper/2112.06323/) (2021)
- [UniCR: Universally Approximated Certified Robustness via Randomized Smoothing](https://mlsanity.com/paper/2207.02152/) (2022)
- [Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks](https://mlsanity.com/paper/2301.02039/) (2023)
- [Adversarially Robust Learning with Tolerance](https://mlsanity.com/paper/2203.00849/) (2022)
- [On the Role of Generalization in Transferability of Adversarial Examples](https://mlsanity.com/paper/2206.09238/) (2022)
- [Hierarchical Randomized Smoothing](https://mlsanity.com/paper/2310.16221/) (2023)
- [Node-aware Bi-smoothing: Certified Robustness against Graph Injection Attacks](https://mlsanity.com/paper/2312.03979/) (2023)
- [Certifiably Robust Policy Learning against Adversarial Communication in Multi-agent Systems](https://mlsanity.com/paper/2206.10158/) (2022)
- [Reducing Certified Regression to Certified Classification for General Poisoning Attacks](https://mlsanity.com/paper/2208.13904/) (2022)
- [Understanding Noise-Augmented Training for Randomized Smoothing](https://mlsanity.com/paper/2305.04746/) (2023)
- [Towards the Worst-case Robustness of Large Language Models](https://mlsanity.com/paper/2501.19040/) (2025)
- [Towards Adversarial Patch Analysis and Certified Defense against Crowd Counting](https://mlsanity.com/paper/2104.10868/) (2021)

## Abstract (arXiv)

Recently, techniques have been developed to provably guarantee the robustness of a classifier to adversarial perturbations of bounded L_1 and L_2 magnitudes by using randomized smoothing: the robust classification is a consensus of base classifications on randomly noised samples where the noise is additive. In this paper, we extend this technique to the L_0 threat model. We propose an efficient and certifiably robust defense against sparse adversarial attacks by randomly ablating input features, rather than using additive noise. Experimentally, on MNIST, we can certify the classifications of over 50% of images to be robust to any distortion of at most 8 pixels. This is comparable to the observed empirical robustness of unprotected classifiers on MNIST to modern L_0 attacks, demonstrating the tightness of the proposed robustness certificate. We also evaluate our certificate on ImageNet and CIFAR-10. Our certificates represent an improvement on those provided in a concurrent work (Lee et al. 2019) which uses random noise rather than ablation (median certificates of 8 pixels versus 4 pixels on MNIST; 16 pixels versus 1 pixel on ImageNet.) Additionally, we empirically demonstrate that our classifier is highly robust to modern sparse adversarial attacks on MNIST. Our classifications are robust, in median, to adversarial perturbations of up to 31 pixels, compared to 22 pixels reported as the state-of-the-art defense, at the cost of a slight decrease (around 2.3%) in the classification accuracy. Code is available at https://github.com/alevine0/randomizedAblation/.