Conformal Prediction Under Covariate Shift

A point mass at infinity stands in for the unknown test score. The threshold should not use the test score, and in the split case should not depend on $y$ at all. Raising the support points of a discrete distribution that lie above its $\beta$ quantile leaves that quantile unchanged, so $$V_{n+1}\le\mathrm{Quantile}\big(\beta;V_{1:n}\cup\{\infty\}\big)\iff V_{n+1}\le\mathrm{Quantile}\big(\beta;V_{1:(n+1)}\big),$$ and the right side says $V_{n+1}$ is among the $\lceil\beta(n+1)\rceil$ smallest of $n+1$ exchangeable values, which has probability at least $\beta$. The point at $\infty$ takes the place of the test score in the ranking, the same device as the inflated quantile in conformalized quantile regression.

Condition on the unordered sample, and exchangeability says which point is the test point. The paper reproves Lemma 1 in a form that generalizes. Condition on the event $E_v$ that the multiset of scores is $\{v_1,\dots,v_{n+1}\}$; permutation invariance of the density gives $$\mathbb P\{V_{n+1}=v_i\mid E_v\}=\frac{\sum_{\sigma:\sigma(n+1)=i}f(v_\sigma)}{\sum_\sigma f(v_\sigma)}=\frac1{n+1}.$$ Given the multiset, $V_{n+1}$ is a uniform draw from it, so it falls below the $\beta$ quantile of that law with probability at least $\beta$; marginalize and apply Step 1. Exchangeability is used once, to compute the probability that each observed value is the test value.

Under weighted exchangeability that probability is the weight $p_i^w$. Condition instead on the multiset of data points $E_z$, so that the scores $v_i=S(z_i,z_{-i})$ are fixed. With $f=\prod_jw_j\cdot g$ and $g$ symmetric, $g$ cancels: $$\mathbb P\{Z_{n+1}=z_i\mid E_z\}=\frac{\sum_{\sigma:\sigma(n+1)=i}\prod_jw_j(z_{\sigma(j)})}{\sum_\sigma\prod_jw_j(z_{\sigma(j)})}=p_i^w .$$ So $V_{n+1}\mid E_z\sim\sum_ip_i^w\delta_{v_i}$, and Step 1 with the test point's weight moved to $\infty$ gives Theorem 2. The upper bound does not carry over: the largest jump of the conditional CDF is $\max_ip_i^w$, which can be large, where in the unweighted case it is $1/(n+1)$.

Under covariate shift the weights reduce to normalized likelihood ratios. The data are weighted exchangeable with $w_i\equiv1$ for $i\le n$ and $w_{n+1}(x,y)=w(x)$. Only the last slot carries a weight, so each permutation's product is $w$ at the point it sends there, and the sum collapses to $$p_i^w=\frac{w(x_i)}{\sum_{j=1}^{n+1}w(x_j)} .$$ The normalizing constant of $w$ cancels, and the test weight $w(X_{n+1})$ is computable because $X_{n+1}$ is observed. That weight goes on $\infty$: when the test point sits where training data are rare, $p_{n+1}^w$ is large, and once it exceeds $\alpha$ the band is all of $\mathbb R$. The infinite band is how the method reports extrapolation, and the mass at $\infty$ cannot be dropped. In a small check of mine (not in the paper: $n=20$, training $X\sim N(0,1)$, test $X\sim N(1,1)$, noise sd $|X|$, absolute-residual scores, 90% target), the weighted band covered 97.3% and was infinite 40% of the time, unweighted split conformal covered 82.3%, and the weighted quantile with the test mass dropped and the training weights renormalized covered 81.6%, no better than ignoring the shift; at $n=200$ the three were 91.3%, 80.9% and 88.9%, with 0.5% infinite.

The airfoil experiment confirms the correction and shows its cost. The airfoil data ($N=1503$, $d=5$) were split into fitting, calibration and test parts over 5000 trials, and a shifted test set was drawn by an exponential tilt of two covariates. Unweighted split conformal covered 90.2% unshifted and 82.2% shifted; with the true weights the weighted band covered 90.8%, with coverage more dispersed across trials. The dispersion is the loss of effective sample size, $\hat n=\|w(X_{1:n})\|_1^2/\|w(X_{1:n})\|_2^2$: unweighted split conformal calibrated on only $\hat n$ points reproduced it. In practice the ratio is estimated from unlabeled test covariates by a classifier of test against training points, whose odds $\hat w(x)=\hat p(x)/(1-\hat p(x))$ are proportional to the density ratio; logistic regression and random forests both gave 91.0% average coverage, the forest with more variable intervals. The guarantee is proved for the true $w$; with estimated weights it is shown only empirically, on one low-dimensional dataset.

The same lemma applies beyond covariate shift. Any factorization that gives the law of which point is the test point gives weights. If only the law of a low-dimensional $Z$ in $Z\to X\to Y$ shifts, the weight is $\tilde p_Z(z)/p_Z(z)$, avoiding a density ratio in high-dimensional $X$; a second site that shares only covariates and the frequency of a binary attribute gets $w(x)=\sum_z\frac{\pi_B(z)}{\pi_A(z)}\mathbb P_A(Z=z\mid X=x)$; and kernel weights $w(x)\propto K((x-x_0)/h)$ give locally averaged conditional coverage around one chosen center $x_0$, rebuilt per center, consistent with the impossibility of exact conditional coverage.