样本复杂度、精度与置信度

$m(\epsilon ,\delta )$ 把“数据够多”变成带量词的资源承诺：精度规定允许多大风险差，置信参数规定最多容忍多少抽样失败，样本复杂度给出同一算法在最坏允许分布上满足二者所需的观测数。置信度是成功概率 $1-\delta$，而 $\delta$ 本身是失败概率上界。它不描述某次训练是否走运，也不等同于计算耗时。定义要求所有 $m\ge m_0$ 都满足保证，是因为某个算法可能在特殊样本量上表现异常；只找到一个成功的样本量，不足以给出这个阈值。实际报告的解析上界通常只证明某个 $m_0$ 足够，并未求出定义中的最小值。

期望与高概率要求不能互换。设非负超额风险随机量 $G$ 以概率 $0.01$ 等于 $1$，其余时候为 $0$，则 $\mathbb{E}G=0.01$；但要求 $\text{Pr}(G\le 0.1)\ge 0.999$ 时它失败了。仅由期望界通常只能用Markov 不等式理路Markov 不等式Markov's inequality非负随机变量超过阈值的概率由其期望除以阈值控制。得到 $\text{Pr}(G>\epsilon )\le \mathbb{E}G/\epsilon$，置信依赖会很弱，不能凭期望小就声称对数置信代价。

还应区分充分上界与最优样本数、分布无关与分布依赖、可实现错误与不可知超额风险。渐近一致性只说 $m\to \mathrm{\infty }$ 时收敛，不能替代统一的有限样本阈值；运行时间、查询次数和在线跨度 $T$ 也是不同资源。

独立重复有时能做概率放大理路概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。，但学习器输出好坏未必可验证，多数投票也可能离开原类，所以 $\log \left(1/\delta \right)$ 不能总由一句“重复即可”证明。

把数字代入可校准量级。若希望 Bernoulli 均值误差不超过 $0.05$，失败概率至多 $0.01$，上式给

更精确地，右端为 $1059.663\dots$，取整数上整得到 $1060$；代回失败概率界是 $2e^{-2\cdot 1060\cdot {0.05}^2}<0.01$。这是分布无关的充分条件，不表示 1059 个样本必然失败，也不表示它是最优常数。若事先知道 $p$ 很接近零，利用方差的 Bernstein 型区间可能更省样本；这属于分布条件更强的界。

多参数大 O 也须说明保持哪些量变化。$m=O((d+\log \left(1/\delta \right))/{\epsilon }^2)$ 表示存在统一常数，使所有规定范围内的 $d,\epsilon ,\delta$ 都受控；不能固定 $\delta =0.05$ 做实验后声称已经验证其对数依赖，更不能把训练耗时随 $m$ 增长误报成样本复杂度。

PAC 可学习性理路PAC 可学习性PAC learnability · Probably Approximately Correct learning在可实现设定中，以有限样本和高概率达到任意小总体错误的可学习性。把有限的 $m_{\mathcal{H}}(\epsilon ,\delta )$ 当作存在性要求，VC 样本复杂度界理路VC 类的样本复杂度界VC sample complexity bounds · PAC optimal sample complexity区分二元 VC 类的教材式 ERM 上界、分布无关最优上界与配套下界，明确可实现和不可知情形的不同精度次数。再把它写成维度、精度与置信度的具体函数。下界方法则构造有限样本无法区分的分布族，证明任何算法都不能突破某个数据量级。

在主动学习、统计查询和 bandit 中，资源分别改成标签数、oracle 查询数或交互轮数；它们可以与样本数同时出现，却不能沿用同一符号而不声明访问协议。比较两个结果前，应先对齐风险基准、分布假设、失败概率和被计数的资源。