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,?,N$, $?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{～}_{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～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不等式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。