形式陈述
假设与结论
设确定性学习算法 接受 个 IID 样本 ，损失 ，其中 ；取 ，并假定算法与损失可测。若它具有算法稳定性理路算法稳定性algorithmic stability · uniform stability用训练集中单点替换对输出损失的影响，刻画学习算法的泛化敏感度。，即任意只相差一个样本的 与任意测试点 都满足
则称 是 -一致稳定的。记泛化间隙理路经验风险与泛化间隙Empirical risk · Generalization gap训练平均损失与总体风险之差，以及数据依赖选择带来的困难。
其期望满足
此外，直接使用有界差分可得一个经典、但未必最紧的高概率版本：以至少 的概率
若采用“删除一个点”而非“替换一个点”的稳定性定义，或对双边绝对间隙取界，常数会改变；应从相应定义重新计算，而非拼接不同版本。
期望界的换一法
写 ，再取独立副本 ，令 把 替换为 。由于 与 同分布，
每一项绝对值至多 ，故结论成立。这里没有对整个假设类取上确界；控制来自算法输出随单点变化不大。
从期望到尾界
将 的第 点替换后，总体风险项至多改变 。经验风险的其余 项各至多改变 ，平均后不超过 ；被替换的那一项还可能改变 。因此
对 个坐标应用 有界差分不等式理路有界差分不等式McDiarmid inequality · 有界差异不等式独立输入的函数若对单个坐标不敏感，其输出便以次高斯速度集中在期望附近。，再代入 ，就得到上述高概率式。若 ，尾项仍是 ；现代稳定性尾界能在某些条件下更好地保留 的尺度，但不应冒充这条朴素 McDiarmid 推导。
直觉
一致稳定性不控制整个假设类，而是直接询问：替换一个训练点，会让最终算法在任意测试点上的损失改变多少？若每个样本只能轻微推动输出，那么训练集中的自我评价与独立测试点评价就难以系统性分离。
期望证明用 ghost point 交换训练点与新样本，使泛化间隙化成相邻数据集输出的损失差；高概率证明则进一步计算 对每个样本坐标的敏感度。两步分别支付 与 ，不能把期望结论直接当作尾界。
例子与边界
强凸正则化 ERM
在非空闭凸集 上考虑正则化 ERM理路正则化经验风险最小化regularized ERM · RERM在经验拟合项上加入结构惩罚，以显式控制解的复杂度与统计—优化权衡。
其中 ， 凸且对所有 都为 -Lipschitz。连续性与二次项的强制增长保证极小点存在，强凸性理路强凸性Strong convexity · Strongly convex function函数在一阶凸下界之外还保留统一二次增长量的曲率性质。保证唯一。
记相邻样本对应的解为 。强凸函数在其极小点有二次增长；即使损失不可微，也可把极小性与连接 的线段不等式结合，再令线段参数趋零，得到
对另一份样本写反向式并相加，只有被替换的两项不抵消，故
再由任意测试点的损失 Lipschitz 性，得到 。若还满足上文统一的 损失范围，便可代入其高概率界；强凸性本身不提供这份损失上界。
边界
若 不随 衰减，期望间隙不会被迫趋零。无界损失也使经典尾界失去 。随机算法还需明确稳定性是对同一随机种子耦合、对内部随机性取期望，还是联合高概率陈述；三者不能互换。本路线与 Rademacher 泛化界理路Rademacher 泛化界Rademacher generalization bound用样本上的 Rademacher 复杂度给出对整个有界实值函数类同时成立的数据依赖总体风险上界。的区别在于，前者评价具体算法的敏感性，后者评价整个函数类在样本上的波动。
推论与应用
强凸正则化 ERM 中，单点只占目标的 权重，强凸性把极小点位移控制为 ，再由 Lipschitz 损失得到 。这把优化曲率直接转成算法依赖的泛化保证。
稳定性特别适合分析由具体训练过程选择的模型，而不必对整个大函数类取上确界。正则化、早停、随机梯度与数据依赖先验可产生不同稳定性概念；每次都要声明邻接方式、随机性耦合和损失范围，才能选择对应期望或高概率定理。
参考资料
