Jul, 2016

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

PDF
TL;DR在本文中，我们研究了量子样本复杂性，使用了二种方法证明了量子和经典样本复杂性在 PAC 和 agnostic 模型上差不多，其中第一种方法可以得到与经典边界相同或仅相差一个对数的量子边界，而第二种方法可以不丧失对数因子的情况下完成分析。
vc dimensionpac modelagnostic modelquantum sample complexitypretty good measurement
发现论文，激发创造
  • PAC 模型中学习量子通道的高效算法及近似状态辨识问题

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

    Oct, 2018

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

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

    Nov, 2004

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

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

    Mar, 2024

  • 多分布学习中 VC 类的样本复杂度

    多分布学习是 PAC 学习在具有多个数据分布的环境中的自然推广，本论文讨论了该问题的最新研究进展以及在统计学习中使用游戏动态的一些基本障碍。

    Jul, 2023

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

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

    Jul, 2020

  • 混合物的高效样本学习

    提出了一种基于混合学习算法的 PAC 学习方法，该算法可用于密度估计中的概率分布，其中包含了学习概率分布，学习混合分布等，其中混合分布包括轴向高斯混合分布，高斯混合分布和对数凹分布。

    Jun, 2017

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

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

    Nov, 2023

  • PAC 学习的最优样本复杂度

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

    Jul, 2015

  • 多分布学习的样本复杂度

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

    Dec, 2023

  • 任意可计算分类器的统计学习

    研究了在所有可计算标签函数中的学习，证明了这是可能的，但也表明了无法独立于分布地限制样本复杂度，这完全是由于学习算法可计算的要求，而不是统计问题的本性。

    Jun, 2008