Ch1 再论集中不等式

1. 三个不等式放在一起

Hoeffding

设 \(Z_i\in[a_i,b_i]\) 相互独立，则

$$\mathbb P\left( \left| \sum_{i=1}^n(Z_i-\mathbb EZ_i) \right|>t \right) \le 2\exp\left( -\frac{2t^2}{\sum_{i=1}^n(b_i-a_i)^2} \right).$$

它只利用每个随机变量的取值范围。

证明方式：

首先使用Markov不等式，将问题转化为对于\(E(e^{s(Z-EZ_i)})\)的控制，然后构造对数

使用对数矩母函数，求一次，二次导数，然后做概率测度的变换，将其转化为一个方差的控制。

不失一般性，可以考虑随机变量处于[0,1]

---

McDiarmid

设

$$F=f(Z_1,\dots,Z_n),$$

且改变第 \(i\) 个输入最多使函数值改变 \(c_i\)：

$$|f(z)-f(z^{(i)})|\le c_i.$$

那么

$$\mathbb P\left( |F-\mathbb EF|>t \right) \le 2\exp\left( -\frac{2t^2}{\sum_{i=1}^n c_i^2} \right).$$

它不要求 \(f\) 是求和，只要求每一个样本对最终结果的影响有限。

其中Amuza不等式是其中的一个特殊情况，其核心在于构造Doob-鞅，一系列的随机变量，然后证明每个部分的指数期望都可以被控制住，进而再次使用Markov不等式。

---

Bernstein

设

$$\mathbb EZ_i=0,\qquad |Z_i|\le c,$$

记

$$V=\sum_{i=1}^n\operatorname{Var}(Z_i).$$

则

$$\mathbb P\left( \left|\sum_{i=1}^nZ_i\right|>t \right) \le 2\exp\left( -\frac{t^2}{2V+\frac{2ct}{3}} \right).$$

它同时使用：

$$\text{真实方差 }V \qquad\text{和}\qquad \text{绝对上界 }c.$$

---

2. Hoeffding 是 McDiarmid 的特殊情况

取

$$f(Z_1,\dots,Z_n)=\sum_{i=1}^n Z_i.$$

如果 \(Z_i\in[a_i,b_i]\)，只替换第 \(i\) 个变量，则

$$\left| f(z)-f(z^{(i)}) \right| = |z_i-z_i'| \le b_i-a_i.$$

所以 McDiarmid 中

$$c_i=b_i-a_i.$$

代入后得到

$$\mathbb P\left( \left| \sum_iZ_i-\mathbb E\sum_iZ_i \right|>t \right) \le 2\exp\left( -\frac{2t^2}{\sum_i(b_i-a_i)^2} \right),$$

正好就是 Hoeffding。

因此：

$$\boxed{ \text{对线性求和而言，McDiarmid 基本就是 Hoeffding。} }$$

McDiarmid 的优势不是在这个情况下给出更小的界，而是允许研究非线性统计量。

---

3. McDiarmid 比 Hoeffding 一般在哪里

例如在学习理论中常研究

$$F(S) = \sup_{h\in\mathcal H} \left| \widehat R_S(h)-R(h) \right|.$$

这里

$$\widehat R_S(h) = \frac1n\sum_{i=1}^n\ell(h,Z_i),$$

但外面还有一个关于 \(h\) 的上确界。因此 \(F(S)\) 本身不是简单的随机变量平均。

假设损失满足

$$0\le \ell(h,z)\le 1.$$

把样本 \(Z_i\) 换成 \(Z_i'\)，对于任意 \(h\)，

$$\left| \widehat R_S(h)-\widehat R_{S'}(h) \right| \le\frac1n.$$

上确界的变化也不超过 \(1/n\)，所以

$$c_i=\frac1n.$$

McDiarmid 给出

$$\mathbb P\left( |F(S)-\mathbb EF(S)|>t \right) \le 2e^{-2nt^2}.$$

Hoeffding 无法直接处理这个 \(F(S)\)，因为它不是固定的独立随机变量之和。

所以 McDiarmid 回答的是：

一个复杂的样本统计量，只要对单个样本不敏感，是否仍然集中？

答案是肯定的。

---

4. McDiarmid 和 Bernstein 谁更精确

在随机变量求和的情况下，McDiarmid 通常和 Hoeffding 一样，只利用最坏情况变化，而 Bernstein 还利用方差。因此如果方差很小，Bernstein 通常更精确。

假设

$$Z_i\in[-c,c], \qquad \sigma^2=\frac1n\sum_i\operatorname{Var}(Z_i).$$

对于平均值

$$\overline Z=\frac1n\sum_iZ_i,$$

Hoeffding 或 McDiarmid 给出

$$\mathbb P(|\overline Z-\mathbb E\overline Z|>t) \le 2\exp\left(-\frac{nt^2}{2c^2}\right).$$

Bernstein 给出

$$\mathbb P(|\overline Z-\mathbb E\overline Z|>t) \le 2\exp\left( -\frac{nt^2}{2\sigma^2+\frac{2ct}{3}} \right).$$

当

$$\sigma^2\ll c^2$$

且 \(t\) 不大时，Bernstein 的分母近似为

$$2\sigma^2,$$

远小于 Hoeffding 或 McDiarmid 的

$$2c^2.$$

因此 Bernstein 明显更强。

---

5. 一个极端例子

设

$$X_i\sim\operatorname{Bernoulli}(p), \qquad Z_i=X_i-p.$$

虽然 \(X_i\in[0,1]\)，但

$$\operatorname{Var}(X_i)=p(1-p).$$

当 \(p=0.001\) 时，

$$p(1-p)\approx0.001.$$

Hoeffding 和 McDiarmid 只知道区间长度是 \(1\)，因此都给出

$$2e^{-2nt^2}.$$

Bernstein 对小 \(t\) 近似给出

$$2\exp\left( -\frac{nt^2}{2p(1-p)} \right) \approx 2e^{-500nt^2}.$$

差别巨大。

原因是：

• Hoeffding/McDiarmid 认为每个样本都可能在整个区间内剧烈波动；
• Bernstein 知道 \(X_i\) 几乎总是 \(0\)，实际方差很小。