Technical Summary: Online Conformal Prediction via Online Optimization

Problem Statement

Conformal prediction offers a principled framework for uncertainty quantification with finite-sample coverage guarantees. While recent advancements have extended these methods to online and sequential settings, existing approaches typically operate at a single coverage level ($1-\alpha$). When multiple coverage levels are required simultaneously—a common scenario in applications like weather forecasting, macroeconomic prediction, and risk management where users have heterogeneous risk tolerances—standard online methods must be run independently for each $\alpha$.

This independent execution leads to a critical limitation: the resulting prediction sets are not guaranteed to be nested. In practical terms, a prediction set for a higher confidence level (e.g., 99%) should be a superset of the set for a lower confidence level (e.g., 90%). Without this nesting property, the uncertainty estimates can be incoherent and difficult to interpret. Furthermore, independent estimation fails to leverage the statistical efficiency gains known from joint quantile regression, where enforcing non-crossing constraints allows for information sharing across quantiles.

The paper addresses the challenge of developing online conformal prediction methods that simultaneously output nested prediction sets across a range of coverage levels while maintaining long-run coverage guarantees, even under non-stationary or adversarial data sequences.

Methodology

The authors propose two novel algorithms based on an online optimization perspective. They frame the problem of updating conformal thresholds as an online learning task where the goal is to minimize a joint loss function while enforcing monotonicity constraints on the thresholds.

1. Problem Formulation

Let $s_t$ be a bounded nonconformity score at time $t$. For a sequence of miscoverage levels $0 = \alpha_0 < \alpha_1 < \dots < \alpha_K < \alpha_{K+1} = 1$, the goal is to estimate thresholds $q_{t,i}$ such that the prediction sets $C^i_t = \{y : s_t(x,y) \le q_{t,i}\}$ are nested ($C^{i+1}_t \subseteq C^i_t$). This requires the thresholds to be monotonically decreasing: $q_{t,1} \ge q_{t,2} \ge \dots \ge q_{t,K}$.

Standard online updates (e.g., Adaptive Conformal Inference) treat each quantile independently:
$$q_{t+1,i} = q_{t,i} - \eta_t (\alpha_i - \text{err}_{t,i})$$
where $\text{err}_{t,i}$ is the indicator of miscoverage. This approach lacks coupling between levels and does not guarantee monotonicity.

2. Proposed Algorithms

The paper introduces two methods that modify the update rule to enforce monotonicity via online optimization techniques:

A. Exponentiated Gradient (EG) Descent

This method leverages the Exponentiated Gradient algorithm applied to a transformed parameter space.

• Parameterization: Instead of updating thresholds directly, the algorithm updates the normalized gaps between consecutive quantiles ($w_{t,i}$) on a truncated simplex. This change of variables ($q_{t,i} = B \sum_{j=i}^K w_{t,j}$) inherently ensures that if the weights are non-negative, the quantiles are ordered.
• Update Rule: The algorithm minimizes a joint loss function $g_t(\bar{w})$ using EG updates. The gradient for each coordinate aggregates miscoverage discrepancies across all relevant quantile levels, inducing a global coupling.
• Mechanism: When the method is overly conservative or undercovers, the cumulative error term adjusts the gaps across the entire quantile curve simultaneously. This allows the method to "borrow strength" across levels, coordinating adjustments to preserve nestedness naturally.

B. Projected Gradient (PG) Descent

This method utilizes Projected Gradient descent with a specific constraint set.

• Update Rule: The algorithm first performs independent gradient updates on the quantile vector $\bar{q}_t$ based on the joint loss.
• Projection: The resulting vector is then projected onto the convex set of decreasing sequences ($Q = \{\bar{q} : B \ge q_1 \ge \dots \ge q_K \ge 0\}$).
• Mechanism: This projection is implemented using the Pool Adjacent Violators Algorithm (PAVA). Unlike EG, PG operates via local correction: it updates quantiles independently and then minimally adjusts them to restore the ordering constraint. It does not inherently redistribute information across levels during the gradient step.

3. Theoretical Guarantees

The authors establish theoretical bounds for both methods:

• Coverage: Both methods provide long-run coverage guarantees, ensuring that the empirical miscoverage rate converges to the target $\alpha_i$ for all levels.
• Regret and Error: The paper derives bounds on the dynamic regret and the deviation of estimated quantiles from the true quantiles ($\|\bar{q}_t - \bar{q}^*_t\|_2$). These bounds depend on the dynamic variation of the true quantiles ($V_T$) and the step size $\eta$. The EG method's bound suggests improved efficiency due to the structured coupling, while PG guarantees feasibility (nestedness) at every time step.

Key Contributions

1. Novel Formulation: Introduction of an online conformal prediction framework that produces nested prediction sets across multiple coverage levels, enabling calibrated uncertainty quantification over the full risk spectrum.
2. Algorithmic Innovation: Proposal of two online algorithms (EG and PG) based on convex optimization that jointly estimate conformal thresholds while strictly enforcing monotonicity.
3. Theoretical Guarantees: Establishment of long-run coverage guarantees for all levels alongside proofs ensuring nested prediction sets at every time step.
4. Empirical Validation: Demonstration that these methods achieve stable coverage, strictly nested sets, and improved statistical efficiency compared to independent single-level baselines.

Experimental Results

The methods were evaluated on both synthetic and real-world datasets.

Synthetic Data

• Setup: A non-stationary environment where score distributions evolve via a latent reflected random walk.
• Findings: The Exponentiated Gradient (EG) method achieved a lower $\ell_1$ tracking error compared to the independent quantile tracker and the Projected Gradient method. This supports the hypothesis that sharing information across quantiles improves statistical efficiency in tracking time-varying distributions. The PG method performed similarly to the independent tracker, indicating limited gains from joint optimization in this specific setting compared to EG.

Real-World Data (US Inflation)

• Setup: Forecasting US Consumer Price Index (CPI) inflation using an AR(3) model with rolling windows.
• Findings:
  • Calibration: All methods eventually converged to low calibration error. However, the unconstrained quantile tracker exhibited oscillatory behavior (overcorrection), while the proposed constrained methods showed more stable trajectories.
  • Nestedness & Smoothness: Baseline methods (independent tracker and post-hoc projection) produced prediction bands with occasional distortions and non-nested regions. In contrast, the proposed methods (especially EG) produced smoother, more coherent prediction sets that strictly preserved the nested structure.
  • Interpretability: The EG update yielded smoother prediction bands by coordinating adjacent quantiles through cumulative discrepancies, reducing abrupt changes across levels.

Significance and Claims

The paper claims that its primary significance lies in addressing the incoherence of uncertainty estimates in multi-level online settings. By enforcing structural constraints (monotonicity) through online optimization, the proposed methods provide a coherent risk spectrum.

Key claims include:

• Statistical Efficiency: Joint estimation improves efficiency by sharing information across quantiles, a benefit explicitly demonstrated by the EG method's superior tracking performance.
• Interpretability: The resulting nested prediction sets are essential for decision-making contexts where stakeholders require consistent uncertainty estimates across different risk tolerances (e.g., emergency planners vs. policymakers).
• Stability: Enforcing monotonicity jointly with updates stabilizes the learning dynamics, preventing the erratic oscillations seen in unconstrained trackers.
• Broader Context: The work bridges the gap between adversarial robustness (guarantees in worst-case settings) and statistical efficiency (tracking time-varying distributions), framing online conformal prediction as a problem of tracking time-varying quantiles with dynamic regret analysis.

The authors note that future work could explore adaptive learning rates to further enhance performance in non-stationary environments, but the current contribution focuses on the structural benefits of joint estimation under fixed step-size regimes.