鲁棒分类中的计算限制与双赢结果

# 鲁棒分类的计算限制与双赢结果 来源：https://openai.com/index/computational-limitations-in-robust-classification-and-win-win-results/ ## 摘要 我们继续研究鲁棒分类器学习中的统计/计算权衡问题，基于 Bubeck、Lee、Price 和 Razenshteyn 的最近工作。他们展示了分类任务的例子，其中 (a) 在小扰动范围内存在高效的鲁棒分类器；(b) 可以高效学习非鲁棒分类器；但 (c) 在分解大数困难的假设下，学习鲁棒分类器在计算上是困难的。在大扰动范围内该任务的鲁棒分类器是否存在的问题似乎与计算数论中的重要开放问题相关。在本工作中，我们从三个方向扩展了他们的工作。 首先，我们证明了存在分类任务，其中即使计算无界的鲁棒分类器存在，计算高效的鲁棒分类也是不可能的。为此，我们依赖平均情况困难函数的存在性。 其次，我们展示了在大扰动范围内难以鲁棒学习的分类任务。即，我们证明了虽然存在对大扰动鲁棒的高效分类器，但学习任何非平凡的鲁棒分类器在计算上都是困难的。我们的第一个构造依赖于单向函数的存在性，第二个依赖于带噪声学习奇偶性问题的困难性。在后一种情况下，不仅存在非鲁棒分类器，而且存在高效算法可以在给定多项式个训练样本的情况下生成新的标记样本（由 Kearns 等人（1994）称为生成）。 第三，我们证明了任何这样的反例都意味着密码学原语（如单向函数）的存在性。这引导我们进入一个双赢场景：要么我们可以学习一个高效的鲁棒分类器，要么我们可以构造密码学原语的新实例。