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

Hoeffding不等式

首先给出Hoeffding不等式的结论

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

首先给出一个引理

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

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

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

引理2

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

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

所以原不等式可以转化为

以及有如下等价关系

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

我们现在对$\frac{\mathbb E[e^{s\sum_{i=1}^nX_i}]}{e^{sn(t+2a )}}$进行处理,注意$X_1,…,X_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$

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

对其取对数可得

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

所以当$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$,只要考虑分子即可

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

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

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

将这个式子带入原式可得

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

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

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

这是因为

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

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

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

Hoeffding不等式的证明

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

从而

所以

由引理2的推论可知可知

从而

从而结论得证。

总结

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

参考资料:

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

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