Research map / Learning theory and algorithms / Prediction and decision losses

Online Quantile Omniprediction for Proper Losses

NeurIPS 2026 · Learning theory and algorithms › Prediction and decision losses · approach: Algorithms with explicit predictors

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives online algorithms that output a vector of quantile forecasts achieving low omniprediction error simultaneously over all bounded proper quantile losses, with O~(sqrt(1/T)) rates, and demonstrates them on COVID-19 hospitalization quantile ensembling.

Problem

Omniprediction (one predictor that is competitive with the best base forecaster on every proper loss) has been well studied for binary outcomes, but multiclass and continuous outcomes have only slow rates or restricted loss classes. The paper targets quantile forecasts over a discrete set of levels.

Approach

Decompose proper quantile losses into mixtures of two-parameter elementary losses, discretize outcomes to a grid so only finitely many elementary losses matter, and run a Hedge-based multiobjective game in which a minimax program over distributions on the grid yields ordered randomized quantile forecasts with O(sqrt(log(mNB)/T)) omni-error.

Key results

• Across 1- to 4-week horizons on US-agg, the algorithm outperforms COVIDhub-Ens and JHUAPL-SLPEns in total omni-error, with larger gaps at longer horizons.
• Versus Hedge-QL, the algorithm has a small advantage in total omni-error and a larger improvement in total quantile loss, especially at 3 and 4 week horizons.
• Theory: omniprediction error over all bounded proper quantile losses is at most 2(c+1/c) sqrt(log(mNB)/T), with computation O(mNB) per step.

Surprising findings

• Optimizing each quantile level separately does not guarantee ordered forecasts, and post-sorting the separate estimates can increase loss and break the omniprediction guarantee.

Limitations

• Restricted to bounded proper losses over a finite set of quantile levels; excludes unbounded losses and density-based losses such as log-loss.
• Requires outcomes and base forecasts to lie on a discrete grid; continuous targets add O(1/m) error.
• Empirical gains over Hedge-QL are modest in total omni-error.

Experimental setup

Datasets: COVID-19 Forecast Hub weekly hospitalization forecasts (18 groups, 51 locations, 4 horizons, Dec 2020 to Jun 2023)

Benchmarks: COVID-19 Forecast Hub US-agg and 51 state-level series

Metrics: omni-error total quantile loss instantaneous normalized quantile loss

Baselines: COVIDhub-Ens JHUAPL-SLPEns Hedge-QL

Builds on: Omnipredictors (GKR+22) Elementary loss characterization of proper losses (EGJK16) Multiobjective learning game framework (LNPR22) Hedge algorithm COVID-19 Forecast Hub

Closest papers by meaning

• Relaxed Quantile Regression: Prediction Intervals for Asymmetric Noise (ICML 2024 · similarity 0.82)
• Multigroup Fairness and Omniprediction: Separations and Equivalences (NeurIPS 2026 · similarity 0.81)
• Online Time Series Forecasting with Theoretical Guarantees (NeurIPS 2025 · similarity 0.81)
• Conditional Forecasts and Proper Scoring Rules for Reliable and Accurate Performative Predictions (NeurIPS 2025 · similarity 0.80)
• Multi-Source Conformal Inference Under Distribution Shift (ICML 2024 · similarity 0.80)
• Online Conformal Prediction via Online Optimization (ICML 2025 · similarity 0.80)