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

$m(\epsilon ,\delta )$ 把“数据够多”变成带量词的资源承诺：精度规定允许多大风险差，置信参数规定最多容忍多少抽样失败，样本复杂度给出同一算法在最坏允许分布上满足二者所需的观测数。置信度是成功概率 $1-\delta$，而 $\delta$ 本身是失败概率上界。它不描述某次训练是否走运，也不等同于计算耗时。

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

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

把数字代入可校准量级。若希望 Bernoulli 均值误差不超过 $0.05$，失败概率至多 $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 查询数或交互轮数；它们可以与样本数同时出现，却不能沿用同一符号而不声明访问协议。比较两个结果前，应先对齐风险基准、分布假设、失败概率和被计数的资源。