有界差分不等式

定理 ​

设 $X_1,\dots ,X_m$ 相互独立，$f:{\mathcal{X}}_1\times \cdots \times {\mathcal{X}}_m\to \mathbb{R}$ 满足坐标有界差分条件：对每个 $i$，只要 $x,x^{\prime }$ 除第 $i$ 个坐标外完全相同，就有

$$|f(x)-f(x^{\prime })|\le c_i.$$

那么对任意 $t>0$，

$$\text{Pr}(f(X)-\mathbb{E}f(X)\ge t)\le \exp (-\frac{2t^2}{\sum _i{c}_i^2}).$$

对 $-f$ 应用同一结论并使用并集界公理库并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，得到

$$\text{Pr}(|f(X)-\mathbb{E}f(X)|\ge t)\le 2\exp (-\frac{2t^2}{\sum _i{c}_i^2}).$$

$c_i$ 控制的是在其他坐标任意固定时，第 $i$ 个输入被最坏替换所能造成的变化；平均变化小、典型变化小都不足以代替这一条件。

证明图像 ​

逐步揭示 $X_1,\dots ,X_m$，令

$$M_i=\mathbb{E}[f(X)\mid X_1,\dots ,X_i].$$

这是从先验期望 $M_0=\mathbb{E}f(X)$ 走到实际值 $M_m=f(X)$ 的 Doob 鞅公理库鞅Martingale · Submartingale · Supermartingale在当前全部信息下，下一步条件均值等于当前值的可积适应过程。。只更换 $X_i$ 最多使最终函数值移动 $c_i$，因而第 $i$ 个条件期望增量的取值区间长度至多 $c_i$。对每个增量应用 Hoeffding 引理，利用条件指数矩逐层相乘，再优化 Chernoff 参数，就得到指数 $-2t^2/\sum _i{c}_i^2$。所以定理的核心不是 $f$ 可加，而是每个独立坐标都只能推动输出一小步。

当 $f(x)=\sum _i{x}_i$ 且 $x_i\in [a_i,b_i]$ 时，可取 $c_i=b_i-a_i$，结论退化为Hoeffding 不等式公理库Hoeffding 不等式Hoeffding's inequality独立有界随机变量和偏离期望的概率以平方偏差的指数速度衰减。。有界差分因此覆盖了任意低敏感函数，而不只覆盖随机变量之和。

例子：经验复杂度 ​

设函数类 $\mathcal{F}$ 中每个 $g:\mathcal{Z}\to [0,1]$，定义

$$F(S)=\underset{g\in \mathcal{F}}{sup}\frac{1}{m}\sum _{j=1}^{m}g(Z_j).$$

替换一个样本 $Z_i$ 时，对每个 $g$ 的平均至多改变 $1/m$；取上确界也不会把差放大，故 $c_i=1/m$。于是

$$\text{Pr}(F(S)-\mathbb{E}F(S)\ge t)\le e^{-2m{t}^2}.$$

这类统计量通常无法写成独立项之和，却仍因单点影响小而集中，正是有界差分在算法稳定性和经验复杂度分析中的价值。

边界 ​

若所有坐标由同一个随机变量复制而来，独立性失败，$m$ 个看似微小的坐标差分不能带来 $e^{-cm}$ 的集中。若 $f$ 对某个坐标无界敏感，例如样本最大值来自无界分布，也不存在有限 $c_i$。更锐利的“方差敏感”版本可使用 Efron–Stein、Bernstein 或 self-bounding 方法；它们是条件不同的强化，不应通过把平均灵敏度代入本定理来伪造。

样本均值提供常数检查。若 $f(X)=m^{-1}\sum _i{X}_i$ 且 $X_i\in [0,1]$，替换第 $i$ 个坐标至多改变 $1/m$，故 $\sum _i{c}_i^2=1/m$，双边界成为 $2e^{-2m{t}^2}$，与 Hoeffding 完全一致。若误把 $c_i$ 写成平均变化 $1/(2m)$，指数会虚假增强四倍。

当各坐标影响不等时，平方和会突出敏感坐标。一个坐标的 $c_1=1$、其余一千个各为 $0.001$ 时，$\sum _i{c}_i^2\approx 1.001$；大量微小坐标并不能抵消单个可能改变整个输出的输入。这一形状也提示算法设计应限制最坏单点影响，而不只是报告平均稳定。

参考资料

• Colin McDiarmid, “On the Method of Bounded Differences,” Surveys in Combinatorics, 1989.
• Stéphane Boucheron, Gábor Lugosi, Pascal Massart, Concentration Inequalities, Oxford University Press, 2013, Ch. 6.