OpenAI研究 鲁棒分类和双赢结果的计算限制
在 Bubeck、Lee、Price 和 Razenshteyn 最近的工作之后，我们继续研究学习稳健分类器的统计/计算权衡，他们展示了分类任务的示例，其中 (a) 在小扰动状态下存在有效的稳健分类器；(b) 可以有效地学习非鲁棒分类器；但是 (c) 假设大数因式分解的难度，学习一个稳健的分类器在计算上是困难的。在大扰动范围内是否存在针对其任务的稳健分类器的问题似乎与计算数论中的重要开放问题有关。在这项工作中，我们将他们的工作扩展到三个方向。
首先，我们展示了分类任务，其中计算高效的鲁棒分类是不可能的，即使存在计算上无界的鲁棒分类器也是如此。为此，我们依赖于平均情况硬函数的存在。
其次，我们展示了在大扰动状态下难以鲁棒学习的分类任务。也就是说，我们表明即使存在对大扰动具有鲁棒性的有效分类器，但在计算上很难学习任何非平凡的鲁棒分类器。我们的第一个构造依赖于单向函数的存在，第二个构造依赖于学习奇偶性与噪声问题的难度。在后一种设置中，不仅存在非稳健的分类器，而且还存在一种有效的算法，该算法可以在访问多项式许多训练示例的情况下生成新的新标记样本（Kearns 等人 (1994) 称为生成）。
第三，我们表明任何这样的反例都意味着存在密码原语，例如单向函数。这将我们引向一个双赢的场景：要么我们可以学习一个有效的鲁棒分类器，要么我们可以构建新的密码原语实例。
相关文章
近期评论
-
来自： GPT-4V（ision）系统卡
-
来自： GPT-4V（ision）系统卡
-
来自： OpenAI研究 用对抗样本攻击机器学习