Omniprediction 关注在不同损失下同时保持预测准确性。早期工作 [CV09] 在在线学习中证明，对有限预测类 $\mathcal{F}$ 和有限混合适当损失类 $\mathcal{L}$，可以实现 $O(\log(|\mathcal{F}||\mathcal{L}|))$ 的 regret。随后 [OKK25, FP26] 将结果推广到有界损失，得到 $\widetilde{O}(\sqrt{T\log(|\mathcal{F}||\mathcal{L}|)})$ 的 regret。本文探讨当 $\mathcal{L}$ 为无限适当损失类时，是否仍能保持次线性 regret。首先给出负面答案：即使 $\mathcal{F}$ 只包含两个线性预测器，也不可能对所有有界适当损失实现次线性 regret。随后构造算法，使得对所有混合适当损失可达 $\widetilde{O}(T^{1/3}(\log|\mathcal{F}|)^{2/3})$ 的 regret，并证明该上界在对数因子之外是最优的。该结果与有限混合损失类可实现常数 regret 的情况形成鲜明对比。进一步，将算法扩展为“全能”版本：在保持上述 $T^{1/3}$ 率的同时，也兼容已有的有限损失类保证。通过适当选择有限类，可同时得到平方损失和对数损失的常数 regret、所有混合适当损失的 $\widetilde{O}(T^{1/3}(\log|\mathcal{F}|)^{2/3})$ regret、以及 $0$-$1$ 损失、所有 Lipschitz 损失、GLM 损失等的 $\widetilde{O}(\sqrt{T\log|\mathcal{F}|})$ regret。
点评