Robust Conformal Prediction Using Privileged Information

We appreciate your review of our work and thank you for the helpful suggestions and interest in our work. In what follows we respond to your concerns in detail.

The privileged information

We thank the reviewer for raising this point which is related to the one raised by Reviewer 3YMV. For the convenience of the reviewer, we repeat our answer below. In the updated manuscript, in Example 1 and Example 2 we expanded about the intuition behind the privileged information. Specifically, in the noisy response setup outlined in Example 1, we explained that since the PI, $Z_i$, is the information about the annotator, it is likely to explain the corruption appearances $M_i$. That is, in this example, the features $X_i(0)$ and the ground truth label $Y_i(0)$ do not provide additional knowledge about the corruption indicator given $Z_i$, i.e., $X_i(0), Y_i(0) \indep M_i \mid Z_i=z$.

Additionally, we added the following example inspired by a real-world medical task. Consider a medical setup where patients are being selected for a costly diagnosis, such as an MRI scan. Here, $X_i(0)=X_i(1)$ is the more standard medical measurements of the i-th patient, such as age, gender, medical history, and disease-specific measurements. The PI $Z_i$ is the information manually collected by the doctor to choose whether the patient should be examined by an MRI scan. This information is obtained through, e.g., a discussion of the doctor with the patient, or a physical examination, and could include, for instance, shortness of breath, swelling, blurred vision, etc. The response $Y_i(0)$ is the disease diagnosis obtained by the MRI scan, and $Y_i(1)=’`NA`’$. The missingness indicator $M_i$ equals 0 if the doctor decides to conduct an MRI scan, and 1 otherwise. At test time, our goal is to assist the doctors in future decisions before examining the patients, and hence the test PI $Z_\text{test}$ is unavailable. This task is relevant in situations where the number of available doctors is insufficient to examine all patients. Here, $Z_i$ explains the missingness $M_i$, and $M_i$ does not depend on $X_i$ or $Y_i$ given $Z_i$.

Finally, we note that PCP can produce valid uncertainty sets even if the independence assumption $(X \indep M) \mid Z$ is not satisfied. In this case, we instead assume that both $X,Z$ explain the corruption indicator, namely, $(Y \indep M) \mid (Z,X)$, and that the features are uncorrupted $X(0)=X(1)$. Also, the weights $w_i$ are instead defined as: $w_i = \frac{\mathbb{P}(M=0)}{ \mathbb{P}(M=0 \mid X=x_i, Z=z_i)}$. We will clarify this point in the revised manuscript as well.

The choice of $\beta$

Thank you for bringing up this important point, which was also raised by reviewer hB3A. First, we emphasize that Theorem 1 holds for any choice of $\beta\in (0,\alpha)$. Therefore, $\beta$ only affects the sizes of the uncertainty sets. Intuitively, as $\beta \rightarrow \alpha$, a higher quantile of the weighted distribution of the scores is taken, and a lower quantile of the $Q_i$’s is taken. Similarly, as $\beta \rightarrow 0$ a lower quantile of the weighted distribution of the scores is taken, and a higher quantile of the $Q_i$’s is taken. An optimal $\beta$ can be considered as the $\beta$ that leads to the narrowest intervals. Such optimal $\beta$ can be practically computed with a grid of values for $\beta$ in $(0,\alpha)$, using a validation set. Nonetheless, to maintain Algorithm 1 (PCP) simple and intuitive, we did not optimize for $\beta$ in the paper. In our experiments, we chose $\beta$ that is close to 0, so the quantile of the weighted distribution of the scores chosen by PCP is close to the quantile chosen by (the infeasible) WCP. In response to this comment, we added this discussion to the text, and we conducted an ablation study for the choice of $\beta$ on a synthetic dataset. The results of the ablation study are provided in the PDF file in the global response. This experiment indicates that the smallest intervals are achieved for $\beta$ that is close to 0, and the interval sizes are an increasing function of $\beta$. Yet, it is important to understand that different results could be obtained for different datasets. Therefore, we recommend choosing $\beta$ using a validation set, as explained above. Thank you for the opportunity to discuss this issue.

Definition of Z

Definitely! We agree that in some tasks it might be difficult to collect privileged information. Indeed, we view the problem of choosing an “ideal” privileged information that satisfies the conditional independence assumption as a thrilling future research direction.

We are appreciative of the reviewer's comments and for acknowledging our previous response. We are thankful for the opportunity to further clarify and expand on the points raised. Below, we address each comment in detail.

Identifying privileged information

Identifying appropriate privileged information is indeed a challenging task. In general, this requires expert knowledge, similar to the unconfoundedness assumption in causal inference applications used for treatment effect estimation, for example. In more detail, our solution lies in the conditional independence assumption: $(X(0), Y(0)) \indep M \mid Z=z$. In words, $Z$ should explain the information about the corruption appearances that is encapsulated in $X(0)$ and $Y(0)$. For instance, in our noisy labels setup in Example 1, the information about the annotator is a good candidate for privileged information, as the noise pattern depends directly on the annotator. Yet, the challenge here is that the conditional independence requirement cannot be directly tested in practice, as we only observe $(X(0), Y(0)) \mid M=0$. In view of unconfoundedness, our work introduces a relaxation of this assumption as we do not assume that $Z$ is observed at test time.

From a practical perspective, we found that PCP can produce valid uncertainty sets even if the independence assumption is not satisfied. For example, in our real-world noisy response experiment from Section 4.3, PCP attained the target coverage rate even though the conditional independence assumption was not confirmed. We believe this is attributed to our formulation of $Z$, being a variable that is highly correlated to $M$. Intuitively, when $Z$ explains the corruption indicator $M$ well, it is sensible to believe that the conditional independence requirement is approximately satisfied.

More formally, below we analyze the setting where the conditional independence assumption is violated and provide a lower bound for the coverage rate attained by PCP. In simple words, this new result reveals that PCP achieves a coverage rate that is closer to the nominal level as the conditional independence assumption violation is smaller.

Extension beyond the conditional independence assumption

We are grateful for the opportunity to discuss this topic. We propose an initial extension of Theorem 1 to a setting where the conditional independence assumption is not fully satisfied. For the simplicity of this initial extension, we assume $X(0) \indep M \mid Z=z$.

The independence assumption $Y(0) \indep M \mid Z=z$ is equivalent to assuming that the density of $Y(0) \mid M=m, Z=z$ is the same for $m \in \\{0,1\\}$, formally:

$f_{Y(0) \mid M=0, X=x,Z=z}(y; 0,x,z) = f_{Y(0) \mid M=1,X=x, Z=z}(y; 1,x,z).$

In our extension, we relax this assumption and instead require that $\forall x\in \mathcal{X}$, there exists $\varepsilon_x \in\mathbb{R}$ such that the difference between the two densities is bounded by $\varepsilon_x$: $\forall y\in\mathcal{Y}, z\in\mathcal{Z}: | f_{Y(0) \mid M=0, X=x,Z=z}(y; 0,x,z) - f_{Y(0) \mid M=1,X=x, Z=z}(y; 1,x,z) | \leq \varepsilon_x .$

$**Theorem [Robustness of PCP to conditional independence violation]**$

Suppose that $\\{(X_i(0),X_i(1), Y_i(0),Y_i(1),Z_i, M_i)\\}\_{i=1}^{n+1}$ are exchangeable, $P_{Z}$ is absolutely continuous with respect to $P_{Z \mid M=0}$, and $\forall x\in\mathcal{X}$ there exists $\varepsilon_x \in\mathbb{R}$ such that: $\forall y\in\mathcal{Y}, z\in\mathcal{Z}: | f_{Y(0) \mid M=0, X=x,Z=z}(y; 0,x,z) - f_{Y(0) \mid M=1,X=x, Z=z}(y; 1,x,z) | \leq \varepsilon_x .$ Then, the coverage rate of the prediction set $C^{PCP}(X^\textup{test})$ constructed according to Algorithm 1 is lower bounded by:

We omit the proof due to the limitation of space. We can send the proof in a separate comment.

This result provides a lower bound for the coverage rate of PCP in the setting where the conditional independence assumption is not exactly satisfied. Intuitively, as $\varepsilon_x$ decreases, i.e., as the two distributions $Y(0) \mid M=m, Z=z$ for $m\in \\{0,1\\}$ are closer to each other, the lower bound is tighter, and closer to the target level. Similarly, as the two distributions diverge, the lower bound becomes looser.

We once again thank the reviewer for these insightful suggestions, which significantly improve our paper. We will include these discussions in the revised manuscript.

We very much appreciate your positive feedback and interest in our work. We thank the reviewer for classifying our contribution as a novel one. We also thank the reviewer for their helpful comments and suggestions. In what follows, we address your comments in detail. $\newcommand{\indep}{\perp \\\!\\!\\! \perp}$

The Privileged Information

We thank the reviewer for raising this point which is related to a comment raised by Reviewer R7TW. In the updated manuscript, in Example 1 and Example 2 we expanded about the intuition behind the privileged information. Specifically, in the noisy response setup outlined in Example 1, we explained that since the PI, $Z_i$, is the information about the annotator, it is likely to explain the corruption appearances $M_i$. That is, in this example, the features $X_i(0)$ and the ground truth label $Y_i(0)$ do not provide additional knowledge about the corruption indicator given $Z_i$, i.e., $X_i(0), Y_i(0) \indep M_i \mid Z_i=z$.

Additionally, we added the following example inspired by a real-world medical task. Consider a medical setup where patients are being selected for a costly diagnosis, such as an MRI scan. Here, $X_i(0)=X_i(1)$ is the more standard medical measurements of the i-th patient, such as age, gender, medical history, and disease-specific measurements. The PI $Z_i$ is the information manually collected by the doctor to choose whether the patient should be examined by an MRI scan. This information is obtained through, e.g., a discussion of the doctor with the patient, or a physical examination, and could include, for instance, shortness of breath, swelling, blurred vision, etc. The response $Y_i(0)$ is the disease diagnosis obtained by the MRI scan, and $Y_i(1)='`NA`'$ is the missing value. The missingness indicator $M_i$ equals 0 if the doctor decides to conduct an MRI scan, and 1 otherwise. At test time, our goal is to assist the doctors in future decisions before examining the patients, and hence the test PI $Z_\text{test}$ is unavailable. This task is relevant in situations where the number of available doctors is insufficient to examine all patients. Here, $Z_i$ explains the missingness $M_i$, and $M_i$ does not depend on $X_i$ or $Y_i$ given $Z_i$.

Finally, we note that PCP can produce valid uncertainty sets even if the independence assumption $(X \indep M) \mid Z$ is not satisfied. In this case, we instead assume that both $X,Z$ explain the corruption indicator, namely, $(Y \indep M) \mid (Z,X)$, and that the features are uncorrupted $X(0)=X(1)$. Also, the weights $w_i$ are instead defined as: $w_i = \frac{\mathbb{P}(M=0)}{ \mathbb{P}(M=0 \mid X=x_i, Z=z_i)}$. We will clarify this point in the revised manuscript as well.

We are very grateful for the time and effort you put into this review. We are also very appreciative of your encouragement and positive assessment of our work. Your feedback is very important to us! Thank you again for your support.

We appreciate your positive and valuable feedback and suggestions. In what follows, we address your concerns in detail.

The weights $w_i$

We thank the reviewer for raising this point. As the reviewer suggested, the real ratios of likelihoods, $w_i$, are required to provide the validity guarantee in Theorem 1. While PCP can be applied with estimates of $w_i$, which can be computed with estimates of $\mathbb{P}(M=0 \mid Z=z)$ according to equation (3), the validity guarantee does not hold in this case. This restriction is similar to WCP which also requires the true weights $w_i$ to provide a validity guarantee. The effect of inaccurate estimates of $w_i$ on the coverage rate attained by PCP could be an exciting future direction to explore, e.g., by borrowing ideas from [1].

Following the reviewer's comment we updated Algorithm 1 (PCP) in the text, and added $w_i$ as an input. Furthermore, in Section 3.2 we explained if the real weights $w_i$ are unavailable, then they can extracted from estimates of $\mathbb{P}(M=0 \mid Z=z)$ according to equation (3), and this conditional probability can be estimated from the training data, using any off-the-shelf classifier. We also clarified in the updated manuscript that Theorem 1 does not hold if PCP is not used with the oracle weights.

[1] Yonghoon Lee, Edgar Dobriban, and Eric Tchetgen Tchetgen. Simultaneous conformal prediction of missing outcomes with propensity score $\epsilon$-discretization. arXiv preprint arXiv:2403.04613, 2024.

The choice of $\beta$

Thank you for bringing up this important point, which was also raised by reviewer R7TW. First, we emphasize that Theorem 1 holds for any choice of $\beta\in (0,\alpha)$. Therefore, $\beta$ only affects the sizes of the uncertainty sets. Intuitively, as $\beta \rightarrow \alpha$, a higher quantile of the weighted distribution of the scores is taken, and a lower quantile of the $Q_i$’s is taken. Similarly, as $\beta \rightarrow 0$ a lower quantile of the weighted distribution of the scores is taken, and a higher quantile of the $Q_i$’s is taken. An optimal $\beta$ can be considered as the $\beta$ that leads to the narrowest intervals. Such optimal $\beta$ can be practically computed with a grid of values for $\beta$ in $(0,\alpha)$, using a validation set. Nonetheless, to maintain Algorithm 1 (PCP) simple and intuitive, we did not optimize for $\beta$ in the paper. In our experiments, we chose $\beta$ that is close to 0, so the quantile of the weighted distribution of the scores chosen by PCP is close to the quantile chosen by (the infeasible) WCP. In response to this comment, we added this discussion to the text, and we conducted an ablation study for the choice of $\beta$ on a synthetic dataset. The results of the ablation study are provided in the PDF file in the global response. This experiment indicates that the smallest intervals are achieved for $\beta$ that is close to 0, and the interval sizes are an increasing function of $\beta$. Yet, it is important to understand that different results could be obtained for different datasets. Therefore, we recommend choosing $\beta$ using a validation set, as explained above. Thank you for the opportunity to discuss this issue.

Limitations

We thank the reviewer for raising this topic. We added a discussion about the limitations of PCP in Section 3.2. Specifically, we clarified that the true conditional corruption probability $\mathbb{P}(M=1 \mid Z=z)$ must be known to provide a theoretical coverage validity guarantee.

We thank the reviewer for these comments, which greatly improve our paper!