고전 일반화 이론은 왜 딥러닝 앞에서 무너지는가

딥러닝 일반화 이론의 출발점은 역설이다. ResNet50은 파라미터가 데이터보다 20배 많고, 완전한 노이즈 라벨도 완벽히 암기할 수 있으며, 그럼에도 ImageNet에서 76%의 정확도로 일반화한다. 고전 통계학습 이론은 이 세 사실을 동시에 설명할 수 없다. 왜 고전 이론이 실패하는가?

숫자로 체감하는 실패

VC 차원 기반 일반화 경계는 다음 형태다.

$$L(h) - \hat{L}_n(h) \leq \sqrt{\frac{8(d_{VC} \log(2en/d_{VC}) + \log(4/\delta))}{n}}$$

Harvey, Liaw, Mehrabian(2017)은 $W$개 파라미터, $L$개 레이어를 갖는 ReLU 네트워크의 VC 차원이 $\Theta(WL \log W)$임을 tight하게 증명했다. ResNet50($W \approx 2.56 \times 10^7$, $L = 50$)에 대입하면

$$d_{VC} \approx 2.56 \times 10^7 \cdot 50 \cdot \ln(2.56 \times 10^7) \approx 2.18 \times 10^{10}$$

ImageNet 훈련셋 $n \approx 1.28 \times 10^6$과 함께 경계를 계산하면

$$\sqrt{\frac{d_{VC}}{n}} \approx \sqrt{\frac{2.18 \times 10^{10}}{1.28 \times 10^6}} \approx 130$$

분류 오류는 $[0, 1]$ 값이다. 경계가 130이라는 말은 경계가 없다는 말과 같다. 이것이 “vacuous”의 정의다 — 경계 $B \geq 1$이면 "$L(h) \leq 1$"이라는 자명한 사실과 동치다.

Random Label이 드러낸 구조적 문제

Zhang, Bengio, Hardt, Recht, Vinyals(2017)의 실험은 이 실패가 단순히 “경계가 느슨한” 수준이 아님을 보여준다. CIFAR-10의 라벨을 완전 랜덤으로 교체하고 표준 네트워크를 훈련시키면 train accuracy 100%에 도달한다. 진짜 라벨에서 같은 네트워크는 test accuracy 94%를 얻는다.

같은 $\mathcal{H}$, 같은 알고리즘, 다른 일반화 성능. 이것이 핵심이다. 네트워크가 임의의 라벨링을 fit할 수 있다면, 해당 함수 클래스의 Rademacher complexity는 최대치에 가깝다.

$$\hat{\mathcal{R}}_n(\mathcal{H}) \geq \frac{1}{2}$$

Bartlett & Mendelson(2002)의 경계 $L(f) \leq \hat{L}_n(f) + 2\hat{\mathcal{R}}_n(\ell \circ \mathcal{F}) + O(\sqrt{\log(1/\delta)/n})$에서 우변의 $2\hat{\mathcal{R}}_n \geq 1$이 되므로 이 경계도 vacuous다.

Norm도 구하지 못한다

그렇다면 연속적 capacity measure, 즉 norm 기반 Rademacher bound는 어떨까. Frobenius norm의 레이어 곱 $\prod_l \|W_l\|_F$를 훈련된 ResNet50에서 측정하면 $10^{30}$ 이상이다. 이를 Rademacher bound에 넣으면 $\sqrt{10^{30}/n} \approx 10^{25}$ — VC보다 더 vacuous하다. Spectral norm 기반 Bartlett(2017)의 정교한 경계도 ResNet50 + ImageNet에서 실측하면 $>1$이다.

Nagarajan & Kolter(2019)는 이것이 우연이 아님을 증명했다.

직관은 간단하다. Uniform convergence는 $\mathcal{H}$ 전체의 worst-case를 본다. SGD가 특정한 “좋은” $h$만 선택한다는 사실을 반영할 방법이 없다.

SGD 자체가 Regularizer다

그 “좋은 $h$“는 어떻게 선택되는가. 과매개변화 선형 회귀에서 GD는 초기화 $\beta_0 = 0$으로부터 최소 $\ell^2$-norm 해 $\beta^* = X^+ y$로 수렴한다. 선형 분리 가능한 데이터에서 logistic loss의 GD는 방향이 hard-margin SVM solution으로 수렴한다.

이것이 implicit regularization의 수학적 기반이다. Max-margin은 SVM 이론으로 명확한 일반화 보장을 갖는다. SGD가 자동으로 max-margin을 찾는다면, 명시적 regularizer 없이도 capacity가 제어된다. 단 이 rigorous 결과는 선형 모델에 한정되고, 깊은 ReLU 네트워크로의 확장은 아직 열린 문제다.

고전 이론이 예측 못 하는 4가지 퍼즐

이 챕터들이 개별적으로 보여준 고전 이론의 실패는 하나의 지도로 묶인다.

Over-parameterization: $p/n \approx 20$인 ResNet50이 일반화한다. 고전 이론의 예측은 심각한 overfitting이다.

Double Descent: test error를 파라미터 수 $p$의 함수로 그리면 $p = n$ 근방에서 정점을 찍고 이후 다시 감소한다. 고전 bias-variance 트레이드오프는 단조 U-shape만 예측한다.

Grokking: modular arithmetic 같은 과제에서 train accuracy가 먼저 100%에 도달하고, test accuracy는 수천 스텝이 지나서야 100%에 합류한다. train loss가 최소에 도달한 이후에도 학습이 계속된다는 것은 고전 이론에 없는 개념이다.

Neural Scaling Laws: loss가 모델 크기 $N$, 데이터 크기 $D$의 power-law $L \sim A/N^\alpha + B/D^\beta$로 감소한다 (Kaplan 2020, Hoffmann 2022). 특정 규모에서 능력이 불연속적으로 출현한다.

네 퍼즐은 고전 이론의 서로 다른 전제를 깬다. 그러나 공통점이 있다 — 모두 “effective capacity $\neq$ classical capacity”를 시사한다. SGD가 도달하는 $\mathcal{H}_\text{SGD} \subsetneq \mathcal{H}$의 capacity가 일반화를 결정한다. PAC-Bayes는 posterior를, NTK는 RKHS 부분공간을, Double Descent 이론은 min-norm interpolator의 자동 capacity 감소를 각기 다른 언어로 이야기하지만, 같은 관찰을 향한다.

정리

• ResNet50의 VC 차원은 $\approx 10^{10}$, ImageNet $n \approx 10^6$. $\sqrt{d_{VC}/n} \approx 130$ — 완전 vacuous.
• Zhang 2017의 random label 실험은 uniform convergence가 구조적으로 실패함을 실증한다. Nagarajan & Kolter 2019는 이를 수학적 불가능성으로 확정한다.
• GD는 선형 모델에서 min-norm / max-margin으로 수렴한다 (Soudry 2018). 이 implicit bias가 explicit regularizer 없는 일반화의 기반이다.
• 고전 이론이 예측 못 하는 4가지 퍼즐 — over-parameterization, double descent, grokking, scaling laws — 은 통합 이론이 아직 없다는 가장 솔직한 현황이다.

고전 이론이 틀린 것이 아니다. 수학적으로 참이다. 단지 ResNet50에 적용하면 의미 있는 숫자를 주지 못한다. 현대 이론들은 “다른 capacity measure”를 찾는 여정이다.