Hoeffding/Bennett/Bernsteinの不等式 - ややプログラム紀行

最近concentration inequalitiesを読み進めていて、今は8章まで読んだところなのだけど、一旦学んだことを整理したくなってきたのでまずは序盤の内容をまとめてみる

Hoeffding/Bennett/Bernsteinの不等式はどれも独立な確率変数の和に関する、古典的な集中不等式というもので、その証明も大体同じような道筋を辿ることになる

Markovの不等式

まず初めに、ほとんどの集中不等式はMarkovの不等式というものが出発地点になる

非負な確率変数 $Y$ と任意の $t > 0$ に対して、
$\displaystyle \mathbb{P}[Y \geq t] \leq \frac{\mathbb{E}[Y]}{t}$

証明は、 $Y1_{Y \geq t} \geq t1_{Y \geq t}$ の両辺を期待値とってから $t$ で割り、 $\mathbb{E}[Y 1_{Y \geq t}] \leq \mathbb{E}[Y]$ であることに気をつければ良い*1

Markovの不等式は、特に $Y = e^{\lambda Z}$ ( $\lambda > 0$ )を代入した時が有用で、これによって非負に限らず任意の確率変数 $Z$ に対して

$\displaystyle \mathbb{P}[Z \geq t] = \mathbb{P}[e^{\lambda Z} \geq e^{\lambda t}] \leq \frac{\mathbb{E}[e^{\lambda Z}]}{e^{\lambda t}}$

となり、右辺にモーメント母関数 $\mathbb{E}[e^{\lambda Z}]$ が出てくる形となる

この不等式は非負でない確率変数を扱えるという点も良いのだが、 $Z$ が独立な確率変数の和で表されるときに真価を発揮する

すなわち、 $Z$ が独立な確率変数 $X_1,\dots,X_n$ を用いて $Z = X_1 + \cdots + X_n$ と表される時、 $e^{X_1},\dots,e^{X_n}$ も独立であることに注目すると

$\displaystyle \mathbb{E}[e^{\lambda Z}] = \mathbb{E}[e^{\lambda \sum_{I=1}^n X_i}] = \prod_{I=1}^n \mathbb{E}[e^{\lambda X_i}]$

となり、 $Z$ のモーメント母関数が $X_1,\dots,X_n$ のモーメント母関数の積で表されることになる

よって、 $P[X_1 + \cdots + X_n > t]$ の挙動を解析するためには、各々の確率変数のモーメント母関数さえ分かれば良い

Hoeffdingの不等式

Hoeffdingの不等式は独立かつ有界な確率変数の和に関する集中不等式であり、具体的には次のようなもの:

$X_1,\dots,X_n$ は独立な確率変数であり、かつ各 $i = 1,\dots,n$ について $X_i$ は区間 $[a_i, b_i] \subset \mathbb{R}$ に値を取るものとする
この時、 $S = \sum_{i = 1}^n (X_i - \mathbb{E}[X_i])$ とすれば、任意の $t > 0$ について
$\displaystyle \mathbb{P}[ S \geq t] \leq \exp\left( - \frac{2t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)$

上で述べたように、この不等式を示すためには $X_1,\dots,X_n$ のモーメント母関数を解析すればよく、これにはHoeffdingの補題というものが存在する:

確率変数 $Y$ が $\mathbb{E}[Y] = 0$ かつ有界な区間 $[a,b] \subset \mathbb{R}$ 上に値をとるとき、
$\displaystyle \psi_Y(\lambda) := \log \mathbb{E}[e^{\lambda Y}] \leq \frac{\lambda^2 (b-a)^2}{8}$

有界な区間に値をとるという仮定のみで対数モーメント母関数の挙動がわかるのは面白いが、どう証明すれば良いか中々難しそう

鍵になるポイントは、有界な区間に値をとる確率変数は分散も有界であるという点: より詳細には、 $|Y - (b+a)/2| \leq (b-a)/2$ であることから

$\displaystyle Var[Y] = Var[ Y - (b+a)/2 ] \leq \mathbb{E}[|Y - (b+a)/2|^2] \leq \frac{(b-a)^2}{4}$

となることがわかる

分散が上から抑えられるということは、モーメント母関数の2次の項を抑えられるということになるので、なんだか証明できそうな気もしてくる

Hoeffdingの補題の証明は次のような感じになる: テイラーの定理より、 $\theta \in [0, \lambda]$ が存在して

$\displaystyle \psi_Y(\lambda) = \psi_Y(0) + \lambda \psi'_Y(0) + \frac{\lambda^2}{2}\psi''_Y(\theta)$

となるが、 $\psi_Y(0) = \psi'_Y(0) = 0$ であることから $\psi''_Y(\theta)$ のみを考えれば良い

具体的に $\psi''_Y(\theta)$ を計算してみると

$\displaystyle \psi''_Y(\theta) = e^{-\psi_Y(\theta)} \mathbb{E}[Y^2e^{\theta Y}] - e^{-2\psi_Y(\theta)}\left( \mathbb{E}[Ye^{\theta Y}] \right)^2$

であるが、これは $\frac{d Z}{d Y}(x) = e^{-\psi_Y(\theta)}e^{\theta x}$ である確率変数 $Z$ の分散に等しい

このようにして定義された確率変数 $Z$ は $Y$ 同様に区間 $[a, b]$ 上に値をとる確率変数であるから、上の議論からその分散は $\frac{(b-a)^2}{4}$ で抑えられ、無事 $\psi_Y(\lambda) = \frac{\lambda^2}{2}\psi''_Y(\theta) \leq \frac{\lambda^2(b-a)^2}{8}$ が示された

さて、Markovの不等式とHoeffdingの補題を合わせることで

$\displaystyle \mathbb{P}[S \geq t] \leq \exp\left( \sum_{i=1}^n \log \mathbb{E}[ e^{\lambda X_i} ] - \lambda t\right) \leq \exp\left( \frac{\lambda^2}{8}\sum_{i=1}^n (b_i - a_i)^2 - \lambda t \right)$

となり、右辺を $\lambda$ について最小化することで、 $\lambda = \frac{4t}{\sum_{i=1}^n (b_i - a_i)^2}$ でHoeffdingの不等式が得られる

Hoeffdingの不等式の右辺は $O(\exp(-t^2))$ という、正規分布のような裾になっていることがわかるが、このような確率変数はsub-gaussianと呼ばれる:

確率変数 $X$ に対して、次の不等式を満たす定数 $K$ が存在するとき $X$ はsub-gaussianであるという
$\displaystyle \mathbb{P}[|X| \geq t] \leq 2\exp\left(-\frac{t^2}{K}\right) \quad (\forall t \geq 0)$

よって、Hoeffdingの不等式は「有界な確率変数はsub-gaussianである」ということを述べていると見做すこともできる

素朴な観察として、もしHoeffdingの不等式において総和 $S$ の分散が $\sum_{i=1}^n (b_i - a_i)^2$ よりも遥かに小さい場合、右辺のバウンドはゆるいものになってしまうことが予想される

実際、 $X_i$ が $p_i$ をパラメータとするベルヌーイ分布に従っている状況を考えると、 $p_i$ がとても小さい時は少数の法則より $S$ がおおよそポアソン分布に従うことになるが、ポアソン分布といえば

$\displaystyle \mathbb{P}[S = k] = e^{-\lambda} \frac{\lambda^k}{k!} \approx \frac{1}{\sqrt{2\pi k}} e^{-\lambda} \left(\frac{e\lambda}{k}\right)^k$

と、正規分布の裾よりも緩やかなものになっている

このような確率変数に対してよりシャープな評価を与えるのが、次に述べるBennett/Bernsteinの不等式である

Bennett/Bernsteinの不等式

分散が有限かつ独立な確率変数の列 $X_1,\dots,X_n$ に対してある定数 $b > 0$ が存在して各 $i=1,\dots,n$ について $X_i \leq b$ となるとき、
$\displaystyle S = \sum_{i = 1}^n (X_i - \mathbb{E}[X_i]),\quad v = \sum_{i=1}^n \mathbb{E}[X^2_i]$

と表すことにすれば、任意の $t > 0$ に対して
$\displaystyle \mathbb{P}[ S \geq t] \leq \exp\left(-\frac{v}{b^2} h\left(\frac{bt}{v}\right) \right)$

となる(ここで $h(u) := (1+u)\log (1+u) - u$ )

ステートメントが少しわかりにくいが、

$\displaystyle h(u) \geq \frac{u^2}{2(1+u/3)}$

であることに注目すると、Bernsteinの不等式と呼ばれる、より解釈のしやすい次の不等式が得られる:

$\displaystyle \mathbb{P}[ S \geq t] \leq \exp\left(-\frac{t^2}{2(v+bt/3)} \right)$

この式からわかることとして、 $t \gg v/b$ 、すなわち裾の端の方ではおおよそ $O(\exp(-t))$ の形になっている一方、 $t$ が小さい領域では右辺は $O(\exp(-t^2))$ とsub-gaussianな形になっていることが挙げられる

これは所謂中心極限定理の現れであり、和を取る確率変数の数 $n$ が大きくなるほど $v$ の値も大きくなるので、それに応じて裾におけるsub-gaussianな領域も広がっていくことが見て取れる

$h(u) = (1+u)\log(1+u)-u$ と $u\mapsto \frac{u^2}{2(1+u/3)}$ のプロット

証明はHoeffdingの不等式と同様にモーメント関数を評価していくことになるわけだが、Hoeffdingの不等式との大きな違いは、Bennettの不等式ではより直接的に確率変数 $X$ の2次モーメントの値が与えられているということだ

これによって、Hoeffdingの不等式では評価が緩くなるような分散が小さい確率変数に対してもシャープな評価を与えることができる

より詳細には次のようになる: まず初めに、 $b = 1$ 、すなわち $X_i \leq 1$ としても一般性を失わないことに注目すると、モーメント母関数は

$\displaystyle \begin{align*} \mathbb{E}[e^{\lambda X_i}] &= \mathbb{E}\left[1 + \lambda X_i + \frac{\lambda^2}{2}X_i^2 + \frac{\lambda^3}{6}X_i^3 + \cdots\right] \\ &\leq \mathbb{E}\left[1 + \lambda X_i + X_i^2\left(\frac{\lambda^2}{2} + \frac{\lambda^3}{6} + \cdots \right)\right] \end{align*}$