Online Conformal Prediction Beyond Symmetric Intervals and Toward Conditional Validity

§ Problem Statement

Setup

Fix a target miscoverage level $\alpha\in(0,1)$ . In online conformal regression, at each round $t=1,2,\dots$ , an adversarially generated pair $(X_t,Y_t)$ is revealed sequentially. Before observing $Y_t$ , the learner outputs a center prediction $\hat Y_t$ and a prediction radius $b_t\ge 0$ , producing the symmetric interval

\hat C_t(b_t)=[\hat Y_t-b_t,\,\hat Y_t+b_t].

Define the nonconformity score and miscoverage indicator by

S_t:=|Y_t-\hat Y_t|,\qquad M_t:=\mathbf 1\{Y_t\notin \hat C_t(b_t)\}=\mathbf 1\{S_t>b_t\}.

The standard online target is long-run calibration

\lim_{T\to\infty}\left|\frac1T\sum_{t=1}^T M_t-\alpha\right|=0.

The paper develops a regret-to-coverage reduction for this interval setting using pinball loss and linearized regret, and proposes a parameter-free universal-portfolio method (UP-OCP) with finite-time miscoverage guarantees under polynomial score growth assumptions such as $S_t\le D t^q$ .

Unsolved Problem

Extend this theory and algorithmic guarantee beyond one-dimensional symmetric intervals to richer online prediction-set families and conditional/feature-dependent calibration targets. Concretely, for a set-valued family $\{\hat C_t(\theta):\theta\in\Theta\}$ (not necessarily centered intervals) and a class of feature subsets $\mathcal G$ , design an online algorithm with finite-time guarantees of the form

\sup_{g\in\mathcal G}\left|\frac{\sum_{t=1}^T \mathbf 1\{X_t\in g\}\big(\mathbf 1\{Y_t\notin \hat C_t(\theta_t)\}-\alpha_g\big)}{\sum_{t=1}^T \mathbf 1\{X_t\in g\}\vee 1}\right| \to 0,

while simultaneously controlling average set size (or another informativeness functional) in adversarial online regimes.

§ Discussion

Loading discussion…

§ Significance & Implications

This asks for a parameter-free online conformal theory that handles realistic prediction sets (not only symmetric radii) and finer calibration notions than global marginal miscoverage. Solving it would connect adversarial online learning guarantees to practically important conditional reliability targets.

§ Known Partial Results

Liu et al. (2026): proves a linearized-regret-to-miscoverage reduction for interval OCP and gives finite-time miscoverage bounds for UP-OCP under polynomial score growth.
Liu et al. (2026): The same source explicitly identifies extension beyond symmetric intervals and toward conditional/feature-dependent validity as an open direction (Discussion section).
Liu et al. (2026): Prior online/adaptive conformal methods provide global or shift-adaptive guarantees in specific settings, but do not close this general adversarial conditional-validity problem for richer set classes.

§ References

[1]

Online Conformal Prediction via Universal Portfolio Algorithms

Tuo Liu, Edgar Dobriban, Francesco Orabona (2026)

arXiv preprint

📍 Section 2 (problem setup), Section 4 (UP-OCP and finite-time coverage), and Section 6 (Discussion: open directions beyond symmetric intervals and toward conditional/feature-dependent validity).

arXiv ↗

[2]

Adaptive Conformal Inference Under Distribution Shift

Isaac Gibbs, Emmanuel Candès (2021)

NeurIPS

📍 Adaptive online/sequential conformal calibration under shift; baseline context for online conformal methods.

arXiv ↗

§ Tags

online-conformal-prediction universal-portfolio conditional-coverage adversarial-online-learning