Omniprediction for All Mixable Proper Losses and Beyond
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, O(log(|ℱ||ℒ|)) 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 Õ(√(Tlog(|ℱ||ℒ|))) 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 Õ(T1/3(log|ℱ|)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, Õ(T1/3(log|ℱ|)2/3) regret for all mixable proper losses, and Õ(√(Tlog|ℱ|)) regret for $0−1$ loss, all Lipschitz losses, all GLM losses, and other structured families.
Related
- Online Quantile Omniprediction for Proper Losses
- Generative SDEs with Trainable Diffusion and Density-Based Losses
- Weighted Risk Aggregation under Long-Memory Dependence: Pathwise Fluctuations of Exposure-Weighted Losses
- UMVUE-Type Estimators under Bregman Losses
- A multivariate unsupervised lognormal-GPD mixture for dependent losses
BibTeX
@misc{liu2026omniprediction,
title = {{Omniprediction for All Mixable Proper Losses and Beyond}},
author = {Junyan Liu and Haipeng Luo and Lillian J. Ratliff},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41023},
eprint = {2610.41023},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41023},
}
RIS
TY - UNPB
TI - Omniprediction for All Mixable Proper Losses and Beyond
AU - Junyan Liu
AU - Haipeng Luo
AU - Lillian J. Ratliff
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.41023
UR - https://arxiv.org/abs/2610.41023
AB - 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(|ℱ||ℒ|)) 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 Õ(√(Tlog(|ℱ||ℒ|))) 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 Õ(T^1/3(log|ℱ|)^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, Õ(T^1/3(log|ℱ|)^2/3) regret for all mixable proper losses, and Õ(√(Tlog|ℱ|)) regret for $0−1$ loss, all Lipschitz losses, all GLM losses, and other structured families.
ER -