Apr, 2024

关于交互证明学习的能力

PDF
TL;DR我们针对不均衡分布学习问题，构建了一种双效证明系统的交互式协议，该协议能够学习给定函数的最大傅立叶特征，学习类 AC^0 [2] 和 k-juntas。此外，我们还提供了一个用于布尔函数学习的新模型，样本复杂度与 n 无关。
发现论文，激发创造
  • 电路评估的时间最优交互证明

    本文描述了一种交互证明协议的改进方法，可以实现具有正确性保证的计算，效率比现有的实现提高了 200 倍，在矩阵乘法和数据并行计算方面也有应用。

    Apr, 2013

  • 多项式阈值函数可测学习

    该研究论文介绍了可测试学习的概念，并研究了在测试者接受标准高斯数据的情况下，多项式阈值函数的可测试学习。研究结果表明，任意常数阶的多项式阈值函数在多项式时间内可以以超出误差 ε 的程度可测试地学习，与测试属性的典型模型相匹配。同时，该研究证明了直接证明可测试学习（而非愚弄测试者）的方法在多项式阈值函数上是行不通的。

    Jun, 2024

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

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

    Oct, 2023

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

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

    Nov, 2004

  • 噪音容忍学习、奇偶问题和统计查询模型

    本文提出了一种学习带有随机分类噪声下奇偶函数的略微次指数时间算法，并给出了有关在 PAC（Probably Approximately Correct）模型中证明不可学习概念类别的噪声容错算法。同时，对于 Kearns 的统计查询模型可证明不可学习的概念类，我们给出了一种有效的噪声容错算法。此外，文章还探讨了基于统计查询模型扩展到 t 元组查询的情况，从而证明该扩展不会增加可弱学习函数的集合。

    Oct, 2000

  • 单调函数的无偏妥善学习：超越黑盒校正障碍

    本论文提出了第一个适用于单调布尔函数的无偏、高效、正确的学习算法，并使用凸优化步骤增进了不正确学习算法。同时，该工作还给出了估计未知函数到单调性的距离的算法，这两个算法的运行时间及假设评估时间为 2^(Õ(√n/ε))

    Apr, 2023

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

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

    Jul, 2016

  • 非平凡节省的不可知成员查询学习：新结果和技术

    设计剩余计算量较少的算法来解决在不确定学习模型中的问题是一项具有挑战性的任务。本文通过提出多个不确定学习算法，重点是针对大小与计算能力相关的电路的学习，探讨了如何节省计算时间，并在统一分布下进行学习。

    Nov, 2023

  • 混合物的高效样本学习

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

    Jun, 2017

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

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

    Nov, 2013