UA MATH567 高維統(tǒng)計(jì)I 概率不等式12 McDiarmid不等式

這一講我們介紹基于Lipschitz性導(dǎo)出概率不等式的思路，這個(gè)思路在下一講正式進(jìn)入隨機(jī)向量之后應(yīng)用非常廣泛。但這一講我們先不正式引入Lipschitz函數(shù)的概念，我們介紹一個(gè)與之相關(guān)的概念，隨機(jī)變量序列的Lipschitz組合(Lipschitz combinations)。

Lipschitz組合 假設(shè)$X_1,?,X_n$是一列獨(dú)立的，值域分別為$R_1,?,R_n$的隨機(jī)變量，假設(shè)$F:R_1\times ?\times R_n\to \mathbb{R}$是一個(gè)實(shí)值函數(shù)滿足$?c_i>0$，$?x_i,x_i^{\prime }$，當(dāng)其他自變量不變時(shí)，有
$$|F(x_1,?,x_i,?,x_n)?F(x_1,?,x_i^{\prime },?,x_n)|\le c_i$$

我們就稱$F(X_1,?,X_n)$是$X_1,?,X_n$的一個(gè)Lipschitz組合。

評(píng)注 Lipschitz組合可以理解成有界的一種推廣，我們回顧一下Hoeffding不等式：假設(shè)$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)$$

也就是說(shuō)有界的隨機(jī)變量，他們的tail probability的階大概是$e^{?t^2}$。如果考慮
$$F(X_1,?,X_N)=\sum _{i=1}^N(X_i?E{X}_i)$$

要使$F(X_1,?,X_N)$成為L(zhǎng)ipschitz組合的充要條件是$X_i$有界，于是Lipschitz組合可以看做是對(duì)有界性的一種推廣，并且我們可以預(yù)期Lipschitz組合tail probability的階也大概是$e^{?t^2}$，如果這個(gè)猜測(cè)成立，那么Hoeffding不等式的結(jié)果就不僅僅局限于隨機(jī)變量的和或者線性組合了，而是對(duì)更一般的Lipschitz組合都成立，這個(gè)結(jié)果由下面的McDiarmid不等式給出。

McDiarmid不等式 $F(X)=F(X_1,?,X_n)$為$X_1,?,X_n$的Lipschitz組合，則$?C,c>0$
$$P(|F(X)?EF(X)|\ge \lambda {\sigma }^2)\le C{e}^{?c{\lambda }^2}$$

其中${\sigma }^2={\sum }_{i=1}^n{c}_i^2$。

證明
這里展示單邊的證明方法：
$$P(F(X)?EF(X)\ge \lambda {\sigma }^2)\le C{e}^{?c{\lambda }^2}$$

另一邊的證明方法類似。

與前面所有基于Markov不等式證明的概率不等式類似，我們計(jì)算$E{e}^{tF(X)}$，這個(gè)期望計(jì)算的難點(diǎn)在于$F(X)$是同時(shí)和$X_1,?,X_n$有關(guān)的，也就是不存在可以把$F(X)$拆分成分別用$X_1,?,X_n$表示的分量的方法，這就與上一講介紹的Azuma不等式的證明很類似了，Azuma不等式證明中，因?yàn)殡S機(jī)變量之間的dependence，我們用的條件期望來(lái)處理，在McDiarmid不等式的證明中我們也可以用類似的技術(shù)。定義
$$\begin{gathered} {\mathcal{F}}_n=\sigma (\{X_1,X_2,?,X_n\}) \\ {Y}_n=E[e^{tF(X)}|{\mathcal{F}}_{n?1}] \end{gathered}$$

則
$$E{e}^{tF(X)}=E[Y_n]=E[Y_n|{\mathcal{F}}_n]$$

在Azuma不等式的證明中，做了這個(gè)構(gòu)造之后，下一步我們要做的是試圖對(duì)條件期望用Hoeffding不等式，這里我們也采用這個(gè)技術(shù)，先用centering技巧對(duì)$F(X)$做一個(gè)分解：
$$F(X)=E[F(X)|{\mathcal{F}}_{n?1}]+(F(X)?E[F(X)|{\mathcal{F}}_n])$$

所以
$$\begin{gathered} Y_n=E[e^{t\{E[F(X)|{\mathcal{F}}_{n?1}]+(F(X)?E[F(X)|{\mathcal{F}}_n])\}}|{\mathcal{F}}_{n?1}] \\ =e^{tE[F(X)|{\mathcal{F}}_{n?1}]}E[e^{t(F(X)?E[F(X)|{\mathcal{F}}_n])}|{\mathcal{F}}_{n?1}] \end{gathered}$$

對(duì)于$F(X)?E[F(X)|{\mathcal{F}}_n]$，它的含義就相當(dāng)于是固定$x_1,?,x_{n?1}$，只允許$x_n$變化，根據(jù)Lipschitz組合的定義，它的絕對(duì)值的上界是$c_n$，于是根據(jù)Hoeffding不等式，
$$E[e^{t(F(X)?E[F(X)|{\mathcal{F}}_n])}|{\mathcal{F}}_{n?1}]\le e^{a_n{t}^2{c}_n^2},?a_n>0$$

這樣我們就獲得了一個(gè)遞推式
$$\frac{E[Y_n|{\mathcal{F}}_n]}{E[Y_n|{\mathcal{F}}_{n?1}]}\le e^{a_n{t}^2{c}_n^2},?a_n>0$$

類似Azuma不等式的證明，根據(jù)這個(gè)遞推式我們可以得到
$$E{e}^{t(F(X)?EF(X))}\le e^{A{t}^2{c}_n^2},A=\underset{n}{\max }{a}_n$$

最后用一下Markov不等式就可以了。

總結(jié)

以上是生活随笔為你收集整理的UA MATH567 高维统计I 概率不等式12 McDiarmid不等式的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。