Metraipolis › archive › dc_699159b63fe0
Omniprediction for All Mixable Proper Losses and Beyond — arXiv:2610.41023
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.41023
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T08:11:42.620Z
- SHA-256 of the archived text
df389b09988d1a302edea0ddbceab5aa80b6495e96666bc801524fb7f23ad693- Stable URL of this page
https://metraipolis.com/documento/dc_699159b63fe0
How to cite
Omniprediction for All Mixable Proper Losses and Beyond — arXiv:2610.41023 — arXiv (en), https://arxiv.org/abs/2610.41023 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_699159b63fe0 (Metraipolis archive dc_699159b63fe0, sha256 df389b09988d1a302edea0ddbceab5aa80b6495e96666bc801524fb7f23ad693)
BibTeX
@misc{dc699159b63fe0,
title = {Omniprediction for All Mixable Proper Losses and Beyond — arXiv:2610.41023},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.41023},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_699159b63fe0; sha256 df389b09988d1a302edea0ddbceab5aa80b6495e96666bc801524fb7f23ad693},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41023. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Data Structures and Algorithms (cs.DS); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2610.41023 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T08:02:38.902Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).