#PAC learning

7 stories · 0 in 7 days · 1 in 30 days

boosting 1 ReLU 1

Stories, products and papers tagged "PAC learning", newest first.

Oct 26

Papers Builders11:57

Chinese contentarXiv 论文：首个在完全多项式时间内学习 ReLU 正线性组合的算法

一群理论研究者把学 ReLU 线性组合的时间复杂度压到了多项式级别，之前没人做到。做学习理论或理解网络可学性的人可以看看这篇的 boosting 和 Hermite 张量技巧。

#ReLU #PAC learning #boosting

arXiv cs.LG@Ilias Diakonikolas et al. (4)Source

Aug 7

Chinese content单调对抗者学习最优速率：VC维1以上额外对数因子不可避免

这篇论文把单调对抗者模型的误差速率定性了：d=1是Θ(1/n)，d≥2多一个log因子，证明很直接。

#Monotone Adversaries #VC dimension #PAC learning #learning theory

arXiv cs.LG@Anay MehrotraSource

Jul 28

Chinese content从多个数据提供者学习分布：条件采样下的PAC学习边界

你想知道从多个供应商凑数据学分布有多难吗？这篇论文给出了从线性到二次的完整样本复杂度图谱，还找到了层次可比性这个好用的结构条件。

#PAC learning #sample complexity

arXiv cs.LG@Jon Kleinberg et al. (4)Source

Jul 8

Chinese content预测量子多体系统时间演化的可证明学习分离

这篇论文给量子机器学习找了个硬核任务：预测多体系统时间演化，量子算法能学，经典学不了，除非BQP进P/poly。理论结果很扎实。

#PAC learning #BQP #quantum machine learning

arXiv cs.LG@Rahul Bandyopadhyay et al. (5)Source

Jun 30

PapersSelected11:47

Chinese content组合函数树的PAC可学习性：科学发现的样本复杂度

论文把PAC学习理论用到符号回归上，证明了组合函数树的样本复杂度不会随深度爆炸，还给了可跑的代码。

#PAC learning #symbolic regression

arXiv cs.LG@Şuayp Talha Kocabay et al. (3)Source

Jun 29

PapersSelected10:15

Chinese content正样本只学习的proper可学习性：新组合条件与分离结果

这篇论文搞清楚了只给正样本时proper学习到底能学啥，发现了VC维不够用，还新造了个叫“均匀外部可分离性”的条件，搞理论的人值得看。

#PAC learning #VC dimension

arXiv cs.LG@Shai Ben-David et al. (4)Source

May 14

PapersSelected13:26

Chinese contentValiant 原始学习模型：可学习类与成员查询的严格夹逼

这篇论文澄清了机器学习理论中一个长期被误解的基础问题——Valiant 原始模型与 PAC 学习的区别，做学习理论或计算复杂度研究的学者值得一读，尤其是对成员查询能力感兴趣的人。

#learning theory #PAC learning

arXiv cs.LG@Steve Hanneke et al. (4)Source