기술적 요약: 스케일 민감한 파편화: 최적 스케일에서의 학습 가능성과 평가 가능성

문제 제기

본 논문은 실수값 함수 클래스에 관한 통계적 학습 이론의 근본적인 질문들을 다룬다. 구체적으로, 무시학습 가능성 (agnostic learnability), 균등 수렴, 그리고 VC 차원의 스케일 민감 일반화인 fat-shattering dimension이라는 세 가지 핵심 개념 간의 정밀한 관계를 조사한다.

이진 분류에 대한 "PAC 학습의 기본 정리"는 이러한 개념들의 동등성을 확립하지만, 실수값 설정에서는 역사적으로 간극이 존재해 왔다. 선행 연구 (예: Bartlett 와 Long, 1998) 는 유한한 $\gamma$-fat-shattering 차원이 균등 수렴과 학습 가능성을 함의함을 보였으나, 오직 $2\gamma$ (또는 $c>2$인 경우 $c\gamma$) 스케일에서만 성립함을 보였다. 이는 스케일에서 2 배의 곱셈 인자가 불가피한지 여부에 대한 질문을 남겼으며, 이는 Anthony 와 Bartlett 의 교재 (1999) 에서 Phil Long 에 의해 제기된 추측이었다.

또한, 본 논문은 **메트릭 엔트로피 (덮개 수의 로그)**가 fat-shattering 차원과 관련하여 어떻게 행동하는지 다룬다. 이전 결과들 (Alon 등, 1997; Rudelson 과 Vershynin, 2006) 은 메트릭 엔트로피에 대한 상한을 제시했으나, 최적 스케일에서 표본 크기 $n$에 대한 의존성이 $O(\log^2 n)$에서 $O(\log n)$으로 개선될 수 있는지, 그리고 이러한 상한에서의 스케일 인자를 강화할 수 있는지 여부는 미해결로 남아 있었다.

마지막으로, 본 논문은 이러한 이론적 통찰을 적분 확률 거리 (IPMs) 를 사용한 생성 모델의 평가 가능성과 추정 가능성에 적용한다. 최근 이진 테스트 함수에 대한 이분법 (Aiyer 등, 2026) 은 그러한 거리들이 최적 스케일 $c=3$에서 추정 가능하거나 약하게 평가 가능함을 시사했다. 그러나 앞서 언급된 균등 수렴 결과의 스케일 간극으로 인해 이를 실수값 함수로 확장하는 것은 방해받았다.

방법론

저자들의 주요 기술적 혁신은 패킹 수 (packing numbers) 를 통한 표준적인 우회로를 피하는 경험적 $\ell_\infty$ 덮개 수에 대한 직접적 상한이다.

1. 부분 개념 클래스를 통한 직접 덮개:
   덮개 수를 패킹 수와 연관시키는 것 (이는 본질적으로 스케일 손실을 초래함) 대신, 저자들은 부분 개념 클래스 (partial concept classes) 이론 (Lon01; AHHM22) 을 활용한다. 그들은 실수값 함수를 스케일 $\gamma$에 대한 임계값을 기준으로 부분 이진 함수로 매핑한다. 이러한 유도된 부분 클래스들의 VC 차원을 상한으로 정함으로써, 그들은 지수 하위 크기의 명시적 덮개를 구성한다. 이를 통해 $2\gamma$가 아닌 최적 스케일 $\gamma/2$에서 직접 덮개 수 상한을 유도할 수 있다.

2. 반복적 정제:
   $\gamma/2$에 임의로 가까운 스케일에서 상한을 달성하기 위해, 저자들은 반복적 구성을 활용한다. 거친 덮개에서 시작하여 상자를 재귀적으로 정제하고, 덮개 크기의 성장을 제어하면서 반지름을 기하급수적으로 줄인다. 이는 $n$에 대해 선형이 아닌 메트릭 엔트로피 $H(F, \gamma/2 + \epsilon, n)$에 대한 상한을 산출한다.

3. 표본 압축과 쌍대 클래스:
   스케일이 큰 ($\gamma > 2\gamma^*$) 영역에서, 저자들은 **표본 압축 체계 (sample compression schemes)**를 활용한다. 유한한 fat-shattering 차원을 가진 함수 클래스의 쌍대 클래스도 균등 수렴을 만족한다는 사실 (주요 정리에 의해 유도된 결과) 을 이용하여 분포를 희소화하고 상수 크기의 압축 체계를 구성한다. 이는 $O(\log n)$ 엔트로피 상한으로 이어진다.

4. 총변동 (Total Variation) 으로 환원:
   평가 가능성에 대한 적용에서, 저자들은 무한한 fat-shattering 차원을 가진 일반적인 IPMs 를 총변동 (TV) 거리 설정으로 환원하는 구성을 만든다. 파편화된 집합에 대한 분포의 혼합을 신중하게 구성하여 IPM 이 점근적으로 TV 거리처럼 행동하며 최적 스케일 상수를 보존함을 보인다.

주요 기여 및 결과

1. 스케일 간극의 해결 (정리 1)

본 논문은 실수값 클래스에 대한 PAC 학습 기본 정리의 정확한 유사체를 확립한다. 유계 함수 클래스 $F$와 스케일 $\gamma > 0$에 대해, 다음은 동치이다:

1. $F$는 $\gamma/2$-학습 가능하다.
2. $F$는 $\gamma$-균등 수렴을 만족한다.
3. 모든 $\gamma' > \gamma$에 대해, $F$의 $\gamma'$-fat-shattering 차원은 유한하다.

의의: 이 결과는 2 배 간극이 불가피하다는 추측을 반증한다. fat-shattering 차원이 $\gamma$보다 엄격하게 큰 임의의 스케일에서 유하다면, 학습 가능성과 균등 수렴이 최적 스케일 $\gamma/2$(학습 가능성의 경우) 와 $\gamma$(수렴의 경우) 에서 성립함을 증명한다.

2. 날카로운 메트릭 엔트로피 상한 (정리 2)

본 논문은 임계 스케일 $\gamma^* = \inf\{\gamma : \text{fat}_\gamma(F) < \infty\}$에 기반한 메트릭 엔트로피 $H(F, \gamma, n)$의 성장을 완전히 특징짓는다:

• 선형 영역 ($\gamma < \gamma^*/2$): $H(F, \gamma, n) = \Theta(n)$.
• 중간 영역 ($\gamma^*/2 < \gamma \le 2\gamma^*$): $H(F, \gamma, n) = O(\log^2 n)$. 본 논문은 이 상한이 (하위 차수 항을 제외하고) $\gamma \in (\gamma^*/2, \gamma^*)$에 대해 엄밀함을 보여, Alon 등 (1997) 이 $\log^2 n$ 인자의 필요성에 대해 제기한 질문을 해결한다.
• 대규모 스케일 영역 ($\gamma > 2\gamma^*$): $H(F, \gamma, n) = O(\log n)$. 이는 충분히 큰 스케일에서 지수를 1 로 줄일 수 있음을 확인하며, Rudelson 과 Vershynin (2006) 이 제기한 질문을 해결한다.

3. 생성 모델 평가 가능성에 대한 이분법 (정리 3 및 명제 1)

날카로운 스케일 민감 결과를 적용하여, 본 논문은 유계 적분 확률 거리 (IPMs) 에 대한 이분법을 확립한다:

• 모든 $\gamma > 0$에 대해 fat-shattering 차원이 유한하면, IPM 은 추정 가능하며 (따라서 $c=1$로 강력하게 평가 가능함).
• 어떤 $\gamma \in (0, 1/2)$에 대해 fat-shattering 차원이 무한하면, IPM 은 최적 스케일 $c=3$에서 약하게 평가 가능하지만, $c < 3$인 경우에는 그렇지 않다.

의의: 이는 Aiyer 등 (2026) 의 이진 이분법을 실수값 함수로 확장한다. 증명은 균등 수렴을 2 배 손실 없이 스케일 $\gamma$에서 확립할 수 있는 저자들의 능력에 결정적으로 의존한다; 이것이 없다면 최적 스케일 $c=3$에 대한 논증이 실패할 것이다.

4. 닫힘 성질

본 논문은 $\gamma$-학습 가능성과 $\gamma$-균등 수렴의 성질이 다음 하에서 불변임을 보인다:

• 쌍대성: 균등 수렴 클래스의 쌍대 클래스도 균등 수렴한다.
• 집계: 1-리프시츠 함수를 통한 클래스의 집계는 동일한 스케일에서 균등 수렴을 보존한다.

의의 및 주장

저자들은 그들의 작업이 학습 이론의 여러 장기적인 미해결 질문들을 해결한다고 주장한다:

1. 2 배 인자 추측의 반증: 최적 스케일에서 학습 가능성과 균등 수렴이 성립함을 증명함으로써, Anthony 와 Bartlett (1999) 이 제기한 질문에 결정적으로 답하며, 2 배 간극이 본질적이지 않음을 보인다.
2. 날카로운 엔트로피 상한: 메트릭 엔트로피가 표본 크기 $n$과 스케일 $\gamma$에 어떻게 의존하는지 명확히 하여, $O(\log n)$ 상한이 언제 달성 가능한지 versus $O(\log^2 n)$이 언제 필요한지 정확히 규명한다.
3. 평가 가능성의 정성적 특징: 스케일에서 2 배에서 1 로의 정량적 개선이 생성 모델 평가의 정성적 특징을 열어준다고 주장하며, 추정 가능성과 $c=3$인 약한 평가 가능성 사이의 날카로운 이분법을 확립한다.

저자들은 점근적 행동과 이분법의 존재를 해결하지만, 중간 범위 $\gamma^* < \gamma \le 2\gamma^*$에서의 엔트로피의 정밀한 행동과 최적 스케일에서의 학습에 대한 정밀한 표본 복잡도 상한은 여전히 미해결 문제라고 지적한다. 또한, 다른 $\ell_p$ 거리 하에서 fat-shattering 차원과 덮개 수 간의 관계는 향후 연구에 맡겨진다.