Non-exchangeable Conformal Prediction with Optimal Transport: Tackling Distribution Shifts with Unlabeled Data

Alvaro H. C. Correia, Christos LouizosarXiv 2025 · DOI · arXiv

Introduction

Conformal Prediction (CP) has emerged as a robust framework for uncertainty quantification, providing finite-sample coverage guarantees. However, these guarantees are predicated on the exchangeability assumption—the requirement that calibration and test data are drawn from the same distribution. In real-world applications, distribution shifts (e.g., sensor noise, demographic changes) frequently violate this assumption, leading to overconfident models and a significant drop in empirical coverage.

The Challenge of Distribution Shift

When exchangeability fails, a model designed for 90% coverage might only achieve 30% in practice. Traditional remedies often rely on specific assumptions about the shift (like covariate shift) or require labeled data from the target distribution, which is rarely available. This paper proposes a more flexible approach that leverages unlabeled test data and Optimal Transport (OT) to restore coverage guarantees without prior knowledge of the shift type.

Methodology: Optimal Transport for Score Alignment

The core insight of this work is that while distribution shifts in high-dimensional input spaces are complex, their impact on CP is entirely mediated by the 1D distribution of nonconformity scores.

1. The Total Coverage Gap

The authors define a "Total Coverage Gap" metric that aggregates error across all target coverage levels. They demonstrate that this gap is mathematically bounded by the 1-Wasserstein distance between the calibration and test score distributions.

2. Sandwiching Unlabeled Data

Calculating the Wasserstein distance requires test scores, which depend on unknown labels. To circumvent this, the authors introduce a "sandwiching" technique. They construct auxiliary distributions ($s_\sharp Q^\downarrow$ and $s_\sharp Q^\uparrow$) that are guaranteed to bound the true, unknown test score distribution. For classification, these bounds are derived from the minimum and maximum possible scores across all potential labels for each unlabeled sample.

The unknown test score distribution (blue) is successfully bounded by auxiliary "sandwich" distributions (green/orange/red) derived from unlabeled data.

3. Learning Optimal Weights

By minimizing the OT-based upper bound using gradient descent, the framework learns importance weights for the calibration data. This process effectively "morphs" the calibration distribution to match the target test distribution, which is then used in a weighted split conformal prediction pipeline.

Experimental Evaluation

The method was tested across three distinct benchmarks:

  • Synthetic Regression: Handling covariate shift via exponential tilting.
  • ImageNet-C: Addressing 15 types of digital corruptions (blur, noise, weather) at varying severities.
  • iWildCam: Navigating natural distribution shifts (different locations, lighting) in wildlife monitoring.

Key Results and Insights

The OT-based reweighting significantly outperforms standard CP and traditional likelihood ratio estimation. On ImageNet-C (Severity 5), where uncorrected coverage plummeted to 30%, the proposed method restored it to between 70% and 80%.

The OT-based methods (green and gray dashed lines) significantly reduce the coverage gap compared to the uncorrected "Raw" scores (red), tracking the ideal diagonal more closely across all target levels.

Unlike likelihood ratio methods that struggle with high-dimensional density estimation, this approach operates on 1D score distributions, making it computationally efficient and model-agnostic. It doesn't require knowing the specific nature of the shift, only access to a batch of unlabeled test data.

Conclusion and Future Work

This framework provides a principled way to maintain CP guarantees under unknown distribution shifts. While the "sandwich" bounds can become loose if the underlying model is highly uninformative, the method offers a significant step forward for reliable uncertainty quantification in the wild. Future work may involve using domain-specific knowledge, such as label hierarchies, to further tighten these bounds and improve coverage precision.

Summary updated

Abstract

Conformal prediction is a distribution-free uncertainty quantification method that has gained popularity in the machine learning community due to its finite-sample guarantees and ease of use. Its most common variant, dubbed split conformal prediction, is also computationally efficient as it boils down to collecting statistics of the model predictions on some calibration data not yet seen by the model. Nonetheless, these guarantees only hold if the calibration and test data are exchangeable, a condition that is difficult to verify and often violated in practice due to so-called distribution shifts. The literature is rife with methods to mitigate the loss in coverage in this non-exchangeable setting, but these methods require some prior information on the type of distribution shift to be expected at test time. In this work, we study this problem via a new perspective, through the lens of optimal transport, and show that it is possible to estimate the loss in coverage and mitigate arbitrary distribution shifts, offering a principled and broadly applicable solution.
BibTeX
@misc{correia2025non,
  author = {Alvaro H. C. Correia and Christos Louizos},
  title = {{Non-exchangeable Conformal Prediction with Optimal Transport: Tackling Distribution Shifts with Unlabeled Data}},
  year = {2025},
  eprint = {2507.10425},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.10425},
}
Figure