stat.MLFeb 3, 2026

Online Conformal Prediction via Universal Portfolio Algorithms

Authors: Tuo Liu, Edgar Dobriban, Francesco Orabona

Organizations: King Abdullah University of Science and Technology, Saudi Arabia · University of Pennsylvania, USA

Abstract

Online conformal prediction (OCP) seeks prediction intervals that achieve long-run 1−α1-α coverage for arbitrary (possibly adversarial) data streams, while remaining as informative as possible. Existing OCP methods often require manual learning-rate tuning to work well, and may also require algorithm-specific analyses. Here, we develop a general regret-to-coverage theory for interval-valued OCP based on the (1−α)(1-α)-pinball loss. Our first contribution is to identify linearized regret as a key notion, showing that controlling it implies coverage bounds for any online algorithm. This relies on a black-box reduction that depends only on the Fenchel conjugate of an upper bound on the linearized regret. Building on this theory, we propose UP-OCP, a parameter-free method for OCP, via a reduction to a two-asset portfolio selection problem, leveraging universal portfolio algorithms. We show strong finite-time bounds on the miscoverage of UP-OCP, even for polynomially growing predictions. Extensive experiments support that UP-OCP delivers consistently better size/coverage trade-offs than prior online conformal baselines.

Figures & tables

Appendix figures & tables60 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Nov 9, 2026

A Black-Box Reduction from Regret to Multi-Level Coverage

Online Conformal Prediction (OCP) sequentially constructs prediction sets whose average empirical coverage converges to a target level over time, for arbitrary, potentially adversarial datasets. In the multi-level setting, prediction sets are produced at dd coverage levels at once. Prior work argued for the use of online gradient descent with isotonic projections, which produces sets nested across levels, but with a d\sqrt{d} dependence in the per-level coverage convergence rate. Here, we both generalize and improve prior work. First, we show that isotonic projections can be used for the construction of multi-level online conformal prediction sets from any online learning algorithm (not just gradient descent). Then, through a black-box reduction, we show that the linearized regret of the online algorithm itself automatically gives control over both per-level coverage and distributional consistency of multi-level predictions via Fenchel duality. Finally, by using the Weighted Interval Score, a standard scoring rule for assessing multi-level interval forecasts, we prove that these projections reduce both the size of the sets and their under-coverage. We study two instantiations of our theory, pp-norm Online Mirror Descent and coordinate-wise Universal Portfolio methods, both improving the dependence on the number of levels to log⁡d\sqrt{\log d} for the multi-level OCP problem. Experiments on several datasets show favorable performance compared to baselines.
Aug 7, 2026

Online Conformal Prediction Beyond Feedback

Online conformal prediction (OCP) provides theoretically principled uncertainty quantification for arbitrary black-box classifiers and non-i.i.d. data streams by constructing prediction sets that are guaranteed to contain the true label at a user-specified frequency. OCP usually updates prediction sets using feedback from previously deployed predictions. We instead study an OCP setting beyond feedback: on each round, the learner can either output a prediction set or query the correct label, but not both. Thus, no deployed prediction is ever evaluated directly. We reduce this problem to a partial monitoring game in which prediction actions return no observation and a separate query action reveals the label. To solve this game, we develop OCP with queries (OCPQ), a label-efficient forecasting algorithm designed for this beyond-feedback setting. Using an adequate reward construction, for any black-box classifier and any (non-i.i.d.) oblivious data stream of length TT, OCPQ has O(T2/3)O(T^{2/3}) expected regret and expected coverage of at least β−O(T−1/3)β-O(T^{-1/3}) for a user-defined ββ, while querying only an expected T−1/3T^{-1/3} fraction of rounds. This provides coverage comparable to bandit-based OCP methods while requiring no feedback from deployed predictions. Experiments on real-world datasets demonstrate the effectiveness of our approach.
Sep 25, 2026

Counterfactual Online Conformal Prediction Under Adaptive Logging

Online conformal prediction can fail when predictions shape actions and actions determine which outcomes enter calibration. Standard adaptive methods may retain marginal coverage while systematically miscovering the counterfactual outcomes of rarely selected actions. This paper formalizes the failure through counterfactual coverage and introduces Propensity-Weighted Online Conformal Prediction, an inverse-propensity-weighted recursion that debiases calibration. A doubly robust variant further reduces nuisance bias to the product of outcome-model and propensity errors. Under positivity and known logging probabilities, both methods attain the minimax expected coverage rate for nondegenerate calibration. Experiments on synthetic decision tasks, Open Bandit data, and financial rebalancing demonstrate counterfactual coverage gains under selection-biased logging, with prediction-set widths close to those of the oracle in the reported sharpness study.