Oct, 2023

常数轮次学习的时间 - 空间下界

PDF
TL;DR对于每个常数 q，我们证明了在样本流上进行 q 次遍历的任何奇偶性学习算法都需要 Ω(n2) 的内存大小或至少需要 2Ω(n) 个样本数量，并且这是对于任何 q≥3 的第一个非平凡的下界。与先前的工作类似，我们的结果适用于具有许多近似正交概念的任何学习问题。我们还通过上界来补充下界，表明带有 q 次遍历的奇偶性学习可以使用 O (n2/log q) 的内存高效地完成。
parity learning algorithmmemory-sample lower boundsstreaming modelmultiple passeslower bound
发现论文，激发创造
  • 噪音容忍学习、奇偶问题和统计查询模型

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

    Oct, 2000

  • 两趟图数据流算法的近二次下界

    研究表明，任何针对 $n$- 顶点有向图中 $s$-$t$ 可达性问题的二遍流图算法都需要近似二次的 $n^ {2-o (1)}$ 比特空间，这个相当于空间的下界也适用于其他基本问题，例如最大二分匹配和在无向图中（近似）最短路径。

    Sep, 2020

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

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

    Jul, 2016

  • 量子记忆与非量子记忆学习之间的指数差距

    通过研究量子记忆在学习量子系统和动力学属性方面的作用，我们展示了不使用量子记忆的学习算法需要更多的数据，提出了量子记忆与样本复杂度的权衡，并针对测试、判别演化以及估计纯度等方面的学习算法展示了量子记忆与非量子记忆算法之间的指数差距。

    Nov, 2021

  • 学习半空间的复杂性理论限制

    该研究讨论了在固定且未知的分布和自然条件下的半空间学习问题，证明了最坏情况下的性能和效率的复杂性。

    May, 2015

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

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

    Oct, 2018

  • 关于交互证明学习的能力

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

    Apr, 2024

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

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

    Nov, 2004

  • 全息子模流处理：紧密逼近、最小内存和低自适应复杂度

    本文讨论了在 streaming setting 下最大化单调次模函数，并给出了一种新的算法 Sieve-Streaming++ 以及其扩展到多源 streaming setting 的方案，最终将该算法应用于 twitter 和 youtube 视频的多源数据摘要任务中进行效率测试。

    May, 2019

  • 多方通信复杂度中，手中数字最小下界简化

    本文利用对称化技术，证明了在黑板模型和消息传递模型中随机多方通信复杂性的下限，并应用该技术证明了关于多方通信的多个直接和结果。

    Jul, 2011