Dec, 2012

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

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

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

    Feb, 2017

  • 鲁棒性和泛化性

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

    May, 2010

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

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

    Oct, 2020

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

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

    May, 2024

  • 均匀稳定算法的高概率泛化界限，近乎最优速率

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

    Feb, 2019

  • 基于一致稳定算法的泛化界限

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

    Dec, 2018

  • 在线可学习稳定性条件

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

    Aug, 2011

  • 对抗训练的数据依赖稳定性分析

    通过加入数据分布信息，我们提供了基于随机梯度下降的对抗训练的泛化界限，分析了数据分布的变化和对抗攻击的影响。

    Jan, 2024

  • 具有健壮泛化保证的自适应学习

    研究三种不同强度的泛化理论 —— 稳健泛化、差分隐私和完美泛化的关系，并证明了每个假设类都可以在稳健泛化的情况下进行 PAC 学习，具有相近的样本复杂度。

    Feb, 2016

  • 收敛于全局最优解的学习算法的稳定性和泛化性

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

    Oct, 2017