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

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

集中不等式(Hoeffding's inequality, Bernstein's inequality)の別表現について考える

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

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

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


勉強を進めていて,集中不等式(concentration inequality)の別表現があることを知り,それらが統計的学習理論の文献において十分な説明がないままに使われている場合を目にしてモヤモヤしてしまいました.説明している資料があまりないように感じられたので,上記の過去記事にある Hoeffding's inequality と Bernstein's inequality についてその別表現と導出をまとめておくことにしました.文献[1]を参考にしています.


集中不等式は確率分布の裾(tail)を評価する不等式で,以下の形式です.
{\displaystyle \;\;\; P( \mathit{deviation} \ge \epsilon ) \le \delta(\epsilon) }

等価な別表現は以下の形式です.
{\displaystyle \;\;\; P( \mathit{deviation} \le \epsilon(\delta) ) \ge 1 - \delta }


冒頭の過去記事より Hoeffding's inequality を再掲し(記号を変更しています),別表現を示し証明します.

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

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

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

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

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

 事実. (別表現)
定理1.が成り立つとき,ある {\displaystyle \delta \in (0,1) } について以下が成り立つ.

{\displaystyle \;\;\; P \left( S_n - E [ S_n ] \lt \sqrt{ \frac{\sum_{i=1}^n (b_i - a_i)}{2} \log \frac{1}{\delta} } \right) \ge 1 - \delta }

{\displaystyle \;\;\; P \left( S_n - E [ S_n ] \gt - \sqrt{ \frac{\sum_{i=1}^n (b_i - a_i)}{2} \log \frac{1}{\delta} } \right) \ge 1 - \delta }


事実の証明.
定理の1つめの不等式について証明する.

{\displaystyle \;\;\; P( S_n - E [ S_n ] \ge \epsilon) \le e^{-2 \epsilon^2 / \sum_{i=1}^n (b_i - a_i) } =: \delta \in (0,1) \;\;\; \because } このように定義する
{\displaystyle \;\;\;\;\;\; \Leftrightarrow \;\;\; 1 - P( S_n - E [ S_n ] \ge \epsilon) \ge 1 - \delta }
{\displaystyle \;\;\;\;\;\; \Leftrightarrow \;\;\; P( S_n - E [ S_n ] \lt \epsilon) \ge 1 - \delta }

ここで

{\displaystyle \;\;\; e^{-2 \epsilon^2 / \sum_{i=1}^n (b_i - a_i) } = \delta }
{\displaystyle \;\;\;\;\;\;\; \Leftrightarrow \;\;\; -2 \epsilon^2 / \sum_{i=1}^n (b_i - a_i) = \log \delta }
{\displaystyle \;\;\;\;\;\;\; \Leftrightarrow \;\;\; -2 \epsilon^2 = \sum_{i=1}^n (b_i - a_i) \left( \log \delta \right) }
{\displaystyle \;\;\;\;\;\;\; \Leftrightarrow \;\;\; \epsilon^2 = \frac{\sum_{i=1}^n (b_i - a_i)}{2} \left( \log \frac{1}{\delta} \right) }
{\displaystyle \;\;\;\;\;\;\; \Rightarrow \;\;\; \epsilon = \sqrt{ \frac{\sum_{i=1}^n (b_i - a_i)}{2} \left( \log \frac{1}{\delta} \right) } \;\;\; \because \epsilon \gt 0 }

であるので以下を得る.

{\displaystyle \;\;\; P \left( S_n - E [ S_n ] \lt \sqrt{ \frac{\sum_{i=1}^n (b_i - a_i)}{2} \left( \log \frac{1}{\delta} \right) } \right) \ge 1 - \delta }


定理の2つめの不等式について証明する.1つめの不等式と同様に

{\displaystyle \;\;\; P( S_n - E [ S_n ] \le - \epsilon) \le e^{-2 \epsilon^2 / \sum_{i=1}^n (b_i - a_i) } =: \delta }
{\displaystyle \;\;\;\;\;\; \Leftrightarrow \;\;\; 1 - P( S_n - E [ S_n ] \le - \epsilon) \ge 1 - \delta }
{\displaystyle \;\;\;\;\;\; \Leftrightarrow \;\;\; P( S_n - E [ S_n ] \gt - \epsilon) \ge 1 - \delta }
{\displaystyle \;\;\;\;\;\; \Rightarrow \;\;\; P \left( S_n - E [ S_n ] \gt - \sqrt{ \frac{\sum_{i=1}^n (b_i - a_i)}{2} \left( \log \frac{1}{\delta} \right) } \right) \ge 1 - \delta \;\;\; \because \epsilon \gt 0 }

となり示せた.(証明終わり)

 

冒頭の過去記事より Bernstein's inequality を再掲し,別表現を示し証明します.

定理 6. (Bernstein's inequality)
{\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 \epsilon \gt 0 } について以下が成り立つ.

{\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) }

事実. (別表現)
定理6.が成り立つとき,ある {\displaystyle \delta \in (0,1) } について以下が成り立つ.

{\displaystyle \;\;\; P \left( \frac{1}{n}\sum_{i=1}^n X_i \lt \sqrt{ \frac{ \sigma^2 \log (1/\delta)}{n} } + \frac{2\varsigma \log(1/\delta) }{3n} \right) \ge 1 - \delta }


事実の証明.

{\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) := \delta \in (0,1) \;\;\; \because } このように定義する
{\displaystyle \;\;\;\;\;\; \Leftrightarrow \;\;\; 1 - P \left( \frac{1}{n}\sum_{i=1}^n X_i \ge \epsilon \right) \ge 1 - \delta }
{\displaystyle \;\;\;\;\;\; \Leftrightarrow \;\;\; P \left( \frac{1}{n}\sum_{i=1}^n X_i \lt \epsilon \right) \ge 1 - \delta \;\;\; } (※)

ここで以下の {\displaystyle \epsilon } についての二次方程式を得る.

{\displaystyle \;\;\; \mathrm{exp} \left( - \frac{ n \epsilon^2 }{ 2 \sigma^2 + 2 \varsigma \epsilon /3 } \right) = \delta }
{\displaystyle \;\;\;\;\;\; \Leftrightarrow \;\;\; - \frac{ n \epsilon^2 }{ 2 \sigma^2 + 2 \varsigma \epsilon /3 } = \log \delta }
{\displaystyle \;\;\;\;\;\; \Leftrightarrow \;\;\; \frac{ n \epsilon^2 }{ 2 \sigma^2 + 2 \varsigma \epsilon /3 } = \log (1/\delta) }
{\displaystyle \;\;\;\;\;\; \Leftrightarrow \;\;\; n \epsilon^2 - \frac{2}{3} \varsigma \log (1/\delta) \epsilon - 2 \sigma^2 \log (1/\delta) = 0 }

解の公式より以下を得る.

{\displaystyle \;\;\; \epsilon = \frac{ (1/3) \varsigma \log (1/\delta) + \sqrt{ \left( \left( 1/3 \right) \varsigma \log (1/\delta))^2 - n (- 2 \sigma^2 \log (1/\delta) \right) } }{n} \;\;\; \because \epsilon \gt 0 }
{\displaystyle \;\;\;\;\;\;\;\; = \frac{ (1/3) \varsigma \log (1/\delta) + \sqrt{ \left( \left( 1/3 \right) \varsigma \log (1/\delta))^2 + 2 n \sigma^2 \log (1/\delta) \right) } }{n} }
{\displaystyle \;\;\;\;\;\;\;\; \le \frac{ (1/3) \varsigma \log (1/\delta) + \sqrt{ \left( 1/3 \right) \varsigma \log (1/\delta))^2 } + \sqrt{ 2 n \sigma^2 \log (1/\delta) } }{n} \;\;\; \because \sqrt{x+y} \le \sqrt{x}+\sqrt{y} }
{\displaystyle \;\;\;\;\;\;\;\; = \frac{ (2/3) \varsigma \log (1/\delta) + \sqrt{ 2 n \sigma^2 \log (1/\delta) } }{n} }
{\displaystyle \;\;\;\;\;\;\;\; = \sqrt{\frac{ 2 \sigma^2 \log (1/\delta)}{n} } + \frac{2 \varsigma \log (1/\delta) }{3n} }

これと(※)より

{\displaystyle \;\;\; P \left( \frac{1}{n}\sum_{i=1}^n X_i \lt \sqrt{\frac{ 2 \sigma^2 \log (1/\delta)}{n} } + \frac{2 \varsigma \log (1/\delta) }{3n} \right) \ge 1 - \delta }

となり示せた.(証明終わり)

 

以上,集中不等式(Hoeffding's inequality, Bernstein's inequality)の別表現について考えてみました.

 


参考文献
[1] University of Washington  Sham M. Kakade先生の(Wharton School, University of Pennsylvania在籍時の)ノート http://stat.wharton.upenn.edu/~skakade/courses/stat928/lectures/lecture06.pdf