우리는 가우시안 분포 (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) 프레임워크를 개발합니다.