Apr, 2023

非均匀收敛下的最优 PAC 上界

PDF
TL;DR本研究提出一种新的框架，超越了传统统一收敛方法的限制，将排列不变预测器的交叉检验误差转化为高概率风险界，并通过 Haussler, Littlestone, 和 Warmuth 的一种算法在二元分类中实现了最优 PAC 界限。在多类分类、部分假设分类和实现有限的回归等三种不同场合中，我们证明了该框架的优越性能。
vc classessample complexitybinary classificationmulticlass classificationhigh probability risk bounds
发现论文，激发创造
  • PAC 学习的最优样本复杂度

    通过对 Hans Simon 最新成果的技术和分析，本文在可实现情况下建立了一个新的 PAC 学习样本数量的上限，该上限匹配了已知的下限，解决了一个长期存在的开放性问题。

    Jul, 2015

  • PAC-Bayes 分析超越平常的边界

    该研究探讨了基于数据相关分布的随机预测模型在训练后的泛化能力以及基于 PAC-Bayes 分析的上界推导方法，同时研究了使用数据相关先验分布的应用，包括针对无界方差的损失函数的一种新颖的边界推导方法。

    Jun, 2020

  • 多数投票的风险界限：从 PAC-Bayesian 分析到 学习算法

    针对多数表决在二元分类中的行为，提出了一种风险界定 ——C-bound，考虑到选民的平均质量和平均分歧，结合具有自我包容性的 PAC-Bayesian 分析可从训练数据中估计 C-bound，最终提出基于 C-bound 最小化的 MinCq 算法，达到与 AdaBoost 和 SVM 相当的效果。

    Mar, 2015

  • 多类别 PAC 型强盗分类的快速速率

    我们研究了具有强化学习反馈的多分类 PAC 学习问题，提出了一种新颖的学习算法将样本复杂度降低到 O ((poly (K) + 1/ε²) log (|H|/δ))，改进了现有问题的边界，同时在一般类别情况下也得到了类似的样本复杂度边界，算法利用随机优化技术通过 Frank-Wolfe 更新计算低方差探索分布。

    Jun, 2024

  • 分布式学习，通信复杂度和隐私

    讨论分布式数据的 PAC 学习问题，分析了涉及的基本通信复杂性问题，包括教学维度和错误绑定。针对特定概念类别，如合取、奇偶函数和决策列表等，给出上下界限。讨论了如何通过增强来在分布式环境下进行一般性通信，以及如何在不确定环境下实现低通信回归。同时，还考虑了隐私性，包括差分隐私和分布式隐私。

    Apr, 2012

  • 对于无偏 PAC 学习的误差指数

    在本文中，我们通过考虑错误指数这一在信息理论中广泛应用的分析方法，研究了统计学习理论和可能近似正确（PAC）准则。在一定的稳定性假设下，我们发现二分类问题中 PAC 错误概率的指数行为，从而建立了对无知学习中可能近似正确学习的理论分析基础。有趣的是，在这些假设下，无知学习可能具有与可实现学习相同的错误指数。此错误指数准则可用于分析在缺少理论分析的知识蒸馏问题。

    May, 2024

  • 一种强凸 PAC-Bayesian 界限

    提出了一种新的 PAC-Bayesian 界并构建了假设空间，使界在后验分布上是凸的，在经验性能与复杂性之间的折衷参数上也是凸的。通过 KL 散度来测量复杂性。提出了一种交替过程来最小化这个界，并给出了一个足够的条件，使得函数具有单一的全局最小值。提供实验结果表明，严格最小化该界在调整复杂性和经验性能之间的权衡方面与交叉验证相媲美。在所有实验中，即使违反了足够的条件，折衷结果仍然是凸的。

    Aug, 2016

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

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

    Apr, 2024

  • 具有有限逃避者维度的基于模型的 RL 的均匀 PAC 保证

    本研究提出了针对非线性赌博机和基于模型的的情境强化学习的算法，使用有界 eluder 维数的通用函数类，通过将每个行为分配到不同的级别，从而实现了统一的概率近似正确性（Uniform-PAC）保证。

    May, 2023

  • 基于统一 PAC-Bayesian-Rademacher-Shtarkov-MDL 复杂度的紧致过量风险界

    提出了一种新的学习理论复杂性概念，它在经验风险最小化和贝叶斯估计器的情况下分别以数据无关的 Rademacher 复杂度和数据相关的信息复杂度进行上限绑定，并通过 Rademacher 复杂度将其与 $L_2 (P)$ 熵进行关联。该研究进一步使用 ' 易于理解 ' 和模型复杂性等相互分离的方法，提供适用于 VC 和多项式熵类的最优性差距上限。

    Oct, 2017