Achieving best possible predictions across many loss measures
Omniprediction for All Mixable Proper Losses and Beyond
Machine LearningData Structures and Algorithms
Summary
This work studies how to make predictions that perform well under many different ways of measuring errors (called losses). The authors show that when considering infinitely many possible losses, it’s impossible to be very accurate on all at once. However, they provide a method that achieves the best possible accuracy when focusing on a special class of these losses called mixable proper losses. Their method also combines different guarantees to perform well across many common loss types used in practice.
What this means in practice
- •For machine learning engineers: Design prediction systems that maintain strong performance simultaneously across multiple accuracy measures in online settings.
- •For data scientists in finance: Develop models that adaptively optimize for various risk and error metrics simultaneously for financial prediction tasks.
A theory result. No direct application yet.
Authors
Junyan Liu, Haipeng Luo, Lillian J. Ratliff
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(|\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.