Majority-of-Three is Optimal

기술 요약: 3인 다수결(Majority-of-Three)의 최적성

문제 정의
본 논문은 실현 가능한(realizable) 설정에서 PAC 학습의 최적 샘플 복잡도를 결정하는 핵심 문제를 다룬다. Hanneke [Han16](Simon [Sim15]의 연구를 계승)에 의해 최적 학습자의 존재가 확립되었으나, 그 결과로 도출된 알고리즘과 확률적 분석은 매우 복잡하다. 최적 학습자의 구체적이고 기초적인 후보는 "3인 다수결(majority-of-three)" 규칙이다. 이는 훈련 샘플을 세 개의 독립적인 블록으로 나누고, 각 블록에서 일관된 분류기(consistent classifier)를 학습시킨 뒤, 그 다수결을 출력하는 방식이다. 이전 연구 [AAHLZ24]는 이 규칙이 기대값 측면에서 최적의 경계(bound)를 달성하며, 근사 최적 PAC 경계(이중 로그 인자 $\log \log(\min\{n/d, 1/\delta\})$ 차이 내에서)를 달당함을 증명했다. [AAHLZ24]의 저자들은 3인 다수결 규칙이 이러한 추가 인자 없이 최적의 PAC 경계를 달성할 것이라고 추측했다. 본 논문은 해당 추측에 대한 증명을 제공한다.

방법론
본 증명은 크기가 $m = n/3$인 독립적인 블록 $S_i$에서 학습된 일관된 분류기 $\hat{f}_i$에 대하여, 다수결 분류기 $Maj(\hat{f}_1, \hat{f}_2, \hat{f}_3)$의 오차에 대한 고확률 상한(high-probability upper bound)을 확립한다.

1. 중첩 모멘트로의 환원(Reduction to Overlap Moments):
   다수결의 오차는 적어도 두 개의 분류기가 어떤 점 $x$를 오분류할 때만 발생한다. $i$번째 분류기의 오차 집합을 $E_i = \{x : \hat{f}_i(x) \neq f^\star(x)\}$라고 할 때, 총 오차는 다음과 같이 쌍별 교집합의 합으로 유계된다:
   $$\text{err}_P(Maj) \leq P(E_1 \cap E_2) + P(E_2 \cap E_3) + P(E_1 \cap E_3).$$
   증명은 이러한 교집합 확률의 $L_q$ 모멘트, 구체적으로 $\|P(E_1 \cap E_2)\|_{L_q}$를 바운딩하는 데 집중한다.

2. 핵심 기술 도구: Proposition 2.2:
   논증의 핵심은 크기가 $m$인 두 독립적인 샘플 $S$와 $T$로부터 얻은 오차 집합의 중첩에 대한 모멘트 바운드를 제공하는 Proposition 2.2이다. VC 차원이 $d$인 VC 클래스 $\mathcal{C}$와 결정론적 일관된 선택자(deterministic consistent selector) $A$ (단, $A(S) \cap S = \emptyset$)에 대하여, 이 명제는 다음과 같이 기술된다:
   $$\|P(A(S) \cap A(T))\|_{L_q} \leq 62400 \frac{d + q}{m}.$$
   이 결과는 Simon [Sim15]의 중첩 추정치와 유사하지만, 중첩된 구조가 아닌 독립적인 샘플에 적용된다. 이러한 독립성은 이전의 중첩 구조 분석에 존재했던 이중 로그 인자를 피하는 데 결정적이다.

3. 재귀적 분해 및 조건부 확률:
   Proposition 2.2를 증명하기 위해, 저자들은 $q$개의 독립적인 테스트 포인트 $X = (X_1, \dots, X_q)$를 도입하여 중첩의 $q$차 모멘트를 분석한다. 모멘트는 $\mathbb{E}_X [p_q(X)^2]$로 재작성되며, 여기서 $p_q(X) = P(X \subseteq A(S))$이다.
   연쇄 법칙 분해(chain-rule decomposition)를 사용하여, $p_q(X)$는 조건부 포함 확률의 곱으로 표현된다:
   $$p_q(X) = \prod_{\ell=1}^q \alpha_{X_{<\ell}(X_\ell}), \quad \text{여기서 } \alpha_{z}(x) = P(x \in A(S) \mid z \subseteq A(S)).$$
   증명은 이러한 조건부 확률에 대한 꼬리 바운드(tail bound)인 Lemma 3.1에 의존한다. 이는 조건부 사건 $E_z$의 확률이 $p_z$일 때, 조건부 포함 확률 $\alpha_z(X)$가 임계값 $a$를 초과할 확률이 다음과 같이 유계됨을 보여준다:
   $$P(\alpha_z(X) > a) \leq \frac{160}{am} \left( d \log \frac{e}{a} + \log \frac{e}{p_z} \right).$$
   이 바운드는 VC 차원 항을 팽창시키지 않으면서 조건부 사건의 "희귀성(rarity)"을 제어한다.

4. 재귀적 논증:
   저자들은 제곱된 조건부 확률과 로그 항을 포함하는 가중 함수 $M_k$를 정의한다. 이들은 $M_k \leq \frac{960}{m} M_{k-1}$이라는 재귀식을 확립한다. $k=1$에서 $q$까지 이 재귀식을 반복 적용하면 원하는 $q$차 모멘트 바운드를 얻으며, 이는 $q = \lceil \log(1/\delta) \rceil$인 마르코프 부등식(Markov's inequality)을 통해 고확률 바운드로 변환된다.

주요 기여 및 결과

• 최적성 증명: 본 논문은 3인 다수결 학습자가 실현 가능한 PAC 설정에서 최적의 샘플 복잡도를 달성함을 증명한다. 구체적으로, 임의의 분포 $P$, 타겟 $f^\star$, 신뢰도 $\delta$에 대하여:
  $$P\left( \text{err}_P(Maj(\hat{f}_1, \hat{f}_2, \hat{f}_3)) \leq 107 \frac{d + \log(1/\delta)}{n} \right) \geq 1 - \delta.$$
  이는 보편적 상수(universal constant) 차이를 제외하면 고전적인 하한선 [EHKV89]과 일치한다.
• 분석의 단순화: 본 증명은 기존의 최적 학습자들(Hanneke [Han16] 및 Larsen의 bagging 분석 [Lar23] 등)의 알고리즘 구조와 확률적 분석을 단순화한다. 이는 복잡한 중첩 샘플 구조와 그로 인해 발생하는 이중 로그 인자들을 제거한다.
• 중첩 대비 독립성: 본 연구는 독립적인 블록을 사용하는 것(중첩된 샘플을 사용하는 것과 대조적으로)이 단순 투표 방식에 필요하다고 여겨졌던 $\log \log$ 인자들을 피하면서 더 깔적인 분석을 가능하게 함을 보여준다.

의의 및 주장
저자들은 이 결과가 3인 다수결 규칙의 최적성에 관한 [AAHLZ24]의 추측을 해결했다고 주장한다. 본 논문은 이 결과를 PAC 학습 이론의 중요한 단순화로 위치시키며, 증명 가능한 최적성을 가진 "가장 단순한 투표 방식"을 제공한다. 증명은 짧고 자기 완결적(self-contained)이며, 이전의 더 복잡한 최적 학습자들의 구성 대신 조건부 포함 확률의 새로운 재귀적 분해에 의존한다.

본 논문은 또한 LLM(대규모 언어 모델)을 사용하여 증명을 단순화한 과정을 설명하는 부록을 포함한다. 저자들은 초기 증명이 더 길었으며 제1저자에 의해 도출되었으나, 대안적인 논증을 탐색하기 위해 LLM의 도움을 받았으며, 그 결과 최종 원고에 제시된 더 짧은 재귀적 형태가 도출되었다고 언급했다. 수학적 주장은 저자들에 의해 검증되고 작성되었다.