Majority-of-Three: The Simplest Optimal Learner?

在可实现的情况下，开发一种最优的PAC学习算法是学习理论中几十年来的一个重大开放问题，其中经验风险最小化（ERM）是次优的。几年前，Hanneke终于解决了这个问题。不幸的是，Hanneke的算法非常复杂，因为它返回许多ERM分类器的多数投票，这些分类器是在精心选择的数据子集上训练的。因此，确定最简单的最优算法是一个自然的目标。在这项工作中，我们研究了可能是最简单的最优算法：返回三个ERM分类器的多数投票。我们证明了这个算法实现了其错误的期望最优界，这是单个ERM分类器无法达到的。此外，我们证明了该算法的错误的高概率界接近最优。我们猜测更好的分析将证明这个算法实际上在高概率区域是最优的。

解决问题：论文试图解决什么问题，或者验证什么假设？这是否是一个新问题？

关键思路：论文中解决问题的方案关键思路是什么？相比当前这个领域的研究状况，这篇论文的思路有什么新意？

其他亮点：论文提出了一个简单的算法，使用三个ERM分类器的多数投票来达到最优的期望误差界限，证明了单个ERM分类器无法达到的界限。此外，论文还证明了该算法的高概率误差界限接近最优。值得注意的是，论文提出的算法比之前的解决方案更加简单，而且实用性更强。

相关研究：在这个领域中，最近的相关研究包括Hanneke的算法。