OpenAI 发布鲁棒分类计算极限与双赢结果研究

这篇 2019 年 2 月 4 日发布的论文沿着 Bubeck、Lee、Price 与 Razenshteyn 早期工作的思路，继续研究鲁棒分类中的统计与计算权衡。Bubeck 等人构造了一类任务：在小扰动范围内存在可以在多项式时间内学习的鲁棒分类器，但学习这一鲁棒分类器在计算上是困难的，前提是大整数分解的困难性。本文把这一图景沿着三个方向推进。

第一个结果给出在大扰动范围下多项式时间内的鲁棒分类不可能的任务，依赖的是平均情形难解函数的存在性；第二个结果展示了即便存在能够抵御大扰动的多项式时间分类器，学习任何非平凡的鲁棒分类器也是计算困难的，所用密码学假设分别是单向函数与含噪奇偶学习问题的难解性，并且在后者的设定下，不仅非鲁棒分类器存在，连给定多项式数量训练样本后生成新标注样本的多项式时间算法也成立，对应 Kearns 等人 1994 年提出的 generation 概念。

第三个结果是论文的核心命题，也是题目里 win-win 一词的来源。任何这样的反例都蕴含某种密码学原语的存在，因此研究者面对的是一个双赢局面：要么能够构造多项式时间的鲁棒分类器，要么能够基于反例构造出新的密码学原语实例。两个方向都对理论计算机科学具有价值，前者直接提升机器学习的对抗鲁棒性，后者拓展密码协议的设计空间。这种把对抗机器学习与密码学难题之间的张力转化为研究资源的视角，为后续鲁棒学习的复杂度理论提供了一个分析框架。