D.7 McDiarmid 不等式

D.7 McDiarmid 不等式

下面是本节的主要结果。其证明利用了 Azuma 不等式。

定理 D.8(McDiarmid 不等式)$Let{X}_1,\dots ,X_m\in {\mathfrak{X}}^{m}beasetofm\ge 1independent$ 随机变量，并假设存在 $c_1,\dots ,c_m>0$ 使得 $f:{\mathcal{X}}^m\to \mathbb{R}$ 满足以下条件:

$$\left|f\left(x_1,\dots ,x_i,\dots ,x_m\right)-f\left(x_1,\dots ,x_i^{\prime },\dots x_m\right)\right|\le c_i,\text{\hspace{1em}(D.15)}$$

对于所有 $i\in \left[m\right]$ 和任意点 $x_1,\dots ,x_m,x_i^{\prime }\in \mathfrak{X}$ 。设 $f\left(S\right)$ 表示 $f\left(X_1,\dots ,X_m\right)$ ，那么，对于所有 $ϵ>0$ ，以下不等式成立:

$$\mathbb{P}\left[f\left(S\right)-\mathbb{E}\left[f\left(S\right)\right]\ge ϵ\right]\le \exp \left(\frac{-2{ϵ}^2}{\sum _{i=1}^m{c}_i^2}\right)\text{\hspace{1em}(D.16)}$$ $$\mathbb{P}\left[f\left(S\right)-\mathbb{E}\left[f\left(S\right)\right]\le -ϵ\right]\le \exp \left(\frac{-2{ϵ}^2}{\sum _{i=1}^m{c}_i^2}\right).\text{\hspace{1em}(D.17)}$$

证明:定义一个随机变量序列 $V_k,k\in \left[m\right]$ ，如下:$V=f\left(S\right)-\mathbb{E}\left[f\left(S\right)\right]$ ，$V_1=\mathbb{E}\left[V\mid X_1\right]-\mathbb{E}\left[V\right]$ ，对于 $k>1$ ，

$$V_k=\mathbb{E}\left[V\mid X_1,\dots ,X_k\right]-\mathbb{E}\left[V\mid X_1,\dots ,X_{k-1}\right].$$

注意到 $V=\sum _{k=1}^m{V}_k$。此外，随机变量 $\mathbb{E}\left[V\mid X_1,\dots ,X_k\right]$ 是 $X_1,\dots ,X_k$ 的一个函数。因此，给定 $X_1,\dots ,X_{k-1}$ 并取其期望为：

$$\mathbb{E}\left[\mathbb{E}\left[V\mid X_1,\dots ,X_k\right]\mid X_1,\dots ,X_{k-1}\right]=\mathbb{E}\left[V\mid X_1,\dots ,X_{k-1}\right]$$

这意味着 $\mathbb{E}\left[V_k\mid X_1,\dots ,X_{k-1}\right]=0$。因此，序列 ${\left(V_k\right)}_{k\in \left[m\right]}$ 是一个马尔可夫差分序列。接下来，观察到，由于 $\mathbb{E}\left[f\left(S\right)\right]$ 是一个标量，$V_k$ 可以表示如下：

$$V_k=\mathbb{E}\left[f\left(S\right)\mid X_1,\dots ,X_k\right]-\mathbb{E}\left[f\left(S\right)\mid X_1,\dots ,X_{k-1}\right].$$

因此，我们可以通过以下方式为 $V_k$ 定义上界 $W_k$ 和下界 $U_k$：

$$W_k=\underset{x}{\sup }\mathbb{E}\left[f\left(S\right)\mid X_1,\dots ,X_{k-1},x\right]-\mathbb{E}\left[f\left(S\right)\mid X_1,\dots ,X_{k-1}\right]$$ $$U_k=\underset{x}{\inf }\mathbb{E}\left[f\left(S\right)\mid X_1,\dots ,X_{k-1},x\right]-\mathbb{E}\left[f\left(S\right)\mid X_1,\dots ,X_{k-1}\right].$$

现在，根据 (D.15)，对于任何 $k\in \left[m\right]$，以下关系成立：

$$W_k-U_k=\underset{x,x^{\prime }}{\sup }\mathbb{E}\left[f\left(S\right)\mid X_1,\dots ,X_{k-1},x\right]-\mathbb{E}\left[f\left(S\right)\mid X_1,\dots ,X_{k-1},x^{\prime }\right]\le c_k,\text{\hspace{1em}(D.18)}$$

因此，$U_k\le V_k\le U_k+c_k$。考虑到这些不等式，我们可以将阿祖玛不等式应用于 $V=\sum _{k=1}^m{V}_k$，这正好得出 (D.16) 和 (D.17)。

McDiarmid 不等式在本书中的多个证明中都有使用。它可以从稳定性的角度理解：如果改变其任何一个参数仅在有限的范围内影响 $f$，那么 $f$ 相对于其均值的偏差可以被指数界定。还要注意，Hoeffding 不等式（定理 D.2）是 McDiarmid 不等式的一个特例，其中 $f$ 定义为 $f:\left(x_1,\dots ,x_m\right)\mapsto \frac{1}{m}\sum _{i=1}^m{x}_i.$