VC 类的样本复杂度界

三种常被混在一起的界 ​

在可实现情形，一致 ERM 输出训练错误为零的 $h$。固定一个总体错误超过 $\epsilon$ 的假设，它在 $m$ 个 IID 样本上仍全对的概率至多 $(1-\epsilon {)}^m\le e^{-m\epsilon }$。用增长函数计数样本上可区分的坏行为并取并集，得到经典教材界

这里的 $\log \left(1/\epsilon \right)$ 来自这条证明路线，不是 VC 类可学习性的必然价格。精细的样本压缩/leave-one-out 型构造与递归学习器可消去它，得到上述最优 $O((d+\log \left(1/\delta \right))/\epsilon )$。

不可知情形没有“坏假设在样本上全对”这一单边事件。经验风险差是带噪平均量，要分辨类内最优与差 $\epsilon$ 的候选，通常需要方差尺度 $1/{\epsilon }^2$；VC 一致收敛给出匹配的

量级（采用更精细的 VC/Rademacher 界可避免无关对数）。

具体例子：$d=1$ 阈值为何是 $1/\epsilon$ ​

令 $H$ 是 $[0,1]$ 上阈值分类器，目标阈值为 $a$，输入均匀分布。若学习器输出的阈值与 $a$ 相隔超过 $\epsilon$，中间区间的概率质量便超过 $\epsilon$。在可实现数据中，只要样本落入 $a$ 两侧各自宽度约 $\epsilon$ 的关键区间，就能把误差夹到常数量级的 $\epsilon$ 内；漏掉一个关键区间的概率按 $e^{-m\epsilon }$ 衰减，所以 $m\asymp \log \left(1/\delta \right)/\epsilon$。

这个例子也给出下界图像：若关键区间没有样本，两个相隔 $\epsilon$ 的阈值产生完全相同的观测，学习器无法知道真实者是谁。高维下界则在被打散的 $d$ 个位置上安排许多独立难点，使所需样本线性依赖 $d$。

算法限制与边界 ​

“最优样本复杂度”允许在定义指定的输出范围内选择最合适的 learner。某个自然的一致 ERM、某种固定 tie-breaking，或强制 proper 的学习器公理库Proper 与 Improper 学习Proper learning · Improper learning区分比较类与学习器实际允许输出的函数类。可能带有额外对数或结构代价；不能从存在一个最优 learner 推出所有 proper ERM 都最优。反过来，允许 improper 输出也不会改变上面一般二元 VC 学习的基本量级，但在特定类和计算限制下会显著改变可实现算法。

若 $d=0$、$\epsilon$ 接近常数或 $\delta$ 不小，精确公式需要处理退化项；本页的 $\mathrm{\Theta }$ 陈述针对非退化参数区间。把不可知的 ${\epsilon }^{-2}$ 套到可实现数据会丢失单边结构，把教材式 $d\log \left(1/\epsilon \right)/\epsilon$ 称作信息论下界则把证明松弛误当成问题本身。

这些量级只有在模型轴也写清后才可比较。可实现与不可知学习公理库可实现与不可知学习Realizable learning · Agnostic learning区分类内是否存在零风险解释，以及学习目标是否只是接近类内最优。决定精度是 ${\epsilon }^{-1}$ 还是 ${\epsilon }^{-2}$，proper/improper 之分决定输出是否被限制在 $H$ 内；样本压缩或递归构造可以改善某条上界，却不自动给出多项式时间。实际引用时应同时报告数据假设、输出约束与算法限制，而不是只摘取一个 $\mathrm{\Theta }$ 式。