Motivated by safety-critical applications, test-time attacks on classifiers
via adversarial examples has recently received a great deal of attention.
However, there is a general lack of understanding on why adversarial examples
arise; whether they originate due to inherent properties of data or due to lack
of training samples remains ill-understood. In this work, we introduce a
theoretical framework analogous to bias-variance theory for understanding these
effects.
We use our framework to analyze the robustness of a canonical non-parametric
classifier - the k-nearest neighbors. Our analysis shows that its robustness
properties depend critically on the value of k - the classifier may be
inherently non-robust for small k, but its robustness approaches that of the
Bayes Optimal classifier for fast-growing k. We propose a novel modified
1-nearest neighbor classifier, and guarantee its robustness in the large sample
limit. Our experiments suggest that this classifier may have good robustness
properties even for reasonable data set sizes.

本文针对分类器的测试攻击问题，引入了一种理论框架，类似于偏差 - 方差理论，并使用该框架对一种典型的非参数分类器 - k 最近邻分类器的鲁棒性进行了分析，并提出了一种新的修改的 1 最近邻分类器，其在大样本极限下具有良好的鲁棒性。