Mar, 2024

正确与不正确的量子 PAC 学习

PDF
TL;DR用量子 Coupon Collector 问题，作者研究了 PAC 学习模型中的正确学习和错误学习，发现其样本复杂性。进而提出了量子 Coupon Collector 问题的解算法，并设计了量子 Padded Coupon Collector 问题，并证明了经典 Coupon Collector 问题和量子 Padded Coupon Collector 问题在样本复杂性上存在渐进性差异。
pac modelproper learningimproper learningquantum coupon collector problemsample complexity
发现论文，激发创造
  • 从平均情况复杂度到不当学习复杂度

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

    Nov, 2013

  • 学习算法的最优量子样本复杂度

    在本文中，我们研究了量子样本复杂性，使用了二种方法证明了量子和经典样本复杂性在 PAC 和 agnostic 模型上差不多，其中第一种方法可以得到与经典边界相同或仅相差一个对数的量子边界，而第二种方法可以不丧失对数因子的情况下完成分析。

    Jul, 2016

  • PAC 模型中学习量子通道的高效算法及近似状态辨识问题

    研究 PAC 学习量子过程问题，给出了样本复杂度估计，并推广了此问题到量子世界，得出了量子电路可在多项式样本下进行 PAC 学习且可近似区分量子状态。

    Oct, 2018

  • 量子学习算法的改进界限

    本文介绍了通过量子查询和量子示例从学习布尔函数的算法的复杂性的新结果，其中我们探讨了中间问题的量子和经典查询复杂度与精确学习问题和谐平衡的自然问题，并提高了期望严格学习的新下界，以达到经典 PAC 学习的已知上界。

    Nov, 2004

  • 关于离散分布的量子与经典可学习性

    本文比较了传统和量子学习者在 Probably Approximately Correct (PAC) 框架下的生成模型能力，并构造了一类离散概率分布，通过决策 Diffie-Hellman 假设证明传统生成模型算法无法高效 PAC 学习，但我们构建了一个高效的量子学习器。同时，本文还讨论了证明经典生成建模难度结果的技术，以及布尔函数和离散概率分布的 PAC 学习性之间的关系。

    Jul, 2020

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

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

    Feb, 2024

  • VC 类可对抗性强鲁棒可学习，但只是不规则的

    研究学习对抗性强预测器的问题，表明任何具有有限 VC 维度的假设类都可以通过不正确的学习规则进行强健的 PAC 学习，而不正确的学习规则是必要的，因为我们展示了具有有限 VC 维度的假设类的例子，不能通过任何正确的学习规则进行强健的 PAC 学习。

    Feb, 2019

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

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

    Feb, 2022

  • 量子数据学习的信息论泛化界限

    我们提出了一个描述量子学习的数学形式，并利用几种量子学习场景进行直观且可访问的推广边界。

    Nov, 2023

  • 本地量子电路输出分布的可学习性

    本文研究了两种不同的神经网络模型下，量子电路 Born 机的可学习性，发现虽然当给定访问样本时可用于统计学习，但具有超对数深度的克里福德电路的输出分布在统计查询模型下不易于学习，这限制了学习本地量子电路输出分布的可能性，并提供了从概率建模角度学习本地量子电路输出分布的严格见解。

    Oct, 2021