A Rate Separation for Agnostic Direct Sums

기술 요약: 에그노스틱 직접 합(Direct Sum)에 대한 비율 분리

문제 정의
본 논문은 에그노스틱 PAC 학습에서 개념 클래스의 직접 합(direct sum)의 거동에 관한 근본적인 질문을 다룹니다. 구체적으로, $r$-중복 직접 합 $C^r$의 에그노스틱 학습 곡선이 단일 인스턴스 학습 곡선 $\varepsilon_{\text{agn}}(n \mid C)$와 인자(factor)의 수 $r$에 의해서만 결정되는지 여부를 조사합니다. 이 질문은 Hanneke, Moran, 그리고 Waknine [HMW24]에 의해 제기되었습니다. 핵심적인 탐구 대상은 제한이 없는 분포 불변(distribution-free) 설정에서, 단일 인스턴스의 학습률 차수와 복사본의 수가 결합되었을 때 제품 클래스의 학습률을 예측하기에 충분한가 하는 점입니다.

방법론 및 설정
저자들은 최적의 개념 클래스 $C$의 멤버에 대한 초과 위험(excess risk)을 최소화하는 것을 목표로 하는 표준적인 에그노스틱 PAC 학습 프레임워크를 활용합니다.

• 직접 합의 정의: 클래스 $C_1 \subseteq Y^{X_1}$와 $C_2 \subseteq Y^{X_2}$에 대하여, 직접 합 $C_1 \otimes C_2$는 함수 $(c_1 \otimes c_2)(x_1, x_2) = (c_1(x_1), c_2(x_2))$를 포함하는 집합입니다. $r$-중복 직접 합은 $C^r = \bigotimes_{i=1}^r C$입니다.
• 손실 함수: 손실은 좌표별 해밍 손실(coordinate-wise Hamming loss)이 아닌, 전체 출력 벡터에 대한 0-1 손실로 정의됩니다.
• 학습 곡선: 에그노스틱 학습 곡선은 $\varepsilon_{\text{agn}}(n \mid C) = \inf_A \sup_D (L_{D,n}(A) - L_D(C))$로 정의됩니다. 여기서 하한(infimum)은 모든 학습 규칙 $A$에 대해, 상한(supremum)은 모든 분포 $D$에 대해 취해집니다.

이 문제를 해결하기 위해 저자들은 도메인과 레이블 공간 $X = Y = \{0, 1\}$에 대한 두 가지 특정 개념 클래스 $F$와 $G$를 구성합니다:

1. 클래스 $F$: 두 개의 상수 이진 함수($f_0(x)=0, f_1(x)=1$)를 포함합니다.
2. 클래스 $G$: 영 함수(zero function)와 항등 함수(identity function)($g_0(x)=0, g_1(x)=x$)를 포함합니다.

저자들은 두 클래스가 동일한 단일 인스턴스 학습률을 보임에도 불구하고, 이들의 $r$-중복 직접 합은 근본적으로 다른 학습률을 나타낸다는 것을 증명합니다.

주요 기여 및 결과

1. 단일 인스턴스 동등성:
   본 논문은 $F$와 $G$가 모두 $n^{-1/2}$의 에그노스틱 학습 곡선을 가짐을 확립합니다.

• $F$의 경우, 상수 함수들과 경험적 위험 최소화(empirical risk minimization)에 대한 표준 분석을 통해 결과가 도출됩니다.
• $G$의 경우, 메인 정리(Theorem 1)에서 $r=1$을 대입함으로써 결과가 유도되며, 이는 $\varepsilon_{\text{agn}}(n \mid G) \asymp n^{-1/2}$임을 보여줍니다.

2. 직접 합에서의 비율 분리 (메인 정리):
   중심적인 기여는 $F^r$과 $G^r$ 사이의 "비율 분리(rate separation)"를 보여주는 Theorem 1입니다.

• $F^r$ (상수 클래스)의 경우: $r$에 관계없이 학습률은 $\Theta(n^{-1/2})$로 유지됩니다. 증명에 따르면 초과 위험은 가장 확률이 높은 상수 벡터의 추정 오차에 의해 지배되며, 이는 $1/\sqrt{n}$의 척도로 스케일링됩니다.
• $G^r$ (영/항등 클래스)의 경우: 학습률은 $\Theta(\min\{1, \sqrt{r/n}\})$로 스케일링됩니다.
  • $r \le n$일 때, 비율은 $\Theta(\sqrt{r/n})$입니다.
  • $r > n$일 때, 미니맥스 초과 위험은 양의 상수(positive constant)로 하한이 씌워집니다 (즉, 극한에서 학습이 불가능합니다).

결과적으로, $\varepsilon_{\text{agn}}(n \mid F) \asymp \varepsilon_{\text{agn}}(n \mid G)$임에도 불구하고, $r$이 커짐에 따라 $\varepsilon_{\text{agn}}(n \mid F^r)$과 $\varepsilon_{\text{agn}}(n \mid G^r)$의 점근적 차수는 서로 달라집니다.

3. 증명 기법:

• 상한 (Upper Bounds): 유한 클래스에 대한 표준적인 경험적 위험 최소화 경계(bounds)를 사용하여 유도되었습니다. $G^r$의 경우, $|G^r| = 2^r$이라는 사실을 이용하여 $\sqrt{\frac{r \log 2}{n}}$에 비례하는 항을 도출합니다.
• 하한 (Lower Bounds): 정보 이론적 도구들을 사용하여 확립되었습니다.
  • $F^r$의 경우, 두 개의 지배적인 상수 레이블을 구별하는 것의 어려움을 보여주기 위해 2-포인트 르 캉(Le Cam) 방법이 사용됩니다.
  • $G^r$의 경우, 저자들은 **아수아드 보조정리(Assouad's Lemma)**와 **핀스커 부등식(Pinsker's inequality)**을 결합하여 사용합니다. 저자들은 $\theta \in \{-1, +1\}^r$에 의해 매개변수화된 분포 패밀리를 구성합니다. 이 구성에서 입력 좌표 $J$는 $\{1, \dots, r\}$에서 균등하게 선택되며, $J=j$가 주어졌을 때 레이블 $Y$는 확률 $1/2 + \theta_j \alpha$로 $e_j$가 되고, 확률 $1/2 - \theta_j \alpha$로 $0^r$이 됩니다. 증명은 $\theta$를 추정하는 해밍 거리와 초과 위험 사이의 관계를 규명하며, $r$ 차원의 매개변수 벡터를 추정하는 데 샘플 크기가 $r$에 비례하는 $r$이 필요함을 보여줍니다.

의의 및 주장
본 논문은 [HMW24]에서 제기된 질문에 대해 부정적인 답변을 제공합니다. 저자들은 단일 인스턴스 학습률과 인자의 수 $r$만으로는 직접 합 $C^r$의 점근적 차수를 결정하기에 불충분하다고 주장합니다.

저자들은 다른 복잡도 프레임워크나 구조적 분포 가정을 적용하여 직접 합을 연구한 후속 연구들(예: [Sur24], [HMS26])이나 멀티클래스 학습에 관한 최근 연구들이 조합론적 경계를 제공하고 있음에도 불구하고, 이러한 결과 중 어느 것도 제한이 없는 분포 불연 변 설정에서 단일 인스턴스 곡선만을 함수로 하여 직접 합 곡선을 표현하지 못한다는 점을 언급합니다. 본 논문은 구조적 특성(상수 vs 항등)이 제품 공간에서 어떻게 발산하는 행동을 이끌어내는지 반례를 제시함으로써 그 간극을 명시적으로 해결합니다.

결론적으로, 임의의 개념 클래스에 대해 $\varepsilon_{\text{agn}}(n \mid C)$와 $r$을 아는 것만으로는 $\varepsilon_{\text{agn}}(n \mid C^r)$의 점근적 차수를 예측할 수 없습니다. 특히 $G^r$의 경우 $r \ge n$일 때 위험이 0에서 멀리 떨어져 있을 수 있는 반면, $F^r$의 경우 위험은 계속해서 $n^{-1/2}$으로 감소합니다.