Online Quantile Omniprediction for Proper Losses

Hyunsuk Kim; Isaac Gibbs; Michael W. Mahoney; Ryan J. Tibshirani

cs.LGOct 15, 2026

Online Quantile Omniprediction for Proper Losses

Authors: Hyunsuk Kim, Isaac Gibbs, Michael W. Mahoney, Ryan J. Tibshirani

Organizations: Department of Statistics, University of California, Berkeley · Department of Statistics, University of Toronto · ICSI, LBNL, and Dept. of Statistics, University of California, Berkeley

Abstract

The task of constructing a predictor that is simultaneously accurate under multiple evaluation metrics has been popularized recently under the name omniprediction. Prior work in this area has largely focused on binary prediction tasks, and existing results for multiclass and continuous outcomes typically suffer from slow error rates. In this paper, we consider forecasts expressed as a set of quantiles over a discrete but otherwise arbitrary set of probability levels. We develop sample-efficient algorithms for constructing forecasts that are accurate simultaneously across all proper losses that satisfy mild regularity conditions, where proper losses are those minimized by predicting the true quantiles. Our algorithms are online and can operate in a dynamic environment, while simultaneously taking multiple losses into account, and their forecasts offer the potential to provide diverse end-users with rich information for evaluating risk and informing a range of practical decision-making tasks. As an example, we demonstrate how our procedure can be used to ensemble quantile forecasts of COVID-19 hospitalizations made by experts during the pandemic.

Figures & tables

$s(a,o)$	$o=1$	$o=0$
$a=1$	$C$	$C$
$a=0$	$L$	$0$

Table 1: Payoff table

Panel of Figure 1 — Figure 1: Visualization of the discretization on the real line. Outcomes $Y_{t}$ and forecasts $f_{b}^{n}(t)$ take values in the grid $\{0,1/m,...,1\}$ that is interleaved by the values of $\theta_{i}$ .

\displaystyle\hat{\mathbf{P}}(t)=\argmin_{P_{1},...P_{N}\in\Delta_{m}}\max_{P^{y}\in\Delta_{m}}\sum_{i=1}^{m}\sum_{n=1}^{N}\sum_{b=1}^{B}w_{ib}^{n}\mathbb{E}_{q_{n}\sim P_{n},Y\sim P^{y}}[\ell_{\tau_{n},\theta_{i}}(q_{n},Y)-\ell_{\tau_{n},\theta_{i}}(f_{b}^{n}(t),Y)];

(9)

Algorithm 1 Omniprediction under all proper losses for multiple quantile levels

Figure 2: Omni-error (Eq. ( 11 )) over time for

1

- to

4

-week-ahead forecasting horizons (left to right panels) on the US-agg data for *Our algorithm (blue), *Hedge-QL (green) and the COVIDhub-Ens and JHUAPL-SLPEns ensembles (both black). The values of

c_{H},c_{O}

shown in the legend of each panel correspond to the learning rate which achieved the lowest total omni-error. The red line shows the results of our algorithm with a fixed learning rate constant

c_{O}=1

. Lower values indicate better performance.

Panel of Figure 3 — Figure 3: Left: State-level comparison of performance relative to *Our algorithm . Rows show comparisons with three baseline ensembles. Each curve shows a Gaussian kernel density estimate of the difference in total omni-error (left column) or total quantile error (right column) across the $51$ state-level time series for a given forecasting horizon. Values to the right of zero (vertical black dotted line) indicate better performance of our algorithm. Right: Comparison of instantaneous quantile loss realized by *Our algorithm (x-axis) and *Hedge-QL (y-axis). See text for detailed descriptions.

Figure 4: Sensitivity of our algorithm to the choice of learning rate. Each panel shows the performance of our algorithm as a function of the learning rate (blue curve) as measured by the total omni-error (top row) or total quantile loss relative to best base forecaster (bottom row) on the US-agg data. Panels from left to right show results at

1

- to

4

-week time horizons, while horizontal lines indicate the performance of three baseline methods. Lower values indicate better performance.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

\displaystyle V_{n}^{*}=\min_{j\in[m]}V_{n}(j),\qquad j_{n}^{*}=\min\left\{j\mid j\in[j_{n-1}^{*},m],V_{n}(j)=V_{n}^{*}\right\}

(25)

Appendix

Algorithm 2 Full description of Algorithm 1

w_{i}^{s}=\sum_{b=1}^{B}w_{ib}^{s},\qquad I_{i}^{s}=\sum_{b=1}^{B}w_{ib}^{s}\mathds{1}\{\theta_{i}<f_{b}^{s}(t)\},\qquad\forall i\in[m],s\in[N].

Appendix

Algorithm 3 Efficient computation of

V_{n}

and its minimizer

j_{n}^{*}

	$\displaystyle V_{n-1}^{}-V_{n}^{}$	$\displaystyle=\theta_{n-1}^{}(Vcum[\max(k_{n-1}^{},0)])+(VFcum[k_{n}^{}-1]-VFcum[\max(k_{n-1}^{},0)])$
		$\displaystyle\quad+\theta_{n}^{}(1-Vcum[k_{n}^{}-1])-\theta_{n-1}^{}(W[n-1])-\theta_{n}^{}(WB[n])-\sum_{b=1}^{B}w_{b}^{n}f_{b}^{n}(t).$

Appendix

Algorithm 5 Efficient computation of

V_{n-1}^{*}-V_{n}^{*}

for all

n\in[N-1]

Figure 5: Runtime of Algorithm 1 with

c_{O}=1

on U.S.-aggregate, 4-week-ahead prediction data versus grid size

m

( Left ), number of quantile levels

N

( Middle ), and number of base forecasters

B

( Right ). Middle and right plots use grid size

500

w_{b}^{n}(t+1)=\frac{w_{b}^{n}(t)\exp\left(-\eta\rho_{n}(f_{b}^{n}(t),Y_{t})\right)}{\sum_{b=1}^{B}w_{b}^{n}(t)\exp\left(-\eta\rho_{n}(f_{b}^{n}(t),Y_{t})\right)}

Appendix

Algorithm 6 Hedge algorithm for multiple quantile levels in parallel

V_{n}(\theta)=\sum_{s=1}^{n}\sum_{b=1}^{B}w_{b}^{s}\max(f_{b}^{s}(t)-\theta,0)+\sum_{s=n+1}^{N}\sum_{b=1}^{B}w_{b}^{s}\max(\theta-f_{b}^{s}(t),0)

Appendix

Algorithm 7 Two-player game based omniprediction for weighted quantile losses

Panel of Figure 6 — Figure 6: Quantile forecasts for US-agg weekly COVID-19 hospitalizations at $1$ -week-ahead and $4$ -week-ahead horizons. The learning rate for *Hedge-QL and *Our algorithm is selected to achieve the best total omni-error. The black curve shows the observed hospitalizations. The blue shaded regions show nested quantile prediction bands: darker regions correspond to more central quantile intervals, while lighter regions correspond to wider intervals.

Figure 7: Sensitivity of Hedge-QL to the choice of learning rate. Each panel shows the performance of Hedge-QL as a function of the learning rate (green curve) as measured by the total omni-error (top row) or total quantile loss relative to best base forecaster (middle row) on the US-agg data. Panels from left to right shows results at one to four week time horizons, while horizontal lines indicate the performance of *Our algorithm and the two baseline ensembles. Lower values indicate better performance. The bottom row shows the percentage of time steps at which the quantile estimates of Hedge-QL exhibit quantile crossing.

Figure 8: Sensitivity of our algorithm to the grid resolution. Each panel shows the total quantile loss relative to the best base forecaster on the US-agg data as a function of the grid unit

\{1000,500,250,100,50,25\}

(a smaller unit yields a larger grid size

m

). Lower values indicate better performance.

Figure 9: Distribution of standardized ranks of instantaneous quantile loss across all (horizon, location, time) tuples for the

51

state-level series. For each tuple, we rank the available forecasts by quantile loss and normalize the ranks to

[0,1]

. The colored segments represent the empirical distribution of ranks grouped into quartiles.

Probabilistic Forecasting

Probabilistic forecasting predicts distributions or events with quantified uncertainty to support reliable decisions under uncertainty.

See all 230 papers

Multigroup Fairness and Omniprediction: Separations and Equivalences
Oct 5, 2026Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade +3Group Fairness Multicalibration
Stanford University · Apple · University of Oxford +2
Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction
Feb 19, 2026Lunjia Hu, Kevin Tian, Chutong YangBlackwell Approachability Online Learning
Northeastern University · University of Texas at Austin
Online Conformal Prediction: Enforcing monotonicity via Online Optimization
May 12, 2026Eduardo Ochoa Rivera, Ambuj TewariConformal Prediction Uncertainty Calibration
University of Michigan · Ann Arbor, USA

Oct 5, 2026J/K move · Enter open · S save

Multigroup Fairness and Omniprediction: Separations and Equivalences

Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade, Omer Reingold+2

Stanford University · Apple · University of Oxford+2

Group Fairness Multicalibration

Open paper AskPDF arXiv

Omniprediction is a learning guarantee which requires a single predictor to be competitive relative to the best hypothesis from a benchmark class for any loss chosen from a family of loss functions. Loss Outcome Indistinguishability (loss OI for short) is a stronger notion that implies omniprediction. It requires the predicted distribution on labels to be indistinguishable from the true distribution to tests that depend on the loss functions and the benchmark class. Multiaccuracy and multicalibration are multigroup fairness notions that generalize classical notions of calibration and accuracy in expectation. Most known learning algorithms for omniprediction (both for the standard notion and for strengthenings like loss OI) rely on some version of these multigroup fairness notions, or on an intermediate notion called calibrated multiaccuracy. We ask if this is necessary: Does omniprediction require some form of multigroup fairness? We show that the answer is no for (plain) omniprediction, and yes for loss OI. First, a sequence of works shows that multicalibration or calibrated multiaccuracy imply omniprediction. We rule out even a weak converse, by showing that omniprediction for proper losses does not imply even accuracy in expectation, a much weaker notion than any of calibration, multiaccuracy, or multicalibration. Second, prior work showed how to achieve loss OI from a combination of calibration and multiaccuracy. We show a converse: loss OI is equivalent to a form of calibrated multiaccuracy.

Abstract

Probabilistic Forecasting

Explore similar work

Multigroup Fairness and Omniprediction: Separations and Equivalences

Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction

Online Conformal Prediction: Enforcing monotonicity via Online Optimization