近似 ERM 与优化误差

优化误差必须以经验目标值的差来计量，才能和统计误差放进同一条比较链。迭代次数、参数移动或梯度范数只是算法迹象；只有额外的凸性、曲率或误差界把它们转成目标 gap 后，才成为可用于学习保证的证书。

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

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

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

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

一个真实的停止情形 ​

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

边界与辨析 ​

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

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

在随机梯度、坐标下降和近似 oracle 中，算法保证可先统一翻译成 ${\epsilon }_{\mathrm{opt}}$，再与泛化项合并。这样可以比较“继续计算”与“增加数据”的边际收益：当优化误差已远小于统计精度时，进一步压低训练目标不再改善现有总体风险证书。