Omniprediction for All Mixable Proper Losses and Beyond

概要

Omniprediction concerns the task of making predictions that are simultaneously accurate with respect to different losses. Earlier results by [CV09] show that in an online learning setting, $O(\log(|\mathcal{F}||\mathcal{L}|))$ regret is achievable simultaneously against every predictor in a finite predictor class $\mathcal{F}$ and for every loss in a finite class $\mathcal{L}$ of mixable proper losses, while recent advances [OKK25, FP26] show that $\widetilde{O}(\sqrt{T\log(|\mathcal{F}||\mathcal{L}|)})$ regret is achievable simultaneously for every loss in a finite class $\mathcal{L}$ of bounded losses. In this work, we ask whether sublinear regret remains possible when $\mathcal{L}$ is an infinite class of proper losses. Our first result gives a negative answer in general: even when $\mathcal{F}$ contains only two linear predictors, it is impossible to achieve sublinear regret simultaneously for all bounded proper losses. We then show that $\widetilde{O}(T^{1/3}(\log|\mathcal{F}|)^{2/3})$ regret is achievable simultaneously for \textit{all} mixable proper losses and that this bound is optimal up to logarithmic factors. This optimal rate stands in stark contrast to the constant (in $T$) regret achievable for a finite class of mixable proper losses. Finally, we extend our algorithm to obtain a best-of-all-worlds result: in addition to the new regret guarantee for all mixable proper losses, the resulting algorithm simultaneously achieves the existing guarantees for finite loss classes. With appropriate choices of these finite classes, our algorithm simultaneously achieves constant regret for squared loss and log loss, $\widetilde{O}(T^{1/3}(\log|\mathcal{F}|)^{2/3})$ regret for all mixable proper losses, and $\widetilde{O}(\sqrt{T\log|\mathcal{F}|})$ regret for $0$-$1$ loss, all Lipschitz losses, all GLM losses, and other structured families.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Omniprediction for All Mixable Proper Losses and Beyond

# 概要
Omniprediction concerns the task of making predictions that are simultaneously accurate with respect to different losses. Earlier results by [CV09] show that in an online learning setting,…

# 原典
https://arxiv.org/abs/2610.41023

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。