Omniprediction concerns making predictions that remain accurate under different loss functions. Early work [CV09] showed that in online learning, for a finite predictor class $\mathcal{F}$ and a finite class of mixable proper losses $\mathcal{L}$, one can achieve $O(\log(|\mathcal{F}||\mathcal{L}|))$ regret simultaneously. Later, [OKK25, FP26] extended this to bounded losses, obtaining $\widetilde{O}(\sqrt{T\log(|\mathcal{F}||\mathcal{L}|)})$ regret. This paper asks whether sublinear regret is still possible when $\mathcal{L}$ is an infinite class of proper losses. First, a negative result is proved: even if $\mathcal{F}$ contains only two linear predictors, sublinear regret for all bounded proper losses is impossible. Then an algorithm is presented that attains $\widetilde{O}(T^{1/3}(\log|\mathcal{F}|)^{2/3})$ regret for all mixable proper losses, and this bound is shown to be optimal up to logarithmic factors. This contrasts sharply with the constant regret achievable for a finite mixable loss class. The algorithm is further extended to a best‑of‑all‑worlds version: it retains the $T^{1/3}$ rate while also inheriting existing guarantees for finite loss classes. By choosing appropriate finite subclasses, the method simultaneously yields constant regret for squared and log losses, $\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, GLM losses, and other structured families.
Review