霍夫丁不等式

1. 简介

在概率论中,霍夫丁不等式(Hoeffding's Inequality)给出了有界独立随机变量之和偏离其均值超过一定数量的概率上界。霍夫不等式是切比雪夫界的推广,同时又是吾妻不等式和McDiarmid不等式(还没给出标准的中文翻译2333)。霍夫丁不等式是机器学习的基础理论。

2. 定义

假设 X1,X2,,XN\boldsymbol{X}_1,\boldsymbol{X}_2,\cdots,\boldsymbol{X}_N 是独立随机变量,且 Xi[ai,bi]\boldsymbol{X}_i \in [a_i,b_i]i=1,2,,Ni = 1,2,\cdots,NXˉ\bar{\boldsymbol{X}}X1,X2,,XN\boldsymbol{X}_1,\boldsymbol{X}_2,\cdots,\boldsymbol{X}_N 的经验均值,即 Xˉ=1Ni=1NXi\bar{\boldsymbol{X}} = \frac{1}{N} \sum_{i=1}^N \boldsymbol{X}_i,则对任意 t>0t \gt 0,以下霍夫丁不等式成立:

P[XˉE(Xˉ)t]exp(2N2t2i=1N(biai)2)P[E(Xˉ)Xˉt]exp(2N2t2i=1N(biai)2)\begin{array}{c} P[\bar{\boldsymbol{X}} - E(\bar{\boldsymbol{X}}) \geq t] \leq \exp{(-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2})} \\ P[E(\bar{\boldsymbol{X}}) - \bar{\boldsymbol{X}} \geq t] \leq \exp{(-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2})} \\ \end{array}

证明

霍夫丁引理可得

E(es(XE(X)))exp(18s2(biai)2)(1in)\begin{array}{cc} E(e^{s(\boldsymbol{X}-E(\boldsymbol{X}))}) \leq \exp{(\frac{1}{8} s^2 (b_i - a_i)^2)} & (1 \leq i \leq n) \end{array}

Sn=X1+X2++Xn\boldsymbol{S}_n = \boldsymbol{X}_1 + \boldsymbol{X}_2 + \cdots + \boldsymbol{X}_n,对于 s,t>0\forall s,t \gt 0,可得

P(SnE(Sn)t)=P(es(SnE(Sn))est)\begin{array}{c} P(\boldsymbol{S}_n - E(\boldsymbol{S}_n) \geq t) = P(e^{s(S_n - E(S_n))} \geq e^{st}) \end{array}

进一步根据马尔可夫不等式Xi\boldsymbol{X}_i 之间的独立性可得

P(es(SnE(Sn))est)estE(es(SnE(Sn)))=esti=1nE(es(XiE(Xi)))esti=1nes2(biai)28=exp(st+18s2i=1n(biai)2)\begin{array}{rl} P(e^{s(S_n - E(S_n))} \geq e^{st}) & \leq e^{-st} E(e^{s(\boldsymbol{S}_n-E(\boldsymbol{S}_n))}) \\ & = e^{-st} \prod_{i=1}^n E(e^{s(\boldsymbol{X}_i-E(\boldsymbol{X}_i))}) \\ & \leq e^{-st} \prod_{i=1}^n e^{\frac{s^2(b_i-a_i)^2}{8}} \\ & = \exp{(-st + \frac{1}{8} s^2 \sum_{i=1}^n (b_i - a_i)^2)} \end{array}

g(s)=st+s28i=1n(biai)2g(s) = -st + \frac{s^2}{8} \sum_{i=1}^n (b_i - a_i)^2,则 g(s)g(s) 为关于 ss 的二次函数,从而易得

s=4ti=1n(biai)2\begin{array}{c} s = \frac{4t}{\sum_{i=1}^n (b_i - a_i)^2} \end{array}

g(s)g(s) 的最小值点。由于

P(es(SnE(Sn))est)exp(st+18s2i=1n(biai)2)\begin{array}{c} P(e^{s(S_n - E(S_n))} \geq e^{st}) \leq \exp{(-st + \frac{1}{8} s^2 \sum_{i=1}^n (b_i - a_i)^2)} \end{array}

s>0\forall s \gt 0 都成立,因此当 ssg(s)g(s) 的最小值点时,得到 P(es(SnE(Sn))est)P(e^{s(S_n - E(S_n))} \geq e^{st}) 的紧上界,即

P(es(SnE(Sn))est)exp(2t2i=1n(biai)2)\begin{array}{c} P(e^{s(S_n - E(S_n))} \geq e^{st}) \leq \exp{(-\frac{2t^2}{\sum_{i=1}^n (b_i - a_i)^2})} \end{array}

最终简单变换后可得 P[XˉE(Xˉ)t]exp(2N2t2i=1N(biai)2)P[\bar{\boldsymbol{X}} - E(\bar{\boldsymbol{X}}) \geq t] \leq \exp{(-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2})}。另一个不等式 P[E(Xˉ)Xˉt]exp(2N2t2i=1N(biai)2)P[E(\bar{\boldsymbol{X}}) - \bar{\boldsymbol{X}} \geq t] \leq \exp{(-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2})} 同理可证。

附录

参考资料: