Apr, 2019

假设集稳定性与泛化能力

PDF
TL;DR本文提出了关于数据相关假设集合普适性的研究，基于一种转移 Rademacher 复杂度的概念，为数据相关假设集合提供了普适性学习保证。我们的主要结果是一种关于数据相关假设集合的普适性界限，这个界限可以用我们引入的假设集合稳定性和数据相关假设集合的 Rademacher 复杂程度来表示。这个界限包括标准 Rademacher 复杂度的界限和算法相关的统一稳定性界限。我们还说明了这些学习界限在几种情况下的应用。
generalizationdata-dependent hypothesis setstransductive rademacher complexityhypothesis set stabilitylearning bounds
发现论文，激发创造
  • 通过算法相关的 Rademacher 复杂度实现泛化保证

    算法和数据相关的广义化界限是解释现代机器学习算法的广义化行为所必需的。在这个背景下，存在包括 (各种形式的) 互信息和基于假设集稳定性的信息论广义化界限。我们提出了一个概念上相关但技术上独特的复杂度度量方法来控制广义化误差，这就是算法和数据相关的假设类的经验 Rademacher 复杂度。通过结合 Rademacher 复杂度的标准特性和这个类的方便结构，我们能够 (i) 获得基于有限分形维度的新界限，这些界限将之前从连续假设类推广到有限假设类，并避免了先前工作中所需的互信息项；(ii) 大大简化了最近一个和维度无关的随机梯度下降的广义化界限的证明；(iii) 我们轻松恢复了 VC 类和压缩方案的结果，类似于基于条件互信息的方法。

    Jul, 2023

  • 基于随机集的 PAC-Bayesian 理论对数据依赖假设集的统一泛化界限

    我们从 PAC-Bayesian 的角度提出了数据相关的均匀泛化界，通过将训练算法输出的数据相关假设集应用于随机集的严格方法，我们证明了数据相关的界，适用于多种情境，并将此方法应用于基于分形维度的泛化界和连续 Langevin 动力学以及随机梯度 Langevin 动力学的轨迹上，这些结果为噪声算法的泛化特性提供了新的信息。

    Apr, 2024

  • 传导式 Rademacher 复杂度及其应用

    利用转导 Rademacher 复杂度及其 Error bounds 技术，借助新型的算法误差求解及算法刻画技术，得出三个已知的算法误差边界并针对混合转导算法提出新的 PAC-Bayesian 边界。

    Jan, 2014

  • 算法稳定性和假设复杂度

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

    Feb, 2017

  • 鲁棒性意味着数据相关的泛化界限推广

    通过数据相关的广义界限，证明了健壮性意味着泛化。我们提出了几个例子，包括 Lasso 和深度学习，证明了我们的界限是明显优于以前的界限的。技术创新包括针对多项式随机变量的改进的浓缩界限。

    Jun, 2022

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

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

    Feb, 2016

  • 利用分数布朗运动得出的深度神经网络的轨迹相关的泛化界

    通过探究 SGD 的轨迹依赖假设集，建立基于 Hausdorff 维数的 Rademacher 复杂度，并通过假设集稳定性推导具有预测力的 DNN 的新型泛化边界。

    Jun, 2022

  • 激进归纳学习的尖锐泛化：一种激进局部拉德马赫复杂度方法

    我们介绍了一种新工具，Transductive Local Rademacher Complexity (TLRC)，用于分析转导学习方法的泛化性能，并激发新的转导学习算法。我们的工作将热门的 Local Rademacher Complexity (LRC) 的概念扩展到转导设置，并与归纳设置中典型的 LRC 方法的分析相比，进行了相当大的改变。我们提出了一种基于局部化的 Rademacher 复杂度的工具，可以应用于各种转导学习问题，并在适当条件下获得尖锐的界限。类似于 LRC 的发展，我们通过从具有方差信息的独立变量的尖锐集中不等式开始，构建了 TLRC，然后将转导学习模型的预测函数类划分为多个片段，其中每个片段的 Rademacher 复杂度上界由一个子根函数表示，并且每个片段中所有函数的方差都受到限制。我们使用精心设计的方差运算符，确保在转导设置中未标记的测试数据的测试损失的界限与归纳设置中经典 LRC 界限具有显著的相似性。我们使用新的 TLRC 工具分析了转导核学习 (TKL) 模型，其中测试数据的标签由一个核函数生成。TKL 的结果为两类转导学习任务，即图转导学习 (GTL) 和转导非参数核回归 (TNKR)，奠定了泛化界限的基础。当目标函数是低维度或近似低维度时，我们为 GTL 和 TNKR 设计了低秩方法，通过 TLRC，这些方法可以获得特别尖锐的泛化界限，据我们所知，这是现有的学习理论方法无法实现的。

    Sep, 2023

  • 信息论归纳学习的广义界限及其应用

    本文首次在信息理论的背景下，为传导学习算法开发了数据相关性和算法相关性的一般化界限。我们表明传导学习算法的一般化差距可以通过训练标签和假设之间的互信息来限制。通过创新性地提出传导超样本的概念，我们超越归纳学习设置，并建立了各种信息测量的上界。此外，我们派生了新颖的 PAC-Bayesian 界限，并建立了传导学习环境下一般化与损失曲面平坦性之间的联系。最后，我们提出了自适应优化算法的上界，并展示了在半监督学习和图学习场景中的应用结果。我们的理论结果在合成数据集和真实世界数据集上得到验证。

    Nov, 2023

  • 线性假设和神经网络的对抗学习保证

    研究了在 $l_r$-norm 测量下带有敌对干扰的线性假设的敌对经验 Rademacher 复杂性的上限和下限，扩展了已有的结果并提供了更精细的维度依赖性分析，并在单个 ReLU 单元和具有一层隐藏层的前馈神经网络中提供了 Rademacher 复杂度上下界。

    Apr, 2020