SGD는 왜 일반화하는가 — Stability 이론의 답

Zhang et al. (2017)은 신경망이 훈련 데이터의 완전히 무작위한 라벨을 암기할 수 있음을 보였다. VC 차원이 사실상 무한한 모델이 실제 데이터에서는 잘 일반화한다는 역설이다. VC와 Rademacher는 이 현상을 설명하지 못한다 — 가설공간이 너무 크기 때문이다. 그렇다면 신경망은 왜 일반화하는가?

다른 렌즈 — “알고리즘이 얼마나 민감한가”

VC와 Rademacher는 가설공간 $\mathcal{H}$의 복잡도를 측정한다.

$\text{Gap} \lesssim \sqrt{\frac{\text{complexity}(\mathcal{H})}{n}}$

Stability는 다른 질문을 던진다. “알고리즘 $A$ 자체가 데이터 변화에 얼마나 민감한가?”

훈련 집합 $S$에서 샘플 하나 $z_i$를 $z_i' \sim \mathcal{D}$로 교체한 집합을 $S^{(i)}$라 하자. 알고리즘이 이 교체에 둔감하다면 — 즉 $A(S)$와 $A(S^{(i)})$가 임의의 테스트 포인트에서 비슷한 손실을 낸다면 — 훈련 분포의 작은 변화가 모델 행동을 크게 바꾸지 않는다. 이것이 일반화를 함의한다.

$\sup_S \sup_{i} \sup_{z_i'} \sup_z \left| \ell(A(S), z) - \ell(A(S^{(i)}), z) \right| \leq \beta$

이 조건을 $\beta$-uniform stability라 한다. $\beta$가 작을수록 알고리즘이 안정적이다. 핵심은 이 경계가 $\mathcal{H}$에 전혀 의존하지 않는다는 점이다.

$\text{Gap} \lesssim \beta$

같은 $\mathcal{H}$를 써도 알고리즘이 다르면 $\beta$가 달라진다. Unregularized ERM은 불안정하고, Ridge는 안정적이다. 이것이 regularization이 일반화를 돕는 이유의 수학적 정체다.

Stability ⇒ Generalization

Uniform stability가 실제로 일반화를 함의한다는 것을 보이려면 두 가지 경계가 필요하다.

평균적 경계 (정리 6.2): $\beta$-uniform stability하면

$\mathbb{E}_S[L_\mathcal{D}(A(S)) - L_S(A(S))] \leq \beta.$

증명의 핵심은 rename trick이다. $z_i$와 $z_i'$가 같은 분포 $\mathcal{D}$에서 독립적으로 뽑혔으므로 교환 가능하다. 이 exchangeability를 이용하면 경험 위험의 기대값을 모집단 위험으로 변환할 수 있고, 그 차이가 stability 항 $\beta$로 bound된다.

고확률 경계 (정리 6.3): 손실 $\ell \in [0, M]$일 때, 확률 $\geq 1 - \delta$로

$L_\mathcal{D}(A(S)) - L_S(A(S)) \leq \beta + O\!\left(\sqrt{\frac{M \log(1/\delta)}{n}}\right).$

Ridge Regression — 정규화의 수학적 정당화

Ridge regression

$w^*_S = \arg\min_{w} \left\{ \frac{1}{n} \sum_{i=1}^n (w^\top x_i - y_i)^2 + \lambda \|w\|^2 \right\}$

의 stability는 strong convexity에서 나온다. 정규화항 $\lambda \|w\|^2$가 목적함수의 Hessian에 $2\lambda I$를 더하므로, 손실함수는 $2\lambda$-strongly convex가 된다.

Strong convexity의 의미: 최적해 근처에서 함수가 가파르게 증가한다. 따라서 $S$와 $S^{(i)}$ 두 문제의 최적해 $w^*_S$, $w^*_{S^{(i)}}$는 서로 멀리 있을 수 없다.

$\lambda \|w^*_S - w^*_{S^{(i)}}\|^2 \leq \frac{4M}{n}$

여기에 squared loss의 Lipschitz 성질을 결합하면:

$\beta_{\text{Ridge}} = O\!\left( \frac{1}{\lambda n} \right).$

SGD — 적게 훈련하는 것이 정규화다

Hardt et al. (2016)의 핵심 결과는 SGD의 stability bound다.

$\beta_{\text{SGD}} \leq \frac{2L^2 \eta T}{n}$

여기서 $L$은 손실의 Lipschitz 상수, $\eta$는 학습률, $T$는 반복 횟수다.

이 결과의 함의는 강력하다: 명시적 정규화항 없이도, 훈련을 일찍 멈추면 $\beta$가 작아지므로 일반화 gap이 줄어든다. 이것이 early stopping의 수학적 정당화다.

$\text{Gap} \leq \frac{2L^2 \eta T}{n} + O\!\left(\sqrt{\frac{\log(1/\delta)}{n}}\right)$

Ridge의 $\lambda$와 SGD의 $T$는 서로 다른 방식으로 같은 목표를 달성한다. Ridge는 목적함수를 가파르게 만들고, SGD는 탐색 범위 자체를 제한한다.

정리

• Uniform Stability는 $\mathcal{H}$-독립적으로 알고리즘의 robustness를 측정한다. 같은 가설공간에서도 알고리즘에 따라 stability가 달라진다.
• 정리 6.2·6.3: $\beta$-stable 알고리즘의 일반화 gap은 기대값 $\leq \beta$, 고확률로 $\leq \beta + O(\sqrt{\log(1/\delta)/n})$.
• Ridge: strong convexity → $\beta = O(1/\lambda n)$. 정규화 강도가 stability를 직접 제어한다.
• SGD: non-expansive step → $\beta = O(\eta T / n)$. Early stopping은 implicit regularization이다.

Zhang et al.의 역설에 대한 stability의 답은 이렇다: 신경망이 일반화하는 이유는 가설공간이 작아서가 아니라, SGD가 유한 단계에서 안정적으로 수렴하기 때문이다 — 적어도 부분적으로는.