Norm-based 일반화 이론은 왜 진공에서 멈추는가

딥러닝의 일반화는 고전 이론으로 설명되지 않는다. VC 차원과 Rademacher complexity는 실제 네트워크에서 vacuous한 bound를 내놓는다. 그렇다면 norm을 기반으로 한 정제가 이 간극을 닫을 수 있을까? Bartlett 2017에서 시작해 PAC-Bayes, path-norm, compression을 거쳐 Nagarajan-Kolter 2019의 반례에 이르는 여정은, norm-based 이론이 가진 구조적 한계를 드러낸다.

Margin과 spectral norm 곱

Bartlett, Foster, Telgarsky 2017의 출발점은 단순한 관찰이다. $L$-layer ReLU 네트워크의 Lipschitz 상수는 각 층의 spectral norm 곱 $\prod_l \|W_l\|_\sigma$으로 bound된다. 두 입력이 가까우면 출력도 그만큼 가깝고, 이는 covering number를 작게 만든다.

여기에 margin normalization을 결합한다. ReLU는 positive homogeneous이므로 전체 네트워크를 $\alpha$배 rescale하면 margin도 $\alpha^L$배가 된다. 그러나 margin-to-Lipschitz 비율

$\frac{\gamma}{\prod_l \|W_l\|_\sigma}$

은 rescaling에 불변이다. 이것이 진짜 capacity measure다.

bound의 구조에서 중요한 것은 초기화 기준 상대적 이동 $\|W_l - W_l^0\|_{2,1} / \|W_l\|_\sigma$이다. 절대적 norm이 아니라 초기화에서 얼마나 벗어났는가가 capacity를 결정한다. 이 아이디어는 이후 NTK의 “lazy regime”과 PAC-Bayes의 prior 설계에서 동일한 형태로 반복된다.

PAC-Bayes — 분포의 KL이 capacity가 되다

Bartlett 2017은 단일 hypothesis의 bound다. PAC-Bayes는 패러다임을 전환한다. 단일 $h$가 아니라 **posterior distribution $Q$ over $h$**의 expected loss를 bound하면, $\mathcal{H}$ 전체의 worst-case 문제를 피할 수 있다.

capacity는 이제 $\mathrm{KL}(Q \| P)$다. Gaussian posterior $Q = \mathcal{N}(\hat{W}, \Sigma)$와 prior $P = \mathcal{N}(W^0, \lambda I)$를 취하면:

$$\mathrm{KL}(Q \| P) \approx \frac{1}{2\lambda}\|\hat{W} - W^0\|^2 + (\text{분산 항})$$

주 항이 다시 “초기화로부터의 거리”다. Bartlett의 $\|W - W^0\|_{2,1}$과 구조가 같다.

Dziugaite & Roy 2017의 기여는 bound 자체를 minimization 목적함수로 삼아 $\mu$, $\Sigma$, $\lambda$를 SGD로 최적화한 것이다. 이로써 MNIST에서 $L \leq 0.161$이라는 최초의 non-vacuous bound를 달성했다. 이것이 역사적인 이유는 단순히 숫자가 작아서가 아니라, uniform convergence 프레임 안에서 non-vacuous가 가능함을 처음 보였기 때문이다.

Path-norm과 compression — 두 가지 정제

Neyshabur 2015의 path-norm은 네트워크 구조를 직접 반영한다. 입력에서 출력까지 각 경로의 weight 곱의 $p$-norm:

$$\|f\|_{\phi_p} = \left(\sum_{\text{path}} \left(\prod_{e \in \text{path}} |w_e|\right)^p\right)^{1/p}$$

이것이 spectral norm product보다 자연스러운 이유는 layerwise rescaling에 완전히 불변하기 때문이다. $W_l \to \alpha_l W_l$, $W_{l+1} \to W_{l+1}/\alpha_l$을 취하면 각 경로에서 $\alpha$와 $1/\alpha$가 상쇄된다. 2-layer 경우 Rademacher complexity는 $O(\|f\|_{\phi_2}\sqrt{\log d / n})$으로, 입력 차원 $d$에 logarithmic하게만 의존한다.

Arora et al. 2018은 전혀 다른 방향을 취한다. 훈련된 네트워크가 $k$-bit으로 압축 가능하면 effective capacity $\leq k$이고, 일반화 gap은 $O(\sqrt{k/n})$으로 bound된다. 핵심 관찰은 noise sensitivity다 — 훈련된 네트워크는 레이어 입력에 Gaussian noise를 넣어도 출력이 거의 변하지 않는다. 이는 각 레이어를 low-rank approximation으로 대체해도 출력이 유지됨을 의미하고, 따라서 압축이 가능하다.

이 관점은 Lottery Ticket Hypothesis와 같은 아이디어를 공유한다 — overparameterized 네트워크 안에 작은 effective subnetwork가 숨어있다.

Nagarajan-Kolter 2019 — 구조적 실패

그러나 훈련 중 $\prod \|W_l\|_\sigma$의 실제 거동을 보면 문제가 드러난다. ResNet CIFAR-10에서 훈련이 진행될수록 이 값은 $10^2$에서 $10^5$으로 단조 증가한다. 그러나 test accuracy는 함께 개선된다. Bound와 실제 일반화가 반대 방향으로 움직인다.

이것은 우연이 아니다. Cross-entropy loss는 confidence를 높이기 위해 weight magnitude를 키우는 방향으로 작용한다. norm 증가는 자연스러운 훈련 현상이고, norm 기반 bound는 이를 capacity 증가로 잘못 해석한다.

Nagarajan & Kolter 2019는 이 관찰을 구조적 불가능성 정리로 격상시킨다.

반례의 핵심은 고차원 구 위의 분포다. SGD가 훈련 샘플 $S$ 위에서 정확히 학습하더라도, 반전 샘플 $S' = \{(-x, y)\}$에서는 완전히 오분류한다. 고차원에서 $x$와 $-x$는 거의 직교하므로 SGD가 “보지 않은” 방향이다. ReLU의 asymmetry로 $f(-x) \neq -f(x)$가 되어 오분류가 발생한다.

uniform convergence는 ”$\mathcal{H}$ 안의 어떤 $h$가 어떤 샘플에서도 나쁠 수 있음”을 제한해야 하므로 vacuous한 bound를 피할 수 없다. SGD가 찾는 $h$는 특정 샘플 방향으로 biased되어 있고, 이 미스매치는 해결 불가능하다.

정리

• Bartlett 2017의 spectral norm 곱과 distance from initialization은 norm-based refinement의 기초다. 모든 후속 연구가 이 구조를 반복한다.
• PAC-Bayes는 패러다임 전환을 이뤄 MNIST에서 non-vacuous bound를 최초로 달성했지만, 이는 natural weight가 아닌 특별히 최적화된 weight의 bound다.
• Path-norm과 compression은 각각 scale-invariance와 effective complexity라는 다른 렌즈를 제공한다.
• Nagarajan-Kolter 2019는 uniform convergence 자체의 구조적 실패를 증명한다. 이것이 NTK(exact analysis), double descent(distribution-specific), implicit bias(algorithm-dependent)로 방향을 전환해야 하는 논리적 이유다.

norm이 진공에 머무는 이유는 capacity measure가 틀려서가 아니라, uniform convergence라는 프레임이 SGD의 algorithm-specific trajectory를 담을 수 없기 때문이다.