算法稳定性

概念图像 ​

容量方法问“整个假设类能做多少事”，稳定性方法问“这个算法看到一条不同数据后会改变多少”。即使候选类很大，一个对单点扰动迟钝的算法仍可能泛化；反过来，输出对单个样本剧烈翻转，会把训练集偶然性带到预测中。

相邻样本与统一稳定性 ​

令 $S=(z_1,\dots ,z_m)$，$S^{(i)}$ 表示把第 $i$ 个样本替换为独立点 $z_i^{\prime }$ 后的样本。学习算法 $A$ 对损失 $\ell$ 具有 ${\beta }_m$-uniform stability，若对所有相邻 $S,S^{(i)}$、所有测试点 $z$，

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

“uniform”指最坏样本与最坏测试点都受控。hypothesis stability 常只对随机训练点或测试点取期望；pointwise hypothesis stability 又有不同量词。它们的结论与常数不能混用。

为什么会控制期望泛化 ​

设 $Z^{\prime }$ 独立于 $S$。利用交换对称性，把总体风险中的 $Z^{\prime }$ 与经验风险中的 $Z_i$ 配对：

$$\mathbb{E}[R(A(S))-{\hat{R}}_S(A(S))]=\frac{1}{m}\sum _i\mathbb{E}[\ell (A(S),Z_i^{\prime })-\ell (A(S),Z_i)].$$

把第一项中的训练样本替换为 $S^{(i)}$ 后，两项分布可对齐；剩下的损失差由稳定性界住。因此绝对期望泛化间隙至多为 ${\beta }_m$（具体替换/删除约定可能产生常数差）。高概率结论还需要损失有界与集中工具。

强凸正则化例子 ​

对 $\lambda$-强凸正则化 ERM，若单点损失关于参数是 $L$-Lipschitz，替换一个样本只以 $1/m$ 改变目标。强凸性把目标扰动转成参数距离，再由 Lipschitz 性转成损失变化，典型得到 ${\beta }_m=O(L^2/(\lambda m))$。参数变化小只是中间步骤；没有 Lipschitz 连接，不能直接声称损失稳定。

边界与辨析 ​

随机算法必须说明如何比较内部随机性：固定同一随机种子的耦合、对随机性取期望，或给高概率稳定性，会产生不同定义。稳定性也不是算法正确性公理库算法正确性Algorithm correctness · Partial and total correctness所有合法执行都符合规格，并在完全正确时保证终止。：一个稳定地输出常数的算法可以泛化得很稳定，却有很高风险。删除式与替换式相邻关系相近但非恒等，使用定理时需固定协议。

参考资料

• Olivier Bousquet, André Elisseeff, Stability and Generalization, JMLR, 2002.
• Vitaly Feldman, Jan Vondrák, High Probability Generalization Bounds for Uniformly Stable Algorithms, COLT, 2019.