一致稳定性泛化界

假设与结论 ​

设确定性学习算法 $A$ 接受 $m$ 个 IID 样本 $S\sim D^m$，损失 $\ell (A(S),z)\in [0,M]$。若任意只相差一个样本的 $S,S^{\prime }$ 与任意测试点 $z$ 都满足

$$|\ell (A(S),z)-\ell (A(S^{\prime }),z)|\le \beta ,$$

则称 $A$ 是 $\beta$-一致稳定的。记泛化间隙

$$\mathrm{\Phi }(S)=R_D(A(S))-{\hat{R}}_S(A(S)).$$

其期望满足

$$|{\mathbb{E}}_S\mathrm{\Phi }(S)|\le \beta .$$

此外，直接使用有界差分可得一个经典、但未必最紧的高概率版本：以至少 $1-\delta$ 的概率

$$\mathrm{\Phi }(S)\le \beta +(2m\beta +M)\sqrt{\frac{\log \left(1/\delta \right)}{2m}}.$$

若采用“删除一个点”而非“替换一个点”的稳定性定义，或对双边绝对间隙取界，常数会改变；应从相应定义重新计算，而非拼接不同版本。

期望界的换一法 ​

写 $S=(Z_1,\dots ,Z_m)$，再取独立副本 $Z_i^{\prime }$，令 $S^{(i)}$ 把 $Z_i$ 替换为 $Z_i^{\prime }$。由于 $(S^{(i)},Z_i)$ 与 $(S,Z_i^{\prime })$ 同分布，

$$\begin{array}{rl}\mathbb{E}\mathrm{\Phi }(S)& =\frac{1}{m}\sum _i\mathbb{E}[\ell (A(S),Z_i^{\prime })-\ell (A(S),Z_i)]\\ & =\frac{1}{m}\sum _i\mathbb{E}[\ell (A(S),Z_i^{\prime })-\ell (A(S^{(i)}),Z_i^{\prime })].\end{array}$$

每一项绝对值至多 $\beta$，故结论成立。这里没有对整个假设类取上确界；控制来自算法输出随单点变化不大。

从期望到尾界 ​

将 $S$ 的第 $i$ 点替换后，总体风险项至多改变 $\beta$。经验风险的其余 $m-1$ 项各至多改变 $\beta$，平均后不超过 $\beta$；被替换的那一项还可能改变 $M/m$。因此

$$|\mathrm{\Phi }(S)-\mathrm{\Phi }(S^{(i)})|\le 2\beta +\frac{M}{m}.$$

对 $m$ 个坐标应用 有界差分不等式公理库有界差分不等式McDiarmid inequality · 有界差异不等式独立输入的函数若对单个坐标不敏感，其输出便以次高斯速度集中在期望附近。，再代入 $\mathbb{E}\mathrm{\Phi }\le \beta$，就得到上述高概率式。若 $\beta =c/m$，尾项仍是 $O((c+M)\sqrt{\log \left(1/\delta \right)/m})$；现代稳定性尾界能在某些条件下更好地保留 $\beta$ 的尺度，但不应冒充这条朴素 McDiarmid 推导。

具体例子：强凸正则化 ERM ​

考虑

$$A(S)=\arg \underset{w}{min}\{\frac{1}{m}\sum _{i=1}^m\ell (w,Z_i)+\frac{\lambda }{2}\Vert w{\Vert }_2^2\},$$

且 $\ell (\cdot ,z)$ 对 $w$ 凸并 $L$-Lipschitz。两个相邻样本对应的目标都为 $\lambda$-强凸；比较彼此最优性并相加，可得解的距离为 $O(L/(\lambda m))$。再用损失的 Lipschitz 性，得到

$$\beta =O\left(\frac{L^2}{\lambda m}\right).$$

图像是：正则项把目标函数底部做成有曲率的碗，单个样本只占 $1/m$ 权重，无法把极小点推得太远。参数距离本身并不是稳定性；必须再由 Lipschitz 损失把参数变化转换为任意测试点上的损失变化。

边界 ​

若 $\beta$ 不随 $m$ 衰减，期望间隙不会被迫趋零。无界损失也使经典尾界失去 $M$。随机算法还需明确稳定性是对同一随机种子耦合、对内部随机性取期望，还是联合高概率陈述；三者不能互换。本路线与 Rademacher 泛化界公理库Rademacher 泛化界Rademacher generalization bound用样本上的 Rademacher 复杂度给出对整个有界实值函数类同时成立的数据依赖总体风险上界。的区别在于，前者评价具体算法的敏感性，后者评价整个函数类在样本上的波动。

参考资料

• Olivier Bousquet and André Elisseeff, “Stability and Generalization,” JMLR, 2002.
• Vitaly Feldman and Jan Vondrák, work on high-probability generalization bounds for uniformly stable algorithms.