Conformal Inference under High-Dimensional Covariate Shifts via Likelihood-Ratio Regularization

We thank the reviewer for the helpful comments.

Weakness 1: "Clarify the definition of a linear class?"

Response to Weakness 1: In our setting, we call a set of functions $H$ from $\mathcal{X}\to \mathbb{R}$ a "linear hypothesis class" if (1) $H$ forms a finite-dimensional vector space and (2) for each function $h\in H$, the second moment $E_1[|h(X)|^2]$ is finite.

Weakness 2: "What if we violate the assumptions on $H$?"

Response to Weakness 2: We thank the reviewer for the question about our regularity conditions on the hypothesis class $H$. Indeed, our theoretical guarantees on the performance of LR-QR rely on the true likelihood ratio $r$ being close in $L^2$-norm to the hypothesis class $H$. This is reflected in the misspecification error term $- (1-\alpha) E_1[ |r(X) - r_B(X)| ]$ appearing in the lower bound in Theorem 4.3.

Further, our guarantees rely on implicit assumptions on the dimensionality on $H$. To illustrate the dependence on $d$ arising from Condition 3 in Appendix E, suppose $\Phi$ forms an orthonormal basis for $P_1$. Then applying the empirical sample covariance tail bound from Chapter 5.6 of [5], 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).

Unfortunately, with the revised conference rules, we are unable to provide additional ablation plots to examine the effect of misspecification. However, we are happy to provide such plots in the revised version. For each of the three experiments, we can run LR-QR with hypothesis classes of varying complexities (e.g., linear combinations of the last-layer features of pretrained models of varying sizes) and compare the resulting coverage properties. We thank the reviewer for their interest.

Q1: Clarification about the Communities and Crime experiment.

Response to Q1: We thank the reviewer for allowing us to clarify the Communities and Crime experiment. Indeed, in our paper, our goal is to achieve marginal coverage at the nominal level in the test domain. Our description of the Communities and Crime experiment in Section 5.2 contained a typo, which we would like to correct here. We would like to clarify that we are not attempting to provide conditional coverage over each of the four groups. Rather, we design four distinct covariate shifts, run the LR-QR algorithm in each of the four scenarios, and evaluate the marginal coverage in the test domain. To elaborate, let us assign the index $i = 1$ to the Black subgroup, $i=2$ to the White subgroup, $i=3$ to the Asian subgroup, and $i=4$ to the Hispanic subgroup. Let $Z$ denote the set of datapoints that were not used for training the regression model. Then, for each $i\in [4]$, we design a covariate shift between calibration and test as follows: the $i$-th calibration set $Z_{cal,i}$ includes all individuals in $Z$ that are not of race $i$, and the $i$-th test set includes all individuals in $Z$ that are of race $i$. Thus, for each $i\in [4]$, we induce a covariate shift between $Z_{cal,i}$ and $Z_{test,i}$, shifting probability mass from "not race $i$" to "race $i$".

In 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. Our results show that on this challenging 127-dimensional task, the LR-QR algorithm achieves excellent marginal coverage at test-time, for each of the four distinct choices of covariate shift.

Q2: "Is $S\in [0,1]$ inconsistent with the experiments?"

Response to Q2: The assumption that $S\in [0,1]$ is simply made for technical convenience. Our 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]$. In 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. On the RxRx1 classification task, the scores are nonnegative, but as noted by the reviewer they are not bounded apriori. Empirically, 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.

Q3: "Why do we assume a linear class?"

Response to Q3: On a technical level, in our theoretical results, we leverage the linearity of $H$ to relate the first-order conditions of the LR-QR problem to the test-time marginal coverage under the covariate shift $r$. This linearity is also the key property leveraged by the pioneering work [2] in order to study conditional coverage. (For a detailed derivation of the connection between the first-order conditions of the LR-QR problem and the test-time marginal coverage, please see the start of Section 3 or the proof of Proposition 4.1.)

We 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. Indeed, we perform experiments involving high-dimensional datasets: the Communities and Crime dataset has a 127-dimensional input, the RxRx1 dataset has a 512 pixel-by-512 pixel image input, and the MMLU dataset has a 1024-dimensional text input. In these challenging settings, LR-QR performs extremely well, which is consistent with our assumption that $r$ lies within $H$ or close to $H$. This underscores the fact that LR-QR is a practically significant algorithm in the high-dimensional setting, with strong and meaningful theoretical guarantees.

Moreover, 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).

[1] Gibbs et al., "Conformal prediction with conditional guarantees".

[2] van der Laan et al., "Generalized Venn and Venn-Abers Calibration with Applications in Conformal Prediction".

[3] Bairaktari et al., "Kandinsky Conformal Prediction".

[4] Cherian et al., "Large language model validity via enhanced conformal prediction methods".

[5] Vershynin. "High-dimensional probability".

We thank the reviewer for the helpful comments.

Strength 1: "The observation linking the optimum of the pin-ball objective and coverage."

Response to Strength 1: This 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.

Weakness 1: "Why is high-dimensionality hard?"

Response to Weakness 1: In 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].

Given that the likelihood ratio is a high-dimensional function when $\text{dim}(\mathcal{X})$ is large, likelihood ratio estimation suffers from similar hardness results. As the reviewer suggests, a natural method for likelihood ratio estimation is through logistic regression. Specifically, 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\}$, one can fit a logistic regression model to obtain a probabilistic classifier $\hat p(x)$ that returns the predicted probability that $x$ was sampled from class 1; then, one returns the likelihood ratio estimate $\hat r(x) = \hat p(x) / (1 - \hat p(x))$. However, in the literature, theoretical results show that logistic regression incurs large estimation errors in high dimension; see e.g., [8]. Here, we numerically illustrate this phenomenon with the following simple setting. Given a dimension $d$, and given a fixed sample size $n_{train} = 10000$, we sample $n_{train}/2$ datapoints from $N(-\frac{\mathbf{1}}{\sqrt d}, \frac{1}{d} I_d)$ and $n_{train}/2$ datapoints from $N(+\frac{\mathbf{1}}{\sqrt d}, \frac{1}{d} I_d)$, where $\mathbf{1}$ denotes the vector of all ones, and $I_d$ denotes the identity covariance matrix. Here, datapoints from $N(-\frac{\mathbf{1}}{\sqrt d}, \frac{1}{d} I_d)$ form class 0 and datapoints from $N(+\frac{\mathbf{1}}{\sqrt d}, \frac{1}{d} I_d)$ form class 1. (We choose this scaling in order to ensure that the signal-to-noise ratio remains of constant order as we vary $d$.) In this setting, the true likelihood $p(x)$ satisfies $\log(\frac{p(x)}{1-p(x)}) = \beta_0 + \beta^\top x$ for $x\in \mathbb{R}^d$, where $\beta_0 = 0$ and $\beta = 2\sqrt{d} \mathbf{1}$. We fit a logistic regression model on the $n_{train}$ samples to obtain the fitted parameters $\hat \beta_0$ and $\hat \beta$. We vary the dimension $d \in \{ 10, 30, 50, 70, 90 \}$, and consider the $\ell_2$ estimation error $(\|\hat \beta_0 - \beta_0\|^2 + \|\hat \beta - \beta\|^2)^{1/2}$ (where $\|\cdot\|$ denotes $\ell_2$-norm), averaged over $n_{batches} = 100$ independent draws of the training data. The results (mean ± standard deviation) are given below. As we see, the risk increases rapidly with dimension, which illustrates the curse of dimensionality. Consequently, the resulting likelihood ratio estimator $\hat p(x) / (1-\hat p(x))$ will be far from the true likelihood ratio $p(x) / (1-p(x))$, as well.

d = 10: risk = 1.1e+1 ± 1.2e-1

d = 30: risk = 5.2e+1 ± 1.6e-2

d = 50: risk = 9.3e+1 ± 1.1e-2

d = 70: risk = 1.3e+2 ± 8.1e-3

d = 90: risk = 1.7e+2 ± 7.0e-3

Weakness 2 : "Clarify whether the idea has appeared elsewhere."

Response to Weakness 2: Our 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. Most prior works on conformal prediction require direct estimation of the likelihood ratio, which as explained in the response to Weakness 1 above, incurs the curse of dimensionality in high-dimensional settings. While related techniques have appeared in other works on covariate shift outside of the conformal prediction literature (we cite the paper [66], Zhang et al.), we believe that our specific regularizer is novel.

Weakness 3: "How does it remove the high-dimensional inaccuracy?"

Response to Weakness 3: After 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.

Q1 + Q2: "Does $H$ contain nonlinear functions? Is it restrictive?"

Response to Q1 + Q2: We would like to emphasize that a linear hypothesis class can be very rich and can contain highly nonlinear functions. In our setting, we call a set of functions $H$ from $\mathcal{X}\to \mathbb{R}$ a "linear hypothesis class" if (1) $H$ forms a finite-dimensional vector space and (2) for each function $h\in H$, the second moment $E_1[|h(X)|^2]$ is finite. In particular, the space of functions representable by linear combinations of the last-layer features of a pretrained model is an example of a linear hypothesis class. 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.

On a technical level, in our theoretical results, we leverage the linearity of $H$ to relate the first-order conditions of the LR-QR problem to the test-time marginal coverage under the covariate shift $r$. This linearity is also the key property leveraged by the pioneering work [2] in order to study conditional coverage. (For a detailed derivation of the connection between the first-order conditions of the LR-QR problem and the test-time marginal coverage, please see the start of Section 3 or the proof of Proposition 4.1.)

Further, we would like to note that our experiments are consistent with our regularity conditions. We perform experiments involving very high-dimensional datasets: the Communities and Crime dataset has a 127-dimensional input, the RxRx1 dataset has a 512 pixel-by-512 pixel image input, and the MMLU dataset has a 1024-dimensional text input. In these challenging settings, LR-QR performs extremely well, which is consistent with the two regularity conditions discussed above. This underscores the fact that LR-QR is a practically significant algorithm in the high-dimensional setting, with strong and meaningful theoretical guarantees.

Moreover, 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).

Q3: "Not a finite-sample guarantee, compare to [1]."

Response to Q3: Compared 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.)

Standard exchangeability arguments used in conformal prediction (e.g., in [1]) do not apply to our setting. Therefore, to achieve these bounds, we need to use different and novel theoretical tools (e.g., the stability result in Lemma G.1). We are able to derive a coverage lower bound with error terms that holds with high probability over the calibration data. The good empirical performance of the LR-QR algorithm in our experiments suggests that in practice, the coverage has an excellent finite-sample behavior.

Q4: "Correction for non-optimality/misspecification of the h estimator?"

Response to Q4: First, we would like to clarify that in the LR-QR algorithm, we never estimate $h$. Therefore, there is no need to consider a correction.

However, 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)|]$ in the lower bound in Theorem 4.3 accounts for the fact that the hypothesis class $H$ might not contain the true likelihood ratio $r$. This quantity is proportional to the $L^1$ distance from $r$ to $H$; hence, the more misspecified $H$ is, the weaker our guarantee becomes.

Regarding 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.

[2] Gibbs et al., "Conformal prediction with conditional guarantees".

[3] Jung et al., "Batch multivalid conformal prediction".

[4] Foygel Barber et al., "The limits of distribution-free conditional predictive inference".

[5] Wainwright, "High-dimensional statistics".

[6] Tibshirani et al., "Conformal prediction under covariate shift".

[7] Yang et al., "Doubly Robust Calibration of Prediction Sets under Covariate Shift".

[8] Sur et al., "A modern maximum-likelihood theory for high-dimensional logistic regression".

[9] van der Laan et al., "Generalized Venn and Venn-Abers Calibration with Applications in Conformal Prediction".

[10] Bairaktari et al., "Kandinsky Conformal Prediction".

[11] Cherian et al., "Large language model validity via enhanced conformal prediction methods".

We thank the reviewer for the helpful comments.

Q1: "Justify regularity conditions."

Response to Q1: We thank the reviewer for the insightful questions about the regularity conditions.

Regarding the conditions on $H$, we would like to emphasize that a linear hypothesis class can be very rich and can contain highly nonlinear functions. In our setting, we call a set of functions $H$ from $\mathcal{X}\to \mathbb{R}$ a "linear hypothesis class" if (1) $H$ forms a finite-dimensional vector space and (2) for each function $h\in H$, the second moment $E_1[|h(X)|^2]$ is finite. In particular, the space of functions representable by linear combinations of the last-layer features of a pretrained model is an example of a linear hypothesis class. 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.

On a technical level, in our theoretical results, we leverage the linearity of $H$ to relate the first-order conditions of the LR-QR problem to the test-time marginal coverage under the covariate shift $r$. This linearity is also the key property leveraged by the pioneering work [2] in order to study conditional coverage. (For a detailed derivation of the connection between the first-order conditions of the LR-QR problem and the test-time marginal coverage, please see the start of Section 3 or the proof of Proposition 4.1.)

Moreover, 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).

Regarding 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.

Finally, we would like to note that our experiments are consistent with our regularity conditions. We perform experiments involving very high-dimensional datasets: the Communities and Crime dataset has a 127-dimensional input, the RxRx1 dataset has a 512 pixel-by-512 pixel image input, and the MMLU dataset has a 1024-dimensional text input. In these challenging settings, LR-QR performs extremely well, which is consistent with the two regularity conditions discussed above. This underscores the fact that LR-QR is a practically significant algorithm in the high-dimensional setting, with strong and meaningful theoretical guarantees.

Overall, we believe that our regularity conditions are practically reasonable, but we believe relaxing our conditions is an interesting future direction.

Q1B. "How to choose lambda?"

Response to Q1B: As the reviewer has noted, introducing the regularization term, which controlled by $\lambda$, is a crucial contribution of our work. Moreover, 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.

Q2: "Clarifications regarding Section 3."

Response to Q2: We appreciate the detailed suggestions regarding the exposition in Section 3. Our presentation was quite compact due to the page limit, but we are happy to expand it in the final version. Indeed, the two crucial ideas we seek to convey in Section 3 are (1) the connection between the first-order optimal condition and the marginal coverage in the test domain, as introduced by [1], and (2) the motivation for our novel regularization, via a data-dependent choice of the hypothesis class $H$. Here, we elaborate on (1) and lines 117-129, to clarify the key steps of the derivation. By inspecting the definition of the pinball loss in Equation (1), we see that the derivative of the pinball loss with respect to its first argument is given by

We thank the reviewer for the helpful comments.

Weakness 1: "Providing code."

Response to Weakness 1: Our code is currently ready to be shared; however, the conference does not allow us to share links, otherwise we would include it here. As a result, we will include our code with the revised paper. We thank the reviewer for their interest.

Weakness 2: "Experimental details?"

Response to Weakness 2:

Regarding point (2.1), we thank the reviewer for allowing us to clarify the Communities and Crime experiment. Our description of the Communities and Crime experiment in Section 5.2 contained a typo, which we would like to correct here. In the experiment, we design four distinct covariate shifts, run the LR-QR algorithm in each of the four scenarios, and evaluate the marginal coverage in the test domain. To elaborate, let us assign the index $i = 1$ to the Black subgroup, $i=2$ to the White subgroup, $i=3$ to the Asian subgroup, and $i=4$ to the Hispanic subgroup. Let $Z$ denote the set of datapoints that were not used for training the regression model. Then, for each $i\in [4]$, we design a covariate shift between calibration and test as follows: the $i$-th calibration set $Z_{cal,i}$ includes all individuals in $Z$ that are not of race $i$, and the $i$-th test set includes all individuals in $Z$ that are of race $i$. Thus, for each $i\in [4]$, we induce a covariate shift between $Z_{cal,i}$ and $Z_{test,i}$, shifting probability mass from "not race $i$" to "race $i$". In Figure 1, we evaluate each algorithm on each of the four experimental setups. Our results show that on this challenging 127-dimensional task, the LR-QR algorithm achieves excellent marginal coverage at test-time, for each of the four distinct choices of covariate shift. We thank the reviewer for this question regarding the choice of covariate shift in Section 5.2. Due to space limitations, we were unable to elaborate in the initial submission.

Regarding points (2.2) through (2.4), we thank the reviewer for catching the error in the legend; we will correct this in the revised version. In Figure 1, for each race, the left-most bar (in blue) denotes LR-QR. We 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).

Weakness 3: "Clarify the limitation?"

Response to Weakness 3: In the limitation stated in the Discussion section, we mean that it would be of interest in future work to study the error terms appearing in the coverage lower bound in Theorem 4.3. In particular, it may be possible to understand these terms when optimizing over particular function classes, or under certain assumptions on the true likelihood ratio $r$. We believe this could shed further light on the practical efficacy of the LR-QR algorithm, and strengthen our theoretical guarantees.

Q1 + Q2 - "Clarify effect of $\lambda$ in Proposition 4.1; clarify the infinite-sample setting?"

Response to Q1 + Q2: Indeed, 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 $\ge (1-\alpha) + 2\lambda \beta E_1[ (r_{H}(X) - \beta h(X))^2 ],$ where $(\beta, h)$ denotes the population LR-QR solution, which in turn depend on $\lambda$. This 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.

The 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).

Q3: "Why do we assume a linear class?"

Response to Q3: On a technical level, in our theoretical results, we leverage the linearity of $H$ to relate the first-order conditions of the LR-QR problem to the test-time marginal coverage under the covariate shift $r$. This linearity is also the key property leveraged by the pioneering work [2] in order to study conditional coverage. (For a detailed derivation of the connection between the first-order conditions of the LR-QR problem and the test-time marginal coverage, please see the start of Section 3 or the proof of Proposition 4.1.)

We 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. Indeed, we perform experiments involving high-dimensional datasets: the Communities and Crime dataset has a 127-dimensional input, the RxRx1 dataset has a 512 pixel-by-512 pixel image input, and the MMLU dataset has a 1024-dimensional text input. In these challenging settings, LR-QR performs extremely well, which is consistent with our assumption that $r$ lies within $H$ or close to $H$. This underscores the fact that LR-QR is a practically significant algorithm in the high-dimensional setting, with strong and meaningful theoretical guarantees.

Moreover, 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).

Q4: "How to obtain unlabeled calibration data?"

Response to Q4: Indeed, given datapoints $\{ (X_i, Y_i) : i\in [n_1+n_3] \}$ drawn i.i.d. from $P_1$, we can split the data into a labeled calibration set $\{ (X_i, Y_i) : i\in [n_1] \}$ and an unlabeled calibration set $\mathcal{S}_3 = \{ X_i : i\in [n_1] \}$ by simply dropping the label $Y_i$ from $(X_i, Y_i)$ for $n_1+1 \le i \le n_3$.

However, to achieve provable coverage guarantees, our current approach requires the two datasets to be indepenent. Thus, it is not possible to set the unlabeled calibration set $\mathcal{S}_3$ to be equal to the features $\{ X_i : i\in [n_1] \}$ of the labeled calibration data $\{ (X_i, Y_i) : i\in [n_1] \}$; if we reuse data in this way, then we violate the i.i.d. assumption that is necessary for our theoretical guarantees.

Q5: "Is the theoretical $\lambda$ consistent with the experimental $\lambda$?"

Response to Q5: This is a great question. As shown in Figure 4 of Section B of the Appendix, for the Communities and Crime task, the regularization strength selected through cross-validation aligns closely with the regularization strength suggested by our theory in Equation (4). In the other two experiments, we observe similar trends, where the selected regularization is consistent with our theory. Unfortunately, with the revised conference rules, we are unable to provide the resulting plots. We are happy to elaborate in the revised paper.

[1] Gibbs et al., "Conformal prediction with conditional guarantees".

[2] van der Laan et al., "Generalized Venn and Venn-Abers Calibration with Applications in Conformal Prediction".

[3] Bairaktari et al., "Kandinsky Conformal Prediction".

[4] Cherian et al., "Large language model validity via enhanced conformal prediction methods".

We thank the reviewer for the helpful comments.

Weakness 1: "Elaborate on high dimensionality."

Response to Weakness 1: This 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.

Our 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.

The 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$. The radius $B$ can be taken to be a constant. The quantity $C_{\Phi}$ can be taken to be a constant if the basis functions are normalized correctly. The quantities $C_{1,max}$ and $C_{1,upper}$ depend polynomially on the preceding six quantities. Thus, $A$ and $A'$ introduce only mild dependence on the complexity of the function class.

To 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.

Also, 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.

We 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.

Q1 + Q2 + Q5: Notation.

Response 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.

Q3: "Why a linear hypothesis class?"

Response to Q3: In our setting, we call a set of functions $H$ from $\mathcal{X}\to \mathbb{R}$ a "linear hypothesis class" if (1) $H$ forms a finite-dimensional vector space and (2) for each function $h\in H$, the second moment $E_1[|h(X)|^2]$ is finite. On a technical level, in our theoretical results, we leverage the linearity of $H$ to relate the first-order conditions of the LR-QR problem to the test-time marginal coverage under the covariate shift $r$. This linearity is also the key property leveraged by the pioneering work [2] in order to study conditional coverage. (For a detailed derivation of the connection between the first-order conditions of the LR-QR problem and the test-time marginal coverage, please see the start of Section 3 or the proof of Proposition 4.1.)

We 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. Indeed, we perform experiments involving high-dimensional datasets: the Communities and Crime dataset has a 127-dimensional input, the RxRx1 dataset has a 512 pixel-by-512 pixel image input, and the MMLU dataset has a 1024-dimensional text input. In these challenging settings, LR-QR performs extremely well, which is consistent with our assumption that $r$ lies within $H$ or close to $H$. This underscores the fact that LR-QR is a practically significant algorithm in the high-dimensional setting, with strong and meaningful theoretical guarantees.

Moreover, 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).

Q4: "Why i.i.d.?"

Response to Q4: In 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.

Q6.A: "Is $r$ linear?"

Response to Q6.A: We 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.

Q6.B: "How plausible is $r\in H$? Include examples."

Response to Q6.B: As 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.

Q7: "Strengthen the misspecification lower bound?"

Response to Q7: We 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

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.