# Generalization Properties of Adversarial Training for ℓ0-Bounded Adversarial Attacks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 34 references that are in the map.
- First posted on arXiv 5 Feb 2024.

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

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Obfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples](https://mlsanity.com/paper/1802.00420/) (2018)
- [Is BERT Really Robust? A Strong Baseline for Natural Language Attack on Text Classification and Entailment](https://mlsanity.com/paper/1907.11932/) (2019)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Adversarially Robust Generalization Requires More Data](https://mlsanity.com/paper/1804.11285/) (2018)
- [Certified Defenses against Adversarial Examples](https://mlsanity.com/paper/1801.09344/) (2018)
- [Adversarial Training Can Hurt Generalization](https://mlsanity.com/paper/1906.06032/) (2019)
- [Towards the first adversarially robust neural network model on MNIST](https://mlsanity.com/paper/1805.09190/) (2018)
- [VC Classes are Adversarially Robustly Learnable, but Only Improperly](https://mlsanity.com/paper/1902.04217/) (2019)
- [Adversarial camera stickers: A physical camera-based attack on deep learning systems](https://mlsanity.com/paper/1904.00759/) (2019)
- [Sparse-RS: a versatile framework for query-efficient sparse black-box adversarial attacks](https://mlsanity.com/paper/2006.12834/) (2020)
- [Adversarial Perturbations Against Deep Neural Networks for Malware Classification](https://mlsanity.com/paper/1606.04435/) (2016)
- [A Simple Explanation for the Existence of Adversarial Examples with Small Hamming Distance](https://mlsanity.com/paper/1901.10861/) (2019)
- [On the Generalization Properties of Adversarial Training](https://mlsanity.com/paper/2008.06631/) (2020)
- [On the Rademacher Complexity of Linear Hypothesis Sets](https://mlsanity.com/paper/2007.11045/) (2020)
- [Adversarial Risk Bounds via Function Transformation](https://mlsanity.com/paper/1810.09519/) (2018)
- [Consistent Non-Parametric Methods for Maximizing Robustness](https://mlsanity.com/paper/2102.09086/) (2021)
- [Robust Classification Under ℓ0 Attack for the Gaussian Mixture Model](https://mlsanity.com/paper/2104.02189/) (2021)
- [Sample Complexity of Adversarially Robust Linear Classification on Separated Data](https://mlsanity.com/paper/2012.10794/) (2020)
- [Efficient and Robust Classification for Sparse Attacks](https://mlsanity.com/paper/2201.09369/) (2022)

## Abstract (arXiv)

We have widely observed that neural networks are vulnerable to small additive perturbations to the input causing misclassification. In this paper, we focus on the ℓ0-bounded adversarial attacks, and aim to theoretically characterize the performance of adversarial training for an important class of truncated classifiers. Such classifiers are shown to have strong performance empirically, as well as theoretically in the Gaussian mixture model, in the ℓ0-adversarial setting. The main contribution of this paper is to prove a novel generalization bound for the binary classification setting with ℓ0-bounded adversarial perturbation that is distribution-independent. Deriving a generalization bound in this setting has two main challenges: (i) the truncated inner product which is highly non-linear; and (ii) maximization over the ℓ0 ball due to adversarial training is non-convex and highly non-smooth. To tackle these challenges, we develop new coding techniques for bounding the combinatorial dimension of the truncated hypothesis class.