Rademacher 복잡도는 왜 VC보다 강한가

VC 차원은 가설공간이 얼마나 많은 패턴을 구분할 수 있는가를 묻는다. 하지만 이 질문은 데이터를 보기 전에 답해야 한다. Rademacher 복잡도는 다르게 묻는다 — 실제 샘플 위에서, 함수족이 완전히 랜덤한 라벨을 얼마나 잘 학습하는가? 이 차이가 왜 현대 ML 이론의 tighter bound를 가능하게 하는가?

랜덤 라벨 상관성이 복잡도를 측정하는 이유

$\sigma_i \in \{\pm 1\}$을 각각 확률 1/2로 취하는 Rademacher 변수라 하자. 동전 던지기로 생성한 노이즈 라벨이다. 고정된 샘플 $S = (x_1, \ldots, x_n)$과 함수족 $\mathcal{F}$에 대해 경험적 Rademacher 복잡도를 다음과 같이 정의한다.

$$\hat{\mathcal{R}}_S(\mathcal{F}) := \mathbb{E}_\sigma\left[\sup_{f \in \mathcal{F}} \frac{1}{n} \sum_{i=1}^n \sigma_i f(x_i)\right]$$

직관은 단순하다. $\mathcal{F}$가 표현력이 높으면 어떤 랜덤 라벨 패턴이든 맞출 수 있고 이 값은 크다. 표현력이 낮으면 랜덤 신호에 거의 상관되지 않아 값이 작다. 큰 Rademacher 복잡도 = 함수족이 노이즈까지 학습하려는 욕심 = 높은 과적합 위험이다.

VC 차원과의 결정적 차이는 데이터 의존성이다. VC는 가설공간의 기하학적 성질(shattering)만 본다. $\hat{\mathcal{R}}_S$는 실제 샘플 $S$에서 함수족이 어떻게 행동하는지 측정하므로, 데이터가 margin structure나 low-density 구조를 가지면 VC보다 훨씬 tighter한 bound를 준다.

일반화 경계의 핵심 구조

Rademacher 복잡도가 실제로 쓸모있으려면 일반화 gap을 bound해야 한다. 핵심 정리는 다음이다.

이 정리의 강점은 VC bound를 특수 경우로 포함한다는 것이다. Massart’s Lemma에 의해 유한 함수족의 Rademacher는 $O(\sqrt{\log|\mathcal{F}|/n})$이고, 여기에 Sauer-Shelah lemma($|\mathcal{H}(S)| \leq (en/d)^d$)를 대입하면 VC bound $O(\sqrt{d\log n/n})$이 정확히 회복된다.

Contraction Lemma — Surrogate Loss의 정당화

실전에서 0-1 loss는 불연속이어서 직접 최적화할 수 없다. hinge, log, cross-entropy 같은 surrogate loss를 쓴다. 왜 이 대체가 이론적으로 정당한가?

직관은 “수축”이다. Lipschitz 함수는 거리를 $L$배로 압축한다. Rademacher 신호의 힘도 같은 비율로 감소한다.

응용이 강력하다. hinge loss $\ell(z) = \max(0, 1-z)$는 1-Lipschitz이므로 $\mathcal{R}_n(\ell_{\text{hinge}} \circ \mathcal{H}) \leq \mathcal{R}_n(\mathcal{H})$. 또한 margin $\gamma > 0$에 대한 margin loss $\ell_\gamma(z) = \max(0, 1 - z/\gamma)$는 $1/\gamma$-Lipschitz이므로:

$$\mathcal{R}_n(\ell_\gamma \circ \mathcal{F}) \leq \frac{1}{\gamma} \mathcal{R}_n(\mathcal{F})$$

margin이 클수록 Rademacher 복잡도가 줄어들고, 일반화 경계가 개선된다. 이것이 SVM margin 최대화의 수학적 정당화다.

선형·커널·신경망으로의 전개

Rademacher 복잡도는 알고리즘마다 구체적인 값으로 계산된다.

선형 함수족 $\mathcal{F} = \{w^\top x : \|w\| \leq B\}$의 경우, Cauchy-Schwarz에 의해:

$$\hat{\mathcal{R}}_S(\mathcal{F}) \leq \frac{B}{n}\sqrt{\sum_{i=1}^n \|x_i\|^2} \leq \frac{B \cdot \max_i \|x_i\|}{\sqrt{n}}$$

파라미터 수가 아니라 norm 제약 $B$와 데이터 norm만이 복잡도를 결정한다. L2 regularization이 $\|w\|$를 줄이면 Rademacher가 직접 감소한다.

**RKHS(kernel method)**에서는 무한차원인데도 결과가 놀랍도록 간단하다. kernel matrix $K_{ij} = k(x_i, x_j)$에 대해:

$$\mathcal{R}_n(\mathcal{F}_B) \leq \frac{B\sqrt{\text{tr}(K)}}{n}$$

kernel matrix의 trace, 즉 대각 원소합이 복잡도를 완전히 제어한다.

신경망으로 가면 Contraction Lemma가 층마다 적용된다. $L$층 망에서 각 activation이 Lipschitz(ReLU는 1, sigmoid는 1/4)이고 weight Frobenius norm이 $\|W_l\|_F \leq M_l$이면(Bartlett & Mendelson 2002):

$$\mathcal{R}_n(\mathcal{F}) = O\left(\frac{1}{\sqrt{n}} \prod_{l=1}^L \|W_l\|_F\right)$$

층이 깊어질수록 norm 곱이 커져 bound가 느슨해질 수 있다. 하지만 SGD는 암묵적 정규화(implicit regularization)를 통해 자연스럽게 norm-small solution으로 수렴한다는 관찰이 있다. 이 때 norm-based bound는 VC bound(파라미터 수에 비례, 거대한 값)와 달리 의미있는 값을 준다.

정리

• Rademacher 복잡도는 함수족이 랜덤 라벨에 상관되는 정도로 표현력을 측정한다. 데이터에 의존하므로 VC보다 tighter하다.
• Symmetrization + McDiarmid로 $\sup_h |L_\mathcal{D}(h) - L_S(h)| \leq 2\mathcal{R}_n + O(\sqrt{\log(1/\delta)/n})$을 얻는다. VC bound는 이 틀의 특수 경우다.
• Contraction Lemma는 surrogate loss(hinge, log)의 Rademacher가 원래 함수족의 Lipschitz 상수 배로 bound됨을 보인다. margin 최대화의 이론적 정당화가 여기서 나온다.
• 선형→커널→신경망: norm 제약이 복잡도를 제어한다. 파라미터 수가 아니라 weight의 크기가 일반화를 결정한다.

신경망에서 이 bound가 실제로 얼마나 tight한지, 그리고 Double Descent 현상을 설명하려면 추가 도구(NTK, PAC-Bayes, stability)가 필요하다.