Why are classifiers in high dimension vulnerable to "adversarial" perturbations? We show that it is likely not due to information theoretic limitations, but rather it could be due to computational constraints. First we prove that, for a broad set of classification tasks, the mere existence of a robust classifier implies that it can be found by a possibly exponential-time algorithm with relatively few training examples. Then we give a particular classification task where learning a robust classifier is computationally intractable. More precisely we construct a binary classification task in high dimensional space which is (i) information theoretically easy to learn robustly for large perturbations, (ii) efficiently learnable (non-robustly) by a simple linear separator, (iii) yet is not efficiently robustly learnable, even for small perturbations, by any algorithm in the statistical query (SQ) model. This example gives an exponential separation between classical learning and robust learning in the statistical query model. It suggests that adversarial examples may be an unavoidable byproduct of computational limitations of learning algorithms.

高维度分类器为何易受到“对抗性”扰动？本文中将阐述这种现象可能不是由于信息论的限制，而是由于计算约束所引起的。同时探讨了分类任务的一种特殊情况，即在高维空间中对于对抗扰动较大的学习是容易的，但是具有计算难度的。这种例子带来了对于经典学习和鲁棒性学习之间的计算复杂度的差异的新见解，并建议这种现象可能是学习算法计算能力所限制的必然副产品。

来自计算限制的对抗性示例