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 $\ell_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 $\ell_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 $\ell_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.

通过对局部化数据分布的理解，提出了一种基于几何形态的简单分类器 Box-NN，并在 MNIST 和 Fashion-MNIST 数据集上取得了对于稀疏攻击的认证稳健性方面的最新研究成果。