ml-Hoeffding's Inequality

Hoeffding’s Inequality

霍夫丁不等式 ($\mathbb P(\Big|v -\mu\Big|\ge \epsilon ) \le 2e^{-2n\epsilon^2}$ ) 的意义：

当n 很大时，抽样的期望$v$可以逼近样本本身的期望值$\mu$（一般是未知），例如：
$n =1000, 误差 \epsilon= 0.05， \mu -0.05 \le v \le \mu+0.05,\mathbb P(|v-\mu|\ge\epsilon)\le2e^{-2*1000*0.05^2} = 0.013$
注意这里只是概率上说明$v$ 和$\mu$的误差关系，真实情况$v$ 的取值是随意的。所以霍夫丁不等式只是告诉我们在一定误差范围内，取得我们想要的$\mu$的估计值$v$的概率可能性，而不是一定。（关于误差的介绍以后会相继推出）

常用的不等式证明

$\sigma$和$\mu$是样本本身的方差和均值，$X$是随机变量，$\epsilon$是任意整数。

$\mathbb E (x) = \int_{-\infty}^{\infty}(x-\mu)f(x)dx =\mu$

$\mathbb D (x) = \int_{-\infty}^{\infty}(x-\mu)^2f(x)dx = \sigma^2$

切比雪夫不等式为： $ \Large \mathbb P [|X-\mu|\ge\epsilon] \le \Large \frac{\sigma^2}{\epsilon^2}$
$ \Large P [|X-\mu|\ge\epsilon] =\Large \int_{|X-\mu|\ge\epsilon}f(X)dX\le\int_{|X-\mu|\ge\epsilon}\frac{|X-\mu|^2}{\epsilon^2}f(X)dX \ \Large \le\frac{1}{\epsilon^2}\int_{-\infty}^{\infty}(X-\mu)^2f(X)dX=\frac{\sigma^2}{\epsilon^2}$

引理 1

同理可以证明马尔科夫不等式，$t$为非负随机变量:

$\Large P [t\ge\alpha] =\Large \int_{t\ge\alpha}f(t)dt\le\int_{t\ge\alpha}\frac{t}{\alpha}f(t)dt\le\frac{1}{\alpha}\int_{0}^{\infty}f(t)dt=\frac{E(t)}{\alpha}$

即： $\Large P [t\ge\alpha] \le \frac{E(t)}{\alpha}$

引理$2^{[1]}$

$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}$

从而结论得证。