Conformal Inference under High-Dimensional Covariate Shifts via Likelihood-Ratio Regularization
Authors: Sunay Joshi
Shayan Kiyani
George J. Pappas
Edgar Dobriban
Hamed Hassani
Venue: NeurIPS 2025 poster ()
Keywords: conformal prediction
covariate shift
uncertainty quantification
distribution shift
distribution-free prediction
prediction sets
high-dimensional data
Primary area: theory

Abstract: We consider the problem of conformal prediction under covariate shift. Given labeled data from a source domain and unlabeled data from a covariate shifted target domain, we seek to construct prediction sets with valid marginal coverage in the target domain. Most existing methods require estimating the unknown likelihood ratio function, which can be prohibitive for high-dimensional data such as images. To address this challenge, we introduce the likelihood ratio regularized quantile regression (LR-QR) algorithm, which combines the pinball loss with a novel choice of regularization in order to construct a threshold function without directly estimating the unknown likelihood ratio. We show that the LR-QR method has coverage at the desired level in the target domain, up to a small error term that we can control. Our proofs draw on a novel analysis of coverage via stability bounds from learning theory. Our experiments demonstrate that the LR-QR algorithm outperforms existing methods on high-dimensional prediction tasks, including a regression task for the Communities and Crime dataset, an image classification task from the WILDS repository, and an LLM question-answering task on the MMLU benchmark.

Conformal Inference under High-Dimensional Covariate Shifts via Likelihood-Ratio Regularization
Sunay Joshi" University of Pennsylvania sunayj@sas.. upenn. edu
Shayan Kiyani' University of Pennsylvania shayankeseas. upenn edu
George Pappas University of Pennsylvania pappasgSseas. upenn edu edu
Edgar Dobriban
University of Pennsylvania
dobriban@wharton upenn. edu
Hamed Hassani
University of Pennsylvania hassani@seas upenn. edu
Abstract
We consider the problem of conformal prediction under covariate shift. Given labeled data from a source domain and unlabeled data from a covariate shifted target domain, seek to construct prediction sets with valid marginal coverage in the target domain. Most existing methods require estimating the unknown likelihood ratio function, which be prohibitive for high-dimensional data such as images. To address this challenge, we introduce the likelihood ratio regularized quantile regression (LR-QR) algorithm, which combines the pinball loss with novel choice of regularization in order to construct a threshold function without directly estimating the unknown likelihood ratio. We show that the LR-QR method has coverage at the desired level in the target domain, up to a small error term that we can control. Our proofs draw on novel analysis of coverage from learning theory. Our experiments demonstrate that the LR-QU algorithm outperforms existing methods on high-dimensional prediction tasks. including a regression task for the Communities and Crime dataset, an image classification task from the WILDS repository, and an L.MM question-anss answering task on the MMLU benchmark.
stability bounds
Introduction
Conformal prediction is a framework to construct distribution- prediction sets for black-box predictive models [c.g., |5| 660 61 etc]. Given pretrained prediction model f X - Y mapping features z E to labels y E y, and ni calibration datapoints (X,, , Y.) : E [na] sampled i.i.d. from calibration distribution P1, we seek to construct prediction set C(X,ss)) S ) for test features X sampled from a marginal test distribution Pz.x. We aim to cover the true label Yest with probability at least
The left-hand side of this inequality the marginal coverage of the prediction set C. averaged over the randomness of both the calibration datapoints and the test datapoint (Xiest Yıea) Pa. In the case that the calibration and test distributions coincide (P1 = P22), there are numerous conformal prediction algorithms that
for some (0, 1): that is, P(Y E C(Xusa)
Equal Contribution. Correspondence to: sunayj@sas upenn edu, shayank#seas. upenn. edu.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

construct distribution-Fe free prediction sets with valid marginal coverage; e.g., split and full conformal prediction [e.g.. 29 36].
However, in practice, it is often the case that test data is sampled from a different distribution than calibration data. This general phenomenon is known as distribution shift [e.g.. AI [52] One particularly common type of distribution shift is covariate shift [50], where the conditional distribution of X stays fixed, but the marginal distribution of features changes from calibration to test time. For instance, in the setting of image classification for autonomous vehicles, the calibration and test data might have been collected under different weather conditions [25 65
Under covariate shift,
ordinary conformal prediction algorithms may lose coverage.
Recently, a number of methods have been proposed to adapt conformal prediction to covariate shift, Most existing approaches attempt to estimate the likelihood ratio function r X RR, defined r(x:)= = (d / /dfP1,x (a:) for all E X, where Pi,,x denotes the marginal distribution of IP; over the features. One can construct an estimate i of the likelihood ratio one has access to additional unlabeled datapoints sampled i.idd from the test distribution Pz. Methods for likelihood ratio estimation include using Bayes' rule to express it as a ratio of classifiers [12 40) and domain adaptation 13 37 However, such estimates may be inaccurate for high-dimensional data. This error propagates to the coverage of the resulting conformal predictor, and the prediction sets may no longer attain the nominal coverage level. Thus, it is natural ask the following question: Can one design a conformal prediction algorithm that attains valid coverage in the target domain, without estimating the entire function r?
e.g., in 15 19 37 38
40
55
64]
In this paper, we present a method that answers this question in the affirmative. We construct our prediction sets by introducing and solving a regularized quantile regression problem, which combines the pinball loss with a novel data-dependent regularization term that can be computed from one- dimensional projections of the likelihood ratio r. Crucially, the objective function can be estimated at the parametric rate, with only a mild dependence on the dimension of the feature space. This regularization is specifically chosen to ensure that the first order conditions of the pinball loss lead to coverage at test- sitettmm.. Geometrically, the regularization aligns the selected threshold function with the true likelihood ratio r. The resulting method, which we call likelihood ratio regularized quantile regression (LR-QR), outperforms existing methods on high- -igh-dimensoonal datasets with covariate shift.
Our contributions include the following:
We propose the LR-QR algorithm, which constructs a conformal predictor that adapts to covariate shift without directly estimating the likelihood ratio.
We show that the minimizers of the population LR-QR objective have coverage in the test distribution. We also show that the minimizers of the empirical LR-QR objective lead to coverage up to a small error term that we can control. Our theoretical results draw on a novel analysis of coverage via stability bounds from learning theory.
We demonstrate the effectiveness of the LR-QR algorithm under covariate shift, including the Communities and Crime dataset, the RxRx1 dataset from the WILDS repository, and the MMLU benchmark. Here, we crucially leverage our theory by choosing the regularization parameter proportional to the theoretically optimal value.
dighedimmnsional datasets
1.1 Related work
Here we only list prior work most closely related to our method; we provide more references in Appendix C The early ideas of conformal prediction were developed in Saunders et al. 45). Vovk
et al. [61]. With the rise of machine learning, conformal prediction has emerged as a widely
used framework for constructing prediction sets [c.g.. 33, 58 59). Classical conformal prediction guarantees validity when the calibration and test data are drawn from the same distribution. In contrast, when there is distribution shift between the calibration and test data [e.g.. 50 52, 54], coverage may not hold. Covariate shift is a type of dataset shift that arises in many settings, e.g., when predicting disease risk for individuals whose features may evolve over time, while the outcome distribution conditioned on the features remains stable [1
Numerous works have addressed conformal prediction under distribution shift 37 38 40
51
55
For example, Tibshirani et al. (55) investigated conformal prediction under covariate shift, assuming the likelihood ratio between source and target covariates is known. Lei and Candès [32 allowed

---

the likelihood ratio to be estimated. Park et al. [37] developed prediction sets with calibration-set conditional (PAC) property under covariate shift. Qiu al. [40], Yang et al. [64] developed prediction sets with asymptotic coverage that are doubly robust in the sense that their coverage error is bounded by the product of the estimation errors of the quantile function of the score and the likelihood ratio.
Cauchois et al. 7 construct prediction sets based on distributionally robust optimization. In contrast, our method entirely avoids estimating the likelihood ratio function.
To achieve coverage under a predefined set of covariate shifts, Gibbs et al. 15 develop an approach based on minimizing the quantile loss over linear hypothesis class. We build on their quantile regression framework, but develop novel regularization scheme that allows us to effectively optimize over a data-driven class, adaptive the unknown shift r. A similar regularization is used [66]. which performs supervised learning under covariate shift by minimizing an upper bound of the test risk. However, when one sets the loss function to equal the pinball loss, minimizing the objective in [66) is not guaranteed to provide coverage at test-time, whereas our construction has asymptotically valid coverage.
2 Problem Formulation
Preliminaries and notations. For E (0, 1), the quantile loss la is defined for all c, E IR as
(1 - as if 2c, ta (c, = a(c- 8) if <c
Let the source or calibration distribution be denoted P1 = PL. x Py where F1,x is the marginal distribution of IP, over features. Let the target test distribution be denoted IP = P2.x x Pyjx. where 12,,x is the marginal distribution of IP2 over features. Since the conditional distribution of labels given features Fy is common to P1 and P2, the test distribution is covariate shifted version of the calibration distribution. Let IE, denote the expectation over P,, i 1,2, Let + r(x) denote the unknown likelihood ratio function.
We consider both discrete and continuous label spaces V When y'= R. prediction sets correspond 2n has marginal (1 -ooerraaeee in a. Let S (x, + S(z, v) denote the nonconformity score associated to a pair (æ. y) E X' x V. Given threshold function q X - IR we consider the corresponding prediction set C : + 2 given by C(x) = {y E ) S(x. y) < g(z)} } for all X. Thus a threshold function q yields a conformal predictor with marginal (1 ax) -oveeraee in the test domain if (P([ Y) < g(X)] > 1- a. Note that the use of an adaptive threshold function common in the conformal prediction literature, going back to (55) We assume that a & 0.5. For our theory, we consider [0, 1j-valued scores; however, in Appendix
to prediction intervals. Recall that a prediction set C:
the test domain if P2 [Y E C()) >
O we comment on conditions
under which unbounded scores can be handled.
In this paper, linear hypothesis class refers to a linear subspace of functions from X' + R that are square-integrable with respect to Pı,x An example is the space of functions representable by a pretrained model with a scalar read-out layer. If + X' + Rd denotes the last hidden-layer feature map of the pretrained model, where +b = (ø1..... dd) for di : X' - R for all i E [d]. then the linear class of functions representable by the network is given by (17, Φ) 7 E IRd), where (s +) is the & inner product on [
Problem statement. We observe n1 labeled calibration (or, source) datapoints ((,,, Yi) : [m]]} drawn i.i.d. from the source distribution Pr, and an additional ny unlabeled calibration datapoints S3. We also have n12 unlabeled (target) datapoints S2 drawn i.i.d. from the target distribution Pz. Given a (0, 1), our goal to construct threshold function q : X -> R that achieves marginal (1 - coveraae in the test domain: P2 P2(S(X,Y) & ((X) > -
3 Algorithmic Principles
Here we present the intuition behind our approach. Our goal is to construct a prediction set of the form C(r) = (y E ) S(I, v) & {(x)). where q should be close to conditional quantile of S given X x. The quantile loss la is designed such that for any random variable Z, the minimizers of the objective
(K,,,, Z) are the (1 ah quantiles of Z. This has motivated prior work
3

---

13 22 where the authors minimize the objective h + S(X, for h in some linear hypothesis class H. At minimizer h" the derivatives in all directions g E H. should be zero. Since the derivative of the pinball loss with respect to its first argument is given by
(c,a s) = (11 - a) > c) + alfs & c) 1/s & cl (1 aa);
the chain rule implies that the directional derivative of h - Bf, (h (XX), in the direction equals
a
+ +x())) = E
(h(X) + (L.
De ==
dE
c=0
= _ & h(x) - - (1-a))],
where in the first step we interchanged derivative and expectation, applied the chain rule, and evaluated at = 0, and in the second step we used the formula for the derivative of the pinball loss. Setting this equal to zero, if g takes the form g g(x) = dQxx / /dPP,x (x) for some distribution Qx. ther this
equality reads Eg [1 (X(X Y) & ht (X))
(1 a)] O, which can be viewed exact coverage
under the covariate shift induced by for the prediction set x H> {y E y S(z y) < h" (x)).. In
other words, if the test distribution is Q Qx Pyjx, then have the exact coverage result
Eq X) & (x)]] = Q) < = a.
Therefore, if the hypothesis class H. is large enough to include the true likelihood ratio r = d22,x ,,x,
1,x, then the threshold function h" attains valid coverage in the test domain P2, as desired.
3.1 Our approach
An adaptive choice of the hypothesis class. The above approach requires special assumptions on the hypothesis class H. The choice of the hypothesis class poses a challenge in practice: if H. is too small, then coverage may fail, while if H. is too large, then finite-sample performance may suffer due large estimation errors.
To address this challenge, our idea is to choose H. adaptively. We start by considering the class of hypotheses h that close to the true likelihood ratio as measured by E (h)()) r(X))² being small. By our remarks above, if we minimize (h(X). S(X, Y)] for restricted to this set, we obtain a threshold function with valid coverage under the covariate shift
Removing the explicit dependence on the likelihood ratio. The quantity [[(()X)- - -(()))))rxx)]] depends on the unknown However, we can expand this to obtain
E [((()) E, [A(x)*] + E + [x))
-
The term E, [r[x]]] does not depend on the optimization variable h, so is enough to consider the first two terms. Due to the change-of-measure identity E, (xX))(X)) [x)], the sum of these terms equals
E, [1())] +
= [4()] + -2(-2h(X))
A key observation is that neither of the terms EE ( or R2 22()2 explicitly involve and thus they can be estimated by sample averages over the source and target data, respectively. Thus, minimize [e, (X))), (X),),(C S(X, Y)) over h H while keeping EE, [f([)]]] + Ezl- (xl-
bounded. The threshold h² will have valid coverage under the covariate shift r.
Introducing a normalizing scalar. We also need to make sure that h is valid likelihood ratio under dPi.x, of the form (zx) = dQx i, (x) for some distribution Qx This imposes the constraint [ h((r)dPi,xx( (1) = 1, which can be equivalently achieved for any non non-negative h by scaling it with an appropriate scalar B. In our analysis, it turns out to be convenient to use the optimization variable 3h and consider the class of functions h such that EE [(hh(X) r(X))² is bounded for some scalar e R. By the above discussion, the term EE [r X)² immaterial and it sufficient to impose the constraint that min (())) + E2 2-1hhhhh2aa (X)) is bounded.
"This holds due to the change of measure identity Es (dQ(((((()) M(X)] = [x]4((X)] for all integrable functions h.

---

Algorithm Likelihood-ratio regularized quantile regression
Input: nı labeled source datapoints, n2 unlabeled target datapoints, fi unlabeled source datapoints I: Compute scores S = S( y:) for E [m1]
2: Solve (h, () E arg simming,,.eee la ( , S(X, Y))] + > - 1E21-23h(X). -E3-1-3h) where E1, Eg, Bg denote expectations over the source, unlabeled target, and unlabeled source data;
Return: Prediction set ((z) fy y ((, < h(x)} with asymptotic 1 coverage in the target distribution
Replacing the constraint with a regularization. Instead of imposing a constraint on minsen (E, (x3)(x))2 Fggl-)(((()))) we this term regularizer. Given regularization strength > 0, we can solve
min bEH
Bi (x( V)) + Amm (T, (3P R2[ (()))))
PER
Since the first term does not depend on 8, this is equivalent to the joint optimization problem
min bEH.
(La(h, = E, (I)(,(((XX,,,((, Y)) X(E, (f -E2228(())))) (LR-QR)
3.2 Algorithm: likelihood ratio regularized quantile regression
solve an empirical version this objective. We use our labeled source data {(x,, Y,) : [m1]] to estimate E, [h( S(X, Y))], our additional unlabeled source data Sş to estimate E2 [x and our unlabeled target data S2 estimate 1Eg(-23h(XX) Letting E1, E2, and É& denote empirical expectations over {Xx,, Yi) : i E [mi]}. S2, and S3. respectively, we then solve the following empirical likelihood ratio regularized quantile regression problem, for À >
(h, 3) arg min hEH.SER {ix(h, = (,, (,00,,,))--((1,,,,,,,,))),,11,11 -,,-,)
XB2[23M(X3]}
(Fappirical-LRR-RR
Our proposed threshold is g h. See Algorithm In the following section, justify this algorithm through a novel theoretical analysis of the test-time coverage.
4 Theoretical Results
4.1 Infinite sample setting
We first consider the infinite sample or "population" setting, characterizing the solutions the LR-QR problem from (LR-QR) in an idealized scenario where the exact values of the expectations E1, Ex, can be calculated. In this case, will show that if the hypothesis class H linear and contains the true likelihood ratio r. then the optimizer achieves valid coverage in the test domain. Let Ex be the projection of onto H. the Hilbert space induced by the inner product (f.g) E, The key step is the result below, which characterizes coverage weighted by T*-
Proposition 4.1. Let H. be linear hypothesis class consisting of square--nnen intter-btteeaalee functions with respect to FL.x- Then under regularity conditions specified Appendix (the conditions of Lemma L.3. if (h*, (8*) = (ha. (3) is a minimizer of the objective in Equation (LRQQR) with regularization strength
0, then we have
< (X))
The proof is given in Appendix ! As consequence of Proposition 4.1 if H contains the true likelihood ratio r, so that I'H r, then in the intinite sample setting, the LR- R-Q threshold function h" attains valid coverage test-time:
E, (X & (X)]] [t (X(,)YY < x*)(
Explicitly, given orthonormal basis (yI,.... saa) for H. we have (rmiinppipp
5

---

However, in practice, we can only optimize over snite-dimensional hypothesis classes, and as a result we must control the effect of mis-specii H. If r not in H. we can derive a lower bound on the coverage as follows. First, write
[x) Y) & h" (X)]]
E1
Y) & h((O]] +
-
(X)]]]]
By Proposition 4. the first term on the right-hand side is at least 1 - Since the random variable [ Y) & h" (X)] is {0, 13-vauudd the second term on the right- side is at least -En [r(X) - TH (X))+) where (z)+ max(0, for R. We set our threshold function q to
equal h", , so that our conformal prediction sets equal (x) = ty E y S(x, 8) & (x)) for all
E X. Thus, we have the lower bound
F2|Y (X)] = E, (xx)) (X)( > (1-a) a) - E [((()) - - (X))+}. Geometrically, this coverage gap is the result of restricting to H. This error decreases if H is made larger, but in the finite sample setting, this comes the risk of overfitting.
4.2 Finite sample setting
From the analysis of the infinite sample regime, it is clear that if the hypothesis class H. is made larger, the test-time coverage of the population level LR-QR threshold function h moves closer to the nominal value. However, in the finite sample setting, optimizing over a larger hypoth- esis class also presents the risk of overfitting. By tuning the regularization parameter X, we are trading off the estimation error incurred for the first term of Equation (LR-QR), namely Y) and the error incurred for the second and third terms of Equation (LR.) QR). namely A(E3 Ex) (x))(+) + E2)( 1-)3 (x)( Heuristically, for a fixed h. the former should be proportional to 1/ /ni, and the latter should be proportional X(1/ /na + 1/222)) Thus, we pick À to make these two errors of equal order, it will be proportional to v /nn2 + na)/n11
(IE, (M(X),
Put differently, in order to ensure that the Empirical LR-QR threshold h from Equation Empirical LR-QR has valid test coverage, one must choose the regularization À based on the relative amount of labeled and unlabeled data. The unlabeled datapoints carry information about the covariate shift r, because r depends only on the distribution of the features. The labeled datapoints provide information about the conditional (1 - a) -quunttile function q1-a. which depends only on the conditional distribution of S| When is large, our optimization problem places more weight on approximating r (the minimizer of E, [( [(5h(X) (X) - r ()) in Bh), and if À is small, we instead aim to approximate 91-a (the minimizer of E, (h().. Y))] in h). Therefore, if the number of unlabeled datapoints (n2 + n2)) is large compared to the number of labeled datapoints (n1). our data contains much more information about the covariate shift r, and we should set À to be large. If instead n is very large, the quantile function -1-o can be well-approximated from the labeled calibration datapoints, and we set to be close to zero. the theoretical results, we make this intuition precise.
In order to facilitate our theoretical analysis in the finite sample setting, we consider constrained versions of Equation (LR-QR) and Equation (Empirical--R-QR)) Fix a collection & (ø1...., oa) of d basis functions, where Φ; X > R for i [d]. Let I [3min 3max] C IR be an interval with Amin > O. Let Hp = {(>, b) : 1/ll2 & B oc) be the B-ball centered at the origin in the linear hypothesis class spanned by føi...., Φ2). We equip Hy with the norm ||A|| = || for h = (1, T).
At the population level, consider the following constrained LR-QR problem: (h*, arg minkeH .EE La B). Also consider the following empirical constrained LR-QR problen
(h. B) E arg min hEHn.BET
Lx B).
We begin by bounding the generalization error of an ERM (h, 8) computed via Equation 2
Theorem 4.2 (Suboptimality gap of ERM for likelihood ratio regularized quantile regression). Under the regularity conditions specified in Appendix E and for appropriate choices of the optimization
hyperparametert"" for sufficiently large n1, n2,, n33 with probability at least 1 - 8, any optimizer
*For brevity, this notation overloads the definition of (h, 3) from LEppirica-LRR-QP From now on. (hi 3)
will refer to the definition from (2) and the from (Empirical -LR QR) will not be used again.
'Specifically, suppose that 3min & Bewerr Buax 30 Bunger. and B 3 Bupper. where the positive scalars Browers the Appendix, and depend on the data distribution and the choice of basis functions, but not the data, the sample sizes, or the regularization parameter A.
Supger. and Bupper are defined in Lemma

---

() of the empirical constrained LR-QR objective from ② with regularization strength X >> 0 has suboptimality gap Lx B) Lx(h" , with respect to the population risk [R-QR) bounded by
Egen == c/= + 1/ng + é /////i + e"
1 Vmm,
and c, c, c" are positive scalars that do not depend on
The proof is in Appendix ! on the order of
The generalization error Egen is minimized for an optimal regularization
X x m1 1/3 (1/n² + 1/mg) 1/3
(3)
which yields optimized upper bound of order Egen O (n (1/nz + 1/na)'/ + 111//// /mi) As
can be seen from Appendix F C, d', c" depend only polynomially on the radius B.
we have the following lower bound the excess marginal coverage of our ERM threshold h in the covariate shifted domain. Let rn denote the projection of onto the closed convex set Hg in the Hilbert space induced by the inner product (S, = E [Sg]-
As corollary of Theorem
Theorem 4.3 (Main result: Coverage under covariate shift). Under the same conditions as Theo-
rem 4.2 consider the RR-QR optimizers h and 1 from (2) with regularization strength X >> Given any for sufficiently large ni, 122, Tig, we have with probability at least 1 - 8 that
- P2 Y E 0(x) > (1 (1-a) a) + 23 ((rl(((((())))))) 3h(x)) Eco - (1 (--))B - [x())]],
where Ecov == A (1/n22 + 1/Tx)//4 x (1m) + X 1 //n onto HB, and A, A' are positive scalars that do not depend X.
1/4 TB denotes the projection of
The proof is in Appendix K This result states that our LR-QR method has nearly valid coverage at level - a under covariate shift, up to small error terms that we can control. The quantity & vanishes as we collect more data. The term E, [[r(X) -ry( (X)] captures the level of mis-specification by not including the true likelihood ratio function in our hypothesis class H.g. This can be decreased by making the hypothesis class HB larger. Of course, this will also increase the size of the terms A, A' in our coverage error, but in our theory we show that the dependence is mild. Indeed, the terms depend only on few geometric properties of Ry: they depend polynomially on the radius B, on the eigenvalues of the sample covariance matrix of the basis ( under the source distribution, and on a quantitative measure of linear dependence of the features; but not explicitly on the dimension of the basis. We also note that the dimension of the feature space dim( (X) does not appear in our results; only dH) affects our bounds.
We highlight the term XB (rB(((((()) - (h())) which an error term relating the projected like- lihood ratio FB to the LR-QR solution 3h. Crucially, this term is a non non-negative quantity multiplied by X, and for appropriate À it may counteract in part the coverage error loss. Consistent with the above observations, we find empirically that choosing small nonzero regularization parameters improves coverage. Moreover, find that choosing the regularization parameter to be the order of the optimal value for Ecoy is suitable choice across a range of experiments.
Our proofs are quite involved and require a number of delicate arguments. Crucially, they draw novel unalysis of coverage via stability bounds from learning theory. Existing stability results cannot directly be applied, due the optimal regularization tends to zero as the sample size goes to infinity, but this is not the case here. To overeome this challenge, argument, and we show that the values of L at the minimizers of L and L are close by introducing intermediate losses that sequentially swap out empirical expectations E, E,g, Eg with their population counterparts. We then leverage the smoothness of L, to derive that the gradient of L at (8, h) is small. Finally, we show that small gradient implies the desired small coverage gap.
use of data-dependent regularizer. For instance, in classical settings,
combine stability bounds [48 49] with novel conditioning
Thee probability P2 [ E(()) is over (X, Y) ~ P2, conditional on É.
7

---

1.00
0.55
0.95
0.45
Coverage
0.85
0.40
0.80
0.75
0.30
0.70
0.65
0.25
0.60
0.20
Black
White
Asian
Hispanic
Black
White
Asian
Hispanic
Features
Features
Nominal Coverage
Welghted-CP
2R-CP
DR-iso
LR-QR
Split conformal
DRO-CP
Robust-CP
Figure 1: (Left) Coverage. (Right) Average prediction set size on the Communities and Crime dataset.
5 Experiments
We compare method with the following baselines: (1) Split/inductive conformal prediction
36] (2) Weighted-CP: Weighted conformal prediction [55]: (3) 2R-CP: The doubly robust method
from Yang al. [64]; (4) DRO-CP: Distributionally robust optimization 77: (5) DR-iso: Isotonic
distributionally robust optimization
[9]; (6) Robust-CP: Robust weighted conformal prediction [
5.1 Choosing the Regularization Parameter
Equation (3) suggests an optimal choice of the regularization parameter À in the LR-QR algorithm. Guided by this, we form a uniform grid of size ten from X /10 to A". We then perform fhree-fold cross-validation over the combined calibration and unlabeled target datasets (without using any labeled test data) follows: we train the LR-QR threshold for each X, and compute as a validation measure the (e-norm of the gradient of the LR-QR objective on the held-out fold. We pick with the smallest average validation measure across all folds.
This validation measure motivated by our algorithmic development: the first-order conditions of the LR-QR objective play fundamental role in ensuring valid coverage in the test domain. While model is trained to satisfy these conditions on the observed data, we seek to ensure this property generalizes well to unseen data. Thus, our selection criterion is based on two key observations: (1) small gradient of the LR-QR objective implies reliable coverage, and (2) the regularization parameter A balances the generalization етгоr of the two terms in LR- R-QQR. By minimizing this measure, select a À that optimally trades off these competing factors.
Finally, we re-train the LR-QR threshold on the entire calibration and unlabeled target datasets using this best X, and report coverage and interval size on the held-on out labeled test set. This ensures that no test labels are used during hyperparameter tuning. Additionally, in Appendix [ we provide deeper insights on different regimes regularization in practice through an ablation study.
5.2 Communities and Crime
We evaluate our methods on the Communities and Crime dataset 42 which contains 1994 datapoints corresponding to communities in the United States, with socio-economic and demographic statistics. The task is to predict the (real-valued) per-capita violent crime rate from a di7-dinensional input.
We first randomly select half of the data training set, and use to fit ridge regression model f as our predictor. We tune the ridge regularization with five-fold cross-validation We use the remaining half design four covariate shift scenarios, determined by the frequency of a specific racial subgroup (Black, White, Hispanic, and Asian). For each of these features, we find the median value m over the remaining dataset. Datapoints with feature value most m form our source set, and the rest form our target set. In other words, in each scenario, the source set consists of data points with below-median frequency of the specified racial subgroup, while the target set contains those with above-median frequency. This creates a covariate shift between calibration and test, as the split procedure only observes the covariates and independent of labels. We then further split the target set into roughly equal unlabeled and labeled subsets. The unlabeled subset and the calibration data (without the labels) is used to estimate r, while the labeled test subset is held out only for final evaluation. The same procedure is applied to each of the four racial subgroups, creating four distinct partitions.

---

0.95
Prediction Set Size
1000
Coverage
0.90
0.85
600
0.80
400
200
26
40
Experiment Setup
Experiment Setup
Weighted CP
2R-CP DRO-CP
LR-QR
DR-ise
Standard
Robust-CP
Nominal Coverage (0.9)
Figure 2: (Left) Coverage, (Right) Average prediction set size the RxRx1 dataset from the WILDS repository.
Experimental details. The nonconformity score is s(x, = 1y - f(x)| Several baselines require an estimate of the likelihood ratio r, which we obtain by training logistic regression model p to distinguish unlabeled source and target data. We then set F T where p(x) is the predicted probability that came from the target distribution. The hypothesis class H. consists of all linear maps from the feature space to R. All experimental results are averaged over 1000 random splits.
Results. Figure D displays the results. Notably, split conformal undercovers in two setups and overcovers the other two. Methods that estimate r and DRO fail to track the nominal coverage, particularly in the first setup on the left. However, the LR-QR method is closer to the nominal level of coverage, showing stronger adaptivity to the covariate shift.
5.3 RxRx1 data WILDS
Our next experiment uses the RxRx1 dataset 53 from the WILDS repository (25. which is designed to evaluate model robustness under distribution shifts. The RxRx1 task involves classifying cell images based on 1339 laboratory genetic treatments. These images, captured using fluorescent microscopy, originate from 51 independent experiments. Variations in execution and environmental conditions lead to systematic differences across experiments, affecting the distribution of input features (e.g., lighting, cell morphology) while the relationship between inputs and labels remains unchanged. This situation creates covariate shift where the marginal distribution of inputs shifts across domains, but the conditional distribution PY|x remains the same.
We use a ResNet50 model (20] trained by the WILDS authors on 37 of the 51 experiments. Using the other experiments, we construct 14 distinct evaluations, where each experiment is selected as the target dataset, and its data is evenly split into an unlabeled target set and labeled test set. The labeled data from the other 13 experiments serves the source dataset.
Experimental details. The nonconformity score is s(z, y) = log fz)). where fz(y) is the probability assigned the image-label pair (Ir, To estimate r, train logistic regression model á on top of the representation layer of the pretrained model to distinguish unlabeled source and target data, and we set f = S We set the hypothesis class to be a linear head on top of the representation layer the pretrained model. Experimental results are averaged over 50 random splits.
Results. Figure 2 presents the coverage and average prediction set size for all methods. To enhance visual interpretability. we display results for eight randomly selected settings out of the 14, with the full plot provided in Figure 3 in the Appendix. The x-axis shows the indices of the test condition. LR-QR adheres more closely to the nominal coverage value of 0.9 compared to other methods.
Notably, split conformal prediction, which assumes exchangeability between calibration and test data, shows under- and overcoverage due to the covariate shift. The coverage of weighted CP and 2R-CP also far from the nominal level, showing that directly estimating the likelihood ratio and conditional quantile insufficient to correct the coverage violations the case of high-dimensional image data. Further, the superior coverage of LR-QR is not due inflated prediction sets.

---

5.4 Multiple choice questions MMLU
Finally, we evaluate all methods using the MMLU benchmark, which covers 57 subjects spanning a wide range of difficulties. To induce a covariate shift, we partition the dataset by subject difficulty: prompts from subjects labeled as elementary or high school are used for calibration, while those from college and professional subjects form the test set.
Motivated by the design from [26]. we follow a prompt- baaee scoring scheme adapted for LLMs: we append the string "The answer is the option:" to the end of each MMLU question and feed the resulting prompt into the Llama 13B model without generating any output. We then extract the next-token logits corresponding to the first decoding position (i.e., immediately after the prompt) and consider the logits associated with the characters A, B. C, and D. These four logits are normalized using the softmax function to produce a probability vector over the answer options.
(() where [xx is the probability assigned to the correct answer. For f and H. we compute prompt embeddings as follows. We extract the final hidden layer outputs from GPT-2 Small to obtain 768 (68-dimensional embeddings. We then apply average pooling across all token embeddings in a prompt to obtain single fixed-length vector representation for each input. We probabilistic classifier ý using logistic regression on the unlabeled pooled embeddings from the source and target data, and we set f I-p- linear head on top of the representation layer of the pretrained model.
Experimental details. The nonconformity score is s(x
We set H. to be
Results. As shown in Table [ our LR-QR method achieves near-nominal coverage and has the smallest average prediction set size among methods that achieve approximately 90% higher coverage, demonstrating both validity and efficiency under covariate shift.
Table 1: Comparison of Methods by Coverage and Set Size (mean + std)
Metric
Nominal
LR-QR
DRO
WCP
Coverage (%)
90.0 0.0
89.6 + 1.2
99.7 0.3
86.5 +: 1.5
Set Size
3.38 0.15
3.92 = 0.20
3.31 + 0.12
Metric
SCP
DR-iso
Robust-CP
2R-CP
Coverage (%)
78.1 + 2.1
96.3 + 0.6
95.8 + 0.7
96.9 + 0.5
Set Size
2.60 + 0.10
3.64 + 0.18
3.56 - 0.14
3.80 + 0.17
Discussion
We proposed the LR-QR method to construct prediction sets under covariate shift. While we have provided strong guarantees on the coverage of our method, it would be desirable to have results that control of the slack in coverage in specific scenarios depending the structure of the likelihood ratio and the hypothesis space. Our work concerns uncertainty quantification and may have positive social impact for reliable decision-making. We do not envision any negative social impact of our work.
7 Acknowledgments
ED and SJ were supported by NSF, ARO, ONR, AFOSR, and the Sloan Foundation. The work of HH, SK, and GP was supported by the NSF Institute for CORE Emerging Methods in Data Science (EnCORE) and the ASSET (AI-End Systems: Safe, Explainable and Trustworthy) Center.
References
[1] Jiahao Ai and Zhimei Ren. Not all distributional shifts are equal: Fine-grained robust conformal inference. arXiv preprini arXiv:2402. / 13422, 2024.
[2] Anastasios N Angelopoulos and Stephen Bates. A gentle introduction conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.075// 2021.
[3] Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. Conformal prediction beyond exchangeability. The Annals of Statistics, 51(2): 845, 2023,
10

---

[4] Stephen Bates, Emmanuel Candès, Lihua Lei, Yaniv Romano, and Matteo Sesia. Testing for outliers with conformal p-values. The Annals of Statistics, 51(1):149-177 2023.
[5] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79: 151-175, 2010.
[6] Aabesh Bhattacharyya and Rina Foygel Barber. Group-weighted conformal prediction. arXiv preprint arXiv:2401.17452, 2024.
[7] Maxime Cauchois, Suyash Gupta. Alnur Ali, and John C Duchi. Robust validation: Confident predictions even when distributions shift. Journal of the American Statistical Association, pages
1 1-66, 2024.
[8] Victor Chemoozuuovv Kaspar Wuthrich, and Yinchu Zhu. Exact and Robust Conformal Inference Methods for Predictive Machine Learning With Dependent Data. In Proceedings of the 3 st Conference On Learning Theory, PMLR, volume 75, pages 732-749, PMLR, 2015 8.
URL. UtR.http:://// httt:://arrttt http://axxvvvro//////// abs/ 1802. 06300
[9] Edgar Dobriban and Mengxin Yu. Symmpi: Predictive inference for data with group symmetries. arXiv preprini arXiv:2312.16166 2023.
[10] Robin Dunn, Larry Wasserman, and Aaditya Ramdas. Distribution-free prediction sets for two-layer hierarchical models. Journal of the American Statistical Association, pages 1-12, 2022.
[11] Bat-Sheva Einbinder, Yaniv Romano, Matteo Sesia, and Yanfei Zhou. Training uncertainty- aware classifiers with conformalized deep learning. Advances in Neural Information Processing Systems, 2022.
[12] Jerome H Friedman. On multivariate goodness-of-fit and two-sample testing. Statistical Problems in Purticle Physics, Astrophysics, and Cosmology, 1:311-313, 2003.
[13] Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In
32nd International Conference on Machine Learning, ICML 2015, volume 2, pages 1180-1189. PMLR, 2015. ISBN 1181510810587.
[14] Isaac Gibbs and Emmanuel Candes. Adaptive conformal inference under distribution shift. Advances in Neural Information Processing Systems, 14:16601177,, 2021.
[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, page qkaf008, 2025.
[16] Leying Guan. A conformal test of linear models via permutation-aagmentte regressions. arXiv preprint arXiv:2309.05488) 2023.
[17] Leying Guan. Localized conformal prediction: A generalized inference framework for confor- mal prediction. Biometrika, 110(1):33-50, 2023.
[18) Leying Guan and Robert Tibshirani. Prediction and outlier detection in classification problems. Journal of the Royal Statistical Society: Series B, 84(2):524-546, 2022.
[19] Yu Gui, Rina Foygel Barber, and Cong Ma. Distributionally robust risk evaluation with an isotonic constraint. arXiv preprini 2407.02007..6666 2024.
[20] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and paltern recognition, pages 770-778, 2016.
[21] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963.
[22] Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Batch multivalid conformal prediction. In International Conference on Learning Representations (ICLR), 2023,
11

---

[23] Kevin Kasa, Zhiyu Zhang, Heng Yang. and Graham W Taylor. Adapting conformal prediction to distribution shifts without labels. arXiv preprint arXiv:2406.01416. 2024.
[24] Ramneet Kaur, Susmit Jha, Anirban Roy, Sangdon Park, Edgar Dobriban, Oleg Sokolsky, and Insup Lee. idecode: In-distribution equivariance for conformal out-of-distribution detection. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
[25] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: A benchmark of in- wild distribution shifts. In International conference on machine learning.
pages 5637-5664. PMLR, 2021.
[26] Bhawesh Kumar, Charlie Lu, Gauri Gupta, Anil Palepu, David Bellamy, Ramesh Raskar, and Andrew Beam. Conformal prediction with large language models for multi-choice question answering, arXiv preprint 1.XXxx:305.18400 2023.
[27] Yonghoon Lee, Eric Tchetgen Tchetgen, and Edgar Dobriban. Batch predictive inference. arXiv preprint arXiv:2409. 13990, 2024.
[28] Jing Lei and Larry Wasserman. Distribution free prediction bands for non- non-parametric regression. Journal of the Royal Statistical Sociery: Series B (Statistical Methodology), 76(1):71-96, 2014.
[29] Jing Lei, James Robins, and Lanyy Wasserman. Distribution-fiee prediction sets. Journal of the American Statistical Association, 108(501):28--887 2013.
[30] Jing Lei, Alessandro Rinaldo, and Larry Wasserman. A conformal prediction approach to explore functional data. Annals of Mathematics and Artificial Intelligence, 74(1):29-43, 2015.
[31] Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113 (523):1094-111 11, 2018
[32] Lihua Lei and Emmanuel J. Candès. Conformal inference of counterfactuals and individual treatment effects. Journal of the Royal Statistical Society. Series B: Statistical Methodology, 83(5):911-995 938, 2021. ISSN 14679868. doi: 10.1 10.1111/rssb. 12445. URL http://axi/ org/ abs/2006.0611
[33] Shuo Li. Xiayan Ji, Edgar Dobriban, Oleg Sokolsky, and Insup Lee. Pac-wrap: Semi-supervised pac anomaly detection. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.
[34] Ziyi Liang, Matteo Sesia, and Wenguang Sun. Integrative conformal p-values for powerful dilto--diittibutiinn testing with labeled outliers. arXiv preprint arXiv:2208. 11111, 2022.
[35] Ziyi Liang, Yanfei Zhou, and Matteo Sesia. Conformal inference is (almost) free for neural networks trained with early stopping. In International Conference on Machine Learning, 2023.
[36] Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In European Conference on Machine Learning, pages 345-356. Springer, 2002.
[37] Sangdon Park, Edgar Dobriban, Insup Lee, and Osbert Bastani. PAC prediction sets under covariate shift. In International Conference on Learning Representations, 2022.
[38] Sangdon Park, Edgar Dobriban, Insup Lee, and Osbert Bastani. PAC prediction sets for meta-learning. In Advances in Neural Information Processing Systems, 2022.
[39] Jing Qin, Yukun Liu, Moming Li, and Chiung- Yu Huang. Distribution-fres prediction intervals under covariate shift, with application to causal inference. Journal of the American Statistical Association, 0-0)1-26,, 2024, doi: 10. org/10. 1080 /00000001111100 01611459 2024 2356886
URL whtph:ttt//ccc //doi
[40] Hongxiang Qiu, Edgar Dobriban, and Eric Tchetgen Tchetgen. Prediction sets adaptive un- known covariate shift. Journal the Royal Statistical Society Series B: Statistical Methodology, 8565):1680-1705 2023.
12

---

[41] Joaquin Saifioner--Candll. Masashi Sugiyama, Neil D Lawrence, and Anton Schwaighofer. Dataset shift in machine learning. Mit Press, 2009.
[42] Michael Redmond. Communities and Crime. UCI Machine Learning Repository, 2002. DOI: https//ddb.or/110224445/333
[43] Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems, 2020.
[44] Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least Ambiguous Set- Valued Classifiers
With Bounded Error Levels. Journal of the American Statistical Association, 114(52))223-234, 2019. ISSN 1537274X. doi: 111180001621459221171113999
[45] Craig Saunders, Alexander Gammerman, and Volodya Vovk. Transduction with confidence and credibility. In IJCAI, 1999.
[46] Henry Scheffe and John W Tukey. Non-parametric estimation. i. validation of order statistics. The Annals of Mathematical Statistics, 16(2):17-192,, 1945.
[47] Matteo Sesia, Stefano Favaro, and Edgar Dobriban. Conformal frequency estimation using discrete sketched data with coverage for distinct queries. Journal of Machine Learning Research, 24(348):1-80, 2023.
[48] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory algorithms. Cambridge university press, 2014.
[49] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-2670, 2010.
[50] Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the log-like ligllikel function. Journal of statistical planning and inference, 90(2):227-244 2000.
[51] Wenwen Si, Sangdon Park, Insup Lee, Edgar Dobriban, and Osbert Bastani. PAC prediction sets under label shift. International Conference on Learning Representations, 2024.
[52] Masashi Sugiyama and Motoaki. Kawanabe. Machine learning in non-stationary environments introduction to covariate shift adaptation. MIT Press, 2012. ISBN 9780262017091.
[53] Macicj Sypetkowski. Morteza Rezanejad, Saber Saberian, Oren Kraus, John Urbanik, James Taylor, Ben Mabey, Mason Victors, Jason Yosinski, Alborz Rezazadeh Sereshkeh, et al. RxIxl: A dataset for evaluating experimental batch correction methods. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4285-4294, 2023.
[54] Rohan Taori, Achal Dave, Vaishaal Shankar, Nicholas Carlini, Benjamin Recht, and Ludwig Schmidt. Measuring robustness to natural distribution shifts image classification. Advances in Neural Information Processing Systems, 33:18583-18599, 2020.
[55] Ryan Tibshirani, Rina Foygel Barber, Emmanuel Candès, and Aaditya Ramdas. Conformal prediction under covariate shift. Advances in neural information processing systems, 32, 2019.
[56] John W Tukey. Non-parametric estimation ii statistically equivalent blocks and tolerance regions-the continuous case. The Annals of Mathematical Statistics, pages 529-539, 1947.
[57] John W Tukey. Nonparametric estimation, iii. statistically equivalent blocks and multivariate tolerance regions-the discontinuous case. The Annals of Mathematical Statistics, pages 30-39, 1948.
[58] Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian conference on machine learning, volume 25, pages 475-490. PMLR, 2013. doi: 10.1007//119944-013-5555
[59] Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic learning random world. Springer Science & Business Media, 2005.
13

---

[60] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic Learning in a Random
World. Springer Nature, 2022.
[61] Volodya Vovk, Alexander Gammerman, and Craig Saunders. Machine-learning applications of algorithmic randomness. In International Conference on Machine Learning, 1999.
[62] Abraham Wald. An Extension of Wilks' Method for Setting Tolerance Limits. The Annals of Mathematical Statistics, 14(1):45-555 55, 1943. ISSN 0003-4851. doi: 10.12 2e1111///mss//11 117773/9117771111111
[63] S. S. Wilks. Determination of Sample Sizes for Setting Tolerance Limits. The Annals of Mathematical Statistics, 12(1):91-96, 1941. ISSN 0003-4851. doi: 10.1214/aoms/1 177731788.
[64] Yachong Yang. Arun Kumar Kuchibhotla, and Eric Tchetgen Tchetgen. Doubly robust calibra- tion of prediction sets under covariate shift. Journal of the Royal Statistical Society Series B: Statistical Methodology, page qkae009, 2024.
[65] Fisher Yu, Haofeng Chen, Xin Wang. Wenqi Xian, Yingying Chen, Fangchen Liu, Vashisht Madhavan, and Trevor Darrell. Bdd100k: A diverse driving dataset for heterogeneous mul- titask learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2636-2645, 2020.
[66] Tianyi Zhang. Ikko Yamane, Nan Lu, and Masashi Sugiyama. A one-step approach to covariate shift adaptation. Asian Conference on Machine Learning, pages 65-80. PMLR, 2020.
A
Additional figures
B
Ablation studies
Here we provide an ablation study for X, the regularization strength that appears in the LR-QR objective. In the same regression setup as Section 5.2 instead of selecting À via cross cross-validation. here we sweep the value of X from 0 to 1, and we plot the coverage of the LR-QE -R-QR algorithm on the test data. Here, note that the split ratios between train, calibration, and test (both labeled and unlabeled data) are fixed and similar to the setup in Section 5.2 We report the averaged plots over 100 independent splits.
Figure displays the effect of different regimes of A. one extreme, when is close to zero, the LR- QR algorithm reduces to ordinary quantile regression. In this regime, the LR-QR algorithm behaves similarly to the algorithm from [15. without the test covariate imputation. In other words, when we set x = 0, we try to provide coverage with respect to all the covariate shifts in the linear hypothesis class that we optimize over. As we can see in Figure 4 this can lead to overfitting and undercoverage of the test labels. As we increase X, as a direct effect of the regularization, the coverage gap decreases. This is primarily due to the fact that larger restricts the space of quantile regression optimization in such a way that it does not hurt the test time coverage, since the regularization is designed to shrink the optimization space towards the true likelihood-ratie Thus, the regularization improves the generalization of the selected threshold, as the effective complexity of the hypothesis class is getting smaller. That being said, this phenomenon is only applicable if X lies within a certain range; once grows too large, due to the data-dependent nature of our regularization, the generalization error of the regularization term itself becomes non-nen neglliiiee and hinders the precise test-time coverage of the LR-QU FR-QR threshold. As is highlighted in Figure 4 theoretical results suggest optimal regime for which can best exploit the geometric properties of the LR-QR threshold.
C Related work
The basic concept of prediction sets dates back to foundational works such as Wilks 63), Wald [2]
Scheffe and Tukey [46], and Tukey [56] 57]. The early ideas of conformal prediction were developed Saunders al. [45, Vovk et al. 61.. With the rise of machine learning, conformal prediction has
emerged as a widely used framework for constructing prediction sets [e.g.. 4 g
16 [8 27
31
36
58
59 A wide range of predictive inference methods have been developed [e.g..
24
3
37
38
40
47 51].
14

---

Coverage Comparison
1.05
1.00
0.95
Coverge
0.90
0.85
0.80
Experiment Setup
Weightee CP Standard
28:CP DRO-CP
L8-OR Robuat-CP
DR: so
Namiinal (0.9)
Set Size Camparison
1000
800
+
Experiment
WetghteeiCP
2R-CP
UR-OR
DR-15o
Figure 3: (Left)) Coverage, (Right) Average prediction set size.
Performance Across Different Lambda Values
Black
large regularization
0.90
Asian
Hispanic
Nominal
Realized coverage
0.85
0.80
mo ragima that ourthoory suggests
0.70
10-3
Lambda
no regularrzation
Figure 4: Ablation study for the effect of À LR-QR performance in the experimental setup of Section 5.2
15

---

Numerous works have addressed conformal prediction under various types of distribution shift B8 40
51 [5]. For example, Tibshirani al. [55] investigated conformal prediction under covariate shift, assuming the likelihood ratio between source and target covariates is known. Lei and Candès [2 allowed the likelihood ratio to be estimated, rather than assuming is known. Park et al. [37 developed prediction sets with calibration-se set conditional (PAC) property under covariate shift. 3 present the nonexchangeable conformal prediction algorithm for arbitrary distribution shifts, assuming that the optimal weights for their method are known. Qiu et al. [40], Yang et al. [64] developed prediction sets with asymptotic coverage that are doubly robust in the sense that their coverage error is bounded by the product of the estimation emrors of the quantile function of the score and the likelihood ratio. Cauchois et al. 7 construct prediction sets based on a distributionally robust optimization approach. Gui et al. [19] develop methods based
B7
isotonic regression estimate of the likelihood ratio. They provide theoretical guarantees for the difference between the population-level distributionally robust risk and its empirical counterpart. However, their results do not directly lead to coverage guarantees under distribution shift in our setting, as that would further require characterizing the effect of estimating the likelihood ratio.
Qin et al. [39] combine a parametric working model with a resampling approach to construct prediction sets under covariate shift. Bhattacharyya and Barber [6] analyze weighted conformal prediction in the special case of covariate shifts defined by a finite number of groups. Ai and Ren [ reweight samples to adapt to covariate shift, while simultancously using distributionally robust optimization to protect against worst-case joint distribution shifts. Kasa et al. [23] construct prediction sets by using unlabeled test data to modify the score function used for conformal prediction.
Our algorthm works by constructing novel regularized regression objective, whose stationary conditions ensure coverage in the test domain. We can minimize the objective by estimating certain expectations of the data distribution-whichh implicitly involve estimating only certain functionals of the likelihood ratio. We further show that the coverage is retained in finite samples via novel analysis of coverage leveraging stability bounds [48] 49]. We illustrate that our algorithms behave better in high-dimensional datasets than existing methods.
D Notation and conventions
Constants are allowed to depend on dimension only through properties of the population and sample covariance matrices of the features, and the amount of linear independence of the features; see the
quantities Amin (E), Amax= Cuin- Caax. and Cindep defined in Appendix E In the Landau notation (o. O θ), we hide constants. We say that a sequence of events holds with high probability if the probability of the events tends to unity. We define S as the features of the labeled calibration dataset. All functions that we minimize can readily be verified be continuous, and thus attain a minimum over the compact domains over which we minimize them; thus all our minimizers will be well-defined. We may not mention this further. We denote by 1[A] the indicator of an event A. Recall that H. denotes the linear hypothesis class H = {(7, T) Y E Rd). This defines one-to-one correspondence between Rd and H. This enables us to view functions defined on Rd equivalently as defined on H. In our analysis, we will use such steps without further discussion. Unless stated otherwise, H is equipped with the norm ||h|| := ||>||| for / (7, Φ). Given differentiable function şo H. -> R, its directional derivative at f = (7, ②) E H in the direction defined by the function g E H. is defined as de |== + Eg). Note that if we write g = (7, D) for some 5 E Rd, then the directional derivative of at if equuls (5, V,(((1)), where V V,((() denotes the gradient of pp Rd - E evaluated at ry Rdd When it is clear from context, we drop the subseript À from the risks LA and L.-
d
E Conditions
Condition 1.
SSuppose Cq. = suPzex [1))2 is finite.
Condition 2. For the population covariance matrix Σ E, 14 J. we have >min > and
Amax (E) is of constant order, not depending on the sample size, or any other problem parameter.
Condition 3. For the sample covariance matrix Σ = Σm $ I ((x)) we have both
Amia (E) > Cain > and Amax ( E Cunx of constant order with probability 1 o(n
16

---

Condition 4. Defining C1 as in 7 in Appendix H E[C]] of constant order.
assume there exists an upper bound L.pper on
Condition 5. The conditional density Js|x=z exists for all
X, and C3
supsex ( is a finite constant.
The following can be interpreted an independence assumption on the basis functions.
Condition 6. Suppose inf [1 Φ>[] Cindep > O for some constant Gindep"
Condition 7. Suppose [r[r]]] 3 Calign > 0 for some minimizer bi of the objective in Equa- [1
lion (18) with regularization X O.
Condition 8. Suppose E,[r²] is finite.
Condition 9. The constant function
IR. given by h(x)) 1 for all X is in H.
The following ensures that the zero function 0 E H. is not a minimizer of the objective in Equation QR).
LR
Condition 10. For each À > O, there exists h E H and 3 E IR such that
(1 S)] + [B r) (0, 8)] XB,[r2].
F
Constants
The following are the constants that appear in Theorem 4.2
P1
2,3 max
BCG
2,3maxx Co.
1/1 = 2,3 Cuin:
Cmin:
P2 P2: = (1 Co)
G = 4pp C2
4p3
A1 = 64C1a1
128C2a2
A2
111
2,32
min Cmin
5
Further,
16
Aa = (1 -1--a] a) + +1) log 8'
A4 = (2(3mmm BC
log 8
max BC
2
As := Ai + A4, a1 2- upper + C2 (1 + BCv),
(1
C C1.max).
The following are the constants that appear in Theorem
As 2 4B2 (E),
A7: == v AB2 82
max Amx (E), As v 22B2 Ararx (E),
Ag = Ao Ar,
and
A1o == AgA!/2
An = max AgA AAA!! /
A12 == A/Al/ A1s AgA//2
A14 Ag AgA
G
Generalization bound for regularized loss
The following is a generalization of Shalev- -haler-S and Ben-David
48 Corollary 13.6].
Lemma G.1 (Generalization bound for regularized loss; extension hypothesis class H equipped with norm || a a compact interval I C R. and a sample space Z.
48
Fix compuct and convex
Consider the objective function f: H I x Z - IR given by (h, 3)z) + [(h,, 3, z) == J (h, B z) + R(h, 8), where R: : H x I + IR is a regularization function, and J H x I x Z + RR can be decomposed as J (h, 3,2) == (h, 3, 21)+ [2 B, for two functions J1. Jz HxIx 2 + R.
Given distributions D D2 on 2, let L x > TR be given for all h.3 by
C(h, 3) Ez,~D, Z. (h, 3, Zı, Zz)] denote the population risk, averaging over independent datapoints Zı Dr and Ze Dzz Suppose that for both Z ~ D2 and Z ~ D2, (h, B, 2)) and (T, 3, Z)] are almost surely bounded by quantity not depending h H and 8 E I.
17

---

Let : HXII + denote the empirical risk computed over Z,, 1.dd.
Dí, i [mn] and Z sid D2.
j E [m2), given by
mi
3), = m1 Σ (,,,,,2,1))
Σ j=1
3, Z.22)
+22+)++ + R),,
Assume that for each fixed 3 & I and E Z.
h + [1, 3, =) is convex and p-Lipschitz with respect to the norm
|| 11æe
h ++ J2(h, 3)2) is convex and p- p-Lipschitz with respect to the norm ll and
h + [(h, 3) is p-strongly convex with respect to the norm || ll with probability o(mi' + +m2))
where the deterministic values fa = p( and p p(33 may depend on B.
Let (h, B) denote ERM, i.e., a minimizer of f(h, over H I. Let hig denote minimizer of the empirical risk in for fixed B.
Suppose the stochastic process 3 + Wa given by W3 = C(h,, - [(h,, 3, 3) for B I obeys [Wa- W K| for all B, B" E I for some random variable K, and suppose that the probability of Km,,mz & Kmux converges to unity as m1, M2 + co, for some constant Kmax- Suppose that there exists constant C such that for all I.
4p(3)²
C.
(B3
Then for sufficiently large mi, m2, with probability least 1 8,
16C
cc 3) - 2(h, <
(mi + mz²
Remark G.2. A special case is when do not have any data from D2, and instead all m, datapoints are sampled i.i.d. from D1. In this case, defining with a slight abuse notation J := J1, the statement simplifies to the analysis of the empirical risk
L(h = Σ Th, Za.1) R(h,
If for each fixed |9 E I, we have that h + [(,, B, is convex and p-Lipschitz with respect to the norm || /l and if (h, 3, Z)] is almost surely bounded by quantity not depending H. and
for ~ D = D2. then under the remaining assumptions, we obtain the slightly stronger
bound
16CKmms
Ic B) 2(h, < V
8m
We omit the proof, because it is exactly as below.
Remark G.3. We relax the strong convexity assumption on the regularizer from Shalev-Shwartz and Ben-David 48 Corollary 13.6], substituting it with the less restrictive condition of strong convexity of the empirical loss É. In order assumptions that merely hold with high probability, impose a boundedness condition on J.
Proof. Fix 3 and let F denote the event that -> L(h, (3) p-strongly convex in h. By assumption, E occurs with probability o(mi²' + m
We modify the proof of Shalev-Shwartz and Ben-David 48 Corollary 13.6] as follows. Let Z D, and Z D2 be drawn independently from all other randomness. For fixed i E [m]], let h + (,, B) denote the empirical risk computed from the sample (Zi.1...., Z.11.1 Zi, Zet1.1..... Zmn. U (Z1,2. 2) and let denote an ERM for this
(6)
18

---

sample. Let 7 be drawn from [m]] uniformly at random. The variables J, (h, 3), h/ are defined similarly but for the sample from D2.
Note that for fixed B, similarly to the argument Shalev-Shwartz and Ben-David 48 Theorem 13.2], we have
Ei B)] = 2,)
-R(h, 222) + R(hs, B)]
=
and
21,2) + R(h3;
Therefore
- (0 ,8,21,1 J1 3, ZI,1)) ( ,,, Z22) -2(hh 3, 1.2))..
Further, splitting the expectations over E and its complement ES, this further equals (B((T.(h)) B, 1), J (ha Zr 11) B[[ ,,, Zr,1 JI (h (1)
(5)
(B(( (J) B, Z3,2) [2 B, 2.222 + 8. Z.,2) - B, Z (E9
On the event E. h + L(h. 3) is p-strongly convex. Now, consider the setting of Shwarrz and Ben-David 48 Corollary 13.6]. We claim that the arguments in their proof hold if we replace the regularizer h + 21|h|12 by + R(h, 8), as they only leverage the strong convexity of the
overall empirical loss L. Indeed, working the event E, since é is y-stronggy convex, we have that L(h)- L(ha) 2 h for all h H. Next, for any h1 h2 E H. we have
E(h2) [(h1) (1, - (h,) + J1 B, Z1,) Jn (h1 3, Z1.1)
m1
Ji B, 2 - (h1, 1, 2i)
m1
Setting h22 = - and h1 = h, since in minimizes h + Lr,1 (h, 3), and using our lower bound on 2(h) L(ha), deduce
2 11lh hellz < T1 8, ZT,) 8,,,,,,,711 (( ,,, J (hs, (6)
m1
Since by assumption, h + Ji(h, 2,2 is p-Lipschitz, we have the bounds |J, ( ,3, (,,1,
(1)
Ti (hg, 3, Zr.1) < pli! - hal and [T (2) 3, Z1) Ji (h,, 3, ZDI & pli h,p Plugging 2e
these into Equation 66 we obtain 1mll - 2 hall²
18 hall. so that [1h hell 4(D)m)
4p(8)
mi
Using once again that h + [1, B, z) is p-pisschitz, we find (1 3, Zr,) - (h,, B. Z1,1)l < 4p(3)² A(3)m
Similarly, on the event E, we have the bound [T Z,,2) (ith,,,....0 <
4p(0)² Thus p(8mm²
the first and third terms are bounded in magnitude by 4p(3)² p(D)m p(0)m. respectively. Due to
and 4p(3)²
their sum is at most C(m + t)
By our assumption that [T, 3, Z) and [T2 3, Z) are almost surely bounded by constant for both Z D, and Z ~ D2. and our assumption that IP [E9] o(mj + m))) the second term and fourth terms from 55) sum to o(m + +mz²), Thus for for each 8, for sufficiently large mi, m2, we have a[] 20(m + my )) By Markov's inequality, for any fixed t > 0, WW t with
19

---

probability at most 2C (mi + -mz'). We now use chaining. Let N be an e-net for I. Then using the fact that by assumption, the process W is Kmimm" -Lipschitz and by union bound.
2C {m] N
IP
sup Wol Kmimg +t BET
<
sup BEN
W sl >
<
+ m2
Pick N with |N| = 1/8, and set / = 4C (mi²
We deduce that
sup WWpl > K Kmi BEI
4C
(mi² + m² )
8
with probability at most g. Set V Ky (mi² + +m²²) We deduce that
40
16CKms.m (m + mz²))
sup BEI
W
with probability at most sufficiently large m1, m2,
3.
Kmax converges to unity, for Since the probability of Km <
16C
sup
W SET
(m + mz
holds with probability at most 6. Since WW' < supaez (Wpl. we may conclude.
H Lipschitz process
Lemma H.1 (Lipschitzness of minimizer of perturbed strongly convex objective). Let C C. Rd be closed convex set. Suppose vp C R is p-strongly convex and g C - TR is L-smooth. Suppose also that g is convex. Let zh denote the minimizer in C, and let Fgtt denote the minimizer of vp + g in C. Then for any x C.
1 180ts x0ll2 (T.l x|12 (V(2))))).
Proof. Since sp is p-strongly convex and since Be 2y are minimizers of &b + g, t respectively,
u|| 2 1 < (vb(zo-)) - Vp(ap), 2 xp)
(v + (F xz) (Vo(z>), xs xv+a)
(V (V I -
< (Vg(a Fett Fz))
(Vg((w+o)) -
I - nnl (Vg(x), Z044 xw))
so that by L-smoothness of
م Al| - 2 (L|lz 2112 [Vg())la)] 12112
which implies the result.
Lemma H.2 (Lipschitzness of minimizer of perturbed ERM). Under Condition Condition 3 and with the notations of Lemma I1.4 we have with respect to the norm > hg is -i-Lipschitz I, and 3 - 3hg is C2-Lipschitz I, where
with E. from on H that
C₁ -32 Amin (((,))aammm B Co) + 4mmaaAma ()) C2= B+ Bma C1- (7)
Proof. First, consider hg. Fix 3> 3' in I. Recalling the definition of from (Empirical-LRR-RR)
difference between the objectives L(h, 9) and (h,, .3') is the quadratic
s(h) i(h, 18) i(h,3)) = XEg - (8)))) XB 1 - B.)
20

---

We claim that is 2A(32 ( (D) -stronggyy convex and 2A (33)))) (e) smooth in h. To see this, write h = (7, ④b for E RR, and note that y can be rewritten as
g(7) 1(32 ( E5y 2 8') B2
quadratic whose Hessian equals 2A (B') ) which implies the claim.
Similarly, we claim that the function (b(h) := [h, 3r) is 2a(8") (2) --ssttooglly convex in h. To see this, again write h = (7, @) for E R.d and note that vp can be rewritten as
(>) > Σn
E, (7 4, []] 1- $).
By Lemma N.3 the second term is convex, and since the third term is linear, it too is convex. The Hessian of the quadratic first term is 2 from which it follows that &) is 2miii Amin (E)-
strongly convex.
Thus vo and y satisfy the conditions of Lemma H.1 which implies the bound
liag hg. < (2X(3") Ami
(1 1l2 + 2X(82 (8") (m) 11hg hgll), (8)
where hg hg. denotes the minimizer of in H.. Since
Vg(n) = - (0) 8')2 - 2122
and by 181.181| < Amax. || & B, and Condition ! we have
[Vg(>)ll & A(4 Amax (Σ) + 2Ca 113 31
for 3,3' E I and h E HB. Plugging this into the bound (8) on [|h fer and using the fact that
8r Pmi and lhall. [|,g]] < B.
|1 h <
(2A3 min Amia Amin
( Amax (L) 2C4) Ba| 8A8max (
Thus we may take
0 = (32 min Amio (iin ( Amax (5)B C+) 4, Amax ())
For the map 3 + Shg. fix B > 8 in I. and write 1|3h, B'h 1| < 13 8 |مواا + | |1 h ||- For the first term, note that since hes H. implies ا < B, the first term is bounded by BIB 8 For the second term, note that since |881 < 8max and since 3 + h is Ci-Lipschitz on I, the second term is bounded by Smax C1 B¹). Summing, deduce that B + Shg is Cz-Lipschitz on I, where C2 = B + BmaxC1.
Lemma H.3 (Lipschitzness of minimizer of perturbed auxiliary ERM). Under Condition 7 that 3 + hg is Ci-Lipschitz on I, and B + Bhg Cz-Lipschitz on I.
we have
Proof. The proof is almost identical to Lemma H.2
Recalling Cunin and Crax from Condition 3 define
C1,max (.32 min Cminn
((28max B + Co) + 48max B),
C2,max B + 3max C1 maax
so that by Condition randomness in S3.
Ci < C1,max and O2 & C2,max with probability tending to unity over the
We now compute the Lipschitz constants of the processes used in the proof of Theorem
Recall T. from 133 i. from (EEmpirical-LR-ORR 1. from 122 and HB {(7, :) |1 B x)) from Section For any fixed 3 E I, define hg as the minimizer of L(h, 8) over Hp. which exists under the conditions of Theorem 4.2 due to our argument checking the convexity of h + L(h, B3 in Term (I) in the proof of Theorem 4.2
21

---

Lemma H.4. Assume the conditions of Theorem 4.2 Define the stochastic processes Wa and Wa on I given by B + (I- (. (3) and + (L (h 3), respectively. Then Wa is x -iipschhtttt on I with probability tending to unity as 111 11,; n23 - 0c, and WB is X2,x-Lipschie on I with probability lending to unity as 111, n2, fg 0G, where
K1,A = 2C (CC,oCC,uuperr + C2. + Pmax BCo) a1>,
22,x == (1 a-) (C1,uppr + C1 =: 0:02
with muu and Cm.xax are defined ( and where Capper satisfies Condition and C2.uppe = BC + Smax C+ upperr In fact, W K on with probability tending to unity condi- tional on S1, and W is xlix-iishh on I deterministically, when conditioning on S2, Ss. when the event C1 & 1mm holds.
Proof. We start with the process W. Consider B, I. Note that for any (h, B), using the definition
of L from 12. we have the identity
L(h, 3) =
= EE, S)] (h,
Thus we may write
We # Wy (E,, -E 8)]) (B, S)] ())
so that
We- Wo.1 < E1 [laa la (hg. 8)ll (hl la la 5)
(10)
Note that we have the uniform bound
|eahh, S) - la (a S) < (1 0) h
< - a 1
< (1- (1-a) B1,
where in the first step applied Lemma N.2. in the second step we used Condition Io apply Lemma N.4. and in the third step we used Lemma H.2] Thus the first term Equation (10)
81,, and the second term in Equation (10p is bounded by (1 E, 3¹). Summing, we deduce that
is bounded by (1 a,
W 3 W < (1 -
( 31,,
so that the process W is K2 K2-Liischitz with K2 = (1- ao (E, [C.] + (ci).
We now condition on S2, S3. Observe that C1. C2 are Sy me-asurrrblee (as Σ from Condition 3 is S3 Sy-measurable). Since E, [C,]] & C1 Cuppper on the event that C₁ C1,maxx we have K₂ < K2 where K2 = (1 a)) (Ci,upper + C1,,ax), as claimed.
We now continue with the process W. Consider 3,3' E I. Note that for any (h, B), using the definition of L from Equation 13), have the identity
T(h B) i(h,,)) (ATE + 2-3h)) - (AEg + -
Thus we may write
Wg W9 >(Ea|3213) -
- E h
A(Bg
-
2,1 fug.))
so that
W wo < AEg | 1133 - (8))2
2AE 1|3hg - 3hh + 1133 (/3) h/3 + 2X B'h
(11)
The integrands of the first and third terms of Equation (T] can uniformly bounded as
182 ( < ls Bhhrrl 1 + 8hh < Co 3' h || Co 110 + sh
< 12 - | 20 B 227 BC -
22

---

where in the first step we used difference of squares, in the second step we used Condition to apply Lemma N.4. in the third step we applied Lemma H.2 bound the first factor and the triangle inequality and the bounds B ε Mmax for / E I and ||]]| Σ
B for h E HB to bound the second
factor. The integrand of the second and fourth term in
be bounded as |shh Bhh x
Co (o.1/hha- - h & C2 - 8 where the first step we used Condition to apply Lemma N.4 and in the second step we applied Lemma
Plugging these into our bound in Equation L we deduce
W W < (E2 + E2(C2] + 23 CB + Bs(C2))) 8
so that the process W is K Ki-Lipschitz with
K = (2Ca (E2[C2] + E2(C2) + 2m +
We now work conditional on Sj. On the event that Cj & C1,max and C2 & C2, and by Condition 4 we have K1 < 1m,aax where
K1,A = (2Cxp Upp.r + C2, + 2,3max CB + C2
= 2C 2C2,(C2,uper + C2. + 3max BC )A
Since C1 & Cmmuu and C2 & C2 mmax with probability tending to one due to Condition 3 K1 < K1,x
and K2 & K2,x both hold with probability tending to one we uncondition on S1, and we are done.
I Proof of Proposition 4.1
there exists a global minimizer (h",8*) of L(h, 3). The first order condition with respect reads 2ΛE, [h^ (X)(6") - r(X)) By Lemma [N.], the first order condition with respect to h reads
Fix À > 0. Under the assumptions of Lemma
L.3
E, [h* (X)(Ps [S(X, Y) < h" (X)) (1 a))] + 2 | (x)
=0
for all & E H. Setting h = rH in the second equation, and subtracting (3r)² times the first equation from the second, we deduce that
E, [h" (X)
& -
+ 2AE 18t (X) (X" - -XX (1 (8"M -,0
(X] - (1]a]]] a))
+ 2AT (rH (X) (31()))))) -r(x))
[,, (X)) s|) (X < [*(X]]]
-1 - (1)
- = =.
Therefore.
(X) [S(X,)) < h2 (X)] = (1 - a) + (1) -
which implies the result.
J Proof of Theorem 4.2
Recall that S₁ are the features of the labeled calibration dataset. We also recall the notation E, and
E. for j = 2,2,3 3 from Section 2 Given the unlabeled test data S2 and the unlabeled calibration data S3. define the auxiliary risks for h HB, 8 E I,
ih, Sa) E, 1.. (h, S)] X A 23hh
(12)
and
((h,3:81) = Bi (h, S) + 1E + AE2( 228h].
(13)
Let
(h, E arg min deZ
S(,,B;S2,5a)
(14)
23

---

For convenience, we leave implicit the dependence of L and (h, B) on S2. S3 and the dependence of L on St.
In order to study the generalization error, we write
L(h, B)
= (L(h, L(h. + (i (),,3)) + ( (f.h,, B) L(h, (T(h,, B) i(hi, ;3)) + (i(hh,, ,00,,8)))))) I(h" (²))-
Since (h 3) is minimizer of the risk L, we have [hh, -(h, B) < 0, and since (h, 3) is minimizer of the risk L, we have L(h, B) I(h", , < 0. Thus our generalization error is bounded by the remaining four terms:
L(h, ( < (L(h, B) i(h, B)) + (I(h, 9) L(h, B))
+
+ (L(h", - L(h", ())
=: (1)+ (TT)+++++ (IV).
(15)
We study the generalization error by conditioning the unlabeled calibration or test data. Then our regularization becomes iata-independent Conditional on S₁, Term (I) can be handled with Lemma G.I abooe.. Conditional on S2, Sg. Term (II) can be handled with Lemma (III) and (IV) are empirical processes at fixed functions, conditional on S2, S3.
Terms
Term (:: We work conditional on Sj. First, note that due to the definition of L from Empir.cal-LR-QR). we can write for any (h, B).
L(h, [(h. 3) L(h, L(h, B).
Since () [l,,9) can be viewed as a difference of a population risk {Eg[8917] + +122 XE2l-233) and an empirical risk AIE3 h3 + 2 with "regularizer" [, (h, S)), this expression enables to apply Lemma G.1 to bound T(h,,)) i) Explicitly, we can write
1 1 3) = = E2l- + X (A,
Hence, fixing B, we can apply Lemma G.1 choosing my ny and m2 = n2. Further, we choose H. HB {(,, D)
11ll2 & B 20} with the norm (7, Φ) 1 Moreover, letting = (x" ,x') for x" x' X, and { = 1/A, we use the objective function given by (h, =) + [h) =) = [h, B,2) 3), where Jhh (,,) (h, B, + Jo B3 2). and where
[1, (1), ((h(
(2,,,,,2) - 233((')) R(h,, 8) = E (h,
We now check the conditions of Lemma G.I
Boundedness: Note that | (h. 3, 2) = |/(") < (BC )², where in the second step we used |3| & 8max for 3 I, and used h H. and Condition 1 to apply Lemma N.4. Similarly, note that (h, 3, 2) = 2|3]|((z')| & 2,mmxx BCG, where in the second step we used [ < Bmax for 3 I. and used h E HD and Condition [ to apply Lemma N.4 Thus [T (h. 3, x) and [22h,, B, =)1 are both bounded by the sum 3 o) 2,3max BC..
Convexity: Write h =(,, ④) for 7 E Rd. The map + (h, can equivalently be written as 7 83yy (xx))((=") 7, a quadratic whose Hessian equals the positive semidefinite matrix 2z ((x"))))))))))))))))))))))))(( Thus h + J1 [1,, 3, is convex. The map / + (2, 8, can equivalently be written + -28y (xx), which is linear, hence convex.
Lipschitzness: Write h= (2, ②) for 7 E IRd. The map li + Ji (h, 3, can equivalently be written as 7 + 82g (T(T")(=")("" y. The gradient of this quadratic given by 7 ++ 2,5 & (0 (=²") Tr. The norm of this gradient can be bounded by
(x "(x")))(("""")
7l1a < 2|/"10(("" 111 < 2 BC
where in the first step we applied the Cauchy-Schwar Schwarz inequality, in the second step we used |3] & 3max for 8 E I. l|yll2 & B, and Condition I
Next, the map h + J2, 2,22 can equivalently
24

---

be written 7 + -23y 2z'). The gradient of this linear map is given by H -234 2mm Co. where we used |3| & 5mux
The norm this gradient can be bounded by 2 21 for 3 E I and Condition [ Thus the norm of each of these gradients is bounded by the sum P1 2 BC + 2,3 Co. and the maps + B,, and + J2(h, 2) are both pr- Lipschitz.
Strong convexity: Since h+ (h, 8) is convex for all IR by Lemma N.3 and since h + [3[ is linear, the map h + [e (h, S)] 2 is convex. Consider the map h + E3 [32h2] Writing h (7, 4) for E Rd, this can be rewritten as 7 + 32yTEn quadratic whose Hessian equals 2, By 3 > Buin for B E I and Condition 3 follows that with probability 1 o0 1- (m + ng ). the map + f2.3[f((h, Z) is p1-strongly convex, where Z = (X", with X' uniform over X₂ and X" is uniform over X3, and where fa1 == 2,32
min Gmin- Cmin- In particular,
h x/ [L, is convex.
Let č = 4pi Let K1 denote the Lipschitz constant of the process Wa, where K1 < K1.x with probability tending to unity conditional on S1 by Condition 4 and Lemma H.4 From Lemma G.
applied with ę = 1/A, & LL and = & L, and W = (L L) X, we obtain that conditional on
S1, for sufficiently large n2, na, with probability at least 1 8 we have for Term (I) from 15
1 Term (I)
11.//1
(
8/4
122
n2
Thus
64C1AK1,
Term (I) <
+
A1
o1 Since the right-hand side does not depend on S1, the same bound
where we define A1
holds when we uncondition on St.
Term (II): We work conditional on S2, Sz. The risks L and L share the same data-independent regularization [ + 2B2(-2 Write 2 = (x, s) for x E X and E [0. 1]. Fixing 8, we apply Lemma G.1 with the objective function (h, + [h, = J (h, B, 2) RR,, B), where
[h, 3,2) Ea (h(
R(h, 9) = Aβ3 | + X x 2,3h).
Since the empirical risk L is computed over the i.i.d. sample Z, = (X,, S₁) for i E [n1], we use the modified version of Lemma G.T given in Remark G.2 In particular, we check boundedness, convexity, and Lipschitzness of J without writing it as sum Ti + J2.
Boundedness: have the uniform bound, for all h, 3,
[T, 8,, 2)1 & (1 (1-aa) (())))(())
< (1 ())(()) 1) < (1 aB + 1),
(16)
where in the first step we used Lemma N.I in the second step we used the triangle inequality and 8 E [0, 1). and the third step we used Hn and Condition | to apply Lemma N.4
Convexity: By Lemma N.3 h h [h, 2) 22 is convex.
(7, Φ) and = (7', Φ) in HB. where 7, / Rdd. Note that Lipschitzness: Fix
[h, 8, [h,
(h(z)) la (h'(z)),
< a) (xx)) N/ (xx)) < a) 1'll,
where in the second step used Lemma N.2 and in the third step used Condition | to apply Lemma N.4 Thus h + [h, 3) is -2- Lipsschhi where P2 = (1 (1-a) C..
Strong convexity: To analyze R. first observe that since h + 1i2[-2,9h] is linear, it is convex. Writing h = (y, Φ) for E Rd, the term h + AE [32 in R can be rewritten y + X,2 Ey, quadratic whose Hessian equals 2 By > Amin for 3 I and Condition 3 it follows
25

---

that with probability 1 -
ong over S2, S3, the map h + R(h, B) is p2-strongly convex, where
(A( = 2 min Smin-
Let (2) [z]A]
4p3 Let K₂ denote the Lipschitz constant of the process W5 p: recall that conditional
on S2, Sg. K2 K2,A deterministically the event C₁ & Cmax by Lemma H.4 By the version of
givgevven Lemma G. given in Remark conditional on S2, S3. if h + R(h, 3) is u2 -ssttonyy convex,
and if Ci & ma. then for sufficiently large ni,, with probability at least 1 g. we have
12)2
A2
Term (II)
(17)
(6/8)m1
Vnn
128C2a2 and C2 where define A2
Unconditioning S2, S3, since (h,, (3) is 22 (2(A)-strongly convex with probability tending to unity by the above analysis, and since by Condition 3 we have C1 & Cmmma with probability tending to unity, we deduce that for sufficiently large n1, n2, fa,, with probability at least 1. (17) still holds.
402
2 Sune
Term (III: We work conditional on S2, Sy. Since from 14) lies in H.. we may use the bound in Equation (16) to obtain supzex [ (h, .S] < (1 - (BCo + 1). Thus by Hoeffding's 's inequality (21] with probability at least 1 - & we have
(1- (1-o)(BCr + 1)
2 log 8/1
(i (t-)) (E, (h),ahh,
&
vni
Thus we have Term (III)
Aa vnr
2 log where we define A3 = (1 (B- + 1)/l
Term (IV): Note that we may write
Since || & B by h" E Hg and since Condition I holds, we may apply Lemma N.4 to deduce that S 1h* (x)] & BCG. Consequently, for I. we have the uniform bound sup,ex |5h [8h((x)] < Pmax BC.. By Hoeffding's 's inequality 211, with probability at least g. we have
MBmmux BCo) ) V log o7.
( 12)
By another application of Hoeffding's inequality, with probability at least 1 - g. we have
42( BCo) V log 2
8/8
(És 2X <
Vn3
Summing, with probability at least 8 we have the bound
A(3maxx BC,) )2 V log 16 8
42 BCo) / log 16
8
L)(",, <
n22
VTg
Using the inequality +b < V2v02 6 for all a R we deduce Term (IV) < And 1 + where we define
16 5 max (Bma BC 4}
A V2 max BC
log
Returning to the analysis of (15), and summing all four terms while defining As = Ai + A4. with probability least 1 we obtain a generalization error bound of
-+ Aa ViI
1 -+
1 1
1hh 3) - L(h", Asd
A
112
n1
VX
M
The result follows by taking As, d' = Ag. and c" = A2
26

---

K Proof of Theorem 4.3
We use the following result to convert the generalization error bound in Theorem 4.2 a coverage lower bound.
Lemma K.1 (Bounded suboptimality implies bounded gradient for smooth functions). Let f. Rd + R. for some positive d'. Suppose x² is global minimizer of f. Suppose x' is such that [(a') & f(x)) +.. Suppose h E TR& is such that the map g R - given by + [(x' + th) is
T-smooth, Le. [g"(h)] is uniformly bounded by L. Then
(f'('':)) 1V (Vff==") & V2L h112.
Proof. Assume there exists and > with f' h) > 8 h|] Setting y = x' th,
f(a' - th) < f(x)) tf' (z': h) |M1
Set t t= (/(((bl to obtain
1(x' - th) & f(x') - & + 21. = f(x'' 8 Since f(x') & f(x*) +s, we have f(x' - th) & f(x") + 2I
2I.
8² I > 22L, then f(x' - th) <
f(*"), ), contradiction.
similar argument with (x(x; < -1|li||| and y = x' + th yields the same contradiction. Hence
-V |M & (h) & |M]l
By Condition T and Condition 5 we may apply Lemma N.5 to deduce that the Hessian of our population risk 7. from (R-QR) the basis - σa) the block matrix
E2
(h) + 2A [2 - r)]
E 22 (2 r)] [2[2A
V)L(h,3) =
Thus by < Bmax, |/||| < B for E HB. Condition 5 and Jensen's inequality, we have the uniform bounds
18L(h, & [12] & 2AB2>an Amax (2) =:
sup heHa.RER
and
V () = | (fsix ( (C, 2A52 2 Amax (2) 12-
sup NEHBBEI
I.. and Lemma a global minimizer of the objective Equation R LR-QR exists, and since Bmin Plowers Bmax 2 Mupper- and B > Bupper. any such minimizer lies in the interior of HB I. Thus we may apply Lemma K. to the objective function L. We utilize two directional derivatives in the space H IR. The first is in the direction Oz x 1, the unit vector in the coordinate, Since (h, B)
By Lemma
HB I. the magnitude of the second derivative of L along this direction is bounded by V1-
The second in the direction of the vector 7B x O, where ræ the projection of onto the closed convex set HB in the Hilbert space induced by the inner product (f, g) [fg]. Since (h, 9) E HB x I, the magnitude of the second derivative of L along this direction is bounded by 12.
Given h, let CXver(X) = PP [ < h(X)ix - -(1 - a). Now, on the event that L(h, 3) L(h", , & Egens we apply Lemma K.1 with f being (7, + L(hy: 3), x² being (h", ) x' being (h. B), = Eyen: and the directions specified above, with their respective smoothness parameters derived above. Using the formulas for L from Lemma N.5 and the bound ||rB|| || < B, obtain that on the event E,
|2XE, [h(3h r)]1 & E,,
E [overr XE, 123rr@Shh r)]l < &
where E₁ 22 Eg v2
27

---

For any h and B, we may write
E1 Covee = Cover + (3r -))) (2 (3h - r)] AE, (3h rr]
Evaluating at (h, 3), the first term is most & in magnitude, the second term is at most 3 in magnitude, and the third term equals 2,9 [(r (h)2). We deduce
Ei [oveer 2 2,X,, [(r 3h) - E E2.
Since Cover E [-(1 (0l--a,,1 ()]
[ [rCver))
E1 [overr {1 (1-a)Eı([1- ral]-
We deduce that
Cover) > 23XEII(TE
- E2 - (1 - a KE ||r - ral]-
We now bound the quantity E + E2. First, since va bb & v vb for all a, b > 0. Theorem 4.2 implies that
Egen & ////21112
1
1
1/4
A
+ A
+
1/4
X1/4 ni
1/4
112
113
n²
We may write & Epen /4B² Amax [Σ) 1/2 VEgens so that for 3 I we have
1 & 1m v 4B Amax (.) 1/2 V Egen= Ag21/2 Egen-
Using the inequality Va bb+ & Va + Vb for a, b > O, we may bound
& 22B B4B282 max max (Σ) 112 V 22B²C (m) V
A7X2/2 VEgon + As Asv Egens
Thus
88,+38 10A V + A721/2 V + As /
Ag V As / Egen
Plugging in our bound on V and grouping terms according to the power of X, we deduce that
328 + Eg & Ecor, where Ecov equals
A1o
+ 1
1/4
A An1
1
1/2 + A12
1/4
+
A13
+
A14
X 1/4 1/4
1/4
1/4 n2
1/4
112
133
112
n13
n1
and where A1o.... .... A14 are the positive constants given in Appendix E,
It follows that on the event
[rvvrr) (1 - a) 23XE, [(rB -Bh) -
Ecor (1
a)) [ rB]]-
By Theorem 4.2 E occurs with probability 1 8 for sufficiently large n1, n2, ns, and we may
conclude.
L Unconstrained existence and boundedness
In this section, we prove apriori existence and boundedness of unconstrained global minimizers of the population objective Equation (LR-QR). We write (h₃, (87) for a minimizer of the unconstrained objective in Equation
(LR-QR) with regularization strength
0.
In Lemma
L..
we show that under Condition 10 we may eliminate /9 from Equation LR-QR) so
that Equation (LRQQR is equivalent to solving the following unconstrained optimization problem
over h:
E, [rh]
E. S)] (EH((0)
min
(18)
E,
[42]
28

---

Lemma L.1. Under Condition 10 for À > O, given any minimizer ( (3) of the objective in
Equation (LR- AR-QRI with regularization X, h2 is a minimizer of the objective Equation (18) with
regularization A. Conversely, if h is minimizer of the objective in Equation (8) with regularization
X, then there exists a minimizer (hx,, (%) of the objective Equation LR-QR with regularization such that h =h.
Proof. By Condition L0] the minimization in Equation LR- ER-QR) with regularization can be taken
over H') \ (0). Further, since the projection of onto span h
ch E [R), for h o 0 is given by
h, we may explicitly minimize the objective in Equation LR- E [K])
(R-QR) over via
E [rh]
27
(h,, S) + Amin E, [(3h r}3] = ta (h, S) + AE PER
E [4,
( (Eibrh) Eg [1:]] 11
27
E, [rh]] E2 [h3]
(a,, + T2 [r E,
la (a, 5)
[B1|/9]-
where in the second step we applied the Pythagorean theorem. Since the term AE [r']] does not depend on the optimization variable h. we may drop it from the objective, which yields the objective in Equation (18). It follows that is a minimizer of the objective in Equation (88 iff h = h for some minimizer (K)) of the objective of Equation (LR-QR).
Lemma L.2. Let FH denote the projection of r onto H. in the Hilbert space induced by the inner
product (f.g) = [.]s Then under Condition and Condition there exists 0" > 0 such that
[i[s] a ---EE E, [ea (0 TTH S)] > O.
a a- (f S)]. Clearly g(0) = 0. Note that by Proof. Define g IR + R by g(0) = [S[ -
Condition Ps|x [S 0] = so that
g'(0)= aa a -E,
[r (P s
& 0] - (1 a)) a
a (11 (1-a)]
ax) [mH]-
By Condition 9 E1 [rx] E, [r 1] B frrr-1 1] Eg [r] 1, so g 0. Thus there exists
8 > 0 such that g(0") > g() = 0, as claimed.
Lemma L.3 (Existence of unconstrained minimizers). Under Condition 2 Condition 5 Condition b
Condition Condition & Condition 9 and Condition 10 for each X 0. there exists global
minimizer (hi 35) of the objective in Equation (LR-QR
Proof. Fix > 0. By Condition 10 and Lemma L.1 suffices to show that there exists global
minimizer of the objective in Equation 18) Let G(h) denote the objective of Equation 18 Define
the function h = 0"TH E H \ {0), where 6* is chosen to satisfy Lemma I.2 With Gindep from Condition 6 define B(A) 2cmde (1 + a [e, (h, S))) and
1 Í(A) = 2 Amax (2)-1/3
1/2 (E - a - (a, >
We show that if [|b]] > B(A) or ||A|| & b(A), then G(h) > G(h). Consequently, the minimization in
Equation (18) can be taken over the compact set {(7, D) b(A) < 11 & B(A) C H. so that by
continuity of G on H. \ {0), global minimizer hī exists.
To see this, first suppose ||A]|| >> ( Then writing h (7, 4) for e Rd and applying Lemma N.1 the triangle inequality, and E [o, 1].
E, [L, S)] > aE, [|h S]] > a (E, [[b]]] E > a 2) 1).
(19)
By Condition 6 and our assumption that ||^|| > B(A), this implies that E 1o. S)] 1). Further, by the Cauchy- inequality.
>
a (()()))
E2 [rh]
Eriri/ < Er
E, [62]
<
MEHA(() [
sup
29

---

Thus by Lemma N.1 and Condition 8 G(h) > a(B(A) - AB1 To prove the inequality G(h) G(h), it suffices show that
R1 [rh]2
ai ((B())Cindep - 1) AE [r E1 Ehl 5)]
E [6.]]
Indeed, since h is scalar multiple of rHe have En [x
R. [r the inequality reduces to
E [
a (() 1) > B, (h, This holds by our choice of (A), which finishes the argument in this case.
Next, suppose ||A|| < b(A). By Lemma N.1 the triangle inequality, and S E [0, 1],
(h, S)] > aEil/h S|] a{E][S] E, [[]]))
(20)
As above, the Cauchy-Schwarz inequality implies the bound [r/r] 13 [R2]
& E1 [r
We deduce that
G(h) ( [S] 1 [[[]]] [r
Writing h = (r, 2) for y IRd our assumption that ||a]| < b(A) implies that
|M4l < E1 |/| 11lr 4 T 7///2 & b(A)Amax (2)1/2,
which when plugged into our lower bound on G(h)) yields
G(h) > a [SE b(A) (2)) XE [r+].
To prove the inequality G(h) > G(h). ). suffices to show that
E [rhr] E₁ hh2
a [S] - B(A) Amax (2) - XE [r > E. [fa (h, S)]
As above, since h is scalar multiple of rw. we have Ej [r
T. [rā]² [h
so the inequality reduces to
a 100--b( - (22) > (,,
This holds for our choice of B(A), finishing the proof.
Lemma L.4 (Bounds on unconstrained minimizers). Under the conditions used in Lemma L.3 for all A > O, for any minimizer (h5,3%, of the objective Equation (LR-QR) we have that || (Blaeers Bupper) and 198 (Bwwer, Supper), where
1/2 (E1 - EE, Blower 2 Amma -//
ru. rH.s))) 8)1) (0" 0,
(21)
Bupper 20 iimeep (ax (0 +1)
Blower
Bupper Amax (E)1/2 > 0,
Calign
E, 2/211/2
Bupper Blower 12)
and where 0* is in Lemma L2 and r' denotes the projection of onto H. in the Hilbert space induced by the inner product (f = [f9].
Proof. In order derive our bounds, we consider the reparametrized optimization problem
[rh]]
min (e,, S)] bEH)(0)
(22)
E, [12]
for & >> O. We claim that for & > 0, any minimizer of the objective in Equation 22 is of the form Miye- To see this, note that for g > 0, the objective of Equation (18) with regularization À = 1/E can be obtained by scaling the objective of Equation (22) by the positive factor 1/5. Next, by
Condition 10, we may apply Lemma I.. deduce that E {0) a minimizer of the objective
in Equation 18) with regularization
1/E iff h hi
30

---

In particular, by Lemma L.3 for all & > 0, there exists global minimizer of Equation (22) with regularization Ç. In the case that ç 0, it is clear that any minimizer his of the objective in Equation (22 with regularization Ç = 0 has the form h = Orx for some scalar 0 > 0.
Since there exists minimizer of the objective in Equation 22 for all regularizations & in the interval [0, oo), we may apply Lemma M.1 to deduce that for all 0 we have E, [Ca ( S)] <
E1 [La (h:e,
We prove lower and upper bounds on ||bi |I for all 5 > We begin with the lower bound.
Lower bound: By
20
we have E, (6. S)] > a (B,, [S] B, E, []). Rearranging, we obtain
the lower bound
E1 / E1 E1[s] a -E, ( ,)
By Lemma L.2 there exists 0* > 0 such that - EE, 1 (0' S)] O. Setting h T" and plugging in the expression for Blower given in (2I). our lower bound becomes Ei / > Amax (2))1/2 Blower We now convert this L norm bound to an L norm bound as follows. Write hife le b) for for 7i/E RR. By the Cauchy-Schwand inequality, obtain the upper bound
/ & [ 1/1/22 Ei((Oije) T T TubTxi 7//e) 1/2 & Amus 12 ll2.
Combining this with the lower bound E, [ > Amax (E)1/2 Blower. deduce that || Ihi/gl12 > Blowers as claimed.
Upper bound: We prove the upper bound in a similar manner. By the first two steps in 19 and using S E [0, 1), we have
E S)] > a (FE
E (|1))) > >a (E, [E - 1).
Rearranging, we obtain the upper bound / < Le 5)] + 1. Write hi (hiye: b) for T Rd. Since we have already established that ||/ > Blower > O, we know that Fi/e A Thus we may write
K 7i/E
>>1
E B E Φ) 2
+
Ihi/gll2
By Condition 6 this is at least // Cidcpp Combining these upper and lower bounds on E, [ we obtain |/ig 122 & a -K (1i S)] + 1. Isolating 1/1i/gl2. we have
| -nn & Tndo
(a - EE S) + 1) < Bupper:
as claimed.
Having established 0 < Blower < infx=o || < supx>0 | < B Bupper <
turn to upper
and lower bounds on 3x- As shown in the proof Lemma L.1 if (h) .95) is a minimizer of
the objective in Equation (LR-QR) with regularization X, then XX E. [rk]]
[| By Condition 7
ErirA 2 Calign > 0 for some minimizer (h (6)) of the objective in Equation (L-QR with ||
regularization 0. By Condition and and Lemma L.I] h a minimizer of the objective in Equation 18
with regularization > 0 iff h
h for some minimizer (hi,33 (x)) of the objective in Equation LR
QR). Thus by Lemma L.3 for all
0, there exists global minimizer of Equation
(18) and we may
Er
apply Lemma M.1 to Equation 18 to deduce that for any À > O we have
Ei [, 1772 2 Calign > 0.
Consequently, by our bounds on Tiy, Condition and the Cauchy-Schwan inequality, if we write h (1x, b for >x IRdd then we have
Calign
Calign
Calign
B
Blower
E, [1ng//11/22
Eg (17)
ΦΦ
1x/1/2
Bupper Amax 1/2
and
E, 1/2
E, 1/21//12
8 <
Suupper:
E
12/122
Blower (2))1/2
completing the proof.
31

---

M Monotonicity
Lemma M.1. For some set X and f.9: : - f.g are such that for some interval I C R. the minimum is attained for all e E I. Then G: I - R. G:cH g(x(e)) is non-increasing in c.
R. let x(c) = arg ge (f(x) + cg(x)), where
Proof. Let 02 I1 < cz Atc= cı, the minimizer r(ci) satisfies:
f(z(c1)) (ng(((c))) & f(x(c=))) + +lg(((()2))
At = the minimizer x(02) satisfies:
f(x(c2)) + (2)(2((2)) S f(x(c))) + c2g(((e)))
Adding the two inequalities, we find
$ + +2g(((())))) + [f(x(()) + c
Subtracting the common terms f(x(e))) + ((x()2)) leads to
(gg(((())) + c2g(2((22) v c2g(x(c1)) + ag(x((2)).
Rearranging, and factoring out сj and 02, we find
[g((((())) g(x(c2))) - c2(g(x((1)) g((((22)) $o. Thus, (cr 22) [s(((e)) s(x(c>)) s 0. Since c > 0. the inequality implies g(a(c1)) >
g(æ(c2)). as desired.
N Helper lemmas
Lemma N.1. a & 0.5. then alc - s| < (c(c, < (1 a)|c- - s) for all c, 8 E IR.
- - < and a & 1 a, we have a(s- - c) & (c, & (1- (1-a((s c). which implies s (o, < (1-a) (1-a)le-s) sl. I <
Proof. If s 3 e, then (c, (1 a) c). Since 8
then (c, = a(c-s). Since c-8 > 0 and a & 1-a, we havea(c-s) < la(c,) & (1-a)(e-s)
which implies ale- < sc (1 ai]e s|. s/.
Lemma N.2. If & 0.5, then the map R + R given by c+ la is (1 a) Lipschitz.
Proof. If 8 & ej < c2, we have 0 < (c2, 8) lo(e,,)) (o(e,,))= ale2 ci), which by < 0.5 is
at most - (c2 - c.). Hence |l, 8) - La (c1 (1-a) - al. If < 8 02 and
8c) 8) > la (),, then we have
0 & (c2, 8) - la (c1, alc2 5) - (1 (1- a)(s c) < a( - 5) + + a) = a(c2 c1),
which by a < 0.5 implies 8) - (c) < (1 - a)le - al. If a & 8 & 02 and
(c) 8) & la (c1, s), then
0 la(C1, la (1 - a) a(c2 s)
< - (s - a) +1- - 5) = (1 a) -1), hence (e2, 8) Lo (c1, 8) < < (1- a)lc2 a1-a)le2
cl. crl Finally, if < c2 < 8, we have & la (c1,8) la(c1 8) < (1 - ax)e2 -al-
la (C2, 8) = - ()-2 ).), hence La
Lemma N.3. The map H. + R given by h + (h(x)), s) is convex for all x E X and s R.
Proof. Write h(z) (7, ②) for 7 Rd. It suffices to show that the mapping Rd + RR given by T la () is convex. But this map is the composition of the linear function Bd + R given by + 7 (x) and the convex function R + E given by (a s), hence it is convex.
D
32

---

Lemma N.4. Under Condition 1 h E H. then sup, zuP |x(x)| & Callbll, where we use the norm given by ||b|| for h (7, 2) In particular. if H.B. then supzex [h(x)] < BC..
Proof. Writing supsex | (1x)l22 & Collell, where in the second step we applied the Schwarz in- equality.
(7, b) for Y E RA, we have suPnex [h(z))
suprex 17% +(=)))
Lemma N.5. Consider the function 4p R R given by pp(7) = (xlla(h,(X),, where h== byy X' + I. is given by h(x) = (r, D(x)) for all I E X. Then under Condition and Condition 5 ip is tvice-differentiable with gradient and Hessian given by
V, R 1 (( (M() > SS 5 (x)]
(2y(()) RR (II
Consequently, given & E R defining g X - R as g(z) (,)) for all x X, the directional derivative of : H + IR in the direction is given by (5, Vas((T)) = E, [(pss (x()>
S] - (X)))
Proof. For each x X, define the function ():)))) : R + IR given, for all u, by n/u; s)
Es (fa S)]. For each E R, define the function ((: s) : R - R, where for all u, x(u; =
allu > 8] - (1 I < s].
By the definition of the pinball loss l-(-,), and since by Condition 5 the conditional density fsix=a() (-)
of S|X = x exists for all x E X. the derivative of la (u. 5) with respect to u agrees with the random variable x(u: 5) almost surely with respect to the distribution S|X = Also, note that for fixed R. (x S)I is bounded by the constant (1 a). By the dominated convergence theorem, it follows that u + (1;;)) ) is differentiable, and that its derivative equals Bu (1; = -E5)x= S)], which, by the formula for X(u; S), can be written as all s| > S] - (1 -a))ssx=== < S].
0
Thus for all u R and x E X, we may write 8 TT; x) = Psxx=> Iu > -] a). Since By
by Condition 5 the conditional density fsix== of the distribution S|X = I exists for all x E X, it follows that the edf u + Pssx=ma > S] is differentiable for all u E R and all x E X with derivative given by u + (u). Thus the map + 8u n(u; ar) is differentiable for all E X with derivative given by u + (u) In particular, n(=xz) is twice-differeniabbe with second derivative given by f.)x==()).
@
Next, for each x E X, define the function ((;x)) : Rd - R given by (( x) = (1)x==(((o((,, where h = h4 = (7, 4) For each x E X, let ev(;;z) Rd + R be given by ev(yzz) = (z). where h = h, (7, 2). Then ((;z)) given by the composition ((;;)) ev(:;)). Since ev(;; = (7, ((x)), ev(;;)) is linear, it is smooth. Its gradient is given by V vv) ((x) for all y E Rdd, and its Hessian is zero. It follows that ((;x) is twice- differentiable. By the chain rule, the gradient of ((;xx) is given by
())()))) = m/( x))
vv(e(1;))) = (Psix= S - (1 (1- (z))))((x).
Du
(==e(())))
Since the map y + Ps)x== > S] - (1 a) is given by the composition a n((xx) o (v
we may again apply the chain rule to deduce that the Hessian of (b(:;z)) x) is given by
g2
(((()))= au n)(;;))) x)
v)e((1))) - x(x) T (Mx)
(==x():))
Returning to our original function ip, note that by the tower property, (p(7) = (+) X)). Note that |V 222 is at most
|P (b)) > $] - (1 - a)) I| (z) < (()))x==\(<)) > S] + (1 - ( < (2 a)Co,
where in the first step we used the triangle inequality, and in the second step we used the fact that (s)==((((r) > S) & 1 and Condition Similarly, we may bound the Frobenius norm || ||| of
V (2 by
33

---

where in the first step we used Condition 1 the identity | l || and in the second step we used Condition 5 Since the entries of (++ æ)) and V (+( æ) are bounded by constants, we may apply the dominated convergence theorem to deduce that yp is twice-differeetiall
with gradient given by Vn(p(n) = E X)] and Hessian given by V2(p()) = E1 [V, (1;; X)]-
Finally, since the directional derivative of yp in the direction g is defined (5: Vy(((1)), we may plug in our expression for the gradient to deduce
(5% v))))) (5, R. [. SIX (IX)) 8] (1 a))((X)))
[r[((s)x(((X) > 5]-(1 -1-(1_a))6,,0(X)
(x((Ps)x(M(X)> > S] -1 33-11-a)ggXX]}
The result follows.
Unbounded scores
In this section, comment S, and given the sigmoid function g R R given by g(x) = T+e the composition g(5) is a.s. [0, 1]-valued. As the proof of Theorem 4.2 only requires boundedness, this allows one to obtain the generalization bound for arbitrary score functions.
assumption that S E [0, 1] a.s. Given an arbitrary a.s. finite score
However, the proof of Theorem 4.3 places a boundedness assumption on the conditional density of S|X in Condition 5 which precludes from directly applying the transformation trick given above. We claim that Condition can be replaced with the following alternate condition:
Condition 11. (1) The conditional density fs|x=s exists for all E X; (2) there exists a constant Cj and real k > 0 such that for all (0, 1), we have
fs)x=z(s) < Cy(
11 - s/ k)
uniformly in x E X: (3) the basis &b obeys
sup Eilty x(X)) $1 < 20, yES1-1
and (4) the quantity Bupper defined in Lemma Condition
I.4 obeys Bupper < Co. where Co is defined in
In other words, we can allow the conditional density of S|X = x to diverge at a polynomial rate near = 0 and 8 = 1, so long as & obeys a certain moment condition, and so long as apriori, the population LR-QR objective can be restricted to a sufficiently small ball.
One can consider point (3) of Condition I as a slight strengthening of Condition 6 quantitative independence condition on the basis functions. Regarding point (4) of Condition note that by inspecting the definition of B Bupper. we see that an upper bound on B Bupper imposes (a) lower bound on Calign Condition 7 as well as (b) an upper bound on E, [ea (8*rH, 5)), which states that optimally scaling the projection l'H can yield a threshold function with low pinball loss.
Now, sketch how utilizing Condition 11 lipliies Theorem 4.3 for unbounded scores. In the original
proof, Condition 5 is used in order to control expressions of the Form E2 ( ((())T)))))))))) Jssjx (h(X) X))
uniformly for Rd with 0 < Blower & I|yll & Buppere where h(X) (y: ((X)). By Condition and Jensen's inequality, this is bounded by EE, [[[[ (x(()))XX)))))))))
[I], up to constants. By point (2) of
Condition 11 this in turn bounded by TE, [|x(x]
x(x))=*,, up to constants. By point
(3) of Condition and the bounds < Blower & || < Bupper, the first term [x)) is uniformly bounded. Next, by the triangle inequality, the Cauchy-Schwan inequality, Condition and point (4) of Condition we have
h(X) > 1 [n(X)| > 1 Co > 0,
so we may uniformly bound the second term by
[ h h(x)==* < (1 Co Bupper)
Putting these bounds together, we that Condition 11 provides the desired uniform control.
34

---

Finally, if we utilize Condition 11 instead of Condition 5 then the sigmoid transformation allows us generalize Theorem 4.2 beyond bounded scores. Note that for g, the conditional density f((s) of the transformed score (S) obeys
1
t 1-) [og 1
f(())|==x(t) t(1 1) fsxx=
for all t (0, 1). Consequently, if the original density fsix=a(s) is supported on R with polynomially-decaying tails as + =o, then the transformed density diverges like (t(1 t)) -))=(1)(11 t 0, 1, which satisfies Condition 11 with k for any
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims in the abstract and introduction are supported by the theoretical results Section and the experiments Section 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of work in the Discussion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
36

---

Justification: All theorems are always stated with their required assumptions, and full proofs are provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All experimental details are provided in Section 5, including dataset informa- tion. An open-source GitHub repository will be released upon publication.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
37

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: The software package implementing method and reproducing the experi- ments will be released as an open-source GitHub repository upon publication. The datasets used are publicly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
y /nips. /nips.cc//ppp httpppplllcggiieeeeeeeeeeee
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The experimental settings are described in Section 5. We evaluate pretrained models without training.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Our plots include error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
38

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
We perform small-scale experiments and provide sufficient detail on the set-up.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: /tt::://nuuuiie /t///enuip.... cc.ppublic/tthiccccccde.......
Answer: [Yes]
Justification: aspects.
The research conducted in this paper follows the NeurIPS Code of Ethics in all
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss the potential social impact of our work in the Discussion section.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
39

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not involve the release of any pretrained models, image generators, or datasets that pose high risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All datasets and sources used in this paper are properly cited.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
40

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
41

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core methodology in this research does involve LLMs.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy bettts://neurre http://earrrreecooooeeereee/e/// cc//oomferencee/22255ILI. for what should or should be described.
42


Reviews:
[{"review_id": "pB2Sjlgq2O", "reviewer": "Reviewer_KaEA", "summary": "This manuscript considers conformal prediction under high-dimensional covariate shift. The\nauthors introduce the Likelihood Ratio-Regularized Quantile Regression (LR-QR) algorithm. By\ncombining the pinball loss with a suitable choice of regularization, the authors construct a threshold\nfunction by getting around direct estimation of the unknown likelihood ratio, which can be difficult\nin high-dimensional setting. The authors provide theoretical properties and experiments to back up\ntheir proposed method.", "questions": "\\textbf{Questions:}\n\n\\begin{itemize}\n\\item Key symbols $\\mathbb{P}_1$ and $\\mathbb{P}_2$ are not consistently defined or used, Their meanings and usage vary between Sections 1 and 2.\n  \n    1. Lines 25–26: The statement ``In the case that the calibration and test distributions coincide ($\\mathbb{P}_1 = \\mathbb{P}_2$), ...\"\n    does not align with the definition of $\\mathbb{P}_1$ and $\\mathbb{P}_2$:  $\\mathbb{P}_1$ is defined over both inputs and outputs, \nwhile $\\mathbb{P}_2$ is defined only over inputs (Lines 21–22).\n\n    2. Lines 36–37: In the definition of the likelihood ratio function $r(x) = d\\mathbb{P}_{2,X}/d\\mathbb{P}_{1,X}$, the \ndistributions  $P_{2,X}$ and $P_{1,X}$ are not clearly defined in Section 1,\n though they appear more explicitly (yet still implicitly) in Section 2.\n  \n\\item Line 100: The prediction set $C: \\mathcal{X} \\rightarrow 2^{\\mathcal{Y}}$ suggests that the output space $\\mathcal{Y}$ is discrete (e.g., for classification). If the method is intended for regression,\n the terminology \"prediction set” could be adjusted to `\"prediction interval/region,” \nor the authors should clarify that the method is focused on classification.\n\n\\item Lines 105–106: It states, ``In this paper, a linear hypothesis class refers to a linear subspace of functions \nfrom $\\mathcal{X} \\rightarrow \\mathbb{R}$ that are square-integrable with respect to $\\mathbb{P}_{1,X}$.” \nWhy is this class particularly considered? Provide motivation or justification.\n\n\\item Lines 111–113: Calibration data are assumed to be i.i.d., which may be unnecessarily restrictive. One strength of conformal prediction is its reliance on weaker assumptions such as exchangeability. Can the method be extended to exchangeable data? If not, explain why the i.i.d. assumption is essential.\n\n\\item Notation inconsistency: The function $C(x)$ is defined differently in Lines 100 and 118 using different threshold symbols $q(x)$ and $\\tilde{q}(x)$. This variation seems unnecessary. Define $C(x)$ once and refer to it consistently.\n\n\\item Line 170: The statement that valid coverage is guaranteed if ${\\cal H}$ is linear and contains the true likelihood ratio $r$ implicitly requires $r$ to be linear. How plausible is this in real-world settings? Provide discussion or examples to help evaluate the adequacy of restricting ${\\cal H}$ to linear functions.\n    How likely would\n this happen for distributions often used in applications? \n    Provide discussion or examples to help evaluate the adequacy of restricting ${\\cal H}$ to linear functions. While it is understood that focusing on\n the linear hypothesis class ${\\cal H}$ can be critical in establishing meaningful theoretical results, a natural concern is its feasibility or adequacy in handling various practical distributions.\n\n\\item Lines 181–183: The lower bound involving $-E_1[(r(X) - r_{\\cal H}(X))^2]^{1/2}$ is derived via the Cauchy–Schwarz inequality. Given the indicator function’s $\\{0,1\\}$ values, could a tighter bound, such as $\\max(0, E_1[r(X) - r_{\\cal H}(X)])$, be used to describe the lower bound in Line 185?\n\n\\item Lines 212–213: Why is a fixed collection $\\Phi = (\\phi_1, \\ldots, \\phi_d)^\\top$ of $d$ basis functions assumed? What is $d$? Is it related to $\\dim(X)$?\n    (The dimension of $X$ does not appear to be explicitly represented using a dedicated notation.)\n    How are these basis functions chosen?\n\n\\item Lines 212–214: The introduction of interval ${\\cal I}$ appears to restrict the domain of the minimization in (LR-QR) from $\\beta \\in \\mathbb{R}$ to a compact subinterval of positive values. Justify this restriction and explain its impact on the solution.\n\n\\item Line 214: The $B$-ball ${\\cal H}_B$ defined in Line 214 depends on the choice of $B$, which in turn may influence the solution $(\\hat h, \\hat \\beta)$ in (3). However, the  results in Theorems 4.2 and 4.3 do not explicitly depend on $B$. Is this discrepancy  meaningful? The lack of $B$ in the bounds  makes to statements in Lines 239-240 less meaningful, though one may intuitively understand the impact of varying the value of $B$.\n\n \\item Line 233: What is $r_B(X)$ in Theorem 4.3? It is used without prior definition.\n\n   \\end{itemize}\n\n\n\n\n\\textbf{Suggestions:}\n\n\\begin{itemize}\n\n\\item The example in Lines 106–110 does not seem to be helpful. It can either be removed or further explained in terms of its relevance to the subsequent development.\nThe description of the “linear hypothesis class” in Lines 105–106 could be moved to the location around Line 122, where the linear hypothesis class ${\\cal H}$ first appears.\n\n\\item Clearly describe the key notations  $E_1$ \nand $E_2$ in relation to\nthe distributions $P_{1,X}$ \nand $P_{2,X}$  \n(or even $P_1$ \nand $P_2$). This clarification will help align the use \nof $E_{\\mathbb{Q}}$ in Line 126 with the other notations.\nBy the way, $P$ and $Q$ in footnote 1 on page 3 should be written as $\\mathbb{P}$ and\n$\\mathbb{Q}$, respectively.\n\n\\item The equation labels “(LR-QR)” in Line 157 and “(Empirical-LR-QR)” in Line 163\nshould be changed to “(1)” and “(2)” to be consistent with numerical labels such as\n(3) in Line 217 and (4) in Line 226 (though authors might intend to use lettered names\nto emphasize the differences in those minimization problems).\n\n\\item In Lines 171–172, it would be helpful to also present the mathematical expression\nof the projection of $r$ onto ${\\cal H}$ in the Hilbert space.\n\n\\item In Line 119, use a symbol different from $S$ to represent a random variable\nto avoid confusion with the use of $S(\\cdot, \\cdot)$ as the nonconformity score defined in Line 98.\n\n\\end{itemize}\n\n(NOTE: For unknown reasons, some LaTeX symbols cannot be displayed properly  in the OpenReview display system, even though they appear properly in my locally compiled PDF).", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. Conformal prediction under covariate shift is an interesting problem that is of practical\nimportance. This manuscript proposes a promising method to handle such a problem.\n2, The proposed approach offers a natural and effective way to incorporate regularization techniques\nin situations where the likelihood ratio function is unknown. The underlying idea is both novel\nand well-justified.\n3. Theoretical results are provided to support the proposed methodology, and they are nontrivial\nto establish.\n4. The manuscript is generally well written, and the presentation follows a logical progression.\n\nWeaknesses:\n1. While the title and main text emphasize the consideration of ’high-dimensional covariate\n(shift),’ the manuscript lacks a clear discussion of this feature. How high is the dimension of\nthe covariate X? Is it treated fixed or diverging with the data size? Relative to the sizes $n_1$, $n_2$,\nand $n_3$ for labeled or unlabeled source data points and target data points, how large is the\ndimension of the covariate? How do different dimensionality settings influence the theoretical\ndevelopments, including the established bounds, regularity conditions, and proofs?\n2. The presentation can be improved with careful revision. Several notations are used inconsistently\nor unclearly, and further clarification is needed in several places (see specific comments below)", "was_revised": true, "final_justification": "I thank the authors for addressing my comments and suggestions on the initial submission. The rebuttal and the planned revisions are satisfactory, and I am pleased to raise my initial rating to 5.", "rebuttal": "We thank the reviewer for the helpful comments.\n\nWeakness 1: \"Elaborate on high dimensionality.\"\n\nResponse to Weakness 1:\nThis is a great question and merits a detailed answer. The reason why we have not already expanded on this in detail in the submission is due to space limitations; because it turns out that the characterization of allowed dimensionalities is quite subtle, as we explain next. \n\nOur theoretical results are meaningful as long as the dimension $d$ of the function class does not grow too rapidly with $n_1$, $n_2$, and $n_3$. Specifically, in Theorems 4.2 and 4.3, $d$ appears implicitly in the constants, e.g., $c$, $c'$, $c''$, $A$, and $A'$. Explicitly, we have $A = A_{10}$ and $A' = A_{14}$, where the quantities $A_{10}$ and $A_{14}$ are defined in Appendix F. Although the exact formulae for $A$ and $A'$ are rather complicated, both $A$ and $A'$ depend only polynomially and inverse-polynomially on the following quantities: $\\lambda_{min}(\\Sigma)$, $\\lambda_{max}(\\Sigma)$, $c_{min}$, $c_{max}$, $B$, $C_{\\Phi}$, $C_{1,max}$, and $C_{1,upper}$, as defined in Appendix E.\n\nThe first four quantities depend on the choice of basis $\\Phi$ only through the smallest and largest eigenvalues of the population and sample covariance matrices $\\Sigma$ and $\\hat{\\Sigma}$, which entails a mild dependence on $d$.\nThe radius $B$ can be taken to be a constant.\nThe quantity $C_{\\Phi}$ can be taken to be a constant if the basis functions are normalized correctly.\nThe quantities $C_{1,max}$ and $C_{1,upper}$ depend polynomially on the preceding six quantities.\nThus, $A$ and $A'$ introduce only mild dependence on the complexity of the function class.\n\nTo illustrate the dependence on the dimension $d$ of the function class, suppose $\\Phi$ forms an orthonormal basis for $P_1$. Then applying the empirical sample covariance tail bound from Chapter 5.6 of [1], we have $\\lambda_{min}(\\hat \\Sigma) \\ge 1 - O(d \\log(dn_3)/n_3)$ with probability $1-o(n_3^{-1})$. This is of constant order if $d \\log(d) \\ll n_3$. So our bounds are meaningful if $d \\ll n_3/\\log(n_3)$, which allows a growing dimension.\n\nAlso, we would like to point out that in our experiments, $d = \\dim(H)$ is typically smaller than the dimension of the original input; for instance, in our pre-trained LLM experiment with GPT-2 Small, the context length (input dimension) is 1024, while the feature dimension is 768.\n\nWe would like to emphasize again that our key contribution is the development of a method that performs well empirically and has theoretical guarantees in such a high-dimensional case, which is not available in prior work.\n\nQ1 + Q2 + Q5: Notation.\n\nResponse to Q1 + Q2 + Q5: We thank the reviewer for the detailed comments. Indeed, LR-QR applies to both regression and classification tasks. We will fix this in the revision.\n\nQ3: \"Why a linear hypothesis class?\" \n\nResponse to Q3: \nIn our setting, we call a set of functions $H$\nfrom $\\mathcal{X}\\to \\mathbb{R}$\na \"linear hypothesis class\" if\n(1) $H$ forms a finite-dimensional vector space\nand\n(2) for each function $h\\in H$, the second moment $E_1[|h(X)|^2]$ is finite.\nOn a technical level, in our theoretical results, we leverage the linearity of $H$ \nto relate the first-order conditions of the LR-QR problem \nto the test-time marginal coverage under the covariate shift $r$.\nThis linearity is also the key property leveraged by\nthe pioneering work [2] in order to study conditional coverage. \n(For a detailed derivation of the connection\nbetween the first-order conditions of the LR-QR problem\nand the test-time marginal coverage,\nplease see the start of Section 3\nor the proof of Proposition 4.1.)\n\nWe would like to emphasize that a linear hypothesis class can be very rich and can contain highly nonlinear functions, e.g., the space of functions representable by linear combinations of the last-layer features of a pretrained model. This is the reason for the example in L105 (see also answer to the suggestion). Consequently, $r\\in H$ does not imply that $r$ is linear, and we do not view the assumption that $r\\in H$ as being restrictive in practice. \nIndeed, we perform experiments involving high-dimensional datasets:\nthe Communities and Crime dataset has a 127-dimensional input,\nthe RxRx1 dataset has a 512 pixel-by-512 pixel image input,\nand the MMLU dataset has a 1024-dimensional text input.\nIn these challenging settings,\nLR-QR performs extremely well,\nwhich is consistent with our assumption that $r$ lies within $H$ or close to $H$. \nThis underscores the fact that LR-QR is a practically significant algorithm\nin the high-dimensional setting,\nwith strong and meaningful theoretical guarantees.\n \nMoreover, we would like to emphasize that such a linear function class setting is now quite standard and well-accepted in the conformal prediction literature (see e.g., [3, 4, 5]), starting with the pioneering work of [2], which has been widely adopted in the community (e.g., cited more than 100 times).\n\nQ4: \"Why i.i.d.?\"\n\nResponse to Q4:\nIn the proof of our generalization bound in Theorem 4.2, we use the i.i.d. assumption to (1)  apply the stability result Lemma G.1 and (2) to apply Hoeffding's inequality to control empirical process terms that arise (e.g., Terms (III) and (IV) on page 25). At present, it is not clear how to extend the analysis to the exchangeable setting, but relaxing the i.i.d. condition is an interesting direction for further work.\n\nQ6.A: \"Is $r$ linear?\"\n\nResponse to Q6.A:\nWe would like to clarify that a linear hypothesis class can be very rich and contain highly nonlinear functions, e.g., the space of functions representable by a pretrained model with a scalar read-out layer. Consequently, $r\\in H$ does not imply $r$ is linear.\n\nQ6.B: \"How plausible is $r\\in H$? Include examples.\"\n\nResponse to Q6.B:\nAs discussed in the response to Q3 and above, a linear hypothesis class with non-linear features can include non-linear functions. In many applications involving conformal prediction, one leverages pre-trained predictors (e.g., neural networks) to compute appropriate score functions and use split conformal calibration. In such settings, we can also leverage the associated features used in the pre-trained models, e.g., last-layer features of a neural net. Whenever such features explain the covariate shift (i.e., are good for classifying the source vs target domains), our approach is quite likely to perform well.\n\nQ7: \"Strengthen the misspecification lower bound?\"\n\nResponse to Q7:\nWe thank the reviewer for the suggestion. Indeed, since $\\mathbf{1}[S(X,Y)\\le h^*(X)]$ only takes on the values $0$ and $1$, we have\n$$ E_1[(r(X) - r_{H}(X)) \\mathbf{1}[S(X,Y)\\le h(X)] ] \n\\le E_1[\\max(0, r(X) - r_{H}(X))],$$\nhence we can improve the coverage lower bound on line 185 to\n$$P_2[Y\\in C(X)]\\ge (1-\\alpha) - E_1[\\max(0, r(X) - r_{H}(X))].$$\nWe will add this in the revised paper.\n\nQ8: \"How to specify $\\Phi$?\"\n\nResponse to Q8:\nIn our theoretical results, the functions $\\Phi = (\\phi_1,\\ldots,\\phi_d)^\\top$ form a basis for the linear hypothesis class $H$,\nso $d = \\text{dim}(H)$ is the dimension of the feature space. \nIn practice, we do not need to explicitly write out $\\Phi$. We simply choose a set of features and perform gradient descent over it. Our method returns the same results as long as we have specified a fixed linear space, regardless of the parametrization (so we do not need to find an orthogonal basis $\\Phi$).\n\nThe dimension of $H$ is an algorithmic choice (e.g., how many pretrained features) and is independent of the dimensionality $\\text{dim}(\\mathcal{X})$ of the original input space.\n\nThe reason why we have not introduced a dedicated notation for $\\dim(\\mathcal{X})$ is that it is never used anywhere. Only $\\dim(H)$ affects the optimal regularization strength $\\lambda^*$ for the LR-QR algorithm.  We will clarify this in the revision.\n\nQ9 + Q10: \"Justify the restrictions $\\beta\\in \\mathcal{I}$ and $\\|h\\| \\le B$ in LR-QR.\"\n\nResponse to Q9 + Q10:\nIn Lemma L.4 of the appendix, we show that the unconstrained population solution lies within the region $\\mathcal{I}\\times H_B$, so at the population level, one loses nothing by restricting to $(\\beta, h) \\in \\mathcal{I}\\times H_B$. This justifies the restriction to $B$ in our algorithm.\n\nRegarding the dependence of the bounds in Theorems 4.2 and 4.3 on $B$, $B$ appears in the quantities\n$c$, $c'$, $c''$, $A$, and $A'$ (we will make this clear in the revision). We provide explicit formulae for these quantities in the proofs of Theorems 4.2 and 4.3, in terms of the quantities defined in Section F of the Appendix. It can be seen that these quantities depend only polynomially on $B$. We will add a detailed discussion to the final version. \n\nQ11: \"Definition of $r_B(X)$?\"\n\nResponse to Q11:\nWe define $r_B$ on lines 229-230 prior the theorem; $r_B$ denotes the orthogonal projection of $r$ onto the closed convex set $H_B$ in the Hilbert space induced by the inner product $\\langle f,g\\rangle = E_1[fg]$. We will link to the definition in the revision.\n\nSuggestions: Thank you! We will make all the changes.\n\nResponse to S1: We thank the reviewer for this suggestion, we can move this to later. The reason for introducing it was to explain how linear spaces can cover non-linear functions in ML, and thus to motivate our approach.\n\nResponse to S2: $E_i$ are defined on line 95. We will fix the footnote in the revision.\n\nResponse to S3: As you suggested, we used these labels for added emphasis; we hope this is alright.\n\nResponse to S4: We will add this in the revision.\n\nResponse to S5: We will add this in the revision.\n\n[1] Vershynin. \"High-dimensional probability\".\n\n[2] Gibbs et al., \"Conformal prediction with conditional guarantees\".\n\n[3] van der Laan et al., \"Generalized Venn and Venn-Abers Calibration with Applications in Conformal Prediction\".\n\n[4] Bairaktari et al., \"Kandinsky Conformal Prediction\".\n\n[5] Cherian et al., \"Large language model validity via enhanced conformal prediction methods\"."}, {"review_id": "l130xV3LkX", "reviewer": "Reviewer_im4Q", "summary": "This paper introduces a conformal prediction method for the covariate shift setting (i.e. when the distribution of the $X$ in the test set is different from the distribution of the $X$ in the calibration set). Whereas existing methods require the estimation of a particular likelihood ratio function, the authors here present an algorithm, called likelihood ratio regularized quantile regression (LR-QR), which outputs a threshold function without directly estimating the likelihood ratio. To do this, they assume that unlabeled data from both distributions are available and minimize a particular objective function (Eq. in line 163). They show theoretically that when there is no estimation error (i.e. expectations are known) and under several assumptions, the function produced by the optimizer achieves valid coverage in the test domain. In the finite sample setting, the validity becomes asymptotic if the class of functions on which we optimize is sufficiently large. Finally, they show the effectiveness of their method on several data sets.", "questions": "1\\ Is Proposition 4.1 true for any $\\lambda$? If yes, I do not understand where is the impact of this hyper-parameter.\n\n2\\ Furthermore, if there is no impact, is the intuition being that in the infinite sample size setting, if the true $r$ is in $H$ then we do not need to regularized the objective as the optimizer is going to return $r$ anyway?\n\n3\\ Line 121: Why $h$ need to be in a linear hypothesis class H ?\n\n4\\ Do you think it could be possible to use the $X$ from $P_{1, X}$ of the calibration instead of assuming that we have another unlabeled set?\n\n5\\ In Eq (4), you provide an optimal value for $\\lambda$. Is this value consistent with the one obtained across all the experiments? (not only Figure 4).", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1) The paper is well-written and the problematic is well motivated.\n\n2) The main idea is interesting and well-presented.\n\n3) This line of research is of particular interest for the CP community.\n\nWeaknesses:\n\n1) The supplementary material does not include the code necessary to run the algorithm. Providing this code would improve reproducibility.\n\n2)  The experimental section lacks clarity compared to the theoretical section (reason why I put a borderline accept but I am willing to increase it because overall this is a good paper).\n    \n     2.1) Section 5.2 \"Communities and Crime\": This section is unclear (at least for me), particularly regarding how the covariate shift is simulated.\n\n    2.2) The results on the size for LR-QR appear to be missing.\n\n    2.3) It is unclear where the results for the coverage of LR-QR are presented in Figure 1.\n\n    2.4) There is no error bar in Table 1.\n\n3) The conclusion only contains one limitation (and this limitation is not clear to me) --> Line 356 : \"to have results that control of the slack in coverage\" ??", "was_revised": true, "final_justification": "I was positive about this article. After the rebuttal and based on the other reviews, I am sticking with my rating.", "rebuttal": "We thank the reviewer for the helpful comments.\n\nWeakness 1: \"Providing code.\" \n\nResponse to Weakness 1: \nOur code is currently ready to be shared; \nhowever, the conference does not allow us to share links,\notherwise we would include it here.\nAs a result, we will include our code with the revised paper.\nWe thank the reviewer for their interest.\n\nWeakness 2: \"Experimental details?\"\n\nResponse to Weakness 2: \n\nRegarding point (2.1), \nwe thank the reviewer for allowing us to clarify the Communities and Crime experiment.\nOur description of the Communities and Crime experiment\nin Section 5.2 contained a typo, which we would like to correct here.\nIn the experiment,\nwe design four distinct covariate shifts,\nrun the LR-QR algorithm in each of the four scenarios,\nand evaluate the marginal coverage in the test domain.\nTo elaborate,\nlet us assign the index $i = 1$ to the Black subgroup,\n$i=2$ to the White subgroup,\n$i=3$ to the Asian subgroup,\nand $i=4$ to the Hispanic subgroup.\nLet $Z$ denote the set of datapoints\nthat were not used for training the regression model.\nThen, for each $i\\in [4]$,\nwe design a covariate shift between calibration and test\nas follows:\nthe $i$-th calibration set $Z_{cal,i}$ includes \nall individuals in $Z$\nthat are not of race $i$,\nand the $i$-th test set\nincludes \nall individuals in $Z$\nthat are of race $i$.\nThus, for each $i\\in [4]$, \nwe induce a covariate shift \nbetween $Z_{cal,i}$ and $Z_{test,i}$,\nshifting probability mass from \n\"not race $i$\"\nto \"race $i$\".\nIn Figure 1, we evaluate each algorithm on each of the four experimental setups.\nOur results show that on this challenging 127-dimensional task,\nthe LR-QR algorithm achieves excellent marginal coverage at test-time,\nfor each of the four distinct choices of covariate shift.\nWe thank the reviewer for this question regarding the choice of covariate shift in Section 5.2.\nDue to space limitations, we were unable to elaborate in the initial submission.\n\nRegarding points (2.2) through (2.4), we thank the reviewer for catching the error in the legend;\nwe will correct this in the revised version.\nIn Figure 1, for each race, the left-most bar (in blue) denotes LR-QR.\nWe are also happy to add error bars to Table 1 in the revised paper (they are quite small and do not change the interpretation of the results).\n\nWeakness 3: \"Clarify the limitation?\"\n\nResponse to Weakness 3:\nIn the limitation stated in the Discussion section,\nwe mean that\nit would be of interest in future work\nto study the error terms appearing in the coverage lower bound\nin Theorem 4.3.\nIn particular, it may be possible to understand these terms\nwhen optimizing over particular function classes,\nor under certain assumptions on the true likelihood ratio $r$.\nWe believe this could shed further light on the practical efficacy\nof the LR-QR algorithm, \nand strengthen our theoretical guarantees.\n\nQ1 + Q2 - \"Clarify effect of $\\lambda$ in Proposition 4.1; clarify the infinite-sample setting?\"\n\nResponse to Q1 + Q2:\nIndeed, in the statement of Proposition 4.1, $\\lambda$ does not appear in the lower bound of $(1-\\alpha)$; however, in the proof, we show that the lower bound can be improved to\n$$\\ge (1-\\alpha) + 2\\lambda \\beta E_1[ (r_{H}(X) - \\beta h(X))^2 ],$$\nwhere $(\\beta, h)$ denotes the population LR-QR solution, which in turn depend on $\\lambda$. \nThis shows that, at the population level, $\\lambda$ has an effect, which is however not straightforward to interpret---for instance, the term $\\lambda \\beta E_1[ (r_{H}(X) - \\beta h(X))^2 ]$ above is of course non-monotone in $\\lambda$ in general. For conciseness, we have omitted this discussion from the paper, but we are happy to add it. \n\nThe question of whether the optimization problem returns the true $r$ is interesting but perhaps surprisingly subtle, as this does not seem to follow directly from our analysis. However, regardless of this question, if $r$ lies in $H$, then even in the case of zero regularization, the LR-QR threshold achieves valid test-time coverage. However, the solution of the optimization problem in this case is not $r$ itself, but rather the conditional quantile function (as the problem is unregularized quantile regression).\n\nQ3: \"Why do we assume a linear class?\"\n\nResponse to Q3:\nOn a technical level, in our theoretical results, we leverage the linearity of $H$ \nto relate the first-order conditions of the LR-QR problem \nto the test-time marginal coverage under the covariate shift $r$.\nThis linearity is also the key property leveraged by\nthe pioneering work [2] in order to study conditional coverage. \n(For a detailed derivation of the connection\nbetween the first-order conditions of the LR-QR problem\nand the test-time marginal coverage,\nplease see the start of Section 3\nor the proof of Proposition 4.1.)\n\nWe would like to emphasize that a linear hypothesis class can be very rich and can contain highly nonlinear functions, e.g., the space of functions representable by linear combinations of the last-layer features of a pretrained model. Consequently, $r\\in H$ does not imply that $r$ is linear, and we do not view the assumption that $r\\in H$ as being restrictive in practice. \nIndeed, we perform experiments involving high-dimensional datasets:\nthe Communities and Crime dataset has a 127-dimensional input,\nthe RxRx1 dataset has a 512 pixel-by-512 pixel image input,\nand the MMLU dataset has a 1024-dimensional text input.\nIn these challenging settings,\nLR-QR performs extremely well,\nwhich is consistent with our assumption that $r$ lies within $H$ or close to $H$. \nThis underscores the fact that LR-QR is a practically significant algorithm\nin the high-dimensional setting,\nwith strong and meaningful theoretical guarantees.\n \nMoreover, we would like to emphasize that such a linear function class setting is now quite standard and well-accepted in the conformal prediction literature (see e.g., [2, 3, 4]), starting with the pioneering work of [1], which has been widely adopted in the community (e.g., cited more than 100 times).\n\nQ4: \"How to obtain unlabeled calibration data?\"\n\nResponse to Q4:\nIndeed, given datapoints $\\{ (X_i, Y_i) : i\\in [n_1+n_3] \\}$\ndrawn i.i.d. from $P_1$, we can split the data into\na labeled calibration set \n$\\{ (X_i, Y_i) : i\\in [n_1] \\}$\nand an unlabeled calibration set\n$\\mathcal{S}_3 = \\{ X_i : i\\in [n_1] \\}$\nby simply dropping the label $Y_i$ from $(X_i, Y_i)$ for $n_1+1 \\le i \\le n_3$.\n\nHowever, to achieve provable coverage guarantees, our current approach requires the two datasets to be indepenent.\nThus, it is not possible to set the unlabeled calibration set $\\mathcal{S}_3$\nto be equal to the features $\\{ X_i : i\\in [n_1] \\}$\nof the labeled calibration data $\\{ (X_i, Y_i) : i\\in [n_1] \\}$;\nif we reuse data in this way, then we violate the i.i.d. assumption that is necessary for our theoretical guarantees.\n\nQ5: \"Is the theoretical $\\lambda$ consistent with the experimental $\\lambda$?\"\n\nResponse to Q5: \nThis is a great question.\nAs shown in Figure 4 of Section B of the Appendix,\nfor the Communities and Crime task,\nthe regularization strength selected through cross-validation\naligns closely with\nthe regularization strength suggested by our theory in Equation (4).\nIn the other two experiments, we observe similar trends, \nwhere the selected regularization is consistent with our theory. \nUnfortunately, with the revised conference rules, we are unable to provide the resulting plots.\nWe are happy to elaborate in the revised paper.\n\n[1] Gibbs et al., \"Conformal prediction with conditional guarantees\".\n\n[2] van der Laan et al., \"Generalized Venn and Venn-Abers Calibration with Applications in Conformal Prediction\".\n\n[3] Bairaktari et al., \"Kandinsky Conformal Prediction\".\n\n[4] Cherian et al., \"Large language model validity via enhanced conformal prediction methods\"."}, {"review_id": "wINPnKDe1w", "reviewer": "Reviewer_wABN", "summary": "This paper addresses the problem of conformal prediction under covariate shift, where the distribution of features differs between a source (calibration) and a target (test) domain. The authors propose a new method called Likelihood Ratio Regularized Quantile Regression (LR-QR) to construct prediction sets that achieve valid coverage in the target domain without explicitly estimating the density ratio $r(x)=dP_{2,X}/dP_{1,X}$ (which can be prohibitive at high dimensions). The key idea is to incorporate a regularization term into a quantile regression target that implicitly encourages the learned threshold function $h(x)$ to adapt to the unknown likelihood ratio.\n\nThe paper addresses the problem of constructing conformal prediction sets under covariate shift—when calibration data comes from a source distribution $P_1$ and test data from a different target distribution $P_2$ sharing the same $Y\\mid X$ but with shifted marginals (pp. 1–2). Existing methods often estimate the density-ratio\n\n$$\nr(x)\\;=\\;\\frac{dP_{2,X}}{dP_{1,X}}(x),\n$$\n\nwhich is challenging in high dimensions (p. 2).\n\n---\n\n## Method (LR-QR)\n\nThe authors propose **Likelihood-Ratio Regularized Quantile Regression** (LR-QR), which replaces direct ratio estimation with a novel regularizer in a quantile-regression objective (pp. 3–4). Concretely, they solve\n\n$$\n\\min_{h,\\;\\beta}\\;\\mathbb{E}_{P_1}\\bigl[\\ell_\\alpha\\bigl(h(X),S(X,Y)\\bigr)\\bigr]\n\\;+\\;\\lambda\\;\\mathbb{E}_{P_1}\\bigl[(\\beta\\,h(X)-r(X))^2\\bigr],\n$$\n\ninvolving only \\(\\mathbb{E}_{P_1}[h^2]\\) and \\(\\mathbb{E}_{P_2}[h]\\), both easily estimated from unlabeled samples (pp. 4–5; Algorithm 1).\n\n---\n\n## Theory\n\n* **Population regime:**\n  If the hypothesis class contains the true ratio $r$, LR-QR attains exact $(1-\\alpha)$-coverage under $P_2$ (Prop. 4.1, p. 5).\n\n* **Finite-sample regime:**\n  They prove a generalization bound (Theorem 4.2, p. 6) showing the empirical minimizer’s risk is within\n\n  $$\n    O\\Bigl(n_1^{-\\tfrac13}\\,(n_2+n_3)^{-\\tfrac13}\\Bigr)\n  $$\n\n  of optimal, and derive a coverage guarantee (Theorem 4.3, p. 7) that the test-domain coverage is at least $(1-\\alpha)$ minus controllable error terms.  The optimal regularization scales as\n\n  $$\n    \\lambda \\;\\propto\\; n_1^{-\\tfrac13}\\,(n_2+n_3)^{-\\tfrac13}\n    \\quad\\text{(Eq. 4, p. 6).}\n  $$\n\n---\n\n## Empirical Results\n\nOn three high-dimensional benchmarks, LR-QR consistently tracks nominal coverage and yields competitive (often smaller) set sizes:\n\n1. **Communities & Crime** regression under four race-based splits (Fig. 1).\n2. **RxRx1** cell-image classification across 14 biological batches (Fig. 2).\n3. **MMLU** multiple-choice with an LLM (Table 1).\n\nAn ablation over $\\lambda$ confirms that moderate regularization (theory-predicted regime) best balances coverage and efficiency (Fig. 4, p. 14).\n\n---\n\n**Overall**, LR-QR offers a scalable, theoretically grounded approach to conformal prediction under high-dimensional covariate shift **without** explicit ratio estimation, backed by strong empirical performance.", "questions": "- A minor problem in terms of technical quality is the fact that the theory is based on certain assumptions. For example, the main coverage guarantee assumes a linear hypothesis class (and even then conditions such as strong convexity or an independence condition for features according to Appendix E/F are required). In practice, authors restrict $H$ to linear functions (often a linear layer over a pre-trained representation), which is consistent with theory, but this can limit the flexibility of $H$ to approximate $r(x)$ when $r(x)$ is very complex. It is understandable that generalizing the theory to nonlinear or very large function classes is challenging (due to overfitting concerns), and the work mitigates this problem by using representation learning (pre-trained models) to make linear $H$ more expressive. Nonetheless, the overfitting guarantee is asymptotic in finite samples and up to an error term, and it depends on conditions that are not completely under the control of the experimenter (e.g., how well $r(x)$ lies within the range of the chosen features). This is not a critical flaw, – just a recognition that, as with any theory-heavy work, practical performance depends on how well reality matches assumptions. - The experimental results suggest that the method is robust, but the paper could be strengthened by a brief discussion of how sensitive the coverage is to misspecification of $H$ or violation of the assumptions (the appendix addresses this with the distance term $||r - r_H||$, but it might be worth highlighting this in the main text). Another minor quality issue is that the method introduces an additional hyperparameter $\\lambda$; while theory dictates the order, in practice the exact choice is tuned – however, the paper handles this well via cross-validation, so I don’t see it as a major drawback.\n- One area where clarity could be improved is the explanation of the “Algorithmic Principles” (section 3) – in particular lines 117–129 of the draft. The derivation presented there is somewhat difficult to follow and seems a little sloppy in its current form. In this section, the authors use the first-order optimality conditions of quantile loss minimization to argue that if the hypothesis class $H$ contains a function proportional to the ratio of the true density, then the learned predictor achieves exact coverage under this covariate shift. While the idea is sound, the explanation is rather poor. Essentially, it imposes the condition that at the optimum $h^(x)$, the expected gradient in each direction $g(x)$ in $H$ is zero. By inserting a special choice $g(x) = \\frac{dQ_X}{dP_{1,X}}(x)$ (the Radon-Nikodym derivative of a shifted distribution $Q$ after that of the source distribution), they deduce that $\\mathbb{E}_{P_1}[g(X)(\\mathbf{1}{S \\le h^(X)} - (1-\\alpha))] = 0$ implies that $\\mathbb{E}_{Q}[,\\mathbf{1}{S(X,Y) \\le h^(X)},] = 1-\\alpha$. In other words, the prediction set defined by $h^$ has an exact $(1-\\alpha)$ coverage under any covariate shift $Q$ whose density ratio is in $H$. The paper’s presentation quickly skips through these steps. I find the argument in Cherian and Gibbs clearer to follow.", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The technical quality of the paper is high. The methodology is derived from sound principles of quantile regression and importance weighting, and the authors provide a rigorous theoretical analysis to support their claims. In particular, Proposition 4.1 and its corollaries prove that the LR-QR solution achieves valid target coverage in the population setting if the hypothesis class contains the true density ratio (and even if it does not, one can quantify the coverage gap). This is a non-trivial theoretical guarantee, and the proof (which has been moved to the appendix) seems to use tools from learning theory (stability bounds, etc.) to deal with finite sample deviations. The paper also relies on a novel analysis of coverage by stability – this suggests that the theoretical results are quite advanced and not just a routine application of existing theorems. The derivations appear to be mathematically sound, given the stated regularity conditions (e.g. linear hypothesis space, integrability and convex assumptions in Appendix E). I found no errors in the reasoning, and important steps  are adequately justified (footnote 1). The authors even derive a guideline for the choice of the regularization parameter $\\lambda$ in practice based on the trade-off of terms of order $1/\\sqrt{n_1}$ and $1/\\sqrt{n_2}$ (number of labeled vs. unlabeled points), which is a valuable insight to avoid ad hoc tuning.\n\nExperimental validation is another strong point: the paper evaluates LR-QR in three different domains (tables, vision, NLP) and compares it to six baselines, showing superior or comparable performance. It is shown that LR-QR achieves coverage very close to the nominal 90% in the target domain, whereas some baselines fall short (e.g., the default split conformal method under Shift drops to ~78% coverage) or overshoot (some robust methods exceed 95% coverage because they are too conservative). At the same time, LR-QR maintains smaller prediction sets than the overly conservative methods, indicating a favorable trade-off between validity and efficiency. The authors also perform  cross-validation to select $\\lambda$ (theory-guided) without using test labels, and an ablation study of regularization (Appendix B) to provide deeper insight.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful comments.\n\nQ1: \"Justify regularity conditions.\"\n\nResponse to Q1:\nWe thank the reviewer for the insightful questions about the regularity conditions. \n\nRegarding the conditions on $H$,\nwe would like to emphasize that a linear hypothesis class can be very rich and can contain highly nonlinear functions.\nIn our setting, we call a set of functions $H$\nfrom $\\mathcal{X}\\to \\mathbb{R}$\na \"linear hypothesis class\" if\n(1) $H$ forms a finite-dimensional vector space\nand\n(2) for each function $h\\in H$, the second moment $E_1[|h(X)|^2]$ is finite.\nIn particular,\nthe space of functions representable by linear combinations of the last-layer features of a pretrained model\nis an example of a linear hypothesis class.\nConsequently, $r\\in H$ does not imply that $r$ is linear, and we do not view the assumption that $r\\in H$ as being restrictive in practice. \n\nOn a technical level, in our theoretical results, we leverage the linearity of $H$ \nto relate the first-order conditions of the LR-QR problem \nto the test-time marginal coverage under the covariate shift $r$.\nThis linearity is also the key property leveraged by\nthe pioneering work [2] in order to study conditional coverage. \n(For a detailed derivation of the connection\nbetween the first-order conditions of the LR-QR problem\nand the test-time marginal coverage,\nplease see the start of Section 3\nor the proof of Proposition 4.1.)\n\nMoreover, we would like to emphasize that such a linear function class setting is now quite standard and well-accepted in the conformal prediction literature (see e.g., [2, 3, 4]), starting with the pioneering work of [1], which has been widely adopted in the community (e.g., cited more than 100 times).\n\nRegarding the effect of misspecification on the coverage lower bound, the last term $-(1-\\alpha) E_1[|r(X)-r_B(X)|]$ in the lower bound in Theorem 4.3 accounts for the fact that our guarantee is weaker if the $L^1$ distance from $r$ to $H$ is large. We hope this addresses the concern of how sensitive the coverage is to misspecification, and we will be happy to add a more detailed discussion to the paper.\n\nFinally, we would like to note that our experiments are consistent with our regularity conditions.\nWe perform experiments involving very high-dimensional datasets:\nthe Communities and Crime dataset has a 127-dimensional input,\nthe RxRx1 dataset has a 512 pixel-by-512 pixel image input,\nand the MMLU dataset has a 1024-dimensional text input.\nIn these challenging settings,\nLR-QR performs extremely well,\nwhich is consistent with the two regularity conditions discussed above. \nThis underscores the fact that LR-QR is a practically significant algorithm\nin the high-dimensional setting,\nwith strong and meaningful theoretical guarantees.\n\nOverall, we believe that our regularity conditions are practically reasonable, but we believe relaxing our conditions is an interesting future direction.\n\nQ1B. \"How to choose lambda?\"\n\nResponse to Q1B: \nAs the reviewer has noted, introducing the regularization term, which controlled by $\\lambda$, is a crucial contribution of our work.\nMoreover, as the reviewer mentioned, in practice it can be quite conveniently tuned using cross-validation. In fact, we have carefully studied this problem in Section 5.1, and designed a bespoke criterion to cross-validate on (because standard accuracy does not work--- we do not assume access to labeled data from the target domain). Overall, the choice of $\\lambda$ is an important issue, but we believe that our current approach handles it satisfactorily.\n\nQ2: \"Clarifications regarding Section 3.\"\n\nResponse to Q2:\nWe appreciate the detailed suggestions regarding the exposition in Section 3.\nOur presentation was quite compact due to the page limit, but we are happy to expand it in the final version.\nIndeed, the two crucial ideas we seek to convey in Section 3 are\n(1) the connection between the first-order optimal condition and the marginal coverage in the test domain, \nas introduced by [1],\nand\n(2) the motivation for our novel regularization,\nvia a data-dependent choice of the hypothesis class $H$.\nHere, we elaborate on (1) and lines 117-129,\nto clarify the key steps of the derivation.\nBy inspecting the definition of the pinball loss in Equation (1),\nwe see that the derivative of the pinball loss with respect to its first argument is given by\n$$\\frac{d}{dc} \\ell_{\\alpha}(c, s) \n= -(1-\\alpha) \\mathbf{1}[s>c] + \\alpha \\mathbf{1}[s\\le c]\n= \\mathbf{1}[s\\le c] - (1-\\alpha).$$\nCombining this identity and the chain rule,\nwe can calculate the directional derivative\nof $h\\mapsto E_1[ \\ell_{\\alpha}(h, S) ]$ in the direction $g$\nto be\n$$ \\frac{\\partial}{\\partial \\epsilon} E_1[\\ell_{\\alpha}(h+\\epsilon g, S)] \n= E_1\\left[ \\frac{\\partial}{\\partial \\epsilon} (h+\\epsilon g)  \n\\cdot \\frac{\\partial}{\\partial h} \\ell_{\\alpha}(h, S) \\right] \n= E_1[ g (\\mathbf{1}[S\\le h] - (1-\\alpha)) ],$$\nwhere in the first step we interchanged derivative and expectation,\napplied the chain rule,\nand evaluated at $\\epsilon=0$,\nand where in the second step we used the formula for the derivative of the pinball loss.\nWhen $g$ is the Radon--Nikoydm derivative $dP_{2,X}/dP_{1,X}$,\nthen as the reviewer rightly observes,\nthis allows us to apply the change-of-measure identity\nto the last expression to obtain $E_2[ \\mathbf{1}[S\\le h] - (1-\\alpha) ]$,\nwhere $E_2$ now denotes expectation with respect to the test distribution.\nFinally, since the expectation of an indicator can be written as a probability,\nour directional derivative becomes the marginal test-time excess coverage\n$P_2[S\\le h] - (1-\\alpha)$, as claimed.\nWe will update Section 3 with these comments in the revised paper.\n\n[1] Gibbs et al., \"Conformal prediction with conditional guarantees\".\n\n[2] van der Laan et al., \"Generalized Venn and Venn-Abers Calibration with Applications in Conformal Prediction\".\n\n[3] Bairaktari et al., \"Kandinsky Conformal Prediction\".\n\n[4] Cherian et al., \"Large language model validity via enhanced conformal prediction methods\"."}, {"review_id": "LCBdLhaxyg", "reviewer": "Reviewer_KYG7", "summary": "The authors address the problem of covariate shift in Conformal Prediction. The standard approach to establishing CP validity in that scenario requires estimating a likelihood ratio. The paper describes a computationally advantageous approach based on regularising the pinball objective used in quantile regression.", "questions": "- Does the \"linear hypothesis class\" contain non-linear regression models?\n- Setting $g=dP/dQ$ implicitly implies that the likelihood ratio is in the linear hypothesis class. How restrictive is this assumption?\n- The validity in Equation 2 is different from the finite-sample validity of Conformal Prediction. In [1], a threshold correction is estimated on a calibration set to conformalize the obtained intervals. How does that approach relate to the finite-sample setup in Section 4.2?\n- Does the correction in Theorem 4.3 account for the non-optimality of the likelihood ratio estimator, h? Can a similar bound be obtained for non-linear $h$?\n\n[1]\nRomano, Yaniv, Evan Patterson, and Emmanuel Candes. *Conformalized quantile regression.* Advances in neural information processing systems 32 (2019).", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 1, "originality": 3, "strengths_and_weaknesses": "**Strength**\n\nThe observation linking the optimum of the pin-ball objective and coverage under distribution shift is interesting. Is this the first time this has been observed and used to build an estimation approach?\n\n**Weaknesses**\n\nIt is unclear why the likelihood ratio *may be inaccurate for high-dimensional data*. As this is the motivation for their work, the authors can spend a few more words explaining the reasons for the claim. One of the simplest likelihood ratio estimators is based on fitting a logistic regression model, whose performance intuitively increases with the input dimensionality. The authors could have also run an ablation experiment to show that the likelihood ratio estimation becomes inaccurate in high dimensions.\n\nThe approach seems to require estimating a model for the likelihood ratio, exploiting the change-of-measure identity. The authors should clarify whether the idea has appeared elsewhere, why it can not be used to direct likelihood ratio estimation, and how it removes the high-dimensional inaccuracy.", "was_revised": true, "final_justification": "The authors provided all needed clarifications during the discussion period. I raised my score to 4 and would vote to accept the paper.", "rebuttal": "We thank the reviewer for the helpful comments.\n\nStrength 1:  \"The observation linking the optimum of the pin-ball objective and coverage.\"\n\nResponse to Strength 1:\nThis connection is known from the works [2, 3], as we have already stated in the paper (see line 121). However, our main innovation is the regularization term, which is both conceptually novel and significantly improves performance. We will be more clear about this in the revision.\n\nWeakness 1: \"Why is high-dimensionality hard?\" \n\nResponse to Weakness 1:\nIn general, estimating a high-dimensional function incurs the \"curse of dimensionality\", whereby accurate estimation at a single point requires an exponential number of nearby datapoints. More specifically, high-dimensional estimation has been widely studied in statistics and ML, and there are many results showing that even under pretty strong smoothness assumptions, this is very hard [5]. \n\nGiven that the likelihood ratio is a high-dimensional function when $\\text{dim}(\\mathcal{X})$ is large, likelihood ratio estimation suffers from similar hardness results.\nAs the reviewer suggests, a natural method for likelihood ratio estimation is through logistic regression.\nSpecifically, given i.i.d. samples $\\{ (X_i, Y_i) : i\\in [n] \\}$ with $X_i\\in \\mathbb{R}^d$ and $Y_i\\in \\{0,1\\}$,\none can fit a logistic regression model to obtain \na probabilistic classifier $\\hat p(x)$ that returns the predicted probability\nthat $x$ was sampled from class 1;\nthen, one returns the likelihood ratio estimate $\\hat r(x) = \\hat p(x) / (1 - \\hat p(x))$.\nHowever, in the literature, theoretical results show that logistic regression \nincurs large estimation errors in high dimension; see e.g., [8].\nHere, we numerically illustrate this phenomenon with the following simple setting.\nGiven a dimension $d$,\nand given a fixed sample size $n_{train} = 10000$,\nwe sample $n_{train}/2$ datapoints from $N(-\\frac{\\mathbf{1}}{\\sqrt d}, \\frac{1}{d} I_d)$\nand $n_{train}/2$ datapoints from $N(+\\frac{\\mathbf{1}}{\\sqrt d}, \\frac{1}{d} I_d)$,\nwhere $\\mathbf{1}$ denotes the vector of all ones,\nand $I_d$ denotes the identity covariance matrix.\nHere, datapoints from $N(-\\frac{\\mathbf{1}}{\\sqrt d}, \\frac{1}{d} I_d)$ form class 0\nand datapoints from $N(+\\frac{\\mathbf{1}}{\\sqrt d}, \\frac{1}{d} I_d)$ form class 1.\n(We choose this scaling in order to ensure that the signal-to-noise ratio \nremains of constant order as we vary $d$.)\nIn this setting, the true likelihood $p(x)$ satisfies\n$\\log(\\frac{p(x)}{1-p(x)}) = \\beta_0 + \\beta^\\top x$ for $x\\in \\mathbb{R}^d$,\nwhere $\\beta_0 = 0$ and $\\beta = 2\\sqrt{d} \\mathbf{1}$.\nWe fit a logistic regression model on the $n_{train}$ samples\nto obtain the fitted parameters $\\hat \\beta_0$ and $\\hat \\beta$.\nWe vary the dimension $d \\in \\{ 10, 30, 50, 70, 90 \\}$,\nand consider the $\\ell_2$ estimation error $(\\|\\hat \\beta_0 - \\beta_0\\|^2 + \\|\\hat \\beta - \\beta\\|^2)^{1/2}$\n(where $\\|\\cdot\\|$ denotes $\\ell_2$-norm),\naveraged over $n_{batches} = 100$ independent draws of the training data.\nThe results (mean ± standard deviation) are given below.\nAs we see, the risk increases rapidly with dimension, which illustrates the curse of dimensionality.\nConsequently, the resulting likelihood ratio estimator $\\hat p(x) / (1-\\hat p(x))$ \nwill be far from the true likelihood ratio $p(x) / (1-p(x))$, as well.\n\nd = 10: risk = 1.1e+1 ± 1.2e-1\n\nd = 30: risk = 5.2e+1 ± 1.6e-2\n\nd = 50: risk = 9.3e+1 ± 1.1e-2\n\nd = 70: risk = 1.3e+2 ± 8.1e-3\n\nd = 90: risk = 1.7e+2 ± 7.0e-3\n\nWeakness 2 : \"Clarify whether the idea has appeared elsewhere.\"\n\nResponse to Weakness 2:\nOur approach avoids the direct estimation of the likelihood ratio, and in this sense it is novel; we are not aware of this technique having appeared in this exact form before. \nMost prior works on conformal prediction require\ndirect estimation of the likelihood ratio,\nwhich as explained in the response to Weakness 1 above,\nincurs the curse of dimensionality\nin high-dimensional settings.\nWhile related techniques have appeared in other works on covariate shift \noutside of the conformal prediction literature\n(we cite the paper [66], Zhang et al.), \nwe believe that our specific regularizer is novel.\n\nWeakness 3: \"How does it remove the high-dimensional inaccuracy?\"\n\nResponse to Weakness 3:\nAfter using the change of measure formula, the regularizer/quantity that we need to estimate becomes an average over a distribution from which we have a data set. By estimating this with a sample average, we obtain high accuracy, while avoiding the need to estimate the high-dimensional likelihood ratio function.\n\nQ1 + Q2: \"Does $H$ contain nonlinear functions? Is it restrictive?\"  \n\nResponse to Q1 + Q2:\nWe would like to emphasize that a linear hypothesis class can be very rich and can contain highly nonlinear functions.\nIn our setting, we call a set of functions $H$\nfrom $\\mathcal{X}\\to \\mathbb{R}$\na \"linear hypothesis class\" if\n(1) $H$ forms a finite-dimensional vector space\nand\n(2) for each function $h\\in H$, the second moment $E_1[|h(X)|^2]$ is finite.\nIn particular,\nthe space of functions representable by linear combinations of the last-layer features of a pretrained model\nis an example of a linear hypothesis class.\nConsequently, $r\\in H$ does not imply that $r$ is linear, and we do not view the assumption that $r\\in H$ as being restrictive in practice. \n\nOn a technical level, in our theoretical results, we leverage the linearity of $H$ \nto relate the first-order conditions of the LR-QR problem \nto the test-time marginal coverage under the covariate shift $r$.\nThis linearity is also the key property leveraged by\nthe pioneering work [2] in order to study conditional coverage. \n(For a detailed derivation of the connection\nbetween the first-order conditions of the LR-QR problem\nand the test-time marginal coverage,\nplease see the start of Section 3\nor the proof of Proposition 4.1.)\n\nFurther, we would like to note that our experiments are consistent with our regularity conditions.\nWe perform experiments involving very high-dimensional datasets:\nthe Communities and Crime dataset has a 127-dimensional input,\nthe RxRx1 dataset has a 512 pixel-by-512 pixel image input,\nand the MMLU dataset has a 1024-dimensional text input.\nIn these challenging settings,\nLR-QR performs extremely well,\nwhich is consistent with the two regularity conditions discussed above. \nThis underscores the fact that LR-QR is a practically significant algorithm\nin the high-dimensional setting,\nwith strong and meaningful theoretical guarantees.\n\nMoreover, we would like to emphasize that such a linear function class setting is now quite standard and well-accepted in the conformal prediction literature (see e.g., [9, 10, 11]), starting with the pioneering work of [2], which has been widely adopted in the community (e.g., cited more than 100 times).\n \nQ3: \"Not a finite-sample guarantee, compare to [1].\"\n\nResponse to Q3:\nCompared to [1], our setting is fundamentally different and more difficult, as it considers coverage under covariate shift. This is more closely related to the works [6,7], and others that we compare with. In this setting, it is known from [7] that it is *impossible* to obtain finite-sample coverage with a non-trivial prediction set in general. Motivated by this result, we aim to establish asymptotic coverage bounds. In contrast, [1] considers the simpler setting of no distribution shift, which explains why they are able to obtain finite-sample coverage with non-trivial prediction sets.)\n\nStandard exchangeability arguments used in conformal prediction (e.g., in [1]) do not apply to our setting. Therefore, \nto achieve these bounds, we need to use different and novel theoretical tools (e.g., the stability result in Lemma G.1). \nWe are able to derive a coverage lower bound with error terms that holds with high probability over the calibration data.\nThe good empirical performance of the LR-QR algorithm in our experiments suggests that in practice, the coverage has an excellent finite-sample behavior.\n\n\nQ4: \"Correction for non-optimality/misspecification of the h estimator?\"\n\nResponse to Q4:\nFirst, we would like to clarify that in the LR-QR algorithm, we never estimate $h$. Therefore, there is no need to consider a correction.\n\nHowever, implicitly, our methods do impose the condition that the likelihood ratio is close to the hypothesis class $H$. Indeed, the last term $-(1-\\alpha) E_1[|r(X)-r_B(X)|]$\nin the lower bound in Theorem 4.3 accounts for the fact that the hypothesis class $H$ might not contain the true likelihood ratio $r$.\nThis quantity is proportional to the $L^1$ distance from $r$ to $H$; hence, the more misspecified $H$ is, the weaker our guarantee becomes.\n\nRegarding the other parts of the question, we would like to emphasize that the hypothesis class $H$ can include nonlinear functions $h$, and that the LR-QR algorithm does not require estimating the likelihood-ratio directly. Indeed, in our experiments we use linear combinations of features of pre-trained foundation models (LLMs) for multiple choice Q&A, which are highly non-linear functions of the original input text.\n\n[2] Gibbs et al., \"Conformal prediction with conditional guarantees\".\n\n[3] Jung et al., \"Batch multivalid conformal prediction\".\n\n[4] Foygel Barber et al., \"The limits of distribution-free conditional predictive inference\".\n\n[5] Wainwright, \"High-dimensional statistics\".\n\n[6] Tibshirani et al., \"Conformal prediction under covariate shift\".\n\n[7] Yang et al., \"Doubly Robust Calibration of Prediction Sets under Covariate Shift\".\n\n[8] Sur et al., \"A modern maximum-likelihood theory for high-dimensional logistic regression\".\n\n[9] van der Laan et al., \"Generalized Venn and Venn-Abers Calibration with Applications in Conformal Prediction\".\n\n[10] Bairaktari et al., \"Kandinsky Conformal Prediction\".\n\n[11] Cherian et al., \"Large language model validity via enhanced conformal prediction methods\"."}, {"review_id": "DPdsHqLh4n", "reviewer": "Reviewer_8HeH", "summary": "This paper tackles the problem of covariate shift in conformal prediction, where existing methods often rely on estimating a likelihood ratio function that may be hard to compute in high dimensions. The authors propose a new method, LRQR, which avoids estimating the likelihood ratio directly but still achieves valid marginal coverage. This is done under a mild assumption formalized through a hypothesis class $\\mathcal{H}$. The method is supported by strong theoretical results and is benchmarked against several state-of-the-art approaches on real datasets.", "questions": "1. It seems that the method does not aim to achieve conditional conformal coverage. If I am wrong, I would appreciate clarification. Otherwise, could the authors explain why they perform conditional evaluations across subgroups (e.g., by race or category) in data analysis, if the method is only designed for marginal validity?\n\n2. On line 104, the authors state that their theory requires scores in the $[0,1]$ range. But many common scores (e.g., residuals or negative log-likelihoods) are not bounded this way, as seen in the later experiments. Could the authors clarify the necessity of this restriction and how it aligns with practice?\n\n3. I would appreciate a high-level explanation of why the linear hypothesis class is needed and how it is used in the proof.", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths\n1. I find the paper clearly written and easy to follow.\n2. The paper addresses a case where existing techniques may not apply due to data-dependent regularizers, and introduces a novel conditioning argument to overcome this.\n3. The theoretical development is comprehensive and appears well-grounded. Although I did not verify all proofs in detail, the results are built upon solid theoretical foundations.\n4. The proposed method is compared against strong baselines and evaluated on realistic benchmark datasets.\n\nWeaknesses\n1. I would appreciate a more formal and precise definition of the hypothesis class $\\mathcal{H}$, as mentioned around lines 105–110. It is unclear what exactly constitutes a “linear hypothesis class” in the authors’ framework.\n2. It is not clear how to verify whether a given dataset satisfies the assumptions required by $\\mathcal{H}$. I would like to see a simulation that intentionally violates this assumption and examines how the method behaves in such cases.", "was_revised": true, "final_justification": "I appreciate the author’s detailed explanation of both the linear class and the experimental results during the rebuttal. Overall, I believe this paper addresses an important and practically problem. The rebuttal further demonstrates the authors’ thoughtfulness and commitment. I will maintain my score of strong accept.", "rebuttal": "We thank the reviewer for the helpful comments.\n\nWeakness 1: \"Clarify the definition of a linear class?\"\n\nResponse to Weakness 1:\nIn our setting, we call a set of functions $H$\nfrom $\\mathcal{X}\\to \\mathbb{R}$\na \"linear hypothesis class\" if\n(1) $H$ forms a finite-dimensional vector space\nand\n(2) for each function $h\\in H$, the second moment $E_1[|h(X)|^2]$ is finite.\n\nWeakness 2: \"What if we violate the assumptions on $H$?\" \n\nResponse to Weakness 2:\nWe thank the reviewer for the question about our regularity conditions\non the hypothesis class $H$.\nIndeed, our theoretical guarantees on the performance of LR-QR\nrely on\nthe true likelihood ratio $r$ being close in $L^2$-norm to\nthe hypothesis class $H$.\nThis is reflected in the misspecification error term\n$- (1-\\alpha) E_1[ |r(X) - r_B(X)| ]$\nappearing in the lower bound in Theorem 4.3.\n\nFurther, our guarantees rely on\nimplicit assumptions\non the dimensionality on $H$.\nTo illustrate the dependence on $d$ arising from Condition 3 in Appendix E, \nsuppose $\\Phi$ forms an orthonormal basis for $P_1$. \nThen applying the empirical sample covariance tail bound from Chapter 5.6 of [5], \nwe have $\\lambda_{min}(\\hat \\Sigma) \\ge 1 - O(d \\log(dn_3)/n_3)$ with probability $1-o(n_3^{-1})$. \nThis is of constant order if $d \\log(d) \\ll n_3$. \nSo our bounds are meaningful if $d \\ll n_3/\\log(n_3)$ (which allows a growing dimension).\n\nUnfortunately, with the revised conference rules,\nwe are unable to provide additional ablation plots\nto examine the effect of misspecification.\nHowever, we are happy to provide such plots in the revised version.\nFor each of the three experiments,\nwe can run LR-QR with hypothesis classes of varying complexities\n(e.g., linear combinations of the last-layer features \nof pretrained models of varying sizes)\nand compare the resulting coverage properties.\nWe thank the reviewer for their interest.\n\nQ1: Clarification about the Communities and Crime experiment.\n\nResponse to Q1:\nWe thank the reviewer for allowing us to clarify the Communities and Crime experiment.\nIndeed, in our paper, our goal is to achieve marginal coverage at the nominal level in the test domain.\nOur description of the Communities and Crime experiment\nin Section 5.2 contained a typo, which we would like to correct here.\nWe would like to clarify that we are not attempting\nto provide conditional coverage over each of the four groups.\nRather, **we design four distinct covariate shifts**,\nrun the LR-QR algorithm in each of the four scenarios,\nand evaluate the marginal coverage in the test domain.\nTo elaborate,\nlet us assign the index $i = 1$ to the Black subgroup,\n$i=2$ to the White subgroup,\n$i=3$ to the Asian subgroup,\nand $i=4$ to the Hispanic subgroup.\nLet $Z$ denote the set of datapoints\nthat were not used for training the regression model.\nThen, for each $i\\in [4]$,\nwe design a covariate shift between calibration and test\nas follows:\nthe $i$-th calibration set $Z_{cal,i}$ includes \nall individuals in $Z$\nthat are not of race $i$,\nand the $i$-th test set\nincludes \nall individuals in $Z$\nthat are of race $i$.\nThus, for each $i\\in [4]$, \nwe induce a covariate shift \nbetween $Z_{cal,i}$ and $Z_{test,i}$,\nshifting probability mass from \n\"not race $i$\"\nto \"race $i$\".\n\nIn Figure 1, we evaluate each algorithm on each of the four experimental setups. Again, this is not conditional coverage, but rather marginal coverage in distinct experiments.\nOur results show that on this challenging 127-dimensional task,\nthe LR-QR algorithm achieves excellent marginal coverage at test-time,\nfor each of the four distinct choices of covariate shift.\n\nQ2: \"Is $S\\in [0,1]$ inconsistent with the experiments?\"\n\nResponse to Q2:\nThe assumption that $S\\in [0,1]$ is simply made for technical convenience.\nOur theoretical results easily generalize to the case of nonnegative and bounded scores. In the MMLU task, this assumption is satisfied, since the score is $1-f(x)_y \\in [0,1]$.\nIn the Communities and Crime regression task, our score is the residual $|y-\\hat f(x)|$, where $y$ is the crime rate and $\\hat f$ is a bounded predictor. Hence, this score is also bounded.\nOn the RxRx1 classification task, the scores are nonnegative, but as noted by the reviewer they are not bounded apriori. \nEmpirically, the LR-QR algorithm performs very well in these scenarios, so we conjecture that the boundedness assumption can be relaxed, and we view this as an interesting direction for further work. Moreover, in the final version of the paper, we will provide additional experiments with the log-score replaced by either the standard score $1-f(x)_y \\in [0,1]$ or other bounded scores.\n\nQ3: \"Why do we assume a linear class?\"\n\nResponse to Q3:\nOn a technical level, in our theoretical results, we leverage the linearity of $H$ \nto relate the first-order conditions of the LR-QR problem \nto the test-time marginal coverage under the covariate shift $r$.\nThis linearity is also the key property leveraged by\nthe pioneering work [2] in order to study conditional coverage. \n(For a detailed derivation of the connection\nbetween the first-order conditions of the LR-QR problem\nand the test-time marginal coverage,\nplease see the start of Section 3\nor the proof of Proposition 4.1.)\n\nWe would like to emphasize that a linear hypothesis class can be very rich and can contain highly nonlinear functions, e.g., the space of functions representable by linear combinations of the last-layer features of a pretrained model. Consequently, $r\\in H$ does not imply that $r$ is linear, and we do not view the assumption that $r\\in H$ as being restrictive in practice. \nIndeed, we perform experiments involving high-dimensional datasets:\nthe Communities and Crime dataset has a 127-dimensional input,\nthe RxRx1 dataset has a 512 pixel-by-512 pixel image input,\nand the MMLU dataset has a 1024-dimensional text input.\nIn these challenging settings,\nLR-QR performs extremely well,\nwhich is consistent with our assumption that $r$ lies within $H$ or close to $H$. \nThis underscores the fact that LR-QR is a practically significant algorithm\nin the high-dimensional setting,\nwith strong and meaningful theoretical guarantees.\n \nMoreover, we would like to emphasize that such a linear function class setting is now quite standard and well-accepted in the conformal prediction literature (see e.g., [2, 3, 4]), starting with the pioneering work of [1], which has been widely adopted in the community (e.g., cited more than 100 times).\n\n[1] Gibbs et al., \"Conformal prediction with conditional guarantees\".\n\n[2] van der Laan et al., \"Generalized Venn and Venn-Abers Calibration with Applications in Conformal Prediction\".\n\n[3] Bairaktari et al., \"Kandinsky Conformal Prediction\".\n\n[4] Cherian et al., \"Large language model validity via enhanced conformal prediction methods\".\n\n[5] Vershynin. \"High-dimensional probability\"."}]

Author rebuttal:

Meta-review: All reviewers agree that this submission addresses an important problem in theory and practice, namely conformal inference with covariate shift, without separate explicit estimation of the probability change measure. The contributions are theoretical and methodological. The paper is clearly presented and well-written. The discussion after the rebuttal allowed to clarify several points and led several reviewers to raise their rating. Clear accept.
Decision: Accept (poster)