传导式 Rademacher 复杂度及其应用
本文提出了基于数据依赖性复杂度概念的学习算法误差的新界限,利用局部和经验版本的 Rademacher 平均值对估计进行优化,适用于具有小样本误差函数子集的情况,并应用于凸函数类和核函数类的分类和预测问题。
Aug, 2005
我们介绍了一种新工具,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
算法和数据相关的广义化界限是解释现代机器学习算法的广义化行为所必需的。在这个背景下,存在包括 (各种形式的) 互信息和基于假设集稳定性的信息论广义化界限。我们提出了一个概念上相关但技术上独特的复杂度度量方法来控制广义化误差,这就是算法和数据相关的假设类的经验 Rademacher 复杂度。通过结合 Rademacher 复杂度的标准特性和这个类的方便结构,我们能够 (i) 获得基于有限分形维度的新界限,这些界限将之前从连续假设类推广到有限假设类,并避免了先前工作中所需的互信息项;(ii) 大大简化了最近一个和维度无关的随机梯度下降的广义化界限的证明;(iii) 我们轻松恢复了 VC 类和压缩方案的结果,类似于基于条件互信息的方法。
Jul, 2023
本文首次在信息理论的背景下,为传导学习算法开发了数据相关性和算法相关性的一般化界限。我们表明传导学习算法的一般化差距可以通过训练标签和假设之间的互信息来限制。通过创新性地提出传导超样本的概念,我们超越归纳学习设置,并建立了各种信息测量的上界。此外,我们派生了新颖的 PAC-Bayesian 界限,并建立了传导学习环境下一般化与损失曲面平坦性之间的联系。最后,我们提出了自适应优化算法的上界,并展示了在半监督学习和图学习场景中的应用结果。我们的理论结果在合成数据集和真实世界数据集上得到验证。
Nov, 2023
本文提出了关于数据相关假设集合普适性的研究,基于一种转移 Rademacher 复杂度的概念,为数据相关假设集合提供了普适性学习保证。我们的主要结果是一种关于数据相关假设集合的普适性界限,这个界限可以用我们引入的假设集合稳定性和数据相关假设集合的 Rademacher 复杂程度来表示。这个界限包括标准 Rademacher 复杂度的界限和算法相关的统一稳定性界限。我们还说明了这些学习界限在几种情况下的应用。
Apr, 2019
该研究提出了一种基于两步半监督模型的多类分类器的 Rademacher 复杂性界,通过聚类技术和较少的带标签数据来训练分类器,并得到包含泛化误差界的数据相关收敛速度的理论结果。
Jul, 2016
利用加权集合大小的一种新技术来估计加权设置大小的新广义 Rademacher 复杂度的上限和下限,并且可以通过解决随机扰动最优化问题来估计加权 Rademacher 复杂度。
Jan, 2018
提出了一种新的学习理论复杂性概念,它在经验风险最小化和贝叶斯估计器的情况下分别以数据无关的 Rademacher 复杂度和数据相关的信息复杂度进行上限绑定,并通过 Rademacher 复杂度将其与 $L_2 (P)$ 熵进行关联。该研究进一步使用 ' 易于理解 ' 和模型复杂性等相互分离的方法,提供适用于 VC 和多项式熵类的最优性差距上限。
Oct, 2017
本文旨在扩展 Rademacher 复杂性和最新 PAC - 贝叶斯理论之间的桥梁,首先通过平移 Rademacher 过程来匹配 Catoni PAC-Bayes 界限的快速率,然后最新地导出了快速 PAC-Bayes 界限,重点是后验集中在的经验风险表面的 “平坦度”。
Aug, 2019
通过向数据集添加少量样本,我们将依靠 PAC 保证的无偏泛化学习转化为依靠转导保证的无偏泛化学习,从而展示了这些问题的等效性。我们还将所得到的结果扩展到了 agnostic 情况,证明了一种 agnostic 转导学习器可以高效转化为 agnostic 无偏泛化学习器。最后,我们对二进制分类的 agnostic one inclusion 图算法进行了性能表征,并且展示了将其和我们的转导转化方法相结合可以得到一个本质上最优的 agnostic 无偏泛化学习器。我们的结果意味着在可实现的环境下,使用伪度量损失函数进行监督学习时,转导学习和 PAC 学习在本质上是等价的;在 agnostic 情况下,对于二进制分类问题,也是如此。我们猜想这个结论在 agnostic 情况下更普遍适用。
May, 2024