OpenAI 研究：強健分類中的計算限制

TL;DR

OpenAI 已證明，在某些分類任務中，雖然存在強健分類器，但在計算上卻無法學習。這項發現建立了強健分類的難度與密碼學原語（cryptographic primitives）存在之間的聯繫，創造了一個「雙贏」情境：要麼可以學習強健分類器，要麼可以構建新的密碼學原語。

強健分類中的計算難度

強健分類是指學習一個在輸入受到微小擾動時仍能保持準確的分類器。繼 Bubeck、Lee、Price 和 Razenshteyn 先前的研究之後，OpenAI 研究人員擴展了對統計與計算權衡的研究。他們發現了特定的分類任務，在微小擾動機制下存在高效的強健分類器，且可以高效地學習非強健分類器，但假設大數分解的難度成立，學習強健分類器在計算上仍然是困難的。

透過平均情況硬函數實現不可能的強健分類

OpenAI 已證明，在某些分類任務中，即使在存在計算無限制的強健分類器的情况下，進行計算高效的強健分類也是不可能的。研究人員依賴於平均情況硬函數（average-case hard functions）的存在，來證明對於這些特定任務，沒有任何高效算法可以學習強健分類器。

大擾動機制下的難度

研究指出，即使在擾動較大時，也存在難以進行強健學習的任務。在這些情境下，存在一個對大擾動具有強健性的高效分類器，但學習任何非平凡的強健分類器在計算上都是困難的。

OpenAI 利用兩種主要的構建方式來證明這種難度：

1. One-Way Functions: 第一種構建方式依賴於單向函數的存在。
2. Learning Parity with Noise: 第二種構建方式依賴於「帶噪聲學習奇偶性」（learning parity with noise）問題的難度。在這種特定設定下，存在一個高效算法可以從多項式數量的訓練樣本中生成全新的標記樣本，然而卻無法高效地學習強健分類器。

密碼學的「雙贏」情境

研究結論指出，任何高效強健分類的反例都意味著密碼學原語（如單向函數）的存在。這創造了一個理論上的「雙贏」情境：研究人員要麼可以找到一種方法來學習所有此類任務的高效強健分類器，要麼這些難以學習的任務的存在證明了密碼學原語的存在。