集中不等式(Bernstein's Inequality)を証明する - エンジニアを目指す浪人のブログ

本記事は以下の過去記事で得た結果を用います．

いくつかの集中不等式(Hoeffding's Inequalityなど)を証明する - エンジニアを目指す浪人のブログ

本記事では，集中不等式(concentration inequality)の一つである Bernstein's inequality を(一部分を除いて)証明します．文献[1]をベースにしてまとめます．

準備をします．
本記事では(確率論における)コーシーシュワルツの不等式を証明なしで用います(たとえば文献[3]にあります)．

補題 : コーシーシュワルツの不等式

$X, \ Y$ は $E(X),E(Y),E(XY)$ が存在するような確率変数とする．このとき以下が成り立つ．

$[ E(XY) ]^2 \le E(X^2)E(Y^2)$

本記事の目的に進みます．
冒頭の過去記事にある Hoeffding's Inequality は確率分布についての情報を用いません．Bernstein's inequality はよりきつくバウンドする(抑える)ために確率分布の分散を用います．以下の命題と証明は，文献[1] Theorem 6をほぼ引用したものです．

定理 6. (Bernstein's inequality)
$X_1,\ldots,X_n$ を $E [ X_i ] =0$ となる互いに独立な確率変数で，確率1で $| X_i | \le \varsigma$ を満たすとする． $\sigma^2 = (1/n) \sum_{i=1}^n Var [ X_i ]$ とする．すべての $\epsilon \gt 0$ について以下が成り立つ．

$\;\;\; P \left( \frac{1}{n}\sum_{i=1}^n X_i \ge \epsilon \right) \le \mathrm{exp} \left( - \frac{ n \epsilon^2 }{ 2 \sigma^2 + 2 \varsigma \epsilon /3 } \right)$

証明.

冒頭の過去記事の定理1.の証明.の冒頭と同様に Chernoff bound を用いて以下を得る(本記事に合わせて記号を変更しています)．

$\;\;\; P \left( \sum_{i=1}^n X_i - E \left[ \sum_{i=1}^n X_i \right] \ge \epsilon \right) = \min_{s \gt 0} e^{-s \epsilon } E \left[ e^{ s ( \sum_{i=1}^n X_i - E \left[ \sum_{i=1}^n X_i \right]) } \right]$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} e^{-s \epsilon } \prod_{i=1}^n E \left[ e^{ s X_i } \right]$ (0)

$\sigma_i^2 = E [ X_i^2 ]$ とおいて以下の関係式を得る．

$\;\;\; \sigma^2 = (1/n) \sum_{i=1}^n Var [ X_i ]$
$\;\;\;\;\;\;\;\; = (1/n) \sum_{i=1}^n E [ (X_i - E [ X_i ] )^2 ]$
$\;\;\;\;\;\;\;\; = (1/n) \sum_{i=1}^n E [ X_i^2 ]$
$\;\;\;\;\;\;\;\; = (1/n) \sum_{i=1}^n \sigma_i^2$ (1)

$E [ X_i^r ]$ について以下を得る．

$\;\;\; E [ X_i^r ] = E [ X_i X_i^{r-1} ]$
$\;\;\;\;\;\;\;\;\;\;\;\;\; \le ( E [ X_i^2 ] )^{1/2} ( E [ X_i^{2(r-1)} ] )^{1/2} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because$ コーシーシュワルツの不等式
$\;\;\;\;\;\;\;\;\;\;\;\;\; = \sigma_i ( E [ X_i^{2(r-1)} ] )^{1/2}$
$\;\;\;\;\;\;\;\;\;\;\;\;\; = \sigma_i \left[ E [ X_i X_i^{2r-3} ] \right]^{1/2}$
$\;\;\;\;\;\;\;\;\;\;\;\;\; \le \sigma_i \left[ ( E [ X_i^2 ] )^{1/2} ( E [ X_i^{2(2r-3)} ] )^{1/2} \right]^{1/2} \;\;\;\;\;\;\;\;\;\; \because$ コーシーシュワルツの不等式
$\;\;\;\;\;\;\;\;\;\;\;\;\; = \sigma_i^{1+\frac{1}{2}} \left[ E [ X_i^{2(2r-3)} ] \right]^{1/4}$
$\;\;\;\;\;\;\;\;\;\;\;\;\; = \sigma_i^{1+\frac{1}{2}} \left[ E [ X_i X_i^{4r-7} ] \right]^{1/4}$
$\;\;\;\;\;\;\;\;\;\;\;\;\; \le \sigma_i^{1+\frac{1}{2}} \left[ ( E [ X_i^2 ] )^{1/2} ( E [ X_i^{2(4r-7)} ] )^{1/2} \right]^{1/4} \;\;\;\;\;\;\; \because$ コーシーシュワルツの不等式
$\;\;\;\;\;\;\;\;\;\;\;\;\; = \sigma_i^{1+\frac{1}{2}+\frac{1}{4} } \left[ ( E [ X_i^{2(4r-7)} ] )^{1/2} \right]^{1/4}$
$\;\;\;\;\;\;\;\;\;\;\;\;\; = \sigma_i^{1+\frac{1}{2}+\frac{1}{4} } \left[ E [ X_i X_i^{8r-15} ] \right]^{1/8}$
$\;\;\;\;\;\;\;\;\;\;\;\;\; \le \cdots \le \cdots \le \cdots \le \cdots \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because$ コーシーシュワルツの不等式を繰り返し用いる
$\;\;\;\;\;\;\;\;\;\;\;\;\; \le \sigma_i^{1 + \frac{1}{2} + \cdots + \left( \frac{1}{2} \right)^{n-1} } \left[ E [ X_i^{2^n r- 2^{n+1} + 2 } ] \right]^{ \left( \frac{1}{2} \right)^n }$
$\;\;\;\;\;\;\;\;\;\;\;\;\; \le \sigma_i^{ \frac{1 - (1/2)^n }{ 1- (1/2)} } \left[ E [ X_i^{2^n r- 2^{n+1} + 2 } ] \right]^{ \left( \frac{1}{2} \right)^n }$
$\;\;\;\;\;\;\;\;\;\;\;\;\; = \sigma_i^{ 2 \left( 1- (\frac{1}{2})^n \right) } \left[ E [ |X_i|^{2^n r- 2^{n+1} + 2 } ] \right]^{ \left( \frac{1}{2} \right)^n }$
$\;\;\;\;\;\;\;\;\;\;\;\;\; \le \sigma_i^{ 2 \left( 1- (\frac{1}{2})^n \right) } \left[ \varsigma^{2^n r- 2^{n+1} + 2 } \right]^{ \left( \frac{1}{2} \right)^n } \;\;\;\;\;\;\;\;\;\; \because | X_i | \le \varsigma \;\;\; \mathrm{with \ probability } \ 1$
$\;\;\;\;\;\;\;\;\;\;\;\;\; = \sigma_i^{ 2 \left( 1- (\frac{1}{2})^n \right) } \varsigma^{r- 2 + \left( \frac{1}{2} \right)^{n-1} }$
$\;\;\;\;\;\;\;\;\;\;\;\;\; \to \sigma_i^{ 2 } \varsigma^{r- 2 }, \;\;\; n \to \infty$ (2)

$F_i$ について以下を得る． $s \gt 0$ とする．

$\;\;\; F_i = \sum_{r=2}^\infty \frac{ s^{r-2} E(X_i^r) }{r! \sigma_i^2 } \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because$ このように定義する
$\;\;\;\;\;\;\;\;\;\;\;\; \le \sum_{r=2}^\infty \frac{ s^{r-2} \sigma_i^{ 2 } \varsigma^{r- 2 } }{r! \sigma_i^2 } \;\;\;\;\;\;\;\;\;\; \because$ (2)
$\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{ s^{ 2} \varsigma^{ 2 } } \sum_{r=2}^\infty \frac{ s^{r} \varsigma^{r} }{r! }$
$\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{ s^{ 2} \varsigma^{ 2 } } \left( \sum_{r=0}^\infty \frac{ ( s \varsigma)^{r} }{r!} -1 - s \varsigma \right)$
$\;\;\;\;\;\;\;\;\;\;\;\; = \frac{1}{ s^{ 2} \varsigma^{ 2 } } \left( e^{ s \varsigma } -1 - s \varsigma \right)$ (3)

テイラー展開 $e^x = 1 + x + \sum_{r=2}^\infty \frac{ x^r }{r!}$ を利用して以下を得る．

$\;\;\; E [ e^{sX_i} ] = 1 + s E [ X_i ] + \sum_{r=2}^\infty \frac{ s^r E(X_i^r) }{r!}$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 1 + \sum_{r=2}^\infty \frac{ s^r E(X_i^r) }{r!} \;\;\;\;\;\;\;\;\;\;\;\;\;\; \because E [ X_i ] =0$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 1 + s^2 \sigma_i^2 \sum_{r=2}^\infty \frac{ s^{r-2} E(X_i^r) }{r! \sigma_i^2 }$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 1 + F_i s^2 \sigma_i^2$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le e^{ F_i s^2 \sigma_i^2 } \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because$ テイラー展開
$\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le e^{ s^2 \sigma_i^2 \frac{1}{ s^{ 2} \varsigma^{ 2 } } \left( e^{ s \varsigma } -1 - s \varsigma \right) } \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because$ (3)
$\;\;\;\;\;\;\;\;\;\;\;\;\;\; = e^{ \sigma_i^2 \frac{ 1 }{ \varsigma^{ 2 } } \left( e^{ s \varsigma } -1 - s \varsigma \right) }$

これと(0)と $E [ X_i ] =0$ より以下を得る．

$\;\;\; P \left( \sum_{i=1}^n X_i \ge \epsilon \right) = \min_{s \gt 0} e^{-s \epsilon } \prod_{i=1}^n E \left[ e^{ s X_i } \right]$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \min_{s \gt 0} e^{-s \epsilon } \prod_{i=1}^n e^{ \sigma_i^2 \frac{ 1 }{ \varsigma^{ 2 } } \left( e^{ s \varsigma } -1 - s \varsigma \right) }$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} e^{-s \epsilon } e^{ \frac{ 1 }{ \varsigma^{ 2 } } \left( e^{ s \varsigma } -1 - s \varsigma \right) \sum_{i=1}^n \sigma_i^2 }$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} e^{-s \epsilon } e^{ \frac{ 1 }{ \varsigma^{ 2 } } \left( e^{ s \varsigma } -1 - s \varsigma \right) n \sigma^2 } \;\;\;\;\;\;\; \because$ (1)
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} e^{ ( n \sigma^2 / \varsigma^{ 2 }) \left( e^{ s \varsigma } -1 - s \varsigma \right) -s \epsilon }$ (4)

関数 $f(s), \ s \gt 0$ を以下のように定義し最小値をとる $\tilde{s}$ を求める．

$\;\;\; f(s) = ( n \sigma^2 / \varsigma^{ 2 }) \left( e^{ s \varsigma } -1 - s \varsigma \right) -s \epsilon$

したがって

$\;\;\; f'(s) = ( n \sigma^2 / \varsigma^{ 2 }) \left( \varsigma e^{ s \varsigma } - \varsigma \right) - \epsilon = 0$

となる $s = \tilde{s}$ を求めればよい．

$\;\;\; ( n \sigma^2 / \varsigma ) \left( e^{ \tilde{s} \varsigma } - 1 \right) - \epsilon = 0$
$\;\;\; \frac{\epsilon \varsigma}{n \sigma^2} = e^{ \tilde{s} \varsigma } - 1$
$\;\;\; \tilde{s} = \frac{1}{\varsigma} \log \left( 1 + \frac{\epsilon \varsigma}{n \sigma^2} \right)$

したがって $f(s)$ の最小値は以下である．

$\;\;\; f(\tilde{s}) = ( n \sigma^2 / \varsigma^{ 2 }) \left( e^{ \tilde{s} \varsigma } -1 - \tilde{s} \varsigma \right) - \tilde{s} \epsilon$
$\;\;\;\;\;\;\;\;\;\;\; = \frac{n \sigma^2}{\varsigma^{ 2 }} \left( \frac{\epsilon \varsigma}{n \sigma^2} - \log \left( 1 + \frac{\epsilon \varsigma}{n \sigma^2} \right) \right) - \frac{\epsilon}{\varsigma} \log \left( 1 + \frac{\epsilon \varsigma}{n \sigma^2} \right)$
$\;\;\;\;\;\;\;\;\;\;\; = \frac{n \sigma^2}{\varsigma^{ 2 }} \left( \frac{\epsilon \varsigma}{n \sigma^2} - \log \left( 1 + \frac{\epsilon \varsigma}{n \sigma^2} \right) - \frac{\epsilon \varsigma}{n \sigma^2} \log \left( 1 + \frac{\epsilon \varsigma}{n \sigma^2} \right) \right)$
$\;\;\;\;\;\;\;\;\;\;\; = - \frac{n \sigma^2}{\varsigma^{ 2 }} \left( \left( 1 + \frac{\epsilon \varsigma}{n \sigma^2} \right) \log \left( 1 + \frac{\epsilon \varsigma}{n \sigma^2} \right) - \frac{\epsilon \varsigma}{n \sigma^2} \right)$ (5)

関数 $H(x),G(x)$ を以下のように定義する．

$\;\;\; H(x) = (1+x) \log (1+x) - x$
$\;\;\; G(x) = \frac{3}{2} \frac{x^2}{x+3}$

以下が成り立つ(ここでは証明なしで認めます...)．

$G(x) \le H(x), \;\;\; \forall x \gt 0$ (6)

(4)(5)より

$\;\;\; P \left( \sum_{i=1}^n X_i \ge \epsilon \right) \le \min_{s \gt 0} e^{ ( n \sigma^2 / \varsigma^{ 2 }) \left( e^{ s \varsigma } -1 - s \varsigma \right) -s \epsilon }$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = e^{f(\tilde{s})}$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = e^{ - \frac{n \sigma^2}{\varsigma^{ 2 }} H(\frac{\epsilon \varsigma}{n \sigma^2}) }$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le e^{ - \frac{n \sigma^2}{\varsigma^{ 2 }} G(\frac{\epsilon \varsigma}{n \sigma^2}) } \;\;\; \because$ (6)
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \mathrm{exp} \left( - \frac{n \sigma^2}{\varsigma^{ 2 }} \frac{3}{2} \frac{ \left( \frac{\epsilon \varsigma}{n \sigma^2} \right)^2}{ \frac{\epsilon \varsigma}{n \sigma^2} + 3} \right)$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \mathrm{exp} \left( - \frac{3}{2} \frac{ \frac{\epsilon^2 }{n \sigma^2} }{ \frac{\epsilon \varsigma}{n \sigma^2} + 3} \right)$

最後に $\epsilon = n \epsilon$ とおきかえると

$\;\;\; P \left( \frac{1}{n} \sum_{i=1}^n X_i \ge \epsilon \right) \le \mathrm{exp} \left( - \frac{3}{2} \frac{ \frac{n^2 \epsilon^2 }{n \sigma^2} }{ \frac{n \epsilon \varsigma}{n \sigma^2} + 3} \right)$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \mathrm{exp} \left( - \frac{3}{2} \frac{ \frac{n \epsilon^2 }{ \sigma^2} }{ \frac{\epsilon \varsigma}{\sigma^2} + 3} \right)$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \mathrm{exp} \left( - \frac{3}{2} \frac{ n \epsilon^2 }{ \epsilon \varsigma + 3 \sigma^2 } \right)$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \mathrm{exp} \left( - \frac{ n \epsilon^2 }{ 2 \sigma^2 + 2 \varsigma \epsilon /3 } \right)$

を得る．(証明終わり)