집중부등식은 왜 ML 이론의 기초인가

“샘플이 충분히 크면 괜찮다.” ML 실무에서 자주 쓰는 말이다. 그런데 얼마나 충분해야 하는가? 그리고 “괜찮다”는 말이 확률적으로 정확히 무엇을 의미하는가? 집중부등식은 이 질문에 수식을 붙이는 이론이다.

첫 번째 계단 — Markov와 Chebyshev

집중부등식의 출발점은 놀랍도록 단순하다. 비음수 확률변수 $X$와 임계값 $t > 0$에 대해 다음이 성립한다.

$$\mathbb{P}(X \geq t) \leq \frac{\mathbb{E}[X]}{t}$$

증명의 핵심은 지시함수(indicator)다. $X$의 기대값을 $X \geq t$인 영역과 아닌 영역으로 쪼개면, $X \geq 0$이라는 조건만으로 $\mathbb{E}[X] \geq t \cdot \mathbb{P}(X \geq t)$가 따라나온다. 분포를 전혀 몰라도 성립한다는 것이 Markov 부등식의 힘이자 한계다.

Chebyshev는 한 단계를 더 올라간다. $Y = (X - \mu)^2$로 놓으면 $Y \geq 0$이므로 Markov를 적용할 수 있고, 결과는

$$\mathbb{P}(|X - \mu| \geq t) \leq \frac{\text{Var}(X)}{t^2}$$

이다. 분산이라는 추가 정보를 쓰는 대신 $1/t^2$ 속도의 경계를 얻는다. 표본 평균 $\bar{X}_n$에 적용하면 경계가 $\sigma^2 / (nt^2)$으로 줄어드는데, $n$이 커져도 여전히 $t$에 대해 다항식으로 감소한다. 이것이 문제다.

지수 속도의 등장 — Hoeffding

Hoeffding 부등식은 이 간극을 메운다. $X_i \in [a_i, b_i]$이고 독립인 확률변수들의 표본 평균에 대해

$$\mathbb{P}(|\bar{X}_n - \mu| \geq t) \leq 2\exp\!\left(-\frac{2nt^2}{\sum_{i=1}^n (b_i - a_i)^2}\right)$$

이 성립한다. 핵심 재료는 두 가지다. Chernoff 방법 — $\mathbb{P}(X \geq t) = \mathbb{P}(e^{\lambda X} \geq e^{\lambda t}) \leq e^{-\lambda t} \mathbb{E}[e^{\lambda X}]$로 확률을 MGF로 bound한 뒤 $\lambda$를 최적화한다. Hoeffding의 Lemma — $X \in [a, b]$이고 $\mathbb{E}[X] = 0$이면 $e^x$의 볼록성으로부터 $\mathbb{E}[e^{\lambda X}] \leq e^{\lambda^2(b-a)^2/8}$이 나온다. 구간 폭의 제곱이 분모에 들어가고, 최적 $\lambda$를 대입하면 지수 속도가 확정된다.

이 한 줄이 PAC learning 전체의 출발점이다. 고정된 가설 $h$ 하나에 대해, 경험 위험 $L_S(h)$와 참 위험 $L_\mathcal{D}(h)$의 편차가 $\epsilon$ 이상일 확률은 $2e^{-2n\epsilon^2}$으로 지수 감소한다. 가설 공간 $\mathcal{H}$가 유한하면 union bound로 모든 $h \in \mathcal{H}$에 확장할 수 있고, Rademacher 복잡도는 이를 무한 공간으로 밀어 올린다.

함수로의 일반화 — McDiarmid

Hoeffding은 표본 평균이라는 특수한 함수에만 작동한다. 교차 검증 오차, 경험적 Rademacher 복잡도, bootstrap 통계량처럼 구조가 복잡한 함수에는 다른 도구가 필요하다.

McDiarmid 부등식은 “한 좌표를 바꿔도 함수가 많이 변하지 않는다”는 조건으로 같은 지수 속도를 보장한다.

Bounded differences 조건: $i$번째 좌표에서만 다른 $x, x'$에 대해 $|f(x) - f(x')| \leq c_i$.

이 조건 아래

$$\mathbb{P}(|f(X) - \mathbb{E}[f(X)]| \geq t) \leq 2\exp\!\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right)$$

이 성립한다. 증명의 구조는 Doob martingale을 경유한다. 샘플을 하나씩 공개하는 수열 $V_i = \mathbb{E}[f(X) | X_1, \ldots, X_i]$은 martingale이고, 차분 $D_i = V_i - V_{i-1}$은 bounded differences 조건에 의해 $|D_i| \leq c_i$를 만족한다. 여기서 Azuma-Hoeffding lemma — martingale 차분의 집중 — 를 적용하면 결론이 따라온다.

경험적 Rademacher 복잡도 $\hat{\mathcal{R}}_S = \frac{1}{n}\sup_{h \in \mathcal{H}} \sum_i \sigma_i h(x_i)$에서 한 점 $x_i$를 바꾸면 함수값이 최대 $1/n$만큼 변한다. $c_i = 1/n$이므로 $\sum c_i^2 = 1/n$이고, McDiarmid를 적용하면 Rademacher 복잡도 자체의 집중을 $2e^{-2t^2 n}$ 수준으로 bound할 수 있다. 이것이 Ch5에서 Rademacher 일반화 경계를 세울 때 McDiarmid가 핵심 도구인 이유다.

분산을 활용하면 — Bernstein

Hoeffding은 분포를 무시하고 범위만 본다. “최악의 경우”를 가정하기 때문에 분산이 작은 상황에서 불필요하게 느슨하다.

Bernoulli($p = 0.01$)을 생각하자. 분산은 $\sigma^2 = 0.01 \times 0.99 \approx 0.01$인데 범위는 $[0, 1]$로 고정이다. Hoeffding은 범위만 보고 $2e^{-2nt^2}$를 준다. Bernstein은 분산을 직접 쓴다.

$$\mathbb{P}(|\bar{X} - \mu| \geq t) \leq 2\exp\!\left(-\frac{nt^2}{2\sigma^2 + 2Mt/3}\right)$$

분모의 구조가 두 가지 정권을 자동으로 구분한다. $t \ll \sigma^2/M$이면 $2\sigma^2$ 항이 지배해 $e^{-nt^2/(2\sigma^2)}$로 수렴하고, $t \gg \sigma^2/M$이면 $2Mt/3$ 항이 지배해 Hoeffding과 비슷해진다. Bernoulli($p = 0.01$)에서 작은 $t$에 대해 Bernstein은 Hoeffding보다 지수적으로 tight하다.

트레이드오프

실전에서의 선택 기준은 단순하다. 표본 평균이고 범위를 알면 Hoeffding, 분산까지 작으면 Bernstein. 표본 평균이 아닌 복잡한 함수(CV 오차, Rademacher, bootstrap 통계량)라면 McDiarmid. 범위도 분산도 모르면 Chebyshev. 아무 정보도 없으면 Markov가 유일한 선택이다.

한 가지 공통된 한계가 있다. 이 부등식들은 모두 iid 가정에 의존한다. 시계열이나 분포 이동 상황에서는 martingale 버전이나 mixing coefficient를 도입한 변형이 필요하다. 그리고 모두 “최악의 경우”를 본다 — 실제 데이터가 분포적으로 깔끔하면 bound는 실제보다 훨씬 느슨하다. 딥러닝 이론에서 이 경계들이 “vacuous”하다고 불리는 이유다.

정리

• Markov는 indicator trick 하나로 작동한다. 비음수성만으로 $\mathbb{P}(X \geq t) \leq \mathbb{E}[X]/t$가 따라나오며, 이 trick은 이후 모든 부등식의 원형이다.
• Hoeffding의 지수 속도는 Chernoff 방법(MGF를 Markov에 적용)과 볼록성 기반 MGF 상한의 조합에서 나온다. 이것이 PAC learning의 수학적 기초다.
• McD