多组别不可知的 PAC 可学习性
研究可靠的不可知学习框架中的问题,使用单边多项式逼近可学习可靠分类器和构建适当的单边多项式逼近来学习大多数时完全可靠,这些算法还满足强属性效率属性并提供样本复杂度和运行时间之间的平滑折衷。
Feb, 2014
通过将对抗性鲁棒学习简化到标准的 PAC 学习问题,即仅使用黑盒非鲁棒性学习器学习鲁棒性预测器的学习复杂度,我们提供了一个降低学习复杂度的方法,并证明了其数学上的正确性。同时,我们也给出了一个必要的下界。
Oct, 2020
研究了高斯分布下对于无偏学习任务的查询访问权限的能力。聚焦于多指数模型(MIMs),研究表明查询访问权限在无偏学习 MIMs 方面相对于随机样本具有显著的运行时改进作用。
Dec, 2023
通过向数据集添加少量样本,我们将依靠 PAC 保证的无偏泛化学习转化为依靠转导保证的无偏泛化学习,从而展示了这些问题的等效性。我们还将所得到的结果扩展到了 agnostic 情况,证明了一种 agnostic 转导学习器可以高效转化为 agnostic 无偏泛化学习器。最后,我们对二进制分类的 agnostic one inclusion 图算法进行了性能表征,并且展示了将其和我们的转导转化方法相结合可以得到一个本质上最优的 agnostic 无偏泛化学习器。我们的结果意味着在可实现的环境下,使用伪度量损失函数进行监督学习时,转导学习和 PAC 学习在本质上是等价的;在 agnostic 情况下,对于二进制分类问题,也是如此。我们猜想这个结论在 agnostic 情况下更普遍适用。
May, 2024
我们研究了对所有政策类 Pi 进行不可知 PAC 强化学习问题:在与一个未知的具有潜在庞大状态和动作空间的 MDP 交互的情况下,需要多少轮才能学习到相对于 Pi 的 epsilon - 次优政策?为此,我们引入了一种新的复杂性度量,称为生成能力,它仅依赖于政策类 Pi 而与 MDP 动力学无关。通过一个生成模型,我们证明了对于任何政策类 Pi,有界的生成能力表征了 PAC 可学习性。然而,对于在线 RL 来说,情况要复杂些。我们展示了存在一个具有有界生成能力的政策类 Pi,需要超多项式数量的样本来进行学习。这揭示了在生成访问和在线访问模型之间(以及在线访问下的确定性 / 随机 MDPs 之间)对于不可知学习能力的令人惊讶的区别。在积极方面,我们确定了一种额外的向日葵结构,它与有界生成能力一起,通过一种名为 POPLER 的新算法实现了统计高效的在线 RL,该算法借鉴了经典的重要性采样方法以及无奖励探索中可达状态识别和政策评估技术。
Oct, 2023
本文基于两种算法(一个可直接恢复出真实标签,另一个则可以在标注标签子集的情况下可靠地推断出大型实例集的真实标签)从而开发利用配对比较查询可在指数级减少标签复杂性的方法,用于众包 PAC 学习阈值函数的设定,并在保留整体查询复杂性和运行时间的同时,可以成功地处理来自可能反对者的注释。
Nov, 2020
我们研究了具有统计子群公平性概念的分类器稽核问题。在高斯分布和一些先前的工作中,我们采用了一种新的方法来审核均匀半空间子群的统计公平性,并获得了多项式时间逼近方案(PTAS),在通用半空间子群和高斯特征分布条件下,没有密码学假设可以保证任何非平凡的审计。
Jan, 2024
针对给定的二元假设类和分布,该研究提出了一种与最优算法相竞争的无偏主动学习算法,该算法在错误率为 η 的情况下只需要 O (m^* log |H|) 的查询次数,并且证明了超越 O (log |H|) 的开销是 NP 难的。
Oct, 2023