Online-to-Batch 转换

基本转换 ​

令 $Z_1,\dots ,Z_T\stackrel{\mathrm{I}\mathrm{I}\mathrm{D}}{\sim }D$。在线算法在第 $t$ 轮看到 $Z_t$ 之前，根据 $Z_1,\dots ,Z_{t-1}$ 产生预测器 $h_t$，随后承担损失 $\ell (h_t,Z_t)$。假设对任意序列都有

$$\sum _{t=1}^T\ell (h_t,Z_t)-\underset{h\in H}{inf}\sum _{t=1}^T\ell (h,Z_t)\le B_T.$$

取独立均匀索引 $J\sim \mathrm{Unif}\{1,\dots ,T\}$，输出随机预测器 $h_J$。则

$$\mathbb{E}{R}_D(h_J)\le \underset{h\in H}{inf}{R}_D(h)+\frac{B_T}{T}.$$

若遗憾界只在期望中成立，右侧相应使用期望遗憾。若 $B_T=o(T)$，随机迭代的期望类内超额风险趋于零。

独立性是整座桥 ​

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

$$\mathbb{E}[\ell (h_t,Z_t)\mid {\mathcal{F}}_{t-1}]=R_D(h_t).$$

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

$$\sum _t\ell (h_t,Z_t)\le \sum _t\ell (h^{\ast },Z_t)+B_T.$$

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

输出方式与具体例子 ​

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

$${\overline{h}}_T=\frac{1}{T}\sum _{t=1}^T{h}_t;$$

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

以在线梯度下降为例，若凸 $G$-Lipschitz 损失在直径 $D$ 的集合上有 $B_T=O(GD\sqrt{T})$，批超额风险便是 $O(GD/\sqrt{T})$。对 Perceptron，错误界可在 IID 可分数据上转成随机在线迭代的期望分类错误，但最终权重或投票的保证需要核对所采用的具体转换。

失败边界与高概率版本 ​

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

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

参考资料

• Nicolò Cesa-Bianchi, Alex Conconi, and Claudio Gentile, work on online-to-batch conversions.
• Nicolò Cesa-Bianchi and Gábor Lugosi, Prediction, Learning, and Games.