Online-to-Batch 转换

独立性是整座桥 ​

$h_t$ 对过去生成的 sigma 代数 ${\mathcal{F}}_{t-1}=\sigma (U,Z_1,\dots ,Z_{t-1})$ 可测，而 $Z_t$ 与它独立，因此

另一方面，对任意固定 $h^{\ast }\in H$，遗憾不等式给

取期望并使用 IID 性，右侧第一项变成 $T{R}_D(h^{\ast })$；再除以 $T$ 并对近似最优 $h^{\ast }$ 取极限，就得到结论。这里不需要把大数定律当作替代证明，真正工作的是“本轮预测尚未看过本轮样本”。

输出方式 ​

随机选择 $h_J$ 适用于任意损失，因为其风险恰是各轮风险平均。如果预测集合是凸的，且 $\ell (\cdot ,z)$ 对预测参数凸，可输出平均参数

Jensen 不等式理路Jensen 不等式Jensen's inequality凸函数作用于平均值不超过函数值的相同加权平均。给 $R_D({\overline{h}}_T)\le T^{-1}\sum _t{R}_D(h_t)$。对二元分类器，参数或标签的算术平均通常不属于 $H$，此时应保留随机迭代，或另行分析多数投票；不能无条件把凸情形的平均步骤搬过来。

失败边界与高概率版本 ​

若算法先看 $Z_t$ 再构造 $h_t$，它可以记住当前标签并令训练损失为零，但 $\mathbb{E}\ell (h_t,Z_t)=\mathbb{E}{R}_D(h_t)$ 已不成立。随机排列的固定有限数据也不等同于 IID 流；无放回抽样需要单独论证。对自适应或漂移分布，比较对象应改成相应序贯风险。

上面的结论是期望保证。要得到高概率风险界，必须再控制鞅差、使用验证样本，或采用带置信转换；不能把期望式中的 $B_T/T$ 原样标上“概率至少 $1-\delta$”。

以在线梯度下降理路在线梯度下降online gradient descent · OGD在每轮凸损失揭示后走一个投影次梯度步，并以距离势函数控制 regret。为例，若凸 $G$-Lipschitz 损失在直径 $D$ 的集合上有 $B_T=O(GD\sqrt{T})$，转换后的批超额风险便是 $O(GD/\sqrt{T})$。对Perceptron理路Perceptron 算法Perceptron · 感知机算法对误分类或零间隔样本沿标签方向更新线性权重的基础在线分类算法。，在同一个有限范数界 $R$ 与正间隔 $\gamma$ 对分布几乎处处成立时，错误界可在 IID 数据上转成随机在线迭代的期望分类错误，但最终权重或投票的保证仍取决于具体输出规则。这个接口也解释了为什么 online no-regret 只控制平均迭代：若需要最后一次迭代保证，还必须引入额外稳定性或曲率。