arXiv CSopen access

Conformalized Quantile Regression and Minimax Limits of Fixed-Score Calibration under Known Covariate Shift

Conformalized Quantile Regression and Minimax Limits of Fixed-Score Calibration under Known Covariate Shift

arXiv:2609.24929v1 [math.ST] 21 Sep 2026

Rustam Isaev1,2∗

1 2 3 4 5

Anton Conrad3 Denis Belomestny1,4 Sergey Samsonov1

Eric Moulines3,5

Faculty of Computer Science, HSE University, Moscow, Russia Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, Moscow, Russia Laboratoire de Recherche d’EPITA, Le Kremlin-Bicêtre, France Faculty of Mathematics, University of Duisburg-Essen, Essen, Germany Computing and Mathematical Sciences Division, Mohamed bin Zayed University of Artificial Intelligence (MBZUAI),

Abu Dhabi, United Arab Emirates

Abstract In this paper, we study nonasymptotic Lp error bounds for interval length and conditional coverage in split conformalized quantile regression (CQR). Our bounds rely on local regularity conditions and accuracy guarantees for the estimated quantiles. We further instantiate our bounds for quantile regression with sparse ReLU neural networks. We also consider covariate shift, where the calibration and test covariates have different distributions, and derive nonasymptotic bounds for this setting. We obtain matching minimax upper and lower bounds in expectation for two constructed fixed-score calibration benchmarks under known covariate shift. The bounds match for every p ∈ [1, ∞] in the scalar problem and for finite p in the K-threshold problem; for the latter, a high-probability minimax lower bound holds for every p ∈ [1, ∞].

Keywords: conformal prediction; quantile regression; covariate shift; finite-sample guarantees; conditional coverage. MSC2020 subject classifications: 62G08, 62G15, 62C20.

1

Introduction

Conformal prediction converts a fitted score into a prediction set with finite-sample marginal coverage under exchangeability [53, 44, 25]. Unless stated otherwise, training, calibration, and test pairs follow PXY := PX ⊗ PY |X . For a target miscoverage level α ∈ (0, 1) and an independent test observation (X, Y ) ∼ PXY , a conformal rule Cˆα constructed from training and calibration samples satisfies P{Y ∈ Cˆα (X)} ≥ 1 − α. This guarantee averages over the test covariate and over the data used to construct the set. Exact distribution-free conditional validity, that is, P{Y ∈ Cˆα (x) | X = x} ≥ 1 − α ∗

Corresponding author: [email protected]

1

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

for almost every x, is unavailable for nontrivial rules without further assumptions, see [52, 14]. We therefore ask how, after the training and calibration samples have been fixed, the resulting random conditional coverage profile and interval length compare with an oracle benchmark. We answer this question for split conformalized quantile regression (CQR) [31, 39]. Split CQR fits the two conditional quantile endpoints on the training fold and selects a common scalar score threshold on the independent calibration fold. For τ ∈ (0, 1), let fτ⋆ (x) denote the conditional τ -quantile of Y given X = x. The equal-tailed oracle interval is  ⋆  ⋆ Cα⋆ (x) = fα/2 (x), f1−α/2 (x) , P{Y ∈ Cα⋆ (x) | X = x} = 1 − α, under the local mass conditions imposed below. For the realized split CQR set Cˆα constructed from both folds, we control, for every p ∈ [1, ∞], ∥|Cˆα | − |Cα⋆ |∥Lp (PX ) ,

∥ CovCˆα −(1 − α)∥Lp (PX ) ,

CovCˆα (x) = P{Y ∈ Cˆα (x) | X = x}.

We prove finite sample bounds for both quantities that hold with high probability jointly over the training and calibration folds and separate endpoint estimation, score calibration, and rank correction. Their only learner-specific input is the Lp (PX ) error of the two fitted quantile endpoints. Covariate shift changes only the covariate law: training and calibration pairs follow PX ⊗ PY |X , whereas the test pair follows QX ⊗ PY |X . When w = dQX /dPX is known, weighted split conformal prediction retains finite sample target marginal coverage [47]. Under the same local mass and endpoint conditions and w ≤ wmax , our bounds additionally control the realized target Lp (QX ) conditional coverage profile and the length deviation from Cα⋆ . Conditional on the training fold, the fitted CQR score is fixed. We therefore isolate calibration in a separate minimax problem: the source and target marginals and a reference score are fixed, the conditional response kernel varies, and only the threshold rule uses the m source calibration observations. The reference score is the oracle CQR score under one baseline kernel and remains fixed across the candidate kernels. On an explicit two-carrier construction with point-mass target QX = δx0 , only the threshold value at x0 affects the target risk. Hence every covariate-dependent threshold rule is equivalent, for this experiment, to its scalar value at x0 . Let Rm,p denote the infimum over these measurable scalar outputs of the worst case, over admissible conditional response kernels, expected Lp (QX ) coverage profile error. For every p ∈ [1, ∞] and m ≥ m⋆ , s s

2 1 + χ (QX ∥PX ) 1 + χ2 (QX ∥PX ) 3 cα ≤ Rm,p ≤ , m 2 m so the exact weighted rule is minimax-rate optimal on this construction. A K-atomic Fano conq
(K) struction with K ≥ 23 and m > m⋆ gives a lower bound of order 1 + χ2 (QX ∥PX ) K/m with probability at least 1 − 2e−K/32 ; atomwise split calibration gives a matching moment upper
bound for finite p. The single-atom construction has effective calibration size m/ 1 + χ2 (QX ∥P
X ) , while each target atom in the K-atomic construction receives on average m/( 1 + χ2 (QX ∥PX ) K) calibration q
observations. The single-atom rate reproduces the 1 + χ2 (QX ∥PX ) /m calibration scaling of the CQR upper bounds. The K-atomic rate instead quantifies the additional cost of estimating K atom-specific threshold values within the separate fixed-score benchmark. Our contributions are: • finite-sample high-probability Lp (PX ) bounds for equal-tailed oracle-length deviation and the realized conditional-coverage profile of CQR, with an explicit sparse-ReLU instantiation of the endpoint condition (Proposition 1, Theorems 2 and 10, and Corollary 11); 2

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

• corresponding Lp (QX ) guarantees under known bounded covariate shift, with calibration rate q
1 + χ2 (QX ∥PX ) /m (Proposition 4, Theorem 5, and Corollary 12); • under the stated sample-size conditions, matching expected bounds for two constructed fixedscore calibration benchmarks: the single-carrier experiment (Theoremq6 and Proposition 7) and,
for K ≥ 23 and every finite p, the K-atomic experiment, with rate 1 + χ2 (QX ∥PX ) K/m and a same-order lower bound holding with probability at least 1 − 2e−K/32 for every p ∈ [1, ∞] (Theorem 8 and Proposition 9). The numerical study evaluates the fixed-score carrier rules and illustrates learned weighted CQR under a continuous shift; detailed carrier calculations and figures are reported in Appendix E.

2

Related Work

CQR efficiency and conditional profiles Split conformal prediction gives finite-sample marginal coverage [31, 53, 25], whereas exact distribution-free conditional validity is generally impossible [52, 14]. Romano et al. [39] introduced CQR, and Sesia and Candès [43] established asymptotic efficiency under consistent quantile estimation. Kivaranovic et al. [21] adapt the interval while retaining marginal validity. Rossellini et al. [40] adapt the conformal correction to estimated endpoint uncertainty; their finite-sample result is marginal, and their conditional comparisons are empirical. Yao et al. [56] bound expected CQR length error for a correctly specified linear quantile model trained by SGD. Other efficiency results compare with a shortest symmetric-residual oracle [24] or estimate more of the conditional law to target shortest or highest-density sets [8, 19]. Our bounds use the equal-tailed CQR oracle and control, with high probability after both data folds are fixed, its length deviation together with the full Lp conditional-coverage profile. This conditioning convention is important: the nonasymptotic decomposition of Min et al. [30] averages conditional coverage over the procedure’s randomness. Localized calibration and score transformations instead pursue pointwise or neighborhood guarantees [33, 9]; their target and the bias–variance tradeoff created by localization differ from the global additive CQR correction studied here. Covariate shift Tibshirani et al. [47] proved finite-sample target marginal validity for weighted conformal prediction with a known likelihood ratio; Lei and Candès [26] applied the construction to counterfactual CQR. Pournaderi and Xiang [35] control target marginal miscoverage after the source sample is fixed, whereas we control the realized target conditional-coverage profile and oracle length. In the unshifted setting, Bian and Barber [5] distinguish training-conditional guarantees from ordinary marginal validity. PAC prediction sets under shift can also be obtained by rejection sampling with known or interval-estimated weights [32]. When the likelihood ratio is unknown, asymptotic target validity can be obtained through nuisance estimation or doubly robust calibration [37, 55]. Direct covariate-dependent threshold learning and weight clipping provide further alternatives [20, 54]. Our finite-sample analysis assumes a known uniformly bounded likelihood ratio. Fixed-score calibration limits Fixed-score calibration is studied for covariate-dependent thresholds [2, 11], prescribed finite-dimensional shift classes [15], and overlapping or fractional groups [3]. Related results give conditional-calibration oracle inequalities for set-valued maps [4] and characterize continuous split calibration through transported beta laws [38]. Section 5 compares our benchmarks 3

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

with the threshold calibration results. Analogous χ2 -controlled rates for mean estimation from biased sources appear in [18]. Quantile endpoint estimation Sparse-ReLU quantile rates are developed by Madrid Padilla et al. [27], building on the approximation architecture of Schmidt-Hieber [41] and its later regression correction [42]. In the isotropic Hölder setting, inserting the resulting L2 (PX ) endpoint-error bound into our general CQR result yields the (log n)3/2 factor in the final rate. Feng et al. [13] analyze expected target L2 error for neural quantile regression under known or estimated covariate shift; our ReLU result instead supplies a high-probability source endpoint condition and then propagates it through conformal calibration.

3

Split CQR

We follow the split-CQR construction of Romano et al. [39]. Let X be an arbitrary measurable space, let Y be real-valued, and let x 7→ PY |X=x be a probability kernel. Set PXY = PX ⊗ PY |X . For any nondecreasing, right-continuous function H : R → [0, ∞) with limt→−∞ H(t) = 0, and any τ > 0, define its generalized inverse by Q(τ ; H) := inf{t ∈ R : H(t) ≥ τ },

inf ∅ := +∞.

Write R = R ∪ {−∞, +∞} with its order-Borel σ-field, and extend every probability CDF F by F (−∞) = 0 and F (+∞) = 1. Weighted empirical cumulative functions retain their realized total mass; an unattained level has generalized inverse +∞. For τ ∈ (0, 1), the conditional τ -quantile is fτ⋆ (x) = inf{t ∈ R : P(Y ≤ t | X = x) ≥ τ } .

(1)

Fix α ∈ (0, 1). The benchmark for interval length is the equal-tailed conditional-quantile interval  ⋆  ⋆ Cα⋆ (x) := fα/2 (x), f1−α/2 (x) . (2) A 1. There are constants 0 < µlow ≤ µup < ∞ and a local mass radius r0 > 0, and one measurable set X0 with PX (X0 ) = 1 such that, for every x ∈ X0 , PY |X=x ([u, v]) ≤ µup (v − u)

for all finite u ≤ v,

(3)

and, for τ ∈ {α/2, 1 − α/2} and 0 ≤ h ≤ r0 , PY |X=x ([fτ⋆ (x) − h, fτ⋆ (x)]) ≥ µlow h,

PY |X=x ([fτ⋆ (x), fτ⋆ (x) + h]) ≥ µlow h.

The upper bound in A 1 makes the conditional CDFs µup -Lipschitz and atomless; hence, for every ⋆ (x)]) = α/2 and P ⋆ x ∈ X0 , PY |X=x ((−∞, fα/2 Y |X=x ((−∞, f1−α/2 (x)]) = 1 − α/2. Thus endpoint error controls score-CDF and conditional-coverage error. The local lower bounds provide two-sided linear growth at the oracle quantiles, which is used to convert score-CDF error into threshold error. Conditions of this form appear in [46, Definition 2.1] and [27, Assumption 2]. Our condition is weaker than the continuous two-sided density bounds of [56, Assumption 3.3]: it requires lower growth only near the two oracle quantiles and allows unbounded response support and discontinuous conditional densities. ⊗n cal ∼ P ⊗m be independent. The training sample produces finite raw maps Let Dntr ∼ PXY and Dm XY (Dntr , x) 7→ fen,τ (x), jointly measurable for τ ∈ {α/2, 1 − α/2}. 4

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

A 2(p). Fix p ∈ [1, ∞]. There is ϵp : N × (0, 1) → R+ such that, for every n ∈ N, δ ∈ (0, 1) and τ ∈ {α/2, 1 − α/2},   PDntr ∥fen,τ − fτ⋆ ∥Lp (PX ) ≤ ϵp (n, δ) ≥ 1 − δ. A 2(p) is the only condition imposed on the endpoint learner. Its Lp (PX ) guarantee controls the spatial error terms and, since p ≥ 1, yields the L1 (PX ) bound needed to compare the estimated and oracle score distributions. Its high-probability form allows endpoint estimation and calibration errors to be combined in a single guarantee. Accordingly, the results below apply to any learner satisfying this integrated error bound. Define the fitted endpoints by pointwise sorting, fˆn,α/2 = fen,α/2 ∧ fen,1−α/2 ,

fˆn,1−α/2 = fen,α/2 ∨ fen,1−α/2 .

(4)

Since the oracle endpoints are ordered, Lemma 13 gives, pointwise, ⋆ ⋆ ⋆ ⋆ |fˆn,α/2 − fα/2 | + |fˆn,1−α/2 − f1−α/2 | ≤ |fen,α/2 − fα/2 | + |fen,1−α/2 − f1−α/2 |.

Thus A 2(p) controls the combined endpoint error after sorting; all scores and prediction intervals below use fˆn,α/2 and fˆn,1−α/2 . Calibration rule Following Romano et al. [39], we calibrate the fitted CQR score by a common scalar empirical quantile and use the resulting score sublevel set as the prediction interval. By A 1, the oracle interval Cα⋆ (x) has conditional coverage 1 − α for PX -almost every x. Define the oracle and fitted scores b y) := max{fˆn,α/2 (x) − y, y − fˆn,1−α/2 (x)}. S(x,

⋆ ⋆ S ⋆ (x, y) := max{fα/2 (x) − y, y − f1−α/2 (x)},

b y) is the smallest scalar t such that y ∈ [fˆn,α/2 (x) − t, fˆn,1−α/2 (x) + t]; calibration For fixed x, S(x, cal = {(X , Y )}m therefore selects one common expansion or contraction across covariates. Write Dm i i i=1 b i , Yi ). Define the empirical score CDF by and Sbi = S(X 1 b (S) (t) := Fbm m

m X

1{Sbi ≤t} .

i=1

Define the split-conformal level and calibrated threshold by βm :=

⌈(m + 1)(1 − α)⌉ , m

b b β := Q(βm ; Fb(S) Q m ). m

(5)

The index ⌈(m + 1)(1 − α)⌉ is the standard finite sample split conformal rank correction. The split CQR interval is b y) ≤ Q b β }. Cˆα (x) := {y ∈ R : S(x, (6) m b β ∈ R, this set equals [fˆn,α/2 (x) − Q b β , fˆn,1−α/2 (x) + Q b β ], with [a, b] = ∅ when a > b. If If Q m m m ˆ b Qβm = +∞, it equals R. Thus |Cα (x)| always denotes the Lebesgue length, namely the positive part of the endpoint difference. Conditional on Dntr , the calibration scores and an independent test score are exchangeable. Consequently, for PDntr -almost every training sample, P(Y ∈ Cˆα (X) | Dntr ) ≥ 1 − α, 5

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

cal and the independent test where the probability is taken over the random calibration sample Dm point (X, Y ) [39, Theorem 1]. For δ ∈ (0, 1), set r log(4/δ) sm := βm − (1 − α), ηm (δ) := , 2m (7) 1−α , r+ := r0 . r− := r0 ∧ 2µup

The exact rank slack satisfies

1−α 2−α ≤ sm < . m m

(8)

Finite-sample guarantees Proposition 1. Let α ∈ (0, 1) and p ∈ [1, ∞], and assume A 1 and A 2(p). Fix δ ∈ (0, 1) and n, m such that 2µup ϵp (n, δ/4) + ηm (δ) ≤ 2µlow r− ,

2µup ϵp (n, δ/4) + ηm (δ) + sm ≤ 2µlow r+ .

(9)

cal ), with probability at least 1 − δ. Then there is an event An,m (δ), measurable with respect to (Dntr , Dm b β is finite and On this event, Q m   µup ηm (δ) + sm ⋆ ˆ p ∥|Cα (·)| − |Cα (·)|∥L (PX ) ≤ 2 1 + . (10) ϵp (n, δ/4) + µlow µlow

The construction of An,m (δ) and the complete proof are given in Appendix B.1. Once the data are fixed, a measurable prediction rule C has conditional coverage profile
CovC (x) := P{Y ∈ C(x) | X = x} = PY |X=x C(x) . The event in Proposition 1 also controls this profile in Lp (PX ). Theorem 2. Let α ∈ (0, 1) and p ∈ [1, ∞], and assume A 1 and A 2(p). Fix δ ∈ (0, 1) and n, m satisfying (9). On the event An,m (δ) defined in Proposition 1,  
µup µup ∥ CovCˆα (·) − (1 − α)∥Lp (PX ) ≤ 2µup 1 + ϵp (n, δ/4) + ηm (δ) + sm . (11) µlow µlow The proof is given in Appendix B.2. For p = 1, nesting of scalar score sublevel sets gives a direct bound that does not require localization of the calibrated threshold. Proposition 3. Let α ∈ (0, 1) and assume A 1 and A2(1). For every δ ∈ (0, 1) and n, m ≥ 1, there is an event of probability at least 1 − δ on which ∥ CovCˆα −(1 − α)∥L1 (PX ) ≤ 4µup ϵ1 (n, δ/4) + ηm (δ) + sm .

(12)

A complete proof is given in Appendix B.2. The three bounds above answer slightly different questions. The marginal split-conformal guarantee is an average over a fresh calibration sample and a fresh test pair, conditional only on the training fold. By contrast, Theorem 2 and Proposition 3 fix the realized training and calibration data and measure how far the resulting conditional-coverage function is from the constant 1 − α. This distinction matters because positive and negative conditional errors may cancel in the marginal 6

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

average. The Lp norm retains their spatial magnitude, increasingly emphasizing regions of poor conditional coverage as p grows; the case p = ∞ controls the essential worst case. Moreover, the same event An,m (δ) controls both length and coverage, so the two criteria do not require separate favorable calibration realizations. Conditions (9) keep the calibrated threshold within the region where A 1 provides the required lower CDF growth; Proposition 3 avoids this localization for the direct L1 coverage bound. Discussion For correctly specified linear CQR fitted by SGD, Yao et al. [56, Theorem 3.2] obtain an expected absolute length deviation of order n−1/2 + (α2 n)−1 + m−1/2 + exp(−α2 m). They assume continuous conditional densities bounded above and below on a common bounded support; A 1 uses a global upper mass bound and local lower mass bounds near the two oracle quantiles. Our length bound holds with probability at least 1 − δ for every p ∈ [1, ∞] and accepts any endpoint learner satisfying A 2(p); Theorem 10 verifies A2(2) for sparse-ReLU pinball ERM. Theorem 2 also controls the realized conditional coverage profile. Le Bars and Humbert [24] bound excess volume relative to an oracle for symmetric intervals with a common radius; our length loss measures deviations in both directions from the equal-tailed CQR oracle. Min et al. [30] average conditional coverage over the procedure’s randomness, while our profile is evaluated after the training and calibration samples are fixed.

4

Known Covariate Shift

In Section 3, training, calibration, and test pairs share the law PX ⊗ PY |X . We now study how the preceding guarantees change under covariate shift, where training and calibration retain this source law while the test pair follows QX ⊗ PY |X . The conditional response law, and hence the conditional quantiles and the oracle interval Cα⋆ , remain unchanged. We analyze the weighted conformal CQR rule under this shift. For this rule, we retain finite-sample target marginal validity and derive high-probability bounds, evaluated after the training and calibration samples have been fixed, for ∥|Cbαw (·)| − |Cα⋆ (·)|∥Lp (QX ) ,

∥ CovCbw (·) − (1 − α)∥Lp (QX ) . α

(13)

L 1. QX ≪ PX , and the likelihood ratio w = dQX /dPX and a deterministic envelope wmax < ∞ satisfying 0 ≤ w ≤ wmax are known. The absolute continuity condition and knowledge of w are inherited from the weighted conformal construction above. Since EPX [w] = 1, the chi-square divergence satisfies Z χ2 (QX ∥PX ) := (w − 1)2 dPX = EPX [w2 ] − 1. Together with w2 ≤ wmax w, this identity gives
1 + χ2 (QX ∥PX ) = EPX [w2 ] ≤ wmax .

(14)

For every measurable g and p ∈ [1, ∞], 1/p ∥g∥Lp (QX ) ≤ wmax ∥g∥Lp (PX ) ,

7

1/∞ := 1. wmax

(15)

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

b j , Yj ) for the fitted calibration scores from Section 3, and Weighted calibration Write Sbj = S(X define the raw weighted empirical function 1 Fbmw (t) := m

m X

w(Xj )1{Sbj ≤t} ,

j=1

1 Fbmw (+∞) = m

m X

w(Xj ).

(16)

j=1

Conditional on Dntr , the fitted score is fixed and the calibration pairs follow the source law. The Radon–Nikodym identity therefore changes the covariate marginal from PX to QX and gives, for every t ∈ R, h i Q tr b E[Fbmw (t) | Dntr ] = EPXY w(X)1{S(X,Y D b n = F b (t) := (QX ⊗ PY |X ){S ≤ t}. )≤t} S

Its total mass Fbmw (+∞) is random. Since Z QX {w = 0} =

w dPX = 0, {w=0}

{w > 0} is QX -full. Following the weighted split conformal construction of Tibshirani et al. [47], for x ∈ {w > 0} define the probability measure m X

w(Xj ) w(x) δSbj + δ+∞ . w w b b mFm (+∞) + w(x) j=1 mFm (+∞) + w(x)

(17)

b w (x) be its (1 − α)-quantile. The corresponding weighted CQR interval is Let Q m w b y) ≤ Q bm Cbαw (x) := {y ∈ R : S(x, (x)}.

(18)

Equivalently, for x ∈ {w > 0}, Lemma 20 gives
w bm Q (x) = Q((1 − α) Fbmw (+∞) + w(x)/m ; Fbmw ).

(19)

By the weighted split conformal validity result of Tibshirani et al. [47, Corollary 1], for almost every training realization,   P Y⋆ ∈ Cbαw (X⋆ ) Dntr ≥ 1 − α, (20) where the probability averages over the source calibration sample and the independent pair (X⋆ , Y⋆ ) ∼ QX ⊗ PY |X ; only the training fold is conditioned upon. The results below fix both folds and control the realized Lp (QX ) profile with probability at least 1 − δ. Target guarantees For δ ∈ (0, 1), set s
1 + χ2 (QX ∥PX ) log(4/δ) 4wmax log(4/δ) w ηm (δ) := 9 + . m 3m

(21)

Proposition 4. Let α ∈ (0, 1), p ∈ [1, ∞], and assume A 1 and L 1 and A 2(p). Fix δ ∈ (0, 1) and n, m ≥ 1 such that 1/p w 2µup wmax ϵp (n, δ/4) + (2 − α)ηm (δ) < 2µlow r− , (1 − α)wmax 1/p w 2µup wmax ϵp (n, δ/4) + (2 − α)ηm (δ) + ≤ 2µlow r+ . m

8

(22)

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

tr cal Then there is an event Aw n,m (δ), measurable with respect to (Dn , Dm ), with probability at least 1 − δ. b w (x) is finite for QX -almost every x and On this event, Q m   µup 1/p w ⋆ b wmax ϵp (n, δ/4) ∥|Cα (·)| − |Cα (·)|∥Lp (QX ) ≤ 2 1 + µlow (23) w (δ) + (1 − α)∥w∥ p (2 − α)ηm L (QX ) /m + . µlow

The event and signed threshold bounds are established in Lemma 21; the proof is given in Appendix C.3. Theorem 5. Let α ∈ (0, 1) and p ∈ [1, ∞], and assume A 1 and L 1 and A 2(p). Fix δ ∈ (0, 1) and n, m satisfying (22). On the event Aw n,m (δ) of Proposition 4,   µup 1/p wmax ϵp (n, δ/4) ∥ CovCbw (·) − (1 − α)∥Lp (QX ) ≤ 2µup 1 + α µlow   (24) µup 1−α w + (2 − α)ηm (δ) + ∥w∥Lp (QX ) . µlow m A complete proof is given in Appendix C.4. Calibration deviation By Lemmas 18 and 19, conditionally on Dntr ,   δ Q w w tr b P sup |Fm (t) − F b (t)| ≤ ηm (δ) Dn ≥ 1 − . S 2 t∈R

(25)

w (δ). The deviation bound applies to the unbiased raw The same event gives |Fbmw (+∞) − 1| ≤ ηm process Fbmw ; the conformal
measure in (17) is normalized. The 1 + χ2 (QX ∥PX ) term follows from the L2 maximal bound for weighted score prefixes; the wmax term comes from the envelope in Bousquet’s inequality. The leading constant 9 combines symmetrization, the martingale maximal inequality, and Bousquet’s fluctuation bound. Bounding the score-CDF and total-mass fluctuations separately gives (2 − α), although the same supremum controls both. These constants are not optimized. For w ≡ 1, this weighted bound is weaker than the unshifted bound based on ηm (δ) in (7).

Discussion For calibration, and test-atom terms in (23) and (24) have orders qfixed δ, the endpoint,
1/p wmax ϵp (n, δ/4), 1 + χ2 (QX ∥PX ) /m + wmax /m, and ∥w∥Lp (QX ) /m, respectively. Pournaderi and Xiang [35, Theorem 1 and Corollary 1] control the one-sided target marginal miscoverage of the same rule conditional on the complete source sample, whereas our bounds control the realized Lp (QX ) profile and equal-tailed oracle length on an event measurable with respect p p to both source folds. Under w ≤ wmax , their bounded-ratio excess has order wmax /m + wmax log(4/δ)/m with exponential confidence, while their second-moment alternative has polynomial dependence on 1/δ. Their score learner is unrestricted; our profile and length bounds additionally require the endpoint event and mass regularity. Joshi et al. [20] learn a covariate-dependent threshold from labeled source observations and unlabeled source and target covariates without directly estimating w. Their result gives target marginal coverage up to estimation and likelihood-ratio projection errors, whereas our known-ratio bounds control the realized Lp (QX ) profile and equal-tailed oracle length. 1/p The three shift quantities in the bounds have distinct roles. The factor wmax transfers an integrated endpoint error from the source covariate law to the target law and disappears when p = ∞. 9

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

The second moment 1 + χ2 (QX ∥PX ) = EPX [w2 ] determines the leading stochastic calibration fluctuation, just as a variance determines the scale of an importance-weighted average. Finally, ∥w∥Lp (QX ) /m comes from the additional mass assigned to +∞ for the test point in (17).
The leading calibration term is not determined by wmax alone. When w ≡ 1, 1 + χ2 (QX ∥PX ) = 1 and the effective calibration size is m. The fixed score benchmarks in Section 5 show that the dependence q
1 + χ2 (QX ∥PX ) /m can arise from calibration alone.

5

Minimax Limits for Fixed-Score Calibration under Covariate Shift

Split CQR uses independent samples for score construction and calibration. Conditional on the training sample, the fitted score Sb is fixed, while the calibration sample determines a threshold function through b y) ≤ Q b w (x)}. Cbαw (x) = {y ∈ R : S(x, m This conditional representation motivates studying calibration with a q fixed score. For fixed failure
probability, the leading calibration term in Theorem 5 has order 1 + χ2 (QX ∥PX ) /m; the benchmarks below ask whether the same dependence can arise from calibration alone. Each construction fixes source and target covariate marginals, a baseline conditional kernel PY0 |X , and its equal-tailed oracle CQR score S ⋆ . The supremum varies PY |X over all conditional kernels satisfying A1 on a measurable set of full PX -measure, while the marginals and S ⋆ remain fixed. Each infimum ranges over calibration rules that are measurable functions of the m source observations K and take values in R for scalar thresholds or in R for threshold vectors; the conformal value +∞ is admissible. Thus only the calibration rule depends on the source observations. Both constructions use finite measurable subsets of X as carriers. p Without covariate shift, Areces et al. [2] obtain an expected minimax lower bound of order d/m for covariate-dependent fixed-score thresholds. Their loss is the supremum of a normalized weighted coverage discrepancy over a class of {−1, 1}-valued functions of the covariates with VC dimension d. Their upper theorem uses a finite-dimensional linear witness space with a uniformly bounded orthonormal basis, so it is not a matching upper bound for every binary VC class. Duchi [11] derives high-probability sample-conditional guarantees for threshold functions estimated by quantile regression. We study two calibration problems with a fixed score. The first has one target atom, so only one threshold value affects the target risk. The second has K target atoms and uses a separate
threshold at each atom. In our construction, each target atom receives m/( 1 + χ2 (QX ∥PX ) K) q
source calibration observations on average, which yields the rate 1 + χ2 (QX ∥PX ) K/m. For p = 1 and K = d, its dimension dependence agrees with the atomic lower-bound geometry of Areces et al. cal to a measurable threshold function Formally, a calibration rule maps each calibration sample Dm cal qbDm bDm cal : X → R, with (Dm , x) 7→ q cal (x) jointly measurable. For a realized calibration sample, define  Cqb⋆ cal (x) := y ∈ R : S ⋆ (x, y) ≤ qbDm cal (x) . Dm

For a candidate conditional kernel PY |X , its realized conditional coverage profile is     CovP{S ⋆ ≤bq cal } (x) := PY |X=x Cqb⋆ cal (x) = PY |X=x S ⋆ (x, Y ) ≤ qbDm cal (x) . Dm

Dm

(26)

The calibration sample is held fixed in this conditional probability. The profile remains random cal through qbDm b, Cqb⋆ , and CovP{S ⋆ ≤bq} . cal . Henceforth, we suppress the subscript Dm and write q 10

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

w (x) is covariate dependent through the test-point weight bm The exact weighted CQR threshold Q w(x) in (17)–(19). The calibration rules considered here may likewise depend on x. In the singlecarrier experiment, QX = δx0 , so an arbitrary threshold function enters the target risk only through the scalar qbDm cal (x0 ); conversely, any scalar rule admits a measurable constant extension. In the K-atomic experiment, QX is uniform on x1 , . . . , xK , so the rule is identified with the vector of its values at these atoms. Values away from the target support do not enter the Lp (QX ) loss.

Theorem 6. Fix α ∈ (0, 1) and κ > 0, and assume that X contains two distinct points whose singleton sets are measurable. Then there exist source and target marginals PX , QX , a reference conditional kernel PY0 |X , and a reference score S ⋆ , all independent of m, with the following properties. The marginals satisfy L 1 and χ2 (QX ∥PX ) = κ. The kernel PY0 |X satisfies A 1 on a set of full PX measure. The score S ⋆ is the equal-tailed oracle CQR score under PY0 |X and is held fixed throughout the minimax problem below. For m ≥ 1 and p ∈ [1, ∞], define h i Rm,p := inf sup E(PX ⊗PY |X )⊗m ∥ CovP{S ⋆ ≤bq} (·) − (1 − α)∥Lp (QX ) . (27) qb PY |X

Set

 4(log 2)(1 + κ) α(1 − α) . m⋆ := min{α, 1 − α}2 

Then for every m ≥ m⋆ and p ∈ [1, ∞], r 1+κ Rm,p ≥ cα , m

cα :=

(28)

1p (log 2)α(1 − α). 8

A complete proof is given in Appendix D.1. Lower-bound construction Choose distinct x0 , xD ∈ X and set QX = δx0 ,

PX =

1 κ δx + δx . 1+κ 0 1+κ D

Then 1 + χ2 (QX ∥PX ) = 1 + κ, the likelihood ratio satisfies w(x0 ) = 1 + χ2 (QX ∥PX ) and w(xD ) = 0, and Z
∥w∥L∞ (PX ) = w(x)2 dPX (x) = 1 + χ2 (QX ∥PX ) . X

Thus a source calibration draw has X = x0 with probability 1/ 1 + χ2 (QX ∥PX ) . Since QX = δx0 , for every candidate kernel PY |X , every realized scalar threshold qb, and every p ∈ [1, ∞], ∥ CovP{S ⋆ ≤bq} (·) − (1 − α)∥Lp (QX ) = CovP{S ⋆ ≤bq} (x0 ) − (1 − α) .
These identities belong to the construction; L 1 itself only gives 1 + χ2 (QX ∥PX ) ≤ wmax . Let PY0 |X be uniform on [−1, 1] at every covariate value, and fix the score S ⋆ (x, y) = |y| − (1 − α). This is the equal-tailed oracle CQR score for PY0 |X ; the same score is retained under the alternative PY1 |X . Define the two score bands B0 = [−(1 − α), 0],

B1 = (0, α],

which have respective masses 1 − α and α under PY0 |X . Let PY1 |X agree with PY0 |X away from x0 and, at x0 , transfer conditional mass ξ from B0 to B1 . 11

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Clipping a realized scalar threshold qb to [0, α] cannot increase its absolute coverage error under either hypothesis. Write the clipped threshold as qe = αa, where a ∈ [0, 1] is the fraction of B1 admitted by the threshold ray. For j ∈ {0, 1}, define j

Dj (a) := CovP{S ⋆ ≤αa} (x0 ) − (1 − α). Then D1 (a) = (α + ξ)a − ξ,

D0 (a) = αa,

whose respective zeros are 0 and ξ/(α + ξ). Thus no scalar threshold attains exact target coverage under both hypotheses. Since the two source experiments differ only when X = x0 , their perobservation divergence is   ξ2
χ2 PX ⊗ PY1 |X PX ⊗ PY0 |X = . 1 + χ2 (QX ∥PX ) α(1 − α)
For ξ 2 = (log 2) 1 + χ2 (QX ∥PX ) α(1 − α)/m, the total variation distance between the two m-sample laws is at most 1/2, and Le Cam’s lemma gives the lower bound ξ/8 in Theorem 6. The density construction and Le Cam reduction are given in Appendix D.1. For an upper bound on the same construction, apply the weighted conformal construction (17) to the calibration scores S ⋆ (Xi , Yi ) under the same source and target marginals and fixed score, b w (x) denote its (1 − α) quantile. Since QX = δx , only Q b w (x0 ) affects the Lp (QX ) and let Q m m 0 profile loss. Proposition 7 bounds this loss uniformly over the candidate conditional kernels, with cal ∼ (P ⊗ P ⊗m . Dm X Y |X ) Proposition 7. Under the assumptions of Theorem 6, consider the source and target marginals and fixed reference score used in its two-point construction,
−1 and let x0 denote the unique target atom. 2 Thus QX = δx0 and PX ({x0 }) = 1 + χ (QX ∥PX ) . Then, for every m ≥ 1 and p ∈ [1, ∞], h i P p sup EDm (·) − (1 − α)∥ cal ∥ Cov L (QX ) b w (x )} {S ⋆ ≤Q m

PY |X

3 ≤ 2 3 ≤ 2

s

s

0

1 + χ2 (QX ∥PX ) m+1





1− 1−

−1 1 + χ2 (QX ∥PX )

m+1 

(29)

1 + χ2 (QX ∥PX ) . m+1

w (x ) is admissible in the definition of R bm The scalar rule qb = Q 0 m,p . Combining Theorem 6 and Proposition 7 therefore gives, for every m ≥ m⋆ and p ∈ [1, ∞], s s s


2 2 1 + χ (QX ∥PX ) 1 + χ (QX ∥PX ) 1 + χ2 (QX ∥PX ) 3 3 cα ≤ Rm,p ≤ ≤ . (30) m 2 m+1 2 m

Thus, on this fixed-score construction, the weighted conformal rule of Tibshirani et al. [47] attains q
2 the expected minimax rate 1 + χ (QX ∥PX ) /m up to α-dependent constants. The effective
calibration size is m/ 1 + χ2 (QX ∥PX ) ; the same shift factor appears in the leading calibration term of Theorem 5. For a target uniform on K atoms, the calibration rule must estimate K threshold values from the same source sample. The theorem below gives a minimax lower bound whose probability tends to one exponentially fast in K. For finite p, Proposition 9 gives the corresponding moment upper bound. 12

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Theorem 8. Fix α ∈ (0, 1), an integer K ≥ 23, and κ > 0, and assume that X contains at least 2K distinct points whose singleton sets are measurable. Then there exist source and target marginals PX , QX , distinct points x1 , . . . , xK , a reference conditional kernel PY0 |X , and a reference score S ⋆ , all independent of m, with the following properties. The marginals satisfy L 1, K

χ2 (QX ∥PX ) = κ,

QX =

1 X δxk . K k=1

PY0 |X satisfies A 1 on a set of full PX -measure. The score S ⋆ is the equal-tailed oracle CQR score under PY0 |X and is held fixed throughout the minimax problem below. For a threshold vector qb1:K , define its canonical measurable extension by ( qbk , x = xk for some k ∈ {1, . . . , K}, qb(x) = 0, x ∈ / {x1 , . . . , xK }. The value chosen off the target support is immaterial to the loss below. Set (K)

m⋆ (K)

Then for every integer m > m⋆

:=

(1 + κ) α(1 − α)K . 4 min{α, 1 − α}2

(31)

and every p ∈ [1, ∞],

inf sup P(PX ⊗PY |X )⊗m ∥ CovP{S ⋆ ≤bq} (·) − (1 − α)∥Lp (QX )

qb1:K PY |X

1 ≥ 64

r

(1 + κ) α(1 − α)K m

! ≥ 1 − 2e−K/32 .

A complete proof is given in Appendix D.2. Geometry of the hypercube The construction pairs each target atom xk with an auxiliary atom xD,k carrying source mass but no target mass. Select distinct points x1 , . . . , xK and xD,1 , . . . , xD,K , and support both marginals on these 2K points. For k = 1, . . . , K, set QX ({xk }) = PX ({xk }) =

1 , K

QX ({xD,k }) = 0,

1 , (1 + κ)K

PX ({xD,k }) =

κ . (1 + κ)K

Then 1 + χ2 (QX ∥PX ) = 1 + κ, w(xk ) = 1 + χ2 (QX ∥PX ) and w(xD,k ) = 0, and
2 K X
1 + χ2 (QX ∥PX )
= 1 + χ2 (QX ∥PX ) , ∥w∥L∞ (PX ) = w(x) dPX (x) = 1 + χ2 (QX ∥PX ) K X k=1 Z

2

and a source draw reaches a given target atom with probability 1/( 1 + χ2 (QX ∥PX ) K). The xD,k absorb the remaining source mass without carrying information about the alternative. Unlike the scalar construction, the target mass is now spread over K atoms. For a threshold vector qb1:K , write ek (b qk ) := CovP{S ⋆ ≤bq} (xk ) − (1 − α). 13

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

Then the target marginal error and the realized profile loss are, respectively, K

1 X ek (b qk ) , K  k=1 !1/p K  X  1   |ek (b qk )|p , p < ∞, K ∥ CovP{S ⋆ ≤bq} −(1 − α)∥Lp (QX ) = k=1    qk )|, p = ∞.  max |ek (b

EQX [CovP{S ⋆ ≤bq} (X)] − (1 − α) =

1≤k≤K

The marginal error may vanish by cancellation, whereas the profile loss retains the deviations at individual atoms. The Fano argument therefore encodes the alternatives by K-dimensional binary vectors and compares the corresponding threshold vectors coordinate by coordinate. Use the same uniform reference conditional at every carrier point, reuse the score bands B0 , B1 from the scalar construction, and write D for the coarsened label of the corresponding dump point xD,k . A vertex τ ∈ {0, 1}K transfers mass ξ from B0 to B1 at target atom xk when τk = 1. After a source observation is coarsened to a label in {1, . . . , K} × {B0 , B1 , D}, let the resulting source law τ be P . Its masses are τ

P (k, B0 ) =

1 − α − ξτk
, 1 + χ2 (QX ∥PX ) K

α + ξτk τ
, P (k, B1 ) = 1 + χ2 (QX ∥PX ) K
1 + χ2 (QX ∥PX ) − 1 τ
. P (k, D) = 1 + χ2 (QX ∥PX ) K

The threshold fraction yielding conditional coverage 1 − α at xk is a⋆k (τ ) =

ξ τk . α+ξ

For τk = 0 and τk = 1, this fraction equals 0 and ξ/(α + ξ), respectively. The proof selects exponentially many binary vectors such that every pair differs in at least K/4 coordinates, and sets s
1 + χ2 (QX ∥PX ) α(1 − α)K 1 ξ= . 4 m For this choice of ξ, the χ2 divergence between each m-sample alternative and the m-sample reference law is at most eK/16 − 1. Target L1 coverage loss below ξ/16 identifies the corresponding binary vector. Fano’s inequality bounds the average probability of correct identification over the selected vectors by 2e−K/32 ; hence the worst-case probability of loss at least ξ/16 is at least 1 − 2e−K/32 . The density and χ2 calculations and the identification argument are given in Appendix D.2. Split conformal calibration at each target atom For the upper bound, apply the standard finite-sample split conformal rank correction separately to the calibration observations at each target P 1 atom xk . For k = 1, . . . , K, let Nk = m i=1 {Xi =xk } be the number of source calibration observations at xk , and set jk = ⌈(Nk + 1)(1 − α)⌉. Define ( ) m X qbk := inf t ∈ R : 1{Xi =xk } 1{S ⋆ (Xi ,Yi )≤t} ≥ jk , k = 1, . . . , K. (32) i=1

14

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Under covariate shift, the source and target laws share PY |X=xk , so S ⋆ (xk , Y ) has the same conditional distribution under both laws. If jk = Nk + 1, then qbk =
+∞ by the generalized inverse convention. 2 On this construction, Nk ∼ Bin(m, 1/(
1 + χ (QX ∥PX ) K)), so the effective calibration size at each 2 target atom is m/( 1 + χ (QX ∥PX ) K). Proposition 9. Under the assumptions of Theorem 8, consider the source and target marginals, target atoms x1 , . . . , xK , and fixed reference score used in its K-atomic construction. In particular, K

QX =

1 X δxk , K

PX ({xk }) =

k=1

1
, 1 + χ2 (QX ∥PX ) K

k = 1, . . . , K.

For every p ∈ [1, ∞), there is a constant Cp < ∞, depending only on p, such that the rule (32), with qb defined by the canonical extension in Theorem 8, satisfies, for every m ≥ 1, s
n h p io1/p 2 (Q ∥P ) K 1 + χ X X . (33) sup EDm ∥ CovP{S ⋆ ≤bq} (·) − (1 − α)∥Lp (QX ) ≤ Cp cal m PY |X A complete proof is given in Appendix D.3. By Markov’s inequality, for every δ ∈ (0, 1), 

s

P −1/p sup PDm cal ∥ Cov{S ⋆ ≤b q } (·) − (1 − α)∥Lp (QX ) ≥ Cp δ

PY |X

1 + χ2 (QX ∥PX ) K m

  ≤ δ.

(34)

Integrating the lower tail bound in Theorem 8 and applying Jensen’s inequality to Proposition 9 gives, for every K ≥ 23, p ∈ [1, ∞), and m satisfying the condition of Theorem 8, s
  pα(1 − α) 1 + χ2 (QX ∥PX ) K −K/32 1 − 2e 64 m s (35)
h i 2 (Q ∥P ) K 1 + χ X X P ≤ inf sup EDm . cal ∥ Cov{S ⋆ ≤b q } (·) − (1 − α)∥Lp (QX ) ≤ Cp m qb1:K PY |X Thus the expected minimax rate on this construction is

q

1 + χ2 (QX ∥PX ) K/m for every fixed

p < ∞. For every fixed δ < 1 − 2e−K/32 , (34) shows that, uniformly over the candidate kernels, the atomwise rule has loss at most s
1 + χ2 (QX ∥PX ) K −1/p Cp δ m with probability at least 1 − δ. Conversely, for every calibration rule, Theorem 8 gives the worst-case lower bound s p
1 + χ2 (QX ∥PX ) K α(1 − α) 64 m with probability at least 1 − 2e−K/32 > δ. The moment bound does not cover p = ∞. Its high probability constant grows as δ −1/p and is therefore not independent of K when δ decreases exponentially in K. 15

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

q

1 + χ2 (QX ∥PX ) /m and 1 + χ2 (QX ∥PX ) K/m are the inverse

square roots of the mean source counts m/ 1 + χ2 (QX ∥PX ) and m/( 1 + χ2 (QX ∥PX ) K) at the target atoms. In both lower bounds, S ⋆ is fixed and the infimum ranges over every measurable scalar or vector threshold rule. The weighted conformal rule attains the one-atom rate for p ∈ [1, ∞], while the atomwise split conformal rule attains the K-atom rate for every fixed p < ∞. For expected loss, the rates

6

q

Numerical Experiments

Experiments E1–E2 evaluate the fixed-score carrier rules from Section 5; Experiment E3 illustrates the learned CQR bounds of Sections 3 and 4 under a continuous shift. The complete carrier identities, parameters, and plots are given in Appendix E.

6.1

Fixed-Score Carrier Experiments

E1 uses the two-point construction of Theorem 6 at α = 0.1 and κ ∈ {1, 3, 9, 27}. The exact weightedrule risk is a Binomial–Beta mixture, so no response simulation is needed. Against the effective size
m/ 1 + χ2 (QX ∥PX ) , the four curves nearly collapse. At small effective sizes, the conformal rank can exceed the number of carrier observations; the threshold is then +∞ and the absolute coverage error is α, producing p the visible plateau. At large effective sizes, the scaled risk converges to the Gaussian constant 2α(1 − α)/π. The comparison with Theorem 6 and Proposition 7 also shows the gap created by unoptimized nonasymptotic constants; see Figure 2. E2 applies split calibration separately at K ∈ {23, 64, 256} target atoms for κ ∈ {1, 3, 9}. Exact beta moments give {ELpp }1/p estimates from 104 replications give ELp . The q, while Monte Carlo
curves illustrate the scaling 1 + χ2 (QX ∥PX ) K/m for finite p. Their separation for p > 1 is the finite-K Jensen gap, rather √ than a discrepancy between theory and simulation. The p = ∞ panel illustrates the carrier rule’s log K behavior after the effective-size limit; see Figure 3.

6.2

Learned CQR under Covariate Shift

At α = 0.1, E3 takes PX = Unif[0, 1] and w(x) =

aκ eaκ x , eaκ − 1

a  aκ κ coth = 1 + κ, 2 2

κ ∈ {1, 3},

so 1 + χ2 (QX ∥PX ) = 1 + κ. The response model is    2 Y | X = x ∼ N sin(2πx), 21 + 14 cos(2πx) . It satisfies A 1. Raw endpoints are fitted either by a one-hidden-layer tanh network of width 20 or by misspecified affine quantile regression, and then sorted as in (4). Thus E3 illustrates the generic learned-score results. We compare the exact weighted rule Cbαw , unweighted split CQR, and the population-normalized diagnostic b y) ≤ Q(βm ; Fbmw )}. {y : S(x, The last rule replaces the random normalization and test-point correction in (19) by βm and therefore has no exact target validity guarantee. Because the conditional law is Gaussian, all coverage profiles and target integrals are evaluated deterministically; only the source training and calibration folds are simulated. 16

Isaev et al.

Conformalized Quantile Regression under Covariate Shift (a) Validity, linear QR n = 2048 1.000

100

100

0.950 0.925 0.900 0.875

target L 2 (QX ) error

0.975

target L 2 (QX ) error

target marginal coverage

(c) Training-size effect m = 4096, ∙ = 3

(b) Exact weighted, pinball MLP n = 8192

10−1

0.850

10−2

10−2

0.825 27

28 calibration size m

exact weighted population-normalized unweighted

29

∙=1 ∙=3 nominal 1 ¡ ®

10−1

27

28 calibration size m

coverage L 2 length L 2

29

28

210

training size n

∙=1 ∙=3

pinball MLP linear QR

coverage L 2 length L 2

m ¡1=2 reference

Figure 1: Learned CQR experiment (E3) under exponential covariate shift at α = 0.1, from R = 200 replications. Panel (a) reports means with pointwise 95% intervals; panels (b)–(c) report medians with pointwise empirical [0.025, 0.975]-quantile bands. Panel (a) uses affine endpoints with n = 2048. The exact weighted rule is consistent with target marginal validity, while the unweighted rule undercovers under the positive tilt. Panel (b), using the network at n = 8192, shows length and coverage-profile errors decaying at the calibration scale m−1/2 , with a larger prefactor for κ = 3. Panel (c) fixes (m, κ) = (4096, 3): network errors decrease with the training size, whereas the affine fit reaches its misspecification floor, illustrating the endpoint term in Proposition 4 and Theorem 5.

7

A Sparse-ReLU Instantiation of the Endpoint Condition

Neural quantile regression rates are established by Madrid Padilla et al. [27] and Shen et al. [45]. Here we verify the p = 2 instance of A 2(p) for one sparse-ReLU pinball estimator and substitute the resulting endpoint radius into the generic CQR bounds. The verification uses the bounded support and two-sided conditional-density bounds required by the sparse-ReLU approximation and the pinball-risk argument. A 3. X = [0, 1]d and Y = [−M, M ] for some M > 0. A 4. For every x ∈ X , the conditional law PY |X=x has support Y and a Lebesgue density satisfying 0 < µlow ≤ pY |X (y | x) ≤ µup < ∞ for every y ∈ Y. For every α ∈ (0, 1), A 3 and 4 imply A 1 with r0 = α/(2µup ); see Appendix F.6. B 1. For each τ ∈ {α/2, 1 − α/2}, the conditional quantile function fτ⋆ belongs to the isotropic Hölder ball Hβ (X , Lβ ) for some β > 0. Estimator and endpoint rate Let FnSH denote the sparse ReLU class in (98), with outputs clipped to [−M, M ]. The pinball loss, Hölder-ball convention, architecture, and training threshold nSH are specified in Appendix F.1. 17

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

Theorem 10. Fix α ∈ (0, 1) and τ ∈ {α/2, 1 − α/2}, and assume A 3 and 4 and B 1. Let fen,τ be a measurable empirical pinball risk minimizer over FnSH . There are constants Crate , Cconf > 0, depending only on (α, µlow , µup , β, d, M, Lβ ), such that, for every δ ∈ (0, 1) and integer n ≥ nSH , with probability at least 1 − δ over Dntr , r log(1/δ) ⋆ −β/(2β+d) 3/2 e ∥fn,τ − fτ ∥L2 (PX ) ≤ Crate n (log n) + Cconf . n The proof combines the sparse ReLU approximation of Schmidt-Hieber [41, Theorem 5], metric entropy, a Bernstein oracle inequality, and the quadratic risk comparison. A complete proof is given in Appendix F.5. Together with the deterministic 2M bound, Theorem 10 verifies A 2(p) at p = 2; the radius ϵ2 is given in (166). Corollary 11. Fix α ∈ (0, 1). Under A 3 and 4 and B 1, construct the endpoints by (4). For every δ ∈ (0, 1), fix n ≥ nSH and m ≥ 1 satisfying (9) with p = 2 and ϵ2 from (166). Then, with probability at least 1 − δ, q − β n o n 2β+d (log n)3/2 + log(4/δ) n q (36) max ∥|Cˆα (·)| − |Cα⋆ (·)|∥L2 (PX ) , ∥ CovCˆα (·) − (1 − α)∥L2 (PX ) ≲ 1 + , + log(4/δ) m m where ≲ hides only (α, µlow , µup , β, d, M, Lβ )-dependent constants. The proof combines Proposition 1 and Theorem 2 with Theorem 10; see Appendix F.7. Corollary 12. Fix α ∈ (0, 1) and assume A 3 and 4, L 1, and B 1, and use the rearranged sparseReLU endpoints of (4). For every δ ∈ (0, 1), fix n ≥ nSH and m ≥ 1 satisfying (22) with p = 2 and ϵ2 from (166). Then, with probability at least 1 − δ, ( ) ( ) r ∥|Cbαw (·)| − |Cα⋆ (·)|∥L2 (QX ) , log(4/δ) 1/2 −β/(2β+d) 3/2 max ≲ wmax n (log n) + n ∥ CovCbw (·) − (1 − α)∥L2 (QX ) (37) α q
1 − α w wmax 1 + χ2 (QX ∥PX ) . + (2 − α)ηm (δ) + m The multiplicative constant depends only Lβ ), not on (n, m, δ, w, wmax ). The q on (α, µlow , µup , β, d, M,
2 last term follows from ∥w∥L2 (QX ) ≤ wmax 1 + χ (QX ∥PX ) and is the correction due to the test atom at +∞. The proof is given in Appendix F.8.

8

Conclusion

We obtained finite-sample high-probability CQR bounds that separate quantile endpoint estimation from score calibration in oracle-length and realized conditional-coverage-profile error. Under known 1/p bounded covariate shift, endpoint transfer contributes wmax , while the leading calibration term is
governed by 1 + χ2 (QX ∥PX ) = EPX [w2 ]. We complemented these guarantees with fixed-score calibration benchmarks qon constructed source–
1 + χ2 (QX ∥PX ) /m target marginals. The single-carrier benchmark has expected minimax rate 18

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

(K)

for m ≥ m⋆ . For the constructed K-atomic benchmark with K ≥ 23 and m > m⋆ , expected upper q
2 and lower bounds match at rate 1 + χ (QX ∥PX ) K/m for every finite p. For every fixed finite q
p and δ < 1 − 2e−K/32 , the atomwise rule has loss at most Cp δ −1/p 1 + χ2 (QX ∥PX ) K/m with probability at least 1 − δ, whereas, for every calibration rule, the worst-case probability of loss at q
least α(1 − α) 1 + χ2 (QX ∥PX ) K/m/64 is at least 1 − 2e−K/32 . The numerical experiments illustrate both effective-calibration-size scalings and the transition from calibration error to endpoint error for a learned CQR score. All shifted results assume a known likelihood ratio. The fixed-score benchmarks quantify calibration on the constructed problems, while the CQR bounds propagate learner-specific endpoint error. We leave a joint minimax analysis of score learning and calibration open.

Acknowledgments The work of Eric Moulines and Anton Conrad was supported by the European Union (ERC-2022SYGOCEAN-101071601). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. The work of Rustam Isaev, Sergey Samsonov, and Denis Belomestny was supported by research project HSE-BR-2025-019 implemented as part of the Basic Research Program at HSE University. This research was supported in part through computational resources of HPC facilities at HSE University [23]. The authors used OpenAI Codex to assist with language editing, consistency checks, literature searches, LATEX formatting, and debugging and editing the code for the numerical experiments. All AI-assisted suggestions were reviewed and verified by the authors. The authors assume responsibility for all content.

19

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

A

Preliminaries on Quantiles and Score Distributions

A.1

Notation and conventions

The appendix uses the notation of Sections 3 and 4. The following decorations distinguish conditional, marginal, empirical, source, and target score CDFs. Distribution functions on the score line We write F for an exact population CDF and Fb for a random empirical CDF based on a finite sample. A superscript ( · | X) denotes a conditional law given X; superscripts P, Q, and ν denote source, target, and generic marginalization over X, while w marks likelihood-ratio weighting. Subscripts S ⋆ and Sb identify the oracle and fitted scores, b (S) while the subscript m in Fbm and Fbmw is the calibration sample size. Thus, F (t) is a marginal CDF and F (t | x) is a conditional CDF evaluated at X = x. We write R = R ∪ {−∞, +∞} with its order-Borel σ-field. Whenever a probability CDF is evaluated at an extended-real quantile, it is extended by F (−∞) = 0 and F (+∞) = 1. Weighted empirical cumulative functions retain their realized total mass; if the requested level is unattained, their generalized inverse equals +∞. For a fixed training realization, the conditional fitted-score CDF is
b b F (S|X) (t | x) := P S(X, Y)≤t|X =x , whereas the marginal CDF of a score S under ν is Z ν FS (t) = F (S|X) (t | x) dν(x). X

w (δ) from Calibration radii The no-shift proof uses ηm (δ) from (7); the known-shift proof uses ηm (21).

A.2

Primitive-mass calibration lemmas

The generic no-shift and known-shift proofs use the next five lemmas; they require neither bounded support nor bounded fitted endpoints. Lemma 13. Fix α ∈ (0, 1). Let gα/2 , g1−α/2 , u, v : X → R be finite measurable functions with u ≤ v, and put a = gα/2 ∧ g1−α/2 , b = gα/2 ∨ g1−α/2 , D = |a − u| + |b − v|. Then a, b are finite measurable, a ≤ b, and (38)

D ≤ |gα/2 − u| + |g1−α/2 − v|.

Consequently, for every probability measure ν, p ∈ [1, ∞] and ε ≥ 0, the bounds ∥gα/2 − u∥Lp (ν) ≤ ε and ∥g1−α/2 − v∥Lp (ν) ≤ ε imply ∥D∥Lp (ν) ≤ 2ε,

∥D∥L1 (ν) ≤ 2ε.

Proof. Measurability follows because minimum and maximum are continuous maps on R2 . If gα/2 ≤ g1−α/2 , (38) is an equality. If g1−α/2 < gα/2 , the ordered matching inequality |g1−α/2 − u| + |gα/2 − v| ≤ |gα/2 − u| + |g1−α/2 − v|,

u ≤ v,

follows by checking the positions of gα/2 , g1−α/2 relative to [u, v]. Minkowski’s inequality gives the Lp bound, also for p = ∞; on a probability space ∥D∥L1 ≤ ∥D∥Lp . 20

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Lemma 14. Fix α ∈ (0, 1) and assume A 1. Let ν be a probability measure on X such that ν ≪ PX . Let a ≤ b and a′ ≤ b′ be finite measurable functions, and define Z ν Fa,b (t) = PY |X=x ([a(x) − t, b(x) + t]) dν(x), with [l, r] = ∅ for l > r, and analogously Faν′ ,b′ . Then Z
ν sup |Fa,b (t) − Faν′ ,b′ (t)| ≤ µup |a − a′ | + |b − b′ | dν.

(39)

t∈R

Moreover, both score CDFs are 2µup -Lipschitz: for s < t, (40)

ν ν 0 ≤ Fa,b (t) − Fa,b (s) ≤ 2µup (t − s),

and likewise for Faν′ ,b′ ; in particular, both are continuous. Proof. For every finite a ≤ b and t ∈ R, {y : max(a − y, y − b) ≤ t} = [a − t, b + t],

(41)

where the right side is empty when a − t > b + t. For possibly empty intervals, [l, r] △ [l′ , r′ ] ⊆ [l ∧ l′ , l ∨ l′ ] ∪ [r ∧ r′ , r ∨ r′ ]. The two covering intervals have lengths |l − l′ | and |r − r′ |. Applying the mass upper bound with l = a(x) − t, r = b(x) + t, l′ = a′ (x) − t, r′ = b′ (x) + t and integrating over x proves (39). For fixed x and s < t, {y : s < max(a(x) − y, y − b(x)) ≤ t} ⊆ [a(x) − t, a(x) − s] ∪ [b(x) + s, b(x) + t]. Each interval on the right has length t − s. The mass upper bound and integration over x prove (40); the argument for a′ , b′ is identical. ⋆ , b⋆ = f ⋆ Lemma 15. Fix α ∈ (0, 1) and assume A 1. Put a⋆ = fα/2 1−α/2 and Z ⋆ ⋆ ⋆ F (S |X) (t | x) = PY |X=x ([a⋆ (x) − t, b⋆ (x) + t]), F (S ) (t) = F (S |X) (t | x) dPX (x).

Then, for every x ∈ X0 , ⋆

F (S |X) (0 | x) = 1 − α,

b⋆ (x) − a⋆ (x) ≥

1−α . µup

Moreover, with r− = r0 ∧ (1 − α)/(2µup ) and r+ = r0 , ⋆

⋆

(S ⋆ )

(S ⋆ )

F (S ) (0) − F (S ) (−u) ≥ 2µlow u F

(v) − F

(0) ≥ 2µlow v

(0 ≤ u ≤ r− ),

(42)

(0 ≤ v ≤ r+ ).

(43)

Proof. The upper mass inequality at l = r gives PY |X=x ({l}) = 0. Hence the two equal-tail identities yield PY |X=x ([a⋆ (x), b⋆ (x)]) = 1 − α/2 − α/2 = 1 − α, and the upper mass bound gives the width inequality. If u ≤ r− , then a⋆ (x) + u ≤ b⋆ (x) − u; removing the two inner boundary intervals from [a⋆ (x), b⋆ (x)] loses at least 2µlow u. If v ≤ r+ , adding the two outer boundary intervals gains at least 2µlow v. Atomlessness removes all endpoint overlaps. Integration over the common full set X0 proves the marginal assertions. 21

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Lemma 16. Let α ∈ (0, 1), d ≥ 0, ρ, r− , r+ > 0, and let F be a CDF with F (0) = 1 − α such that F (0) − F (−u) ≥ ρu

(0 ≤ u ≤ r− ),

F (v) − F (0) ≥ ρv

(0 ≤ v ≤ r+ ).

Let Ĥ : R → [0, ∞) be nondecreasing and right-continuous, limt→−∞ Ĥ(t) = 0, and supt |Ĥ(t) − F (t)| ≤ d. For s ∈ R, suppose β = 1 − α + s > 0. If (d − s)+ < ρr− ,

(d + s)+ ≤ ρr+ ,

then {t : Ĥ(t) ≥ β} is nonempty and bounded below. Thus its ordinary infimum is finite and −

(d − s)+ (d + s)+ ≤ Q(β; Ĥ) ≤ . ρ ρ

(44)

Proof. Put t+ = (d + s)+ /ρ. If d + s ≥ 0, right growth and uniform approximation give Ĥ(t+ ) ≥ F (t+ ) − d ≥ 1 − α + ρt+ − d = β, whereas d + s < 0 gives t+ = 0 and Ĥ(0) ≥ 1 − α − d > β. Thus the superlevel set is nonempty. Let a = (d − s)+ /ρ. If −r− ≤ t < −a, left growth gives Ĥ(t) ≤ 1 − α − ρ|t| + d < β. If t < −r− , monotonicity and the strict left-window condition give Ĥ(t) ≤ Ĥ(−r− ) ≤ 1 − α − ρr− + d < β. Hence every superlevel point is at least −a, proving finiteness and (44). The strict left condition is necessary for discontinuous empirical cumulative functions. Take 1 − α = 1/2, ρ = 1/2, r− = r+ = 1, d = 1/2, s = 0, let F be the uniform CDF on [−1, 1], and set   t < −2, 0, Ĥ(t) = 1/2, −2 ≤ t < 1,   1, t ≥ 1. Then supt |Ĥ(t) − F (t)| = 1/2 and the left condition holds with equality, but Q(1/2; Ĥ) = −2 < −1. Lemma 17. Fix α ∈ (0, 1) and assume A 1. Let ν be a probability measure on X such that b ν ≪ PX . Let a ≤ b be finite measurable functions, q ∈ R, and C(x) = [a(x) − q, b(x) + q], with ⋆ ⋆ the empty-interval convention. Put D(x) = |a(x) − fα/2 (x)| + |b(x) − f1−α/2 (x)|. Then, for every p ∈ [1, ∞], CovCb −(1 − α) Lp (ν) ≤ 2µup |q| + µup ∥D∥Lp (ν) . (45) Proof. For x ∈ X0 , compare ⋆ ⋆ [a(x) − q, b(x) + q] and [fα/2 (x), f1−α/2 (x)].

Their symmetric difference is covered by the two endpoint-movement intervals, whose total length is at most D(x) + 2|q|, also when the first interval is empty. Therefore | CovCb (x) − (1 − α)| ≤ µup D(x) + 2µup |q|. Taking the Lp (ν) norm proves (45). 22

Conformalized Quantile Regression under Covariate Shift

B

Proofs for Global CQR

B.1

Proof of Proposition 1

Isaev et al.

This section gives the complete training and calibration events, DKW allocation, signed-threshold localization, and length calculation. We restate Proposition 1 in complete form to display the two localization inequalities used in the inversion step. Proposition 1. Let α ∈ (0, 1), p ∈ [1, ∞], and assume A 1 and A 2(p). Fix δ ∈ (0, 1) and n, m satisfying 2µup ϵp (n, δ/4) + ηm (δ) ≤ 2µlow r− ,

2µup ϵp (n, δ/4) + ηm (δ) + sm ≤ 2µlow r+ .

cal ), Q b β is finite, With probability at least 1 − δ over (Dntr , Dm m

− and

2µup ϵp (n, δ/4) + ηm (δ) b β ≤ 2µup ϵp (n, δ/4) + ηm (δ) + sm , ≤Q m 2µlow 2µlow

  µup ηm (δ) + sm ⋆ ˆ ∥|Cα (·)| − |Cα (·)|∥Lp (PX ) ≤ 2 1 + . ϵp (n, δ/4) + µlow µlow

Proof. ⋆ ⋆ Dn (x) = |fˆn,α/2 (x) − fα/2 (x)| + |fˆn,1−α/2 (x) − f1−α/2 (x)|.

(46)

For ε = ϵp (n, δ/4), let n o ∥fen,τ − fτ⋆ ∥Lp (PX ) ≤ ε .

\

Etr =

(47)

τ ∈{α/2,1−α/2}

By A 2(p) and a union bound, P(Etr ) ≥ 1 − δ/2. On this event, Lemma 13 gives, also for p = ∞, ∥Dn ∥Lp (PX ) ≤ 2ε,

∥Dn ∥L1 (PX ) ≤ 2ε.

(48)

Conditional on Dntr , the calibration scores are i.i.d. real random variables with CDF b F (S) (t) = P(S(X, Y ) ≤ t | Dntr ). b

For the two right-continuous CDFs in the following supremum, the supremum over R equals that over Q and is therefore measurable. The two-sided Dvoretzky–Kiefer–Wolfowitz inequality with Massart’s sharp constant [12, 28], applied conditionally on Dntr , requires no continuity of this CDF and gives   δ 2 b b (S) (S) tr b P sup |Fm (t) − F (t)| > ηm (δ) Dn ≤ 2e−2mηm (δ) = . (49) 2 t∈R Define

 EDKW =

 b b (S) sup |Fbm (t) − F (S) (t)| ≤ ηm (δ) . t∈R

The tower property and another union bound give An,m (δ) = Etr ∩ EDKW ,

P(An,m (δ)) ≥ 1 − δ.

⋆

Let F (S ) (t) = P(S ⋆ (X, Y ) ≤ t). On Etr , Lemma 14 with ν = PX gives ⋆

sup |F (S) (t) − F (S ) (t)| ≤ µup ∥Dn ∥L1 (PX ) ≤ 2µup ε. b

t

23

(50)

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

Consequently, on An,m (δ), ⋆

(S) sup |Fbm (t) − F (S ) (t)| ≤ 2µup ε + ηm (δ). b

t

(51)

⋆

By Lemma 15, F (S ) (0) = 1 − α and its left and right growth constants are 2µlow on r− and r+ , ⋆ respectively. Moreover, (8) gives sm > 0 and βm = 1 − α + sm . Since F (S ) (r+ ) ≤ 1, right growth at r+ gives 2µlow r+ ≤ α; hence the right localization condition and 2µup ε + ηm (δ) ≥ 0 imply sm ≤ α and βm ≤ 1. Apply Lemma 16 to (51) with ρ = 2µlow , d = 2µup ε + ηm (δ), s = sm , and level βm > 0. Since sm > 0, the first localization inequality implies the strict left-window condition (d − sm )+ < 2µlow r− : either d ≤ sm and (d − sm )+ = 0, or (d − sm )+ = d − sm < d ≤ 2µlow r− . The second localization inequality is the right-window condition (d + sm )+ ≤ 2µlow r+ . The lemma gives a nonempty, bounded-below empirical superlevel set, hence a finite ordinary infimum, and, since (d − sm )+ ≤ d, −

2µup ε + ηm (δ) b β ≤ 2µup ε + ηm (δ) + sm . ≤Q m 2µlow 2µlow

(52)

It remains to control the genuine length. Since fˆn,α/2 ≤ fˆn,1−α/2 ,
⋆ ⋆ bβ |Cˆα (x)| = fˆn,1−α/2 (x) − fˆn,α/2 (x) + 2Q |Cα⋆ (x)| = f1−α/2 (x) − fα/2 (x). m +, The positive-part map is 1-Lipschitz, so, for every x, b β |. |Cˆα (x)| − |Cα⋆ (x)| ≤ Dn (x) + 2|Q m This includes negative thresholds and empty learned intervals. Therefore, on An,m (δ), taking the b β | ≤ (2µup ε + ηm (δ) + sm )/(2µlow ) from (52) gives ∥ · ∥Lp (PX ) norm and using (48) together with |Q m   µ ηm (δ) + sm up ⋆ ∥|Cˆα (·)| − |Cα (·)|∥Lp (PX ) ≤ 2 1 + ε+ , µlow µlow which proves Proposition 1.

B.2

Proofs of Theorem 2 and Proposition 3

Section 3 of the article gives the coverage mechanism. Here we retain the complete common-event bookkeeping, endpoint/threshold calculation, and direct L1 argument. Theorem 2. Let α ∈ (0, 1), p ∈ [1, ∞], and assume A 1 and A 2(p). Fix δ ∈ (0, 1) and n, m satisfying 2µup ϵp (n, δ/4) + ηm (δ) ≤ 2µlow r− ,

2µup ϵp (n, δ/4) + ηm (δ) + sm ≤ 2µlow r+ .

On the event An,m (δ) of (50), whose probability is at least 1 − δ,  
µup µup ∥ CovCˆα (·) − (1 − α)∥Lp (PX ) ≤ 2µup 1 + ϵp (n, δ/4) + ηm (δ) + sm . µlow µlow

(53)

bβ Proof. Work on An,m (δ), where (52) ensures that Q ∈ R. On X0 , Lemma 15 gives m ⋆ ⋆ PY |X=x ([fα/2 (x), f1−α/2 (x)]) = 1 − α. Apply Lemma 17 with ν = PX , a = fˆn,α/2 , b = fˆn,1−α/2 , b β and D = Dn : q=Q m

b β | + µup ∥Dn ∥Lp (P ) . ∥ CovCˆα (·) − (1 − α)∥Lp (PX ) ≤ 2µup |Q m X 24

(54)

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Equations (48) and (52) bound, respectively, the endpoint and threshold terms in (54): µup ∥Dn ∥Lp (PX ) ≤ 2µup ϵp (n, δ/4),

bβ | ≤ 2µup |Q m

µup 2µup ϵp (n, δ/4) + ηm (δ) + sm . µlow

Substitution in (54) gives ∥ CovCˆα (·) − (1 − α)∥

Lp (P

 
µup µup ϵp (n, δ/4) + ≤ 2µup 1 + ηm (δ) + sm , X) µlow µlow

which is (53). Proposition 3. Let α ∈ (0, 1) and assume A 1 and the p = 1 instance of A 2(p). For every δ ∈ (0, 1) and n, m ≥ 1, let An,m (δ) be the event in (50), with Etr defined by (47) using ϵ1 (n, δ/4). Then P(An,m (δ)) ≥ 1 − δ, and, on this event, ∥ CovCˆα −(1 − α)∥L1 (PX ) ≤ 4µup ϵ1 (n, δ/4) + ηm (δ) + sm .

(55)

Proof. Work on An,m (δ). Conditional on Dntr , let
b b F (S) (t) = P S(X, Y ) ≤ t | Dntr . The CDF F (S) is continuous by Lemma 14. b β ∈ R, and the definition of the generalized inverse together with the DKW If βm ≤ 1, then Q m bound gives b b βm − ηm (δ) ≤ F (S) (Q βm ) ≤ βm + ηm (δ). b

b b b β = +∞ and |F (S) If βm > 1, then Q (Qβm ) − (1 − α)| = α < sm . Since βm = 1 − α + sm , both m cases give b b |F (S) (Q (56) β ) − (1 − α)| ≤ ηm (δ) + sm . m

b0 (x) = {y : S(x, b y) ≤ 0} = [fˆn,α/2 (x), fˆn,1−α/2 (x)]. For every x, the sets Cˆα (x) and C b0 (x) Set C are nested; hence b b b (S) ∥ CovCˆα − CovCb0 ∥L1 (PX ) = F (S) (Q (0) . βm ) − F The upper interval-mass condition makes the conditional laws atomless, so the equal-tailed oracle has coverage 1 − α. Applying Lemma 17 at threshold zero gives ∥ CovCb0 −(1 − α)∥L1 (PX ) ≤ µup ∥Dn ∥L1 (PX ) . Moreover, (48) gives ∥Dn ∥L1 (PX ) ≤ 2ϵ1 (n, δ/4). Therefore, b β ) − (1 − α) + F (S) (0) − (1 − α) ∥ CovCˆα −(1 − α)∥L1 (PX ) ≤ F (S) (Q m b

b

+ ∥ CovCb0 −(1 − α)∥L1 (PX ) ≤ ηm (δ) + sm + 2µup ∥Dn ∥L1 (PX ) ≤ ηm (δ) + sm + 4µup ϵ1 (n, δ/4). This is (55).

25

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

C

Proofs for Known Covariate Shift

Section 4 of the article gives the known-shift mechanism and decisive displays. Here we verify the complete event and constant calculations for the weighted empirical process, target length, and target profile bounds. The separate fixed-score calibration benchmarks are proved in the next section.

C.1

Setup and procedure

The generic shifted proof assumes A 1 and L 1 and A 2(p), and uses the sorted endpoints in (4). The target functionals are those in (13); the realized profile is evaluated under the target marginal.

C.2

Known-Shift Calibration Lemmas

Section 4 of the article records the unbiasedness, ordered-prefix mechanism, and final radius; this subsection verifies the exact constants. Weighted calibration deviation Fix a training realization. Joint measurability and finiteness b y)) a measurable map into R2 . The calibration of the sorted endpoints make (x, y) 7→ (w(x), S(x, images are therefore i.i.d., and   b Dtr . F bQ (t) := (QX ⊗ PY |X )(Sb ≤ t) = EPXY w 1(−∞,t] (S) n S

The equality follows by first integrating the indicator against PY |X=x and then using dQX = w dPX ; the normalization is deterministic and no random denominator appears. Lemma 18. Fix m ≥ 1 and assume L 1. Conditionally on Dntr , set + := sup{Fbmw (t) − F bQ (t)}, Zm

− := sup{F bQ (t) − Fbmw (t)}. Zm

S

t∈R

t∈R

S

Then, with the universal constant CHL = 4, s + − E[Zm | Dntr ] ∨ E[Zm | Dntr ] ≤ CHL

1 + χ2 (QX ∥PX ) . m

(57)

Proof. Write gt (x, y) = w(x)1S(x,y)≤t . Because the empirical and population weighted CDFs are b right-continuous, each one-sided supremum over R equals the corresponding supremum over Q. Hence the indexing class may be taken countable and the suprema are measurable. The one-sided consequence of the symmetrization lemma [50, Lemma 2.3.1, p. 108] gives, for either sign, m

1 X εi gt (Zi ), t∈R m

± E[Zm | Dntr ] ≤ 2EZ,ε sup

i=1

− where the εi are independent Rademacher signs. The same symmetrization bound applies to Zm after replacing every Rademacher sign by its negative; the joint sign law is unchanged. Conditional on the sample, order the finite scores Sbi increasingly, with any fixed ordering inside ties. Every set {i : Sbi ≤ t} ends at a tie-block boundary and is therefore one of these ordered prefixes. Hence

sup t

X i

εi w(Xi )1Sbi ≤t ≤ max

0≤k≤m

26

X j≤k

επ(j) w(Xπ(j) ) .

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

The partial sums form a martingale in the Rademacher signs. Doob’s L2 maximal inequality [10, Chapter VII, Theorem 3.4, p. 317] and Cauchy–Schwarz give conditional expectation at most P 2( i w(Xi )2 )1/2 . Thus Jensen’s inequality yields v s
um X u 1 + χ2 (QX ∥PX ) 4 ± tr 2 t . E[Zm | Dn ] ≤ E w(Xi ) ≤ 4 m m i=1

Ties only remove possible prefix endpoints and cannot increase the maximum. Empirical-process refinement of the weighted deviation For gt = w1S≤t b ,
sup VarPXY (gt ) ≤ sup EPXY [gt2 ] ≤ 1 + χ2 (QX ∥PX ) ≤ wmax . t

t∈R

(58)

This variance upper bound, together with envelope wmax , is the input to the concentration inequality below. Lemma 19. Fix m ≥ 1 and δ ∈ (0, 1), and assume L 1. Conditionally on Dntr , define   Q w w w Eunif := sup Fbm (t) − F b (t) ≤ ηm (δ) . S

t∈R

(59)

Then w P(Eunif | Dntr ) ≥ 1 − δ/2. w (δ) is defined in (21). The empirical and population weighted CDFs are rightProof. The radius ηm continuous, so their difference has the same supremum over Q as over R. This gives the countable class required by [7, Theorem 2.3] and makes the supremum measurable. For µt = Egt , apply that theorem separately to the centered classes gt −µt and µt −gt , t ∈ Q. Both have centered envelope wmax : indeed gt − µt ≤ wmax , while µt − gt ≤ µt ≤
Ew = 1 ≤ wmax ; in fact 2 |gt − µt | ≤ wmax . Their variances are bounded above by 1 + χ (QX ∥PX ) by (58). In the notation
± , σ 2 ≤ 1 + χ2 (Q ∥P ) /w 2 , of [7, Theorem 2.3], the two applications have Z = (m/wmax )Zm X X max and v = mσ 2 + 2EZ. Rescaling its unnormalized unit-envelope bound gives, for either sign and every u > 0, r

wmax u 2u ± ± ± Zm ≤ EZm + 1 + χ2 (QX ∥PX ) + 2wmax EZm + m 3m

with failure probability at most e−u . Since s ± 4uwmax EZm uwmax ± + ≤ EZm , m m Lemma 18 yields s

s 2 (Q ∥P ) 2u 1 + χ2 (QX ∥PX ) 1 + χ 4uwmax X X ± Zm ≤ 2CHL + + . m m 3m √ √ Take u = uδ = log(4/δ). Since uδ ≥ log 4 and 8/ log 4+ 2 < 9, the right-hand side above is at most w (δ). Each sign has failure probability δ/4, so a union bound gives P(E w | D tr ) ≥ 1 − δ/2. ηm n unif 27

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Calibration threshold bound Let Z ⋆ ⋆ (x) + t]) dQX (x). (x) − t, f1−α/2 PY |X=x ([fα/2 FSQ⋆ (t) := X

Since QX ≪ PX , the common set X0 of A 1 is also QX -full. The pointwise argument of Lemma 15, now integrated under QX , gives FSQ⋆ (0) = 1 − α, FSQ⋆ (0) − FSQ⋆ (−u) ≥ 2µlow u (0 ≤ u ≤ r− ), FSQ⋆ (v) − FSQ⋆ (0) ≥ 2µlow v

(60)

(0 ≤ v ≤ r+ ).

Thus the same asymmetric inversion lemma applies under the target marginal; no density or bounded-support specialization is used. Lemma 20. Fix α ∈ (0, 1) and m ≥ 1, and assume L 1. The set {w > 0} is QX -full. For every fixed calibration realization and every x in this set, mFbmw (+∞) + w(x) > 0, the measure in (17) is a w (x) bm probability measure, its (1 − α)-quantile satisfies the raw-level representation (19), and x 7→ Q is measurable as an R-valued map. In particular, if X⋆ ∼ QX , then mFbmw (+∞) + w(X⋆ ) > 0

w(X⋆ ) > 0,

almost surely.

For every a ∈ R, o n
w w w b b b {x : w(x) > 0, Qm (x) ≤ a} = x : w(x) > 0, (1 − α) Fm (+∞) + w(x)/m ≤ Fm (a) .

(61)

Proof. The Radon–Nikodym identity gives Z QX {w = 0} =

w(x) dPX (x) = 0. {w=0}

Hence {w > 0} is QX -full and w(X⋆ ) > 0 almost surely. Moreover, w(Xj ) ≥ 0 for every j, so Fbmw (+∞) ≥ 0. Thus, for x ∈ {w > 0}, mFbmw (+∞) + w(x) ≥ w(x) > 0, and the coefficients in (17) are nonnegative and sum to Pm j=1 w(Xj ) + w(x) = 1. mFb w (+∞) + w(x) m

This also proves the asserted positivity at X⋆ ; no positivity of the individual calibration weights is required. For x ∈ {w > 0} and t ∈ R, the measure in (17) assigns to (−∞, t] the mass mFbmw (t) mFbmw (+∞) + w(x)

,

which is at least 1 − α exactly when
Fbmw (t) ≥ (1 − α) Fbmw (+∞) + w(x)/m . 28

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

The (1 − α)-quantile of this measure is the infimum of such t when one exists; otherwise the requested level is carried by the atom at +∞ and the quantile equals +∞, which matches the convention that an unattained level has generalized inverse +∞. This proves (19). b w (x) ≤ a exactly On {w > 0}, (19) and right-continuity of the finite weighted step function give Q m w when its requested raw level does not exceed Fbm (a). The right-hand side of (61) is measurable in the trace σ-field on {w > 0}; finite sublevels generate the order-Borel σ-field of R. Lemma 21. Let α ∈ (0, 1), p ∈ [1, ∞], and assume A 1 and L 1 and A 2(p). Fix δ ∈ (0, 1) and tr cal n, m ≥ 1 satisfying (22). There is an event Aw n,m (δ), measurable with respect to (Dn , Dm ) and of probability at least 1 − δ, on which Fbmw (+∞) > 0 and, for QX -almost every x, 1/p

w

b w (x) ≥ − 2µup wmax ϵp (n, δ/4) + (2 − α)ηm (δ) , Q m 2µlow 1/p

w (δ) + (1 − α)w(x)/m 2µup wmax ϵp (n, δ/4) + (2 − α)ηm w bm Q (x) ≤ . 2µlow

(62)

w (x) is finite on a target-full set and bm In particular, Q 1/p

w bm ∥Q ∥Lp (QX ) ≤

w (δ) + (1 − α)∥w∥ p 2µup wmax ϵp (n, δ/4) + (2 − α)ηm L (QX ) /m . 2µlow

(63)

Proof. Let Dn and Etr be as in (46)–(47), and put ε = ϵp (n, δ/4). The endpoint assumption and sorting contraction give P(Etr ) ≥ 1 − δ/2 and, on this event, ∥Dn ∥Lp (PX ) ≤ 2ε,

∥Dn ∥L1 (PX ) ≤ 2ε.

The change of measure and monotonicity of probability-space norms yield 1/p ∥Dn ∥Lp (QX ) ≤ 2wmax ε,

Consequently,

(64)

1/p sup |F bQ (t) − FSQ⋆ (t)| ≤ 2µup wmax ε,

(65)

1/p w sup |Fbmw (t) − FSQ⋆ (t)| ≤ 2µup wmax ε + ηm (δ).

(66)

t∈R

w , and, on Eunif

1/p ∥Dn ∥L1 (QX ) ≤ 2wmax ε.

S

t∈R

Set

w Aw n,m (δ) := Etr ∩ Eunif .

The conditional calibration bound, the tower property, and a union bound give P(Aw n,m (δ)) ≥ 1 − δ. w w b On this event, |Fm (+∞) − 1| ≤ ηm (δ). The first condition in (22), together with 2µlow r− ≤ 1 − α, w (δ) < 1; hence F bmw (+∞) > 0. For fixed x, write implies ηm 1/p w d = 2µup wmax ε + ηm (δ),
w s(x) = (1 − α) Fbm (+∞) − 1 + w(x)/m .

Then 1 − α + s(x) = (1 − α)(Fbmw (+∞) + w(x)/m) > 0, and 1/p w (d − s(x))+ ≤ 2µup wmax ε + (2 − α)ηm (δ), 1/p w (d + s(x))+ ≤ 2µup wmax ε + (2 − α)ηm (δ) + (1 − α)w(x)/m.

The bound w(x) ≤ wmax and (22) verify the strict left and weak right windows. Apply Lemma 16 to (60) and (66) with ρ = 2µlow , then use (19). This proves (62) and finiteness. Since the right numerator dominates the absolute value of both bounds, Minkowski’s inequality gives (63). 29

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

For finite p,
p−1 p−1 ∥w∥pLp (QX ) = EPX [wp+1 ] ≤ wmax EPX [w2 ] = wmax 1 + χ2 (QX ∥PX ) .

(67)

For p = ∞, ∥w∥L∞ (QX ) ≤ wmax .

C.3

Proof of Proposition 4

Proposition 4. Let α ∈ (0, 1) and p ∈ [1, ∞], and assume A 1 and L 1 and A 2(p). Fix δ ∈ (0, 1) and n, m ≥ 1 satisfying (22). On the event Aw n,m (δ) of Lemma 21, the pointwise threshold bound (62) holds and   µ up w ⋆ 1/p ∥ |Cbα (·)| − |Cα (·)| ∥Lp (QX ) ≤ 2 1 + wmax ϵp (n, δ/4) µlow (68) w (δ) + (1 − α)∥w∥ p (2 − α)ηm L (QX ) /m . + µlow w (x) is finite, bm Proof. For every x at which Q

b w (x) . |Cbαw (x)| = fˆn,1−α/2 (x) − fˆn,α/2 (x) + 2Q m + The positive-part map is 1-Lipschitz, including negative thresholds and empty fitted intervals, so b w ∥Lp (Q ) . ∥ |Cbαw (·)| − |Cα⋆ (·)| ∥Lp (QX ) ≤ ∥Dn ∥Lp (QX ) + 2∥Q m X

(69)

Substitute (64) and (63) into (69) and collect terms.

C.4

Proof of Theorem 5

Theorem 5. Let α ∈ (0, 1) and p ∈ [1, ∞], and assume A 1 and L 1 and A 2(p). Fix δ ∈ (0, 1) and n, m ≥ 1 satisfying (22). On the event Aw n,m (δ) of Proposition 4,   µup 1/p ∥ CovCbw (·) − (1 − α)∥Lp (QX ) ≤ 2µup 1 + wmax ϵp (n, δ/4) α µlow   µup 1−α w + (2 − α)ηm (δ) + ∥w∥Lp (QX ) . µlow m

(70)

Proof. On the target-full set X0 , the symmetric difference between Cbαw (x) and Cα⋆ (x) is covered by b w (x)|. The upper conditional endpoint-movement intervals of total length at most Dn (x) + 2|Q m interval-mass bound therefore gives b w ∥Lp (Q ) . ∥ CovCbw (·) − (1 − α)∥Lp (QX ) ≤ µup ∥Dn ∥Lp (QX ) + 2µup ∥Q m X α

Substitute (64) and (63). Remark 22. Under the p = 2 endpoint assumption, Cauchy–Schwarz gives q
∥g∥L1 (QX ) ≤ 1 + χ2 (QX ∥PX ) ∥g∥L2 (PX ) .

30

(71)

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Thus the p = 1 results remain valid after replacing every endpoint factor wmax ϵ1 (n, δ/4) by q
1 + χ2 (QX ∥PX ) ϵ2 (n, δ/4), including in the localization conditions. Since ∥w∥L1 (QX ) = 1 +
χ2 (QX ∥PX ) , the resulting length and profile bounds contain, respectively,
 q w (δ) + (1 − α) 1 + χ2 (Q ∥P ) /m
(2 − α)η µup X X m 2 1+ 1 + χ2 (QX ∥PX ) ϵ2 (n, δ/4) + µlow µlow and

 q
µup µup w 2µup 1 + 1 + χ2 (QX ∥PX ) ϵ2 (n, δ/4) + (2 − α)ηm (δ) µlow µlow
µup (1 − α) 1 + χ2 (QX ∥PX ) + . µlow m This refinement leaves the weighted calibration radius and its envelope assumption unchanged. Exact target marginal validity Conditional on Dntr , the fitted score is fixed and measurable. Corollary 1 of Tibshirani et al. [47], together with the split-conformal extension described in their Section 2.2 and supplementary material, applied to the source calibration sample and an independent target test point, gives   P Y⋆ ∈ Cbαw (X⋆ ) Dntr ≥ 1 − α. (72) Equation (72) averages over both calibration and test data; it does not condition on the realized calibration sample. Pournaderi and Xiang [35, Theorem 1 and Corollary 1] control the upper tail of the corresponding target marginal miscoverage after the calibration sample is also fixed. By contrast, Theorem 5 controls the two-sided spatial Lp (QX ) deviation of the complete realized profile. Its p = 1 instance also bounds the absolute realized marginal deviation through Z CovCbw (x) dQX (x) − (1 − α) ≤ ∥ CovCbw (·) − (1 − α)∥L1 (QX ) . X

α

α

D

Proofs for Fixed-Score Calibration Limits

D.1

Scalar fixed-score calibration: Le Cam lower bound and achievability

Every supremum over PY |X ranges over conditional kernels for which A 1 holds on a measurable set of full PX -measure. All infima below range over scalar or vector thresholds measurable in the m source calibration observations. We use the symbols cα , m⋆ , and Rm,p from Section 5. For a realized threshold function qb, the notation CovP{S ⋆ ≤bq} always refers to the conditional-coverage profile defined in (26). Theorem 6. Fix α ∈ (0, 1) and κ > 0, and assume that X contains two distinct points whose singleton sets are measurable. Then there exist source and target marginals PX , QX , a reference conditional kernel PY0 |X , and a reference score S ⋆ , all independent of m, with the following properties. The marginals satisfy L 1 and χ2 (QX ∥PX ) = κ. The kernel PY0 |X satisfies A 1 on a set of full PX -measure. The score S ⋆ is the equal-tailed oracle CQR score under PY0 |X and is held fixed throughout the minimax problem below. For m ≥ 1 and p ∈ [1, ∞], define h i Rm,p := inf sup E(PX ⊗PY |X )⊗m ∥ CovP{S ⋆ ≤bq} (·) − (1 − α)∥Lp (QX ) . qb PY |X

31

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Set

 4(log 2)(1 + κ) α(1 − α) . m⋆ := min{α, 1 − α}2 

Then for every m ≥ m⋆ and p ∈ [1, ∞], r 1+κ , Rm,p ≥ cα m

cα :=

1p (log 2)α(1 − α). 8

Proof. Fixed experiment and density realization. We construct two kernels PY0 |X , PY1 |X satisfying j A 1 with the common marginal PX , and write PXY = PX ⊗ PYj |X . At threshold zero, their target coverages will be 1 − α and 1 − α − ξ, respectively. The total variation distance between their m-fold j ⊗m source laws will be at most 1/2. Write Ej for expectation under PXY . Fix an arbitrary scalar threshold rule qb. Choose distinct points x0 , xD ∈ X and set

QX = δx0 ,

PX =

1 κ δx0 + δx . 1+κ 1+κ D

Then 1 + χ2 (QX ∥PX ) = 1 + κ and QX ({x0 }) = 1, 1
, PX ({x0 }) = 2 1 + χ (QX ∥PX )

QX ({xD }) = 0, PX ({xD }) = 1 −

1 1 + χ2 (QX ∥PX )

.

Then w = dQX /dPX equals 1 + χ2 (QX ∥PX ) at x0 and zero at xD , and
EPX [w2 ] = 1 + χ2 (QX ∥PX ) ,

EPX [w] = 1,
χ2 (QX ∥PX ) = 1 + χ2 (QX ∥PX ) − 1.

A source draw reaches x0 with probability 1/ 1 + χ2 (QX ∥PX ) . Since QX = δx0 , for every candidate kernel PY |X , every realized threshold qb, and every p ∈ [1, ∞], ∥ CovP{S ⋆ ≤bq} (·) − (1 − α)∥Lp (QX ) = CovP{S ⋆ ≤bq} (x0 ) − (1 − α) . Take PY0 |X uniform on [−1, 1] for every x, and fix S ⋆ (x, y) = |y| − (1 − α). This is the equal-tailed oracle CQR score for PY0 |X , whose oracle endpoints are −1 + α and 1 − α; the same score is retained under PY1 |X . Define B0 = [−(1 − α), 0],

B1 = (0, α].

Thus the score-band lengths and reference masses are |B0 | = 1 − α and |B1 | = α. At x0 define p1Y |X (y | x0 ) =

1−α−ξ α+ξ 1 + 1 , 2(1 − α) {|y|≤1−α} 2α {1−α<|y|≤1}

(73)

and set PY1 |X = PY0 |X off x0 . The fixed score then has masses (1 − α − ξ, α + ξ) on (B0 , B1 ) under the alternative. 32

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

If 0 < ξ ≤ 12 min{α, 1 − α}, both densities lie between 1/4 and 3/4 on [−1, 1]. Each side of either equal-tail quantile has mass at least α/2, so the upper density bound places both quantiles at distance at least 2α/3 from both support boundaries. Hence all four one-sided neighborhoods of radius r0 = α/2 lie in [−1, 1]. The density bounds give the upper interval-mass inequality with µup = 3/4 and the four lower inequalities with µlow = 1/4. Thus both kernels satisfy A 1. Threshold and fraction-loss geometry. The action class consists only of rays {S ⋆ ≤ q}. Clipping q to [0, α] cannot increase either absolute coverage error, so it is enough to write qe := min{α, max{0, qb}},

a :=

qe ∈ [0, 1] α

0 1 for the fraction of B1 admitted by the ray. Under PXY the split is (1 − α, α), whereas under PXY it ⋆ is (1 − α − ξ, α + ξ). Hence, with a := ξ/(α + ξ), 0

D0 (a) := CovP{S ⋆ ≤αa} (x0 ) − (1 − α) = αa, 1

D1 (a) := CovP{S ⋆ ≤αa} (x0 ) − (1 − α) = (α + ξ)(a − a⋆ ). The zeros are a0 = 0 and a1 = a⋆ . By the point-mass target collapse, the theorem’s loss under hypothesis j equals Ej |Dj (a)| for every p ∈ [1, ∞]. 1 ∥P 0 ). The hypotheses differ only in the Two-point information bound. Write χ2obs := χ2 (PXY XY (B0 , B1 ) split at x0 . The reference joint masses of these cells are PX ({x0 })(1 − α) and PX ({x0 })α, and their changes are −PX ({x0 })ξ and PX ({x0 })ξ. Since the densities are constant within each cell, the widths cancel in the χ2 integral. Thus χ2obs = PX ({x0 }) ξ 2

h

1 1i ξ2
+ = , 1−α α 1 + χ2 (QX ∥PX ) α(1 − α)

where 1/ 1 + χ2 (QX ∥PX ) is the mass of the informative atom. To control product total variation, use the tensorizing χ2 divergence. For P ≪ Q, Cauchy– Schwarz gives sZ sZ Z Z 1 1 |p − q| √ (p − q)2 1p 2 1 |p − q| = q= TV(P, Q) = q≤ χ (P ∥Q) . √ 2 2 q 2 q 2 Expanding the square gives Z 2 Z Z Z (p − q)2 p = −2 p+ q, q q

i.e.

2

1 + χ (P ∥Q) =

Z

p2 , q

and this integral factorizes on products [48, Section 2.4]: Z Y m m m Z Y

m p(zs )2 Y p2 1 + χ2 P ⊗m ∥Q⊗m = dzs = = 1 + χ2 (P ∥Q) . q(zs ) q s=1

s=1

(74)

s=1

The two displays chain to
1q
1q 1 ⊗m 0 ⊗m 1 ⊗m 0 ⊗m TV PXY , PXY ≤ 2 χ2 PXY ∥PXY = 2 (1 + χ2obs )m − 1 , so TV ≤ 21 holds once (1 + χ2obs )m ≤ 2. By 1 + x ≤ ex , the budget χ2obs ≤ 33

log 2 m

(75)

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

suffices:

2

whence

(1 + χ2obs )m ≤ em χobs ≤ elog 2 = 2 ,

√ TV ≤ 12 2 − 1 = 12 .

Because the per-draw divergence increases with ξ, the largest gap allowed by (75) saturates it: s
2 (log 2) 1 + χ2 (QX ∥PX ) α(1 − α) log 2 ξ ⋆
= =⇒ ξ = ξ := , m m 1 + χ2 (QX ∥PX ) α(1 − α) 0 ⊗m 1 ⊗m whence TV(PXY , PXY ) ≤ 12 . The theorem assumes m ≥ m⋆ , which gives ξ ⋆ ≤ 12 min{α, 1 − α}; hence the density check following (73) applies. 1 ⊗m 0 ⊗m Le Cam assembly. Write p0 , p1 for the densities of PXY , PXY against a common dominating measure. For any statistic a of the sample, the triangle inequality |a − a0 | + |a − a1 | ≥ |a1 − a0 | = a⋆ against the minimum density gives Z
E0 |a − a0 | + E1 |a − a1 | ≥ min(p0 , p1 ) |a − a0 | + |a − a1 | Z ⋆ ≥ a min(p0 , p1 ) = a⋆ (1 − TV) .

Here the last P equality is the affinity identity maxj ≥ 12 j and TV ≤ 21 , max Ej |a − aj | ≥ j

R

min(p0 , p1 ) = 1 − TV [48, Theorem 2.2]. With a⋆ a⋆ (1 − TV) ≥ . 2 4

Both slopes are at least α: |D0 (a)| = α |a − a0 | and |D1 (a)| = (α + ξ) |a − a1 | ≥ α |a − a1 |. Thus the two-point inequality transfers to the deviations at the price of the smaller slope: max Ej Dj (a) ≥ α max Ej |a − aj | ≥ j

j

α a⋆ αξ αξ ξ = ≥ = , 4 4(α + ξ) 4 · 2α 8

the last inequality by α + ξ ≤ 2α, i.e. ξ ≤ α. At the saturated ξ = ξ ⋆ , s
p 1 + χ2 (QX ∥PX ) ξ⋆ 1 = 8 (log 2)α(1 − α) . 8 m | {z } = cα

Both hypotheses lie in the supremum class. By the point-mass target collapse, for every p ∈ [1, ∞], h i sup E(PX ⊗PY |X )⊗m ∥ CovP{S ⋆ ≤bq} (·) − (1 − α)∥Lp (QX ) PY |X

ξ⋆ ≥ max Ej |Dj (a)| ≥ 8 j∈{0,1} s
1 + χ2 (QX ∥PX ) = cα . m Taking the infimum over qb yields s
1 + χ2 (QX ∥PX ) Rm,p ≥ cα , m

cα =

1p (log 2)α(1 − α). 8

Every displayed Lp (QX ) norm equals |EQX [CovP{S ⋆ ≤bq} (X)] − (1 − α)|, so the same bound holds for the absolute target marginal-coverage deviation. This proves the theorem. 34

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Proposition 7. Under the assumptions of Theorem 6, use the source and target marginals and fixed reference score used in its two-point construction, target atom.
−1 and let x0 denote thePunique m 2 Thus QX = δx0 and PX ({x0 }) = 1 + χ (QX ∥PX ) . For m ≥ 1, let N = i=1 1{Xi =x0 } , order the corresponding scores as T(1) ≤ · · · ≤ T(N ) , set T(N +1) = +∞, and define qbcar := T(kN ) ,

kn = ⌈(n + 1)(1 − α)⌉ .

For each admissible kernel, let FP (t) = PY |X=x0 {S ⋆ (x0 , Y ) ≤ t}, with expectation taken over cal ∼ (P ⊗ P ⊗m . Dm X Y |X ) sup EDm q car ) − (1 − α)| cal |FP (b

PY |X

3 ≤ 2 3 ≤ 2

s

s

1 + χ2 (QX ∥PX ) m+1





1− 1−

−1 1 + χ2 (QX ∥PX )

m+1 

1 + χ2 (QX ∥PX ) . m+1

The supremum risk on the left is asymptotic to
χ2 (QX ∥PX ) → ∞.

q
2α(1 − α) 1 + χ2 (QX ∥PX ) /(πm) as m/ 1 +

Proof of Proposition 7. Put τ = 1 − α and N=

m X

1{Xi =x0 } ∼ Bin(m, 1 + χ2 (QX ∥PX ) −1 ).

i=1

On this construction, every calibration observation at x0 and the test atom at x0 have weight
1 + χ2 (QX ∥PX ) , while every observation at xD has weight zero. After cancelling the common positive factor, the exact weighted conformal measure (17) becomes N

1 X 1 δ+∞ . δT(j) + N +1 N +1 j=1

Its (1 − α)-quantile is therefore the carrier rule: w bm Q (x0 ) = qbcar = T(kN ) ,

kn = ⌈(n + 1)τ ⌉,

T(n+1) = +∞.

For N = 0, the measure is δ+∞ ; if kN = N + 1, its quantile is again +∞. Thus the identity covers every calibration realization. The all-interval upper mass bound in A 1 makes the conditional law atomless, while S ⋆ (x0 , ·) has level sets of cardinality at most two; hence FP is continuous. Conditional on N = n, the probability integral transform makes the transformed carrier scores i.i.d. uniform. Consequently, FP (T(k) ) ∼ Beta(k, n + 1 − k),

1 ≤ k ≤ n;

see also [38, Proposition 2]. Let Bn,k ∼ Beta(k, n + 1 − k) for k ≤ n, and set Bn,n+1 = 1. Since QX ({x0 }) = 1, the Lp (QX ) profile loss is |FP (b q car ) − τ | for every p ∈ [1, ∞]. Averaging over N gives sup EDm q car ) − τ |] cal [|FP (b

PY |X

=

m   X m n=0

n

1 + χ2 (QX ∥PX )

−n 

−1 m−n 1 − 1 + χ2 (QX ∥PX ) E|Bn,kn − τ |. 35

(76)

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

The right side does not depend on the kernel and equals the supremum risk of the carrier rule. Write rn = E|Bn,kn − τ |. If kn ≤ n, the beta mean µn = kn /(n + 1) and variance satisfy 0 ≤ µn − τ < Therefore rn ≤

1 , n+1

Var(Bn,kn ) =

kn (n + 1 − kn ) 1 ≤ . (n + 1)2 (n + 2) 4(n + 2)

q 1 1 + Var(Bn,kn ) + |µn − τ | ≤ √ . 2 n+2 n+1

If kn = n + 1, the ceiling identity implies 1 − τ < 1/(n + 1), and the same bound holds because Bn,n+1 = 1. Hence, for every n ≥ 0, 1 1 3 + . rn ≤ √ ≤ √ 2 n+2 n+1 2 n+1

(77)

By Cauchy–Schwarz, the left side of (76) is at most s     3 1 3 1 E √ ≤ E . 2 2 N +1 N +1 The binomial identity
    
−1 m+1 1 + χ2 (QX ∥PX ) 1 2 E = 1 − 1 − 1 + χ (QX ∥PX ) (78) N +1 m+1

m+1 follows from m /(n + 1) = n n+1 /(m + 1). This proves both finite upper bounds. It remains to identify the leading constant. Since kn /n = τ + O(n−1 ), Corollary 21.5 and Lemma 21.7 of van der Vaart [49] give
√ n (Bn,kn − τ ) ⇝ N 0, τ (1 − τ ) . The moment bound above gives uniform integrability; the convention Bn,n+1 = 1 applies only to finitely many n. Thus r √ 2τ (1 − τ ) n rn −→ cτ := . π
√ Set λm = m/ 1 + χ2 (QX ∥PX ) . If λm → ∞, then N/λm → 1 in probability and λm rN → cτ in probability. Moreover, (77) and (78) give   h p 
2 i 9 m
−1 m+1 9 2 λm rN ≤ 1 − 1 − 1 + χ (QX ∥PX ) ≤ . E 4 m+1 4 √ Hence { λm rN } is uniformly integrable. Therefore, the left-hand side of (76) is asymptotic to q

2α(1 − α) 1 + χ2 (QX ∥PX ) /(πm) as m/ 1+χ2 (QX ∥PX ) → ∞. At α = 0.1, the leading constant is 0.2394.

D.2

A high-probability fixed-score lower bound for an atomic target

Spread the perturbation over K target atoms and assign one threshold value to each atom. A Varshamov–Gilbert packing [16, 51], followed by the χ2 form of Fano’s inequality, raises the failure probability from the two-point constant to 1 − 2e−K/32 while preserving the realized-coverage loss
2 and the factor 1 + χ (QX ∥PX ) . 36

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Lemma 23. For every integer K ≥ 0 there exists A ⊆ {0, 1}K with |A| ≥ eK/8

dH (v, v ′ ) ≥

and

K 4

for all distinct v, v ′ ∈ A.

Proof. For K = 0 take the single point A = {0, 1}0 . For K ≥ 1, [29, Lemma 4.7] states that, for every β ∈ (0, 1), there exists A ⊆ {0, 1}K with dH (v, v ′ ) > (1 − β)

K 2

for all distinct v, v ′ ∈ A,

and

ln |A| ≥

ρβ K , 2

where ρβ = (1 + β) ln(1 + β) + (1 − β) ln(1 − β); we use β for the parameter there called α. Take β = 12 . Then dH (v, v ′ ) > K/4, hence dH (v, v ′ ) ≥ K/4. Moreover, ρ1/2 = 32 ln 23 + 12 ln 12 > 14 , so ln |A| ≥ ρ1/2 K/2 > K/8 and |A| ≥ eK/8 . Theorem 8. Fix α ∈ (0, 1), an integer K ≥ 23, and κ > 0, and assume that X contains at least 2K distinct points whose singleton sets are measurable. Then there exist source and target marginals PX , QX , distinct points x1 , . . . , xK , a reference conditional kernel PY0 |X , and a reference score S ⋆ , all independent of m, with the following properties. The marginals satisfy L 1, K

χ2 (QX ∥PX ) = κ,

QX =

1 X δxk . K k=1

PY0 |X satisfies A 1 on a set of full PX -measure. The score S ⋆ is the equal-tailed oracle CQR score under PY0 |X and is held fixed throughout the minimax problem below. For a threshold vector qb1:K , define its canonical measurable extension by ( qbk , x = xk for some k ∈ {1, . . . , K}, qb(x) = 0, x ∈ / {x1 , . . . , xK }. The value chosen off the target support is immaterial to the loss below. Set (K)

m⋆ (K)

Then for every integer m > m⋆

:=

(1 + κ) α(1 − α)K . 4 min{α, 1 − α}2

(79)

and every p ∈ [1, ∞],

inf sup P(PX ⊗PY |X )⊗m ∥ CovP{S ⋆ ≤bq} (·) − (1 − α)∥Lp (QX )

qb1:K PY |X

1 ≥ 64 Proof. Set 1 ξ := 4

r

r

(1 + κ) α(1 − α)K m

(1 + κ) α(1 − α)K . m

(K)

! ≥ 1 − 2e−K/32 .

(80)

Since m > m⋆ , (79) gives ξ < 21 min{α, 1 − α}. Step 1: geometry and density admissibility. The 2K hypotheses assign one reference or alternative bit to each target atom. The extra K points required by the theorem serve only as source-only dump 37

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

atoms. Fix distinct points x1 , . . . , xK , xD,1 , . . . , xD,K , support both marginals on these 2K points, and define QX ({xk }) =

1 , K

QX ({xD,k }) = 0,

PX ({xk }) =

1 , (1 + κ)K

PX ({xD,k }) =

κ , (1 + κ)K

k = 1, . . . , K.

Thus 1 + χ2 (QX ∥PX ) = 1 + κ, the target law is uniform on the atoms xk , each xD,k is source-only, and
w(xk ) = 1 + χ2 (QX ∥PX ) , w(xD,k ) = 0,
EPX [w] = 1, EPX [w2 ] = 1 + χ2 (QX ∥PX ) .
Consequently, χ2 (QX ∥PX ) = 1 + χ2 (QX ∥PX ) − 1. Let PY0 |X=x be uniform on [−1, 1] for every x ∈ X , and set S ⋆ (x, y) = |y| − (1 − α). This is the equal-tailed oracle CQR score under PY0 |X . Define its two score bands by B0 = [−(1 − α), 0],

B1 = (0, α].

They have masses 1 − α and α, respectively. Coarsen an observation to a label T ∈ {1, . . . , K} × {B0 , B1 , D}: the label is (k, Bb ) when X = xk and S ⋆ (xk , Y ) ∈ Bb , and it is (k, D) when X = xD,k . Thus D records a dump atom, not a score region at xk . ◦ Let PXY = PX ⊗ PY0 |X and Q◦XY = QX ⊗ PY0 |X be the all-reference source and target laws, and ◦

◦

let P and Q denote their coarsenings under T . For each index k, 1−α

◦

P (k, B0 ) =

1 + χ2 (QX ∥PX ) α

◦

P (k, B1 ) = ◦

P (k, D) =

K

, ,

1 + χ2 (QX ∥PX ) K
1 + χ2 (QX ∥PX ) − 1
1 + χ2 (QX ∥PX ) K

(source)

1−α , K α ◦ Q (k, B1 ) = , K ◦ Q (k, D) = 0 ◦

Q (k, B0 ) =

(target)

For τ ∈ {0, 1}K , let PYτ |X use the alternative density (73) at xk exactly when τk = 1 and agree with PY0 |X otherwise. Thus it moves conditional mass ξ from B0 to B1 at precisely the perturbed τ

τ target atoms. Set PXY = PX ⊗ PYτ |X and let P be its coarsening under T . Then

(1 − α) − ξ 1{τk =1}
, 1 + χ2 (QX ∥PX ) K α + ξ 1{τk =1} τ
, P (k, B1 ) = (81) 1 + χ2 (QX ∥PX ) K
1 + χ2 (QX ∥PX ) − 1 τ
P (k, D) = . 1 + χ2 (QX ∥PX ) K

The dump mass ( 1 + χ2 (QX ∥PX ) − 1)/( 1 + χ2 (QX ∥PX ) K) is constant across vertices, and τ

P (k, B0 ) =

◦

τ ≡0

P = P . Since ξ < 12 min{α, 1 − α}, the density calculation following (73) applies to every vertex. Thus all vertex kernels satisfy A 1 with common constants µlow = 1/4, µup = 3/4, and r0 = α/2, while the marginals, target atoms, reference conditional, and S ⋆ do not depend on m. Their coarsened source masses are exactly (81). 38

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Step 2: action and leverage. For a = (a1 , . . . , aK ) ∈ [0, 1]K , the threshold αak at xk admits all of B0 and a fraction ak of B1 . Its conditional coverage is     τ Gτk (ak ) := CovP{S ⋆ ≤αak } (xk ) = (1 − α) − ξ 1{τk =1} +ak α + ξ 1{τk =1} . (82) | | {z } {z } B0 -mass

B1 -mass

Write Gτ (a) := (Gτ1 (a1 ), . . . , GτK (aK )). Set a⋆ := ξ/(α + ξ). Then ( αak , τk = 0, τ Gk (ak ) − (1 − α) = ⋆ (α + ξ)(ak − a ), τk = 1. Thus the zero is 0 at an unperturbed target atom and a⋆ at a perturbed target atom. τ )⊗m and P = (P ◦ )⊗m . Conditional Step 3: per-draw and product χ2 budget. Let Pτ = (PXY ◦ XY on the label T , the full observation (X, Y ) has the same distribution at every vertex: within each score band the density is uniform, and the dump conditional is vertex-independent. Consequently, the one-draw likelihood ratio is a function of T alone, and τ

◦

τ ◦ χ2 (PXY ∥PXY ) = χ2 (P ∥P ).

We therefore compute the divergence on the finite label space and then bound every χ2 (Pτ ∥P◦ ) against this common reference. The per-draw divergence is
2 τ ◦ K X X P (k, ℓ) − P (k, ℓ) τ ◦
2 = . χ P ∥P ◦ P (k, ℓ) k=1 ℓ∈{B ,B ,D} 0

1

By (81) the gaps in coordinate k are τ

◦

τ

◦

P (k, B0 ) − P (k, B0 ) = − P (k, B1 ) − P (k, B1 ) = τ

ξ 1{τk =1}

, 1 + χ2 (QX ∥PX ) K ξ 1{τk =1}
, 1 + χ2 (QX ∥PX ) K

◦

P (k, D) − P (k, D) = 0 , so an unperturbed coordinate contributes zero. A perturbed coordinate contributes

2

2 ξ/( 1 + χ2 (QX ∥PX ) K) ξ/( 1 + χ2 (QX ∥PX ) K)

+ (1 − α)/( 1 + χ2 (QX ∥PX ) K) α/( 1 + χ2 (QX ∥PX ) K)   ξ2 1 1
= + 1 + χ2 (QX ∥PX ) K 1 − α α = Write h(τ ) :=

ξ2
; 1 + χ2 (QX ∥PX ) α(1 − α)K

PK

k=1 τk for the Hamming weight. Therefore, for every vertex τ ∈ {0, 1}

K,

τ ◦
τ ◦ χ2 PXY ∥PXY = χ2 P ∥P =

h(τ ) ξ2
K 1 + χ2 (QX ∥PX ) α(1 − α)

≤

ξ2
. 1 + χ2 (QX ∥PX ) α(1 − α) 39

(83)

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

with equality at the all-alternative vertex τ ≡
1. τ ∥P ◦ ) m − 1. Moreover, (80) gives By (74), χ2 (Pτ ∥P◦ ) = 1 + χ2 (PXY XY K m ξ2
= , 2 16 1 + χ (QX ∥PX ) α(1 − α) and 1 + x ≤ ex together with the radius (83) give, for every τ , χ2 Pτ ∥ P◦

2

◦

τ

≤ em χ (PXY ∥PXY ) − 1 ≤ eK/16 − 1 .

(84)

Step 4: packing, decoding, and action-class transfer. For z = (z1 , . . . , zK ) ∈ RK , define the normalized discrete norm K 1 X ∥z∥1,K := |zk |. K k=1

PK −1

Because QX = K k=1 δxk , any function f satisfies ∥f ∥L1 (QX ) = ∥(f (x1 ), . . . , f (xK ))∥1,K . Fix an atom-specific calibration vector a ∈ [0, 1]K measurable in the sample. Decoding occurs in fraction space: collect the zero-error fractions, 0 at an unperturbed atom and a⋆ at a perturbed atom, into
a⋆ (τ ) := a⋆1 (τ ), . . . , a⋆K (τ ) , a⋆k (τ ) := a⋆ 1{τk =1} ∈ {0, a⋆ } . For any two vertices, K

∥a⋆ (τ ) − a⋆ (τ ′ )∥1,K =

1 X ⋆ a⋆ a 1{τk ̸=τk′ } = dH (τ, τ ′ ) . K K

(85)

k=1

For the packing A of Lemma 23, distinct codewords are therefore separated by at least a⋆ /4. The rounding test rounds a to the nearest of the a⋆ (σ): dev(σ) := ∥a − a⋆ (σ)∥1,K (σ ∈ A),

ψ := arg min dev(σ) . σ∈A

Break ties by a fixed order. If dev(τ ) < a⋆ /8, then for every σ = ̸ τ , the triangle inequality and (85) give dev(σ) ≥ ∥a⋆ (τ ) − a⋆ (σ)∥1,K − dev(τ ) a⋆ a⋆ a⋆ ≥ − dev(τ ) > − 4 4 8 a⋆ = > dev(τ ) . 8 Thus τ is the strict minimizer. Consequently, ψ ̸= τ implies dev(τ ) ≥ a⋆ /8. The fraction and coverage losses satisfy, for every a ∈ [0, 1]K and τ , Gτ (a) − (1 − α)1K 1,K ≥ α ∥a − a⋆ (τ )∥1,K .

(86)

Indeed, the two slopes in Step 2 are α and α + ξ; averaging their coordinatewise bounds gives (86). (K) Since m > m⋆ , (79) gives ξ < 12 min{α, 1 − α} ≤ α, so α + ξ ≤ 2α and α a⋆ =

αξ αξ ξ ≥ = . α+ξ 2α 2

40

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Chaining rounding and transfer on a fixed realization, ψ ̸= τ forces dev(τ ) ≥ a⋆ /8, hence Gτ (a) − (1 − α)1K 1,K ≥ α dev(τ ) ≥

α a⋆ ξ/2 ξ ≥ = . 8 8 16

Thus, for every τ ∈ A, {ψ ̸= τ } ⊆ {∥Gτ (a) − (1 − α)1K ∥1,K ≥ ξ/16}, and under Pτ  ξ  Pτ Gτ (a) − (1 − α)1K 1,K ≥ ≥ Pτ (ψ ̸= τ ) = 1 − Pτ (ψ = τ ) . 16

(87)

The χ2 form of Fano’s inequality is the f (t) = (t − 1)2 case of the f -divergence bound of [17, Example II.5, equation (12), p. 2389]; see also [34]. For probability measures P1 , . . . , PN dominated by a probability measure Q on a common measurable space, and a measurable test ψ with values in {1, . . . , N } and fibers Ej := {z : ψ(z) = j}, it states v u N N u 1 X 1 X 1 Pj (Ej ) ≤ +t 2 χ2 (Pj ∥Q) , (88) N N N j=1

j=1

whose left side is the average probability of correct identification. Indeed, Cauchy–Schwarz gives q Pj (Ej ) − Q(Ej ) ≤ Q(Ej ) χ2 (Pj ∥Q), P and summing over the disjoint fibers, using j Q(Ej ) = 1, proves (88). The radius (83) and budget (84) control all N divergences simultaneously. Apply (88) directly to the full calibration sample, with reference Q = P◦ , hypotheses {Pτ : τ ∈ A}, N := |A| ≥ eK/8 (Lemma 23), and the rounding test ψ: s
1 X 1 1 X 2 Pτ (ψ = τ ) ≤ + χ Pτ ∥ P◦ . 2 N N N τ ∈A

τ ∈A

By the budget (84) each summand is ≤ eK/16 − 1 ≤ eK/16 , so s r r s
1 X 2 N eK/16 eK/16 eK/16 χ Pτ ∥ P◦ ≤ = ≤ = e−K/32 , 2 2 N N N eK/8 τ ∈A

while 1/N ≤ e−K/8 ≤ e−K/32 . Therefore 1 X N

Pτ (ψ = τ ) ≤ 2 e−K/32 .

(89)

τ ∈A

Averaging (87) over A and using (89) gives  ξ  1 X sup Pτ Gτ (a) − (1 − α)1K 1,K ≥ Pτ (ψ = τ ) ≥ 1 − 2e−K/32 . ≥ 1− 16 N τ ∈A τ ∈A

Since A ⊆ {0, 1}K and a was arbitrary, this establishes the Fano bound for atom-specific fractions under the normalized ℓ1 loss. For a realized threshold vector qb1:K , set, for each k,   qbk ≤ 0, 0, ak = qbk /α, 0 < qbk < α,   1, qbk ≥ α. 41

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

When 0 ≤ qbk ≤ α, the threshold ray has coverage (82); outside this window its absolute coverage error dominates that of the clipped fraction. Indeed, for qbk ≤ 0 the coverage is at most 1 − α and is nondecreasing in the threshold, whereas for qbk ≥ α the coverage equals one. Therefore, under every vertex τ , on every realization, and for every p ∈ [1, ∞], τ

∥ CovP{S ⋆ ≤bq} (·) − (1 − α)∥Lp (QX ) ≥ Gτ (a) − (1 − α)1K 1,K . Here the right side is an L1 loss; the inequality follows from the coordinatewise clipping comparison and monotonicity of Lp (QX ) over the probability measure QX . The cube conditionals satisfy A 1, while the marginals, target atoms, reference conditional, and S ⋆ remain fixed. The fraction-space bound therefore transfers to the theorem’s action and supremum classes: inf sup P(PX ⊗PY |X )⊗m ∥ CovP{S ⋆ ≤bq} (·) − (1 − α)∥Lp (QX )

qb1:K PY |X

s 1 ≥ 64

!
1 + χ2 (QX ∥PX ) α(1 − α)K ≥ 1 − 2e−K/32 . m

This completes the proof of Theorem 8.

D.3

Split conformal calibration at each target atom

Proposition 9. Under the assumptions of Theorem 8, consider the source and target marginals, target atoms x1 , . . . , xK , and fixed reference score used in its K-atomic construction. In particular, K

QX =

1 X δxk , K

PX ({xk }) =

k=1

1
, 1 + χ2 (QX ∥PX ) K

k = 1, . . . , K.

For every p ∈ [1, ∞), there is a constant Cp < ∞, depending only on p, such that the rule (32), with qb defined by the canonical extension in Theorem 8, satisfies, for every m ≥ 1, s
n h p io1/p 1 + χ2 (QX ∥PX ) K P sup EDm ∥ Cov{S ⋆ ≤bq} (·) − (1 − α)∥Lp (QX ) ≤ Cp . cal m PY |X Proof. Fix an admissible PY |X and put τ = 1 − α. Throughout the proof, Cp denotes a finite constant depending only on p and may increase from line to line. For each target atom, let Fk (t) = PY |X=xk {S ⋆ (xk , Y ) ≤ t}. The upper interval-mass bound in A 1 and the form of S ⋆ make Fk continuous. Conditional on Nk = n, the probability integral transform therefore gives Fk (b qk ) ∼ Bn,jn ,

jn = ⌈(n + 1)τ ⌉,

where Bn,j has the Beta(j, n + 1 − j) distribution for j ≤ n, and Bn,n+1 = 1. We first record a uniform moment bound. If jn = n + 1, then α < 1/(n + 1) and |Bn,jn − τ |p ≤ (n + 1)−p . If jn ≤ n, set µn = jn /(n + 1). Then 0 ≤ µn − τ < 1/(n + 1). For admissible values of t > 0, the binomial representation of the jn th uniform order statistic and Hoeffding’s inequality give
2 P(Bn,jn ≥ µn + t) = P Bin(n, µn + t) ≤ jn − 1 ≤ e−2nt ,
2 P(Bn,jn ≤ µn − t) = P Bin(n, µn − t) ≥ jn ≤ e−2nt . 42

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Indeed, n(µn + t) − (jn − 1) = nt + 1 − µn ≥ nt and jn − n(µn − t) = nt + µn ≥ nt; outside the admissible range the corresponding tail probability is zero. Hence Z ∞ 2 E|Bn,jn − µn |p ≤ 2p tp−1 e−2nt dt ≤ Cpp n−p/2 . 0

Absorbing the bias |µn − τ | < (n + 1)−1 and treating the case jn = n + 1 above yields E|Bn,jn − τ |p ≤ Cpp (n + 1)−p/2 , n ≥ 0. (90)

Here Nk ∼ Bin(m, 1/( 1 + χ2 (QX ∥PX ) K)). Write λ = m/( 1 + χ2 (QX ∥PX ) K). If λ ≤ 1, then E[(Nk + 1)−p/2 ] ≤ 1 ≤ λ−p/2 . If λ > 1, the binomial lower-tail bound gives P(Nk ≤ λ/2) ≤ e−λ/8 , whence E[(Nk + 1)−p/2 ] ≤ (2/λ)p/2 + e−λ/8 ≤ Cpp λ−p/2 . (91) Since QX is uniform on the target atoms and the values of qb away from them do not contribute to its Lp (QX ) loss, h p i EDm ∥ CovP{S ⋆ ≤bq} −(1 − α)∥Lp (QX ) cal
!p/2 K 1 + χ2 (QX ∥PX ) K 1 X p p EDm = qk ) − τ | ≤ Cp . cal |Fk (b K m k=1

The bound is independent of the admissible kernel. Taking the supremum and the pth root proves the proposition.

E

Additional Details for the Numerical Experiments

Experiments E1 and E2 evaluate the fixed-score calibration benchmarks, whereas E3 evaluates learned CQR under a continuous shift. They therefore refer to distinct statistical experiments. Experiments E1 and E2 use τ = 1 − α and the fixed reference score S ⋆ (x, y) = |y| − (1 − α). The probability integral transform reduces the coverage error to a beta order statistic. Put kn = ⌈(n+1)τ ⌉, let Bn,k ∼ Beta(k, n + 1 − k) for k ≤ n, and set Bn,n+1 = 1. The resulting risks are independent of the admissible conditional kernel.

E.1

Scalar carrier experiment

For the two-point construction QX = δx0 ,

PX =

1 κ δx0 + δx , 1+κ 1+κ D

we have 1 + χ2 (QX ∥PX ) = 1 + κ and N ∼ Bin(m, (1 + κ)−1 ) carrier observations. Writing rn = E|Bn,kn − τ |, with rn = α when kn = n + 1, the exact worst-kernel risk of the weighted rule is m   X m n R(m, κ) = q (1 − q)m−n rn , n

q = (1 + κ)−1 .

n=0

For B ∼ Beta(a, b), µ = a/(a + b), and regularized incomplete beta function Ix (a, b), we evaluate E|B − τ | = 2τ Iτ (a, b) − 2µIτ (a + 1, b) + µ − τ. 43

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

quantity

exact R(m; ∙) finite achievability bound

m=(1 + ∙) R(m; ∙)

10−2 10−3

27

100

10−1

p

exact risk R(m; ∙)

10−1

∙ (color) 3 9

Scaled risk

(b)

0

10−1

100 101 102 103 effective size m=(1 + ∙)

104

10−1

100 101 102 103 effective size m=(1 + ∙)

104

Dependence on miscoverage, x = m=(1 + ∙)

(c) 0.30

scaled risk

p

xR

1

Exact risk and finite bounds, ® = 0:1

(a) 10

Le Cam floor Gaussian limit 0:2394

0.25 0.20 exact at x = 10 4

0.15 0.050

0.075

0.100

0.125 0.150 miscoverage ®

0.175

0.200

0.225

Figure 2: Scalar carrier experiment (E1) at α = 0.1. All curves are exact evaluations of the Binomial–Beta identity for κ ∈ {1, 3, 9, 27}; no simulation is used. E1 takes α = 0.1 and κ ∈ {1, 3, 9, 27}. The blue curves in Figure 2 are exact Binomial–Beta mixtures. When kN = N + 1, the threshold equals +∞ and the conditional error equals α, causing the initial plateau. In effective-size coordinates, the Le Cam lower bound starts at 4(log 2)α(1 − α) m ≥ ≈ 25.0, 1+κ min{α, 1 − α}2 up to the integer ceiling in (28). Moreover, the leading-term calculation in the proof of Proposition 7 gives, as m/(1 + κ) → ∞, r r m 2α(1 − α) R(m, κ) −→ . 1+κ π Panel (c) varies α ∈ {0.05, 0.1, 0.2} at effective size 104 . Constants in the finite and minimax bounds are not optimized.

44

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

E.2

Atomwise carrier experiment

For the K-atomic construction, 1 1 QX ({xk }) = , PX ({xk }) = , K (1 + κ)K

PX ({xD,k }) =

κ . (1 + κ)K

−1 and The atomwise PK rule (32) has rank jn = ⌈(n + 1)τ ⌉ at count n. With q = ((1 + κ)K) ND = m − k=1 Nk ,   κ (N1 , . . . , NK , ND ) ∼ Multinomial m; q, . . . , q, . 1+κ

Conditionally on the counts, the atom-specific errors are independent and d

ek (b qk ) | {Nk = n} = Bn,jn − τ. For 1 ≤ p < ∞, set K

Lp =

1 X |ek (b qk )|p K

!1/p Mp = {ELpp }1/p .

,

k=1

(p) Writing rn = E|Bn,jn − τ |p gives the exact identity

(m   )1/p X m n m−n (p) Mp = q (1 − q) rn . n n=0

The Monte Carlo curves estimate ELp by sampling multinomial counts and conditional beta variables; Jensen’s inequality gives ELp ≤ M
p. Let λ = m/( 1 + χ2 (QX ∥PX ) K), σα2 = α(1 − α), and let Z1 , . . . , ZK be independent standard normal variables. For fixed K, as λ → ∞, conditional independence, the joint convergence Nk /λ → 1 in probability for k = 1, . . . , K, and the beta quantile central limit theorem give √
λ e1 (b q1 ), . . . , eK (b qK ) ⇝ σα (Z1 , . . . , ZK ). The moment bounds (90) and (91), applied at arbitrarily large exponents, give uniform integrability of the normalized losses. Hence, for 1 ≤ p < ∞, !1/p K √ √ 1 X p 1/p p |Zk | . λMp −→ σα {E|Z1 | } , λELp −→ σα E K k=1

For L∞ = maxk |ek (b qk )|, the same argument gives √ λEL∞ −→ σα E max |Zk |. k≤K

Finally, for every fixed ε ∈ (0, 1), Mills’ ratio gives the lower bound below, while the Gaussian moment generating function gives the upper bound: p p (1 − ε) 2 log K{1 − o(1)} ≤ E max |Zk | ≤ 2 log(2K). k≤K

√

Letting ε ↓ 0 yields E maxk≤K |Zk | ∼ 2 log K. E2 takes α = 0.1, κ ∈ {1, 3, 9}, and K ∈ {23, 64, 256}. Gray lines in Figure 3 are exact Mp ; hollow markers estimate ELp from 104 replications per point with seed 20260826. Only counts and beta variables are simulated. Panels (b1)–(b3) show p ∈ {1, 2, 8} and the√finite-K Jensen gap. Panel (c) uses K ∈ {23, 64, 256, 1024}, κ = 3, and λ = 104 to illustrate the log K behavior. Its conclusion is empirical. 45

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

quantity

K (color)

exact Mp

Gaussian reference Fano lower bound

MC mean Lp (95% CI band)

Cellwise risk, p = 2, ® = 0:1

(a)

64

1.0

10−2

p=1 ∙ = 3, ¸ ¼ 10000

p c log K fit MC

p

0.7 100

26 28 210 number of cells K

101 102 103 effective cell size ¸ = m=((1 + ∙)K)

p

p=1

p=2

(b2) 0.30

(b3)

p=8

0.6 0.25

0.20

0.20

0.4

0.15 0.15 0.10

0.2

0.10

p

¸ Mp and MC mean

9

0.8

10−5

exact

3

¸ L1

10−4

(b1) 0.25

1

0.9

10−3

10−6

∙ (style/marker) 256

(c)

10−1

¸ Lp

exact M2 and MC mean L2

23

100 101 102 103 effective cell size ¸

100 101 102 103 effective cell size ¸

100 101 102 103 effective cell size ¸

Figure 3: Atomwise carrier experiment (E2) at α = 0.1. Gray lines are exact moments Mp ; hollow markers are Monte Carlo estimates of ELp from 104 replications with pointwise 95% bands.

E.3

Learned CQR computational details

For E3 in Section 6.2, write µ(x) = sin(2πx) and σ(x) = 1/2 + cos(2πx)/4. For a realized interval C(x) = [ℓC (x), uC (x)], exact Gaussian conditional coverage is     uC (x) − µ(x) ℓC (x) − µ(x) CovC (x) = Φ −Φ , σ(x) σ(x) with the natural values for empty sets and infinite endpoints. Composite trapezoidal quadrature on xj = j/1024, j = 0, . . . , 1024, evaluates all target integrals; Monte Carlo randomness is confined to the source training and calibration folds, and the optimizer stream is fixed across replications. For R = 200 replications and seed 20260826, panel (a) of Figure 1 reports means with pointwise T ± 1.96 se(T b ) intervals, truncated to [0, 1]. Panels (b)–(c) report medians with pointwise empirical [0.025, 0.975]-quantile bands. All realized exact weighted thresholds entering the length and conditional-profile panels are finite.

46

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

F

Neural Network Approximation, Metric Entropy, and Estimation

F.1

Neural network classes and notation

This subsection fixes the pinball-risk, Hölder, and sparse-network notation used in Theorem 10 and its proof. Pinball risk and Hölder class For τ ∈ (0, 1), define
  ρτ (u) := u τ − 1{u<0} , Rτ (f ) := E(X,Y )∼PXY ρτ (Y − f (X)) . The empirical risk Rn,τ (f ) is the sample average of the same loss over Dntr . For β > 0, set kβ := ⌈β⌉−1, the largest integer strictly smaller than β. The Hölder ball of radius H > 0 on Ω ⊂ Rd is ( ) X X |∂ γ f (x) − ∂ γ f (y)| β γ H (Ω, H) := f : Ω → R : ∥∂ f ∥∞ + sup ≤H . (92) β−k x,y∈Ω ∥x − y∥∞ β |γ|≤kβ |γ|=kβ x̸=y

For a function f on X , ∥f ∥∞ denotes the uniform norm supx∈X |f (x)|. Sparse-ReLU class Let σ(t) = max(t, 0) and σv (y) = (σ(y1 − v1 ), . . . , σ(yr − vr ))⊤ . For an architecture (L, p) with p = (p0 , . . . , pL+1 ) ∈ NL+2 , define the network realization recursively by h0 (x) := x,
hℓ (x) := σvℓ Wℓ−1 hℓ−1 (x) , fθ (x) := WL hL (x).

1 ≤ ℓ ≤ L,

(93)

Here Wℓ ∈ Rpℓ+1 ×pℓ , vℓ ∈ Rpℓ , v0 := 0, p0 = d, and pL+1 = 1. Output truncation Define the output truncation by TM (x) := min{max(x, −M ), M }.

(94)

As the Euclidean projection onto [−M, M ], TM is 1-Lipschitz. Consequently, output truncation preserves Lipschitz continuity and does not increase the metric entropy of the class. It also cannot increase pointwise error relative to any function taking values in [−M, M ]. Writing ∥W ∥∞ and ∥W ∥0 for the max-entry norm and number of nonzero entries, define the clipped sparse class by    max ∥W ∥ ∨ |v | ≤ 1,   j ∞ j ∞     0≤j≤L   L F(L, p, s, M ) := TM ◦ fθ : fθ is of the form (93), X . (95)
    ∥W ∥ + |v | ≤ s j 0 j 0     j=0

Every f ∈ F(L, p, s, M ) satisfies ∥f ∥∞ ≤ M .

47

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Schmidt-Hieber architecture for nonparametric rates For input dimension d, smoothness β > 0, and sample size n, we define the Schmidt-Hieber width parameter   Nn := nd/(2β+d) , (96) and the Schmidt-Hieber architectural parameters

LSH (n) := 8 + ⌈log2 n⌉ + 5 1 + ⌈log2 (d ∨ β)⌉ ,

(97a)

WSH (n) := 6(d + ⌈β⌉) Nn ,

(97b)

pSH (n) :=

d, WSH (n), . . . , WSH (n), 1 , | {z }

(97c)

SSH (n) :=

l

(97d)

LSH (n) terms

m 141(d + β + 1)3+d Nn ⌈log2 n⌉ + 6 .

These are the depth, width, and sparsity parameters supplied by [41, Theorem 5] with width parameter Nn and discretization parameter ⌈log2 n⌉. They define the class used in Theorem 10. The resulting clipped class is F(LSH , pSH , SSH , M )(n) := F(LSH (n), pSH (n), SSH (n), M ).

(98)

Its depth is O(log n), its maximal width is O(nd/(2β+d) ), and its sparsity is O(nd/(2β+d) log n). Define the training threshold by l m nSH := (β + 1)2β+d ∨ (Lβ + 1)(2β+d)/d e2β+d ∨ e3(2β+d)/(2β) . (99)

F.2

Lipschitz stability of network parameters

Proposition 24. Fix L ∈ N and an architecture p = (p0 , . . . , pL+1 ) ∈ NL+2 . Let θ(m) = (1) (m) (m) (Wℓ , vℓ )ℓ , m ∈ {1, 2}, have all parameters in [−1, 1]. The corresponding realizations f θ (2) and f θ satisfy (1)

∆W := max ∥Wℓ 0≤ℓ≤L

(1)

(2)

− Wℓ ∥∞ , (2)

∆v := max ∥vℓ − vℓ ∥∞ ,

(100)

1≤ℓ≤L

(1)

(2)

sup |f θ (x) − f θ (x)| ≤ (∆W ∨ ∆v )(L + 1)

x∈[0,1]p0

L Y

(pj + 1).

j=0

The proof needs a bound on the intermediate layers. Lemma 25. Fix L ∈ N and (p0 , . . . , pL ) ∈ NL+1 . For x ∈ [0, 1]p0 , let h0 (x) = x and
hk (x) = σvk Wk−1 hk−1 (x) , k = 1, . . . , L, where Wk−1 ∈ [−1, 1]pk ×pk−1 and vk ∈ [−1, 1]pk . Then, for 1 ≤ k ≤ L, sup ∥hk (x)∥∞ ≤

x∈[0,1]p0

k−1 Y

(pj + 1).

j=0

48

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Proof. For k = 0, ∥h0 (x)∥∞ = ∥x∥∞ ≤ 1, matching the empty product. Suppose for some k ≥ 1 that k−2 Y sup ∥hk−1 (x)∥∞ ≤ Πk−1 , Πk−1 := (pj + 1). x∈[0,1]p0

j=0

For the pre-activation vector zk := Wk−1 hk−1 (x) ∈ Rpk and 1 ≤ j ≤ pk , pk−1

|(zk )j | =

X

(Wk−1 )jl (hk−1 (x))l .

l=1

The weight bound and induction hypothesis imply pk−1

X

|(zk )j | ≤

(101)

|(Wk−1 )jl | |(hk−1 (x))l | ≤ pk−1 Πk−1 . {z } | {z } | l=1 ≤Πk−1

≤1

Since hk (x) = σvk (zk ) and |σ(u)| ≤ |u|, (102)

|(hk (x))j | ≤ |(zk )j − (vk )j | ≤ |(zk )j | + |(vk )j |. Thus ∥vk ∥∞ ≤ 1 and Πk−1 ≥ 1 give ∥hk (x)∥∞ ≤ pk−1 Πk−1 + 1 ≤ (pk−1 + 1)Πk−1 . Iterating from the base case yields ∥hk (x)∥∞ ≤

k−1 Y

(pj + 1).

j=0

(1)

(2)

(1)

(2)

Proof of Proposition 24. Let h0 (x) = h0 (x) = x. For 1 ≤ k ≤ L, define hk and hk recursively as in Lemma 25, using (W (1) , v (1) ) and (W (2) , v (2) ), respectively. Set ε := ∆W ∨ ∆v and Πk := Qk−1 j=0 (pj + 1). Also put (1)

(2)

∆k (x) := ∥hk (x) − hk (x)∥∞ . At the input layer, ∆0 (x) = ∥x − x∥∞ = 0. For 1 ≤ k ≤ L,
(m) (m) (m) hk (x) = σv(m) Wk−1 hk−1 (x) ,

m ∈ {1, 2}.

k

The 1-Lipschitz property of ReLU gives     (1) (1) (2) (2) ∆k (x) = ∥σv(1) Wk−1 hk−1 (x) − σv(2) Wk−1 hk−1 (x) ∥∞ k  k  (1) (1) (1) (2) (2) (2) ≤ ∥ Wk−1 hk−1 (x) − vk − Wk−1 hk−1 (x) − vk ∥∞ (1)

(1)

(2)

(2)

(1)

(2)

(2)

Adding and subtracting Wk−1 hk−1 (x) gives (1)

(1)

(2)

(2)

(1)

(1)

(2)

(1)

(2)

(2)

Wk−1 hk−1 − Wk−1 hk−1 = Wk−1 (hk−1 − hk−1 ) + (Wk−1 − Wk−1 )hk−1 . 49

(104) (105)

≤ ∥Wk−1 hk−1 (x) − Wk−1 hk−1 (x)∥∞ + ∥vk − vk ∥∞ . (1)

(103)

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

For a pout × pin matrix, ∥Ay∥∞ ≤ pin ∥A∥∞ ∥y∥∞ . The parameter bounds therefore imply (1)

(1)

(2)

(2)

∆k (x) ≤ pk−1 ∥Wk−1 ∥∞ ∆k−1 (x) + pk−1 ∥Wk−1 − Wk−1 ∥∞ ∥hk−1 (x)∥∞ + ε {z } | | {z } ≤1 ≤ε   (2) ≤ pk−1 ∆k−1 (x) + ε pk−1 ∥hk−1 (x)∥∞ + 1 .

(106) (107)

(2)

By Lemma 25, ∥hk−1 (x)∥∞ ≤ Πk−1 and pk−1 Πk−1 + 1 ≤ (pk−1 + 1)Πk−1 = Πk . Hence ∆k (x) ≤ pk−1 ∆k−1 (x) + εΠk . Solving this recurrence from ∆0 (x) = 0 yields ∆L (x) ≤ ε

L X





Πk 

pj  .

L−1 Y

k=1

j=k

(1) (1)

(2) (2)

For the final layer, f (1) (x) = WL hL (x) and f (2) (x) = WL hL (x), so (1) (1)

(2) (2)

∥f (1) (x) − f (2) (x)∥∞ = ∥WL hL (x) − WL hL (x)∥∞

(108)

(1) (1) (2) (2) ≤ pL ∥WL ∥∞ ∆L (x) + pL ∥WL − WL ∥∞ ∥hL (x)∥∞

(109)

≤ pL ∆L (x) + εpL ΠL .

(110)

Since pL ΠL ≤ ΠL+1 , summing the layer contributions gives ∥f

(1)

(x) − f

(2)

(x)∥∞ ≤ ε(L + 1)

L Y

(pj + 1).

j=0

Taking the supremum over x proves (100).

F.3

Approximation by ReLU networks

The integer nSH is defined in (99). Its first two terms enforce the width condition of [41, Theorem 5]; the third makes n 7→ n−β/(2β+d) (log n)3/2 non-increasing on [nSH , ∞) and guarantees log n ≥ 1 there. Lemma 26. Fix α ∈ (0, 1), τ ∈ {α/2, 1 − α/2}, d ∈ N, β > 0, and Lβ > 0, and assume B 1 and A 3. For n ≥ nSH , let FnSH be the sparse ReLU class in (98). Then some f˜ ∈ FnSH satisfies ∥f˜ − fτ⋆ ∥∞ ≤ Capp n−β/(2β+d) ,

(111)

Capp := 2(2Lβ + 1) 1 + d2 + β 2 6d + Lβ 3β .

(112)

where Proof. By B 1, fτ⋆ ∈ Hβ (X , Lβ ). For n ≥ nSH , the first two terms of (99) give d/(2β+d)

Nn = ⌈nd/(2β+d) ⌉ ≥ nSH

≥ (β + 1)d ∨ (Lβ + 1)ed .

Applying [41, Theorem 5] with width parameter Nn and depth parameter ⌈log2 n⌉, the condition Nn ≥ (β + 1)d ∨ (Lβ + 1)ed guarantees the existence of a ReLU network f˜SH of depth LSH (n), hidden width WSH (n), sparsity at most SSH (n), and all parameters in [−1, 1], satisfying ∥f˜SH − fτ⋆ ∥∞ ≤ c1 Nn 2−⌈log2 n⌉ + c2 Nn−β/d , 50

(113)

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

with c1 = (2Lβ + 1) 1 + d2 + β 2 6d and c2 = Lβ · 3β . Set f˜ := TM ◦ f˜SH . Membership in F(LSH , pSH , SSH , M )(n) follows from (95) and the preceding parameter and sparsity bounds. Projection onto [−M, M ] fixes fτ⋆ by A 3 and is nonexpansive; hence, for every x ∈ X , f˜(x) − fτ⋆ (x) = TM (f˜SH (x)) − TM (fτ⋆ (x)) ≤ f˜SH (x) − fτ⋆ (x) .

(114)

Taking suprema and using 2−⌈log2 n⌉ ≤ n−1 and Nn ≤ nd/(2β+d) + 1, the first term in (113) satisfies   Nn 2−⌈log2 n⌉ ≤ nd/(2β+d) + 1 n−1 ≤ 2 n−2β/(2β+d) . (115) −β/d

Similarly, for the second term, Nn ≤ n−β/(2β+d) . Since 2β/(2β + d) > β/(2β + d), the first term in (113) is dominated by the second for n ≥ 1. Therefore, ∥f˜ − fτ⋆ ∥∞ ≤ (2c1 + c2 ) n−β/(2β+d) = Capp n−β/(2β+d) .

F.4

(116)

Estimation error

Fix α ∈ (0, 1) and τ ∈ {α/2, 1 − α/2}. Define the pinball Lipschitz and Bernstein constants by V =

2Kτ2 µlow

and Kτ = max{τ, 1 − τ }.

(117)

To separate approximation from estimation, define the best-in-class predictor over Θ by f˜τ = f θ̄τ

where θ̄τ ∈ arg min Rτ (f θ ),

(118)

θ∈Θ

and define its approximation error by Aτ = Rτ (f˜τ ) − Rτ (fτ⋆ ).

(119)

Proposition 27. Fix α ∈ (0, 1) and τ ∈ {α/2, 1 − α/2}. Assume A 3, A 4, and that ∥f θ ∥∞ ≤ M for all θ ∈ Θ. Assume that the population minimizer in (118) exists and that Rn,τ (f θ ) has a measurable b minimizer θbn,τ over Θ, and set fˆn,τ = f θn,τ . Assume that, for every ε > 0, there is a finite ε-net Nε ⊂ Θ such that sup min ∥f ϑ − f θ ∥∞ ≤ ε. (120) θ∈Θ ϑ∈Nε

For every δ ∈ (0, 1) and ε > 0, with probability at least 1 − δ, r (4V + (8/3)K M )u (δ) V (2Aτ + Kτ ε)uε (δ) τ ε Rτ (fˆn,τ ) − Rτ (f˜τ ) ≤ +4 + 4Kτ ε, n n

(121)

where f˜τ is defined in (118) and where we have set uε (δ) = log

 |N |  ε

δ

.

(122)

Following [36, Theorem 1], the proof has three steps: a pointwise Bernstein deviation for a fixed

f θ , Lipschitz stability of the empirical and population risks under the sup-norm approximation in

(120), and an ε-net union bound.

51

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Lemma 28. Fix α ∈ (0, 1) and τ ∈ {α/2, 1 − α/2}, and assume A 3 and 4. For every measurable function f : X → Y, the excess pinball risk satisfies µup µlow ∥f − fτ⋆ ∥2L2 (PX ) ≤ Rτ (f ) − Rτ (fτ⋆ ) ≤ ∥f − fτ⋆ ∥2L2 (PX ) , 2 2

(123)

where fτ⋆ is the conditional τ -quantile function. In this paper, the lemma is used only in the proof of Theorem 10, where (95) clips every competitor to Y = [−M, M ] and A 3 places fτ⋆ in the same interval, so A 4 controls the entire segment between them. Proof. Fix x ∈ X outside a PX -null set on which the conclusions of A 4 hold, and define the conditional risk   rx (t) := E ρτ (Y − t) | X = x , t ∈ R. Set

v := fτ⋆ (x).

u := f (x), Let

Fx (t) := FY |X (t | x),

t ∈ R.

By A 4, the conditional distribution of Y | X = x is absolutely continuous on [−M, M ] with density pY |X (· | x) satisfying µlow ≤ pY |X (y | x) ≤ µup , y ∈ [−M, M ]. Hence Fx is continuous and strictly increasing on [−M, M ]. Since v = fτ⋆ (x) is the conditional τ -quantile, it follows that Fx (v) = τ. (124) By Knight’s identity [22], for every y, u, v ∈ R, ρτ (y − u) − ρτ (y − v) = (u − v) 1{y≤v} − τ +

Z u

1{y≤z} − 1{y≤v} dz.

(125)

Taking the conditional expectation in (125) given X = x and using (124), we obtain Z u

rx (u) − rx (v) = (u − v) Fx (v) − τ + Fx (z) − Fx (v) dz v Z u
= Fx (z) − Fx (v) dz.

(126)

v

v

Case 1: u ≥ v. Since both u and v belong to [−M, M ], for every z ∈ [v, u] we have Z z Fx (z) − Fx (v) = pY |X (t | x) dt. v

Using the density bounds from A 4, µlow (z − v) ≤ Fx (z) − Fx (v) ≤ µup (z − v),

z ∈ [v, u].

Integrating this inequality with respect to z over [v, u] and using (126) gives µup µlow (u − v)2 ≤ rx (u) − rx (v) ≤ (u − v)2 . 2 2 52

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

Case R v 2: u < v.
The opposite deviation is bounded identically: from (126), rx (u) − rx (v) = u Fx (v) − Fx (z) dz, and the same density bounds give µup µlow (v − u)2 ≤ rx (u) − rx (v) ≤ (v − u)2 . 2 2 Combining the two cases, for PX -almost every x,
2
2

µup µlow f (x) − fτ⋆ (x) ≤ rx f (x) − rx fτ⋆ (x) ≤ f (x) − fτ⋆ (x) . 2 2 Finally, taking expectation with respect to PX and using the tower property,     E rX (f (X)) = Rτ (f ), E rX (fτ⋆ (X)) = Rτ (fτ⋆ ), we conclude that µup µlow ∥f − fτ⋆ ∥2L2 (PX ) ≤ Rτ (f ) − Rτ (fτ⋆ ) ≤ ∥f − fτ⋆ ∥2L2 (PX ) . 2 2

For the Bernstein step in Proposition 27, define the excess loss by

ℓf (X, Y ) := ρτ Y − f (X) − ρτ Y − fτ⋆ (X) .

(127)

On the clipped class, it has envelope 2Kτ M ; the next lemma gives the companion second-moment bound E[ℓf (X, Y )2 ] ≤ V E[ℓf (X, Y )] used in Proposition 27. Lemma 29. Fix α ∈ (0, 1) and τ ∈ {α/2, 1 − α/2}, and assume A 3 and 4. For every measurable f : X → Y, the following bound holds     E ℓf (X, Y )2 ≤ V E ℓf (X, Y ) = V (Rτ (f ) − Rτ (fτ⋆ )) , (128) where the constant V is defined in (117). Proof. The pinball loss is Kτ -Lipschitz, where Kτ = max{τ, 1 − τ }. Therefore, almost surely,

|ℓf (X, Y )| = ρτ Y − f (X) − ρτ Y − fτ⋆ (X) ≤ Kτ |f (X) − fτ⋆ (X)|. Squaring and taking expectation gives   E ℓf (X, Y )2 ≤ Kτ2 ∥f − fτ⋆ ∥2L2 (PX ) .

(129)

By the lower bound in Lemma 28, ∥f − fτ⋆ ∥2L2 (PX ) ≤

2 µlow

Rτ (f ) − Rτ (fτ⋆ ) .

Substituting this into (129) and using V = 2Kτ2 /µlow from (117),  
E ℓf (X, Y )2 ≤ V Rτ (f ) − Rτ (fτ⋆ ) . By (127), E[ℓf (X, Y )] = Rτ (f ) − Rτ (fτ⋆ ), which gives the equality in (128). The pointwise Bernstein bound
used in Proposition 27 has centered envelope 4Kτ M and variance bound 2V Rτ (f θ ) − Rτ (f˜τ ) + 2Aτ , with f˜τ as in (118). 53

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Lemma 30. Fix α ∈ (0, 1) and τ ∈ {α/2, 1 − α/2}. Assume A 3, A 4, and that ∥f θ ∥∞ ≤ M for all θ ∈ Θ. Assume that the population minimizer in (118) exists. For every θ ∈ Θ and δ ∈ (0, 1), with probability at least 1 − δ, Rτ (f θ ) − Rτ (f˜τ ) ≤ Rn,τ (f θ ) − Rn,τ (f˜τ ) s
4V Rτ (f θ ) − Rτ (f˜τ ) + 2Aτ log(1/δ) 4Kτ M log(1/δ) + + , (130) n 3n where Aτ is defined in (119). Proof. Fix θ ∈ Θ and define

Zi := ρτ Yi − f θ (Xi ) − ρτ Yi − f˜τ (Xi ) ,

i = 1, . . . , n.

Then Z1 , . . . , Zn are i.i.d., and n

1X Zi = Rn,τ (f θ ) − Rn,τ (f˜τ ), n

E[Z1 ] = Rτ (f θ ) − Rτ (f˜τ ).

(131)

i=1

Because ρτ is Kτ -Lipschitz and both f θ and f˜τ take values in [−M, M ], we have almost surely |Zi | ≤ Kτ f θ (Xi ) − f˜τ (Xi ) ≤ 2Kτ M. Hence |Zi − E[Zi ]| ≤ 4Kτ M

a.s.

(132)

Next we bound the variance. Write

Ai := ρτ Yi − f θ (Xi ) − ρτ Yi − fτ⋆ (Xi ) ,

Bi := ρτ Yi − f˜τ (Xi ) − ρτ Yi − fτ⋆ (Xi ) . Then Zi = Ai − Bi , so by (a − b)2 ≤ 2a2 + 2b2 , Zi2 ≤ 2A2i + 2Bi2 . Taking expectations and applying Lemma 29 first with f = f θ and then with f = f˜τ , we get (133)

E[Zi2 ] ≤ 2E[A2i ] + 2E[Bi2 ] ≤ 2V = 2V

Rτ (f ) − Rτ (fτ⋆ ) + 2V Rτ (f˜τ ) − Rτ (fτ⋆ )
Rτ (f θ ) − Rτ (fτ⋆ ) + Aτ . θ

(134) (135)

Since


Rτ (f θ ) − Rτ (fτ⋆ ) = Rτ (f θ ) − Rτ (f˜τ ) + Rτ (f˜τ ) − Rτ (fτ⋆ ) = Rτ (f θ ) − Rτ (f˜τ ) + Aτ , it follows that

Var(Zi ) ≤ E[Zi2 ] ≤ 2V Rτ (f θ ) − Rτ (f˜τ ) + 2Aτ .

(136)

Apply Bernstein’s inequality [6, Theorem 2.9 and (2.10), pp. 35–36] to the centered variables Wi := E[Zi ] − Zi . 54

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

They are i.i.d., centered, satisfy |Wi | ≤ 4Kτ M by (132), and have variance
Var(Wi ) = Var(Zi ) ≤ 2V Rτ (f θ ) − Rτ (f˜τ ) + 2Aτ by (136). Therefore, with probability at least 1 − δ, r n 1X 2 Var(Z1 ) log(1/δ) 4Kτ M log(1/δ) E[Z1 ] − Zi ≤ + n n 3n i=1 s
4V Rτ (f θ ) − Rτ (f˜τ ) + 2Aτ log(1/δ) 4Kτ M log(1/δ) + . ≤ n 3n

(137) (138)

Substituting the identities in (131) yields (130). Proof of Proposition 27. Apply Lemma 30 at confidence level δ/|Nε |. A union bound gives an event of probability at least 1 − δ on which, for every θ′ ∈ Nε , ′ ′ Rτ (f θ ) − Rτ (f˜τ ) ≤ Rn,τ (f θ ) − Rn,τ (f˜τ ) s
4V Rτ (f θ′ ) − Rτ (f˜τ ) + 2Aτ uε (δ) + n 4Kτ M uε (δ) + . 3n

(139)

Fix θ ∈ Θ. Choose π(θ) ∈ Nε such that ∥f π(θ) − f θ ∥∞ ≤ ε. The preceding Bernstein bound holds at θ′ = π(θ). The pinball loss is Kτ -Lipschitz. Hence |Rτ (f θ ) − Rτ (f π(θ) )| ≤ Kτ ε,

|Rn,τ (f π(θ) ) − Rn,τ (f θ )| ≤ Kτ ε.

(140)

It follows that Rτ (f θ ) − Rτ (f˜τ ) ≤ Rτ (f π(θ) ) − Rτ (f˜τ ) + Kτ ε, Rn,τ (f π(θ) ) − Rn,τ (f˜τ ) ≤ Rn,τ (f θ ) − Rn,τ (f˜τ ) + Kτ ε.

(141)

Substitute these inequalities into the Bernstein bound. Inside the square root, use Rτ (f π(θ) ) ≤ Rτ (f θ ) + Kτ ε. This gives the uniform bound Rτ (f θ ) − Rτ (f˜τ ) ≤ Rn,τ (f θ ) − Rn,τ (f˜τ ) s
4V Rτ (f θ ) − Rτ (f˜τ ) + 2Aτ + Kτ ε uε (δ) 4Kτ M uε (δ) + + 2Kτ ε. (142) + n 3n b b Since θbn,τ minimizes the empirical risk, Rn,τ (f θn,τ ) − Rn,τ (f˜τ ) ≤ 0. Set x = Rτ (f θn,τ ) − Rτ (f˜τ ). Equation (142) gives r 4V (x + 2Aτ + Kτ ε)uε (δ) 4Kτ M uε (δ) x≤ + + 2Kτ ε. (143) n 3n p ε (δ)/n, B = 2A√ τ + Kτ ε, and C = 4Kτ M uε (δ)/(3n) + 2Kτ ε. Then x ≤ √Set A = 2 V u√ √ √ A x + B + C. Use x + B ≤ x + B and A x ≤ x/2 + A2 /2. We obtain √ x ≤ A2 + 2A B + 2C. (144)

55

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

Substitution gives 4V uε (δ) x≤ +4 n

r

V (2Aτ + Kτ ε)uε (δ) 8Kτ M uε (δ) + + 4Kτ ε. n 3n

(145)

This proves the proposition. Corollary 31. Fix α ∈ (0, 1) and τ ∈ {α/2, 1 − α/2}. Assume A 3, A 4, and that ∥f θ ∥∞ ≤ M for all θ ∈ Θ. Assume that the population minimizer in (118) exists and that Rn,τ (f θ ) has a measurable b minimizer θbn,τ over Θ, and set fˆn,τ = f θn,τ . Assume that, for every ε > 0, there is a finite ε-net satisfying (120). Let N1/n be a (1/n)-net satisfying (120) with ε = 1/n, and set Hn = log |N1/n |. Then, for every δ ∈ (0, 1) and n ≥ 1, with probability at least 1 − δ, r Aτ (Hn + log(1/δ)) Hn + log(1/δ) 1 Rτ (fˆn,τ ) − Rτ (f˜τ ) ≤ K1 + K2 + K3 , (146) n n n √ where K1 = 4 2V , K2 = 4V + (8/3)Kτ M + 2, and K3 = 4Kτ + 2V Kτ . Proof. Substitute u1/n (δ) = Hn + log(1/δ) and ε = 1/n in Proposition 27. With A := Hn + log(1/δ), this gives r   V (2Aτ + Kτ /n) A 8 A 4Kτ ˆ ˜ Rτ (fn,τ ) − Rτ (fτ ) ≤ 4 + 4V + Kτ M + . (147) n 3 n n The square-root term satisfies r r r V (2Aτ + Kτ /n) A 2V Aτ A V Kτ A 4 ≤4 +4 n n n n r   √ V Kτ A Aτ A +2 + ≤ 4 2V n n n r √ Aτ A 2V Kτ 2A = 4 2V + + . n n n

(148) (149) (150)

Substitution in (147) gives (146) with the stated constants. Lemma 32. Fix d ∈ N and M > 0. Let F(L, p, s, M ) be the sparse-ReLU network class defined in (95), with depth L ≥ 1, width vector p = (d, W, . . . , W, 1) of constant hidden width W ≥ d, integer sparsity budget s ∈ N, and truncation level M . Then, for any n ≥ 1,

log N n1 , F (L, p, s, M ), ∥ · ∥∞ ≤ s log (2L + 1) W 2 + 1 (151)
+ s log 1 + 2n (L + 1)(W + 1)L+1 . Proof. Parameter support count. Every element of F(L, p, s, M ) is TM ◦ fθ with fθ of the form (93); embed every such raw network into the uniform-width ambient architecture   p̄ = d, W, . . . , W , 1 , | {z } L hidden layers

which contains p. Any such raw network fθ is realized by a parameter vector θ ∈ [−1, 1]P with ∥θ∥0 ≤ s, where P = Wd + (L − 1)W 2 + W + LW ≤ (2L + 1) W 2 , 56

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

e ⊂ [−1, 1]P the set of ambient parameter vectors realizing using d ≤ W and W ≥ 1. Denote by Θ e T := the F(L, p, s, M ). For each T ⊂ {1, . . . , P } with |T | ≤ s, let Θ n raw networks underlying o S e = e : supp(θ) ⊂ T . Since Θ e θ∈Θ T :|T |≤s ΘT , the number of admissible supports is at most

P P (P + 1)s : if s ≤ P , then sk=0 Pk ≤ sk=0 ks P k = (P + 1)s ; if s > P , it is 2P ≤ (P + 1)s . Quantization. Fix ε > 0, set CLip := (L + 1)(W + 1)L+1 and η := ε/CLip , and fix an admissible support T . Partitioning [−1, 1]T into axis-parallel cells of side η yields at most (1 + 2/η)|T | = (1 + 2CLip /ε)|T | e T ̸= ∅, pick one representative θQ ; every θ ∈ Q ∩ Θ e T satisfies cells. For each cell Q with Q ∩ Θ ∥θ − θQ ∥∞ ≤ η. e Proposition 24 applied to p̄ gives Network-output stability. For θ, θ′ ∈ Θ, ′

∥fθ − fθ′ ∥∞ ≤ ∥θ − θ ∥∞ (L + 1)

L Y

(W + 1) ≤ CLip ∥θ − θ′ ∥∞ ,

j=0

e T satisfies ∥fθ − fθ ∥∞ ≤ CLip η = ε, where the last inequality uses d ≤ W. Thus every θ ∈ Q ∩ Θ Q hence ∥TM ◦ fθ − TM ◦ fθQ ∥∞ ≤ ε because TM is 1-Lipschitz. Therefore, for each fixed support T ,  n o   s e T , ∥ · ∥∞ ≤ 1 + 2CLip . N ε, TM ◦ fθ : θ ∈ Θ ε Covering-number multiplication. Multiplying the number of supports by the preceding per-support bound gives  s 2C N (ε, F(L, p, s, M ), ∥ · ∥∞ ) ≤ (P + 1)s 1 + εLip . Taking logs, substituting the bounds on P and CLip , and setting ε = 1/n yields (151). Corollary 33. Fix d ∈ N, β > 0, and M > 0. Let Nn and the Schmidt–Hieber architectural parameters be defined by (96)–(97). Consider the class F(LSH , pSH , SSH , M )(n). Define CL⋆ := 15 (1 + ⌈log2 (d ∨ β)⌉) ,

⋆ CW := 12(d + ⌈β⌉),

CS⋆ := 4512 (d + β + 1)3+d ,

so that, for every n ≥ 2, LSH (n) ≤ CL⋆ log2 n,

⋆ WSH (n) ≤ CW nd/(2β+d) ,

SSH (n) ≤ CS⋆ nd/(2β+d) log2 n.

(152)

Then there exists a constant Cent > 0, depending only on d and β, such that for every n ≥ 2,
(153) log N n1 , F (LSH , pSH , SSH , M )(n), ∥ · ∥∞ ≤ Cent nd/(2β+d) (log2 n)3 . Proof. Set γ := d/(2β + d) ∈ (0, 1) and fix n ≥ 2, so that log2 n ≥ 1 and log n ≤ log2 n. The bounds (152) follow from Nn ≤ 2nγ , ⌈log2 n⌉ + 5 ≤ 7 log2 n, ⌈log2 n⌉ + 6 ≤ 8 log2 n, and ⌈z⌉ ≤ 2z for z ≥ 1, substituted into (97a)–(97d); the constant CL⋆ absorbs the additive 8 in (97a) via log2 n ≥ 1. Applying Lemma 32 with W = WSH (n),

log N n1 , F (LSH , pSH , SSH , M )(n), ∥ · ∥∞ ≤ s log (2L + 1)W 2 + 1 (154)
+ s log 1 + 2n (L + 1)(W + 1)L+1 . 57

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

Using (2L + 1)W 2 + 1 ≤ 4LW 2 and (152),

⋆ 2 ) + log log2 n + 2γ log n ≤ c1 log2 n, log (2L + 1)W 2 + 1 ≤ log 4CL⋆ (CW
⋆ )2 + 3. with c1 := log 4CL⋆ (CW From 1 + 2n(L + 1)(W + 1)L+1 ≤ 4n(L + 1)(W + 1)L+1 , L + 1 ≤ (CL⋆ + 1) log2 n, and log(W + 1) ≤ ⋆ + 1) + log n, log(CW 2
log 1 + 2n(L + 1)(W + 1)L+1 ≤ log 4 + log n + log(L + 1) + (L + 1) log(W + 1) (155) (156)

≤ c2 (log2 n)2 , ⋆ + 1) + 1). with c2 := log 4 + 2 + log(CL⋆ + 1) + (CL⋆ + 1) (log(CW ⋆ γ Multiplying both terms of (154) by s ≤ CS n log2 n and using log2 n ≤ (log2 n)2 ,
log N n1 , F (LSH , pSH , SSH , M )(n), ∥ · ∥∞ ≤ CS⋆ (c1 + c2 ) nγ (log2 n)3

=: Cent nd/(2β+d) (log2 n)3 , with


⋆ 2 Cent := CS⋆ log 4CL⋆ (CW ) + 5 + log(CL⋆ + 1)  ⋆ + (CL⋆ + 1) (log(CW + 1) + 1) + log 4 .

(157)

Explicitly, 
Cent = 4512 (d + β + 1)3+d log 8640 (1 + ⌈log2 (d ∨ β)⌉) (d + ⌈β⌉)2 + 5 + log(16 + 15⌈log2 (d ∨ β)⌉)

(158)

 + (16 + 15⌈log2 (d ∨ β)⌉) (log(12(d + ⌈β⌉) + 1) + 1) + log 4 .

F.5

Proof of Theorem 10

Proof. The proof combines the approximation bound Lemma 26, the entropy bound Corollary 33, and the oracle inequality Corollary 31. We use fen,τ for the raw empirical minimizer throughout. Fix τ ∈ {α/2, 1 − α/2} and let FL,W,S,M,1 := F(LSH (n), pSH (n), SSH (n), M ) denote the Schmidt–Hieber network class with architecture parameters chosen as functions of n. Let fen,τ be the raw empirical minimizer of Theorem 10. Step 1: approximation error By B 1 and Lemma 26, some gτ,n ∈ FL,W,S,M,1 satisfies ∥gτ,n − fτ⋆ ∥∞ ≤ Capp n−β/(2β+d) .

(159)

The parameter set of FL,W,S,M,1 is a finite union of closed subsets of a finite-dimensional cube and is therefore compact. The parameter-stability bound of Proposition 24, output clipping, and Lipschitz continuity of the pinball loss make the population risk continuous on this set. Hence a population minimizer f˜τ ∈ arg minf ∈FL,W,S,M,1 Rτ (f ) exists (see (118)). Both f˜τ and gτ,n depend on 58

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

n through FL,W,S,M,1 , but we suppress this dependence. For every training sample, the empirical pinball risk is continuous in the parameter on the same compact set, so its argmin is nonempty and compact. The empirical risk is jointly measurable in the sample and the parameter. Since ([0, 1]d × [−M, M ])n is a standard Borel space, the measurable maximum theorem [1, Theorem 18.19] yields a measurable exact empirical-risk minimizer. This justifies the measurable ERM used in Theorem 10. By minimality, Rτ (f˜τ ) ≤ Rτ (gτ,n ). Therefore, Aτ := Rτ (f˜τ ) − Rτ (fτ⋆ ) ≤ Rτ (gτ,n ) − Rτ (fτ⋆ )

2 (160) µup Capp µup µup − 2β ∥gτ,n − fτ⋆ ∥2L2 (PX ) ≤ ∥gτ,n − fτ⋆ ∥2∞ ≤ n 2β+d . 2 2 2 The second inequality uses the upper bound in (123); the last uses (159) and ∥h∥L2 (PX ) ≤ ∥h∥∞ .

≤

Step 2: metric entropy Choose a finite 1/n-net N1/n of FL,W,S,M,1 of minimum cardinality in the uniform norm and fix one parameter representative for each network. We use the same symbol for the resulting subset of the parameter set. By Corollary 33 and the change-of-base formula log2 n = (log n)/(log 2),   d 1 Hn := log |N1/n | = log N , FL,W,S,M,1 , ∥ · ∥∞ ≤ C̄ent n 2β+d (log n)3 , (161) n where C̄ent := Cent /(log 2)3 and Cent is the constant of (158). Step 3: rate assembly The boundedness hypothesis of Corollary 31 holds because (95) clips every output to [−M, M ]. Define En (fen,τ ) := Rτ (fen,τ ) − Rτ (fτ⋆ ).
Decomposing this excess risk as En (fen,τ ) = Rτ (fen,τ ) − Rτ (f˜τ ) + Aτ , Corollary 31 yields, with probability at least 1 − δ, r r A H Aτ log(1/δ) Hn log(1/δ) 1 τ n En (fen,τ ) ≤ Aτ + K1 + K1 + K2 + K2 + K3 , (162) n n n n n where K1 , K2 , K3 are p defined in Corollary 31. The bound K1 Aτ log(1/δ)/n ≤ Aτ + (K12 /4) log(1/δ)/n turns (162) into r   Aτ Hn Hn K 2 log(1/δ) K3 + K2 + K2 + 1 + . En (fen,τ ) ≤ 2Aτ + K1 n n 4 n n 2 /2. Equations (160) and (161) give Set Cbias := µup Capp

Aτ ≤ Cbias n−2β/(2β+d) ,

Hn ≤ C̄ent n−2β/(2β+d) (log n)3 . n

Consequently, the cross-term satisfies r Aτ Hn p ≤ Cbias C̄ent n−2β/(2β+d) (log n)3/2 . n

59

(163)

Isaev et al.

Conformalized Quantile Regression under Covariate Shift

For n ≥ 3, (log n)3/2 ≤ (log n)3 and n−1 ≤ n−2β/(2β+d) (log n)3 . Absorbing these terms gives   p En (fen,τ ) ≤ 2Cbias + K1 Cbias C̄ent + K2 C̄ent + K3 | {z } =: Crisk

×n

2β − 2β+d

 K12 log(1/δ) (log n) + K2 + . 4 n | {z } 3



(164)

′ =: Cconf

Finally, the lower bound in (123) and (164) give ∥fen,τ − fτ⋆ ∥2L2 (PX ) ≤

2 µlow

En (fen,τ ).

Taking square roots and using subadditivity yields s s r ′ β 2 C 2 C log(1/δ) risk − ⋆ 3/2 conf ∥fen,τ − fτ ∥L2 (PX ) ≤ n 2β+d (log n) + . µlow µlow n | {z } | {z } = Cconf

= Crate

F.6

(165)

Verification of the CQR assumptions

Under A 3 and 4, the upper density bound gives atomlessness and the all-interval mass bound in A 1. Each side of either oracle quantile has probability at least α/2, so both quantiles lie at distance at least α/(2µup ) from both support boundaries. The lower density bound then gives all four local inequalities in A 1 with r0 = α/(2µup ). For u ∈ (0, 1), define   2M,( ) n < nSH , r ϵ2 (n, u) := (166) log(1/u) −β/(2β+d)  (log n)3/2 + Cconf , n ≥ nSH . min 2M, Crate n n For either τ ∈ {α/2, 1 − α/2} and n ≥ nSH , Theorem 10 at confidence u gives the stochastic bound in the second branch. The deterministic 2M bound holds for every n because the raw minimizer and the oracle quantile take values in [−M, M ]. Thus A 2(p) holds at p = 2 with this radius. Pointwise sorting as in (4) preserves the output range; Lemma 13 gives the contraction used by the generic results.

F.7

Proof of Corollary 11

Proof. Appendix F.6 verifies the CQR assumptions. Under the localization conditions assumed in Corollary 11, apply Proposition 1 and Theorem 2 at p = 2. On the common event An,m (δ), which has probability at least 1 − δ, substitution of (166) at u = δ/4 in (10) and (11) yields (36). Its hidden constant depends only on (α, µlow , µup , β, d, M, Lβ ).

60

Conformalized Quantile Regression under Covariate Shift

F.8

Isaev et al.

Proof of Corollary 12

The specialization uses the rearranged endpoints of (4) and the source L2 rate of Theorem 10. Proof of Corollary 12. The argument in Appendix F.6 verifies the p = 2 instance of A 2(p) for the raw endpoints with ϵ2 of (166); pointwise sorting gives the rearranged fitted pair. At confidence u = δ/4 and for n ≥ nSH , this error is at most r log(4/δ) −β/(2β+d) 3/2 . Crate n (log n) + Cconf n Under the localization conditions assumed in Corollary 12, apply Proposition 4 and Theorem 5 at p = 2 on Aw n,m (δ), the common event defined in Lemma 21, and substitute this rate in (68) and (70). Change of measure and 0 ≤ w ≤ wmax give
∥w∥2L2 (QX ) = EPX [w3 ] ≤ wmax EPX [w2 ] = wmax 1 + χ2 (QX ∥PX ) . Substitution into the exact shifted bounds gives the term qendpoint term, the random-normalization
w −1 2 (2 − α)ηm (δ), and the test-atom term (1 − α)m wmax 1 + χ (QX ∥PX ) in (37).

References [1] Charalambos D. Aliprantis and Kim C. Border. Infinite Dimensional Analysis: A Hitchhiker’s Guide. Springer, Berlin, Heidelberg, 3 edition, 2006. doi: 10.1007/3-540-29587-9. [2] Felipe Areces, Chen Cheng, John Duchi, and Rohith Kuditipudi. Two fundamental limits for uncertainty quantification in predictive inference. In Proceedings of the Thirty-Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 186–218. PMLR, 2024. URL https://proceedings.mlr.press/v247/areces24a.html. [3] Konstantina Bairaktari, Jiayun Wu, and Steven Wu. Kandinsky conformal prediction: Beyond class- and covariate-conditional coverage. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 2581–2602, 2025. URL https://proceedings.mlr.press/v267/bairaktari25a.html. [4] Yajie Bao, Chuchen Zhang, Zhaojun Wang, Haojie Ren, and Changliang Zou. Shape-adaptive conditional calibration for conformal prediction via minimax optimization, 2026. arXiv version 2, revised 12 May 2026. [5] Michael Bian and Rina Foygel Barber. Training-conditional coverage for distribution-free predictive inference. Electronic Journal of Statistics, 17(2):2044–2066, 2023. doi: 10.1214/23-E JS2145. [6] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, Oxford, 2013. ISBN 9780199535255. doi: 10.1093/acprof:oso/9780199535255.001.0001. [7] Olivier Bousquet. A Bennett concentration inequality and its application to suprema of empirical processes. C. R. Math. Acad. Sci. Paris, 334(6):495–500, 2002. doi: 10.1016/S1631-073X(02)0 2292-6. URL https://www.numdam.org/item/CRMATH_2002__334_6_495_0/.

61

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

[8] Victor Chernozhukov, Kaspar Wüthrich, and Yinchu Zhu. Distributional conformal prediction. Proceedings of the National Academy of Sciences, 118(48):e2107794118, 2021. doi: 10.1073/pnas .2107794118. URL https://arxiv.org/abs/1909.07889. [9] Anton Conrad, Rustam Isaev, Denis Belomestny, Eric Moulines, and Sergey Samsonov. Beyond marginal validity: Finite-sample guarantees for localized conformal prediction. arXiv preprint arXiv:2608.06206, 2026. doi: 10.48550/arXiv.2608.06206. Version 1, submitted 6 August 2026. [10] Joseph L. Doob. Stochastic Processes. John Wiley & Sons, New York, 1953. [11] John C. Duchi. Sample-conditional coverage in split-conformal prediction. In Advances in Neural Information Processing Systems, volume 38, 2025. doi: 10.52202/085713-2903. URL https://proceedings.neurips.cc/paper_files/paper/2025/hash/7d83f9e9462c417e208 d55e83a5058a8-Abstract-Conference.html. [12] Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, 27(3):642–669, 1956. doi: 10.1214/aoms/1177728174. [13] Xingdong Feng, Xin He, Yuling Jiao, Lican Kang, and Caixing Wang. Deep nonparametric quantile regression under covariate shift. Journal of Machine Learning Research, 25(385):1–50, 2024. URL https://jmlr.org/papers/v25/24-0906.html. [14] Rina Foygel Barber, Emmanuel J. Candès, Aaditya Ramdas, and Ryan J. Tibshirani. The limits of distribution-free conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2):455–482, 2021. doi: 10.1093/imaiai/iaaa017. URL https: //arxiv.org/abs/1903.04684. [15] Isaac Gibbs, John J. Cherian, and Emmanuel J. Candès. Conformal prediction with conditional guarantees. Journal of the Royal Statistical Society Series B: Statistical Methodology, 87(4): 1100–1126, 2025. doi: 10.1093/jrsssb/qkaf008. [16] Edgar N. Gilbert. A comparison of signalling alphabets. Bell System Technical Journal, 31(3): 504–522, 1952. doi: 10.1002/j.1538-7305.1952.tb01393.x. [17] Adityanand Guntuboyina. Lower bounds for the minimax risk using f -divergences, and applications. IEEE Transactions on Information Theory, 57(4):2386–2399, 2011. doi: 10.1109/TIT.2011.2110791. [18] Michael O. Harding, Vikas Singh, and Kirthevasan Kandasamy. Learning from biased and costly data sources: Minimax-optimal data collection under a budget. arXiv preprint arXiv:2602.17894, 2026. Version 2; COLT 2026; extended abstract in PMLR 336:3184–3184. [19] Rafael Izbicki, Gilson Shimizu, and Rafael B. Stern. CD-split and HPD-split: Efficient conformal regions in high dimensions. Journal of Machine Learning Research, 23(87):1–32, 2022. URL https://jmlr.org/papers/v23/20-797.html. [20] Sunay Joshi, Shayan Kiyani, George J. Pappas, Edgar Dobriban, and Hamed Hassani. Conformal inference under high-dimensional covariate shifts via likelihood-ratio regularization. In Advances in Neural Information Processing Systems, volume 38, 2025. doi: 10.52202/085713-0543. URL https://proceedings.neurips.cc/paper_files/paper/2025/hash/17aa70697d6cd35835f 201c6fb0a2fd5-Abstract-Conference.html. 62

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

[21] Danijel Kivaranovic, Kory D. Johnson, and Hannes Leeb. Adaptive, distribution-free prediction intervals for deep networks. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 4346–4356. PMLR, 2020. URL https://proceedings.mlr.press/v108/kivaranovic 20a.html. [22] Keith Knight. Limiting distributions for L1 regression estimators under general conditions. The Annals of Statistics, 26(2):755–770, 1998. doi: 10.1214/aos/1028144858. [23] P. S. Kostenetskiy, R. A. Chulkevich, and V. I. Kozyrev. HPC resources of the Higher School of Economics. Journal of Physics: Conference Series, 1740(1):012050, 2021. doi: 10.1088/1742-6596/1740/1/012050. [24] Batiste Le Bars and Pierre Humbert. On volume minimization in conformal regression. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 3030–3053. PMLR, 2025. URL https://proceedings.ml r.press/v267/bars25a.html. [25] Jing Lei, Max G’Sell, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry Wasserman. Distribution-free predictive inference for regression. Journal of the American Statistical Association, 113(523):1094–1111, 2018. doi: 10.1080/01621459.2017.1307116. [26] Lihua Lei and Emmanuel J. Candès. Conformal inference of counterfactuals and individual treatment effects. Journal of the Royal Statistical Society Series B, 83(5):911–938, 2021. doi: 10.1111/rssb.12445. [27] Oscar Hernan Madrid Padilla, Wesley Tansey, and Yanzhen Chen. Quantile regression with ReLU networks: Estimators and minimax rates. Journal of Machine Learning Research, 23 (247):1–42, 2022. URL https://jmlr.org/papers/v23/21-0309.html. [28] Pascal Massart. The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality. The Annals of Probability, 18(3):1269–1283, 1990. doi: 10.1214/aop/1176990746. [29] Pascal Massart. Concentration Inequalities and Model Selection, volume 1896 of Lecture Notes in Mathematics. Springer, Berlin, 2007. doi: 10.1007/978-3-540-48503-2. Lectures from the 33rd Summer School on Probability Theory held in Saint-Flour, July 6–23, 2003. [30] Yinjie Min, Liuhua Peng, and Changliang Zou. A unified theory of conditional coverage in conformal prediction with applications. arXiv preprint arXiv:2605.11602, 2026. doi: 10.48550/a rXiv.2605.11602. Version 3, revised 2 June 2026. [31] Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In Proceedings of the 13th European Conference on Machine Learning, ECML’02, pages 345–356, Berlin, Heidelberg, 2002. Springer-Verlag. ISBN 3540440364. doi: 10.1007/3-540-36755-1_29. [32] Sangdon Park, Edgar Dobriban, Insup Lee, and Osbert Bastani. PAC prediction sets under covariate shift. In International Conference on Learning Representations, 2022. URL https: //arxiv.org/abs/2106.09848. [33] Vincent Plassier, Alexander Fishkov, Victor Dheur, Mohsen Guizani, Souhaib Ben Taieb, Maxim Panov, and Eric Moulines. Rectifying conformity scores for better conditional coverage. 63

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 49459–49492. PMLR, 2025. URL https: //proceedings.mlr.press/v267/plassier25a.html. [34] Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge University Press, Cambridge, 1st edition, 2025. [35] Mehrdad Pournaderi and Yu Xiang. Training-conditional coverage bounds under covariate shift. Transactions on Machine Learning Research, 2026. ISSN 2835-8856. URL https: //openreview.net/forum?id=F6hHT3qWxT. [36] Nikita Puchkin, Sergey Samsonov, Denis Belomestny, Eric Moulines, and Alexey Naumov. Rates of convergence for density estimation with generative adversarial networks. Journal of Machine Learning Research, 25(29):1–47, 2024. URL https://www.jmlr.org/papers/v25/23-0062.ht ml. [37] Hongxiang Qiu, Edgar Dobriban, and Eric Tchetgen Tchetgen. Prediction sets adaptive to unknown covariate shift. Journal of the Royal Statistical Society Series B: Statistical Methodology, 85(5):1680–1705, 11 2023. ISSN 1369-7412. doi: 10.1093/jrsssb/qkad069. [38] Thiago R. Ramos, Helton Graziadei, and Luben M. C. Cabezas. Conformal prediction via transported beta laws, 2026. Version 1, submitted 18 May 2026. [39] Yaniv Romano, Evan Patterson, and Emmanuel J. Candès. Conformalized quantile regression. Advances in Neural Information Processing Systems, 32, 2019. URL https://proceedings.ne urips.cc/paper_files/paper/2019/hash/5103c3584b063c431bd1268e9b5e76fb-Abstract. html. [40] Raphael Rossellini, Rina Foygel Barber, and Rebecca Willett. Integrating uncertainty awareness into conformalized quantile regression. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 1540–1548. PMLR, 2024. URL https://proceedings.mlr.press/v238/rossellini2 4a.html. [41] Johannes Schmidt-Hieber. Nonparametric regression using deep neural networks with ReLU activation function. The Annals of Statistics, 48(4):1875–1897, 2020. doi: 10.1214/19-AOS1875. [42] Johannes Schmidt-Hieber and Don Vu. Correction to “nonparametric regression using deep neural networks with ReLU activation function”. The Annals of Statistics, 52(1):413–414, 2024. doi: 10.1214/24-AOS2351. [43] Matteo Sesia and Emmanuel J. Candès. A comparison of some conformal quantile regression methods. Stat, 9:e261, 2020. doi: 10.1002/sta4.261. URL https://arxiv.org/abs/1909.05433. [44] Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research, 9:371–421, 2008. URL https://jmlr.org/papers/v9/shafer08a.html. [45] Guohao Shen, Yuling Jiao, Yuanyuan Lin, Joel L. Horowitz, and Jian Huang. Deep quantile regression: Mitigating the curse of dimensionality through composition. arXiv preprint arXiv:2107.04907, 2021. URL https://arxiv.org/abs/2107.04907.

64

Conformalized Quantile Regression under Covariate Shift

Isaev et al.

[46] Ingo Steinwart and Andreas Christmann. Estimating conditional quantiles with the help of the pinball loss. Bernoulli, 17(1):211–225, 2011. doi: 10.3150/10-BEJ267. URL https: //arxiv.org/abs/1102.2101. [47] Ryan J. Tibshirani, Rina Foygel Barber, Emmanuel J. Candès, and Aaditya Ramdas. Conformal prediction under covariate shift. In Advances in Neural Information Processing Systems, volume 32, pages 2530–2540, 2019. URL https://proceedings.neurips.cc/paper_files/p aper/2019/hash/8fb21ee7a2207526da55a679f0332de2-Abstract.html. [48] Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, 2009. [49] Aad W. van der Vaart. Asymptotic Statistics. Cambridge University Press, 1998. [50] Aad W. van der Vaart and Jon A. Wellner. Weak Convergence and Empirical Processes: With Applications to Statistics. Springer Series in Statistics. Springer, New York, 1996. doi: 10.1007/978-1-4757-2545-2. [51] Rom R. Varshamov. Estimate of the number of signals in error correcting codes. Doklady Akademii Nauk SSSR, 117(5):739–741, 1957. [52] Vladimir Vovk. Conditional validity of inductive conformal predictors. In Proceedings of the Asian Conference on Machine Learning (ACML), volume 25 of Proceedings of Machine Learning Research, pages 475–490, 2012. [53] Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in a Random World. Springer, 2005. [54] James Wang and Surbhi Goel. Weight clipping for robust conformal inference under unbounded covariate shifts, 2026. [55] Yachong Yang, Arun Kumar Kuchibhotla, and Eric Tchetgen Tchetgen. Doubly robust calibration of prediction sets under covariate shift. Journal of the Royal Statistical Society Series B, 86(4): 943–965, 2024. doi: 10.1093/jrsssb/qkae009. [56] Yunzhen Yao, Lie He, and Michael Gastpar. Non-asymptotic analysis of efficiency in conformalized regression. In International Conference on Learning Representations, 2026. URL https://openreview.net/forum?id=UkDte1jM2Q. arXiv version 3, revised 5 March 2026.

65