[CS229M] Concentration Inequalities - Part II

Sung Jae Hyuk·2023년 9월 12일
CS229MConcentartion inequalityHoeffding's InequalityMLMcDiarmid’s inequalitySub-gaussianmachine learningstatistic
1

CS229

목록 보기
3/3

Part I에 이어, 추가적으로 Concentration Inequality에 대해서 이야기해봅시다.

(Cont'd) Sub-gaussian

Review

가볍게 sub-gaussian이 무엇인지에 대한 정의부터 다시 언급해보죠
sub-gaussian Random Variable이 무엇인지를 정의하는 방법은 22가지 존재합니다.
첫 번째는 MGF의 관점에서 보는 것이고, 두 번째는 Tail Bound에 대해서 보는것이죠

Defintion I (Momentum Generating Function)

XX를 μ:=E[X]<∞\mu:=\mathbb{E}[X]<\infty인 Random Variable라고 합시다. 이때, 다음 성질을 만족하는 XX를 variance proxyvariance~proxy가 σ2\sigma^2인 sub-gaussian이라고 합니다.

∀ λ∈R : E[eλ(X−μ)]≤eλ2σ2/2\forall\:\lambda\in \R \::\:\mathbb{E}[e^{\lambda (X-\mu)}]\leq e^{\lambda^2 \sigma^2/2}

Definition II (Tail-bound)

위와 동일한 셋팅으로 갑시다. 즉, XX는 μ<∞\mu<\infty를 가지는 Random Variable입니다. 이때, 다음 성질을 만족하는 XX를 variance proxyvariance~proxy가 σ2\sigma^2인 sub-gaussian이라고 합니다.

∀t∈R : Pr⁡[∣X−μ∣≥t]≤2exp⁡(−t22σ2)\forall t\in\R\::\:\Pr[|X-\mu|\geq t]\leq 2\exp\left(-\dfrac{t^2}{2\sigma^2}\right)

Example 1 (Rademacher R.V)

Rademacher이란 50%50\%의 확률로 ±1\pm 1을 취하는 Random Variable을 의미합니다.
즉, Rademacher R.V. XX의 support는 {−1, 1}\{-1,\:1\}이고, 각각의 확률은 1/21/2가 됩니다.
현재 보일 것은 이 XX가 variance proxy가 11인, 즉 11-sub-gaussian인 R.V.임을 보일 예정입니다.
확률이 1/21/2로 같으므로 각각에 대해 Taylor's series 전개를 생각하면 쉽게 보일 수 있습니다.

E[exp⁡(λX)]=12{exp⁡(−λ)+exp⁡(λ)}=12{∑k=0∞(−λ)kk!+∑k=0∞(λ)kk!}=12×2×∑k=0∞λ2k(2k)!=∑k=0∞λ2k(2k)!≤1+∑k=0∞(λ2)k2k⋅k!=exp⁡(λ2/2)\begin{aligned}\mathbb{E}[\exp(\lambda X)]&=\dfrac{1}{2}\{\exp(-\lambda)+\exp(\lambda)\}\\ &= \dfrac{1}{2}\left\{\displaystyle\sum_{k=0}^\infty \dfrac{(-\lambda)^k}{k!}+\sum_{k=0}^\infty \dfrac{(\lambda)^k}{k!}\right\}\\ &=\dfrac{1}{2}\times 2 \times\sum_{k=0}^\infty \dfrac{\lambda^{2k}}{(2k)!}\\&=\sum_{k=0}^\infty \dfrac{\lambda ^{2k}}{(2k)!}\\&\leq 1+\sum_{k=0}^\infty \dfrac{(\lambda^2)^k}{2^k \cdot k!}=\exp(\lambda^2/2)\end{aligned}

이는, σ2=1\sigma^2=1인 상황과 동일하므로 XX는 11-sub-Gaussian임을 알 수 있습니다.

Example 2 (Bounded R.V.)

뒤에 나올 McDiarmid's inequality를 위해 증명해야하는 성질 중 하나로는 Bounded하는 Random Variable은 (b−a)24\dfrac{(b-a)^2}{4}를 Variance Proxy로 가지는 sub-gaussian 입니다.
조금 더 statement를 다듬고, 증명을 알아봅시다.

Theorem

기댓값이 μ=E[X]\mu=\mathbb{E}[X]인 Random Variable XX를 생각하고, 이가 [a, b][a,\:b]에서 almost surely하다고 합시다.
즉, Almost surely하게 a≤X≤ba\leq X \leq b입니다.
이때, XX는 Variance proxy가 (b−a)2/4(b-a)^2/4인 Sub-gaussian입니다. 즉 임의의 실수 λ∈R\lambda \in\R에 대해

E[eλ(X−E[X])]≤exp⁡[λ2(b−a)28]\mathbb{E}\left[e^{\lambda(X-\mathbb{E}[X])}\right]\leq\exp\left[\dfrac{\lambda^2(b-a)^2}{8}\right]

Analysis

sub-gaussian의 정의 중 Tail-bound를 이용한 것을 보면, 저기에서 부등호를 적절히 바꿔주고 독립적인 R.V.를 모두 들고와서 긁으면 저 꼴은 이전에 소개한 Hoeffding's inequality와 아주 비슷한 꼴이 됩니다.
이때, Bounded R.V.에 대해 Theorem을 증명하게 되면, 이와 이전에 소개했던 독립적인 sub-gaussian의 합은 다시 sub-gaussian이 됨을 이용하여 Hoeffiding's inequality를 증명할 수 있습니다.

Cumulent Generating Function

본격적인 증명에 들어가기 앞서 Cumulent Generating function에 대해 알아봅시다.
MGF에서 가장 아쉬운 점이라고 하면, R.V. XX의 MGF MX(t)M_X(t)의 second derivation은 second momentum을 제공하기 때문에 Variance를 계산하기 위해서는 추가적인 연산이 들어간다는 점입니다.
즉, d2dt2MX(t)=E[X2]\dfrac{d^2}{dt^2}M_X(t)=\mathbb{E}[X^2]이 되므로 분산을 계산하기 위해서는 한번 미분해서 00을 대입한 값이 추가로 필요하게 됩니다.
그러면 두번 미분해서 00을 넣었을 때 바로 분산에 대한 정보를 제공하는 Generating function은 없을까요?
이가 바로 Cumulent Generating Function이고, MGF에 ln을 씌운 꼴로 정의합니다.
즉, cumulnet generating function K(t)K(t)는

K(t)=log⁡E[etX]=log⁡[MX(t)]K(t)=\log \mathbb{E}[e^{tX}]=\log [M_X(t)]

로 정의합니다.
이때,

K′(0)=1MX(0)×ddtMX(t)∣t=0=E[X]MX(0)=E[X]K′′(0)=ddt[K′(t)]∣t=0=ddt(1MX(t)⋅dMX(t)dt)∣t=0=−1[MX(t)]2×(dMX(t)dt)2+1MX(t)d2MX(t)dt2∣t=0=E[X2]−(E[X])2=Var[X]\begin{aligned}K'(0)&=\dfrac{1}{M_X(0)}\times\left.\dfrac{d}{dt}M_X(t)\right\vert_{t=0}\\ &=\dfrac{\mathbb{E}[X]}{M_X(0)}=\mathbb{E}[X]\\ K''(0)&=\left.\dfrac{d}{dt}[K'(t)]\right\vert_{t=0}\\ &=\dfrac{d}{dt}\left.\left(\dfrac{1}{M_X(t)}\cdot\dfrac{dM_X(t)}{dt}\right)\right\vert_{t=0} \\&=\left.-\dfrac{1}{[M_X(t)]^2}\times\left(\dfrac{dM_X(t)}{dt}\right)^2+\dfrac{1}{M_X(t)}\dfrac{d^2M_X(t)}{dt^2}\right\vert_{t=0}\\&=\mathbb{E}[X^2]-(\mathbb{E}[X])^2=Var[X]\end{aligned}

더 자세하게, K′′(t)K''(t)에 대해 탐구하면

K′′(t)=ddt[K′(t)]=ddt(1MX(t)⋅dMX(t)dt)=−1[MX(t)]2×(dMX(t)dt)2+1MX(t)d2MX(t)dt2\begin{aligned}K''(t)&=\dfrac{d}{dt}[K'(t)]\\ &=\dfrac{d}{dt}\left(\dfrac{1}{M_X(t)}\cdot\dfrac{dM_X(t)}{dt}\right) \\&=-\dfrac{1}{[M_X(t)]^2}\times\left(\dfrac{dM_X(t)}{dt}\right)^2+\dfrac{1}{M_X(t)}\dfrac{d^2M_X(t)}{dt^2} \end{aligned}

Lemma

XX가 bounded되는 R.V.라고 합시다. 즉, almost surely하게 Y∈[a, b]Y\in[a,\:b]입니다. 이때, Var(Y)≤(b−a)24\text{Var}(Y)\leq \dfrac{(b-a)^2}{4}가 성립합니다.

Proof (Lemma)

Var(Y)\text{Var}(Y)는 E[Y2]−(E[Y])2\mathbb{E}[Y^2]-(\mathbb{E}[Y])^2 외에도 kk에 대한 함수 E[(Y−k)2]\mathbb{E}[(Y-k)^2]의 최솟값이기도 합니다. 따라서,

Var(Y)=min⁡k∈RE[(Y−k)2]≤E[(Y−a+b2)2]≤E[(b−a+b2)2]=(b−a)24\begin{aligned} \text{Var}(Y) &=\min_{k\in \R} \mathbb{E}[(Y-k)^2]\\ &\leq \mathbb{E}\left[\left(Y-\dfrac{a+b}{2}\right)^2\right]\\ &\leq \mathbb{E}\left[\left(b-\dfrac{a+b}{2}\right)^2\right]=\dfrac{(b-a)^2}{4} \end{aligned}

Proof (Theorem)

XX가 Bounded R.V. 이므로 X−E[X]X-\mathbb{E}[X] 도 동일하게 bounded되는 R.V이고, 이의 범위는 a−E[X]≤X−E[X]≤b−E[X]a-\mathbb{E}[X]\leq X-\mathbb{E}[X] \leq b-\mathbb{E}[X]입니다.
편의를 위해 Y=X−E[X]Y=X-\mathbb{E}[X]라 하면 E[Y]=E[X−E[X]]=0\mathbb{E}[Y] = \mathbb{E}[X-\mathbb{E}[X]]=0입니다.
ϕ : λ↦log⁡(E[exp⁡(λY)])\phi\::\:\lambda\mapsto\log(\mathbb{E}[\exp(\lambda Y)])를 생각합시다.
위의 CGF에서 ϕ(0)=0\phi(0)=0이고 ϕ′(0)=E[Y]=0\phi'(0)=\mathbb{E}[Y]=0이 됩니다.
또한, R.V. YY의 Probability distribution을 PP라 하고, f:=eλyEP[eλY]f:=\dfrac{e^{\lambda y}}{\mathbb{E}_P [{e^{\lambda Y}]}}라 하면 EY[f]=1E_Y[f]=1이 ff가 almost surely한 R.V.가 되므로 measure를 바꿔서

Qλ(y):=∫RfdP(y)Q_{\lambda}(y) :=\int_{\R}fdP(y)

로 정의를 하면, QλQ_\lambda 역시 YY의 Probability distriubtion이 되고 dQλ(y)=fdP(y)dQ_{\lambda} (y) = fdP(y)가 성립합니다.
또한

Ey∼Qλ[Y]=∫[a, b]y dQλ(y)=∫[a, b]fy dP(y)=∫[a, b]yeλyEP[eλY]dP(y)=EP[YeλY]EP[eλY]=ϕ′(λ)Vary∼Qλ[Y]=Ey∼QY[Y2]−(Ey∼QY[Y])2=EP[Y2eλY]EP[eλY]−EP[YeλY]2EP[eλY]2=ϕ′′(λ)\begin{aligned} \mathbb{E}_{y\sim Q_{\lambda}}[Y]&=\int_{[a,\:b]} y\:dQ_{\lambda}(y)\\ &=\int_{[a,\:b]} fy\:dP(y)\\&=\int_{[a,\:b]} \dfrac{ye^{\lambda y}}{\mathbb{E}_P[e^{\lambda Y}]} dP(y)\\ &=\dfrac{\mathbb{E}_P[Ye^{\lambda Y}]}{\mathbb{E}_P[e^{\lambda Y}]}=\phi'(\lambda)\\ \text{Var}_{y\sim Q_{\lambda}}[Y]&=\mathbb{E}_{y\sim Q_Y}[Y^2]-(\mathbb{E}_{y\sim Q_Y}[Y])^2\\&=\dfrac{\mathbb{E}_P[Y^2e^{\lambda Y}]}{\mathbb{E}_P[e^{\lambda Y}]}-\dfrac{\mathbb{E}_P[Y e^{\lambda Y}]^2}{\mathbb{E}_P[e^{\lambda Y}]^2}\\ &=\phi''(\lambda) \end{aligned}

마지막 줄은 MY(λ)=E[etY]M_Y(\lambda)=\mathbb{E}[e^{tY}]이므로 이를 대입하면 K′′(t)K''(t)를 정리해놓은 식에 의해 성립합니다.
이때, λ>0\lambda>0에 대해 ϕ\phi에 대해 Taylor's theorem을 사용하면

ϕ(λ)=ϕ(0)+λϕ′(0)+λ22ϕ′′(ε)=λ22ϕ′′(ε)≤λ22(b−a)24=λ2(b−a)28\begin{aligned} \phi(\lambda)&=\phi(0)+\lambda\phi'(0)+\dfrac{\lambda^2}{2}\phi''(\varepsilon)\\ &=\dfrac{\lambda^2}{2}\phi''(\varepsilon)\\ &\leq \dfrac{\lambda^2}{2}\dfrac{(b-a)^2}{4} = \dfrac{\lambda ^2 (b-a)^2}{8} \end{aligned}

ϕ(λ)=log⁡(E[exp⁡(λY)]]≤λ2(b−a)28\phi(\lambda)=\log(\mathbb{E}[\exp(\lambda Y)]]\leq\dfrac{\lambda^2 (b-a)^2}{8}이므로

E[exp⁡(λY)]≤exp⁡(λ2(b−a)28)\mathbb{E}[\exp(\lambda Y)]\leq\exp\left(\dfrac{\lambda ^2 (b-a)^2}{8}\right)

이 성립하고, λ<0\lambda<0에 대해서는 대칭적으로 사용하면 증명이 마무리됩니다.

Why subgaussian is important?

  1. Sub-gaussian의 정의는 Concentration Inequaility와 굉장히 밀접한 관련이 있습니다.
  • 특히, Bounded R.V.에서 사용할 수 있는 Hoeffiding's inequality와 굉장히 닮아있는 걸 볼 수가 있습니다.
  • 하나의 R.V.에 대해 분석하는 것은 쉽지만, 그것들의 합에 대해 다루는 건 굉장히 어렵습니다. 독립성이 보장이 된다고 하여도 합이 정해져있다고 해서 각각의 R.V.에 대한 값들이 정해지는 것은 아니기 때문이죠
  • 이때 Sub-gaussian 성질을 이용하면 그 합에 대한 Tail bound를 보장해줄 수 있다는 것이기도 하고, 자체로도 sub-gaussian을 유지하는 것 자체로도 굉장히 강력합니다.
  1. 적용할 수 있는 R.V.의 범위가 굉장히 넓습니다.
  • 가장 많이 나오는 Gaussian, 그리고 베르누이 분포, loss function의 범위를 제한 시켰다고 가정하면 Bounded되는 R.V.에 대해서도 항상 sub-gaussian이 적용이 됩니다.
  • 그러면서도 강력한 성질을 가지고 있기 때문에, application의 범위가 굉장히 넓습니다.

Functions of Random Variable

Motivation

우리가 일반적으로 가지고 있는 것은 데이터셋, 즉 D={(xi, yi)}i=1n\mathcal D=\{(x_i,\:y_i)\}_{i=1}^n 뿐입니다. 하지만, 실제로 우리가 처리해야하는 것은 sampling한 Dataset이 아니라 그것으로부터 결과를 얻은 f(X1, X2, ⋯ , XN)f(X_1,\:X_2,\:\cdots,\:X_N)에 대해서 알아봐야한다는 것이죠.
이때, 만약 Sampling한 R.V.가 Bounded하게 되면 이를 어느정도 보장해줄 수 있습니다! 이가 바로 McDiarmid's inequality입니다.

Theorem (Mcdiarmid's inequality)

함수 f : Rn→Rf\::\:\R^n\rightarrow\R가 독립적인 R.V.로 부터 sampling한 데이터들을에 대해 하나하나씩 바꾸어도 값의 차이가 Bounded된다고 가정합시다. Formally하게,

∣f(x1, x2, ⋯ , xn)−f(x1, x2, ⋯ , xi′, xi+1, ⋯ , xn)∣≤ci|f(x_1,\:x_2,\:\cdots,\:x_n)-f(x_1,\:x_2,\:\cdots,\:x_i',\:x_{i+1},\:\cdots,\:x_n)|\leq c_i

즉, 어느 하나의 변수를 바꾸어도 함수 ff의 값의 차이는 크게 나지 않는다라는 것을 의미합니다. ff는 변수 하나가 바뀐다고 해서 크게 영향을 받지 않는 것이죠.
이때, 다음의 Concentration inequality가 성립합니다.

Pr⁡[f(X1, ⋯ , Xn)−E[f(X1, ⋯ , Xn)]≥t]≤exp⁡(−2t2∑i=1nci2)\Pr[f(X_1,\:\cdots,\:X_n)-\mathbb{E}[f(X_1,\:\cdots,\:X_n)]\geq t]\leq \exp\left(-\dfrac{2t^2}{\sum_{i=1}^n c_i^2}\right)

i.e.i.e., f(X1, X2, ⋯ , Xn)f(X_1,\:X_2,\:\cdots,\:X_n)은 O(∑i=1nci2)O\left(\sqrt{\displaystyle\sum_{i=1}^n c_i^2}\right)-sub-gaussian입니다.

Analysis

오직 하나의 변수에 대해서 어떤 함수가 non-sensitive함을 보이게 되면, 그 함수의 전체에 대한 Tail-bound를 보장해주는 아주 강력한 정리입니다.
이때, 만약 ff를 ∑i=1nxi2\sum_{i=1}^n x_i^2으로 정의하게 되면, 이는 Hoeffiding's inequality와 동일하게 됩니다.

Proof

Part I

먼저, 함수 ff에 대해서 저희가 가지고 있는 정보는 오직 하나의 변수에 대한 것뿐입니다. 허나, McDiamird's inequality에서는 전체에 대해서 다룰 필요가 있죠. 그렇기 때문에, 전체를 하나하나씩에 대해 쪼개줄 필요가 있습니다.
기본적인 아이디어는 Conditional Expectation입니다. E[E[X∣Y]]=E[X]\mathbb E[\mathbb{E}[X|Y]] = \mathbb E[X]에서 우변은 모르겠지만 좌변 같은 경우 저 식은 YY에 대한 함수가 되죠.
이렇게 하나하나씩 쪼개다보면, 결국은 전체에 대해 구성할 수 있습니다.
먼저 위의 방식대로 R.V.들을 정의합시다.

Z0=E[f(X1, ⋯ , Xn)](this is constant value)Z1=E[f(X1, ⋯ , Xn)∣X1](a funtion of X1)⋮Zi=E[f(X1, ⋯ , Xn)∣X1, ⋯ , Xi](a function of X1, ⋯ , Xi)Zn=f(X1, X2, ⋯ , Xn)\begin{aligned} Z_0&=\mathbb{E}[f(X_1,\:\cdots,\:X_n)]&&&&(\text{this is constant value})\\ Z_1&=\mathbb{E}[f(X_1,\:\cdots,\:X_n)|{\color{red}{X_1}}]&&&&(\text{a funtion of } X_1)\\ \vdots\\ Z_i&=\mathbb{E}[f(X_1,\:\cdots,\:X_n)|{\color{red}{X_1,\:\cdots,\:X_i}}]&&&& (\text{a function of }X_1,\:\cdots,\:X_i)\\ Z_n&=f(X_1,\:X_2,\:\cdots,\:X_n) \end{aligned}

또한, Law of total expectation에 의해

∀i≤n : E[Zi]=E[E[f(X1, ⋯ , Xn)∣X1, X2, ⋯ , Xi]=f(X1, X2, ⋯ , Xn)\forall i\leq n\::\:\mathbb{E}[Z_i]=\mathbb{E}[\mathbb{E}[f(X_1,\:\cdots,\:X_n)|X_1,\:X_2,\:\cdots,\:X_i]=f(X_1,\:X_2,\:\cdots,\:X_n)

Part II

따라서 Di=Zi−Zi−1D_i=Z_i-Z_{i-1}이라 정의하면 E[Di]=E[Zi]−E[Zi−1]=0\mathbb{E}[D_i]=\mathbb{E}[Z_i]-\mathbb{E}[Z_{i-1}]=0입니다.
또한, 초기의 확률 식은

Pr⁡[Zn−Z0≥t]≤exp⁡(−2t2∑i=1nci2)\Pr[Z_n-Z_0\geq t]\leq\exp\left(-\dfrac{2t^2}{\sum_{i=1}^n c_i^2}\right)

으로 바뀌게 됐습니다.
그러면, 이제 어찌 Zn−Z0Z_n-Z_0을 처리해야할까요?
Assumption에서는 하나에 대한 값의 변화입니다. 또한, ZiZ_i와 Zi−1Z_{i-1}을 보면, 각각 ii개에 대한 함수와 i−1i-1개에 대한 함수죠. 그러면, Conditional Expectation을 이용하여 Zi−Zi−1Z_i-Z_{i-1}을 Expectation에 대해 쓰고, ZiZ_i에서 추가된 항목에 대한 함수로 새롭게 정의하면 우리가 원하는 형태를 만들 수 있을 것 같군요!
그러면, 하나에 대한 차이로 Zn−Z0Z_n-Z_0을 만들 수 있을까요? 정답은 yes입니다. Telescoping 기법을 활용하면

Zn−Z0=∑i=1n(Zi−Zi−1)=∑i=1nDiZ_n-Z_0=\sum_{i=1}^n (Z_i-Z_{i-1})=\sum_{i=1}^n D_i

이제 DiD_i에 대해 관점을 바꿔보죠

Part III

Ai=inf⁡xE[f(X1, X2, ⋯ , Xn)∣X1, ⋯ , Xi−1, Xi=x]−E[f(X1, X2, ⋯ , Xn)∣X1, ⋯ , Xi−1]Bi=sup⁡xE[f(X1, X2, ⋯ , Xn)∣X1, ⋯ , Xi−1, Xi=x]−E[f(X1, X2, ⋯ , Xn)∣X1, ⋯ , Xi−1]\begin{aligned} A_i&=\inf_{x} \mathbb{E}[f(X_1,\:X_2,\:\cdots,\:X_n)|X_1,\:\cdots,\:X_{i-1},\:{\color{red}X_i=x}]-\mathbb{E}[f(X_1,\:X_2,\:\cdots,\:X_n)|X_1,\:\cdots,\:X_{i-1}]\\ B_i&=\sup_{x} \mathbb{E}[f(X_1,\:X_2,\:\cdots,\:X_n)|X_1,\:\cdots,\:X_{i-1},\:{\color{red}X_i=x}]-\mathbb{E}[f(X_1,\:X_2,\:\cdots,\:X_n)|X_1,\:\cdots,\:X_{i-1}] \end{aligned}

라 하면, 임의의 R.V.에 대해 어떤 값이 배정이 되더라도 Ai≤Di≤BiA_i \leq D_i\leq B_i가 됩니다.
또한, 각각의 sampling한 값은 전부 독립이므로 따로 생각하면,

Bi−Ai≤sup⁡x1,x2,⋯ , xi−1sup⁡xi,xi′∫(f(x1, x2, ⋯ ,xi, ⋯ , xn)−f(x1, x2, ⋯ , xi′, ⋯ , xn)) dP(xi+1, ⋯ , xn)≤ci (∵ Only one change of variable is non-sensitive on f)\begin{aligned} B_i-A_i&\leq\sup_{x_1,x_2,\cdots,\:x_{i-1}}\sup_{x_i, x_i'}\int (f(x_1,\:x_2,\:\cdots,x_i,\:\cdots,\:x_n)-f(x_1,\:x_2,\:\cdots,\:x_i',\:\cdots,\: x_n)) \,dP(x_{i+1},\:\cdots,\:x_n)\\ &\leq c_i ~(\because~\text{Only one change of variable is non-sensitive on }f) \end{aligned}

즉, DiD_i는 Bounded한 R.V.이며, Bi−AiB_i-A_i는 cic_i보다 작습니다.

Part IV

마지막입니다. Part III을 이용하여 원하는 바를 증명해봅시다.
위의 정리를 증명하기 위해서 Zn−Z0Z_n-Z_0이 O(∑i=1nci2)O\left(\sqrt{\displaystyle\sum_{i=1}^n c_i^2}\right)-sub-gaussian임을 보여줘도 충분합니다.

E[eλ(Zn−Z0)]=E[eλ∑i=1n(Zi−Zi−1)]=E[E[eλ(Zn−Zn−1)|X1, X2, ⋯ , Xn−1]eλ∑i=1n−1(Zi−Zi−1)]≤eλ2cn2/8×E[eλ∑i=1n−1(Zi−Zi−1)] (∵ Bounded R.V. is sub-gaussian)       ⋮≤eλ2(∑i=1nci2)/8\begin{aligned} \mathbb{E}[e^{\lambda (Z_n-Z_0)}]&=\mathbb{E}[e^{\lambda \sum_{i=1}^n (Z_i-Z_{i-1})}]\\ &=\mathbb{E}\left[\mathbb{E}\left[e^{\lambda (Z_n-Z_{n-1})}\middle \vert X_1,\:X_2,\:\cdots,\:X_{n-1}\right]e^{\lambda \sum_{i=1}^{n-1} (Z_i-Z_{i-1})}\right]\\ &\leq e^{\lambda^2 c_n^2/8}\times \mathbb{E}\left[e^{\lambda\sum_{i=1}^{n-1} (Z_i-Z_{i-1})}\right]~(\because~\text{Bounded R.V. is sub-gaussian})\\ &~~~~~~~\vdots\\ &\leq e^{\lambda ^2 (\sum_{i=1}^n c_i^2)/8} \end{aligned}

Next Posting

  • Generalization Bound on Finite Hypothesis Case
  • Generalization Bound on infinite Hypothesis Case
  • Rademacher Complexity
profile
Sung Jae Hyuk
Hello World!
이전 포스트

[CS229M] Concentration Inequalities - Part I

0개의 댓글

관련 채용 정보