算法稳定性

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

交换证明的图像是把一个训练点暂时拔掉，换成来自同一分布的新点。替换后的算法几乎不变，新点又不再参与原模型的训练，于是训练损失与独立测试损失可以配对。稳定性控制的正是完成这次“拔掉再放回”所付的误差。

稳定性不等于算法正确性理路算法正确性Algorithm correctness · Partial and total correctness所有合法执行都符合规格，并在完全正确时保证终止。：它只说明算法没有过度依赖某一条记录，并不说明它学到了正确规律。一个始终输出同一预测器的算法完全不受样本替换影响，可积损失下的期望泛化间隙为零，但每份样本的间隙仍会波动。例如标签为公平二元变量、算法总预测零时，风险恒为 $1/2$，经验风险却是样本正类比例。它也可能同时具有很高的经验风险和总体风险；稳定性需要与优化或拟合质量结合，才能导出低风险。

算法稳定性固定学习算法，比较替换一个样本前后的输出或损失变化；经验风险的一致收敛理路经验风险的一致收敛Uniform convergence of empirical risks以高概率同时控制整个假设类的经验风险与总体风险偏差。固定函数类，对所有假设同时比较经验风险与总体风险。前者可利用算法的选择偏好，后者是类级别事件，二者导出泛化的路径不同。

强凸正则化 ERM ​

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

定义与随机性边界 ​

随机算法必须说明如何比较内部随机性：固定同一随机种子的耦合、对随机性取期望，或给高概率稳定性，会产生不同定义。删除式与替换式相邻关系相近但非恒等，使用定理时需固定协议。

较弱的期望稳定性不能直接代入 uniform stability 的高概率定理。损失无界时，即使 ${\beta }_m$ 很小，尾部集中也需要额外矩条件。

对强凸正则化经验风险最小化，稳定性把正则强度、样本量和损失 Lipschitz 常数直接连到期望泛化间隙。这提供了一条不必先控制整个假设类容量的路线，也解释了正则化为何不仅改善数值条件，还能降低算法对单条记录的敏感性。

要把期望界提升为高概率界，必须结合有界差分、鞅或更精细的稳定性集中结果；前面的 $|\mathbb{E}\mathrm{gap}|\le {\beta }_m$ 控制有符号均值，不能直接使用 Markov 推出尾界；必须先另行控制 $\mathbb{E}|\mathrm{gap}|$ 等非负量，才可用 Markov 得到相应的概率上界。相应结论应注明损失范围、失败概率和稳定参数的精确依赖，而不是把“稳定”直接等同于“高概率泛化”。

差分隐私提供另一种分布级稳定性：它控制相邻数据集上的整个输出分布，而 uniform stability 控制指定损失值。差分隐私蕴含泛化理路差分隐私蕴含泛化Differential privacy implies generalization · Differential privacy and generalization · 隐私稳定性泛化把相邻数据集上的差分隐私稳定性转化为自适应选择统计量的高概率泛化保证。利用更强的后处理与组合性质处理自适应选择；两类工具目标相近，但定义对象和可组合方式不能互换。