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ólya 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 premier framework for providing "distribution-free" uncertainty guarantees. Traditionally, these guarantees are marginal: they ensure that a prediction interval will cover the true value with a specified probability (e.g., 95%) on average across many trials. However, in many practical "transductive" scenarios, practitioners are concerned with a specific batch of $m$ test points. In these cases, the goal is to bound the actual proportion of errors within that specific batch with high confidence.
Standard conformal tools often struggle in this setting because conformal $p$-values are not independent; they are exchangeable, tied together by shared calibration data. This paper addresses this gap by providing a new theoretical foundation for transductive conformal inference, enabling rigorous guarantees even when using "adaptive" scores that leverage unlabeled test data to improve accuracy.
Theoretical Framework: The Pólya Urn Model
The authors' primary theoretical contribution is the discovery of a deep connection between conformal inference and classical probability models. They prove that the joint distribution of $m$ conformal $p$-values (based on $n$ calibration points) is equivalent to drawing balls from a Pólya urn with $n+1$ colors. This provides an explicit mathematical structure for the dependencies between test points.
Building on this, they derive a novel DKW-type concentration inequality for the empirical distribution function (ecdf) of these $p$-values. Unlike standard inequalities that assume independence, this new bound accounts for the exchangeable structure inherent in conformal inference. Crucially, because this inequality holds uniformly over all possible thresholds, it allows for "data-driven" decision-making—such as choosing a threshold post-hoc—without compromising the $1-\delta$ confidence guarantee.
Adaptive Scores and Transfer Learning
A significant advantage of this framework is its support for adaptive scores. Most conformal methods assume data is i.i.d. (independent and identically distributed). However, this work formalizes a framework where the scoring function (e.g., a regressor) can be trained using the features (covariates) of both the calibration and test sets. As long as the training process is permutation-invariant, the statistical guarantees remain valid.
This is particularly powerful for transfer learning, where there may be a "domain shift" between the training data and the test data. By using tools like Optimal Transport to align distributions during the scoring phase, the resulting prediction intervals become significantly tighter and more accurate.
Empirical Validation and Error Control
The methods were evaluated on synthetic regression tasks and several real-world novelty detection benchmarks, including the UCI Shuttle dataset, a Credit Card fraud detection dataset, and a Mammography imaging dataset.
The results demonstrate that the new DKW-type bound provides a tight, high-probability upper limit on the False Coverage Proportion (FCP). As shown in the experimental results, the adaptive approach ($\mathcal{I}^{\text{transfer}}$) consistently outperforms naive methods that ignore domain shift, producing more informative intervals while maintaining rigorous error control.
When compared to the classic Simes inequality, the authors found that while Simes can be sharper for extremely small $p$-value thresholds, their DKW-based bound is generally superior across a wider range of practical settings, especially as the number of calibration ($n$) and test ($m$) points increases.
Conclusion
By reinforcing that exchangeability, rather than independence, is the fundamental requirement for conformal inference, this work opens the door for more flexible and adaptive machine learning pipelines. The ability to provide uniform, batch-level guarantees allows practitioners to handle complex tasks like transfer learning and novelty detection with unprecedented statistical rigor. Future work may explore extending these bounds to selective inference and further refining the tightness of the inequalities for extreme thresholds.
Summary updated