エンジニアを目指す浪人のブログ

情報系に役立ちそうな応用数理をゆるめにメモします

集中不等式(Bernstein's Inequality)を証明する

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

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

 

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


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

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

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

{\displaystyle [ E(XY) ]^2 \le E(X^2)E(Y^2) }

  

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

定理 6.
{\displaystyle X_1,\ldots,X_n }{\displaystyle E [ X_i ] =0 } となる互いに独立な確率変数で,確率1で {\displaystyle | X_i | \le \varsigma } を満たすとする.{\displaystyle \sigma^2 = (1/n) \sum_{i=1}^n Var [ X_i ] } とする.このとき以下が成り立つ.

{\displaystyle \;\;\; 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 を用いて以下を得る(本記事に合わせて記号を変更しています).

{\displaystyle \;\;\; 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] }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} e^{-s \epsilon } \prod_{i=1}^n E \left[ e^{ s X_i } \right] }                 (0)


{\displaystyle \sigma_i^2 = E [ X_i^2 ] } とおいて以下の関係式を得る.

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


{\displaystyle E [ X_i^r ] } について以下を得る.

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


{\displaystyle F_i } について以下を得る.{\displaystyle s \gt 0 } とする.

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


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

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


これと(0)と {\displaystyle E [ X_i ] =0 } より以下を得る.

{\displaystyle \;\;\; 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] }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \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) } }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \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 } }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \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)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \min_{s \gt 0} e^{ ( n \sigma^2 / \varsigma^{ 2 }) \left( e^{ s \varsigma } -1 - s \varsigma \right) -s \epsilon } }                 (4)


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

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

したがって

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

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

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

したがって {\displaystyle f(s) } の最小値は以下である.

{\displaystyle \;\;\; f(\tilde{s}) = ( n \sigma^2 / \varsigma^{ 2 }) \left( e^{ \tilde{s} \varsigma } -1 - \tilde{s} \varsigma \right) - \tilde{s} \epsilon }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; = \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) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; = \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) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; = - \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)


関数 {\displaystyle H(x),G(x) } を以下のように定義する.

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

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

{\displaystyle G(x) \le H(x), \;\;\; \forall x \gt 0 }                 (6)


(4)(5)より

{\displaystyle \;\;\; 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 } }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = e^{f(\tilde{s})} }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = e^{ - \frac{n \sigma^2}{\varsigma^{ 2 }} H(\frac{\epsilon \varsigma}{n \sigma^2}) } }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le e^{ - \frac{n \sigma^2}{\varsigma^{ 2 }} G(\frac{\epsilon \varsigma}{n \sigma^2}) } \;\;\;  \because } (6)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \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) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \mathrm{exp} \left( - \frac{3}{2} \frac{ \frac{\epsilon^2 }{n \sigma^2} }{ \frac{\epsilon \varsigma}{n \sigma^2} + 3} \right) }

最後に {\displaystyle \epsilon = n \epsilon } とおきかえると

{\displaystyle \;\;\; 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) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \mathrm{exp} \left( - \frac{3}{2} \frac{ \frac{n \epsilon^2 }{ \sigma^2} }{ \frac{\epsilon \varsigma}{\sigma^2} + 3} \right) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \mathrm{exp} \left( - \frac{3}{2} \frac{ n \epsilon^2 }{ \epsilon \varsigma + 3 \sigma^2 } \right) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \mathrm{exp} \left( - \frac{ n \epsilon^2 }{ 2 \sigma^2 + 2 \varsigma \epsilon /3 } \right) }

を得る.(証明終わり) 

 

以上,集中不等式の一つである Bernstein's inequality を(一部分を除いて)証明しました.

 

参考文献
[1] Cornell University  Karthik Sridharan先生のノート https://www.cs.cornell.edu/~sridharan/concentration.pdf
[2] New York University  Afonso S. Bandeira先生のノート http://math.mit.edu/~bandeira/2015_18.S096_4_Concentration_Inequalities.pdf
[3] The University of Hong Kong  Dong Fanghu Joseph先生のノート http://web.hku.hk/~jdong/new/work/teaching/stat1301/t7/proofs_corr.pdf