OpenAI 研究：鲁棒分类中的计算限制

TL;DR

OpenAI 已经证明，在某些分类任务中，虽然存在鲁棒分类器，但在计算上是无法学习的。这一发现建立了鲁棒分类的难度与密码学原语的存在之间的联系，创造了一个“双赢”局面：要么可以学习到鲁棒分类器，要么可以构建出新的密码学原语。

鲁棒分类中的计算难度

鲁棒分类是指学习一个在输入受到微小扰动时仍能保持准确性的分类器。继 Bubeck、Lee、Price 和 Razenshteyn 的先前工作之后，OpenAI 研究人员扩展了对统计和计算权衡的研究。他们确定了特定的分类任务，在这些任务中，小扰动机制下存在高效的鲁棒分类器，且可以高效地学习非鲁棒分类器，但假设大数分解的难度，学习鲁棒分类器在计算上仍然是困难的。

通过平均情况硬函数实现不可能的鲁棒分类

OpenAI 已经证明，在某些分类任务中，计算高效的鲁棒分类是不可能的，即使在存在计算无限制的鲁棒分类器的情况下也是如此。研究人员依靠平均情况硬函数（average-case hard functions）的存在来证明，对于这些特定的任务，没有任何高效算法可以学习到鲁棒分类器。

大扰动机制下的难度

研究确定了即使在扰动较大时也难以进行鲁棒学习的任务。在这些场景中，存在一个对大扰动具有鲁棒性的高效分类器，但学习任何非平凡的鲁棒分类器在计算上都是困难的。

OpenAI 利用两种主要的构建方式来证明这种难度：

1. One-Way Functions: 第一种构建方式依赖于单向函数的存在。
2. Learning Parity with Noise: 第二种构建方式依赖于“learning parity with noise”问题的难度。在这种特定设置下，存在一种高效算法可以从多项式数量的训练样本中生成全新的带标签样本，然而，却无法高效地学习到鲁棒分类器。

密码学“双赢”局面

研究结论指出，任何高效鲁棒分类的反例都意味着密码学原语（如 one-way functions）的存在。这创造了一个理论上的“双赢”局面：要么研究人员可以找到一种方法来学习所有此类任务的高效鲁棒分类器，要么这些难以学习的任务的存在证明了密码学原语的存在。