提出可复现的泛化学习样本复杂度下界，逼近 (log|H|)^{3/2}。
The Sample Complexity of Replicable Realizable PAC Learning
- 构造难学问题，通过凯莱图与随机游走分析
- 样本复杂度下界接近 (log|H|)^{3/2}
- 结果逼近最优，适合理论学习研究者
本文研究可复现的真实世界 PAC 学习的样本复杂度。我们构造了一个特别困难的学习问题，证明了样本复杂度下界在假设类大小 |H| 上具有接近 (log|H|)^{3/2} 的依赖关系。证明引入新技巧，通过定义与假设类 H 相关的凯莱图，并分析其邻接矩阵的谱性质来研究随机游走行为。此外，我们对所构造实例给出了近乎匹配的上界，说明若存在更强下界，必须考虑不同的问题实例。
原文摘要 · Abstract (English)
In this paper, we consider the problem of replicable realizable PAC learning. We construct a particularly hard learning problem and show a sample complexity lower bound with a close to $(\log|H|)^{3/2}$ dependence on the size of the hypothesis class $H$. Our proof uses several novel techniques and works by defining a particular Cayley graph associated with $H$ and analyzing a suitable random walk on this graph by examining the spectral properties of its adjacency matrix. Furthermore, we show an almost matching upper bound for the lower bound instance, meaning if a stronger lower bound exists, one would have to consider a different instance of the problem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。