いくつかの集中不等式(Hoeffding's Inequalityなど)を証明する

勉強を進めていて，確率論における概念である集中不等式(concentration inequality)を知りました．これは確率変数がある値(例えば期待値)からどのくらい確率的に乖離するかを評価する不等式のことです．

本記事では，統計的学習理論あるいは機械学習に応用される Hoeffding's Inequality を最終目標にして，いくつかの集中不等式を証明します．文献[1]をベースにしてまとめます．

はじめに本記事であつかう集中不等式の基礎となる Markov's inequality を証明します．

命題1. (Markov's inequality)
$\mathbb{R}$ 上の(可積分な)非負確率変数 $U$ とすべての $t \gt 0$ について以下が成り立つ．
$\;\;\; P(U \ge t ) \le \frac{1}{t} E [ U ]$

証明.
$\;\;\; P(U \ge t ) = E [ \mathbf{1}_{ \{ U \ge t \} } ] \le E \left[ \frac{U}{t} \mathbf{1}_{ \{ U \ge t \} } \right] = \frac{1}{t} E [ U \mathbf{1}_{ \{ U \ge t \} } ] \le \frac{1}{t} E [ U ]$

ここで2つの不等号には $U$ が非負であることを用いている．(証明終わり)

Markov's Inequality の系として Chebyshev's inequality を得ます．

系1. (Chebyshev's inequality)
$\mathbb{R}$ 上の(二乗可積分な)確率変数 $Z$ の平均 $E [ Z ] = \mu$ , 分散 $E [ ( Z - E [ Z ] )^2 ] = \sigma^2$ であるとする．すべての $t \gt 0$ について以下が成り立つ．
$\;\;\; P( | Z - \mu | \ge \sigma t ) \le \frac{1}{t^2}$

証明.
確率変数 $(Z-\mu)^2$ に Markov's Inequality を適用して
$\;\;\; P( | Z - \mu | \ge \sigma t ) = P \left( (Z-\mu)^2 \ge \sigma^2 t^2 \right) \le \frac{1}{\sigma^2 t^2} E [ (Z-\mu)^2 ] = \frac{1}{\sigma^2 t^2} \sigma^2 = \frac{1}{t^2}$
を得る．(証明終わり)

Markov's Inequality の系として Chernoff bound を得ます．これは次の Hoeffding's inequality の証明に使用します．

系2. (Chernoff bound)
$\mathbb{R}$ 上の確率変数 $Z$ とすべての $t \gt 0$ について以下が成り立つ． $M_Z (s)$ はモーメント母関数である．
$\;\;\; P(Z \ge t) \le \inf_{s \gt 0 } \left( e^{-st} E [ e^{sZ} ] \right)$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \inf_{s \gt 0 } \left( e^{-st} E \left[ 1 + sZ + \frac{1}{2}s^2 Z^2 + \cdots \ \right] \right)$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \inf_{s \gt 0 } \left( e^{-st} \sum_{i=1}^\infty \frac{1}{i!} s^i E [ Z^i ] \right) \;\;\; \because$ 自明ではないが成り立つ(証明なしで認める)

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \inf_{s \gt 0 } \ e^{-st} M_Z (s)$

証明.
任意の $s \gt 0$ について， Markov's Inequality を適用して
$\;\;\; P(Z \ge t) = P(sZ \ge st ) = P( e^{sZ} \ge e^{st} ) \le e^{-st} E [ e^{sZ} ] = e^{-st} M_Z (s)$
が成り立つ．(証明終わり)

補題1. (Hoeffding's lemma)
$V$ を $E [ V ] =0$ を満たす $\mathbb{R}$ 上の確率変数とし， $a \le V \le b$ が確率1で成り立つとする( $a \lt 0 \lt b$ である)．このときすべての $s \gt 0$ について以下が成り立つ．

$\;\;\; E [ e^{sV} ] \le e^{s^2 (b-a)^2 /8 }$

証明.
$x \in [ a,b ]$ のとき関数 $x \to e^{sx}$ が凸関数であることと $E [ V ] =0$ より以下を得る．

$\;\;\; e^{sx} \le \frac{x-a}{b-a}e^{sb} + \frac{b-x}{b-a}e^{sa}$
$\;\;\; E [ e^{sV} ] \le \frac{b}{b-a}e^{sa} - \frac{a}{b-a}e^{sb}$

$p=b/(b-a), \ u=(b-a)s$ として以下の関数を導入する．

$\;\;\; \phi(u)= \log (ps^{sa} + (1-p)e^{sb} )$
$\;\;\;\;\;\;\;\;\;\; = \log s^{sa} ( p + (1-p)e^{s(b-a)} )$
$\;\;\;\;\;\;\;\;\;\; = sa + \log ( p + (1-p)e^{s(b-a)} )$
$\;\;\;\;\;\;\;\;\;\; = sb - u + \log ( p + (1-p)e^{u} )$
$\;\;\;\;\;\;\;\;\;\; = sp(b-a) - u + \log ( p + (1-p)e^{u} )$
$\;\;\;\;\;\;\;\;\;\; = pu - u + \log ( p + (1-p)e^{u} )$
$\;\;\;\;\;\;\;\;\;\; = (p-1)u + \log ( p + (1-p)e^{u} )$

この関数は滑らかであるのでテイラーの定理(文献[4]にあります)より任意の $u \in \mathbb{R}$ について以下を満たす $\xi = \xi (u) \in \mathbb{R}$ が存在する．

$\;\;\; \phi(u) = \phi(0) + \phi'(0)u + \frac{1}{2}\phi'' (\xi) u^2$

すぐにわかるように $\phi (0) = 0$ である．また

$\;\;\; \phi'(u)= (p-1) + \frac{ (1-p)e^{u} }{p + (1-p)e^{u}}$
$\;\;\;\;\;\;\;\;\;\;\; = (p-1) + \frac{- p+p+(1-p)e^{u} }{p + (1-p)e^{u}}$
$\;\;\;\;\;\;\;\;\;\;\; = (p-1) + 1 - \frac{p}{p + (1-p)e^{u}}$

から $\phi' (0) = 0$ である．つぎに $\phi''(u)$ の最大値を求める．

$\;\;\; \phi''(u)= \frac{p(1-p)e^{u} }{ (p + (1-p)e^{u})^2 }$

$\;\;\; \phi''' (u)= \frac{p(1-p) e^u ( p+(1-p) e^{u})^2 - p(1-p)e^u 2(p+(1-p)e^u )(1-p) e^u }{ (p + (1-p)e^{u})^4 }$
$\;\;\;\;\;\;\;\;\;\;\; = \frac{p(1-p) e^u }{ (p + (1-p)e^{u})^2 }- \frac{ 2 p(1-p)^2 e^{2u} }{ (p + (1-p)e^{u})^3 }$
$\;\;\;\;\;\;\;\;\;\;\; = \frac{ p(1-p)e^u}{ (p + (1-p)e^{u})^3 } \left( (p + (1-p)e^{u}) -2(1-p)e^u \right)$
$\;\;\;\;\;\;\;\;\;\;\; = \frac{ p(1-p)e^u}{ (p + (1-p)e^{u})^3 } \left( p -(1-p)e^u \right)$

であり， $\phi''' (0) = 0$ とすると

$\;\;\; e^u = \frac{p}{1-p} \; \left( = \frac{b/(b-a)}{1 - b/(b-a)} = - \frac{b}{a} \gt 0 \right)$

であり，このとき最大値

$\;\;\; \phi''(u)= \frac{p(1-p) p/(1-p) }{ (p + (1-p) p/(1-p) )^2 } = \frac{p^2 }{ ( 2p )^2 } = \frac{1}{4}$

をとる(たしかに $e^u \to 0, \infty$ とするとどちらも $\phi'' (u) \to 0$ である)．以上をあわせると

$\;\;\; E [ e^{sV} ] \le \frac{b}{b-a}e^{sa} - \frac{a}{b-a}e^{sb}$
$\;\;\;\;\;\;\;\;\;\;\; = e^{ \phi(u) }$
$\;\;\;\;\;\;\;\;\;\;\; = e^{ \phi(0) + \phi'(0)u + (1/2)\phi'' (\xi) u^2 }$
$\;\;\;\;\;\;\;\;\;\;\; \le e^{ (1/2)(1/4) u^2 }$
$\;\;\;\;\;\;\;\;\;\;\; = e^{ s^2 (b-a)^2 / 8 }$

を得る．(証明終わり)

互いに独立な確率変数列の総和に対する不等式として Hoeffding's inequality が成り立ちます．

定理1. (Hoeffding's inequality)
$Z_1,\ldots,Z_n$ を $\mathbb{R}$ 上の互いに独立な確率変数とし，確率 $1$ で $a_i \le Z_i \le b_i$ を満たすとする． $S_n = \sum_{i=1}^n Z_i$ とする．すべての $t \gt 0$ について以下が成り立つ．

$\;\;\; P(S_n - E [ S_n ] \ge t) \le e^{-2 t^2 / \sum_{i=1}^n (b_i - a_i)^2 }$

$\;\;\; P(S_n - E [ S_n ] \le -t) \le e^{-2 t^2 / \sum_{i=1}^n (b_i - a_i)^2 }$

注意.
2つをあわせて以下を得る．

$\;\;\; P( | S_n - E [ S_n ] | \ge t) \le 2 e^{-2 t^2 / \sum_{i=1}^n (b_i - a_i)^2 }$

証明.
確率変数 $S_n - E [ S_n ]$ に Chernoff bound と補題1.を適用して以下を得る．

$\;\;\; P( S_n - E [ S_n ] \ge t ) \le \min_{s \gt 0} \ e^{-st} E [ e^{s (S_n - E [ S_n ]) } ] \;\;\;\;\;\;\;\;\;\; \because$ Chernoff bound
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} \ e^{-st} E [ e^{s ( \sum_{i=1}^n Z_i - E \left[ \sum_{i=1}^n Z_i \right]) } ]$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} \ e^{-st} E [ e^{s ( \sum_{i=1}^n Z_i - \sum_{i=1}^n E \left[ Z_i \right]) } ]$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} \ e^{-st} E [ e^{ s \sum_{i=1}^n ( Z_i - E \left[ Z_i \right]) } ]$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} \ e^{-st} E \left[ \prod_{i=1}^n e^{ s ( Z_i - E \left[ Z_i \right]) } \right]$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} \ e^{-st} \prod_{i=1}^n E \left[ e^{ s ( Z_i - E \left[ Z_i \right]) } \right] \;\;\; \because$ $Z_i$ は互いに独立
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \min_{s \gt 0} \ e^{-st} \prod_{i=1}^n e^{ s^2 (b_i - a_i)^2 /8 } \;\;\;\;\;\;\;\;\; \because$ 補題1.
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} \ e^{-st} e^{ \sum_{i=1}^n s^2 (b_i - a_i)^2 /8 }$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} \ e^{-st+ s^2 /8 \sum_{i=1}^n (b_i - a_i)^2 }$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} \ e^{ ( \sum_{i=1}^n (b_i - a_i)^2 /8 ) s^2 - t s }$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} \ e^{ \left( \sum_{i=1}^n (b_i - a_i)^2 /8 \right) \left( s^2 - ( 8/ \sum_{i=1}^n (b_i - a_i)^2 )t s \right) }$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} \ e^{ \left( \sum_{i=1}^n (b_i - a_i)^2 /8 \right) \left[ \left( s - 4 t/ \sum_{i=1}^n (b_i - a_i)^2 \right)^2 - \left( 4t / \sum_{i=1}^n (b_i - a_i)^2 \right)^2 \right] }$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = e^{ \left( \sum_{i=1}^n (b_i - a_i)^2 /8 \right) \left[ - \left( 4t / \sum_{i=1}^n (b_i - a_i)^2 \right)^2 \right] } \;\;\;\;\; \because t \gt 0$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = e^{ - 2 t^2 / \sum_{i=1}^n (b_i - a_i)^2 }$

これは1つ目の不等式である．ここで $Z_1 = - Z_1,\ldots,Z_n = - Z_n$ とおきかえると， $-b_i \le - Z_i \le - a_i, \ - a_i - (- b _i) = b_i - a_i$ であるので2つ目の不等式を得る．(証明終わり)