在线到 PAC 转换:通过遗憾分析获得泛化界
通过将训练数据从一个混合过程进行采样,我们研究了统计学习算法在非独立同分布的环境中的泛化误差,并基于延迟反馈的在线学习提出了一个分析框架。特别地,我们展示了即使数据序列是从混合时间序列采样得到的情况下,通过存在一个具有有界遗憾的在线学习算法(针对一个固定的统计学习算法,在一个特殊构建的延迟反馈的在线学习博弈中),所述统计学习方法的泛化误差较低。这些速率展示了在线学习博弈中的延迟量和连续数据点之间的依赖程度之间的权衡,当延迟适当地调整为过程的混合时间的函数时,可以在许多研究良好的情形下恢复近乎最优的速率。
Jun, 2024
该论文提出了一种普遍框架,用于研究在线学习框架下的自适应遗憾界限,包括模型选择界限和数据相关界限;该框架基于顺序复杂度量的修正,并使用单侧尾不等式来界定此界限,并在线性优化和在线 PAC-Bayes 定理中进行了实例化。
Aug, 2015
在线学习方法在最小假设下产生顺序遗憾界限,并为统计学习提供期望风险界限;然而,最近的研究结果表明,在许多重要情况下,遗憾界限可能无法保证统计背景下紧致的高概率风险界限。本研究通过将通用在线学习算法应用于在线到批次转换,通过对定义遗憾的损失函数进行一般的二阶校正,获得了几个经典统计估计问题(如离散分布估计、线性回归、逻辑回归和条件密度估计)的几乎最优的高概率风险界限;我们的分析依赖于在线学习算法的不恰当性,因为它们不限制使用给定参考类别的预测器;我们的估计器的不恰当性使得在各种问题参数上显著改善了依赖;最后,我们讨论了我们的顺序算法与现有批处理算法之间的一些计算上的优势。
Aug, 2023
我们使用在线到批次转换范例,给出了从依赖数据源中获取的样本训练的统计学习算法的泛化界限,包括期望值和高概率。我们表明,统计学习器在依赖数据环境中的泛化误差等同于独立同分布环境中的泛化误差,除了一个依赖于底层混合随机过程的衰减速率且与统计学习器复杂性无关的项。我们的证明技巧涉及基于 Wasserstein 距离定义在线学习算法稳定性的新概念,并利用基于依赖随机变量的 “近似鞅” 浓度界限,得出了统计学习算法在依赖数据上的泛化误差的适当上界。
May, 2024
本研究探讨了一类广泛问题的在线可学性,并将其扩展到远超过外部遗憾的性能评估简单规范。我们的框架同时捕捉了其他著名规范,例如内部和一般 Phi 规范、学习使用非加性全局成本函数、Blackwell 的可挑战性、预测者的校准、自适应遗憾等。我们展示了在所有这些情况下的可学习性归因于控制相同的三个量:马田哥小定理收敛项、如果已知未来则能够表现良好的能力描述项、以及顺序 Rademacher 复杂性的概括,该复杂性在 (Rakhlin, Sridharan, Tewari, 2010) 中得到研究。由于我们直接研究问题的复杂性,而不是专注于高效算法的开发,因此我们能够改进和扩展许多已知结果,这些结果之前是通过算法构造推导出来的。
Nov, 2010
用 PAC-Bayesian 理论为学习优化问题提供了第一个具备可证估计以及收敛保证和收敛速度权衡的框架,学习出的优化算法在比起仅从最坏情况分析得出的算法上具备可证的优越性能,基于指数族的 PAC-Bayesian 上界对一般的、可能无界的损失函数提供了可行性,我们通过将学习过程转化为一维最小化问题并研究全局最小值的可能性,提供了一个具体算法实现和学习优化的新方法,并进行了四个实际相关的实验来支持我们的理论,展示出该学习框架使得优化算法的性能有了数个数量级的改进。
Apr, 2024
本研究提出了关于深度学习的泛化误差的准则,介绍了一种基于边际似然的 PAC-Bayesian Bound 方法来预测泛化误差,并进行了广泛实证分析以评估该方法的效果和特性。
Dec, 2020
通过 PAC-Bayes 和算法稳定性的结合研究了随机梯度下降算法的泛化误差,提出了一种基于后验优化的自适应采样算法,并在基准数据集上进行评估。结果表明,相较于均匀采样,自适应采样既可以更快地降低经验风险,也可以提高样本外准确性。
Sep, 2017
本文介绍了基于 Wasserstein 距离的 PAC-Bayesian 泛化边界,并从分别适用于批量学习与独立同分布数据和在线学习的角度进行了证明,并获得了用于 SRM 的可优化培训目标。
Jun, 2023
该研究利用分解的 PAC-Bayes 边界框架得出一个可适配任意复杂度度量的一般泛化边界,其中关键步骤是考虑一系列常用的分布:Gibbs 分布。该边界在概率上同时适用于假设和学习样本,允许复杂度根据泛化差距进行调整,以适应假设类和任务。
Feb, 2024