一致稳定性泛化界 | Codeboy's Blog

形式陈述

假设与结论

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

|\ell(A(S),z)-\ell(A(S'),z)|\le\beta,

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

\Phi(S)=R_D(A(S))-\widehat R_S(A(S)).

其期望满足

|\mathbb E_S\Phi(S)|\le\beta.

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

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

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

期望界的换一法

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

\begin{aligned} \mathbb E\Phi(S) &=\frac1m\sum_i\mathbb E\bigl[\ell(A(S),Z_i')-\ell(A(S),Z_i)\bigr]\\ &=\frac1m\sum_i\mathbb E\bigl[\ell(A(S),Z_i')-\ell(A(S^{(i)}),Z_i')\bigr]. \end{aligned}

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

从期望到尾界

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

|\Phi(S)-\Phi(S^{(i)})|\le 2\beta+\frac Mm.

对 $m$ 个坐标应用有界差分不等式，再代入 $\mathbb E\Phi\le\beta$ ，就得到上述高概率式。若 $\beta=c/m$ ，尾项仍是 $O((c+M)\sqrt{\log(1/\delta)/m})$ ；现代稳定性尾界能在某些条件下更好地保留 $\beta$ 的尺度，但不应冒充这条朴素 McDiarmid 推导。

直觉

一致稳定性不控制整个假设类，而是直接询问：替换一个训练点，会让最终算法在任意测试点上的损失改变多少？若每个样本只能轻微推动输出，那么训练集中的自我评价与独立测试点评价就难以系统性分离。

期望证明用 ghost point 交换训练点与新样本，使泛化间隙化成相邻数据集输出的损失差；高概率证明则进一步计算 $\Phi(S)$ 对每个样本坐标的敏感度。两步分别支付 $\beta$ 与 $2\beta+M/m$ ，不能把期望结论直接当作尾界。

例子与边界

强凸正则化 ERM

考虑

A(S)=\arg\min_w\left\{\frac1m\sum_{i=1}^m\ell(w,Z_i)+\frac\lambda2\|w\|_2^2\right\},

且 $\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 泛化界的区别在于，前者评价具体算法的敏感性，后者评价整个函数类在样本上的波动。

推论与应用

强凸正则化 ERM 中，单点只占目标的 $1/m$ 权重，强凸性把极小点位移控制为 $O(L/(\lambda m))$ ，再由 Lipschitz 损失得到 $\beta=O(L^2/(\lambda m))$ 。这把优化曲率直接转成算法依赖的泛化保证。

稳定性特别适合分析由具体训练过程选择的模型，而不必对整个大函数类取上确界。正则化、早停、随机梯度与数据依赖先验可产生不同稳定性概念；每次都要声明邻接方式、随机性耦合和损失范围，才能选择对应期望或高概率定理。

参考资料

Olivier Bousquet and André Elisseeff, “Stability and Generalization,” Journal of Machine Learning Research 2, 2002, pp. 499–526.
Vitaly Feldman and Jan Vondrák, High Probability Generalization Bounds for Uniformly Stable Algorithms with Nearly Optimal Rate, Proceedings of Machine Learning Research 99 (COLT 2019), pp. 1270–1279.

形式陈述 ​

假设与结论 ​

期望界的换一法 ​

从期望到尾界 ​

强凸正则化 ERM ​

边界 ​

反向链接

形式陈述

假设与结论

期望界的换一法

从期望到尾界

强凸正则化 ERM

边界