Adversarial examples from computational constraints
Adversarial examples from computational constraints
复制标题
DOI：
--
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Sébastien Bubeck;Eric Price;Ilya P. Razenshteyn
中科院分区：
文献类型：
--
作者：
Sébastien Bubeck;Eric Price;Ilya P. Razenshteyn
为什么高维的分类器容易受到“对抗性”扰动的影响？我们表明，这可能不是由于信息理论的限制，而是由于计算的限制。首先，我们证明，对于一组广泛的分类任务，仅仅存在一个鲁棒分类器就意味着它可以通过一个可能的指数时间算法用相对较少的训练样本找到。然后我们给出了一个特定的分类任务，其中学习一个鲁棒分类器在计算上是难以处理的。更准确地说，我们在高维空间中构建了一个二元分类任务，该任务(i)理论上易于对大扰动进行鲁棒学习，（ii）通过简单的线性分隔符有效地（非鲁棒地）学习，（iii）即使对于小扰动，统计查询（SQ）模型中的任何算法也不能有效地鲁棒学习。这个例子给出了统计查询模型中经典学习和鲁棒学习之间的指数分离。这表明，对抗性示例可能是学习算法计算限制的不可避免的副产品。
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.