The goal of this paper is to analyze an intriguing phenomenon recently
discovered in deep networks, namely their instability to adversarial
perturbations (Szegedy et. al., 2014). We provide a theoretical framework for
analyzing the robustness of classifiers to adversarial perturbations, and show
fundamental upper bounds on the robustness of classifiers. Specifically, we
establish a general upper bound on the robustness of classifiers to adversarial
perturbations, and then illustrate the obtained upper bound on the families of
linear and quadratic classifiers. In both cases, our upper bound depends on a
distinguishability measure that captures the notion of difficulty of the
classification task. Our results for both classes imply that in tasks involving
small distinguishability, no classifier in the considered set will be robust to
adversarial perturbations, even if a good accuracy is achieved. Our theoretical
framework moreover suggests that the phenomenon of adversarial instability is
due to the low flexibility of classifiers, compared to the difficulty of the
classification task (captured by the distinguishability). Moreover, we show the
existence of a clear distinction between the robustness of a classifier to
random noise and its robustness to adversarial perturbations. Specifically, the
former is shown to be larger than the latter by a factor that is proportional
to \sqrt{d} (with d being the signal dimension) for linear classifiers. This
result gives a theoretical explanation for the discrepancy between the two
robustness properties in high dimensional problems, which was empirically
observed in the context of neural networks. To the best of our knowledge, our
results provide the first theoretical work that addresses the phenomenon of
adversarial instability recently observed for deep networks. Our analysis is
complemented by experimental results on controlled and real-world data.

本论文分析了深层网络的一个有趣现象，即它们对于对抗性扰动的不稳定性，并提出了一个分析分类器鲁棒性的理论框架，并且为对抗性扰动的鲁棒性建立了一个上限。具体而言，我们建立了分类器对于对抗性扰动的鲁棒性的一个通用上限并用一些线性和二次分类器的例子说明了所获得的上限。我们的结果表明，在涉及小区分能力的任务中，所有选定的分类器将不会对于对抗性扰动产生鲁棒性，即使达到了较高的准确率。