규모 민감형 샤터링 (Scale-Sensitive Shattering): 최적 규모에서의 학습 가능성 및 평가 가능성

우리는 실수 값 함수 클래스 (real-valued function classes)가 균등 수렴 (uniform convergence) 및 학습 가능성 (learnability)을 나타내는 최적의 규모 (optimal scale)를 연구합니다. 우리의 주요 결과는 PAC 학습 (PAC learning)의 기본 정리 (fundamental theorem)를 규모 민감형 (scale-sensitive)으로 일반화합니다. 즉, 모든 유계된 실수 값 클래스 (bounded real-valued class)와 모든 $\gamma>0$에 대하여, 규모 $\gamma$에서의 균등 수렴, 규모 $\gamma/2$에서의 에그노스틱 학습 가능성 (agnostic learnability), 그리고 모든 규모 $\gamma'>\gamma$에서의 fat-shattering 차원 (fat-shattering dimension)의 유한성은 서로 동치입니다. 이는 학습 가능성을 지배하는 정확한 규모에 관한 Anthony와 Bartlett (Cambridge Univ. Press 1999)의 질문을 해결하며, 곱셈적 2배 차이 (multiplicative 2-factor gap)가 불가피하다는 Phil Long의 추측을 반박하고, 그러한 손실을 초래했던 Bartlett과 Long (JCSS 1998)의 상한 (upper bounds)을 개선합니다. 핵심적인 기술적 요소는 패킹 수 (packing numbers)를 거치는 표준적인 우회 과정을 피하고, 경험적 $\ell_\infty$ 커버링 수 (empirical $\ell_\infty$ covering numbers)에 대한 직접적인 경계 (direct bound)를 구하는 것입니다. 그 결과, 우리는 fat-shattering 규모 $\gamma$에 따른 날카로운 점근적 메트릭 엔트로피 (asymptotic metric-entropy) 경계를 얻습니다. 즉, 규모 $\gamma/2$에서는 이미 $O(\log^2 n)$ 경계가 성립하며, 규모 $2\gamma$에서는 $O(\log n)$ 경계가 성립합니다. 나아가 우리는 $O(\log^2 n)$ 경계가 때때로 타이트 (tight)함을 보여줍니다. 이러한 결과는 Alon 등 (JACM 1997)과 Rudelson 및 Vershynin (Ann. of Math. 2006)의 미해결 질문들을 해결합니다. 응용 사례로서, 우리는 유계된 적분 확률 메트릭 (bounded integral probability metrics, IPM)에 대한 날카로운 이분법 (sharp dichotomy)을 확립합니다. 모든 그러한 IPM은 추정 가능 (estimable)하거나, 혹은 어떠한 곱셈적 인자 $c<3$ 내에서도 약하게 평가 (weakly evaluated)될 수 없으며, 반면 $3$-약한 평가 가능성 (3-weak evaluability)은 항상 성립합니다. 이는 Aiyer 등 (ICML 2026)의 미해결 질문을 해결합니다. 또한 우리는 정량적 샘플 복잡도 (quantitative sample complexity) 및 평가 가능성에 관한 몇 가지 미해결 질문들을 강조합니다.