提出一种新方法，在保证最优学习效率的同时降低对经验风险最小化算法的依赖。
Efficient Optimal PAC Learning
- 采用不同思路设计最优PAC学习器，减少对经验风险最小化的计算依赖
- 新方法在保持理论最优性的同时优化了计算开销
- 适合关注高效学习算法设计的研究者
Hanneke [2016b] 和 Larsen [2023] 在二分类设定中提出了最优PAC学习器，分别利用巧妙的确定性子采样和经典的装袋法（bagging）Breiman [1996]。两者均以经验风险最小化（ERM）作为子程序，因此其计算成本受限于ERM算法的复杂度。本文提出一种新视角，证明存在一种最优PAC学习器，能以不同方式权衡对ERM算法的计算依赖，从而实现新的计算效率与理论最优性的平衡。
原文摘要 · Abstract (English)
Recent advances in the binary classification setting by Hanneke [2016b] and Larsen [2023] have resulted in optimal PAC learners. These learners leverage, respectively, a clever deterministic subsampling scheme and the classic heuristic of bagging Breiman [1996]. Both optimal PAC learners use, as a subroutine, the natural algorithm of empirical risk minimization. Consequently, the computational cost of these optimal PAC learners is tied to that of the empirical risk minimizer algorithm. In this work, we seek to provide an alternative perspective on the computational cost imposed by the link to the empirical risk minimizer algorithm. To this end, we show the existence of an optimal PAC learner, which offers a different tradeoff in terms of the computational cost induced by the empirical risk minimizer.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。