破解了任意分类任务的最优学习速率，揭示四类收敛速度
A Theory of Universal Agnostic Learning
- 打破可实现性假设，建立普适学习理论框架
- 发现四类收敛速率：指数快、次指数、根号慢、任意慢
- 用组合结构判定任一类概念的收敛类型，适合理论研究者
我们给出了二分类任务在不可知设定下的最优普适学习速率的完整理论。该理论扩展了Bousquet、Hanneke、Moran、van Handel与Yehudayoff（2021）在可实现情形下的结果，移除了对分布可实现性的假设。我们识别出最优泛化误差率收敛速率的根本四分法：对任意概念类，其最优通用收敛速率必为 $e^{-n}$、$e^{-o(n)}$、$o(n^{-1/2})$，或任意缓慢之一。进一步，我们确定了决定任一概念类属于哪一类的简单组合结构。
原文摘要 · Abstract (English)
We provide a complete theory of optimal universal rates for binary classification in the agnostic setting. This extends the realizable-case theory of Bousquet, Hanneke, Moran, van Handel, and Yehudayoff (2021) by removing the realizability assumption on the distribution. We identify a fundamental tetrachotomy of optimal rates: for every concept class, the optimal universal rate of convergence of the excess error rate is one of $e^{-n}$, $e^{-o(n)}$, $o(n^{-1/2})$, or arbitrarily slow. We further identify simple combinatorial structures which determine which of these categories any given concept class falls into.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。