Conformal Prediction with Corrupted Labels: Uncertain Imputation and Robust Re-weighting
Authors: Shai Feldman
Stephen Bates
Yaniv Romano
Venue: ICLR 2026 Poster (2026)
Keywords: Conformal Prediction
Uncertainty Quantification
Distribution Shift
Corrupted Labels
Privileged Information
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)

Abstract: We introduce a framework for robust uncertainty quantification in situations where labeled training data are corrupted, through noisy or missing labels. We build on conformal prediction, a statistical tool for generating prediction sets that cover the test label with a pre-specified probability. The validity of conformal prediction, however, holds under the i.i.d assumption, which does not hold in our setting due to the corruptions in the data. To account for this distribution shift, the privileged conformal prediction (PCP) method proposed leveraging privileged information (PI)---additional features available only during training---to re-weight the data distribution, yielding valid prediction sets under the assumption that the weights are accurate. In this work, we analyze the robustness of PCP to inaccuracies in the weights. Our analysis indicates that PCP can still yield valid uncertainty estimates even when the weights are poorly estimated. Furthermore, we introduce uncertain imputation (UI), a new conformal method that does not rely on weight estimation. Instead, we impute corrupted labels in a way that preserves their uncertainty. Our approach is supported by theoretical guarantees and validated empirically on both synthetic and real benchmarks. Finally, we show that these techniques can be integrated into a triply robust framework, ensuring statistically valid predictions as long as at least one underlying method is valid.

Published as a conference paper at ICLR 2026
CONFORMAL PREDICTION WITH CORRUPTED LABELS: UNCERTAIN IMPUTATION AND ROBUST RE-WEIGHTING
Shai Feldman
Stephen Bates
Department of Computer Science Technion, Israel shai. fe dman@cs. www.nitn..c...n............
Department Electrical Engincering and Computer Science Massachusetts Institute of Technology s stephenbates@mit.c edu
Yaniv Romano
Departments of Electrical and Computer Engineering and of Computer Science
Technion, Israel y proman@@technion.e. ac.
ABSTRACT
We introduce framework for robust uncertainty quantification in situations where labeled training data corrupted, through noisy missing labels. We build conformal prediction, a statistical tool for generating prediction sets that cover the test label with pre-specified probability. The validity of conformal prediction, however, holds under the i.i.d assumption, which does not hold in our setting due the corruptions in the data. To account for this distribution shift, the privileged conformal prediction (PCP) method proposed leveraging privileged information (PI) (PI)-addiional features available only during training- re- re-weight the data distribution, yielding valid prediction sets under the assumption that the weights are accurate. In this work, we analyze the robustness of PCP to inaccuracies in the weights. Our analysis indicates that PCP can still yield valid uncertainty estimates even when the weights are poorly estimated. Furthermore, we introduce uncertain imputation (UI), new conformal method that does not rely weight estimation. Instead, we impute corrupted labels in a way that preserves their uncertainty. Our approach supported by theoretical guarantees and validated empirically both synthetic and real benchmarks. Finally, we show that these techniques can be integrated into a triply robust framework, ensuring statistically valid predictions long as at least one underlying method is valid.
INTRODUCTION
Modern machine learning models are increasingly deployed in high-stakes settings where reliable uncertainty quantification is essential. This need becomes even more critical when dealing with imperfect training data, which may be affected by noisy or missing labels. A common strategy to quantify prediction uncertainty to construct prediction sets that cover the true outcome with user-specified probability, e.g., 90%. Conformal prediction (CP) (Vovk et al., 2005) is a powerful framework for constructing theoretically valid prediction sets. Given a predictive model, utilizes labeled holdout calibration samples to compute prediction errors, which are then used to construct prediction sets for unseen test points. To provide a validity guarantee, this procedure requires that the training and test data are exchangeable, an assumption that does not hold in many real-world scenarios in which the observed data is corrupted.
To illustrate the challenge of providing reliable inference under corrupted data, we conduct an experiment on the Medical Expenditure Panel Survey (MEPS) (meps 19) dataset where the goal is to predict an individual's 's medical utilization (Y E )) given set of features (X X)), such race, income, medical conditions, and other demographic variables. We simulate a missing-at-randee at-random setup by randomly removing labels with probability that depends the features. Since cannot

---

Published as a conference paper at ICLR 2026
use the samples with missing labels compute the prediction error, we naively employ CP using only the observed data to construct prediction sets aiming to cover the true Y with 90% probability, Figure 1 shows that this Naive CP fails to achieve the desired coverage due to the distributional shift induced by the missing labels.
However, in this special case, the distributional shift is covariate shift which using the method of weighted conformal prediction (WCP) (Tibshirani et al., 2019). This method weights the data distribution by the labels' likelihood ratio so that the train and test points will look exchangeable. Figure reveals that WCP applied with the true weights attains the desired 1 a 90% coverage rate, as theoretically guaranteed in (Tibshirani et al., 2019). Nevertheless, WCP requires all test features X to be observed to compute the weights. This assumption might not hold in practice, e.g., when an individual does not share sensitive attributes at test time, such as their income or race in our MEPS example, due to privacy concerns. In such cases, WCP is infeasible and cannot be employed as is impossible to compute the weights.
account for
The goal of this work is to provide reliable inference under the setup of corrupted labels with missing features at test time (Collier et al., 2022; Wu et al., 2021; Ortiz-Jimenez et al., 2023). We refer to these features as privileged add9)aaddiionaall information available during training but unavailable at test time. In MEPS example, the privileged features are race, income, an individual's rating of feeling. and more; see Appendix B for more practical examples of PI. Privileged conformal prediction (PCP) (Feldman & Romano, 2024) is a recent novel calibration scheme that builds on WCP to generate theoretically valid prediction sets without access to the test PI. However, PCP assumes access to the true weights of WCP, a requirement that might not hold in real-world applications. Indeed, Figure 1 shows that when applied with estimated weights, PCP does not achieve the nominal coverage level on the MEPS dataset. In this work, we focus precisely on this gap: what if the true weights are unavailable?
Coverage
90.0
information (PI) (Vapnik & Vashist,
87.5
(Iriessiale)
Naive CP WCP
PCP
Ours
Figure I: Coverage rate obtained on the MEPS19 data.
1.1 OUR CONTRIBUTION
This work provides two key contributions. First, we analyze the robustness of PCP and NCP to inaccuracies in the approximated weights. We formally characterize the conditions under which these methods maintain valid coverage despite the errors of the weights. In contrast with prior work (Lei & Candès, 2021; Bhattacharyya & Barber, 2024; Gui et al., 2024; Marmarelis et al., 2024) that deal with worst-case analysis, our study reveals that PCP and WCP may construct prediction sets that attain the desired coverage rate even under significant errors in the weights, as demonstrated in empirical simulations in Section 3.1.2. Hence, the formulations developed in this work offer new theoretical guarantees and practical insights for these methods.
Second, propose uncertain imputation (UT)-a a novel calibration scheme that generates theoreti- cally valid prediction sets in the presence of corrupted labels. In contrast to WCP and PCP, which assume that the weights can be estimated well from the PI, here, we assume that the clean labels can be estimated well from the PI (Wu et al., 2021; Xu et al., 2021; Collier et al., 2022). Under several assumptions, we show how to impute corrupted labels in way that preserves the uncertainty of the imputed labels. By leveraging recent results on label-noise robustness of conformal predic- tion (Einbinder et al., 2023; Sesia et al., 2024). we theoretically show that our eeperaiinty-prseevvin imputation guarantees the validity of our proposal even when the weights are unreliable. Importantly, PCP might fail to achieve the nominal coverage level such cases. Indeed, Figure demonstrates that our proposed UI achieves the desired coverage rate while PCP does not.
Finally, we leverage the complementary validity conditions of PCP, UI, and CP, and propose combining all three into a triply robust calibration scheme (TriplyRobust) that constructs valid prediction sets when the assumptions of one of the methods are satisfied. Lastly, we conduct experiments synthetic and real datasets to demonstrate the effectiveness of our proposed methods. Software implementing the proposed method and reproducing our experiments is available at ht https: / //gi thub. com/ Shaii/haiii 28 ui
2

---

Published as a conference paper at ICLR 2026
1.2 PROBLEM SETUP
Suppose we are given n training samples {(X;, Pi, Z,, Mo) where X; E X denotes the observed covariates, Y, E y the observed, potentially corrupted, labels, Z, E Z the PI, and M; E {0, 1} is the corrptiion indicator. Specifically, if M; 0 then Y; = Y,, where Y,, is the clean, ground truth label. Otherwise, if M; = 1, then Y; is corrupted. For instance, in a missing response setup, if M; 1 then Y; "NA". At test time, we are given the test features X X and our goal is to construct prediction set ( S y that covers the test response yrest Ya+1 at a user-specified probability 1 a, e.g., 90%:
P( C(X(ee)) 2 at.
(I)
This property is called marginal coverage, as the probability is taken over all samples ((X,, Y,, Yi, Zi, M, which are assumed to be drawn exchangeably (e-g.. i...d) from Xx,YyyZ.M The primary challenge in obtaining (1) is the distributional shift between the training data Y;));= and the test pair (X,+1, Xx++1,,+1). In practice, naively applying CP on the corrupted data could lead unreliable uncertainty estimates (Barber al., 2023), overly conservative prediction sets (Finbinder et al., 2023). Moreover, calibrating using only the clean data introduces bias since the clean samples drawn from Px,y P while the test distribution is Рx,.. This bias might lead to undercoverage, as demonstrated in Figure 1.
To account for this bias, we assume the privileged information explains the corruption appearances, i... (X, Y) IL M Z. We study the robustness of PCP (Feldman & Romano, 2024) to inaccuracies
of the weights under this assumption. We then consider an alternative setup where the clean label Y can be estimated well from Z, and develop the method UT to construct prediction sets satisfying (1) even when the weights cannot be approximated accurately. Lastly, we combine all methods into triply robust calibration scheme which enjoys the validity guarantees of both methods. See Table in Appendix C.4 for summary of our results.
BACKGROUND AND RELATED WORK
2.1 CONFORMAL PREDICTION
Conformal prediction (CP) (Vovk al., 2005) is popular framework for generating prediction sets with guaranteed coverage rate (1). It splits the dataset into a training set, denoted by Z,, and a calibration set, denoted by Ig. A learning model f is then trained on the training data and its performance is assessed on the calibration set using a non-conformity score function S(-) E RR
S, = (X, f). Vi E Iz. For example, in regression problems, the score could be the absolute residual S(I, yi f) = f (z) - yl. where f represents a mean estimator. The next step is computing the (1 + 1/ [2) ax) -th empirical quantile of the calibration scores for the nominal coverage level:
Qe0 (1 1/ (1 a- empirical quantile of the scores (ith.
Finally, the prediction set for test point is defined as:
C (x {y S(x y: f)
S ".)
This prediction set is guaranteed to achieve the desired marginal coverage rate, assuming that the calibration and test samples are exchangeable (Vovk et al., 2005). Since this is not the case in our setup, the next section introduces WCP, an extension of CP designed to handle covariate shifts.
2.2 WEIGHTED CONFORMAL PREDICTION
In the previous section, we noted that prediction sets constructed by CP might fail to achieve the desired coverage level due to the corruptions in the data. To overcome this issuc, one could apply CP using only the scores of the uncorrupted samples, i.e., (S(X,, Y,, f) Hizzy, where I = (i E Iz M, = 0} are the indexes of the uncorrupted calibration samples. Although these scores computed using the true labels and are therefore accurate, considering only the uncorrupted samples induces a covariate shift between the calibration and test data. The weighted conformal prediction (WCP) (Tibshirani et al., 2019) method corrects this covariate shift by weighting the
3

---

Published as a conference paper at ICLR 2026
non-conformity scores using the likelihood ratio w(2) dPea (2), where d (2))((2). d.Prainn (z) are the densities of the test and train probabilities, respectively. In this context, the weights can be expressed
w(= P(M [Z==) (Feldman & Romano, 2024). Then, extracts the quantile of the weighted
P P(M=0)
distribution:
(Z,) Jjzzy (Zz) + w Ziest ds +
w (uuu
Que2 (ZuSt) = Quantile
1- E AEZ
800
E Ejezy Zz) + wi (iez
(3)
The prediction set is constructed similarly to (2), except for using the threshold Quc2( (Zus)). While this procedure is guaranteed to achieve the nominal coverage level, it cannot be applied directly since it relies on access to the test PI Zrest, which is unavailable in our framework.
2.3 CONFORMAL PREDICTION WITH NOISY LABELS
The works of Einbinder al. (2023); Sesia et al. (2024); Penso & Goldberger (2024); H. Zargarbashi et al. (2024); Penso et al. (2025); Bashari et al. (2025) explore the setup where CP is employed with noisy labels. The main conclusion of Einbinder et al. (2023) is that CP remains valid label noise when the noise is dispersive, i.e., increasing the variability of the observed labels. Specifically in regression tasks, their analysis reveals that CP remains valid when the noise is symmetric and additive. Their study also explores different noise models and provides empirical evidence for the robustness of CP. Building on these results, in Section 3.2, we impute corrupted labels with noisy versions the true ones in way that leads to valid coverage rate. Additional related work is given in Appendix B.
3 METHODS
In this section, we split our study into two cases based on the role of the Pl: either as an indicator of the corruption variable .M or proxy for the label Y. In the first case, for example, Z may represent an annotator's s expertise level, such that lower value may correspond to a higher likelihood of label noise. We present PCP, method for constructing reliable uncertainty sets in this setup, and analyze its robustness to inaccuracies in the estimated corruption probabilities. In the second setting, we assume that the Pl serves as a proxy for the label itself, for example, may be a high-resolution image or detailed clinical reports available only during training. For this case, we develop UT-a novel imputation technique that leverages Z to generate theoretically valid uncertainty sets.
3.1 CASE 1: WHEN THE PI EXPLAINS THE CORRUPTION INDICATOR
3.1.1 PRIVILEGED CONFORMAL PREDICTION
The PCP (Feldman Romano, 2024) procedure begins by partitioning the data into a training set, I, and calibration set, Iz. Subsequently, predictive model f is trained on the training set, and non-conformity score computed for each sample in the calibration set: S; SXx,, Y;; f), Vi E Iz- We also compute the likelihood ratio between the calibration and test distributions to calculate the weight for each sample w;== =(M=)]Z=Z]' Next, treat each calibration point in Ig test point and apply WCP subroutine using the uncorrupted calibration samples derive the score threshold (Zz)) for the i-th sample. The final test score threshold, denoted as QPCP, is then defined as the (1 - -t empirical quantile of the calibration thresholds (Q(Z.))
P(M=0)
QecP Quantile (1-3:
SQ(Z)) +
[2 + 830
I
TT
where E (0, is a pre-defined level, e.g., 33 0.05. Finally, for new test input Xtest the prediction for yiest is constructed as follows: CFCP (XTa) {u S(Xtes, y. Qece .his
prediction set is guaranteed to obtain valid coverage rate, as stated next.
Theorem (Validity of PCP (Feldman & Romano, 2024)). Suppose that {(x,, Y,, Y,, Z;, M,) nn+1 are exchangeable, Y IL M Z, and Pz is absolutely continuous with respect to P2 M= Then, the prediction set CFCP (Xws) achieves the desired coverage rate: PPyYut CCC (Xles)) > 1
4

---

Published as a conference paper at ICLR 2026
The above theorem provides valid coverage rate guarantee even without access the test PI Z and despite the corruptions present in the data. Nevertheless, the true weights wi are required for this guarantee to hold. In the following section, we study the robustness of PCP to inaccurate weights. Surprisingly, our analysis provided hereafter reveals that PCP can achieve the nominal coverage rate even when applied with inaccurate approximates of wt:
3.1.2 IS PCP ROBUST TO INACCURATE WEIGHTS?
The following robustness analysis of PCP is divided into two parts. First, consider case where the inaccurate weights [w:);-1 are shifted by a constant error E E from the true weights for all samples. In the second, we extend the analysis to a more general setting where the error varies across samples. We remark that the theory developed in this section also applies to WCP, as detailed in Appendix A. We begin by examining the case of constant error, formulated as:
i = w, + 6, vi= 1..... n.
We remark that, in this analysis, we do not consider the sign of the weights and allow them become negative. We denote the sum of the true weights by W₂ = Σÿ= wy and recall that QueP from (3) is the threshold constructed by WCP using the true weights. We also denote by Q the threshold generated by Naive CF, which is CP from Section 2.1 applied using only the uncorrupted data; Appendix A.1.1 for more details. These notations set the ground for the conditions required for PCP to achieve the desired coverage rate.
Theorem 2. Suppose that the assumptions Theorem hold. Further, suppose that at least one of the 2 1 - and 8 2 0, (2) TP (Q QWPP
following holds: (1) (Q
W QWOPP)
8 < Wa+1
2 1 s;
a+1
(3) IP @ <QUEP,& ,8> prediction set CFCe constructed by PCP with weights shifted by 6, as in (4), satisfies:
1 and 5 S 0; (4) P (Q = Q (CP) 2 1 - &. Then, the
at1
P(y E CFCP ( (Xter)) 2 1- a
The proofs are provided in Appendix A. If Na Nvvve CP attains the nominal coverage rate, i.e., QeP > QR02 PCP also achieves high coverage even when the weights are poorly estimated (6 > 0 or ò is sufficiently negative). However, if Naive CP undercovers, i.c., Q < Quice, then the weights must be accurate for PCP to be valid, specifically, 8 must lie within the narrow interval
WW 0).
We demonstrate Theorem 2 on two synthetic datasets. In the first dataset, Naive CP achieves over-coverage. while in the second, Naive CP undercovers the response. For each dataset, we apply PCP using weights shifted by 6, as in (4). We refer to Appendix D.3 for the full details about this experimental setup. The coverage rates of PCP for different values of 5 are shown in Figure 2. This figure indicates that when Naive CP over-covers, PCP achieves valid coverage for 5 2 or
5 <
Wa+1
n+1 x 1. However, when Naive CP undercovers, 8 must lie within (- (-#+1" .) for
PCP to achieve the nominal coverage rate. This result is connected to the MEPS experiment from Figure I in which Naive CP and PCP undercover the response, indicating that the weight error does not fall inside the interval. In conclusion, the empirical regions of in which PCP is valid that observed in this experiment align with the theoretical bounds from Theorem 2.
Next, we consider the setting in which the errors are not uniform:
W = wi + 8,, Vi = L,..., n.
(5)
We assume that the errors are bounded: &, E [dmin, dmax] for some dmin dmax E R and d, = (6.
Smin) / Ômin) are the normalized errors. We denote the XOR operator by (a XOR b)
((not a) and b) or (a and (not b)), and the NXOR operator by (a NXOR 8) = (not (a XOR b)). We also denote by MCC the index of the score corresponding to the threshold Q from (3), generated by
WCP with true weights: s == min {k: Σt_ wx/Wn+1 2 1 11-aa -). We now derive the conditions
under which PCP applied with weights of a general emor achieves valid coverage.
Theorem 3. Suppose that the assumptions in Theorem I hold. Further suppose that one of the following is satisfied:
5

---

Published as a conference paper at ICLR 2026
Naive CP achieves under coverage
Naive CP achieves over coverage
100
100
Coverage
Coverage
50
PCP w/ approx. weights
50
PCP w/ approx. weights
90%
90%
0
-2
-2
0
1
2
Figure 2: The coverage rate of PCP applied on synthetic data with weights shifted by 8. Green: valid coverage region, orange: invalid coverage region. Left: Naive CP under-covers the response. Right: Naive CP achieves over-coverage. Results are averaged over 20 random splits of the data.
1. P Qe0 < <QUOP, (5
Ant1 Wa Jice Wa+1 NXOR Ómin Watikas k (m+I) ANEP
Omn Amw 11
n+ Anti
E,
2. P (Q0h: > Quer, (ō
A.ti Waner - Aunce W Wa+t kai 1)
XOR 8min
A..1+ 21-6
++1-An11
3. IP (Q QhoP, (ā
Anti W WAn Ann Wn+1 NXOR A sac
Wance
))
1-
Wx (n+t)WWn
Bnt1
Cx
Above, Å = 5, and == Smin/ (6mus mm Then, the prediction set CP (X constructed by PCP with weights shifted by general error, in (5), attains the following coverage rate:
P(y CC (x(er)) 2 1-
Theorem establishes the connection between the errors ó, and the validity of PCP. Similarly to the constant error setting, the validity of PCP depends on whether Naive CP obtains overcoverage or undercoverage. Here, however, the region of 6min max in which we attain valid coverage is more complex and determined by the true weights wy and the distribution of the normalized errors 8, In the case that Naive CP achieves overcoverage, the validity region is defined by the XOR of two variables, whereas in the case of undercoverage, the validity region is the exact complement, and given by the NXOR of the same variables.
Figure 8 in Appendix F.2 illustrates the coverage validity of PCP along with the theoretical bounds derived in Theorem for various combinations of 6min; Ōmin- We experiment on the same synthetic datasets from Figure 2 while using weights with varying errors. We examine two distributions of 5,: uniform distribution and right-skewed distribution, where most samples are concentrated in the top 5% of the range (dmin: dmax). See Appendix E.2 for further details regarding the experimental setup. This figure shows that the bounds of Theorem 3 align with the empirical coverage validity of PCP, with minor discrepancies arising from interpolating discrete values. Furthermore, this figure reveals that different error distributions of ó; yield diverse validity regions: the validity region of uniform distribution diagonal, while the validity region of the right-skewed distribution is horizontal. Moreover, we observe a pattern similar to the one observed in Figure 2: when Naive CP overcovers the response, the validity region extensive, spanning almost the entire space, excluding one interval. In contrast, when Naive CP undercovers. the validity region is limited to one interval. Finally, we refer to Appendix F.2 for additional experiments demonstrating the effect of inaccurate weights on the coverage rate attained by PCP.
3.2 CASE 2: WHEN THE PI EXPLAINS THE LABEL
In this section, we introduce uncertain imputation (UT), a novel and different approach address corrupted labels, which, in contrast to PCP, does not require access to the conditional corruption probabilities. With UI, however, we use the PI, which is always observed, to impute the corrupted labels with uncertain version of them, and show that this procedure achieves valid coverage rate under several assumptions. This way, UI can obtain valid coverage even when PCE does not. Intuitively, UI is more useful than PCP when Y is relatively easy predict given X, Z.
We begin by splitting the data into three parts: a training set, I, a calibration set, Iz, and a reference set Ig, from which the residual emrors will be sampled to account for the uncertainty in the estimated

---

Published as a conference paper at ICLR 2026
labels. Then, we fit two predictive models to estimate the response using the training data: (1)
predictive model (x) that takes an input only the feature vector X --a as in standard CP; and (2) an additional predictive model ((x, 2) that utilizes both the feature vector X and the PI to predict Y. Next, we compute the residual error of ğ for each point in the reference set:
E Y (X,, Z.), Vi E Iz.
(6)
We define {z) as a reference set of holdout errors conditional on z, i.e. {(2) == (E;: : I3, Zi = F, M, 0} and denote by E(z) random variable drawn uniformly from E(z). We impute the corrupted labels using this set, and denote the imputed label by Y;:
Y L0(X, 2.) + E(Z,)
if M, = 0, otherwise
V
Vi E I2
Next, compute the non-conformity scores of the imputed calibration set, denoted by S S: s(X,, Y6 A Vi E Ig, and define the threshold using these scores:
DI_ == Quantile 1 a;
Σ IE
8s. + [22l + 600 )
In
+1
Finally, for new input data Xtest, we construct the prediction set for yost as: C (X y: S(X v. s Qui J. We summarize this procedure in Algorithm 2 in Appendix C.3. We now show that JJ achieves valid marginal coverage rate if (1) 9 is sufficiently accurate; and (2) the set C contains all peaks of the distribution of Y X, Z, as formulated next.
Theorem 4. Suppose that {(X,, Y,, Y., Zi M.) are i.i.d,, and (X,Y) TL M Z. Denote by (x)(x) = [a(x), b(x) the prediction set constructed by UI that draws errors from the true distribution of E Z. Suppose that Y follows the model: Y = (X, a distribution PE- and = 1L X Z. Further, suppose that
(X,2) Z) + e, where e is drawn from
1. 9 is sufficiently uccurate so that there exists a residual Rees satisfying: (a) g(Xee Zierr= =
g" (Xics 2 + Riest and (b) piess 11 (9" (X 3 CUI (X Zieus
2. For every 2 E Z and x E X such that fx= 2 (2, 2) the density of y X
(I,2) x, Z = z is peaked inside the interval (a(x), b(x)), i.e.,
(a) Yu > 0: fyud X mx, 7 (b(x) + v) S frae X 7 (b(x) v), and
(b) Vu > 0:
v) S
(a(x) + v).
Then, P(Y C"T 2 2- a
The proof is given in Appendix A.2. We pause here to clarify the assumptions of Theorem 4. The first assumption requires that the residual errors are independent of the prediction of 9 and of Co given the PI Z. Notably, this assumption does not restrict the distribution of the errors or their magnitude and holds even under substantial errors. Intuitively, this means that the PI serves as good proxy for Y. For example, in medical imaging, a pathologist's diagnostic report can act privileged information that predicts tissue diagnosis. In this case, we require that the predictor that estimates Y from the Pl is accurate up an error that independent of g" C conditional on Z. The second assumption of Theorem states that the distribution of Y X, Z is concentrated in the predicted interval, and that the density Y y decreases as we move away from this interval. Importantly, this assumption does not limit the number of peaks in the distribution of Y X, Z, as long as all such peaks are inside the interval. Moreover, since the PI is strongly indicative of the label in our framework, the distribution of Y X, Z is expected to be relatively simple in practice. Overall, this assumption is relatively mild, particularly for prediction intervals that aim to achieve a high coverage rate. In Appendix F.5 demonstrate in experiments that UI can obtain valid coverage even when the independence requirements of this theorem are not exactly satisfied. We remark that in practical applications, if Z is continuous or digh-dimensional, the reference set E(2) might be empty or too small. To alleviate this, we recommend employing the clustering techniques described in Appendix C.3.I.
7

---

Published as a conference paper at ICLR 2026
3.3 TRIPLY ROBUST CONFORMAL PREDICTION WITH PRIVILEGED INFORMATION
Recall that PCP and UI rely on different sets of assumptions to provide a theoretical guarantee. Therefore, we propose combining these calibration schemes enjoy the robustness guarantees of both methods. In addition, since Naive CP generates valid prediction sets when the underlying model f is ideal, we include it in the ensemble of the calibration schemes. In sum, this Tripl yRobust method takes the test features vector X and unifies the prediction sets of all three methods:
CTrip plrtpbyt (Xtet) Caavvv cp (P(" CPCP (X!=t) C C (X!ss).
(8)
This approach achieves the nominal coverage rate if the assumptions of one of the methods hold:
Theorem 5. Suppose that {(X;, Y,, Y,, Zi, M are exchangeable, and (X,Y) TT M Z. Further, suppose that at least one of the following is satisfied: (1) The model is sufficiently accurate so that the scores {S(X,, Y; f) : ..., n, M, 0} U {S(X"" y f)} are exchangeable; (2) The assumptions Theorem hold; (3) The assumptions of Theorem hold. Then, the prediction set C"eiplyRobust (Xiss) from (8) achieves the desired coverage rale:
(x P(Y E e C'rrplyyobust (Xlee) 2 21-a.
Intuitively, Theorem 5 guarantees that Tri Priplyy plyRobust. generates valid uncertainty sets at least one of the following distributions is well-estimated: Y X (Naive CP), M Z (PCP), Y Z (UI). In the following section, we demonstrate the robustness of this approach.
4 EXPERIMENTS
In this section, we quantify the effectiveness of our proposed techniques through three experiments. In all experiments, the dataset is randomly split into four distinct subsets: training, validation, calibration, and test sets. For the UI method, the original calibration set is further partitioned into reference set and calibration set. The training set used for fitting a predictive model, and the validation set is used for early stopping. The model is then calibrated using the calibration data, and the performance evaluated on the test set over 30 random data splits. Moreover, we use the CQR (Romano et al., 2019) non-conformity scores, aiming obtain 1 the training methodology, datasets, corruption techniques, and the overall experimental protocol are given in Appendix E. We further demonstrate our proposals a causal inference task using the NSLM dataset (Yeager et al., 2019) in Appendix F.3.
90% coverage rate. The full details regarding
4.1 SYNTHETIC EXPERIMENT: THE ROBUSTNESS OF TRIPLYROBUSE
We demonstrate the robustness of TriplyRobust by combining degenerate and oracle variants of each underlying component: quantile regression (QR). PCP, and UI. We generate a synthetic dataset with 10-dimensional inputs X. 3-dimensional privileged information Z, and continuous response Y that is function of X and Z. The dataset is artificially corrupted by removing labels, such that labels with greater uncertainty have higher probability of being removed. The degenerate variant of QR outputs the trivial prediction set {0). while the oracle version uses the true conditional quantiles of Y X to achieve the desired conditional coverage. Similarly, the degenerate version of PCP computes weights using half the true corruption probabilities. In contrast, its oracle counterpart employs the correct probabilities. The trivial imputation method assigns missing labels the value O, while the oracle method draws labels from the true conditional distribution of Y Z. Figure 3 shows that when all three components are degenerate, than the nominal level. However, when at least one technique is oracle-based, TriplyRobus produces valid uncertainty estimates. This experiment reveals that the coverage rate achieved by TriplyRobuse not overly conservative, despite being union of three intervals.
achieves a coverage rate lower
4.2 SYNTHETIC EXPERIMENT: WEIGHTS ARE HARD TO ESTIMATE
To demonstrate the advantages of UI compared PCP, adopt the synthetic setup from Feldman Romano (2024), where Z is a strong predictor of Y. The only difference is that we engineer the missingness mechanism to be challenging estimate; Appendix D.3 for details. Figure
8

---

Published as a conference paper at ICLR 2026
degenerate QR
oracle QR
Coverage
90
PCP
degenerate oracle
80
degenerate
oracle
degenerate
oracle
Imputation
Imputation
Figure 3: The coverage achieved by TriplyRobust with "degenerate" or "oracle" models.
Interval length
4
Coverage
3
85
Naive CP
PCP
Uncertain Imp.
Naive CP
PCP
Uncertain Imp.
Figure Complex weights experiment. The performance of Naive CP, PCP and UI.
shows that PCP fails to attain the nominal 90% coverage rate due to inaccuracies in the estimated weights. In contrast, UT relies accurate estimates of Y from (X, Z) rather than weights; therefore, it consistently achieves the desired coverage, as guaranteed by Theorem 4. This experiment demonstrates that UI can achieve the desired coverage rate, even in cases where PCP does not.
4.3 REAL DATASETS WITH ARTIFICIAL CORRUPTIONS
In this section, we evaluate the proposed UI in missing response setup using five benchmarks used in Feldman & Romano (2024): Facebook 1,2 (facebook), Bio (bio), House (house), Meps19 (meps 19). We follow Feldman & Romano (2024) and artificially define the PI as the feature in X with the highest correlation to Y and remove it from X, that the PI is unavailable test time. Since all true labels are available in the original datasets, we artificially remove 20% of them similarly to Feldman Romano (2024) to induce a distribution shift between missing and observed variables.
We employ the naive conformal prediction (Naive CP) that uses only the observed labels, PCP, with either estimated corruption probabilities or true ones used for computing the weights w=z), and the proposed UI. Additionally, to demonstrate the importance of the error sampling scheme of UI, we apply CP with a naive imputation scheme that replaces missing labels with the mean estimates of Y X, Z (Na i Imputation). The performances of all calibration schemes are presented Figure This figure indicates that the naive approaches produce too narrow intervals that do not achieve the desired coverage level. This is anticipated, as the validity guarantees of CP do not hold under distribution shifts or naive imputations. However, PCP, and the proposed UI consistently achieve the target 90% coverage level, as they appropriately account for the distributional shift. This is also indicated by Theorem Notably, since PCP with estimated weights is valid while Na lvee CP is not, Figure 2 suggests that weight estimation errors fall within the theoretical validity region. Overall, this experiment reveals that UI constructs uncertainty intervals that are both statistically efficient and reliable. The performance of Tripl yRobust this experiment is provided in Appendix F.6.
DISCUSSION AND IMPACT STATEMENT
In this work, we analyzed the impact of inaccurate weights on WCP and PCP, and introduced UI, a novel calibration technique for reliable uncertainty quantification under corrupted labels. Our theoretical guarantees, supported by empirical experiments, demonstrate that UI constructs valid uncertainty estimates. While the validity conditions we derived for WCP and PCP are theoretically grounded, they require access to true weights, which unavailable in practice. This calls for promising future research direction in estimating these conditions from the available data. One limitation of our proposed UT is that requires the features and responses to be independent of

---

Published as a conference paper at ICLR 2026
Method
Coverage
90
Naive CP
Naive Imp.
80
PCP (est. weights)
facebook1
facebook2
bio Dataset
house
meps19
PCP (oracle weights)
Uncertain Imp.
Interval length
facebook1
facebook2
bio
house
meps19
Dataset
Figure 5: Missing response experiment. The performance of various methods; see text for details.
the corruption indicator given the privileged information, which resembles the strong ignorability assumption in causal inference (Rubin, 1978; Rosenbaum & Rubin, 1983; Imbens & Rubin, 2015). Furthermore, our approach assumes that the label variability depends only on the PI and that the labels can be accurately estimated from the features and PI. In practice, our experiments indicate that our method attains valid coverage. Future work could explore extending our theoretical guarantees to multiple-annotatee settings and incorporating privileged information into ambiguity-awee awaare calibration methods Javanmardi et al. (2024); Caprio et al. (2025). Finally, we acknowledge potential social implications, akin to many developments ML.
ACKNOWLEDGMENTS
Funded by the European Union (ERC, SafetyBounds, 101 101163414) Views and opinions expressed are however those the authors only and do not necessarily reflect those the European Union or European Research Council Executive Agency (ERCEA), Neither the European Union nor the granting authority can held responsible for them. Y.R. thanks the Career Advancement Fellowship, Technion.
REFERENCES
Anastasios N. Angelopoulos and Stephen Bates. Conformal prediction: A gentle introduction. Foundations and Trends0 in Machine Learning, 16(4):494591, 2023. ISSN 1935-8237.
Rina Foygel Barber, Emmanuel Candès, Aaditya Ramdas, and Ryan J. Tibshirani. Conformal prediction beyond exchangeability. The Annals of Statistics, (1):)8816 845, 2023.
Meshi Bashari, Matteo Sesia, and Yaniv Romano, Robust conformal outlier detection under contami- nated reference data. arXiv preprint 2xXi:25522.08077, 2025.
Aabesh Bhattacharyya and Rina Foygel Barber. Group-weighted conformal prediction. arXiv preprint arXiv:2401.17452 2024.
bio.
Physicochemical properties of protein tertiary structure data set. https: //archive ics uci http://ddmmmmmaamaeeeeae//aa ippppsicocheeeee Par.iiaaatteoeeeesss.seee of oer
Accessed: Jamuary, 2019.
Jennie E Brand and Yu Xie. Who benefits most from college? evidence for negative selection in heterogeneous economic returns higher education. American sociological review, 75(2): 273-302, 2010.
Michele Caprio, David Stutz, Shuo Li, and Arnau Doucet. Conformalized credal regions for classification with ambiguous ground truth. arXiv preprint (tl::2//1.048555 2024.
10

---

Published as a conference paper at ICLR 2026
Michele Caprio, David Stutz, Shuo Li, and Arnaud Doucet. Conformalized credal regions for classification with ambiguous ground truth. Transactions on Machine Learning Research, 2025.
ISSN 2835-8856.
Carlos Carvalho, Avi Feller, Jared Murray, Spencer Woody, and David Yeager. Assessing treatment effect variation in observational studies: Results from data challenge. Observational Studies, (2):21-35, 2019.
Mark Collier, Rodolphe Jenatton, Effrosyni Kokiopoulou, and Jesse Berent. Transfer and marginalize: Explaining away label noise with privileged information. In International conference on machine learning, pp. 4219 4237. PMLR, 2022.
Bat-Sheva Einbinder, Shai Feldman, Stephen Bates, Anastasios Angelopoulos, Asaf Gendler, and Yaniv Romano. Conformal prediction is robust to dispersive label noise. In Conformal and Probabilistic Prediction with Applications, pp. 624-626. PMLR, 2023.
facebook. Facebook comment volume data set. https: https://archi //rchiireeeeeeee ics. uci .dd holu/mm// ml datasets Sattaastss/Faeebook-ooee Comment + +Volum
Accessed: January, 2019.
Shai Feldman and Yaniv Romano. Robust conformal prediction using privileged information. In
The Thirtt-eighth Annual Conference on Neural Information Processing Systems, 2024. URL
https: ht/p//peeevviiieeeeeeeeeeeeeeeee net. / forum? d=
Shai Feldman, Liran Ringel, Stephen Bates, and Yaniv Romano. Achieving risk control in online learning settings. Transactions Machine Learning Research, 2023. ISSN 1835-8856.
Jean-Pierre Florens, James J Heckman, Costas Meghir, and Edward Vytlacil. Identification of treatment effects using control functions in models with continuous, endogenous treatment and heterogeneous effects. Econometrica,
2008
Isaac Gibbs and Emmanuel Candes. Adaptive conformal inference under distribution shift. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021.
Isaac Gibbs and Emmanuel J Candès. Conformal inference for online prediction with arbitrary distribution shifts. Journal of Machine Learning Research, 2--1 2024.
Yu Gui, Rohan Hore, Zhimei Ren, and Rina Foygel Barber. Conformalized survival analysis with adaptive cut-offs. Biometrika, 111(2)459-477, 2024.
Soroush H. Zargarbashi, Mohammad Sadegh Akhondzadeh, and Aleksandar Bojchevski. Robust yet efficient conformal prediction sets. In Ruslan Salakhutdinov, Zico Kolter. Katherine Heller, Adrian Weller, Nuria Oliver. Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 17123-17181 PMLR, 21-27 Jul 2024.
Miguel A Hernán and James M Robins. Causal inference, 2010.
house. House sales in king county, USA. https: /www. kaggle ccom/hartie housesalespredicte.
me aataaaa. Accessed: July, 2021.
Guido W Imbens and Donald B Rubin. Causal inference in statistics, social, and biomedical sciences. Cambridge university press, 2015.
Alireza Javanmardi, David Stutz, and Eyke Hüllermeier. Conformalized credal set predictors. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang (eds.), Advances Neural Information Processing Systems, volume 37, pp. 116987-117014. Curran Associates, Inc., 2024. doi: 10.52202/079017-3377
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Inter- national Conference on Learning Representations, 2015. URL http:://axiv.. org /abs/ 1412. 6980.
Roger Koenker. Quantile regression, volume 38. Cambridge university press, 2005.
11

---

Published as a conference paper at ICLR 2026
Roger Koenker and Gilbert Bassett. Regression quantiles. Econometrica: Journal of the Econometric Society, pp. 33-50, 1978.
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):111-935 2021.
David Lopez-Paz, Léon Bottou, Bernhard Schölkopf, and Vladimir Vapnik. Unifying distillation and privileged information. arXiv preprint arXiv:/511.03644 2015.
Myrl G Marmarelis, Greg Ver Steeg, Aram Galstyan, and Fred Morstatter. Ensembled prediction intervals for causal outcomes under hidden confounding. In Causal Learning and Reasoning, pp. 18-40. PMLR, 2024.
meps_19 19. Medical expenditure panel survey, panel 19. data_stat down oad files_flleeeteeeeee jaap:ccooufNuumbreettt cessed: January, 2019.
Ac-
Stephen L Morgan.
Counterfactuals, causal effect heterogeneity, and the catholic school effect on learning. Sociology of education, pp. 341-374, 2001.
Guillermo Ortiz- vitiz-Jimenez, Mark Collier, Anant Nawalgaria, Alexander Nicholas D' Amour, Jesse Berent, Rodolphe Jenatton, and Efi Kokiopoulou. When does privileged information explain away label noise? International Conference on Machine Learning, pp. 26646-26669. PMLR, 2023.
George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshminarayanann Normalizing flows for probabilistic modeling and inference. Journal of Machine Learning Research, 22( 2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high pert-rmancoreeeee deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-28308 2011.
Coby Penso and Jacob Goldberger. conformal prediction score that robust label noise. arXiv preprint 205502240,,02648, 2024.
Coby Penso, Jacob Goldberger, and Ethan Fetaya. Estimating the conformal prediction threshold from noisy labels. arXiv preprint arXiv:2501.12749 2025.
Taylor Pospisil and Ann B Lec. Rfede: Random forests for conditional density estimation. arXiv preprint S05.::8800000755 2018.
Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows. In International conference on machine learning, pp. 1530-1538. PMLR, 2015.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Advances in neural information processing systems, 32, 2019.
Paul R Rosenbaum and Donald Rubin. The central role of the propensity score in observational studies for causal effects. Biometrika, 70(1):41-55 1983.
Donald B. Rubin. Inference and missing data. Biometrika, 63(3):581-592 12 1976. ISSN 0046-3444. doi: 10.1093/biomee/633.555 URL https: /dwi. http://i..orrr//// org/10. 1093/0990ii/ htt////iie///////eee/eeeeeeeeeee 16.3334644 3..33.3.... 581.
Donald B Rubin. Bayesian inference for causal effects: The role of randomization. The Annals of statistics, pp. 34-58, 1978.
12

---

Published as a conference paper at ICLR 2026
Donald B Rubin. Multiple imputation after 18+ years. Journal of the American statistical Association, 91(434):473 489, 1996.
Donald B Rubin. Multiple imputation. In Flexible imputation of missing data, second edition, pp. 29 62. Chapman and Hall/CRC, 2018.
Matteo Sesia, YX Rachel Wang, and Xin Tong. Adaptive conformal classification with noisy labels. Journal of the Royal Statistical Society Series B: Statistical Methodology, pp. qkael 14, 2024.
Ingo Steinwart and Andreas Christmann. Estimating conditional quantiles with the help of the pinball loss. Bemoulli, 17:211-225, 2011. URL https: /tpp//app..p/// ses.steettt.cccc..a...... org/
22xpusID:21704877
David Stutz, Abhijit Guha Roy, Tatiana Matejovicova, Patricia Strachan, Ali Taylan Cemgil, and Araad Doucet. Conformal prediction under ambiguous ground truth. arXiv preprint arXiv:2307.09332. 2023.
Ichiro Takeuchi, Quoc Le, Timothy D Sears, Alexander Smola, and Chris Williams. Nonparamet- ric quantile estimation. Journal of machine learning research, 7(7), 2006.
Ryan J Tibshirani, Rina Foygel Barber, Emmanuel Candes. and Aaditya Ramdas. Conformal prediction under covariate shift. Advances in neural information processing systems, 32, 2019.
Vladimir Vapnik and Akshay Vashist. A new learning paradigm: Learning using privileged informa- tion. Neural networks, 22(5-6):544-5555 545-577, 2009.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in Random World. Springer, New York, NY, USA, 2005.
Zhengning Wu, Xiaobo Xia, Ruxin Wang, Jiatong Li, Jun Yu, Yinian Mao, and Tongliang Liu. Lr- svm+: Learning using privileged information with noisy labels. IEEE Transactions on Multimedia, 14:1080-1092, 2021.
Yu Xie, Jennie Brand, and Ben Jann. Estimating heterogeneous treatment effects with observational data. Sociological methodology, 42(1):314-344 2012.
Chen Xu and Yao Xie. Conformal prediction for time series. IEEE transactions pattern analysis and machine intelligence, 15((0)111575-11887, 2023.
Liyuan Xu, Heishiro Kanagawa, and Arthur Gretton. Deep proxy causal learning and its application to confounded bandit policy evaluation. Advances in Neural Information Processing Systems, 34: 26264-26275, 2021
Shuo Yang, Sujay Sanghavi, Holakou Rahmanian, Jan Bakus, and Vishwanathan SVN. Toward understanding privileged features distillation in learning-to-rank, Advances in Neural Information Processing Systems, 15:226558-26700 2022.
David S Yeager, Paul Hanselman, Gregory M Walton, Jared Murray, Robert Crosnoe, Chandra Muller, Elizabeth Tipton, Barbara Schneider, Chris S Hulleman, Cintia P Hinojosa, al. A national experiment reveals where a growth mindset improves achievement. Nature, 573(7774)3364336) 2019.
Margaux Zaffran, Olivier Féron, Yannig Goude, Julie Josse, and Aymeric Dieuleveut. Adaptive conformal predictions for time series. In International Conference on Machine Learning, pp. 25834-25866. PMLR, 2022.
Margaux Zaffran, Aymeric Dieuleveut, Julie Josse, and Yaniv Romano. Conformal prediction with missing values. In International Conference on Machine Learning, pp. 40578-40604, PMLR, 2023.
Margaux Zaffran, Julie Josse, Yaniy Romano, and Aymeric Dieuleveut. Predictive uncertainty quantification with missing covariates. arXiv preprint wxXi:2405.11644 2024,
Zhongheng Zhang. Missing data imputation: focusing on single imputation. Annals of translational medicine, 4(1):9, 2016.
13

---

Published as a conference paper at ICLR 2026
A THEORETICAL RESULTS
A.1 ANALYSIS OF INACCURATE WEIGHTS ON WEIGHTED CONFORMAL PREDICTION
In this section, analyze the coverage rate achieved by WCP applied with estimated (inaccurate) weights. Before we present the analysis, we begin by defining notations that will be used throughout the theoretical analysis.
A.1.1 NOTATIONS
Suppose, without loss of generality, that the indices of the calibration set are {l,.... nj. For the simplicity of the proof, we suppose without loss of generality that the indices are sorted by the score, i.c.,
Vi E (1,-.., - : S Si+1
For ease of notations, define Su+1 = oc, while the score of the test sample is denoted by S(X+11, Mn+1; f). Recall that the ground truth weights used by WCP are formulated by:
S7
Wi = ((.))
frain (4)
The inaccurate weights denoted by úi;- The true normalized weights formulated by: pt W where WA Σ)=1 wy partial sum of weights. Similarly, we denote the normalized inaccurate weights by pt. We denote the threshold chosen by WCP with the oracle weights { by Quee, which is the (1 a:) empirical quantile of the distribution > p:os, + Pn+ 800. The corresponding index &CP defined as:
wi
NCP
min
h:
2 1
Similarly, denote by QUEC the threshold chosen by WCP applied with the inaccurate weights w;, which the a empirical quantile of the distribution Σ,= p:og, + Pn+10 Finally, we denote by Q the threshold of naive CP applied with weights, and by &CP its corresponding index:
& k
min
(10)
1=1
Notice that the interval constructed by WCP with oracle weights is given by:
CRCPP (x) = {y e y S(x, vi & QNCF),
and similarly, the interval constructed by WCP with the inaccurate weights is
SweP (x) = (y E y S(x, y. s )
(11)
A.1.2 CONSTANT ERROR
In this section, consider the setting where the inaccurate weights have constant bias from the ground truth ones across all samples. Formally, we assume that there exists 8 such that:
W == + 8, Vi E [l.....n}.
The normalized inaccurate weights are therefore given by:
w
+ 5 [ +)
8
Dj
2j=1
W + (n + 1)6"
We begin with a general lemma that provides a deterministic connection between f and ANCP, as defined in (10) and (9), respectively.
Lemma 1. Suppose that the calibration set is fixed, and equals to {(x,, Y, 2z) = (x,, Vs. 2z) ) for some Ha E X, ys E D 2, E Z for all E (I....,n) Further suppose that the test PI is fixed as well, i.e., Zat1 = 2 for some E Z. Then, QUEPP 2 QuEP if and only if one of the following is satisfied:
14

---

Published as a conference paper at ICLR 2026
1. kP >> kete and (6 2 or 8 <
Wai1 at1
2. kcp < kNP and
Wn+1 n+1
< <0
3. kCp k
Furthermore, QUeP= 2 20 if and only if one of the following is satisfied:
1. kep >> kNee and (6
W.11)
n+1
2. kc < kWce and
Wn+1 n+1
< 6
3. kcD = kNCP
Proof. If 5 = then v;; = ne for all i and thus the intervals constructed by WCP with the oracle weights Wt are identical to the ones constructed with the inaccurate weights ú; and therefore achieve the same coverage rate. From this point on, we only consider 8 o O. Furthermore, if 8 W.,
n+1
then p. is not defined and hence we do not consider this case and suppose that ö + Wn+1, Observe that
x+1
Ps
k
NCC
QUCF
QUCP.
We now analyze when Di=1 5 > 0:
Pi
Di=1 Ps is satisfied. We split into three cases. First, we consider
P
Ps
1=1
t=1
Wane + A.0C 8
W
W n+1 (n 1)6
W n+1
(W + 1.0P Wn++1
W Wn+11 + (n + 1)6)
R9c2 Sw n+1
W (n + 1)6
RPCP
WER
8
n +
W n++1
RCP
W
1
Wn+1
NCP
We now turn
Wa+1 n+1
< 8 < 0:
ps S
Pi
1=1
i=1
W ANNCO + AOOP 5
W n+ + (n 1)8
W
(W + k MCP 8) W n1 S WAec (W + (n+ 1)6)
90? 8W n+1 S
WAme (n + 1)8
Ance
Weme
+ 5 <
Wn+1
1 MCP
W WEAn
1
Wh+1
NCP
15

---

Published as a conference paper at ICLR 2026
Finally, if Wa11
k
Pr
Pi
1=1
2m
WARCS + A:RPP 8
Waas
W n+1 (n 1)6
W n+1
(W A0CD + 1000 8) Wnn1
Waeer (W n+1 (n + 1)6)
k oWn+1
WA (n + 1)8
k
W 8
n
Wn+1
kRCP
Wyas
1
Wn+1
cC
2
kaCP
We now compare the threshold of WCP applied with inaccurate weights the threshold of naive CP:
A
Wg A:P88
kC
MCP
MPP 2 c2
S
n2 ++1
W + (n+ + 1)8 7 + 1
If 8 >
We. a+1
then:
WRO + &CPO
kCP
Wn+1= + (n + 1)8 n +
(W + h. 8) + +1) S c Wa+1
c (n + 1)6
Wk (n + 1) S &
W (n + 1) s B+FW+t
W
k
Wn+1 n+1
CP KCP
If 8 <
W.
then:
#+1
QuCP 2 -00
W A2
c.
cP
RCP
W
W1+1
We now present stochastic result that states the conditions under which WCP achieves a conserva- tive coverage rate with inaccurate weights. Here, the randomness is taken over random draws of (Xn+1, Yn+1) from Px,y|2-
Proposition 1. Suppose that the calibration set is fixed, and equals to {(2,, Yi, Z.) (x Vo. 2, Ti for some I; E X. y/s E V, 24 E Z for all E f1,..., n). Further suppose that the test PI is fixed as well, i.e., Zn+1 = 2 for some E Z. Then, CNNC (Xn-1). as defined in (11), achieves a conservative coverage rate, i.e.:
IP(Y+1 E (ORF((n (Xn-1) Zn+1 =,, = Y1, Zi) (1ir {/))
P(YY+ E C.CF (PRCF(Xn-1) Zn+1 = z, ((xi, Zi) (2i, Vi, =
if one of the following is satisfied:
1. c > weY and (6 2 0 or 8 <
Wa41 n+1
2. CC < RCP and
Wa+1 a+l
< 50
16

---

Published as a conference paper at ICLR 2026
3. kCP kNCc..
If the above holds with probability at least E over the drawing of Znti, then we get high marginal coverage rate:
P(Y++1 E C (Xn+1) (,, (1t, Vs, 2))1==1)
2 P(n++ E C (Xn+1) f(X,, Y,, Y,, (It, Vs, 21) E.
Furthermore, CHCP (Xa+1) achieves higher coverage rate than Naive CP, i.e,
P(Y++1 E CNCC (Xn+1) Zu+1 = ((2,, Yú, Zi) = (Zi, yi, 2im) 2 P((Y++1 E CC (Xn+1) Zn+1 = 2, f(X, Y,, Z,) = (I Vi, 2)))
if one of the following is satisfied
Wo+1 kce >> kace and <
a+1
< 8 2. kCp < kccP and W
n+1
3. kcP R.CP.
If the above holds with probability at least 1 - for the drawing of Zn+1. then, we get a high marginal coverage rate:
P(Yx+1 E SUEP (Xn+1) 1 | {(X,, Y, 2.) = (z Bir 2:))
2 PY E CC (Xn+1) {(X,, Y,, Z.) = (I Mis 2)))=1) -
Proof. The probabilities in this proof are taken for drawing (X,+1, Yn+1) ~ Px, conditional on the fixed calibration set [(X,, Y,) (xi y: }== and the fixed test PI 7n+1 z. For ease of notation, we omit the conditioning on the calibration set the formulas. Notice that in this case, Q Q
Qee are deterministic since these are functions of the calibration set and the test PI Zn+i. Observe that by the construction of the uncertainty sets:
QUCP and
Q Qu22 P(Yn+1 C (X Zut1 =) P(Y E CHCP (Xn+1) Z =2),
QUCP 2 Q = P(Y+t1 E CNiC (X,+1) Zn+1 = PY E C22((enX Zut1 = 2).
Therefore, IP(Y++1 CHCP (Xn+1) Z 2) 2 TP C (Xx+1) )
7 2) holds if
QueP 2 QMEP, which, according to Lemma 1, is equivalent assuming that one of the following satisfied:
1. hT Mc2 and (6 2 or 8 W n+1
2. k < wcs
and
W
6550 0 ++1
3. k 1ice
Denote the event that one of the above requirements satisfied by F. Following Lemma we get
that P(QNNE 2 QRCP E') = 1. If E holds with probability 1 - E, where the randomness is taken over Zn+1, then we get:
P((n+1 E SHCP (Xn+1))
2 P(Y.+1 E S (Xar)X)))) ())(E
2 P(Yn+1 E CHOP (Xa+1) ()P(()
= :((Y++ E CREP
(Xa+1)) IP((+ E CACP (o E)P(E)
2 P(Y E COPP
(Xn+1)) -
Similarly, IP(Y+1 Óncc (Xn+1) Zn+1 = 2) 2 P(Y+11 (**(Xn)1) Zn+1 = 2) holds QMEP 2 Q²", which, according to Lemma 1, is equivalent to assuming that one of the following is Satisfied:
17

---

Published as a conference paper at ICLR 2026
1. ke >> kmt? and d < W..1
2. ke < kMCs and
W.
n+1
3. k0? 1902
If the above holds with probability 1-2 E over random draws of Zn-1 = 2 E Z, then by the same reasoning as before, we get a high marginal coverage rate:
IP(Y++1 E CWCCP (Xa+1)) 2 P(Yn+1 E (Xn+(())))
We now present a different stochastic result in which the randomness taken over the randomness in the drawing of all calibration and test data points.
Proposition 2. Suppose that the calibration and test samples given by ((X, Y, 2 Further, suppose that one of the following holds:
IP (KCP kNCP)= 2 1 8 and 0,
1 2. P ( > kww , n+1
2 1 -
3. PP (KCP < kCy 8
Wi+1 a+1
2 & and 6 S 0,
4. P (K k
Then, we get high marginal coverage rate:
P(Y++1 E (Xn+i)) 2 P(Yn+1 E C (Xx+1)) -
Proof. Denote by Eg the following event:
cC KNCP
if 2 0, if 0.
E1
kep
KCC 8
Wh+1 n+1
We denote Eg = h.P
NCF Eg CP
MCP and 8 <
W at1
E == Eg Ez.
By the construction of E and our assumptions, P(E) PiQ QQOOP F) By combining these, we get:
e. Following Lemma get that
P(Yn+1 E SweP (Xn+1)) 2 P(Y,+1 ÓHEP (Xn+1) E)P(E) 2 P(Yn+1 CHOP (Xn+1) E)P(E')
P(Yn+1 CRCP (Xn+1)) PP C C E)P(E)
P(Yn+1 CPCP (Xat1))
Building on our theoretical results for WCP under constant weight error, we now turn PCP applied with constant weight errors and prove Theorem 2.
Proof of Theorem 2. According Feldman & Romano (2024, Theorem 1), get that when applied with the same weights, PCP achieves a higher coverage rate than WCP, that is:
PP(Y++1 SP (Xn+1)) 2 P(Yn+1 S (Xx+1))-
18

---

Published as a conference paper at ICLR 2026
Since the assumptions of Proposition 2 hold, obtain:
P(Y++1 E ÓWICE (X++1)) 2 P(Y++1 C (Xx+1)) - E.
Lastly, under the exchangeability of the samples, Tibshirani et al. (2019, Corollary 1) states that: By combining all, we get:
P(Yn11 E C (X++1)) 2 1-a.
P(Y+11 CR (Xn+1)) 2
A.1.3 GENERAL BOUNDED ERROR
We now turn to consider the setup where the inaccurate weights wū are at bias ó; from the true weights w
vi f1....,,++ 1)
wi ò;.
The errors ó; are assumed to be bounded by 6; E [Omin; m, where Ómn < 6mx E R. Notice that the setting where dmin mmax the case analyzed in Appendix A. We denote the normalized error 5, by: 8, := (6, - Ómin)/ (6max - dmnn) and Åg = Ei= 8g. We also denote å (6max - mmnn). Notice that since Ómax > Ōmin we get Ånt1 < + 1. We follow the notations from A.1.1 and define the following requirements:
1. 8 S Ant W A Aanc Wa+1 Wn-th (1+
Kezs A 11
2. mmin
n+1 Ant1
3. A paa Weme
An Cnsi
We begin with general lemma that provides a deterministic connection between kCP and &.CP, For this purpose, we define
(a XOR b) ((not and b) or (a and (not b)),
(a NXOR b) = (not (a XOR b)).
Lemma 2. Suppose that the calibration set is fixed, and equals to {(X,, Ys, 73) (Ii, Ms. 23) ) for T4 E X, 34 E V,2, Z for all i (1...., n.). Further suppose that the test PI and the errors {5 are also fixed, i.e. Zn+1 2 for some E Z. Then, QUOF 2 Q if and only if one of the following is satisfied:
1. kCP < NCP and (requirement NXOR requirement 2),
2. k0v > wiv and (requirement XOR requirement 2).
3. CC = NCP and (requirement NXOR requirement 3).
Proof. We begin the proof by developing Σ
Eien
KCP
Pi and Σi=1 Ps
W
W ANCP
P4
W W
Wj
APPP
+ 63
WANCr + Apee
1=
wy
-= Wy + +.
W Anti
Observe that:
A
Σ
Pi S Σ
Ps -
2
Quee 2 QMCP.
i=l
19

---

Published as a conference paper at ICLR 2026
We begin by developing requirement 2:
W Wn+1- + An+1 >> 0
Wn+1 + (8mix - ómin) A + (n + 1)0min > 0
Ómax Ân-1- 8min A An+ + (n + 1)0min > - WW++1 n+1
I(+ 1) An+1)mmii 10min
Ómnx An+1 W n+1
6max A An+1 + Wn+1
min
n + An+1
We now turn to requirement I, considering the case where
Wasse Wa+1"
meaning that Q < Quee.
n+1
Here, we have
W.
W W K.CP - (n + 1)W k000
O.
n+I
W
(W poce
W I (Wn+1 + A
W Macr W Wa+1
Wa+1 Wn+I Wanee + An+1 WANEP
Wp
A
n+1
W Wn41
WiReer
(6max - 8min) Appcs + MC? 8min S
[[6max - Smin (min)An11 + (n2 + 1)6min]
W n+11
WER
Å 1000 + RCF
(An+1 + (n+ + 1)8]
Wn+1
W W + W WntIk#CP3
3 < W
We j An+1 + WK (n + 1)5
[Wn+1khee Race
(n 1)W [men]]]
$ A WAner - Apwr Wn+1
Ån+1 Was ② A W n++1
Wa+IhNCP (n + 1)W
We conclude the case
Wawr Wo+1
by observing that
A
WAR + Apcc
W Wo
QACF QHCP
P [=1
W Ar+1
Wn+1
i=1
Notice that, according to the above derivations, the last inequality holds if and only if both requirement 1 and requirement 2 are satisfied, or both requirements are not satisfied. This is equivalent to requirement NXOR requirement
We now consider the case where
W Wame
that is that Q QUOP, Here, ntI
W
n+1
Wa+i
W
Wn+1 (n + g)
< 0. This case is almost identical to the previous one, except for the
following:
Α n+ WANCE ÂANCO Wn+1
(WANER + AgEE) W S (Wa+1 + An-1) gaee
W MOOP - (n + 1)W
Also, according to the same reasoning, we know that:
WANCE + ANRO
W
QUCP QHCP
W An+1
Wh+1
Therefore, QuCE QUCP holds if and only if exactly one of requirement 1 and requirement 2 is satisfied. This is equivalent to requirement XOR requirement
We now turn to analyze the setting where
Aaae n-I
Wowe
Wnt1
(W A
W x+1 < (W + An+1) &
8| h 1900 (n+ 1)W WWWar>
pur>
< Ån+1 Waas ÁP Wn+1
0 < A Wyss A Wnt1 0
A Kones
W n+1
< Ant Wene +
WAND
A n+1
W
20

---

Published as a conference paper at ICLR 2026
Notice that requirement is defined the last inequality. We therefore conclude that QUCP holds and only if requirement NXOR requirement is satisfied.
Q
We now present a stochastic result that states the conditions under which WCP achieves a valid coverage rate when applied with weights that have general error. The randomness is taken over random draws of (Xn+1. Yn+1) from Px,y
Proposition 3. Suppose that the calibration set fixed, and equals to {(xx, Y,, 2,) (It Mss 2 ===1 for some 24 E X, Yi E V,24 Z for all i E {I...., n.. Further suppose that the test PI and the ervors I=1 also fixed, i.e. Zn+1 for some Z. Then, ÓNCe (Xn+1), defined in (11), achieves a conservative coverage rate, i.e,
P(Yn+1 E (ACF((n-1) (Xn-1) Zn+l =2, 22, Yi, Zi) (e: 2 P(Y,+1 E CRCE (Xn-1) Zn+1 = 2, (1x Z.) (2 Mer ==))==))
and only if one of the following is satisfied:
kCe < keee and (requirement NXOR requirement 2)
2. kc >> kuce and (requirement XOR requirement 2)
3. kCp k and (requirement I NXOR requirement 3)
Furthermore, if the above holds with probability at least we get a high marginal coverage rate:
the random draws of Zu+i, then
P(Yn+1 E CCC (Xn+1) {(2,, Y,, Z,) (It, Vis 23) 2)))
2 P(Y,+1 E CCC (X++1) f(X,, Y, 2,) (z,, Vi, 2))
Proof. The proof is identical to the proof of Proposition except for applying Lemma 2 instead of Lemma I and hence omitted.
We now present different stochastic result which the randomness is taken over random splits of the calibration and test samples.
Proposition 4. Suppose that the calibration and test samples are given by {(X,, Y,, Z Further suppose that:
1. IP C < NCY
(requirement NXOR requirement 2)) 2 1
2. IP CP > MCP (requirement 1 XOR requirement 2)) 2 1 -
3. IP (R:CP NCP
(requirement I NXOR requirement 3)))
Then, we get high marginal coverage rate:
P(Y++1 E SNce (Xx+1)) 2 P(Y++1 E MCP (Xn+1))
Proof. The proof is identical to the proof of Proposition 2 except for applying Lemma 2 instead of Lemma I and marginalizing over the randomness of the errors, and hence omitted.
The above theory sets the ground for Theorem 3.
Proof of Theorem 3. The proof is identical to the proof of Theorem 2 except for applying Propo- sition instead of Proposition 2, and marginalizing over the randomness of the errors, and hence omitted.
21

---

Published as a conference paper at ICLR 2026
A.2 UNCERTAIN IMPUTATION
Lemma 3. Denote the prediction interval functtion C(x) = [a(x), b(x)). Suppose that Y follows the model:
== (X, 2) 6,, where E is drawn from a distribution PE. and & 1L X Z. Suppose that
1. There exists a random variable Rles drawn from a distribution PD such that:
(a) [( Z(En) = =0a (Xiem, Zuet) + R
(b) Riest 1L g" (Xtten Zl(srr) Zeen
(c) Riest 1L C(Xten) Zueu.
2. For every
2 and x E X such that fx 2wm (x. 2) the densiry of Yiest X 2, Zust = 2 is peaked inside the interval C(x) -0(())(((x))) b(x)), i.e.
(a) Yu > 0: 2 (b(z) + v) S fy Xwmi (b(x) v), and v) S Xxs 7/ 200= + v).
(b) Yu > 0: X 2=== 2
Suppose that the test Pf is fixed and equals to 7ies for some 2. Denote the imputed test variable:
Yies = g X Z +
where e a random variable drawn from the same distribution as Y - g(Xiest Zient Ziest Then,
P(yle E C(X(ee)) ZIeu = =) Z P(ytest E C(X(er) Zien =2).
Above, the probability is taken over draws of the test variables: (Xiest Zies y glest) Px..Y,, we further assume that Riest 11 Xteu, i.e., Reent a deterministic function of Ziest then oblain coverage equality:
P(Y E C(X(et)) Z 2) = PPY E C(Xie)) Z = 2).
Proof. All formulations in this proof are conducted conditioned on Z 2. For ease of notation, omit this conditioning, yet emphasize that the probabilities are taken over draws conditional on Z = 2. From the definition of e, and under the model Y, there exist (X, Y, D', ~ PX,Y,D,E' such that:
c= Y (77-g(X,22 ((X, (X, + 0(X, g" + - (X, D') =E
We remark that IL X D' 11 X and 11. Yess since these are drawn independently of Xeest Following the assumption on Y, there exists test which satisfies:
rest g" gX
Z + glest
where gle ~ Pg- and glstt 11 Xestt Therefore, the variable Y', formulated as:
Y' : g" (xxtest Z +
is equal in distribution to ylatt that is: y d ylest Furthermore, since glest II. X we also get that:
Y' X yest Xeest
We denote by R the sum of plest and DD:
R Riest D'.
Observe that since Riest d D' we get that R is a symmetric random variable:
P(R < <r
P Rlest
= rr)
D' S
Rlest S r) S
Moreover, the mean of is 0:
E [R = Reee D'
=E( E 0.
22

---

Published as a conference paper at ICLR 2026
Since R. is symmetric random variable with mean O, its median is 0 well. We now develop the imputed value Y
yiess g(X - +e
i(Xieu 7 + D 9" (Xtox 7.oa)) + Reess + D'
Y' + R.
Suppose that (( [a b(x is a prediction interval for Y We now compute the probability P(Ysи < b(X(es))). For ease of notation, we denote b(Xist) by B.
P(yleu I B) P(Y" + R S B)
= P(g"(X 7 + B)
PX Z + glost
+ B)
=P(Y RSR/A B)
P(Y +R B R 0)P 0) + + B ()P(R<< < 0)
= [F + R B
R 0) + PY + R R < 0)
2
=
[P Mest
R B
R 2 0) + P uett R B R 0)
2
1
(P
S B R R 2 + P(Y Test
B +
2 0)
2
1
PP(Yts < B-
R
R
+ P(ytes
< B + R
R R= R=r) (RI
Jr20
We now turn to develop P(y < B - R R = + P(Y < B + R R = r). conditioning on X test being equal to some x E X. Therefore, we can write:
We begin by
(( < - R R = r X = 2) + P(y
<B R= = X,es xx)
= 2P rett B R = Xtest = x)
+ P(Y < B - R R X Xtest x) - P(ytest <B R = r, Xtest =x)
+ P(Y < B + R R = X =x) - -PPY rest
B R = r, Xtest = x)
= 2P((Y < R = r, Xtest = x)
+ +P < test < B R R = r, test x)
PPB R < test < R = r, X 2).
Observe that Yles 11 R since g" (X 2) is independent of Rlest Therefore, can omit the
conditioning on R = r
P(B < test
B + R R = X =x)
you < B R = x x)
P < Yies
< B+r iiest - y test < B X x).
Since the density of lest X is assumed to peak inside the interval, we get:
F(B test B B X =x)
P(B -x)-
5 rist B X =x) $0.
Therefore:
PP test < B 8-R R R = r, x = x) + P(y
< + R R = r, x = x)
< 2P
< R r, x 1 z).
23

---

Published as a conference paper at ICLR 2026
We return to the marginal statement:
P( I B - R R= P(Y SB+ R R= =))
P(Y
B - R
R X = x)
ZEN + P(Y
S + R R = X = x)]fx n2- (2; dx
1 ZEX
12 < B
R = X = =x][/x" (1; r)dx
= 2P
< R R=
We plug this in and get:
P(Y tes
S B3 =
[P lest <B R R =
2 r20
+ P(Yle
< R
R = r)] f fR)R
< 2 Jr20
22
< B R = r)] (rr)][RRze SRIRZo(F)dr
P(Yles B R R20 0)
P(yus B).
The last equality holds since Yiest (Restt D') Zue and C(Xust) JL (Reett D') | Zest The proof
for PYYlest 2 A) < PP A) is similar and hence omitted. By combining these get:
P(y E )( ((a(X S yeuu S b(x()s))
P(ytess S b((( P(P 2 a(X
P(Yies < ((x P(Yieu a(X(os))
P(a(X S yuu )(X((O))
P(Yle C(Xle))).
now consider the setting where Reest 1L X i.e. plest a deterministic function of Z Since we conditioned Z = in this analysis, we get that Iiest = D' are constants. Therefore:
= Y' R Y
Hesst D
Which leads to:
PPYYest ((X(es)) P(Y' C(XIe)) IP C(Xier)
Lemma 4. Suppose that C(x)) is a prediction set satisfying the assumptions of Lemma 3. Denote the imputed variable by:
y ( Ziest) + + Miest 1,
Most = 0,
where is random variable drawn from the distribution of Y yest - Xix 2 Zeest Then, under the assumptions of Lemma and assuming (X Y 11 M Ziest we get:
IPy =((x(en)) 2 P(ytest E C(X
If we further assume that Riest 1L Xlest, i.e., Riest a deterministic function of Ziest then we obtain coverage equality:
Pa C(X"")) = w(Stt C(X"")).
Proof. All formulations in this proof are conducted conditioned on Z 2 unless explicitly stated otherwise. For ease of notation, omit this conditioning, while the probabilities are taken of draws
24

---

Published as a conference paper at ICLR 2026
conditional on Z 2. By applying Lemma 3 and assuming (X y 11 M Z get:
P(Y )( P( E C(Xtst) M 0)P 0)
P(Y E c( M 1)P Mest 1)
P(Y E c( Mu = 0)1((M (M = 0)
+ P(O(X est 2 +E E C(X M 1)I 1)
P(Y E (((X
0)
+ P( ? +6 E (( =1)
I P(Y (C(XES))) P(M = 0)
+ P(Y E C(X P) )(X = 1)
= P(Y test E C(Xter) M = 0) = 0)
+ IP(YIE E ((Xeet) M (MM 1)
= P(( E C(Xte))
We now return to explicitly stating the conditioning on Zest. Thus far, we showed that for every
2 E Z:
P(yles E C(X glest =) S P(Yles E C(Xtes) = 2).
By marginalizing this, we obtain:
PP(y C(x((s)) S P(ytst E C(xtss))
When assuming that Roest 11. X by Lemma we get
P(j(X z + e E C(x((s)) z = 2) = P(Prest E C(xtet) z = 2).
By plugging this expression to the development PP(Ye E ((Xist)) above, we get:
P(P E C(Xte) z = 2) = P(Ptest E ((xtet) ztss== 2). By taking the expectation over Zuett we obtain:
PPSYts C(X(es)) = P( E C(xtst)).
Armed with the above theory, we now prove Theorem 4
Proof of Theorem 4. Denote the imputed variable by:
ytes ( Zlest te, Miss 1.
M 0,
Yresst
Above, e is a random variable drawn from the distribution of Y - g(X, 2) 2 = 2 M = 0.
Since (X, Y) IL M Z, this distribution is equivalent to the distribution of Y 0(x, Z) 1 Zust Since OUT is constructed by CP using the imputed labels, and due to the exchangeability of the data, C covers less the desired coverage rate Vovk et al. (2005); Angelopoulos & Bates (2023):
IP E C"
a.
By applying Lemma 4, and since the samples drawn independently, we get:
P( E CHO (xxeet) I {(X,, Y, Y,, Z,, M)) 2 P(ytes E (Xiee)))) ((X,, Y, Y. Z,, M)))..
By marginalizing the above, we obtain:
P(y E C. (x1est) 2 P(Pros (x 2 a.
25

---

Published as a conference paper at ICLR 2026
A.3 TRIPLY ROBUST CALIBRATION
Building on the validity of UI, we turn to prove the validity of the triply robust method.
Proof of Theorem 5. Under the assumptions of Theorem we get PP C (X under the assumptions of Theorem 4 we get P(Y E C (Xle") ( 2 1 - a. By Vovk et al. (2005); Angelopoulos Bates (2023), CP constructs prediction sets with the nominal coverage level when the scores are exchangeable, i.e., PY E C (Xtet) 2 1 - a. Thus, when at least one of the above assumptions hold, one of the above prediction sets achieves the desired coverage rate. Since Tr trrplyyRose plyyobbust is the union of all three sets, its coverage rate is greater than equal to the coverage rate of each prediction set. Therefore:
a,
P(Y E C'rsplyyobust (xxraaabstttxll) 2
B ADDITIONAL RELATED WORK
Practical examples for tasks with privileged information include crowd-soureing settings, such as CIFAR-10P in which annotator metadata, e.g., response times, confidence scores, and expertise level, may serve as PI. Another example is e-commerce recommendation, where user's click history can be considered as PI, which is good predictor for actual purchases (Yang et al., 2022). In this example, vendors may not share the user's click history with the model provider due to privacy issues, which makes the PI unavailable test time. In medical imaging, a pathologist's diagnostic report for a biopsy image can act as privileged information that strongly predicts whether the tissue is cancerous or healthy (Lopez-Paz et al., 2015). In this context, the Pl may not be available for all patients at test time for various reasons, such as limited resources or prioritization.
Several recent works extend conformal prediction beyond the i.idd. assumption to handle various forms of distribution shifts, including arbitrary shifts (Barber et al., 2023), online and time-series settings (Gibbs & Candes, 2021; Gibbs & Candès, 2024; Zaffran et al., 2022; Feldman et al., 2023; Xu & Xie, 2023), missing covariates (Zaffran et al., 2023; 2024), and ambiguous labels (Stutz et al., 2023; Caprio al., 2024). Related research on missing-data imputation includes analyses of missingness mechanisms (Rubin, 1976). and multiple imputation frameworks (Rubin, 1996; 2018). Furthermore, the work of Zhang (2016) studies regression imputation approaches and discusses adding residual variance to account for prediction uncertainty.
C ALGORITHMS
C.1 PRIVILEGED CONFORMAL PREDICTION
Algorithm 1 given below details the PCP method.
C.2 NAIVE IMPUTATION
natural approach to handle corrupted labels to impute them, using the observed covariates and privileged information. Then, CP can be simply employed using the imputed labels. Formally, we begin similarly to CP and PCP and split the data into two parts: a training set, I,, and a calibration set, Zz. Then, we fit two predictive models to estimate the response using the training data: model fz) which takes an input the feature vector X, and label imputator ğ(z, 2) which takes as an input the feature vector X and the privileged information Z. Next, we impute the corrupted labels in the calibration using the model Ò:
Y2 (0(X, Z,) otherwise
M, = O, Vi IZ
We compute the non-conformity scores using the imputed labels: S, = S(Xi, Vr; A) Vi Iz. The scores threshold is defined using the above scores:
@MaiveImpate = Quantile 1 [- a;
83.
1
800
In
[Z
+
iEI
26

---

Published as a conference paper at ICLR 2026
Algorithm 1: Privileged Conformal Prediction (PCP)
Input:
Data (X,, y, Z₁, M,) X x (0,1),15i n, weights (wi)i=1. miscoverage level
a E (0, 1), level E (0, a:), an algorithm f(z). a score function S, and a test point X 2.
Process:
Randomly split (1..... n into two disjoint sets I,, Fit the base algorithm f on the training data {(,, He),,
Compute the scores S; = (X,, Y; f) for the calibration samples, E Iz.
Compute the normalized weights:
W
kEzy Wk + wi
Compute a threshold Q(Z;) for each calibration sample:
1- 1--a+B B: Σ
Q(Z.) = Quantile
přos, - 0,000
JEZZ
Compute QPCF, the (1 3) quantile of (Q(Zi))iez}
11 33 Σ
QPCP = Quantile
6Q(Z)) +
Ig + 600
I
JEZZ
Output:
Prediction set CPCP (z) {y S(x, v:
PPCP..
Finally, for a new input data Xtest, we construct the prediction set for ylest as follows:
Chliiverppute (X X = {u= S(Xteu .y, < Quaiveimpute
While this approach is simple and intuitive, does not hold any theoretical guarantees. Furthermore, the experiments in Section 4.3 reveal that it consistently undercovers the response. We believe that this is attributed to the fact that the imputed labels are estimates of EE|Y X, 2J. which reduces the uncertainty of the imputed label. This, in turn, leads narrower intervals.
C.3 UNCERTAIN IMPUTATION
The UI algorithm is fully described in Algorithm C.3 below.
C.3.1 ERROR SAMPLING TECHNIQUES
In this section, we present our suggestions for sampling errors conditional on the privileged informa- tion for the imputation process of UI in (7). Instead of using strict equality condition of Z; in {()) == {Eg E Ig, Z 2). we can relax this requirement by clustering the Z space and comparing the clusters into which each falls, that is, {()) == (E, : Is. h(Z,) h(2)), where h is clustering function. The first clustering method we use is Kmeans, which we fit on the training and validation data. Then, we cluster the of the reference set. When imputing the corrupted labels of the calibration set, we sample an error from the cluster corresponding to the test PI. The second clustering approach we examine is L Linear clustering. a linear model that takes as input the PI Z and outputs estimated label Y. We used this model to compute the estimated labels for each point in the reference set and then split them into bins. We note that the alternative approach of learning the error distribution given the PI Z may be applied as well, such as random forest for conditional density estimation (Pospisil & Lee, 2018), or normalizing flows (Rezende & Mohamed, 2015; Papamakarios et al., 2021).
first fit on the training and validation data
27

---

Published as a conference paper at ICLR 2026
Algorithm 2: Uncertain imputation (UI)
Input:
Data (X,, Y, Z₁, M4) E xxxxxxxxxxx (0,1),15 iiisis n, miscoverage level a (0, 1), an
algorithm ((x),, and algorithm j(x, z), a score function S, and test point X 2.
Process:
Randomly split f1..... n into three disjoint sets I2I
Fit the base algorithm on the training data {X,, Y.)
Fit the predictor 9 on the training data {(X,, Zi, Jie,
Compute the errors E, of f on the reference set Za according to (6).
Generate the imputed labels Y, Vi I2, according (7).
Compute the scores S; (X, Y; f) using the imputed labels for the calibration samples,
i I2
Compute Q", the (1 - ox) quantile the scores
Q U1 Quantile
a-a;
Σ
85.
+
1
800
I2
+
[2
+
JEI2
Output:
Prediction set C (I) = (y S(x,,v (( Q
C.4 METHOD VALIDITY CONDITIONS SUMMARY
We summarize the validity conditions of each method in Table 1. This table illustrates that TriplyRobust achieves the desired coverage rate when at least one of the underlying methods is valid.
Table 1: Summary of Method Validity Conditions
Method
Guarantee
Accurate Y X est.
Accurate M Z est.
Accurate Y Z est.
Quantile
(Koenker Bassett,
NA
NA
Regression
1978;
Koenker,
2005;
Steinwart
& Christ-
mann,
2011;
Takeuchi
al.,
2006)
PCP
Theorem
X
UI
Theorem
X
NA
TriplyRcbust Theorem 5
D DATASETS DETAILS
D.1 GENERAL REAL DATASET DETAILS
Table displays the size of each dataset, the feature dimension, and the feature that is used as privileged information in the tabular data experiments.
28

---

Published as a conference paper at ICLR 2026
Table Information about the real data sets.
Dataset
Samples
X/2/Y Dimensions
Z description
facebook1 (facebook)
40948
52/1/1
Number posts comments
facehook2 (facebook)
81311
52/1/1
Number posts comments
Bio (bio)
45730
8/1/1
Fractional area of exposed non polar residue
House (house)
21613
17/1/1
Square footage of the apartments interior living space
Meps19 (meps_19)
15785
138
Overall rating of feelings, age, working limitation
NSLM (Yeager et al., 2019)
10391
10/1/1
Synthetic normally distributed random variahle
D.2 NSLM DATASET DETAILS
The 2018 Atlantic Causal Inference Conference workshop on heterogeneous treatment effects (Car- valho et al., 2019) introduced the National Study of Learning Mindsets (NSLM) dataset (Yeager et al., 2019). We refer to Carvalho al. (2019, Section 2) for its full details. In our experiments, the approach outlined in Carvalho et al. (2019); Lei & Candès (2021) to generate synthetic potential outcomes and synthetic PI variable. The process begins by standardizing the dataset so that all features have mean of O and standard deviation of 1. The data is then randomly split into two subsets: 80% samples are used for training, while the remaining 20% samples are used for validation. To model the relationship between X and Y, we train neural network with single hidden layer containing 32 neurons. The learning mechanism of the network is described in Section E.I. We employ XGBoost classifier to estimate the
adopt
refer its learned function (o(-). Additionally, original treatment variable M using the features in X. The classifier is configured with a maximum depth of 2 and uses 10 estimators. We then calibrate the estimated propensity same marginal probability as the original probability and denote the calibrated score é(X;). Once these models are trained, we generate new treatment indicator M,, synthetic PI variable Zi, and semi-s synthetittttic outcome variable Y; as detailed next:
to have the
Z; ~ 0.0.0.22)
E, 1[2; 2 Quantile(O.9, Z) or Z, S Quantile (0.1, Z)} M, (er(min(0.8, (1 +1+ E,)((X,)))
т: = 0.228 0.051 (X,,s < 0.07) - (0.01[[X,, < -0.69) 0.081 (Xt, E (1, 14))
Y, Ao(X,) + + (1 + E,)
D.3 SYNTHETIC DATASET DETAILS
In this section, we present the synthetic datasets used in this work. Across all datasets, X, Y, generated using the same procedure from Feldman & Romano (2024), where the only difference is the label corruption mechanism. We first describe the generation process for X, Y. Z and then detail the corruption mechanisms.
The feature vectors are uniformly sampled as follows:
X; Uni(1,5)
where Uni(a, b) is a unifrom distribution in the range (a, b). The p = 3 dimensional PI Zij, for each dimension j E 31 sampled as:
Eig ~ 1),,1),
F Uni(-1,11
E N(0,
P.j ~ Pois(cos(E))) + 0.1) x E,,
Zi ~ P; + 2E
29

---

Published as a conference paper at ICLR 2026
Above, Pois(A) is poisson distribution with parameter X, and W(,, σ²) is normal distribution with mean and variance o². We define some additional variables:
31 Uni(0, 1)
31 = B1 /11
32 Uni(0, 1)P
32 B2/11/2111
Z'; = 82Z;
U, 12 +0r-<=++22 2==1=3231 +8* 121
E, ~ 1(0.1)
Finally, the label is defined as:
Y; = 0 U,E,
Turning to the corruption mechanism, for the dataset in which Naive CP achieves under-coverage. the corruption probability is defined detailed in Appendix E.I. In the alternative dataset, in which Naive CP overcovers the response, the corruption probability is formulated as follows. For each sample, we subtract from Z the minimal value between the 5% quantile and 0. Then, divide by the 95% quantile of these values and multiply by 2.5. Next, we zero out all negative values. After that, we raise by the power of the negative of these values and take minus this result. Lastly, we zero out all negative values and those that are greater than the 30% quantile. To obtain the corruption probabilities, we normalize these values between 0.2 and 0.9 and raise them the power that leads to 20% marginal corruption probability.
In Section 4.2 we employed a different corruption mechanism in which the weights are hard to estimate from Z. We begin by computing complex function of Z:
1/3
arctan (0.3 (0.3/6sin2(z))
cos 2z:))
0.Stanh
+.5 + sin (1//)) cos (2///8)
T :=
0.5g (2) 0.5
The rest of the process is similar to our default mechanism in Appendix E.I, except for zeroing all values for the samples with T; < 1.2 in addition to zeroing all negative values. Furthermore, instead of zeroing values that are lower than the 30% quantile, we zero the values that are lower than the 50% quantile. By incorporating T,, which is complicated function of Z, we turn the estimation process of M to be more challenging, which leads to inaccurate estimates of the weights.
E EXPERIMENTAL SETUP
E. GENERAL SETUP
Across all experiments, the data is divided into a training set (50%), calibration set (20%), validation set (10%) used for early stopping, and a test set (20%) for performance evaluation. For further split the original calibration set equally into reference set (50%) and
the UI method, a calibration set (50%). Next, we normalize the feature vectors and response variables so that they have a mean and unit variance. In experiments with missing variables, a linear model that is fitted on the variables that are always observed, out of X, Y, Z. This linear model trained using samples from both the training and validation sets. For datasets that are not originally corrupted, the corruption probability is defined as follows. First, for the MEPS19 dataset, we fit a random forest model on the entire dataset to predict the 70% and 30% quantiles of Y given Z, and we use their difference as the initial value. For the other datasets, we take Z as the initial value; if Z is multi-dimennional,, we multiply it by a random vector to convert into a scalar. We start by subtracting the minimum value between the 5% quantile and 0, then divide by the 95% quantile of these values, and multiply by 2.5. Negative values are then set to zero. Next, we raise to the power of the negative of these values and subtract the result from 1. Finally, we out any negative values and those below the 77% quantile. To obtain the corruption probabilities, these values normalized lie between 0.2 and 0.9 and then raised to power that results in 20%
impute them using
30

---

Published as a conference paper at ICLR 2026
marginal corruption probability. Thus, by definition, the average corruption probability is 20%. In every experiment, we train a base learning model and then wrap it with a calibration scheme. The learning model is designed to estimate the 5% and 95% conditional quantiles of Y X. In Table 3, we summarize the models employed for each dataset across both tasks. For neural network models, an Adam optimizer (Kingma & Ba, 2015) with learning rate of 1e-4 and a batch size of 128. The network architecture contains hidden layers with sizes 32, 64, 64, 32, with a dropout rate of 0.1, and uses leaky ReLU as the activation function. We used 100 estimators for both xgboost and random forest models. The networks are trained for 1000 epochs; however, training stops early if the validation loss does not improve for 200 epochs, at which point the model with the lowest validation loss is selected. We used the scikit-learn package (Pedregosa et al., 201 1) to construct random forest models and the xgboost package (Pedregosa et al., 2011). 1). The neural networks are implemented using the PyTorch package (Paszke et al., 2019). The hyperparameters we employed are the default ones unless stated otherwise. For PCP, we set the parameter 3 to 3 = 0.005. In all experiments in which we employed UI, unless specified otherwise, we used Full + Linnarr model for the label regression model ((x, ), in which a linear model is given both Z and the output of a neural network model trained using X, Z. Moreover, the conditional errors were sampled using the linear clustering approach described in Section C.3.1 When applying Kmeans clustering, we use the default number of clusters = 8.
Table 3: The learning models used for each dataset.
Dataset
Base learning model
Corruption probability estimator
Facebook1 (facebook)
Neural network
Neural network
Facebook2 (lacebook)
Neural network
Neural network
Bio (bio)
Neural network
Neural network
House (house)
Neural network
Neural network
Meps19 (meps_ 19)
Random forest
Random forest
NSLM (Yeager et al., 2019)
XGBoost
XGBoost
Synthetic datasets (Feldman Romano, 2024)
Neural network
Neural network
E.2 INACCURATE WEIGHTS STUDY
We generated 30000 samples from the synthetic datasets in Appendix D.3. As described in Appendix E, we split each dataset into training, validation, calibration, and test sets. We ap- plied the error to the weights according to the setup and employed each method using the in- accurate weights. For the varying error setup, the errors were sampled independently of the data. The performance
computed for 30 random splits of the data in the constant er- ror setup. For the varying error setup, we fix the training and calibration set and fix Xiest to X = (2.6752, 1. 1.2141, 2.0997, 4.4819. 3.9244, 4. 10668 4.9509, 1.9368, 4.8397, 1.6686) and Zrest to Zrest = - (-2.3365 3.4784, 1.3291), and generate 100K random response values yess conditional on these values. The values we fixed for X Zieu were drawn from their marginal distribution. Since the calibration data, as well as X Xuest Zuest are fixed, the validity regions are deterministic and therefore can be computed accurately. The validity intervals of the varying errors setup are computed
according to Theorem 3 as follows:
Smna A.ti + W.
8min
n n+ 1 An+1
8 = 8min (3 (1)))
Above, 8 is set to
An+1 W Wencr - Å pncce Wn+1
W W kWCP (n + 1)Wasce
Theorem 3 states that PCP applied with any values of smin: Smax in this interval range is guaranteed to achieve valid coverage rate.
31

---

Published as a conference paper at ICLR 2026
E.3 MACHINE'S SPEC
The resources used for the experiments are:
CPU: Intel(R) Xeon(R) CPU E5-2683 v4 @ 2. 2.10GHz, Intel(R) Xcon(R) Gold 5318Y CPU @ 2. 2.10GHz, Intel(R) Xeon(R) Gold 6336Y CPU @ 2.40GHz..
GPU: NVIDIA A40, NVIDIA TITAN X (Pascal), NVIDIA 2080 TI, NVIDIA RTX 2060 SUPER.
OS: Ubuntu 20.04.6.
Experiments typically take at most 10 minutes to run, though actual times may vary with workload.
F ADDITIONAL EXPERIMENTS
F.1 WCP WITH INACCURATE WEIGHTS
We study the coverage rate attained by WCP when applied with various distributions of weight errors. We employ WCP on the two synthetic datasets described in Appendix D.3. the first dataset, Naive CP achieves over-coverage, and in the second one, Naive CP undercovers the response. In Figure and Figure we display the validity regions of WCP with various distributions for the error of the weights. These figures show that the validity regions depend the distribution of the error. Furthermore, is indicated by the figures that the validity region is small interval when Na i ve CP undercovers the response while when it overcovers, the validity region spans through the entire space except for one interval.
F.2 PCP WITH INACCURATE WEIGHTS
In this section, analyze the coverage rate of PCP when applied with various distributions of weight errors. We study the performance using the two synthetic datasets described in Appendix D.3. In the first dataset, Naive CP achieves over-coverage, and in the second one, Naive undercovers the response. Figure 9 and Figure 10 show the validity regions of PCP with various distributions for the error of the weights. These figures show the effect as observed in Appendix F.1.
F.3 CAUSAL INFERENCE EXPERIMENT: NSLM DATASET
In this causal inference example, our goal is to estimate the uncertainty of individual treatment effects (Hernán & Robins, 2010). We utilize the semi-synthetic National Study of Learning Mindsets (NSLM) dataset (Yeager et al., 2019), which deals with behavioral interventions. Further details about the dataset can be found in Carvalho al. (2019, Section 2), and Appendix D.2 outlines our adaptation for this dataset. Here, X; are the individual's characteristics, Z; are the privileged information, M, E {0, 1} denotes the binary treatment indicator, and (0), (1))) E R denote the counterfactual outcomes under control and treatment conditions, respectively. In practice, we only observe one of them, Y. which equals to (0) if M, = 0 and to YI(1) if M, = 1. In this task, our goal is to estimate the uncertainty of the unknown response under no treatment Y₂+1 = (0) at pre-specified level 1
90%. As explained in Feldman & Romano (2024), estimating uncertainty for ((()) is crucial since it can be used to construct a reliable prediction interval for the individual treatment effect (ITE), (1) Y0), which is of great interest in many causal inference applications (Brand & Xie, 2010; Morgan, 2001; Xie et al., 2012: 2: Florens et al., 2008). Furthermore, Feldman & Romano (2024) emphasizes that constructing valid prediction sets for (0) is challenging due to the distribution shift berween the observed control responses, which are drawn from (Y In contrast, the test control response is drawn from (o Moreover, Feldman & Romano (2024) highlight the diffieulty of constructing valid prediction sets for (0), it requires correcting the distribution shift between the observed control responses, which follow the distribution (y M== and the test control responses, which are drawn from Py
We display the performance of each calibration scheme in Figure 11. This figure indicates that Na i ve CP and Na ve Imputation fail to achieve the nominal 1 90% coverage rate. In
32

---

Published as a conference paper at ICLR 2026
Error distribution
Naive CP overcovers
Naive CP undercovers
Uniform
1.0
Uniform distr.
Uniform distr.
10
2.5
Density
Öman
0.5
0.0
-2.5
-10
0.0
-25
0.0
2.5
10
10
8
Omin
8min
Right sided
1.0
Right sided distr.
Right sided distr.
10
2.5
Density
0.5
Ó
Ómax
0.0
-2.5
-10
0.0
0
2.5
0.0
2.5
-10
10
6
6min
Omin
Left sided
1.0
Left sided distr.
Left sided distr.
10
2.5
Density
Ōmax
0.5
0.0
-2.5
-10
0.0
0
2.5
0.0
2.5
-10
10
5
Omin
Omin
Small tails
1.0
Small tails distr.
Small tails distr.
10
Density
2.5
0.5
iunx
Omax
0.0
-2.5
-10
0.0
-25
0.0
2.5
10
10
8
8min
8
Extreme tails
1.0
Extreme tails distr.
Extreme tails distr.
10
2.5
Density
0.5
Omxx
0.0
-2.5
-10
0.0
0
2.5 6min
0.0
2.5
10
10
5
8min
Figure 6: The validity regions of WCP applied with inaccurate weights along with the theoretical bounds from Theorem 3 displayed in dashed line. Here, the coverage rate is computed over random draws of 100K test responses test conditionally on the calibration set, Xeest and Ztest Green: valid coverage, i.c., greater than the coverage rate WCP with weights; Orange: invalid coverage. Left: Distribution of the error. Mid: Naive CP achieves over-coverage. Right: Naive CP achieves under-coverage.
33

---

Published as a conference paper at ICLR 2026
Error distribution
Naive CP overcovers
Naive undercovers
Beta U
1.0
distr.
distr.
10
2.5
Density
0.5
Ómax
Ómax
0.0
-2.5
-10
0.0
0
-2.
0.0
2.5
10
10
5
Omin
8 8
1.0
Beta right
Right beta distr.
Right beta distr.
10
Density
2.5
0.5
òmex
Omax
0.0
-2.5
-10
0.0
0
1
2.5
0.0
2.5
-10
10
8
Ópin
Beta left
1.0
Left beta distr.
Left beta distr.
Density
2.5
0.5
Ōmaxe
8mas
0.0
-2.5
-10
0.0
-2.
0.0
2.5
-10
5
Ómin
8min
Beta right hill
Right hill distr.
Right hill distr.
10
Density
2.5
0.5
Ōmax
8max
0.0
-2.5
-10
0.0
225
0.0
2.5
10
10
8
8min
8min
1.0
Beta left hill
Left hill distr.
Left hill distr.
10
Density
2.5
0.5
Ömas
8max
0.0
-2.5
-10
0.0
-1
0 8
2.5
0.0 8pin
2.5
10
10
8
Figure 7: The validity regions of WCP applied with inaccurate weights along with the theoretical bounds from Theorem 3 displayed in dashed line. Here, the coverage rate is computed over random draws of 100K test responses ylest conditionally on the calibration set, X and Z Green: valid coverage, i.e., greater than the coverage rate of RCP with true weights; Orange: invalid coverage. Left: Distribution the error. Mid: Naive CP achieves over-coverage. Right: Naive CP achieves under-coverage.
34

---

Published as a conference paper at ICLR 2026
Uniform distr.
Right sided distr.
Uniform distr.
Right sided distr.
2.5
2.5
Onnx
Omax
0,0
0.0
-10
10
-2.5
-2.
10
0 min
10
10
10
-25
0.0 Omin
2.5
-2.5
0.0
2.5
Omin
Onin
Figure 8: The validity regions of PCP applied with inaccurate weights along with the theoretical bounds from Theorem 3 displayed in dashed line. Here, the coverage rate is computed over random draws of ylex conditionally on the calibration set, Xlest and Zues, Green: valid coverage region, i... greater than the coverage rate of WCP with true weights; Orange: invalid coverage region. Left: Naive CP under-covers the response. Right: Naive CP achieves over-coverage.
contrast, PCP attains a valid coverage rate, despite being employed with estimated weights. Moreover, our proposed UI constructs valid uncertainty sets as well, as guaranteed by our theory.
F.4 IMPUTATION AND ERROR SAMPLING METHODS
We study the impact of the label regression model I of UI and the effect of the error sampling mechanisms from Appendix C.3.1 on the validity of the constructed prediction sets. For this purpose, we follow the setup detailed in Section 4 and use the same real datasets in missing response setting. We apply UI with the following label regression models, aiming to achieve 90% coverage rate:
Linear: where ğ is linear function of both and Z, implemented using Scikit-learn's LinearRegressor (Pedregosa al., 2011) 1);
Full: 1: neural network that takes X and Z as inputs;
Full 1 +I.i Hear: a combined method in which a linear model is given both Z and the output of the pre-trained Full model.
Figure 12 presents the performance of UI with the Linear model, showing that UI tends to overcover the response. This can be explained by the large estimation errors of the linear model, caused by its limited expressive power, leading to increased uncertainty in the imputed samples. This high uncertainty drives UI to construct large uncertainty sets.
In contrast, shown in Figure 13, the Full model achieves a coverage rate that is closer to the nominal level when applied with linear or K-means clustering error sampling. However, the marginal emor sampling approach, which does not condition Z, leads undercoverage. This highlights the importance of sampling errors conditionally on Z to obtain valid prediction sets.
Finally, Figure 14 illustrates that the Pull+Linear model tends to attain the target coverage when the linear or K-means clustering error sampling techniques are applied. Once again, the marginal error sampling strategy results in undercoverage, emphasizing that conditioning the error sampling on the privileged information is necessary to construct reliable uncertainty sets.
To conclude, these experiments demonstrate the importance of both accurate label regression model Ò and a conditional error sampling mechanism to construct prediction sets that are valid in the missing response setup.
F.5 EMPIRICALLY EVALUATING THE ASSUMPTIONS OF THEOREM
In this section, assess whether the assumptions of Theorem 4 are satisfied in practice, by conduct- ing two experiments following the protocol in Section 4.3.
In the first experiment, we evaluate the dependence between residual errors y X Ziest) and (i) the predictions "eetsst Zrest,, (ii) the lower bounds (Xtee), and (iii) the upper bounds C¹ (Xred) of the intervals produced by UI. We assess the dependence by computing the partial correlation (PC) conditional test between the terms. We emphasize that residual errors were used in place of Rlest because the latter is unavailable in practice. Likewise, since the true function g is unknown,
35

---

Published as a conference paper at ICLR 2026
Error distribution
Naive CP overcovers
Naive CP undercovers
Uniform
1.0
Uniform distr.
Uniform distr.
10
2.5
Density
Öman
0.5
0.0
-2.5
-10
0.0
-25
0.0
2.5
10
10
8
Omin
8min
Right sided
1.0
Right sided distr.
Right sided distr.
10
2.5
Density
0.5
Ó
Ómax
0.0
-2.5
-10
0.0
0
2.5
0.0
2.5
-10
10
6
6min
Omin
Left sided
1.0
Left sided distr.
Left sided distr.
10
2.5
Density
Ōmax
0.5
0.0
-2.5
-10
0.0
0
2.5
0.0
2.5
-10
10
5
Omin
Omin
Small tails
1.0
Small tails distr.
Small tails distr.
10
2.5
Density
0.5
iunx
Omax
0.0
-2.5
-10
0.0
-25
0.0
2.5
10
10
8
8min
8
Extreme tails
1.0
Extreme tails distr.
Extreme tails distr.
10
2.5
Density
0.5
Omxx
0.0
-2.5
-10
0.0
0
2.5
0.0 6min
2.5
10
10
5
8min
Figure 9: The validity regions of PCP applied with inaccurate weights along with the theoretical bounds from Theorem 3 displayed in dashed line. Here, the coverage rate is computed over random draws of 100K test responses test conditionally on the calibration set, Xees and Ztest Green: valid coverage, i.c., greater than the coverage rate of PCP with weights; Orange: invalid coverage. Left: Distribution of the error. Mid: Naive CP achieves over-coverage. Right: Naive CP achieves under-coverage.
36

---

Published as a conference paper at ICLR 2026
Error distribution
Naive CP overcovers
Naive undercovers
Beta U
1.0
distr.
distr.
10
2.5
Density
0.5
Ómax
Ómax
0.0
-2.5
-10
0.0
0
-2.
0.0
2.5
10
10
5
Omin
8 8
1.0
Beta right
Right beta distr.
Right beta distr.
10
Density
2.5
0.5
òmex
Omax
0.0
-2.5
-10
0.0
0
1
2.5
0.0
2.5
-10
10
8
Ópin
Beta left
1.0
Left beta distr.
Left beta distr.
Density
2.5
0.5
Ōmaxe
8mas
0.0
-2.5
-10
0.0
-2.
0.0
2.5
-10
5
Ómin
8min
Beta right hill
Right hill distr.
Right hill distr.
10
Density
2.5
0.5
Ōmax
8max
0.0
-2.5
-10
0.0
225
0.0
2.5
10
10
8
8min
8min
1.0
Beta left hill
Left hill distr.
Left hill distr.
10
Density
2.5
0.5
Ömas
8max
0.0
-2.5
-10
0.0
-1
0 8
2.5
0.0 8pin
2.5
10
10
8
Figure 10: The validity regions of applied with inaccurate weights along with the theoretical bounds from Theorem 3 displayed in dashed line. Here, the coverage rate is computed over random draws of 100K test responses ylest conditionally on the calibration set, X and Z Green: valid coverage, i.e., greater than the coverage rate of PCP with true weights; Orange: invalid coverage. Left: Distribution the error. Mid: Naive CP achieves over-coverage. Right: Naive CP achieves under-coverage.
37

---

Published as a conference paper at ICLR 2026
Iinerval langth
Coverage
85
Noive CP
Notee Imp.
wiigtt)
Uncertain Imp.
Natee
Nave
PCP wegges) Uncortain Imp.
Method
Figure 11: NSLM dataset experiment. The coverage rate and average interval length achieved by naive conformal prediction (Naive CP), conformal prediction with naive imputations Naive Imputation atiin, in, PCP which estimates the corruption probability from Z, and the proposed method (UI). All methods applied to attain coverage rate at level evaluated over random data splits.
90%. The metrics
97.5
Error
95.0
Marginal
Coverage
92.5
Kmeans
Linear
90.0
87.5
facebook1
facebook2
bio
house
meps19
nslm
Dataset
Interval length
3
2
facebook1
facebook2
bio
house
meps19
nslm
Dataset
Figure 12: Linear regression model. The coverage rate and average interval length obtained by UI with various error sampling methods. Performance metrics are evaluated over 30 random data splits.
we replaced it with its estimator g. These replacements serve as fair alternatives for the unknown variables. For completeness, we also report the coverage rate attained by and the prediction error (MSE) of g. All metrics were computed on the test set, and the results are averaged over 10 random data splits. The empirical results, summarized Table 4, reveal that there non-negligible partial comelation between the interval endpoints and the residual errors. This suggests that the independence requirements of Thcorem are not exactly satisfied. Nevertheless, the intervals of UI still achieve the nominal coverage rate. This observation reveals the robustness of the UI procedure: even when the theoretical conditions are only approximately satisfied, still constructs valid intervals.
Table 4: Metrics assessing the assumptions of Theorem
Dataset
Coverage
9 MSE
PC
C PC
C PC
Bio
90.72 + 0.49
0.56 + 0.00
-0.02 + 0.00
0.03 + 0.00
-0.02 +: 0.00
Facebook]
90.96 + 0.36
1.84 + 0.21
-0.07
+ 0.05
-0.02 + 0.04
-0.03 0.05
House
91.23 + 0.36
0.71 + 0.03
0.15 + 0.01
0.18 + 0.01
0.19 + 0.01
In the second experiment, we analyze the setup where the PI is weak predictor of Y. We follow the same experimental protocol in Section 4.3 and simulate this setup by adding random Gaussian noise
38

---

Published as a conference paper at ICLR 2026
95
Error
Marginal
Coverage
100
Kmeans
Linear
85
facebook1
facebook2
bio
house
meps19
nslm
Dataset
Interval length
2
facebook1
facebook2
bio
house
meps19
nslm
Dataset
Figure 13: Full regression model. The coverage rate and average interval length obtained by with various error sampling methods. Performance metrics are evaluated over 30 random data splits.
Z, with varying standard deviations. Figure 15 summarizes the performance of UI with these weak PIs, indicating that as the magnitude of the noise increases, the coverage rate of UI increases. That is, as the PI becomes a weak predictor of the labels, the uncertainty the imputed labels increases, which, in turn, widens the resulting prediction sets. This experiment suggests that UT still obtain a valid coverage rate even when the is weak predictor of the labels.
F.6 THE PERFORMANCE OF TRIPLYROBUST
We employ Triply Roobuus,,, which combines CP, PCP that uses either the estimated corruption probabilities or the true ones, and UI on the datasets from Section 4.3. We present the coverage rate and interval length in Figure 16. This figure shows that Triply pripplyRobust. employed with PCF that uses estimated weights constructs wider intervals, which is in line with the results in Section 4.3, which this version PCP constructs wider intervals, as its approximations are not sufficiently accurate. Nevertheless, this figure reveals that combining the three approaches does not significantly harm the statistical efficiency of the predicted intervals, especially when using oracle or sufficiently accurate weights.
39

---

Published as a conference paper at ICLR 2026
95
Error
Marginal
Coverage
90
Kmeans
Linear
85
facebook1
facebook2
house
meps19
nslm
Dataset
Interval length
2
facebook1
facebook2
bio
house
meps19
nslm
Dataset
Figure 14: Full+Linear regression model. The coverage and average interval length obtained by UT with various error sampling methods. Performance metrics are evaluated over 30 random data splits.
40

---

Published as a conference paper at ICLR 2026
house dataset
Coverage
92.5
90.0
0.1
2.5
5
10
50
100
500
1000
5000
Noise s.t.d
facebook 1 dataset
Coverage
95
90
0.1
2.5
5
10
50
100
500
1000
5000
Noise s.t.d
bio dataset
Coverage
93
92
91
0.1
2.5
5
10
50
100
500
1000
5000
Noise s.t.d
Figure 15: Weak PI experiment. The coverage rate a function of the noise of the PI. The coverage rate is evaluated over 4 random data splits.
41

---

Published as a conference paper at ICLR 2026
Method
Coverage
96
Triply Robust (PCP est. weights)
Triply Robust (PCP oracle weights)
90
facebook1
facebook2
bio Dataset
house
meps19
Interval length
1.5
1.0
facebook1
facebook2
house
meps19
Dataset
Figure 16: Missing response experiment. The coverage rate and average interval length obtained by TriplyRobusts employed with PCP that uses either the estimated corruption probabilities or the true ones. Performance metrics are evaluated over 30 random data splits.
42


Reviews:
[{"review_id": "wil6tIX2Zz", "reviewer": "Reviewer_7Q63", "summary": "In this paper, the authors investigate how to construct prediction sets with$1-\\alpha$coverage for the test points, using datasets with corrupted labels. While the existing PCP method relies on a distribution shift$w(z)$to achieve the target coverage, its practical application is limited when $w(z)$ is not precisely known. To bridge this gap, the authors first analyze the theoretical behavior of PCP under scenarios where the shift$w(z)$deviates from the true value. Furthermore, they introduce a new approach called UI, which imputes corrupted labels and directly constructs valid prediction sets without requiring explicit knowledge of the distribution shift. Finally, the authors present extensive experimental results, demonstrating that the UI method achieves shorter prediction sets while maintaining the desired coverage guarantee.", "questions": "1. Theorem 4 requires that \"the residual errors are independent of the prediction of $g^{*}$and of $C^{UI}$ given the PI$Z$\". However, under what specific settings can this condition be reasonably expected to hold? \n2. When dealing with a practical problem, what specific characteristics should one consider to determine which method is more suitable? For instance, would the UI method outperform the PCP method when $Z$ is highly correlated with $Y$?\n3. In line 318, is the residual $E_i$ computed solely for the uncorrupted samples, or for all samples in the reference set? If it's computed for all samples, the true $Y_i$ for the corrupted samples is unobservable. The notation here appears ambiguous.\n4. In lines 343 and 344, regarding the condition for the peak of the conditional distribution within the interval $[a(x), b(x)]$, would the symbol \"$\\geq$\" be more appropriately replaced by \"$\\leq$\"?\n5. In the experimental section, would the prediction interval lengths produced by the TriplyRobust method be significantly longer than those of the other methods?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "First, the authors investigate the theoretical properties of the PCP method when the distribution shift$w(z)$deviates from the true value, thereby enriching the existing theoretical results. Second, the authors propose a novel UI method. By incorporating the idea of imputation, this method constructs reliable and effective prediction sets for test points without requiring the shift$w(z)$. The paper is clearly written and provides a new solution for constructing prediction sets using datasets with corrupted labels, thereby extending the existing body of work.", "weaknesses": "The paper could be strengthened by a more thorough discussion of the proposed UI method. For instance, Theorem 4 assumes that \"the residual errors are independent of the predictions of $g^{*}$ and of$C^{UI}$given the PI $Z$.\" It would be important to clarify the practical scenarios in which this condition can be reasonably expected to hold. Furthermore, there is no clear evidence that the UI method consistently outperforms the PCP method. When facing a practical problem, what characteristics should one consider to determine which method is more appropriate? Finally, the experimental section would benefit from including the prediction set lengths of the TriplyRobust method for a complete performance assessment, and some notations could be revised for better clarity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JQeoSeUiWG", "reviewer": "Reviewer_Ypqe", "summary": "This paper analyzes the robustness of existing weighted and privileged conformal prediction methods under inaccurate weight estimation and introduces a new Uncertain Imputation approach for corrupted labels.", "questions": "1- While the paper provides solid theoretical analysis, it would strengthen the work if the authors could elaborate on the computational overhead of combining PCP, UI, and CP in the Triply Robust scheme\n\n2-  The assumptions underlying Theorem 4,may not hold in many practical scenarios. It would be valuable for the authors to discuss how realistic these assumptions are and whether the proposed method remains approximately valid when they are violated.\n\n3- It would be helpful if the authors clarified what predictive models were used in their experiments\n\n4- Can the authors comment on whether their theoretical results extend to more general or data-dependent weight estimation errors, beyond the fixed bias or bounded error settings analyzed in Theorems 2 and 3?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1- The paper presents a solid and technically sound theoretical analysis of conformal prediction methods under label corruption, with clear insights into how PCP and WCP behave when weight estimates are inaccurate.\n\n2- The manuscript is clearly written, logically structured, and easy to follow despite the technical content.", "weaknesses": "Please check questions!", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hTJjkvf6FF", "reviewer": "Reviewer_wCwu", "summary": "The paper addresses the label corruption in conformal prediction. While conformal prediction assumes exchangeability between the calibration points and the test point, if a subset of calibration points have corrupted labels (specifically if the corruption is non-random or dependent to a feature) then the exchangeability breaks. The paper is focused in the case that there is a privileged information either indicating the faulty label or carrying information about the true label. \n\nFor the case where the information indicates the corruption label, one existing approach - a.k.a. PCP - is to treat each calibration point as a test point and calibrate on the rest of non-corrupted points. With those scores we can find a threshold for the left out calibration point. Then the conformal threshold will be the 1 - beta quantile of those threshold. For this case the authors evaluate the robustness of PCP under various noise in the weights of the weighted conformal prediction. They further characterize under which cases does the PCP sets violate the coverage guarantee.\n\nAdditionally they also propose a label imputation setup by splitting the calibration and adding the label-estimation error to the labels.", "questions": "1. I can not understand the PCP setup. What is the Q(Z_i)? Do you compute WCP with 1 - alpha threshold for it? Does your theorem 1 hold for any values of beta?\n2. Are you sure about line 190? Shouldn’t it be the training and calibration distribution?\n3. I am not sure about it, but seems that the theorems in Section 3 are relying on the conditional assessment of error. If so, is this possible in real datasets? Because this means that you are intuitively assuming that you already have access to the clean label that you can estimate its corruption.\n4. Is the entire requirement in Theorem 4 for the noise of the classifier to be independent from X conditional to Z? Does any classifier work? Is this even possible to be independent to X conditional to Z?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem is applicable in many cases when there is any type of label noise. \n2. The authors approached the problem in an organized way. They clearly break down the cases where the labels are faulty, and address each case separately.\n3. The theoretical contribution of the paper is considerable. \n\nIn total while the problem is not clearly defined and solved I think the contribution in theory is above the standard for acceptance.", "weaknesses": "1. In general I could not connect the theorems in Section 3.1 to derive a robustness guarantee and a well delivered understanding of what the procedure is and what the guarantee would be. This is a shortcoming in the application as it is not clear what assumption holds.\n2. Minor writing points: Line 176 the term indicator is used twice, maybe you can drop the second one. \n3. Why the authors even discuss the setup with the constant noise on the weights? Isn’t it too unrealistic?\n4. The definition of sufficiently accurate does not conform with the term used. Here the only requirement for the error is to be independent from conditional to Z.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5kpGD3FeJ1", "reviewer": "Reviewer_9dC5", "summary": "This paper addresses the challenge of preserving the validity guarantees of Conformal Prediction (CP) when training and test data are non-exchangeable due to label corruption or missing information. The authors propose three complementary approaches to restore reliable coverage: Privileged Conformal Prediction (PCP), which reweights calibration samples using privileged information to correct for corrupted labels; Uncertain Imputation (UI), which imputes missing or noisy labels while injecting uncertainty to prevent overconfident intervals; and a Triply Robust CP method that ensures valid coverage if any of these assumptions hold. The paper provides theoretical proofs of coverage guarantees under each setting and supports them with synthetic and real-world experiments. Overall, it extends CP to corrupted-label scenarios and offers a practical framework for robust uncertainty quantification beyond the standard exchangeability assumption.", "questions": "Exchangeability vs. i.i.d.: Please clarify the precise assumption used in your theoretical results. Some parts (e.g., the abstract) seem to equate exchangeability with i.i.d., though the former is weaker.\n\nAssumption robustness:\nHow sensitive are PCP and UI to violations of their key assumptions? A short sensitivity or ablation analysis would clarify how performance degrades when these assumptions fail.\n\nImplementation details:\nProvide more detail on how the weighting function ($w(Z)$) and residual noise in UI are estimated in practice, particularly in high-dimensional settings, to improve reproducibility.\n\nEvaluation metrics:\nConsider adding calibration error or conditional coverage metrics to complement coverage and interval width, giving a fuller view of empirical performance.\n\nRelationship to Literature: How do the authors' findings compare with the existing literature for CP with ambiguous ground truth in the calibration data, that is https://openreview.net/forum?id=L7sQ8CW2FY and https://proceedings.neurips.cc/paper_files/paper/2024/hash/d42a8bf2f40555d4a5120300f98c88f6-Abstract-Conference.html ?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Conformal Prediction (CP) to data settings with label corruption and non-exchangeability. It also explores solutions for cases where the fundamental exchangeability assumption of traditional CP is violated. This is a problem that has received little attention in previous research.\n\n\nThe proposed combination of Privileged Conformal Prediction (PCP), Uncertain Imputation (UI), and Triply Robust CP creatively integrates ideas from conformal prediction, causal inference, and robust statistics, building a novel framework for uncertainty quantification under data corruption.\n\n\nIn terms of research quality, the theoretical analysis in the paper is rigorous, the assumptions are clearly stated, and precise coverage guarantees are provided under different robustness conditions. In terms of clarity, the paper is well-structured, with clear motivation and consistent notation. Although the technical content is deep, the core ideas are clearly expressed and easy to understand.", "weaknesses": "First, the distinction between exchangeability and i.i.d. should be made explicit early in the paper, particularly in the abstract. Currently, the text occasionally treats these terms as interchangeable, but this is conceptually inaccurate: exchangeability is a strictly weaker assumption than i.i.d., and making this distinction clear would improve both theoretical rigor and readability.\n\nSecond, the robustness assumptions underlying each proposed method (e.g., $((X,Y)\\perp M|Z$) for PCP and accurate conditional modeling $(Y|Z)$ for UI) are relatively strong and may not hold in many real-world corruption processes. A more detailed discussion or empirical sensitivity analysis would help clarify how performance degrades when these assumptions are violated.\n\nThird, while the theoretical analysis is rigorous, the implementation aspects (such as how to estimate the weighting function ($w(Z)$) or residual noise in high-dimensional settings) are under-explained and may limit reproducibility.\n\nFinally, the experimental evaluation, though adequate, could be expanded to include additional diagnostics such as calibration error or coverage-interval efficiency, and more intuitive visualizations would help convey how weighting and imputation mechanisms restore validity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)