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

Oct 5, 2026

Multigroup Fairness and Omniprediction: Separations and Equivalences

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.

Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade +3

Stanford University · Apple · University of Oxford +2

Group Fairness Multicalibration

Ask PDF

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

\mathcal{L}

against a family of comparator predictors

\mathcal{C}

. We initiate the study of omniprediction in a multiclass setting, where the comparator family

\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)

\approx \varepsilon^{-(k+1)}

, for

\varepsilon

-omniprediction in a

k

-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.

Lunjia Hu, Kevin Tian, Chutong Yang

Northeastern University · University of Texas at Austin

Blackwell Approachability Online Learning Multiclass Classification

Ask PDF

May 12, 2026

Online Conformal Prediction: Enforcing monotonicity via Online Optimization

Conformal prediction provides a principled framework for uncertainty quantification with finite-sample coverage guarantees. While recent work has extended conformal prediction to online and sequential settings, existing methods typically focus on a single coverage level and do not ensure consistency across multiple confidence levels. In many real-world applications, such as weather forecasting, macroeconomic prediction, and risk management, different users operate under heterogeneous risk tolerances and require calibrated uncertainty estimates across a range of coverage levels. In such settings, it is desirable to produce prediction sets corresponding to different coverage levels that are nested and valid simultaneously. In this paper, we propose two novel online conformal prediction methods that output nested prediction sets across a range of coverage levels, enabling simultaneous uncertainty quantification across the entire risk spectrum. Beyond interpretability, jointly estimating multiple coverage levels is known to improve statistical efficiency in classical quantile regression by enforcing non-crossing constraints and sharing information across quantiles. Our approaches leverage an online optimization perspective with small regret that translates to quantile estimation error control while enforcing nestedness of prediction sets. Empirical results on synthetic and real-world datasets, including applications in forecasting tasks with heterogeneous risk requirements, demonstrate that our method achieves stable coverage across all levels, strictly nested prediction sets, and improved efficiency compared to existing online conformal baselines.

Eduardo Ochoa Rivera, Ambuj Tewari

University of Michigan · Ann Arbor, USA

Conformal Prediction Uncertainty Calibration

Ask PDF

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