UA MATH567 高维统计I 概率不等式1 Hoeffding不等式与Chernoff不等式

• Hoeffding不等式
• Chernoff不等式

MATH 564系列我们已经介绍了几个基本的概率不等式：Markov不等式、Chebyshev不等式、Chernoff不等式，这一类不等式有一个共同的名字，叫concentration inequalities，因为它们反映的是概率集中到分布的中心（比如均值）的程度，所以我觉得翻译成集中度不等式是还可以的，中文的wiki用的是集中不等式，我觉得含义也差不多。在概率不等式0中我们讨论了Chebyshev不等式，它在大样本时非常不sharp，所以这一讲的目标是基于Markov不等式推出更sharp一点的不等式，也就是Hoeffding不等式与Chernoff不等式。

Hoeffding不等式

假设$X_i\in [m_i,M_i],i=1,\cdots ,N$, $\forall t>0$, 下面的不等式被称为Hoeffding不等式，
$$P\left(\sum _{i=1}^N(X_i-E{X}_i)\ge t\right)\le \exp \left(-\frac{2t^2}{{\sum }_{i=1}^N(M_i-m_i{)}^2}\right)$$

完整的证明可以参考Hoeffding (1963)的文章，这里证明一个特殊情况，$X_i{\sim }_{iid}Ber(1/2)$ (对称Bernoulli分布)：
$$P\left(\sum _{i=1}^N{a}_i{X}_i\ge t\right)\le \exp \left(-\frac{t^2}{2{\sum }_{i=1}^N{a}_i^2}\right)$$

证明这个特例是因为接下来用到的证明方法是用来证明类似Hoeffding不等式的一般性思路。

证明
考虑函数$g(t)=e^{\lambda t}$，对随机变量${\sum }_{i=1}^N{a}_i{X}_i$使用Markov不等式，
$$P\left(\sum _{i=1}^N{a}_i{X}_i\ge t\right)\le e^{-\lambda t}E\exp \left(\lambda \sum _{i=1}^N{a}_i{X}_i\right)$$

因为$\lambda$的任意性，我们可以选择一个最小的上界：
$$\underset{\lambda }{\min }{e}^{-\lambda t}E\exp \left(\lambda \sum _{i=1}^N{a}_i{X}_i\right)$$

接下来我们要做的就是找到这个最值，计算
$$\begin{gathered} e^{-\lambda t}E\exp \left(\lambda \sum _{i=1}^N{a}_i{X}_i\right)=e^{-\lambda t}\prod _{i=1}^{N}E{e}^{\lambda a_i{X}_i} \\ =e^{-\lambda t}\prod _{i=1}^N\frac{e^{\lambda a_i}+e^{-\lambda a_i}}{2}\le e^{-\lambda t}\prod _{i=1}^N{e}^{{\lambda }^2{a}_i^2/2} \\ =\exp \left(-\lambda t+\frac{{\lambda }^2}{2}\sum _{i=1}^N{a}_i^2\right) \end{gathered}$$

需要注意的是第二行我们把这个上界又放大了一点，主要的目的是找一个更容易计算最小值的形式：
$$\min \exp \left(-\lambda t+\frac{{\lambda }^2}{2}\sum _{i=1}^N{a}_i^2\right)=e^{-\lambda t}E\exp \left(\lambda \sum _{i=1}^N{a}_i{X}_i\right)$$

证毕

Hoeffding不等式在统计学习中具有广泛的应用，比如监督学习理论中Principle of empirical risk minimization的一致性推导，Boosting的运行次数估计等。

Chernoff不等式

在UA MATH564 概率论 概率不等式中，我们介绍了Chernoff上界。给定具有某种特定分布形式的随机变量，我们可以用Legendre变换的思路计算出随机变量尾部概率的Chernoff上界。Chernoff不等式是Chernoff上界的一个特例，考虑互相独立的Bernoulli变量$X_i\sim Ber(p_i)$，定义$S_N={\sum }_{i=1}^N{X}_i$，$\mu =E{S}_N$，对于$t>\mu$，
$$P(S_N\ge t)\le e^{-\mu }(e\mu /t{)}^t$$对于$t<\mu$，
$$P(S_N\le t)\le e^{-\mu }(e\mu /t{)}^t$$

为了展示证明方法，这里给出上界的证明，当然也可以用564介绍的计算Chernoff bound的方法。

证明
根据Hoeffding不等式的证明过程，
$$P(S_N\ge t)\le e^{-\lambda t}\prod _{i=1}^{N}E{e}^{\lambda X_i}$$

下面计算：
$$\prod _{i=1}^{N}E{e}^{\lambda X_i}=\prod _{i=1}^N[1+(e^{\lambda }-1)p_i]\le \prod _{i=1}^N\exp [(e^{\lambda }-1)p_i]=\exp [(e^{\lambda }-1)\mu ]$$

中间一步用了Bernoulli不等式。因此
$$P(S_N\ge t)\le e^{-\lambda t}\exp [(e^{\lambda }-1)\mu ]$$

这个上界在$\lambda =\ln (t/\mu )$时取最小值，因此
$$P(S_N\ge t)\le e^{-\lambda t}\prod _{i=1}^{N}E{e}^{\lambda X_i}$$

证毕

Hoeffding不等式与Chernoff不等式它们的上界关于$t$都是指数级递减的，这种上界就比Chebyshev那种二次的递减更sharp。

总结

以上是生活随笔为你收集整理的UA MATH567 高维统计I 概率不等式1 Hoeffding不等式与Chernoff不等式的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。