가우시안 주변 분포 하에서의 다중 클래스 선형 분류를 위한 다항 시간 강건 학습

우리는 가우시안 분포 (Gaussian distribution) 하에서의 다중 클래스 선형 분류기 (multiclass linear classifiers)의 비가정적 학습 (agnostic learning) 과제를 연구합니다. 가우시안 $x$-주변 분포 (Gaussian $x$-marginal)를 갖는 $\mathbb{R}^d \times [k]$ 상의 분포로부터 레이블이 지정된 예시 $(x, y)$가 주어졌을 때, 목표는 최적의 $k$-클래스 선형 분류기의 오차와 유사한 오차를 갖는 가설을 출력하는 것입니다. 이진 분류 (binary case)인 $k=2$의 경우 잘 발달된 알고리즘 이론이 존재하지만, $k \ge 3$인 경우에는 알려진 바가 훨씬 적습니다. 심지어 $k=3$인 경우에도, 기존의 강건한 알고리즘 (robust algorithms)들은 복잡도와 표현 크기(representation size) 모두에서 원하는 정확도의 역수에 대해 지수적 의존성 (exponential dependence)을 가집니다. 본 연구에서 우리는 다중 클래스 선형 분류기를 위한 새로운 구조적 결과들을 개발하였으며, 이를 사용하여 차원에 독립적인 오차 보장 (dimension-independent error guarantees)을 갖는 완전 다항 시간 강건 학습기 (fully polynomial-time robust learners)를 설계합니다. 우리의 첫 번째 결과는 표준 다중 클래스 퍼셉트론 (multiclass perceptron) 알고리즘이 깨끗한 레이블 (clean labels)과 가우시안 주변 분포를 갖는 경우에도 초다항식(super-polynomially) 개수의 샘플과 업데이트를 필요로 함을 보여주며, 이는 이진 분류 사례에는 없는 기본적인 장애물 (obstruction)을 드러냅니다. 우리의 주요 긍정적 결과는 일반적인 $k$에 대해 $\widetilde O(k^{3/2}\sqrt{\mathrm{opt}})+\epsilon$의 오차를 갖는 효율적인 학습기를 산출하는 쌍별 부적절 학습 (pairwise improper-learning) 프레임워크입니다. 추가적으로, 우리는 $k=3$인 경우 $O(\mathrm{opt})+\epsilon$의 오차를, 기하학적으로 규칙적인 (geometrically regular) $k$-클래스 선형 분류기에 대해 $\mathrm{poly}(k)\mathrm{opt}+\epsilon$의 오차를 이끌어내는 더 정교한 국소화 기반 (localization-based) 프레임워크를 개발합니다.