Adaptive Conformal Inference through the Lens of Blackwell Approachability

Technical Summary: Adaptive Conformal Inference through the Lens of Blackwell Approachability

Problem Statement
Adaptive Conformal Inference (ACI), introduced by Gibbs and Candès (2021), addresses the limitation of standard conformal inference, which relies on the assumption of exchangeability often violated in sequential or time-dependent settings (e.g., time series forecasting). ACI aims to construct prediction sets sequentially such that the empirical coverage converges to a desired level $1-\alpha$ for arbitrary data sequences. While existing ACI strategies guarantee validity (empirical coverage $\geq 1-\alpha$), they generally lack simultaneous theoretical guarantees on efficiency (the average length of prediction intervals). In adversarial settings, no non-trivial efficiency guarantees are possible without additional assumptions, while in exchangeable settings, existing methods often yield suboptimal interval lengths. The core challenge is to design a unified strategy that ensures validity for arbitrary sequences while adapting efficiency to the underlying degree of stochasticity of the data.

Methodology
The authors reformulate ACI as a repeated two-player finite game with vector-valued payoffs.

1. Game Formulation:
   • Learner's Action: Selects a miscoverage level $a_t \in A$, where $A$ is a finite grid derived from the calibration set's order statistics. This determines the prediction set $C_{1-a_t}(x_t)$.
   • Opponent's Action: Selects an outcome $y_t$, which is mapped to a discrete action $b_t \in B$ representing the "tightest" conformal set containing $y_t$.
   • Payoff Vector: The learner receives a vector $m(a_t, b_t) = (1_{b_t \leq a_t}, L(C_{1-a_t}))$, encoding the miscoverage indicator (validity) and the interval length (efficiency).
2. Approachability Framework:
   • The objective is to steer the average payoff vector $m_T$ toward a target set $C_{\alpha, Q} \subseteq [0, \alpha] \times [0, 2L]$.
   • The target set depends on a constraint $Q \subseteq \Delta(B)$ on the opponent's play. $Q$ represents the set of distributions the opponent's actions asymptotically follow.
   • Opportunistic Approachability: The authors employ the theory of Blackwell approachability and its extension by Bernstein et al. (2014), known as opportunistic approachability. This framework allows the learner to approach a smaller, more efficient target set if the opponent's play is restricted to a specific set $Q$, without the learner needing to know $Q$ in advance.
3. Algorithm (BO-ACI):
   • The proposed strategy, Blackwell Opportunistic Adaptive Conformal Inference (BO-ACI), utilizes an auxiliary calibrated forecaster $F$.
   • At each round, $F$ predicts the distribution of the opponent's next action $b_t$.
   • The learner deterministically selects the action $a_t$ that minimizes the expected length while satisfying the validity constraint against the forecasted distribution (via a response function $p^*$).

Key Contributions

1. Game-Theoretic Reformulation: The paper establishes a novel formulation of ACI as a repeated finite game with vector-valued payoffs, explicitly linking validity and efficiency to a multi-objective approachability problem.
2. Unified Strategy (BO-ACI): The authors introduce a strategy based on opportunistic approachability that guarantees validity for any data sequence (stochastic or adversarial) while providing efficiency guarantees that adapt to the unknown stochasticity of the data.
3. "Best of Many Worlds" Guarantees: The strategy achieves a unified set of guarantees:
   • Exchangeable Setting: Recovers the optimal efficiency guarantee $L(C_{1-\alpha})$, matching the performance of standard conformal prediction in ideal conditions.
   • Adversarial Setting: Guarantees validity but accepts the trivial efficiency bound (interval length $2L$), consistent with impossibility results in fully adversarial settings.
   • Intermediate Settings: Provides meaningful efficiency guarantees for scenarios such as single distributional shifts or "almost-exchangeable" data (e.g., time series with weak dependencies), where the interval length adapts to the degree of non-exchangeability.

Results

• Theoretical Convergence: Theorem 19 proves that under the BO-ACI strategy, the average payoff vector $m_T$ converges almost surely to the target set $C_{\alpha, Q}$ for any convex set $Q$ restricting the opponent's play.
• Specific Scenarios:
  • Exchangeable Data: If the opponent is restricted to the uniform distribution $q_{unif}$, the average interval length converges to $L(C_{1-\alpha})$.
  • Single Distributional Shift: If test scores follow a distribution $V$ different from the calibration distribution $S$, the strategy converges to the length $L(C_{1-a_{S,V}})$, where $a_{S,V}$ is the optimal miscoverage level for the shifted distribution.
  • $\epsilon$-Exchangeable/Time Series: For data with small deviations from exchangeability (measured by Total Variation or Kolmogorov distance), the strategy achieves lengths close to the optimal exchangeable length, degrading gracefully as the deviation increases.
  • Adversarial: In the absence of restrictions ($Q = \Delta(B)$), the strategy ensures validity but cannot guarantee efficiency better than the trivial bound, confirming the necessity of $Q$-restrictions for non-trivial efficiency.
• $\epsilon$-Calibration: The results are extended to strategies using $\epsilon$-calibrated forecasters (Theorem 34), providing convergence bounds dependent on $\epsilon$.

Significance and Claims
The paper claims to provide a unified theoretical framework for adaptive conformal inference that resolves the tension between validity and efficiency. By leveraging Blackwell approachability, the authors demonstrate that it is possible to design a single algorithm that:

1. Guarantees validity regardless of the data-generating mechanism.
2. Automatically adapts to the "degree of stochasticity" of the data to maximize efficiency.
3. Recovers known optimal results in extreme cases (exchangeable and adversarial) while offering new, meaningful guarantees in intermediate, realistic scenarios (such as time series forecasting) where previous methods lacked theoretical backing.

The authors position this work as a "best of many worlds" solution, avoiding the need to tune hyperparameters based on the assumed data distribution, as the strategy is "unaware" of the specific $Q$-restriction yet exploits it if it exists. The work also highlights the limitations of the fully adversarial setting, reinforcing that efficiency guarantees require some structural assumption on the data.