协作 PAC 学习的改进算法

May, 2018

Improved Algorithms for Collaborative PAC Learning

Huy L. Nguyen, Lydia Zakynthinou

TL;DR研究了一种近期的协作 PAC 学习模型，在这个模型下，k 个执行 k 个不同任务的参与者协作学习单个工作于所有任务的分类器。该研究设计了新算法，其中的样本复杂度仅为学习单个任务的最坏情况样本复杂度的 O (ln (k)) 倍，样本复杂度的上界与之前的算法匹配，并且在某些参数范围内甚至比允许输出不同分类器以适用于不同任务的先前算法更好。

Abstract

We study a recent model of collaborative pac learning where $k$ players with $k$ different tasks collaborate to learn a single classifier that works for all tasks. Previous work showed that when there is a

collaborative pac learning classifier sample complexity realizable setting non-realizable setting

发现论文，激发创造

通过乘性权重的协作 PAC 学习的紧密界限

本文提出了一种具有 O (log k) 开销的协作学习算法，改进了之前文献中 O (log^2 k) 开销的算法，同时证明了当 k 由假设类的 VC 维度多项式限制时，必须存在 Omega (log k) 的开销。此外，我们在实际数据集上的实验研究表明，我们的算法比 Blum 等人的算法优越。

May, 2018

不同标签函数的协同学习

研究一种协作 PAC 学习的变体，旨在学习每个数据分布的准确分类器，同时最小化从这些数据分布中所抽取的样本数总量。给出基于经验风险最小化算法的学习方法，并且分析依赖于增强的假设类的 VC 维度的上界。在计算效率方面，证明了在一般情况下，基于增强的假设类的 ERM 是 NP 难的，为不存在计算效率高的学习器提供了依据，但对于两种特殊情况，给出了既有样本效率又有计算效率的学习器。

Feb, 2024

从众策中高效的 PAC 学习

通过交错标注和学习的过程，可以在更少的标注成本下实现计算效率，以高精度去标记收集的数据，从而进行有效的学习算法。

Mar, 2017

多分布学习的样本复杂度

这篇论文研究多分布学习，给出了一个样本复杂度为 $\widetilde {O}((d+k)\epsilon^{-2}) \cdot (k/\epsilon)^{o (1)}$ 的算法，解决了 COLT 2023 的开放问题。

Dec, 2023

学习合作游戏

探索了在合作博弈中的 PAC（可能近似正确）学习模型，研究了几种合作博弈的 PAC 可学习性以及 PAC 可学习性与核稳定之间的联系，如网络流游戏，阈值任务游戏和诱导子图游戏。通过多项式样本数，可以找到可能稳定的收益分配。

Apr, 2015

PAC 学习的最优样本复杂度

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

Jul, 2015

对抗性多源 PAC 学习的样本复杂度

探讨来自多个不可信数据源的学习问题，提出了一种解决方法，该方法可以在合作学习模式下有效应对某些数据源的有偏差性和攻击性干扰，并能够提供有限样本保证。

Feb, 2020

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

本研究提出一种新的框架，超越了传统统一收敛方法的限制，将排列不变预测器的交叉检验误差转化为高概率风险界，并通过 Haussler, Littlestone, 和 Warmuth 的一种算法在二元分类中实现了最优 PAC 界限。在多类分类、部分假设分类和实现有限的回归等三种不同场合中，我们证明了该框架的优越性能。

Apr, 2023

使用成对比较从群众中高效学习 PAC

本文基于两种算法（一个可直接恢复出真实标签，另一个则可以在标注标签子集的情况下可靠地推断出大型实例集的真实标签）从而开发利用配对比较查询可在指数级减少标签复杂性的方法，用于众包 PAC 学习阈值函数的设定，并在保留整体查询复杂性和运行时间的同时，可以成功地处理来自可能反对者的注释。

Nov, 2020

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

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

Jun, 2024