经验风险的一致收敛

随机上确界 ​

学习理论中的一致收敛研究

$$\underset{h\in \mathcal{H}}{sup}|R_D(h)-{\hat{R}}_S(h)|.$$

若对任意 $\epsilon ,\delta$，样本足够大时该量以至少 $1-\delta$ 的概率不超过 $\epsilon$，便称经验风险在类上高概率一致收敛。这里“uniform”是对 $h$，不同于分析中函数列对输入 $x$ 的一致收敛公理库函数列一致收敛Uniform convergence of functions误差对定义域中所有点可由同一阶段统一控制的函数列收敛。。

它足以保证 ERM：在好事件上，加减经验风险得

$$R({\hat{h}}_{ERM})\le \underset{h\in \mathcal{H}}{inf}R(h)+2\epsilon .$$

逐点大数律只对每个预先固定 $h$ 成立，不能交换 $m\to \mathrm{\infty }$ 与对 $h$ 取上确界。有限类可由并集界完成交换；无限类需组合或度量复杂度。

技术边界 ​

一致收敛是强而通用的证明路线，但“某类可学”不在所有广义设定下都必须通过最朴素的双边上确界证明。无穷类还会出现上确界不可测；标准教材常假定可数类、可分性，或使用外概率。省略技术细节时应明确这是正则性假设，而非上确界天然可测。

逐点而不一致的风险来自“规则会随样本移动”。对每个固定 $h$，大数律可以保证其经验风险收敛；但若类足够丰富，算法总能在看过数据后挑一个专门适配本次经验噪声的 $h_m$，固定规则的收敛速度并未控制这一串变化的选择。上确界正是先把所有可能的数据依赖输出纳入同一个事件。

统一控制也未必必须是双边绝对偏差。可实现一致学习主要需要证明“总体错误大的规则不可能经验错误为零”，不必精确估计每个规则的风险；这解释了它可能获得 $1/\epsilon$ 而非 $1/{\epsilon }^2$。陈述一致收敛时应写清控制绝对偏差、单侧偏差，还是零经验误差的坏事件。

一致收敛的样本复杂度可定义为最小 $m$，使对所有 $D$ 都有

$$\text{Pr}(\underset{h\in \mathcal{H}}{sup}|R_D(h)-{\hat{R}}_S(h)|>\epsilon )\le \delta .$$

这是类—损失对的性质；同一个函数类换成无界平方损失后，原有有界 0–1 结论不再自动成立。

经验 Rademacher 方法常先控制该上确界的期望，再用有界差分把随机上确界集中到其期望附近。组合 VC 证明则先把无限限制化成有限标注计数。两者是同一目标的不同上界机制。

参考资料

• Vapnik, Chervonenkis, 1971.
• van der Vaart, Wellner, Weak Convergence and Empirical Processes, 1996.