# Certified Robustness against Sparse Adversarial Perturbations via Data Localization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 22 references that are in the map.
- First posted on arXiv 23 May 2024.

## Builds on (most cited first, 15 of 15)

- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [One pixel attack for fooling deep neural networks](https://mlsanity.com/paper/1710.08864/) (2017)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Are adversarial examples inevitable?](https://mlsanity.com/paper/1809.02104/) (2018)
- [(De)Randomized Smoothing for Certifiable Defense against Patch Attacks](https://mlsanity.com/paper/2002.10733/) (2020)
- [Consistency Regularization for Certified Robustness of Smoothed Classifiers](https://mlsanity.com/paper/2006.04062/) (2020)
- [Robustness Certificates for Sparse Adversarial Attacks by Randomized Ablation](https://mlsanity.com/paper/1911.09272/) (2019)
- [Certified Defense to Image Transformations via Randomized Smoothing](https://mlsanity.com/paper/2002.12463/) (2020)
- [Certified Patch Robustness via Smoothed Vision Transformers](https://mlsanity.com/paper/2110.07719/) (2021)
- [ANCER: Anisotropic Certification via Sample-wise Volume Maximization](https://mlsanity.com/paper/2107.04570/) (2021)
- [A Game Theoretic Analysis of Additive Adversarial Attacks and Defenses](https://mlsanity.com/paper/2009.06530/) (2020)
- [Almost Tight L0-norm Certified Robustness of Top-k Predictions against Adversarial Perturbations](https://mlsanity.com/paper/2011.07633/) (2020)
- [Projected Randomized Smoothing for Certified Adversarial Robustness](https://mlsanity.com/paper/2309.13794/) (2023)
- [Adversarial Examples Might be Avoidable: The Role of Data Concentration in Adversarial Robustness](https://mlsanity.com/paper/2309.16096/) (2023)
- [Understanding Noise-Augmented Training for Randomized Smoothing](https://mlsanity.com/paper/2305.04746/) (2023)

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

- [Certified Robustness from Approximate Gaussian Mixture Structures in Pretrained Latent Spaces](https://mlsanity.com/paper/2605.25352/) (2026)

## Abstract (arXiv)

Recent work in adversarial robustness suggests that natural data distributions are localized, i.e., they place high probability in small volume regions of the input space, and that this property can be utilized for designing classifiers with improved robustness guarantees for ℓ2-bounded perturbations. Yet, it is still unclear if this observation holds true for more general metrics. In this work, we extend this theory to ℓ0-bounded adversarial perturbations, where the attacker can modify a few pixels of the image but is unrestricted in the magnitude of perturbation, and we show necessary and sufficient conditions for the existence of ℓ0-robust classifiers. Theoretical certification approaches in this regime essentially employ voting over a large ensemble of classifiers. Such procedures are combinatorial and expensive or require complicated certification techniques. In contrast, a simple classifier emerges from our theory, dubbed Box-NN, which naturally incorporates the geometry of the problem and improves upon the current state-of-the-art in certified robustness against sparse attacks for the MNIST and Fashion-MNIST datasets.