Transductive conformal inference with adaptive scores

Ulysse Gazin, Gilles Blanchard, Étienne Roquain

Abstract

Conformal inference is a fundamental and versatile tool that provides distribution-free guarantees for many machine learning tasks. We consider the transductive setting, where decisions are made on a test sample of $m$ new points, giving rise to $m$ conformal $p$-values. While classical results only concern their marginal distribution, we show that their joint distribution follows a P'olya urn model, and establish a concentration inequality for their empirical distribution function. The results hold for arbitrary exchangeable scores, including adaptive ones that can use the covariates of the test+calibration samples at training stage for increased accuracy. We demonstrate the usefulness of these theoretical results through uniform, in-probability guarantees for two machine learning tasks of current interest: interval prediction for transductive transfer learning and novelty detection based on two-class classification.

Introduction

Conformal inference has emerged as a robust framework for uncertainty quantification, offering guarantees that prediction intervals will contain the true value with a specified probability. However, most existing literature focuses on marginal guarantees, which ensure coverage for a single, arbitrary new point. In practice, we often encounter the transductive setting, where a batch of $m$ test points is processed simultaneously. In such scenarios, practitioners are concerned with the False Coverage Proportion (FCP) across the entire batch. Because these predictions share the same calibration data, they are statistically dependent, necessitating a more sophisticated theoretical treatment.

Theoretical Innovations: The Pólya Urn Connection

A core contribution of this work is the characterization of the joint distribution of $m$ conformal p-values. The authors prove that these p-values follow a Pólya urn model with $n+1$ colors (where $n$ is the number of calibration points). This insight allows for the derivation of a new Dvoretzky-Kiefer-Wolfowitz (DKW)-type concentration inequality. Unlike the classical DKW inequality designed for i.i.d. variables, this version accounts for the specific dependence structure of conformal p-values, providing a tight "confidence envelope" for their empirical distribution.

Adaptive Scores and Transfer Learning

Standard conformal methods often falter under domain shift, where the training distribution differs from the test distribution. To address this, the paper introduces an adaptive score framework. This approach allows models to be trained using both the labeled training set and the unlabeled covariates of the calibration and test sets. By ensuring the training process is permutation invariant with respect to these unlabeled points, the resulting scores remain exchangeable, preserving the validity of the theoretical guarantees.

Comparison of prediction intervals for transductive transfer learning under domain shift.

As shown in the figure above, the adaptive approach ($ℐ^{\text{transfer}}$) leverages Optimal Transport to map training data to the test domain. This results in prediction intervals that are significantly narrower and more accurate than those produced by "naive" ($ℐ^{\text{naive}}$) or "split" ($ℐ^{\text{split}}$) conformal methods, which do not account for the domain shift effectively.

Key Results and Applications

The proposed framework provides uniform, in-probability guarantees. Unlike "in-expectation" results that average over many possible datasets, these guarantees provide high-confidence bounds (e.g., 99% certainty) for the specific batch of test points at hand.

  • Transfer Learning Superiority: In synthetic regression tasks with significant domain shift, the adaptive method outperformed traditional baselines, maintaining coverage while reducing interval width.
  • Novelty Detection: Evaluated on real-world datasets like "Shuttle," "Credit card," and "Mammography," the adaptive two-class classification scores achieved higher True Discovery Proportions than standard one-class methods while strictly adhering to False Discovery Proportion (FDP) upper bounds.

Conclusion

This work bridges the gap between theoretical exchangeability and practical machine learning pipelines that "peek" at test covariates. By establishing the Pólya urn connection and providing uniform concentration bounds, it enables rigorous uncertainty quantification for complex, multi-prediction tasks in non-stationary environments. While the new DKW-type bound is sharper in most practical regimes, future work may explore hybrid approaches to improve tightness at extremely small p-value thresholds.

Summary updated

Abstract

Conformal inference is a fundamental and versatile tool that provides distribution-free guarantees for many machine learning tasks. We consider the transductive setting, where decisions are made on a test sample of $m$ new points, giving rise to $m$ conformal $p$-values. While classical results only concern their marginal distribution, we show that their joint distribution follows a P\'olya urn model, and establish a concentration inequality for their empirical distribution function. The results hold for arbitrary exchangeable scores, including adaptive ones that can use the covariates of the test+calibration samples at training stage for increased accuracy. We demonstrate the usefulness of these theoretical results through uniform, in-probability guarantees for two machine learning tasks of current interest: interval prediction for transductive transfer learning and novelty detection based on two-class classification.
BibTeX
@inproceedings{gazin2024transductive,
  author = {Ulysse Gazin and Gilles Blanchard and Étienne Roquain},
  title = {{Transductive conformal inference with adaptive scores}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=4KdhbEoDEg},
}
Figure