近似 ERM 与优化误差

概念图像 ​

统计学习有两道彼此独立的缝：有限样本让经验风险偏离总体风险，有限计算又让算法停在经验最优值之上。近似 ERM 专门量第二道缝。它不是“训练得不够久”的口语说法，而是把优化器真正交付的经验目标值与类内最优值放在同一标尺上比较。

定义 ​

对样本 $S$、假设类 $\mathcal{H}$ 和经验风险 ${\hat{R}}_S$，若输出 $\hat{h}$ 满足

$${\hat{R}}_S(\hat{h})\le \underset{h\in \mathcal{H}}{inf}{\hat{R}}_S(h)+{\epsilon }_{\mathrm{opt}},$$

就称它是加性 ${\epsilon }_{\mathrm{opt}}$-ERM。随机优化器的保证还要注明概率来源：例如以至少 $1-{\delta }_{\mathrm{opt}}$ 的概率成立，或只保证期望经验次优不超过 ${\epsilon }_{\mathrm{opt}}$。这两种陈述不能直接互换。

优化误差怎样进入风险界 ​

设 $h^{\ast }\in \arg \underset{h\in \mathcal{H}}{min}R(h)$，并且事件

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

成立。沿着总体风险、经验风险、经验最优和总体最优依次比较，得到

$$R(\hat{h})-R(h^{\ast })\le [R(\hat{h})-{\hat{R}}_S(\hat{h})]+{\epsilon }_{\mathrm{opt}}+[{\hat{R}}_S(h^{\ast })-R(h^{\ast })]\le 2u+{\epsilon }_{\mathrm{opt}}.$$

因此优化误差在这个基本分解中按加法进入；没有统一泛化事件时，仅知道训练目标接近最优并不能推出总体风险接近最优。

一个真实的停止情形 ​

训练凸 Lipschitz 损失时，迭代算法可能在可验证的 primal gap 降到 ${10}^{-3}$ 后停止。如果同一置信事件给出统一泛化项 $u=0.02$，则上式只承诺类内超额风险不超过 $0.041$，而不是 $0.001$。这解释了为什么把数值容差继续压到机器精度，往往不会改善由样本量主导的统计保证。

边界与辨析 ​

梯度范数小、参数移动小或迭代次数多，都不是经验风险次优的定义；把它们转成 ${\epsilon }_{\mathrm{opt}}$ 需要凸性、光滑性或误差界等额外条件。近似比公理库近似比Approximation ratio近似算法解值与最优值之间的最坏情形乘法保证。使用乘法尺度，目标最优值为零、为负或允许平移时会失去合适语义，学习风险通常采用加性容差。还要区分优化容差 ${\epsilon }_{\mathrm{opt}}$ 与 PAC 精度 $\epsilon$：前者是算法求解目标的误差，后者约束最终总体风险。

关系 ​

本页把经验风险最小化公理库经验风险最小化Empirical risk minimization · ERM在假设类中选择训练样本平均损失最小的规则。的精确 argmin 放宽为实际可计算的输出，并把误差交给超额风险分解公理库超额风险与误差分解Excess risk · Error decomposition把相对最优决策的风险差拆成逼近、估计和优化来源。。数值优化中的 stopping criterion 只有在能证明控制经验目标 gap 时，才可作为这里的证书。

参考资料

• Shai Shalev-Shwartz et al., Stochastic Convex Optimization, COLT 2011.
• Léon Bottou, Frank E. Curtis, Jorge Nocedal, Optimization Methods for Large-Scale Machine Learning, SIAM Review, 2018.