Source-linked AI summary
Online Quantile Omniprediction for Proper Losses
Hyunsuk Kim, Isaac Gibbs, Michael W. Mahoney, Ryan J. Tibshirani
TL;DR
Prior omniprediction work has focused largely on binary prediction, while multiclass and continuous-target results often have slower rates. This paper develops online methods using forecasts at a finite set of quantile levels to achieve simultaneous accuracy over proper losses. Its stated error rate matches single-loss learning up to logarithmic factors, and the approach improves expert COVID-19 hospitalization forecasts.
Problem
Prior omniprediction results largely concern binary prediction, while results for multiclass and continuous outcomes typically have slower rates; choosing one proper loss also need not ensure good performance on others.
Source: §1 · p. 1Method
Results
Takeaways & Limitations
Quantile forecasts provide diverse users information for evaluating risk and guiding decisions, and are used here to summarize uncertainty in practical forecasting.
Source: §1 · pp. 1–2The results cover bounded proper losses over a finite set of quantile levels, not unbounded or full-distribution losses such as density-based log-loss.
Source: §5 · p. 10
Abstract
from arXiv · showhide
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.
1 Introduction
Omniprediction seeks one predictor that performs well across multiple losses, but results beyond binary prediction have often had slower error rates. This paper uses quantile forecasts to develop online methods for simultaneous accuracy across proper losses, with a single-loss-matching rate and a COVID-19 forecasting demonstration.
1 Introduction
- Probabilistic forecasts give users richer uncertainty information than point predictions for evaluating risk and guiding decisions.This is especially relevant when one forecast serves users with different objectives.Source: §1 · p. 1
- Proper losses share the true distribution as a global optimum but penalize deviations asymmetrically, so near-optimality under one loss need not transfer to another.Source: §1 · p. 1
- Prior multiclass and continuous-target omniprediction methods have slower rates, while one general multiclass method's rates deteriorate with the number of classes.For the latter method, the stated online and offline k-class rates are (k/T)1/(k+1) and (k/n)1/(k+1), respectively.Source: §1 · p. 2
- The method targets quantile forecasts because proper quantile losses decompose into a smaller class of elementary losses, and quantiles summarize uncertainty in practical forecasting domains.The paper demonstrates the approach on expert COVID-19 hospitalization forecasts.Source: §1 · p. 2
- ˜O(1/T) omniprediction error matches single-loss learning rates up to logarithmic factors for the proposed online method.The procedure is also used to improve expert quantile forecasts of COVID-19 hospitalizations.Source: §1 · p. 2
2 Preliminaries
The preliminaries define the online quantile-forecasting objective and explain why proper quantile losses can be handled through elementary losses. A vector loss decomposes across quantile levels, connecting the single-quantile characterization to the paper's multi-quantile setting.
2.1 Problem statement
- The online setting allows each outcome distribution to depend on prior outcomes and predictions, with outcomes assumed to lie in [0, 1].Source: §2.1 · p. 2
- At each time, the forecaster predicts a vector of quantile estimates using past outcomes and current base forecasts, seeking performance against the best base forecaster separately for each loss.The comparator may vary by loss, so a fixed base forecaster need not achieve low omniprediction error.Source: §2.1 · pp. 2–3
- Proper losses for quantile levels are minimized by predicting the true quantiles, making them the largest class sharing that common minimizer.Source: §2.1 · p. 3
2.2 Existing characterizations of proper losses
- For one quantile level, sufficiently regular proper losses can be represented as mixtures of elementary losses indexed by a threshold.The representation is described as exhaustive for losses satisfying the stated regularity conditions.Source: §2.2 · p. 3
- An elementary loss has a decision interpretation: choosing whether to take a preventative action at threshold θ corresponds to forecasting a quantile determined by the action and event costs.The paper's example uses hospital capacity as the preventative-action cost context.Source: §2.2 · p. 4
- For vectors of quantiles, proper losses decompose into sums of proper losses for the individual quantile levels.The paper combines this result with the single-quantile mixture characterization to represent losses through elementary losses.Source: §2.2 · p. 4
3 Main theoretical results
The section develops an online method for low omniprediction error across proper quantile losses, reducing the loss class to a finite set and jointly optimizing quantile levels. The algorithm has efficient computation and ordered, minimally randomized forecasts; separate optimization lacks the same ordering guarantee.
3.1 Discretization
- Discretization reduces control of omniprediction error over all proper losses to a finite collection of elementary losses at the specified quantile levels.For continuously distributed outcomes with bounded density, the discretization lemma extends with additive error O(1/m).Source: §3.1 · p. 5
3.2 Algorithm
- Algorithm 1 achieves its desired omniprediction guarantee by combining Hedge over elementary losses with a randomized predictor minimizing worst-case mixture loss.The guarantee assumes outcomes and base forecasts lie on a uniform grid of size m.Source: §3.2 · pp. 5–6
- The randomized forecast uses at most two support values per quantile, can be coupled to preserve quantile ordering, and stays within the base-forecast range.These properties characterize the computed solution to the minmax program.Source: §3.2 · p. 6
- Each step computes the forecast distribution in O(mNB) time, yielding O(mNB) per-step complexity for Algorithm 1.Source: §3.2 · p. 7
- At fixed resolution, enlarging the initial grid interval leaves outputs unchanged through rounds whose outcomes and forecasts remain inside the smaller interval.Thus the data range need not be known in advance; the grid can be enlarged when out-of-range values appear.Source: §3.2 · p. 7
3.3 Comparison with Separate Optimization of Quantile Levels
- Joint optimization guarantees ordered quantile estimates, whereas separate optimization offers no such guarantee and post-sorting may increase loss and fail omniprediction.Source: §3.3 · p. 7
4 Empirical example
The evaluation tests quantile forecasts on COVID-19 hospitalization series against existing ensembles and Hedge-QL. The proposed algorithm is comparable to or better than baselines, with performance gains especially evident on harder tasks.
Experimental setup
- The evaluation covers 127 weeks of weekly aggregated hospitalizations, using 23 quantile levels, four forecast horizons, and 18 groups’ forecasts as base forecasts.It includes 51 state-level series and the US aggregate, comparing against two submitted-forecast ensembles and Hedge-QL.Source: §4 · p. 7
Metrics
- Performance is assessed using approximate cumulative omniprediction error, cumulative quantile loss, and instantaneous normalized quantile loss.The approximate omniprediction error is within a factor of 2 of the true omniprediction error.Source: §4 · pp. 7–8
Results
- On US-agg, the algorithm outperforms COVIDhub-Ens and JHUAPL-SLPEns across all horizons, with larger gaps at longer, more challenging horizons.Hedge-QL performs similarly, with relative performance varying across horizons and learning rates.Source: §4 · p. 8, Figure 2 · p. 8
- With fixed cO = 1, the algorithm performs as well as or better than the baseline ensembles across all horizons.This learning rate minimizes the theoretical bound given in Theorem 3.Source: §4 · p. 9
- Across almost all horizons and learning rates, the algorithm outperforms COVIDhub-Ens and JHUAPL-SLPEns and matches or improves on Hedge-QL.The total quantile loss varies more smoothly with learning rate than total omni-error, but neither metric appears significantly sensitive to it.Source: §4 · p. 9
- The learning-rate sensitivity analysis evaluates total omni-error and total quantile loss over 1- to 4-week horizons against three baseline methods.The algorithm is evaluated over cO ∈ {10^i/4 | i = −8, . . . , 5}.Source: §4 · pp. 8–9, Figure 4 · p. 10
5 Limitations and future work
The method is limited to bounded proper losses over a finite set of quantile levels; it does not cover unbounded losses or losses defined on the full predictive distribution.
5 Limitations and future work
- The results cover bounded proper losses at finitely many quantile levels, not unbounded losses or proper losses on the full predictive distribution.Density-based log-loss requires a forecasted density, which quantile-based representations may not provide for evaluation.Source: §5 · p. 10
A.1 Proof of Lemma 1
The proof uses discretization to relate quantile indicators to nearby grid values, then applies the proper-loss characterization to bound the resulting quantity.
A.1 Proof of Lemma 1
- The proof selects the closest grid value from θ, breaking ties by rounding up, so the threshold indicators agree for the stated range of a.The passage gives the relation 1(θ < a) = 1(θi* < a).Source: §A.1 · p. 13
- The argument combines this indicator relation with the characterization of losses in L1 to derive a bound.The remaining bound is expressed in terms of the maximum possible value of the loss.Source: §A.1 · p. 13
- The proof uses endpoint values of gn and the condition |ℓ| ≤ 1 to bound the sum of the measures Hn([0, 1)).It notes gn(1) − gn(0) = Hn([0, 1)) and compares the maximum loss with the average of two endpoint losses.Source: §A.1 · p. 13
A.2 Proof of Theorem 4
The proof constructs a sorted sequence of minimizing indices and associated distributions, then shows these distributions solve the minimax program and satisfy the theorem’s stated properties.
A.2 Proof of Theorem 4
- The proof establishes a sorted sequence of indices minimizing Vn(j), using monotonicity to resolve any neighboring indices that are out of order.This sorted sequence is used in constructing the distributions P*n.Source: §A.2 · p. 14
- For each quantile level, Proposition 3 constructs P*n with support on two neighboring grid points and establishes properties used in the minimax proof.The distribution is given as (1 − Cn)δkn/m + Cnδ(kn+1)/m.Source: §A.2 · pp. 14–15
- The minimax argument shows Aj ≤ 0 for every grid index and Aj*n = 0 for the selected indices, establishing the required objective value.The proof uses the support of the maximizing distribution on points where Aj = 0.Source: §A.2 · pp. 17–18
- The theorem’s additional properties follow by showing successive P*n distributions are stochastically ordered and that the endpoint distributions obey the stated bounds.The proof establishes P*1 ≥ m1/m almost surely and P*N ≤ m2/m almost surely.Source: §A.2 · p. 18
A.3 Proof of Theorem 3
The appendix supplies proof details for the main regret guarantee and supporting propositions, then describes implementation algorithms and faster computation of their minimizers.
A.3 Proof of Theorem 3
- Theorem 5’s proof combines Hedge’s regret bound with a non-positive minimax-program value to establish the omniprediction-error guarantee.The proof assumes forecasts and targets lie on a uniform grid, with bounded-interval outcomes handled by rescaling.Source: §A.3 · p. 19
A.4 Proof of Proposition 2
- In-range equivalence is preserved when the grid expands by one cell, with an extra normalizing-denominator computation supporting the weight update.The proof distinguishes whether an out-of-range value first appears as a target or a forecast.Source: §A.4 · pp. 19–20
A.5 Single quantile level case
- For one quantile level, the minimax program has value 0, and the proposition gives a closed-form prediction.The passage states that the resulting prediction solves the minimax program.Source: §A.5 · p. 20
B Additional algorithmic details
- Algorithm 2 gives the full main-algorithm procedure, including its data stream, quantile levels, grid, learning rate, and base forecasters.The appendix also identifies efficient subroutines for computing V*_n and θ*_n.Source: B Additional algorithmic details · p. 22
B.1 Efficient subroutine for Algorithm 2
- The subroutine computes V*_n and its minimizing grid index for each n in O(mNB) time.This is the stated complexity for the efficient subroutine.Source: §B.1 · p. 22
B.2 Efficient subroutine for Algorithm 7
- The minimizer θ*_n is found from slope changes in a piecewise-linear objective, with cumulative weights enabling faster search.The appendix states an O(NB) computation for all needed V*_n values and an O(K log(K)) computation for θ*_0, where K is the number of unique forecast values.Source: §B.2 · pp. 22–23
B.3 Runtime analysis
The appendix reports runtime scaling for the main algorithm and introduces two approaches to omniprediction for weighted quantile losses, including a parallel Hedge method.
B.3 Runtime analysis
- Runtime grows linearly with grid size m, quantile levels N, and base forecasters B when each is varied with the other two fixed.The measurements use U.S.-aggregate, 4-week-ahead data; the middle and right plots fix m at 500.Source: §B.3 · pp. 24–25, Figure 5 · p. 24
C Omniprediction under weighted quantile losses
- The weighted-quantile-loss algorithms target a restricted subset of proper losses but avoid discretizing outcomes or base-forecast predictions.The paper introduces two algorithms for this loss class.Source: C Omniprediction under weighted… · p. 25
C.1 Hedge algorithm on each quantile level
- Algorithm 6 runs Hedge separately at each quantile level and provides an omniprediction error bound.The stated per-level guarantee uses convexity of pinball loss and Hedge’s regret bound.Source: §C.1 · p. 26
C.2 Two-player game based algorithm
The two-player game method produces ordered quantile forecasts and has a distinct error-bound and computational profile relative to the parallel-Hedge method. The experiments use COVID-19 hospitalization forecasts across U.S. locations and forecasters.
C.2 Two-player game based algorithm
- The two-player game algorithm’s output does not exhibit quantile crossing and solves the stated minimax program.Its forecasts remain between the minimum and maximum base forecasts and are ordered across quantile levels.Source: §C.2 · pp. 26–28
C.3 Comparison between two algorithms
- Algorithm 7 guarantees no quantile crossing, while Algorithm 6 does not; post-sorting Algorithm 6’s forecasts can increase loss in examples.The passage states that post-sorting does not always decrease loss.Source: §C.3 · p. 29
- Algorithm 7’s error bound depends on output error relative to base forecasters, whereas Algorithm 6’s depends on base-forecaster error.The paper suggests the game method may perform better on harder tasks, where base-forecaster errors are likely larger relative to the comparison error.Source: §C.3 · p. 29
D.1 Experiment details
- The experiment covers 52 location series, 127 weeks from 2020-12-29 to 2023-06-05, and 18 base forecasters.The locations comprise 50 states, DC, and the U.S. aggregate series.Source: §D.1 · p. 30
D.2 Additional plots
The additional plots compare forecast trajectories, learning-rate sensitivity, grid resolution, and standardized ranks. They show that the proposed method ranks above the baseline ensembles across multiple instances, while its accuracy varies little with grid resolution.
D.2 Additional plots
- The proposed algorithm’s forecast intervals are slightly wider than COVIDhub-Ens and Hedge-QL’s, but sharper than JHUAPL-SLPEns’s while tracking observed hospitalizations.The plot shows one- and four-week-ahead forecasts for US-agg weekly hospitalizations.Source: §D.2 · p. 30, Figure 6 · p. 31
- Hedge-QL can exhibit substantial quantile crossing, especially at large learning rates, whereas the proposed algorithm never produces crossings.Figure 7 compares Hedge-QL’s omni-error and quantile loss across learning rates and horizons.Source: §D.2 · p. 30, Figure 7 · p. 31
- Across all four horizons, the proposed algorithm’s total quantile loss varies little with grid unit, so a coarse grid suffices in practice.A smaller grid unit corresponds to a larger grid size m.Source: §D.2 · p. 30, Figure 8 · p. 32
- *Our algorithm and *Hedge-QL rank higher than both ensemble baselines and all base forecasters in the standardized-rank comparison.The first and third quartiles of the proposed algorithm’s ranks are comparable to or higher than those of the ensemble models.Source: §D.2 · pp. 30, 32, Figure 9 · p. 32
E The effect of post-sorting on proper loss functions
The section characterizes when post-sorting preserves or improves proper quantile loss, including a subclass for which it does not increase loss. It also states regularity conditions used for the theoretical results.
E The effect of post-sorting on proper loss functions
- For weighted sums of pinball losses at two quantile levels, the section characterizes when post-sorting does not increase loss and shows that outside those conditions some instance has increased loss.A further subclass with identical functions g_n(x)=g(x) also has non-increasing loss after post-sorting.Source: E The effect of post-sorting on proper… · pp. 33–34
F.1 Regularity conditions
- The stated regularity conditions include (S2) and (VS1), which are conditions on the loss function; (S2) requires differentiability and locally Lipschitz gradient of expected loss.The section notes that (V1), (V3), (V4), and (F1) hold for quantile functionals.Source: §F.1 · p. 34
F.2 Omniprediction for multi-horizon forecast
The appendix extends the omniprediction objective to vector-valued multi-horizon forecasts, minimizing the maximum regret across horizons. It reduces this task to separate horizon-wise minimax problems and also provides a Hedge regret bound used in proofs.
F.2 Omniprediction for multi-horizon forecast
- For multi-horizon forecasts, the objective minimizes the maximum regret across horizons rather than average regret, and the problem reduces to solving a minimax program separately for each horizon.Running Algorithm 1 per horizon and combining the solutions solves the multi-horizon problem.Source: §F.2 · p. 35
F.3 Regret bound of Hedge algorithm
- The appendix gives the Hedge regret bound for an online learning problem with bounded losses and B experts, which is used in the paper’s proofs.The described prediction randomizes among experts.Source: §F.3 · p. 35