揭示了非可实现下经验风险最小化学习率的三种可能类型
Universal rates of ERM for agnostic learning
- 在不可实现设定下分析经验风险最小化的通用学习率
- 发现三类可能速率：指数衰减、快于1/√n、任意缓慢
- 给出概念类别的完整分类，适用于理论研究者
通用学习框架旨在获得对任意固定分布都成立的学习速率保证，其速度远超对所有分布一致成立的速率。尽管经验风险最小化（ERM）是PAC理论的基础且在实际机器学习中广泛应用，但现有工作仅研究了可实现情形下的通用速率。事实上，大多数通用学习文献集中于可实现情况，而对不可实现情形的研究几乎空白。本文研究了在不可实现设定下，通过经验风险最小化进行二分类的通用学习问题，其中'学习曲线'反映过拟合风险随样本量增加的衰减趋势。我们探索了不可实现通用速率的可能性，揭示了一个简洁的三分类结构：存在三种可能的不可实现通用速率，分别为$e^{-n}$、$o(n^{-1/2})$或任意缓慢。我们给出了概念类落入每类的具体刻画，并进一步建立了目标依赖与贝叶斯依赖通用速率的完整分类。
原文摘要 · Abstract (English)
The universal learning framework has been developed to obtain guarantees on the learning rates that hold for any fixed distribution, which can be much faster than the ones uniformly hold over all the distributions. Given that the Empirical Risk Minimization (ERM) principle being fundamental in the PAC theory and ubiquitous in practical machine learning, the recent work of arXiv:2412.02810 studied the universal rates of ERM for binary classification under the realizable setting. However, the assumption of realizability is too restrictive to hold in practice. Indeed, the majority of the literature on universal learning has focused on the realizable case, leaving the non-realizable case barely explored. In this paper, we consider the problem of universal learning by ERM for binary classification under the agnostic setting, where the ''learning curve" reflects the decay of the excess risk as the sample size increases. We explore the possibilities of agnostic universal rates and reveal a compact trichotomy: there are three possible agnostic universal rates of ERM, being either $e^{-n}$, $o(n^{-1/2})$, or arbitrarily slow. We provide a complete characterization of which concept classes fall into each of these categories. Moreover, we also establish complete characterizations for the target-dependent universal rates as well as the Bayes-dependent universal rates.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。