Nov, 2013

从平均情况复杂度到不当学习复杂度

PDF
TL;DR这篇论文介绍了一种新的证明不适当学习难度的技术，基于难以处理的问题的规约，通过与密码假设相结合，发现了学习 $DNF$，半平面和超平面的交集等问题的困难性。
发现论文，激发创造
  • 正确与不正确的量子 PAC 学习

    用量子 Coupon Collector 问题，作者研究了 PAC 学习模型中的正确学习和错误学习，发现其样本复杂性。进而提出了量子 Coupon Collector 问题的解算法，并设计了量子 Padded Coupon Collector 问题，并证明了经典 Coupon Collector 问题和量子 Padded Coupon Collector 问题在样本复杂性上存在渐进性差异。

    Mar, 2024

  • 私有的 PAC 学习可能比在线学习更困难

    根据合理的密码学假设，我们展示了一个概念类别，该类别允许在多项式时间内以多项式错误边界运行的在线学习器，但不存在计算效率高的差异隐私 PAC 学习器。

    Feb, 2024

  • PAC 学习的参量化理论

    本文提出了一种参数化 PAC 学习理论，通过该理论可对 CNF、DNF 和图形学习等问题的可行性边界进行更精细的界定，并发展了机器学习领域的参数化固定参数学习的概念。

    Apr, 2023

  • 可计算学习者的学习可能性特征

    本篇论文研究可计算的 PAC 学习，着眼于强 CPAC 学习的特征及不可计算性质，提供了本领域初步的研究，并囊括了 VC 类的考虑。

    Feb, 2022

  • 半空间对抗性鲁棒适当学习的复杂性（不知情噪音）

    我们研究了在分布无关的对抗性健壮 PAC 模型中半空间的计算复杂度，重点研究了 L_p 扰动。我们提出了一种计算有效的学习算法和一种几乎匹配的计算难度结果。我们发现的一个有趣的含义是，L_∞扰动的情况被证明比 2≤p<∞的情况更加计算上困难。

    Jul, 2020

  • 关于强鲁棒分类的困难程度

    本文研究了机器学习模型对抗攻击的容易受攻击性问题，并从计算学习理论的角度探究了鲁棒学习的可行性和计算复杂度，并给出了相应的计算困难性证明。

    Sep, 2019

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

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

    Apr, 2012

  • 从 Nisan 的自然证明中分布式 PAC-Learning

    自然证明能够推导有效学习算法的条件在分布式 PAC 学习模型中得以推广，证明了我们的主要结果，以及对深度 - 2 多数电路、多面体和自然目标分布中的 DNFs 的分布式 PAC 学习算法的应用以及通过深度 - 2 多数电路评估的编码输入弱 PRF 的不存在性。

    Oct, 2023

  • 学习标签比例的复杂性

    本文研究了一种学习模型，即以标签比例学习为代表的 LLP 学习模型，通过计算学习复杂度和 PAC 学习的比较，以及 VC 类的研究，得出了该模型的基础特性。

    Apr, 2020

  • 约束下的可能近似正确学习

    本文提出一种基于 PAC 学习框架的约束学习方法，该方法通过对经验风险最小化规则进行约束来解决分类问题中的偏差、不公平和不稳定性等问题，研究表明该方法能够实现约束学习的泛化。

    Jun, 2020