KL divergenceを使ったchernoff boundの証明

概要. Chernoff boundとは独立な確率変数の和の集中性を意味する不等式であり, moment generating functionを抑える方法などによって証明される. ここでは情報理論の道具(KL divergence)を使ってChernoff boundを証明する方法を知ったのでまとめました.

所感ですが, KL divergenceについては自分で定義に則って色々と手計算しまくってchain ruleなどが成り立つことを確認していけば, 慣れてくるものだと思います.

Preliminary

二つの確率変数$X,Y$に対し, それらのKL divergence $D(X||Y)$を
\begin{align*}
D(X||Y) = \sum_a \Pr[X=a]\log\frac{\Pr[X=a]}{\Pr[Y=a]}
\end{align*}
で定義します. ここで総和は$\Pr[X=a]>0$を満たす全ての$a$について動きます. このような$a$の集合を$X$の台(support)と呼び, $\mathsf{supp}(X)$と書きます. また, 確率変数と分布をしばし同一視した記述をします. すなわち, 二つの分布$\mu,\nu$に対してそのKL divergence $D(\mu||\nu)$も考えます.

また, 二つのベルヌーイ試行$\mathrm{Ber}(p),\mathrm{Ber}(q)$に対し, そのKL divergenceを$\delta(p||q)$とします. すなわち
\begin{align*}
\delta(p||q) = D(\mathrm{Ber}(p)||\mathrm{Ber}(q)) = p\log\frac{p}{q} + (1-p)\log\frac{1-p}{1-q}.
\end{align*}

次に, 条件つきKL divergenceを定義します.

定義 (条件つきKL divergence).
二つの確率変数の組$(X_1,X_2),(Y_1,Y_2)$に対し, 条件つきKL divergence $D(Y_1|Y_2 || X_1|X_2)$を以下で定める:
\begin{align*}
D(Y_1|Y_2 || X_1|X_2) &= \mathbb{E}_{y\sim Y_2}\left[ D(Y_1|_{Y_2=y} \,||\, X_1|_{X_2=y})\right] \\
&= \sum_{y_2\in\mathsf{supp}(Y_2)}\Pr[Y_2=y_2]\cdot \sum_{y_1\in\mathsf{supp}(Y_1)}\Pr[Y_1=y_1|Y_2=y_2]\log\frac{\Pr[Y_1=y_1|Y_2=y_2]}{\Pr[X_1=y_1|X_2=y_2]}
\end{align*}

KL divergenceに関する以下の基本的な事実を使います. これらは計算で確認できます:

1. 凸性: $D(\cdot||\cdot)$を分布の組$\to$実数値の関数とみなし, 分布をベクトルとみなしたとき, 凸性を持つ.

2. Chain rule: $D((Y_1,Y_2)||(X_1,X_2)) = D(Y_1|Y_2\,||\,X_1|X_2) + D(Y_2||X_2)$.

3. $X_1,X_2$が独立ならば, $D(Y_1|Y_2\,||\,X_1|X_2)\geq D(Y_1||X_1)$.

性質3の証明:
$D(\cdot||\cdot)$の凸性より,
\begin{align*}
D(Y_1|Y_2\,||\,X_1|X_2) &= \mathbb{E}_{y_2\sim Y_2}\left[ D\left(Y_1|_{Y_2=y}\,||\,X_1|_{X_2=y}\right) \right] \\
&\geq D\left(Y_1|_{Y_2}\,||\,X_2|_{Y_2}\right) & & \text{convexity and Jensen} \\
&= D(Y_1||X_2) & & \text{$X_1,X_2$ are independent}.
\end{align*}

定理 (Chernoff bound).
$X_1,\dots,X_n$を$\{0,1\}$値をとる独立な確率変数とし, $\mu=\frac{1}{n}\sum_{i=1}^n\mathbb{E}[X_i]$とする. このとき, 任意の$t>0$に対して
\begin{align*}
& \Pr\left[\frac{1}{n}\sum_{i=1}^n X_i \leq \mu - t\right] \leq \exp\left(-n\delta(\mu-t||\mu)\right), \\
& \Pr\left[\frac{1}{n}\sum_{i=1}^n X_i \geq \mu + t\right] \leq \exp\left(-n\delta(\mu+t||\mu)\right).
\end{align*}

証明

まず, 以下の事実を使います:
$X$を確率変数, $E$を$X$の事象とする. $Y=X|_E$を, $E$の発生で条件つけたときの$X$とする (つまり, 任意の$a\in E$に対して$\Pr[Y=a]=\Pr[X=a|E]$). このとき
\[
\log\frac{1}{\Pr[E]} = D(Y||X).
\]
これは簡単な計算で確認できます. 実際,
\begin{align*}
D(Y||X) &= \sum_{a\in E}\Pr[X=a|E]\log\frac{\Pr[X=a|E]}{\Pr[X=a]} \\
&= \sum_{a\in E}\Pr[X=a|E]\log\frac{\Pr[E|X=a]}{\Pr[E]} \\
&= \log\frac{1}{\Pr[E]}\sum_{a\in E}\Pr[X=a|E] & & \Pr[X=a|E]=1\text{ for }a\in E \\
&= \log\frac{1}{\Pr[E]}.
\end{align*}

では, Chernoff boundの証明に戻ります. 確率変数$X=(X_1,\dots,X_n)$に対して事象$E$を$E=\left\{\frac{1}{n}\sum_{i=1}^n X_i \geq \mu+t\right\}$とし, $Y=X|_E$とします. $X',Y'$を, 一様ランダムに選ばれた$i\sim[n]$に対し$X'=X_i$, $Y'=Y_i$と定義される確率変数とします. すると
\begin{align*}
\log\frac{1}{\Pr[E]} &= D(Y||X) \\
&= \sum_{i=1}^n D(Y^{\leq i}|Y^{\leq i-1}||X^{\leq i}|X^{\leq i-1}) & & \text{chain rule} \\
&= \sum_{i=1}^n D(Y_i|Y^{\leq i-1}||X_i|X^{\leq i-1}) \\
&\geq \sum_{i=1}^n D(Y_i||X_i) & & \text{$X_i$s are indepenent} \\
&= n\mathbb{E}_{i\sim[n]}\left[ D(Y_i||X_i)\right] \\
&\geq n D(Y'||X') & & \text{convexity of KL divergence and Jensen's inequality}.
\end{align*}

ここで, $D(Y'||X')$を計算してみます. どちらも$\{0,1\}$値確率変数であり, $X=(X_1,\dots,X_n)$で条件つけたときは$\Pr[X'=1]=\frac{1}\sum_{i=1}^n X_i$となるので, $\Pr[X'=1]=\mu$です. 一方で$Y=X|_E$なので, $E$の定義から$\Pr[Y'=1]\geq\mu+t$を得ます. 従って, $D(Y'||X')\geq \delta(\mu+t||\mu)$となり, upper tailを得ます.

lower tailも同様に示すことができます.　(証明終)

注釈1 ($\delta(p||q)$のバウンド).
Pinskerの不等式を用いると, $d_{\mathrm{tv}}(\mathrm{Ber}(p),\mathrm{Ber}(q))=|p-q|\leq \sqrt{\frac{\delta(p||q)}{2}}$を得ます. これをChernoff boundに代入するとHoeffding boundを得ます.

注釈2 ($[0,1]$値への拡張.)
証明では$D(Y'||X')$の下界を得るために$X$が$\{0,1\}$値をとることを利用しましたが, data processing 不等式などを使うと簡単に$[0,1]$値確率変数の集中不等式を得ることができます (詳細は省略).