좋은 보간기(Interpolators)는 얼마나 풍부한가?

Let $S$를 사전에 고정된 음수일 수 있는 마진(margin) $\kappa$에 대해, 레이블이 지정된 데이터셋 $(X_i,y_i)_{i=1}^n$, $X_i \in \mathbb{R}^d$, $y_i \in {-1,+1}$의 모든 점을 올바르게 분류하는 단위 노름(unit norm) 선형 분류기 $\theta \in \mathbb{R}^d$의 집합이라고 합시다. $(X,y)$ 쌍의 두 가지 자연스러운 데이터 생성 분포인 가우시안 혼합 모델(Gaussian mixture model)과 가우시안 특징(Gaussian features)을 가진 로지스틱 모델(logistic model) 하에서, 그리고 충분히 작은 $\alpha$를 갖는 비례 체제(proportional regime) $n/d \to \alpha$에서, 우리는 데이터 선택에 대해 높은 확률로 $S$에서 무작위로 선택된 점 $\theta$가 주어진 일반화 오차(generalization error)를 달성하는 사건에 대한 대편차 원리(large deviation principle)를 확립합니다. 관련된 대편차율 함수(large deviation rate function)는 결정론적이며, 주어진 원하는 성능을 갖는 보간 분류기(interpolating classifiers)의 비율을 $d$의 지수 스케일에서 설명합니다. 그 결과로, 우리는 다음과 같은 집중 현상(concentration phenomenon)을 확립합니다: 지수적으로 작은 비율을 제외한 모든 보간 분류기는 이 율 함수의 유일한 극대화값(maximizer)에 의해 주어지는 거의 동일한 일반화 성능을 가집니다. 우리는 이 극대화값을 경사 하강법(gradient descent)에 의한 경험적 위험 최소화(empirical risk minimization)의 성능 및 $S$ 내의 한 점을 찾는 자연스러운 선형 계획법(linear program)의 성능과 수치적으로 비교하였으며, 작은 $\alpha$의 과매개변수화(overparametrized) 체제에서 이러한 효율적인 절차들이 대다수의 보간기보다 뛰어난 성능을 보임을 도출하였고, 이는 이 설정에서 이들의 비자명한 양성 과적합(benign overfitting)을 시사합니다.