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

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

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

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

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


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

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

証明.
{\displaystyle \;\;\; 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つの不等号には {\displaystyle U } が非負であることを用いている.(証明終わり)

 

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

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

証明.
確率変数 {\displaystyle (Z-\mu)^2 } に Markov's Inequality を適用して
{\displaystyle \;\;\; P( | Z - \mu | \ge \sigma t ) = P \left( (Z-\mu)^2 \le \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)
{\displaystyle \mathbb{R} } 上の確率変数 {\displaystyle Z } とすべての {\displaystyle t \gt 0 } について以下が成り立つ.{\displaystyle M_Z (s) } はモーメント母関数である.
{\displaystyle \;\;\; P(Z \ge t) = \inf_{s \gt 0 } \left( e^{-st} E [ e^{sZ} ] \right) }

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

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

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

証明.
任意の {\displaystyle s \gt 0 } について, Markov's Inequality を適用して
{\displaystyle \;\;\; 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)
{\displaystyle V }{\displaystyle E [ V ] =0 } を満たす {\displaystyle \mathbb{R} } 上の確率変数とし,{\displaystyle a \le V \le b } が確率1で成り立つとする( {\displaystyle a \lt 0 \lt b } である).このときすべての {\displaystyle s \gt 0 } について以下が成り立つ.

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


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

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

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

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

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

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

すぐにわかるように {\displaystyle \xi (0) = 0 } である.また

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

から {\displaystyle \xi' (0) = 0 } である.つぎに {\displaystyle \phi''(u) } の最大値を求める.

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

{\displaystyle \;\;\; \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 } }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; = \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 } }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; = \frac{ p(1-p)e^u}{ (p + (1-p)e^{u})^3 } \left( (p + (1-p)e^{u}) -2(1-p)e^u \right) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\; = \frac{ p(1-p)e^u}{ (p + (1-p)e^{u})^3 } \left( p -(1-p)e^u \right) }

であり,{\displaystyle \xi''' (0) = 0 } とすると

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

であり,このとき最大値

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

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

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

を得る.(証明終わり)

 

互いに独立な確率変数列の総和に対する不等式として 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 t \gt 0 } について以下が成り立つ.

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

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

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

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


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

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

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

 

 以上,いくつかの集中不等式を証明しました.

 

参考文献
[1] University of Michigan  Clayton Scott先生のノート http://web.eecs.umich.edu/~cscott/past_courses/eecs598w14/notes/03_hoeffding.pdf
[2] Massachusetts Institute of Technology  Michel Goemans先生のノート http://math.mit.edu/~goemans/18310S15/chernoff-notes.pdf
[3] Cornell University  Karthik Sridharan先生のノート https://www.cs.cornell.edu/~sridharan/concentration.pdf
[4] Wikipedia  Taylor's theorem のページ https://en.wikipedia.org/wiki/Taylor%27s_theorem
[5] Wikipedia  Concentration inequality のページ https://en.wikipedia.org/wiki/Concentration_inequality