论文标题
在分离数据上的对抗性鲁棒线性分类的样本复杂性
Sample Complexity of Adversarially Robust Linear Classification on Separated Data
论文作者
论文摘要
我们认为学习的样本复杂性具有对抗性的鲁棒性。此问题的大多数先前的理论结果都考虑了一个设置数据中不同类别的类别封闭或重叠的设置。相比之下，我们考虑到存在具有完美精确性和鲁棒性的分类器的良好情况，并表明样本复杂性叙述了一个完全不同的故事。具体而言，对于线性分类器，我们显示了一大批分离良好的分布，其中任何算法的可靠损失至少为$ω（\ frac {d} {n}）$，而最大利润率算法则预期了标准损失$ O（\ frac {1}} {n} {n} {n}）$。这显示了无法通过先前技术获得的标准和稳健损失的差距。此外，我们提出了一种算法，在一个实例的情况下，鲁棒性半径远小于类之间的差距，给出了一个带有预期稳健损失的解决方案为$ O（\ frac {1} {n}）$。这表明，对于非常分离的数据，可以实现$ o（\ frac {1} {n}）$的收敛速率，否则就不是这样。我们的结果适用于在任何$ \ ell_p $ norm中用$ p> 1 $（包括$ p = \ infty $）测量的鲁棒性。
We consider the sample complexity of learning with adversarial robustness. Most prior theoretical results for this problem have considered a setting where different classes in the data are close together or overlapping. Motivated by some real applications, we consider, in contrast, the well-separated case where there exists a classifier with perfect accuracy and robustness, and show that the sample complexity narrates an entirely different story. Specifically, for linear classifiers, we show a large class of well-separated distributions where the expected robust loss of any algorithm is at least $Ω(\frac{d}{n})$, whereas the max margin algorithm has expected standard loss $O(\frac{1}{n})$. This shows a gap in the standard and robust losses that cannot be obtained via prior techniques. Additionally, we present an algorithm that, given an instance where the robustness radius is much smaller than the gap between the classes, gives a solution with expected robust loss is $O(\frac{1}{n})$. This shows that for very well-separated data, convergence rates of $O(\frac{1}{n})$ are achievable, which is not the case otherwise. Our results apply to robustness measured in any $\ell_p$ norm with $p > 1$ (including $p = \infty$).
