OpenAI 연구: 강건한 분류에서의 계산적 한계

TL;DR

OpenAI는 강건한 분류기가 존재하지만 계산적으로 학습하는 것이 불가능한 분류 작업이 존재함을 입증했습니다. 이 발견은 강건한 분류의 난이도와 암호학적 프리미티브의 존재 사이의 연결 고리를 구축하여, 강건한 분류기를 학습할 수 있거나 새로운 암호학적 프리미티브를 구축할 수 있는 "win-win" 시나리오를 만듭니다.

강건한 분류에서의 계산적 난이도

강건한 분류는 입력에 대한 작은 섭동(perturbation)에도 정확도를 유지하는 분류기를 학습하는 것을 의미합니다. Bubeck, Lee, Price, 및 Razenshteyn의 이전 연구를 따라, OpenAI 연구원들은 통계적 및 계산적 트레이드오프 연구를 확장했습니다. 그들은 작은 섭동 영역(small-perturbation regime)에서 효율적인 강건한 분류기가 존재하고 비강건한 분류기는 효율적으로 학습될 수 있지만, 큰 수의 소인수분해의 난이도를 가정할 때 강건한 분류기를 학습하는 것은 계산적으로 어려운 특정 분류 작업을 식별했습니다.

평균 사례 난이도가 높은 함수를 통한 불가능한 강건한 분류

OpenAI는 계산적으로 무제한인 강건한 분류기가 존재하는 경우에도 계산적으로 효율적인 강건한 분류가 불가능한 분류 작업을 입증했습니다. 연구원들은 이러한 특정 작업에 대해 효율적인 알고리즘이 강건한 분류기를 학습할 수 없음을 증명하기 위해 평균 사례 난이도가 높은 함수(average-case hard functions)의 존재에 의존합니다.

큰 섭동 영역에서의 난이도

이 연구는 섭동이 클 때조차 강건하게 학습하기 어려운 작업들을 식별합니다. 이러한 시나리오에서는 큰 섭동에 강건한 효율적인 분류기가 존재하지만, 어떠한 비자명한(non-trivial) 강건한 분류기도 학습하기 어렵습니다.

OpenAI는 이 난이도를 증명하기 위해 두 가지 주요 구성을 사용합니다:

1. One-Way Functions: 첫 번째 구성은 일방향 함수의 존재에 의존합니다.
2. Learning Parity with Noise: 두 번째 구성은 "learning parity with noise" 문제의 난이도에 의존합니다. 이 특정 설정에서는 다항식 개수의 훈련 예제로부터 새로운 라벨링된 샘플을 생성할 수 있는 효율적인 알고리즘이 존재하지만, 강건한 분류기는 효율적으로 학습될 수 없습니다.

암호학을 위한 "Win-Win" 시나리오

이 연구는 효율적인 강건한 분류에 대한 어떠한 반례도 일방향 함수와 같은 암호학적 프리미티브의 존재를 시사함을 결론짓습니다. 이는 이론적인 "win-win" 시나리오를를 만듭니다: 연구원들이 그러한 모든 작업에 대해 효율적인 강건한 분류기를 학습할 수 있는 방법을 찾거나, 아니면 이러한 학습하기 어려운 작업들의 존재가 암호학적 프리미티브의 존재를 증명한다는 것입니다.