cs.LGOct 29, 2026

Omniprediction for All Mixable Proper Losses and Beyond

Authors: Junyan Liu, Haipeng Luo, Lillian J. Ratliff

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, O(log⁡(∣F∣∣L∣))O(\log(|\mathcal{F}||\mathcal{L}|)) regret is achievable simultaneously against every predictor in a finite predictor class F\mathcal{F} and for every loss in a finite class L\mathcal{L} of mixable proper losses, while recent advances [OKK25, FP26] show that O~(Tlog⁡(∣F∣∣L∣))\widetilde{O}(\sqrt{T\log(|\mathcal{F}||\mathcal{L}|)}) regret is achievable simultaneously for every loss in a finite class L\mathcal{L} of bounded losses. In this work, we ask whether sublinear regret remains possible when L\mathcal{L} is an infinite class of proper losses. Our first result gives a negative answer in general: even when F\mathcal{F} contains only two linear predictors, it is impossible to achieve sublinear regret simultaneously for all bounded proper losses. We then show that O~(T1/3(log⁡∣F∣)2/3)\widetilde{O}(T^{1/3}(\log|\mathcal{F}|)^{2/3}) 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 TT) 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, O~(T1/3(log⁡∣F∣)2/3)\widetilde{O}(T^{1/3}(\log|\mathcal{F}|)^{2/3}) regret for all mixable proper losses, and O~(Tlog⁡∣F∣)\widetilde{O}(\sqrt{T\log|\mathcal{F}|}) regret for 00-11 loss, all Lipschitz losses, all GLM losses, and other structured families.

Figures & tables

Explore similar work

Aug 27, 2026

Sharp Minimax Regret for Infinite-Memory Logistic Prediction

We study sequential prediction of binary marks whose log-odds are a linear function of all past inputs. The inputs are independent uniform signs. The coefficient of the input observed jj steps earlier is unknown, but its absolute value is at most a known number rjr_j, and ∑jrj≤B\sum_j r_j\le B. A learner is judged by its expected cumulative log loss in excess of the loss of the true conditional probabilities. We show that for every such sequence rr and every horizon TT, the minimax value of this regret lies between c ΓT(r)/max⁡{1,B2}c\,Γ_T(r)/\max\{1,B^2\} and 12ΓT(r)\frac12Γ_T(r), where ΓT(r)=∑j≤Tlog⁡(1+(T−j+1)rj2)Γ_T(r)=\sum_{j\le T}\log(1+(T-j+1)r_j^2) and cc is an absolute constant. The term for lag jj combines the size bound rjr_j with the number T−j+1T-j+1 of rounds in which that lag influences a prediction, and no monotonicity or other regularity of rr is needed. The upper bound is attained by a Bayesian mixture with independent Gaussian priors. For the lower bound, we apply the van Trees inequality at each prediction step and then bound the expected log-determinant of the random matrix whose rows are the lagged input vectors. We also characterize when 12\frac12 is the exact leading constant: for envelopes with a common bound BB, possibly changing with TT, the regret is asymptotic to 12ΓT(r)\frac12Γ_T(r) if and only if ∑j≤Tmin⁡{1,(T−j+1)rj2}=o(ΓT(r))\sum_{j\le T}\min\{1,(T-j+1)r_j^2\}=o(Γ_T(r)). This gives, for example, log⁡2(A2T)/(8α)\log^2(A^2T)/(8α) for rj=Ae−αjr_j=Ae^{-αj}, whereas for rj=Aj−sr_j=Aj^{-s} with s>1s>1 the regret is of order T1/(2s)T^{1/(2s)} and its ratio to ΓT(r)Γ_T(r) stays below 12\frac12. Finally, for a known horizon, an online Newton predictor with features scaled by rjr_j attains regret of order ΓT(r)Γ_T(r) with polynomial computation per round.
Jun 16, 2026

Toward Simultaneously Optimal Regret in U-Calibration

U-calibration studies online forecasting algorithms whose predictions can be consumed by any unknown downstream agent, guaranteeing sublinear regret simultaneously for all proper loss functions. Existing U-calibration algorithms achieve worst-case optimal O(T)O(\sqrt{T}) regret for every bounded proper loss, but they fail to adapt to easier losses: as we show, even for smooth losses such as squared loss, they incur Ω(T)Ω(\sqrt{T}) regret instead of the optimal O(log⁡T)O(\log T) regret. In this work, we show that this limitation is not inherent. Specifically, we design a single forecast algorithm that simultaneously achieves O~(T)\tilde O(\sqrt{T}) regret for every bounded proper loss and O(log⁡T)O(\log T) regret for every bounded smooth proper loss. More generally, our algorithm also attains logarithmic regret for losses that are smooth relative to the log-barrier, which include several non-Lipschitz examples. Our approach is based on a novel variant of Follow-the-Perturbed-Leader (FTPL) in which perturbations are applied directly in the prediction space using self-concordant noise. The resulting analysis also departs substantially from prior FTPL analyses due to the complex nature of this noise and may be of independent interest.
Feb 19, 2026

Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction

Omniprediction is a learning problem that requires suboptimality bounds for each of a family of losses L\mathcal{L} against a family of comparator predictors C\mathcal{C}. We initiate the study of omniprediction in a multiclass setting, where the comparator family C\mathcal{C} may be infinite. Our main result is an extension of the recent binary omniprediction algorithm of [OKK25] to the multiclass setting, with sample complexity (in statistical settings) or regret horizon (in online settings) ≈ε−(k+1)\approx \varepsilon^{-(k+1)}, for ε\varepsilon-omniprediction in a kk-class prediction problem. En route to proving this result, we design a framework of potential broader interest for solving Blackwell approachability problems where multiple sets must simultaneously be approached via coupled actions.