# Provable Robustness Against a Union of ℓ0 Adversarial Attacks

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2023.

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

- [How Deep Learning Sees the World: A Survey on Adversarial Attacks & Defenses](https://mlsanity.com/paper/2305.10862/) (2023)
- [Privacy-preserving Universal Adversarial Defense for Black-box Models](https://mlsanity.com/paper/2408.10647/) (2024)
- [RDI: An adversarial robustness evaluation metric for deep neural networks based on model statistical features](https://mlsanity.com/paper/2504.18556/) (2025)
- [Your Classifier Can Do More: Towards Balancing the Gaps in Classification, Robustness, and Generation](https://mlsanity.com/paper/2505.19459/) (2025)
- [Provable Robustness against Backdoor Attacks via the Primal-Dual Perspective on Differential Privacy](https://mlsanity.com/paper/2605.21780/) (2026)

## Abstract (arXiv)

Sparse or ℓ0 adversarial attacks arbitrarily perturb an unknown subset of the features. ℓ0 robustness analysis is particularly well-suited for heterogeneous (tabular) data where features have different types or scales. State-of-the-art ℓ0 certified defenses are based on randomized smoothing and apply to evasion attacks only. This paper proposes feature partition aggregation (FPA) -- a certified defense against the union of ℓ0 evasion, backdoor, and poisoning attacks. FPA generates its stronger robustness guarantees via an ensemble whose submodels are trained on disjoint feature sets. Compared to state-of-the-art ℓ0 defenses, FPA is up to 3,000× faster and provides larger median robustness guarantees (e.g., median certificates of 13 pixels over 10 for CIFAR10, 12 pixels over 10 for MNIST, 4 features over 1 for Weather, and 3 features over 1 for Ames), meaning FPA provides the additional dimensions of robustness essentially for free.