提出最优的无差别PAC学习算法，理论性能达极限。

An Optimal Agnostic PAC Algorithm

• 基于有限VC维假设，设计可达到最优风险边界的算法
• 在样本数n下，风险上界逼近理论最低值，误差与√(d/n)成正比
• 适合关注理论极限的机器学习研究者，尤其重视学习复杂度分析

设 $H\subseteq\{-1,+1\}^X$ 为有限VC维 $d\ge1$ 的分类器类，$L$ 表示二元风险，$L^*=\min_{h\in H}L(h)$。我们构造了一个学习器，从大小为 $n$ 的独立同分布样本中，在任意 $0<δ\le 1/2$ 下，以至少 $1-δ$ 的概率满足： $$ L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/δ))}{n}} +\frac{d+\log(1/δ)}{n} \right). $$ 该结果在固定 $L^*$ 条件下，将无差别PAC学习的样本复杂度优化至常数倍最优，与 Devroye、Györfi 与 Lugosi [《Pattern Recognition: A Probabilistic Theory》，Springer, 1996] 所给出的下界一致。

原文摘要 · Abstract (English)

Let $H\subseteq\{-1,+1\}^X$ be a class of finite VC dimension $d\ge1$. Writing $L$ for the binary risk and $L^*=\min_{h\in H}L(h)$, we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\ sample of size $n$, for every $0<δ\le 1/2$, with probability at least $1-δ$, \[ L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/δ))}{n}} +\frac{d+\log(1/δ)}{n} \right). \] This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed $L^*$, matching the lower bounds of Devroye, Györfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。