Jun, 2024

通过延迟的在线到 PAC 转换推导混合过程的归纳界

PDF
TL;DR通过将训练数据从一个混合过程进行采样，我们研究了统计学习算法在非独立同分布的环境中的泛化误差，并基于延迟反馈的在线学习提出了一个分析框架。特别地，我们展示了即使数据序列是从混合时间序列采样得到的情况下，通过存在一个具有有界遗憾的在线学习算法（针对一个固定的统计学习算法，在一个特殊构建的延迟反馈的在线学习博弈中），所述统计学习方法的泛化误差较低。这些速率展示了在线学习博弈中的延迟量和连续数据点之间的依赖程度之间的权衡，当延迟适当地调整为过程的混合时间的函数时，可以在许多研究良好的情形下恢复近乎最优的速率。
generalization errorstatistical learning algorithmsnon-i.i.d. settingmixing processonline learning
发现论文，激发创造
  • 在线到 PAC 转换：通过遗憾分析获得泛化界

    本文提出了从在线学习的角度推导统计学习算法的泛化界限的新框架，建立在线学习算法与统计学习算法之间的联系，通过构造一种在线学习游戏来实现该框架并得到多种泛化保证。

    May, 2023

  • 使用在线批量转换的相关数据泛化界限

    我们使用在线到批次转换范例，给出了从依赖数据源中获取的样本训练的统计学习算法的泛化界限，包括期望值和高概率。我们表明，统计学习器在依赖数据环境中的泛化误差等同于独立同分布环境中的泛化误差，除了一个依赖于底层混合随机过程的衰减速率且与统计学习器复杂性无关的项。我们的证明技巧涉及基于 Wasserstein 距离定义在线学习算法稳定性的新概念，并利用基于依赖随机变量的 “近似鞅” 浓度界限，得出了统计学习算法在依赖数据上的泛化误差的适当上界。

    May, 2024

  • 通过顺序预测器获得高概率风险边界

    在线学习方法在最小假设下产生顺序遗憾界限，并为统计学习提供期望风险界限；然而，最近的研究结果表明，在许多重要情况下，遗憾界限可能无法保证统计背景下紧致的高概率风险界限。本研究通过将通用在线学习算法应用于在线到批次转换，通过对定义遗憾的损失函数进行一般的二阶校正，获得了几个经典统计估计问题（如离散分布估计、线性回归、逻辑回归和条件密度估计）的几乎最优的高概率风险界限；我们的分析依赖于在线学习算法的不恰当性，因为它们不限制使用给定参考类别的预测器；我们的估计器的不恰当性使得在各种问题参数上显著改善了依赖；最后，我们讨论了我们的顺序算法与现有批处理算法之间的一些计算上的优势。

    Aug, 2023

  • 随机学习的 PAC-Bayesian 分析及其在随机梯度下降中的应用

    通过 PAC-Bayes 和算法稳定性的结合研究了随机梯度下降算法的泛化误差，提出了一种基于后验优化的自适应采样算法，并在基准数据集上进行评估。结果表明，相较于均匀采样，自适应采样既可以更快地降低经验风险，也可以提高样本外准确性。

    Sep, 2017

  • 缓慢混合过程的泛化能力

    给出了关于由平稳和 phi 混合过程生成的数据的多个损失类的绑定一致性界限，其中混合时间（获得近似独立所需的时间）仅以加法方式进入样本复杂性。

    Apr, 2023

  • 自适应在线学习

    该论文提出了一种普遍框架，用于研究在线学习框架下的自适应遗憾界限，包括模型选择界限和数据相关界限；该框架基于顺序复杂度量的修正，并使用单侧尾不等式来界定此界限，并在线性优化和在线 PAC-Bayes 定理中进行了实例化。

    Aug, 2015

  • 应对马尔科夫数据随机优化中的混合时间

    本研究提出了一种新颖的多层蒙特卡罗渐进优化方法，针对含有 Markov 链随机数据的优化问题，能够在不知道 Markov 链混合时间的情况下获得最佳渐进收敛速率，并适用于非凸优化求解及在时间差分 (TD) 学习中获取更好的混合时间依赖性。

    Feb, 2022

  • 漂移分布学习的新分析和算法

    利用差异的理念，我们对批处理情景下学习漂移分布的问题进行了新的分析，并证明了基于假设集和分布的差异的 Rademacher 复杂度的学习界限，包括漂移 PAC 情景和跟踪情景。 我们提出了一种新算法，利用这些学习保证，我们展示了该算法可以被表述为一个简单的 QP。

    May, 2012

  • 关于在线学习算法在成对损失函数中的泛化能力

    本文研究了基于在线学习的随机方法的泛化特性，提出了一种通用的解耦技术，可以提供基于 Rademacher 复杂度的泛化误差界限，并进一步分析了一类内存效率的在线学习算法。

    May, 2013

  • 包括稳定 RNN 的动态系统 PAC-Bayes 泛化界限

    在这篇论文中，我们推导了一个 PAC-Bayes 界限，用于一类特殊的离散时间非线性动力系统的监督时间序列设置。这个类别包括稳定的递归神经网络（RNN），而这项工作的动机就是应用于 RNN。我们在允许的模型上施加一些稳定性约束，这里的稳定性是以动力系统的概念来理解的。对于 RNN，这些稳定性条件可以表示为关于权重的条件。我们假设所涉及的过程在本质上是有界的，并且损失函数是利普希茨的。所提出的对于泛化差距的界限依赖于数据分布的混合系数和数据的本质上最大值。此外，随着数据集大小的增加，这个界限收敛于零。在这篇论文中，我们 1）正式化了学习问题，2）为这类系统推导了一个 PAC-Bayesian 误差界限，3）讨论了这个误差界限的各种结果，以及 4）展示了一个说明性例子，并讨论了计算所提出的界限的方法。与其他可用的界限不同，这个推导的界限适用于非独立同分布的数据（时序数据），并且它不随 RNN 的步骤数增长。

    Dec, 2023