算法稳定性可测试吗？在计算限制下的统一框架

May, 2024

算法稳定性可测试吗？在计算限制下的统一框架

Is Algorithmic Stability Testable? A Unified Framework under Computational Constraints

Yuetian Luo, Rina Foygel Barber

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

Abstract

algorithmic stability is a central notion in learning theory that quantifies the sensitivity of an algorithm to small changes in the training data. If a learning algorithm satisfies certain →

algorithmic stability learning algorithm stability properties testing certifying

发现论文，激发创造

几乎处处算法稳定性与泛化误差

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

Dec, 2012

算法稳定性和假设复杂度

本研究提出了算法稳定性的概念，即我们称之为 “参数稳定性”，它捕捉从中选择假设的函数的规范空间中学习算法产生的假设的稳定性。论文的主要结果在于以参数稳定性来限制任何学习算法的泛化误差。这些限制基于 Banach 空间中的鞅不等式。我们将普遍限制应用于基于经验风险最小化和随机梯度下降的一些学习算法的性能边界。

Feb, 2017

算法性能无假设测试的限制

对于限定的数据量，我们研究了算法评估与比较的理论极限，发现在黑盒测试下无法客观评价算法性能，除非可用数据点数远大于样本量。在评估特定训练模型性能方面则较为简单，只需要保留一组验证数据即可。同样地，我们探讨了算法稳定性假设是否足以解决问题，结果发现只有在高稳定性范围内，模型才能基本无差别。最后，我们还针对多个算法的比较问题也得出了类似的理论困难。

Feb, 2024

鲁棒性和泛化性

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

May, 2010

技术笔记：偏置与稳定性的量化

研究机器学习算法偏差对预测精度的影响时，应考虑稳定性因素，本文提出了一种基于概念一致性的稳定性度量方法，讨论了稳定性、预测精度和偏差之间的关系。

Dec, 2002

在线可学习稳定性条件

研究表明，稳定性是一种可以用来量化学习算法的稳定程度的一般概念，是推动在线学习和减少后悔的关键。本文引入了在线稳定性，这是与均匀留一稳定性相关的一种稳定性条件，足以实现在线可学习性，并且说明了流行类的在线学习算法的一些理论。在特定的二分类设置中，稳定性条件是充分必要的。

Aug, 2011

局部弹性稳定性更好的泛化界限

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