Generalization Properties of Adversarial Training for $\ell_0$-Bounded Adversarial Attacks
This work addresses the robustness of neural networks against sparse adversarial attacks, providing theoretical insights for researchers in adversarial machine learning, though it is incremental as it builds on existing empirical and theoretical results.
The paper tackles the problem of neural network vulnerability to ℓ₀-bounded adversarial attacks by theoretically characterizing adversarial training for truncated classifiers, proving a novel distribution-independent generalization bound for binary classification.
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 $\ell_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 $\ell_0$-adversarial setting. The main contribution of this paper is to prove a novel generalization bound for the binary classification setting with $\ell_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 $\ell_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.