探讨了算法稳定性作为分析学习算法泛化误差的可行框架的概念。引入了学习算法训练稳定性的新概念，并证明在一般情况下它足以得到泛化误差的好界。在 PAC 设置中，训练稳定性在可学习性上既是必要的也是充分的。基于训练稳定性的方法不涉及 VC 维或 VC 熵，不需要证明一致收敛，而广义 McDiarmid 不等式可直接限制泛化误差。因此，它可能使我们处理比经验风险最小化更广泛的学习算法类。还探讨了 VC 维、泛化误差和各种稳定性概念之间的关系，并考虑了几个学习算法的例子。

Dec, 2012

算法稳定性是学习理论中的一个核心概念，它量化了算法对训练数据中微小变化的敏感性。如果学习算法满足特定的稳定性属性，这将导致许多重要的下游影响，如泛化性能、鲁棒性和可靠的预测推理。然而，最近的研究结果表明，对于黑盒算法而言，在有限来自未知分布的数据的情况下，验证稳定性是不可能的，尤其是当数据存在于无穷空间（如实值数据）的情况下。在本文中，我们将这个问题扩展到更广泛的设置中，其中数据可以存在于任何空间，例如分类数据。我们提出了一个统一的框架来量化测试算法稳定性的难度，这证明了在所有设置中，如果可用的数据是有限的，则穷举搜索基本上是唯一有效的证明算法稳定性的机制。由于在实践中，任何稳定性测试自然都会受到计算约束的限制，因此穷举搜索是不可能的，这意味着我们测试黑盒算法的稳定性属性能力存在根本限制。

May, 2024

基于稳健性的学习算法的普适性界限推导及其稳健性被证明是学习算法发挥作用的基本属性。

May, 2010

本文提出了一种新的方法来证明算法稳定性，并且在此基础上给出了关于多次随机梯度下降和正则 ERM 的高概率泛化界，同时也解决了一些之前的开放性问题。

Feb, 2019

本文提出了关于数据相关假设集合普适性的研究，基于一种转移 Rademacher 复杂度的概念，为数据相关假设集合提供了普适性学习保证。我们的主要结果是一种关于数据相关假设集合的普适性界限，这个界限可以用我们引入的假设集合稳定性和数据相关假设集合的 Rademacher 复杂程度来表示。这个界限包括标准 Rademacher 复杂度的界限和算法相关的统一稳定性界限。我们还说明了这些学习界限在几种情况下的应用。

Apr, 2019

提出了一种新的分析技术，证明了一些熟知算法具有更强的泛化保证，并改善了这个算法稳定性的相关细节。

Dec, 2018

这篇论文研究了学习理论中有关稳定算法的泛化界，通过构造一个弱相关随机变量的集中不等式，得到了一般性的集中界，使得上已知的高概率上界的泛化界水平得到了提高。

Oct, 2019

本文提出一种基于局部弹性的弱稳定性概念，用以提供具有指数通用性限制条件的机器学习算法算法稳定性，比常见的分布无关的最坏损失情况敏感性更具参考价值，该概念在支持向量机、最小二乘回归和随机梯度下降等模型中具有受限制的情况下比统一稳定性提供更紧的泛化限制条件。

Oct, 2020

本文通过建立黑盒稳定性结果，仅依赖于学习算法的收敛和损失函数最小值周围的几何形态，为收敛到全局最小值的学习算法建立新的泛化界限，适用于满足 Polyak-Lojasiewicz（PL）和二次增长（QG）条件的非凸损失函数以及一些具有线性激活的神经网络，并使用黑盒结果来证明 SGD、GD、RCD 和 SVRG 等优化算法的稳定性在 PL 和强凸设置中具有可拓展性，同时指出存在简单的具有多个局部最小值的神经网络，在 PL 设置下 SGD 稳定，但 GD 不稳定。

Oct, 2017

分析迭代算法的收敛速度与稳定性之间的平衡问题，得出迭代算法总体表现是由最小二乘统计误差下界和稳定性共同决定的结论。以几种收敛速度较快的迭代算法为例，讨论了它们的稳定性上界和下界，并提出一些问题，说明改进收敛速度需要牺牲稳定性的平衡关系。

Apr, 2018