Finite-Sample Optimal Conformal Prediction Sets under Covariate Shift

Zhongyang Li

stat.MLOct 27, 2026

Finite-Sample Optimal Conformal Prediction Sets under Covariate Shift

Authors: Zhongyang Li

Organizations: Department of Mathematics, University of Connecticut, 341 Mansfield Road, Unit 1009, Storrs, CT 06269-1009, USA

Abstract

We study conformal prediction under covariate shift with a known covariate density ratio, seeking prediction sets with minimum expected length under the target distribution. For every calibration sample size, we prove that the rule combining the inverse conditional-density score with randomized weighted conformal calibration minimizes this expected length among all rules valid over the full weighted-exchangeability class. We approximate the oracle using quantile and kernel histograms, including forest-weighted estimators, and select estimators and tuning parameters by resampling to estimate calibrated target length. On a bounded response domain, we bound excess length linearly in $L^1$ density error at fixed calibration size, without requiring a uniform positive lower bound on the true density. We also bound selection-pool and resampling errors. Under explicit growth conditions, the selected procedure approaches the same oracle while the calibration size remains fixed. Experiments on 36 known-density configurations and four public regression datasets compare coverage, prediction-set length, and runtime with existing methods. In targeted low-coverage and strong-shift comparisons, inverse-density selection yields shorter mean sets in most cases and lower mean runtime than the evaluated weighted baselines, with some differences in achieved coverage.

Figures & tables

Panel of Figure 1 — Figure 1: Alternative selection criteria for inverse-density prediction. Length selection is the primary method; NLL selection is the comparator. Each branch selects one candidate and proceeds separately to final calibration. Training, selection, and final calibration use independent data. See Sections 5 and 6 .

Method	Asymmetric	Heterosc.	Separated	Unequal
Known-density oracle	0.4603 (0.0060)	0.4663 (0.0055)	0.5716 (0.0066)	0.5566 (0.0067)
Density: length selection	0.4647 (0.0062)	0.4660 (0.0054)	0.5746 (0.0069)	0.5583 (0.0064)
Density: NLL selection	0.4639 (0.0060)	0.4644 (0.0055)	0.5740 (0.0066)	0.5563 (0.0066)
Density: one tuning bag	0.4687 (0.0080)	0.4709 (0.0063)	0.5770 (0.0069)	0.5649 (0.0073)
CTI: fixed $B=20$	0.4702 (0.0060)	0.4726 (0.0072)	0.6092 (0.0076)	0.5984 (0.0078)
Density: quantiles only	0.4645 (0.0060)	0.4667 (0.0058)	0.5766 (0.0068)	0.5686 (0.0069)

Table 1: Synthetic expected lengths at

n=8{,}000

training labels per group,

m=200

, ratio

3

, and

p=0.9

. Parentheses are standard errors across 50 independent repetitions. The oracle is the exact finite-

m

weighted density rule, not the population highest-density set. All fitted methods use the same data within a repetition.

Figure 2: Excess expected length above the weighted finite-

m

oracle at

m=200

and shift ratio

3

. Bars are

1.96

times the standard error of the paired oracle difference, computed from 50 independent repetitions. The zero line denotes oracle risk. Training observations are counted per group; design and final calibration sizes stay fixed.

Figure 3: Fixed-

m

comparison of growing-

r_{n}

and

r=30

selection with the prescribed estimator (no selection). Left: paired oracle gaps with

1.96

Monte Carlo standard-error bars over 50 repetitions. Right: mean total time on a logarithmic scale. The design and timing scope are specified in the text.

Method	Power Plant	Concrete	Real Estate	Yacht
Density: length selection	0.0912 (0.0015) 0.8998 (0.0021)	0.2303 (0.0037) 0.9002 (0.0055)	0.2345 (0.0047) 0.9026 (0.0071)	0.0870 (0.0045) 0.9009 (0.0134)
Density: NLL selection	0.0893 (0.0005) 0.8973 (0.0021)	0.2354 (0.0039) 0.9024 (0.0052)	0.2414 (0.0058) 0.9101 (0.0060)	0.0937 (0.0058) 0.8947 (0.0159)
Density: one tuning bag	0.0913 (0.0015) 0.9000 (0.0021)	0.2289 (0.0034) 0.8997 (0.0053)	0.2382 (0.0047) 0.9027 (0.0073)	0.0915 (0.0048) 0.9003 (0.0136)
CTI: fixed QRF	0.1023 (0.0005) 0.8994 (0.0022)	0.3088 (0.0044) 0.8954 (0.0061)	0.3056 (0.0086) 0.9003 (0.0083)	0.2112 (0.0111) 0.8967 (0.0172)
Density: quantiles only	0.0978 (0.0019) 0.9013 (0.0022)	0.2429 (0.0036) 0.8961 (0.0050)	0.2943 (0.0185) 0.8975 (0.0089)	0.1008 (0.0065) 0.8899 (0.0157)
Density: kernels only	0.0893 (0.0005) 0.8973 (0.0021)	0.2310 (0.0040) 0.9015 (0.0054)	0.2361 (0.0045) 0.9037 (0.0066)	0.0821 (0.0036) 0.9029 (0.0141)

Table 2: Main real-data results at shift ratio

3

and nominal coverage

0.9

. Each cell gives expected length on the first line and coverage on the second line, both as mean (split standard error) over 30 shared splits. Coverage is a probability. Length is measured on the training-transformed

[0,1]

scale. Target averages use self-normalized importance weights. All rows use the same randomized weighted final calibration; Gao-style and Ad-EffOrt are the stated weighted adaptations.

A. Common NLL15 fit: change the score
Dataset	HPD $-$ inverse density	DCP-opt $-$ inverse density
Power Plant	$-0.00025$ (0.00025)	$-0.00137$ (0.00029)
Concrete	$-0.00173$ (0.00239)	$-0.01806$ (0.00318)
Real Estate	$-0.00178$ (0.00332)	$-0.00978$ (0.00471)
Yacht	$+0.00375$ (0.00290)	$+0.00477$ (0.00661)
B. Fixed score: length selection $-$ NLL15 selection

Table 3: Controlled length differences at shift ratio

3

. Entries are paired means (standard errors) over 30 splits, on the transformed

[0,1]

response scale. Negative values favor the first method in each difference. Panel A holds the selected density fixed; Panel B holds the score and the labeled tuning budget fixed. Uncertainty describes split variation within each dataset.

		Length (SE)		Coverage (%)		Seconds
Dataset	$p$	Density	DCP-opt	Density	DCP-opt	Density	DCP-opt
Power Plant	0.6	0.04290 (0.00030)	0.04394 (0.00027)	60.39	60.47	5.151	6.453
	0.7	0.05395 (0.00041)	0.05472 (0.00031)	69.87	69.87	5.157	6.470
	0.8	0.06894 (0.00046)	0.06856 (0.00048)	79.91	79.72	5.162	6.497
	0.9	0.09242 (0.00212)	0.08914 (0.00058)	89.97	89.77	5.161	6.453
Concrete	0.6	0.10501 (0.00220)	0.10581 (0.00225)	59.82	59.01	0.299	0.503

Table 4: Inverse-density and DCP-opt length selection at shift ratio

10

: means over 30 paired splits, with length standard errors in parentheses. Length is measured on the training-transformed

[0,1]

scale. Timing is from a separate serial, one-thread run and includes the full fitting, selection, and final calibration/evaluation costs defined in Section 7.6 . Compare times within this table. Coverage and timing standard errors and paired intervals are supplied with the reproduction files.

A. Four split workers; one numerical thread per worker
Method	Power Plant	Concrete	Real Estate	Yacht
Density: length selection	5.7861 (0.0680)	0.3096 (0.0068)	0.1803 (0.0055)	0.1779 (0.0053)
Density: NLL selection	5.4297 (0.0642)	0.2889 (0.0065)	0.1710 (0.0053)	0.1695 (0.0052)
CTI: fixed QRF	1.1620 (0.0259)	0.1088 (0.0034)	0.0707 (0.0025)	0.0762 (0.0027)
HPD score	5.9223 (0.0682)	0.3237 (0.0065)	0.1863 (0.0056)	0.1830 (0.0055)
DCP-opt score	7.4235 (0.0924)	0.5075 (0.0097)	0.2918 (0.0090)	0.2710 (0.0079)

Table 5: Seconds per split at shift ratio

3

and

p=0.9

: means (standard errors) over the 30 splits of Table 2 . Compare methods within each timing panel. Costs follow the protocol above. The density selector is a common reference; † fixed WQ includes unused tuning-input preparation.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Scenario	True HPD $-$ true density	True DCP-opt $-$ true density
Asymmetric	$+0.00055$ (0.00068)	$+0.00338$ (0.00107)
Heteroscedastic	$+0.00033$ (0.00125)	$+0.00033$ (0.00125)
Separated modes	$+0.00022$ (0.00082)	$+0.20079$ (0.00795)
Unequal modes	$-0.00063$ (0.00118)	$+0.20772$ (0.00682)
Asymmetric, no floor	$-0.00024$ (0.00102)	$+0.00123$ (0.00168)
Separated modes, no floor	$+0.00149$ (0.00102)	$+0.25701$ (0.00404)

Appendix

Table 6: True-score length differences in the diagnostic simulations, with

m=200

. Entries are paired means (standard errors) over 50 repetitions. True references are counted once per repetition; uncorrected descriptive

95\%

intervals use the

t_{49}

quantile.

Relative shift weights $(1,10)$
		Length (SE)		Coverage (%)		Time (s)
Dataset	$p$	Density	HPD	Density	HPD	Density	HPD
Power Plant	0.3	0.01746 (0.00021)	0.02004 (0.00019)	30.27	30.83	5.432	5.567
	0.4	0.02486 (0.00023)	0.02635 (0.00026)	40.60	40.87	5.438	5.558
	0.5	0.03347 (0.00033)	0.03445 (0.00024)	50.53	50.21	5.436	5.571
Concrete	0.3	0.04082 (0.00222)	0.04778 (0.00184)	30.87	31.48	0.331	0.348

Appendix

Table 7: Inverse-density and HPD selection at lower coverage levels: means over 30 shared splits, with length standard errors in parentheses. Both methods use the same 12 densities and training-transformed

[0,1]

responses. Timing follows Section 7.6 and charges the full shared fitting cost to each method. Coverage and timing standard errors, and paired intervals, are in the reproduction files.

Method	Power Plant	Concrete	Real Estate	Yacht
Density: length selection	0.0895 (0.0008) 0.8997 (0.0022)	0.2273 (0.0044) 0.8982 (0.0054)	0.2600 (0.0064) 0.8978 (0.0069)	0.0741 (0.0045) 0.8986 (0.0132)
Density: NLL selection	0.0882 (0.0005) 0.8975 (0.0021)	0.2320 (0.0035) 0.9009 (0.0051)	0.2559 (0.0058) 0.8967 (0.0066)	0.0713 (0.0032) 0.8837 (0.0132)
Density: one tuning bag	0.0897 (0.0008) 0.9003 (0.0022)	0.2277 (0.0038) 0.9006 (0.0049)	0.2729 (0.0110) 0.9051 (0.0065)	0.0747 (0.0044) 0.8995 (0.0132)
CTI: fixed QRF	0.1014 (0.0005) 0.8984 (0.0022)	0.3038 (0.0043) 0.8933 (0.0060)	0.3189 (0.0069) 0.8973 (0.0082)	0.1545 (0.0085) 0.8980 (0.0125)
Density: quantiles only	0.0953 (0.0011) 0.9015 (0.0024)	0.2381 (0.0036) 0.8984 (0.0050)	0.2947 (0.0124) 0.8921 (0.0089)	0.0740 (0.0048) 0.8914 (0.0143)
Density: kernels only	0.0882 (0.0005) 0.8975 (0.0021)	0.2253 (0.0037) 0.8999 (0.0054)	0.2588 (0.0060) 0.8982 (0.0067)	0.0708 (0.0030) 0.8993 (0.0135)

Appendix

Table 8: No-shift control at nominal coverage

0.9

. Each cell gives expected length on the first line and coverage on the second line, both as mean (split standard error) over 30 shared splits. Coverage is a probability; length uses the training-transformed

[0,1]

scale. The splits and fitted estimators are shared with the shifted evaluation.

Method	Power Plant	Concrete	Real Estate	Yacht
Density: length selection	0.9053 (0.0024) 0.8980 (0.0024)	0.8988 (0.0100) 0.9006 (0.0056)	0.8403 (0.0104) 0.9238 (0.0086)	1.0000 (0.0000) 0.8708 (0.0187)
HPD score	0.9063 (0.0021) 0.8945 (0.0024)	0.9163 (0.0090) 0.8989 (0.0051)	0.8499 (0.0104) 0.9163 (0.0097)	0.9918 (0.0036) 0.8717 (0.0217)
DCP-opt score	0.9044 (0.0023) 0.8958 (0.0024)	0.9152 (0.0087) 0.8928 (0.0062)	0.8482 (0.0125) 0.9128 (0.0093)	0.9942 (0.0024) 0.8569 (0.0184)
WQ: selected	0.8919 (0.0029) 0.9008 (0.0027)	0.8715 (0.0135) 0.8936 (0.0067)	0.8481 (0.0158) 0.9187 (0.0106)	0.9930 (0.0030) 0.8420 (0.0254)
Gao-style, $k=2$	0.9037 (0.0028) 0.9005 (0.0026)	0.9052 (0.0115) 0.8977 (0.0047)	0.8648 (0.0138) 0.9093 (0.0100)	0.9844 (0.0047) 0.8895 (0.0160)
Ad-EffOrt: tuned	0.9012 (0.0028) 0.8979 (0.0021)	0.8872 (0.0092) 0.9042 (0.0065)	0.8799 (0.0113) 0.9135 (0.0100)	0.9715 (0.0077) 0.8852 (0.0173)

Appendix

Table 9: Coverage in the two input groups defining the ratio-

3

shift. Each cell gives Group 0 on the first line and Group 1 on the second, with split standard errors in parentheses. These are diagnostics, not the coverage constraint optimized by the theorem.

Conformal Prediction

Conformal prediction wraps predictive models with calibrated sets or intervals that provide statistical coverage guarantees.

See all 357 papers

Backward Conformal Prediction under Covariate Shift
Oct 12, 2026Amin Meghrazi, Yuanyuan LiConformal Prediction Weighted Conformal Prediction
The Ohio State University · Munich RE
Sharp training-conditional coverage for conformal prediction under covariate shift
Sep 27, 2026Mehrdad PournaderiWeighted Conformal Prediction Set Prediction
Mofid Securities
Conformal Prediction under Exponential-Tilt Joint Shift
Sep 25, 2026Seungjin ChoiDistribution Shift Robustness Distribution Shift
CROID Research and aSSIST University, Seoul, Korea

Oct 12, 2026J/K move · Enter open · S save

Backward Conformal Prediction under Covariate Shift

Amin Meghrazi, Yuanyuan Li

The Ohio State University · Munich RE

Conformal Prediction Weighted Conformal Prediction Covariate Shift Density Ratio Estimation

Open paper AskPDF arXiv

Backward conformal prediction (BCP) fixes the size of a prediction set and estimates its miscoverage, but assumes calibration and test data are exchangeable. We extend BCP to covariate shift through importance weighting, preserving its guarantees when the density ratio is known. We show that BCP's tight miscoverage report depends only on the relative weight assigned to missed calibration examples, explaining why a better domain classifier can sometimes produce a worse estimate. Motivated by the fact that BCP depends only on nonconformity scores, we propose estimating density ratios on sorted score vectors rather than high-dimensional inputs. We prove that this approach recovers the same report asymptotically under an interpretable condition and characterize the resulting bias otherwise. Experiments with simulated and benchmark distribution shifts show that the proposed method improves BCP's miscoverage estimates, while score-based weighting consistently yields more accurate estimates than embedding-based weighting.

Abstract

Conformal Prediction

Explore similar work

Backward Conformal Prediction under Covariate Shift

Sharp training-conditional coverage for conformal prediction under covariate shift

Conformal Prediction under Exponential-Tilt Joint Shift