Technical Summary: Parameter-Free and Group Conditional Online Conformal Prediction

1. Problem Setting and Motivation

Machine learning models are increasingly deployed in high-stakes, non-stationary environments (e.g., medical triage, autonomous vehicles) where data distributions shift over time, violating the exchangeability assumption required by standard Conformal Prediction (CP). Online Conformal Prediction (OCP) addresses this by generating a sequence of prediction sets for adversarial data streams. However, standard OCP methods typically guarantee only marginal coverage (i.e., the overall error rate approaches $1-\alpha$). This marginal guarantee can mask systematic under-coverage for specific subpopulations, leading to fairness and safety issues.

While previous works have proposed Group-Conditional OCP (G-OCP) to ensure coverage guarantees for specific groups, existing methods (e.g., GCACI) rely on learning rates (step sizes) that must be manually tuned. In adversarial or shifting data environments, tuning learning rates is problematic because:

1. No validation set is available for tuning.
2. Arbitrary data shifts can render a previously "good" learning rate inappropriate.
3. Existing parameter-free OCP methods (e.g., UP-OCP) only achieve marginal coverage, not group-conditional guarantees.

The core problem addressed is the design of a parameter-free OCP algorithm that simultaneously provides rigorous group-conditional coverage guarantees without requiring manual hyperparameter tuning.

2. Methodology: POGO

The authors propose POGO (Portfolios for Online Group Conformal), the first parameter-free algorithm for group-conditional OCP. The methodology builds upon the concept of Universal Portfolio (UP) optimization, previously applied to marginal OCP (UP-OCP), and extends it to handle multiple overlapping groups.

2.1 Problem Formulation

Given a stream of data $(X_t, Y_t)$ and a predictor $\hat{Y}_t$, the goal is to learn a sequence of radii $\tau_t$ such that the prediction interval $I_t = [\hat{Y}_t - \tau_t, \hat{Y}_t + \tau_t]$ satisfies:
$$\lim_{T \to \infty} \left| \frac{1}{T_j} \sum_{t=1}^T \mathbb{1}\{Y_t \in I_t\} c_j(X_t) - (1-\alpha) \right| = 0$$
for all $k$ groups, where $c_j(X_t) \in [0, 1]$ is a soft indicator function for group membership, and $T_j$ is the cumulative count of group $j$.

2.2 Linear Parameterization

Unlike standard OCP which learns a scalar radius, POGO learns a $k$-dimensional parameter vector $\theta_t \in \mathbb{R}^k$. The radius is parameterized as a linear function of the group membership vector $c(X_t)$:
$$\tau_t(X_t) = \langle \theta_t, c(X_t) \rangle$$
This allows the algorithm to assign different radii based on the specific group memberships of a sample while ensuring a single, unified prediction interval is produced.

2.3 Portfolio Optimization Mechanism

POGO treats the learning of $\theta_t$ as a portfolio optimization problem.

1. Subgradients as Errors: The algorithm defines a quantile loss (pinball loss) for each group. The subgradient $g_t$ of this loss quantifies the miscoverage error. Specifically, the $j$-th entry of the cumulative subgradient sum $\sum g_{t,j}$ corresponds to the miscoverage error for group $j$.
2. Wealth Processes: For each group $j$, POGO constructs a "market" with two stocks. The returns of these stocks depend on whether the current prediction covers the true label:
   • If the prediction misses (under-coverage), one stock yields a high return.
   • If the prediction covers, the other stock yields a modest return.
3. Universal Portfolio (UP): POGO employs the Universal Portfolio algorithm to learn a sequence of portfolio weights $\lambda_{t,j}$ for each group $j$. The goal is to maximize the logarithmic growth of the "wealth" $W_{t,j}$ associated with each group.
4. Parameter Update: The parameters $\theta_{t,j}$ are derived directly from the wealth processes $W_{t,j}$ and the portfolio weights $\lambda_{t,j}$, ensuring that the cumulative subgradients grow slowly. This slow growth directly translates to bounded group-conditional miscoverage.

Crucially, this process is parameter-free; it does not require a learning rate $\eta$ or step size, relying instead on the intrinsic properties of the Universal Portfolio algorithm.

3. Key Contributions

1. First Parameter-Free G-OCP Algorithm: The introduction of POGO, which provides group-conditional coverage guarantees without manual tuning of learning rates.
2. Rigorous Finite-Time Guarantees: The authors establish theoretical coverage bounds for POGO. The miscoverage rate for group $j$ is bounded by:
   $$\text{MisCov}_T(c_j) \leq \frac{1}{T_j} \left[ U_T(k) + \sqrt{2T_j \alpha(1-\alpha) U_T(k)} \right]$$
   where $U_T(k)$ scales logarithmically with the number of groups $k$ and time $T$. This represents the best known finite-time group-coverage results.
3. Superior Scalability: Theoretical analysis shows POGO's error bound depends logarithmically on the number of groups ($O(\ln k)$), whereas existing parameter-dependent methods (like GCACI) scale with $\sqrt{k}$ and depend heavily on the choice of learning rate.
4. Single-Interval Output: Unlike naive approaches that run separate OCP algorithms for each group (producing $k$ different radii), POGO produces a single radius $\tau_t$ for each sample, avoiding issues with conflicting intervals and potential privacy leaks regarding group membership.

4. Experimental Results

The authors evaluate POGO on synthetic and real-world datasets, comparing it against GCACI (the current standard for group-conditional OCP) and UP-OCP (parameter-free marginal OCP).

4.1 Synthetic Experiments

• Bounded, Gradually Varying Scores: POGO achieves target coverage rates within 3% for all groups and produces the smallest average radii compared to GCACI variants. It maintains high adaptivity, with the longest sequence of consecutive miscoverage events being comparable to the best-tuned GCACI.
• Abrupt Shifts: When data distributions shift abruptly, POGO remains robust. In contrast, GCACI with a fixed learning rate (even a well-tuned one like $\eta=0.01$) suffers from poor adaptivity, exhibiting long sequences of miscoverage until the learning rate is effectively "re-tuned" by the data.
• Unbounded Growing Scores: In scenarios where non-conformity scores grow quadratically for a specific group, most GCACI variants fail to achieve target coverage. POGO consistently achieves coverage closer to the target levels, particularly at high coverage requirements ($1-\alpha \in [0.9, 0.95]$).

4.2 Real-World Data

• MIMIC-IV (ICU Length of Stay): Using patient data (race, insurance, sex as groups), POGO achieves coverage comparable to GCACI but with smaller prediction set sizes (radii).
• Stock Market (Apple, Delta, Boeing): For daily price prediction, POGO again demonstrates competitive performance, achieving target coverage with smaller set sizes than GCACI.
• Trade-offs: While POGO sometimes exhibits slightly longer consecutive miscoverage streaks than the best-tuned GCACI in specific static regimes, it significantly outperforms GCACI in dynamic or shifting regimes where tuning is impossible.

5. Significance and Claims

The paper claims that POGO lays a foundation for fair and robust uncertainty quantification in shifting environments. By unifying group-conditional coverage with parameter-free online learning, the method eliminates the need for manual hyperparameter tuning, which is a critical bottleneck in adversarial or non-stationary settings.

The authors emphasize that:

• POGO provides the best known finite-time group-coverage bounds.
• It achieves these guarantees without the fragility of learning rate selection.
• It offers a practical solution for high-stakes applications where fairness across subpopulations is required, and where data distributions cannot be assumed to be static or exchangeable.

The paper concludes modestly, noting that while POGO uses a linear specification for radii, future work could explore richer models for the radius and extend these tools to other forms of online uncertainty quantification, such as calibration.