Hoeffding不等式的证明

Hoeffding不等式在机器学习的理论知识中非常重要，是证明VC-bound的基础，这篇文章给出其证明。

Hoeffding不等式

首先给出Hoeffding不等式的结论

$$X_1,...,X_n是独立同分布的随机变量，X_i服从参数为p的伯努利分布，\\ 即\mathbb P(X_i=1)=p,\mathbb P(X_i=0)=1-p，那么\\ \mathbb P(\Big|\overline X -\mathbb E[\overline X]\Big|\ge t )\le2e^{-2nt^2}\\ 其中\overline X=\frac 1 n\sum_{i=1}^n X_i,\mathbb E[\overline X]=\frac1n\mathbb E[\sum_{i=1}^n X_i]=p,t>0\\$$

下面就来证明这个结论，证明方法主要受到MIT概率课程的启发。

首先给出一个引理

引理1 (马尔可夫不等式)

$$Z为非负随机变量，那么\mathbb P(Z\ge c)\le \frac{\mathbb E[Z]}{c}$$

这个引理是马尔可夫不等式，后面证明中会用到，这个不等式的证明比较简单，这里略过。

接着，我们不直接证明结论，而是证明一个类似的结论，如下

引理2

$$X_1,...,X_n是独立同分布的随机变量,\mathbb P(X_i=1)=\frac 1 2+a,\mathbb P(X_i=-1)=\frac 1 2-a\\ 那么\mathbb P(\overline X -\mathbb E[\overline X]\ge t )\le e^{-\frac{n t^2}{2}}$$

可以看到这个结论和我们需要证明的结论形式非常类似，但是相对于原来的命题，这个结论更加“对称”一些，这是因为$-1,+1$以及$\frac 1 2+a,\frac 1 2-a$都比较对称，后面证明中可以看到，这样的对称性可以使得证明更加方便，下面来证明这个结论。

证明：首先计算$\mathbb E[X_i],\mathbb E[\overline X]$

$$\mathbb E[X_i]=(\frac 1 2+a)\times 1 +(\frac 1 2-a)\times(-1)=2a\\ \mathbb E[\overline X]=\mathbb E[X_i]=2a$$

所以原不等式可以转化为

$$\mathbb P(\overline X -2a\ge t )\le e^{-\frac{n t^2}{2}}$$

以及有如下等价关系

$$\mathbb P(\overline X -2a\ge t )\le e^{-\frac{n t^2}{2}}\Leftrightarrow \\ \mathbb P(\sum_{i=1}^nX_i \ge n(t+2a ))\le e^{-\frac{n t^2}{2}}\Leftrightarrow\\ \mathbb P(e^{s\sum_{i=1}^nX_i} \ge e^{sn(t+2a )})\le e^{-\frac{n t^2}{2}}(s>0)$$

这里$s​$是任意正数，接下来使用引理1

$$\mathbb P(e^{s\sum_{i=1}^nX_i} \ge e^{sn(t+2a )})\le \frac{\mathbb E[e^{s\sum_{i=1}^nX_i}]}{e^{sn(t+2a )}}$$

我们现在对$\frac{\mathbb E[e^{s\sum_{i=1}^nX_i}]}{e^{sn(t+2a )}}$进行处理，注意$X_1,…,X_n$独立同分布

$$\frac{\mathbb E[e^{s\sum_{i=1}^nX_i}]}{e^{sn(t+2a )}}=\frac{1}{e^{snt}}\times \frac{(\mathbb E[e^{sX_1}])^n}{e^{2asn }} =\frac{1}{e^{snt}}\times (\frac{\mathbb E[e^{sX_1}]}{e^{2as }})^n$$

接下来我们处理$\frac{\mathbb E[e^{sX_1}]}{e^{2as }}$，利用$\mathbb P(X_i=1)=\frac 1 2+a,\mathbb P(X_i=-1)=\frac 1 2-a$

$$\frac{\mathbb E[e^{sX_1}]}{e^{2as }}=\frac{e^s(\frac 1 2+a)+e^{-s}(\frac 1 2-a)}{e^{2as}}=\frac{\frac12(e^s+e^{-s})+a(e^{s}-e^{-s})}{e^{2as}}$$

记$m=\frac12(e^s+e^{-s}),n=e^{s}-e^{-s}​$，所以上式可以改写为

$$f(a)=\frac{m+na}{e^{2as}}$$

对其取对数可得

$$g(a)=\text{ln}f(a)=\text{ln}(m+na)-2as$$

研究$f(a)$的极值只要研究$g(a)$的极值即可

$$g^{'}(a)=\frac{n}{m+na}-2s=0\\ a=\frac{n-2ms}{2ns}\\ g^{''}(a)=-\frac{n^2}{m+na}<0$$

所以当$a=\frac{n-2ms}{2ns}$时，$g(a)$取极大值，并且$a\le \frac{n-2ms}{2ns}$时单调递增，$a>\frac{n-2ms}{2ns}$时单调递减，但是注意这里的$a\in [0,\frac 1 2]$，所以还要看$\frac{n-2ms}{2ns}$与$[0,\frac 12 ]$的关系，我们先判断$\frac{n-2ms}{2ns}$是否大于$0$，因为$s>0$，所以分母$2ns=2s(e^s-e^{-s})>0$，只要考虑分子即可

$$h(s)=n-2ms=e^s-e^{-s}-s(e^s+e^{-s})\\ h^{'}(s)=e^s+e^{-s}-(e^s+e^{-s})-s(e^s-e^{-s})=-s(e^s-e^{-s})<0\\ h(s)=n-2ms<h(0)=0$$

所以$\frac{n-2ms}{2ns}<0​$，从而$g(a)​$在$[0,\frac 1 2]​$上单调递减，因此

$$g(a)\le g(0)\\ f(a)\le f(0) = m=\frac12(e^s+e^{-s})$$

所以现在只要处理$\frac12(e^s+e^{-s})$即可，对$e^s,e^{-s}$分别使用泰勒展开

$$e^s=\sum_{i=0}^{+\infty} \frac{s^i}{i!},e^{-s}=\sum_{i=0}^{+\infty} \frac{(-s)^i}{i!}\\ \frac12(e^s+e^{-s})=\frac 1 2 \sum_{i=0}^{+\infty}\frac {(1+(-1)^i)}{i!}s^i=\sum_{k=0}^{+\infty}\frac {s^{2k}}{(2k)!}$$

对$(2k)!​$稍作变形

$$(2k)!=1\times 2\times...\times k\times (k+1)\times ...\times 2k\ge k!\times\underbrace {2 \times...\times 2}_{k个2}=2^kk!$$

将这个式子带入原式可得

$$\frac12(e^s+e^{-s})=\sum_{k=0}^{+\infty}\frac {s^{2k}}{(2k)!}\le \sum_{k=0}^{+\infty}\frac {(s^{2})^k}{k!2^k} = \sum_{k=0}^{+\infty}\frac {(\frac{s^{2}}{2})^k}{k!}=e^{\frac{s^2}{2}}$$

把以上几点结合起来可以得到

$$\frac{\mathbb E[e^{sX_1}]}{e^{2as }}\le e^{\frac{s^2}{2}}\\ \frac{\mathbb E[e^{s\sum_{i=1}^nX_i}]}{e^{sn(t+2a )}}=\frac{1}{e^{snt}}\times (\frac{\mathbb E[e^{sX_1}]}{e^{2as }})^n \le \frac{1}{e^{snt}}\times e^{\frac{ns^2}{2}}=(e^{\frac {s^2}2-st})^n$$

由于$s​$为任意大于$0​$的数，取$s=t​$，从而

$$\frac{\mathbb E[e^{s\sum_{i=1}^nX_i}]}{e^{sn(t+2a )}}\le(e^{-\frac {t^2}2})^n=e^{\frac{-nt^2}{2}}\\ \mathbb P(\overline X -\mathbb E[\overline X]\ge t )=\mathbb P(e^{s\sum_{i=1}^nX_i} \ge e^{sn(t+2a )})\le \frac{\mathbb E[e^{s\sum_{i=1}^nX_i}]}{e^{sn(t+2a )}}\le e^{-\frac{n t^2}{2}}$$

所以结论得证。这里再补充一点，我们还有以下对称的结论

$$\mathbb P(\overline X -\mathbb E[\overline X]\le -t )\le e^{-\frac{n t^2}{2}}$$

这是因为

$$\mathbb P(\overline X -\mathbb E[\overline X]\le -t )=\mathbb P(-\overline X -\mathbb E[-\overline X]\ge t )$$

因为$\mathbb P(X_i=1)=\frac 1 2+a,\mathbb P(X_i=-1)=\frac 1 2-a​$，所以$-X_i​$也是形式一致的随机变量，由引理2可知

$$\mathbb P(\overline X -E[\overline X]\le -t )=\mathbb P(-\overline X -E[-\overline X]\ge t )\le e^{-\frac{n t^2}{2}}$$

把以上两者结合有以下推论

$$\mathbb P(\Big|\overline X -\mathbb E[\overline X]\Big| \ge t )=\mathbb P(\overline X -\mathbb E[\overline X]\le -t )+\mathbb P(\overline X -\mathbb E[\overline X]\ge t )\le 2e^{-\frac{n t^2}{2}}$$

最后就利用上述引理2及其推论证明Hoeffding不等式

Hoeffding不等式的证明

Hoeffding不等式中的随机变量$X_1,…,X_n$满足$\mathbb P(X_i=1)=p,\mathbb P(X_i=0)=1-p$，对其稍作变形，转化为引理2的形式

$$Y_i=2X_i-1\\ \mathbb P(Y_i=1)=p,\mathbb P(Y_i=-1)=1-p$$

从而

$$\overline Y= 2\overline X-1,\mathbb E[\overline Y]= 2\mathbb E[\overline X]-1$$

所以

$$\begin{aligned} \mathbb P(\Big|\overline X -\mathbb E[\overline X]\Big|\ge t ) &=\mathbb P(\Big|2\overline X -2\mathbb E[\overline X]\Big|\ge 2t )\\ &=\mathbb P(\Big|2\overline X-1 -(2\mathbb E[\overline X]-1)\Big|\ge2t )\\ &=\mathbb P(\Big|\overline Y -\mathbb E[\overline Y]\Big|\ge2t ) \end{aligned}$$

由引理2的推论可知可知

$$\mathbb P(\Big|\overline Y -\mathbb E[\overline Y]\Big|\ge2t )\le 2e^{-\frac{n (2t)^2}{2}}=2e^{-2nt^2}$$

从而

$$\mathbb P(\Big|\overline X -\mathbb E[\overline X]\Big|\ge t ) =\mathbb P(\Big|\overline Y -\mathbb E[\overline Y]\Big|\ge 2t )\le 2e^{-2nt^2}$$

从而结论得证。

总结

这个证明是我自己思考的，可能不是太简洁，但是比较初等，不需要随机过程等知识，证明思路主要是受到MIT概率课程的启发，我个人也强烈推荐这门课。

参考资料：

https://en.wikipedia.org/wiki/Hoeffding%27s_inequality

http://www.xuetangx.com/courses/course-v1:MITx+6_041x+2018_T1/about