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

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

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


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


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

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


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

定理1. (Hoeffdings 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} } 
ight) 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} } 
ight) 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) ;;; ecause } このように定義する
{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 
ight) }
{displaystyle ;;;;;;; Leftrightarrow ;;; epsilon^2 = frac{sum_{i=1}^n (b_i - a_i)}{2} left( log frac{1}{delta} 
ight) }
{displaystyle ;;;;;;; Rightarrow ;;; epsilon = sqrt{ frac{sum_{i=1}^n (b_i - a_i)}{2} left( log frac{1}{delta} 
ight) } ;;; ecause 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} 
ight) } 
ight) 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} 
ight) } 
ight) ge 1 - delta ;;; ecause epsilon gt 0 }

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

 

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

定理 6. (Bernsteins 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 
ight) le mathrm{exp} left( - frac{ n epsilon^2 }{ 2 sigma^2 + 2 varsigma epsilon /3 } 
ight) }

事実. (別表現)
定理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{2varsigma log(1/delta) }{3n} 
ight) ge 1 - delta }


事実の証明.

{displaystyle ;;; P left( frac{1}{n}sum_{i=1}^n X_i ge epsilon 
ight) le mathrm{exp} left( - frac{ n epsilon^2 }{ 2 sigma^2 + 2 varsigma epsilon /3 } 
ight) := delta in (0,1) ;;; ecause } このように定義する
{displaystyle ;;;;;; Leftrightarrow ;;; 1 - P left( frac{1}{n}sum_{i=1}^n X_i ge epsilon 
ight) ge 1 - delta }
{displaystyle ;;;;;; Leftrightarrow ;;; P left( frac{1}{n}sum_{i=1}^n X_i lt epsilon 
ight) ge 1 - delta ;;; } (※)

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

{displaystyle ;;; mathrm{exp} left( - frac{ n epsilon^2 }{ 2 sigma^2 + 2 varsigma epsilon /3 } 
ight) = 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 
ight) varsigma log (1/delta))^2 - n (- 2 sigma^2 log (1/delta) 
ight) } }{n} ;;; ecause epsilon gt 0 }
{displaystyle ;;;;;;;; = frac{ (1/3) varsigma log (1/delta) + sqrt{ left( left( 1/3 
ight) varsigma log (1/delta))^2 + 2 n sigma^2 log (1/delta) 
ight) } }{n} }
{displaystyle ;;;;;;;; le frac{ (1/3) varsigma log (1/delta) + sqrt{ left( 1/3 
ight) varsigma log (1/delta))^2 } + sqrt{ 2 n sigma^2 log (1/delta) } }{n} ;;; ecause 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} 
ight) ge 1 - delta }

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

 

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

 


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