Omniprediction for All Mixable Proper Losses and Beyond
Organizations: University of Washington. · University of Southern California.
Abstract
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, regret is achievable simultaneously against every predictor in a finite predictor class and for every loss in a finite class of mixable proper losses, while recent advances [OKK25, FP26] show that regret is achievable simultaneously for every loss in a finite class of bounded losses. In this work, we ask whether sublinear regret remains possible when is an infinite class of proper losses. Our first result gives a negative answer in general: even when contains only two linear predictors, it is impossible to achieve sublinear regret simultaneously for all bounded proper losses. We then show that regret is achievable simultaneously for 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 ) 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, regret for all mixable proper losses, and regret for - loss, all Lipschitz losses, all GLM losses, and other structured families.
Figures & tables
| Loss family | Prior results | Our results |
| Finite class of mixable proper losses | ( Chernov and Vovk, 2009 ) | Same Algorithm 3 and Theorem 1.4 |
| Finite class of bounded losses | ( Okoroafor et al., 2025 ; Farina and Perdomo, 2026 ) | Same Algorithm 3 and Theorem 1.4 |
| All mixable proper losses | None | Algorithm 2 and Theorem 1.2 Algorithm 3 and Theorem 1.4 matching lower bound Theorem 1.3 |
| All bounded proper losses or all bounded variation losses | if is -valued for a finite ( Okoroafor et al., 2025 ) | Theorem 1.1 |
| All -Lipschitz losses | ( Okoroafor et al., 2025 ) | Same Algorithm 3 and Corollary 1.5 |
| All generalized linear model (GLM) losses | ( Okoroafor et al., 2025 ) | Same Algorithm 3 and Corollary 1.5 |
Regret Minimization
Regret minimization studies how to make sequential decisions whose cumulative loss or reward approaches the best available comparator in hindsight.
See all 125 papers