arXiv ID:
2602.19552
arXiv 提交日期: 2026-02-23
可复现可实现PAC学习的样本复杂度 / The Sample Complexity of Replicable Realizable PAC Learning
1️⃣ 一句话总结
这篇论文通过构造一个特别困难的学习问题,并利用图论和随机游走等新颖方法,首次证明了在可复现的PAC学习框架下,所需样本量的下界几乎与假设类大小的(对数)的3/2次方成正比,并且这个下界几乎是紧的。