Conformal Prediction is Robust to Label Noise
Authors: Bat-Sheva Einbinder
Stephen Bates
Anastasios Nikolas Angelopoulos
Asaf Gendler
Yaniv Romano
Venue: Submitted to ICLR 2023 (2023)

Abstract: We study the robustness of conformal prediction—a powerful tool for uncertainty quantification—to label noise. Our analysis tackles both regression and classification problems, characterizing when and how it is possible to construct uncertainty sets that correctly cover the unobserved noiseless ground truth labels. Through stylized theoretical examples and practical experiments, we argue that naïve conformal prediction covers the noiseless ground truth label unless the noise distribution is adversarially designed. This leads us to believe that correcting for label noise is unnecessary except for pathological data distributions or noise sources. In such cases, we can also correct for noise of bounded size in the conformal prediction algorithm in order to ensure correct coverage of the ground truth labels without score or data regularity.

Under review as a conference paper at ICLR 2023
CONFORMAL PREDICTION IS ROBUST TO LABEL NOISE
Anonymous authors Paper under double-blind review
ABSTRACT
We study the robustness of conformal prediction- a powerful tool for uncertainty quantification-to label noise. Our analysis tackles both regression and classifica- tion problems, characterizing when and how it is possible construct uncertainty sets that correctly cover the unobserved noiseless ground truth labels. With both theory and experiments, we argue that conformal prediction with noisy labels con- servatively covers the clean ground truth labels except in adversarial cases. This leads us believe that correcting for label noise unnecessary except for patho- logical data distributions or noise sources. In such cases, we can also correct for noise of bounded size in the conformal prediction algorithm in order to ensure correct coverage of the ground truth labels without score or data regularity.
INTRODUCTION
In most supervised classification and regression tasks, one would assume the provided labels reflect the ground truth. In reality, this assumption is often violated; see (Cheng et al. 2022 Xu et al.) 2019 Yuan al. 2018 Lee & Barber 2022, Cauchois et al., 2022). For example, doctors labeling the same medical image may have different subjective opinions about the diagnosis, leading to variability in the ground truth label itself. In other settings, such variability may arise due to sensor noise, data entry mistakes, the subjectivity of human annotator, or many other sources. In other words, the labels we use to train machine learning (MI.) models may often be noisy in the sense that these are not necessarily the ground truth. Quantifying the prediction uncertainty is crucial in high- stakes applications in general, and especially so in settings where the training data is inexact. We aim to investigate uncertainty quantification in this challenging noisy setting via conformal prediction, a framework that uses hold-out calibration data to construct prediction sets that are guaranteed to contain the ground truth labels; see (Vovk al. 2005 AAngelopoulos & Bates 2021). In short, this paper shows that conformal prediction typically yields confidence sets with conservative coverage when the hold-out calibration data has noisy labels.
We adopt a variation of the standard conformal prediction setup. Consider a calibration data set of i.i.d. observations {(X,, {=) sampled from an arbitrary unknown distribution Pxy. Here, X, E RRP is the feature vector that contains p features for the ith sample, and Y, denotes its response, which can be discrete for classification tasks continuous for regression tasks. Given the calibration dataset, an i.id. test data point (Xust, Yeest), and pre-trained model f. conformal prediction constructs a set ((Xesst that contains the unknown test response, Yeests with high probability, e.g., 90%. That is, for a user-specified level a E (0, 1),
IP (Yeest ((Xtest) 2
This property is called marginal coverage, where the probability is defined over the calibration and test data.
In the setting of label noise, we only observe the corrupted labels v = _(Y))) for some corruption
function g V> x (0, 1] + V, so the i.i.d. assumption and marginal coverage guarantee are invalidated. The corruption is random; we will always take the second argument of g to be random seed U uniformly distributed on [0. 1). To ease notation, we leave the second argument implicit henceforth. Nonetheless, using the noisy calibration data, we seek to form a prediction set Croisy (X that covers the clean, uncorrupted test label, Ytest- More precisely, our goal is delineate when it is

---

Under review as a conference paper at ICLR 2023
possible to provide guarantees of the form
P (Yrest E Enoisyy
(Xuest)(Xuss)) (Xuest) 2 a,
(2)
where the probability is taken jointly over the calibration data, test data, and corruption function (this will be the for the remainder of the paper). Our theoretical vignettes and experiments suggest that in realistic situations, 2 is usually satisfied. That is, even with access only to noisy that have conservative coverage clean labels. There are a few failure cases involving adversarial noise that we discuss, but in general we argue that user should feel safe deploying conformal prediction even with noisy labels.
labels, conformal prediction yields confidence
MOTIVATIONAL EXAMPLE
As real-world example of label noise, conduct an image classification experiment where only observe one annotater's label but seek to cover the majority vote of many annotators. For this purpose, we use the CIFAR-IOH data set, first introduced by Peterson al. (2019); [Battlday al. (2020); Siighh et al. (2220). which contains 10,000 images labeled by approximately 50 annotators. We calibrate using only single annotator and seek cover the majority vote of the 50. The single annotator differs from the ground truth labels in approximately 5% of the images.
Using the noisy calibration set (i.e., calibration set containing these noisy labels), we applied vanilla conformal prediction as if the data were i.id, and studied the performance of the resulting prediction sets. Details regarding the training procedure can be found in section 4.2 The fraction of majority vote labels covered is demonstrated calibration set the marginal coverage is 90%, expected. When using the noisy calibration coverage increases to approximately 93%. Figure also demonstrates the prediction sets that are larger when calibrating with noisy labels. This experiment demonstrates the main intuition behind our paper: adding noise will usually increase the variability in the labels, leading to larger prediction sets that retain the coverage property.
Figure 1 As we can see, when using the clean the
0.94
noley
dlean
True label:
True label:
Coverage
nominal
Car
Noisy:
Noisy:
(Cat, Dog)
[Car, Ship, Cat}
Clean:
Clean:
0.88
{Cat}
{Car)
Figure 1: Effect of label noise on CIFAR-10. Left: distribution of average coverage on a clean test set over 30 independent experiments evaluated on CIFAR-IOH test data with target coverage 1 a 90%, using noisy and clean labels for calibration. We use a pre-trained resnet 18 model, which has T accuracy of 93% and 90% on the clean and noisy test set, respectively. The gray bar represents the interquartile range. Center and right: prediction sets achieved using noisy and clean labels for calibration.
2 THEORETICAL ANALYSIS
In this section we show mathematically that under stylized settings and some regularity conditions, the marginal coverage guarantee (I) of conformal prediction persists even when the labels used for calibration are noisy: i.c., (2) holds. In Sections 3 and 4 we support this argument with realistic experiments. Towards that end, now give more details the conformal prediction algorithm.
As explained in the introduction, conformal prediction uses held-out calibration data and pre-trained model to construct the prediction set on a new data point. More formally, we use the model to construct score function, X' y + R, which is engineered to be large when the model uncertain and small otherwise.
Abbreviate the scores on each calibration data point as = s(X,, Y2) for each 1,..., n. Conformal prediction tells us that achieve marginal coverage guarantee by picking
2

---

Under review as a conference paper at ICLR 2023
Jclean ([[(++ () (1=1]) as the [(n + 1)(1 a]] -smallest of the calibration scores and constructing the prediction sets as
(Xtest) { E y 8 (Xrest, y) S J
We will introduce different score functions for both classification and regression needed in the following subsections.
In this paper, we do not allow ourselves access to the calibration labels, only their noisy versions, Yi.... Yn, so we cannot calculate ÿelean- Instead, we can calculate the noisy quantile quoisy as the [(n + ()(-))(11111))1 --a--aa)sslsllll -smallest of the noisy score functions, 3; sX,,, Y,). The main formal question of our work is whether the resulting prediction set, Cuoisy (Xtest) {yr ((Xeest y) S Quoisy J. covers the clean label as in ( We state this general recipe algorithmically for future reference: Recipe (Conformal prediction with noisy labels).
1. Consider i...d data points (x,, (.)...... (Xn: Yn); (Xtest, Yiest), comuptiio model y - Y, and a score function 8: X y + R.
2. Compute the conformal quantile with the corrupted labels,
(n 1)(1 ox)
Iuoiay = Quantile
(s(X,, (1)imi)
n
where Y; = gYY).
3. Construct the prediction sel using the noisy conformal quantile,
Euoisy = {y s t(xtest y) S "Iuoisy) }-
This recipe will produce valid prediction sets whenever the noisy score distribution stochastically dominates the clean score distribution. The intuition is that the noise distribution 'spreads out' the distribution the score function such that Inoisy is (stochastically) larger than Íclean- Theorem 1. Assume that P(Stest
1) S TP (Stest
f). Then,
P (Yrest E Cnoleyy (Xrest) 2 1 1 a. Furthermore, for any satisfying PP(Srsst 1) + u PlSteest S (), then
P (Yeest E Enotey (Xeesa) < 11-a+ + n
+ u.
In the following subsections, we present examples under which this schochastic dominance holds, and conformal prediction with noisy labels succeeds covering the true, noiseless label. The pur- pose of these examples is to illustrate simple and intuitive statistical setups where Theorem 1 holds. Under the hood, all proofs from Sections 2.1 2.3 are applications of Theorem T Though the noise be adversarially designed violate these assumptions and cause miscoverage (as in the impos- sibility result Proposition []. the evidence presented here suggests that in the majority of practical settings, conformal prediction can be applied without modification. All proofs are in Appendix A1
2.1 RANDOM CORRUPTIONS IN CLASSIFICATION
First will examine classification problem similar our motivating example in Section D in which the noisy label is randomly flipped 6 fraction of the time. This noise model is well-studied in the literature: see, for example, (Aslam Decatur 1996; Angluin Laird 1988 Ma et al.) 2018 Jenni & Favaro 20188] Jiindll et al. 2016)] Yuan et al. 2018).. Formally, in the setting of K-class classification, we deñine the corruption model as follows:
[y Y
w-p--c
Hip (v)
else,
where Y is uniformly drawn from the set {1, K Also consider the adaptive prediction sets (APS) scores, first introduced by Romaao (2020).
ArS (x. y)
Σ f. (x) I ( ( (x) my (x)) + fry (x) U y'yy
3

---

Under review as a conference paper at ICLR 2023
where is the indicator function, Ry (x) is the estimated conditional probability P(Y y X = z) and U" ~ UO, 1). To make this non-random, variant of the above where U = 1 is often used.
The next proposition shows that for any classifier that ranks classes in the same order as IP(Y) | X) the APS score leads to valid coverage when calibrated noisy data.
Example 1. Let ČAPS (Xtest) be constructed as in Recipe 1 with the corruption function g gatp and Doisy the score function sAPS (deterministic version) with any classifier that ranks the classes in the same order the oracle classifier #y(x)) = P(Y - X =x). Then
K-1 K
1 1-a a S SP Ylest
noisy (X 5 a
++1
The APS score one of two popular conformal methods for classification. The other score from Vovk et al. (2005): Lei et al. (2013), is referred to as homogeneous prediction sets (HPS) score, RP (z. y)
ny (z), for some classifier ăy (x) E [0. 1]. The next proposition shows that
with access to an oracle classifier for the noisy label distribution fy(x) = P(Ý = X = z),
conformal prediction covers the noiseless test label.
Example 2. Let CHPS (Xesa) be constructed as in Recipe with the corruption function g where noisy
< ) and the score function HHPS with the oracle classifier Ry(x) (P = y x =)x Then
1
1- S
Ytest E Coiss (X S
1).
should be noted that the above theorem only requires knowledge of the noisy conditional distribu- tion (Y | X), so model trained on a large amount of noisy data should approximately have the desired coverage as well.
2.2 CONFORMALIZED QUANTILE REGRESSION WITH SYMMETRIC NOISE
Next we will analyze a regression task where the labels are continuous-valued and the corruption function is
-سm + Z
for some symmetrie, unimodal, independent noise sample Z. We also assume that Y X is symmet- ric unimodal. We analyze the most common regression strategy, conformalized quantile regression (CQR) as presented by Romano et al. (201)). Let the score function be
CQR (x, v) max((qu (xr) y- 1/ Oon: ())
where qa., and Ja,. estimates of the a/2 and - a/2 conditional quantiles respectively.
We will analyze the setting where da,. and Gans fall on the correct side of the true median of the noisy distribution, an extremely weak assumption about the fitted model. In this case, conformalized quantile regression achieves valid coverage even with noisy labels, as stated next.
Example 3. Let moisy Xust) be constructed as in Recipe with the corruption function geym and the score function CQQ where the estimated quantiles satisfy qono (x) S <91/2(z) S qanc (I), where 41/2(x) is the true median of Y | T. Then
P P(Yiest
ZCQR (Xeest)
21-
2.3 CONFORMALIZED UNCERTAINTY SCALARS
We next analyze the case of a score function using a single uncertainty scalar, ú(x) > 0. In this setting, conformal prediction will work whenever the noisy label distribution has the same mean as, but heavier tails than, the ground truth label distribution.
We set the corruption function be
(4)) y Z,
4

---

Under review as a conference paper at ICLR 2023
where Z satisfies
P P(Y Joy-EYVII x = ==]] =]|> i x =x) s S < Y
- B x =|] -|| x=)
This condition is satisfied in many statistical setups, including the case from the previous section, where Y and Z are symmetric and Y is unimodal.
Also take the score function to be the normalized magnitude of the residual,
RM (zs, y) [f(x) vl/ū(x).
The following result states that conformal prediction is robust to these conditions. Example Let CRM be constructed as in Recipe with the score function gRM using the oracle model f(x)) E, X₃ x and the corruption function g" Then
P (Vrest
FRM Colaay (Xess))
2 -
This example summarizes the practical intuition that if has lighter tails than Y+Z, then conformal prediction will be conservative (see Corollary in Appendix AT for a statement terms of tail bounds).
2.4 DISCLAIMER: DISTRIBUTION-RRIE RESULTS
Though the coverage guarantee holds in many realistic cases, have also given examples where conformal prediction fails to cover. Indeed, the general case, conformal prediction will fail to cover, and must be adjusted to account for the size of the noise. The following proposition makes clear that for any nontrivial noise distribution, there exists a score function that breaks naive conformal.
Proposition 1 (Coverage is impossible in the general case.). Take any Ý Y.. Then there exists score function that yields P (Yest Croisy (Xust) < <P
<P(Yeest (Yrest =((eest)).
The above proposition says that for any noise distribution, there exists an adversarially chosen score function that will disrupt coverage. Furthermore, as we discuss in Appendix AT with noise of sufficient magnitude, it is possible to get arbitrarily bad violations of coverage.
Next, we discuss how to adjust the threshold of conformal prediction to account for noise of a known size, as measured by total variation (TV) distance from the clean label.
Corollary (Corollary of Barber et (2022)). Let Y be any random variable satisfying DTv(Y, Ý) Take a' = =a TTTE. Letting Enoisy (Xuest be the output of Recipe with any score function at level yields
P(Yeet Enoisy (Xreet) 1
We discuss this strategy more in Appendix AT the algorithm implied by Corollary [ may not be particularly useful, as the TV distance is badly behaved quantity that is also difficult to estimate.
As final note, if the noise is bounded in TV norm, then the coverage is also not too conservative. Corollary 2 (Corollary of Barber al. 2022) Theorem 3). Let Y be any random variable satisfying DYv Y) < ç. Letting Croisy (Xtest) be the oulput of Recipe with any score function at level o yields
P(Yrest Enninyy (X (Xeost))
1
n+1
3 SYNTHETIC EXPERIMENTS
3.1 CLASSIFICATION
In this section, we focus on multi-class classification problems, where we study the validity of conformal prediction using different types of label noise distributions, described below.

---

Under review as a conference paper at ICLR 2023
Neural network classifier
Oracle classifier
Neural network classifier
Oracle classifier
Clean
sype.
Uniform flip
HPS
Confusion matrix
nominal
frequent class
0.90
0.95
0.85
0.90
0.95
1.0
1.5
1.0
1.5
Coverage
Average
Figure 2: Effect of label noise on synthetic multi-class classification data. Performance con- formal prediction sets with target coverage 1 90%, using noisy training set and noisy calibration set. Left: Marginal coverage; Right: Average size predicted sets. The results are evaluated over 100 independent experiments and the gray bar represents the interquartile range.
Class-independent noise. This noise model, which we call uni form flip, randomly flips the ground truth label with probability e, defined formally by the class corruption function g in (A6). We analyzed this setting in depth in Section 2.1 and proved that the coverage achieved by an oracle classifier is guaranteed to increase.
Class deasndee noise. In contrast to uniform flip noise, here we consider a more challeng- ing setup which the probability of label be flipped depends on the ground truth class label Y. Such noise label is often called Noisy at Random (NAR) in the literature, where certain classes are more likely to be mislabeled or confused with similar ones. Let T be row stochastic transition matrix of size K x K such that Ti is the probability of a point with label to be swapped with label j. In what follows, we consider three possible strategies for building the transition matrix T. (1) Con Confus fusi on matrix (Algan & Ulusoy 2020): we define T as the oracle classifier's confusion matrix, up to a proper normalization to ensure the total flipping probability is e. We provide a theo- retical study of this case in Appendix AL.3 (2) Rare to most frequent class (Xu et al.) 2019): here, we flip the labels of the least frequent class with those of the most frequent class. This noise model is not uncommon in medical applications: imagine setting where only small fraction of the observations are abnormal, and thus likely to be annotated as the normal class. If switching between the rare and most frequent labels does not lead total probability of e, we move the next least common class, and so on.
To set the stage for the experiments, we generate synthetic data with K = 10 classes as fol- lows. The features X E IRd follow a standard multivariate Gaussian distribution dimen- sion d = 100. The conditional distribution of Y X is multinomial with weights wy exp((x B)r)/ E exp((x' B):), where B Rd K whose entries are sampled independently from the standard normal distribution. In our experiments, we generate total of 60, 000 data points, where 50, 000 are used to fit classifier, and the remaining ones are randomly split to form calibra- tion and test sets, each of size 5, 000. The training and calibration data corrupted using the label noise models we defined earlier, with a fixed flipping probability of c = 0.05. Of course, the test set not corrupted and contains the ground truth labels. We apply conformal prediction using both the HPS and the APS score functions, with a target coverage level a of 90%. We use two predictive models: two-layer neural network and oracle classifier that has access the conditional distri- bution of Y X. Finally, report the distribution of the coverage rate as in ( and the prediction set sizes across 100 random splits of the calibration and test data. As a point of reference, we repeat the same experimental protocol described above on clean data; in this case, do not violate the i.i.d. assumption required to grant the marginal coverage guarantee in (T.
The results are depicted in Figure As expected, in the clean setting all conformal methods achieve the desired coverage of 90%. Under the uniform flip noise model, the coverage of the or- acle classifier increases around 94%, supporting our theoretical results from Section 2. The neural network model follows a similar trend. Although not supported by a theoretical guarantee, when corrupting the labels using the more challenging confusion matrix noise, can a conservative behavior similar to the uni form flip. By contrast, under the rare to most decrease in coverage, which is in line with dis-
requent cl ass noise model,

---

Under review as a conference paper at ICLR 2023
100
10
clean length
90
Coverage
nominal
Longth
6-
80
symmetric heavy-tail
symmetric light-tail
70
asymmetric
biased
0.0
0.1 Noise Magnitude
0.01
1.0
0.0
0.1 Noise Magnitude
0.01
1.0
Figure 3: Response-independent noise. Performance of conformal prediction intervals with target coverage a = 90%, using noisy training set and a noisy calibration set. Left: Marginal cov- erage; Right: Length of predicted intervals (divided by the average clean length) using symmetric, asymmetric and biased noise with a varying magnitude. The results are evaluated over 50 inde- pendent experiments, with error bars showing one standard deviation. The standard deviation of Y (without noise) and the square root of E [ar [Y X]] are both approximately 2.6.
claimer from Section 2.4
Yet, observe how the APS score tends to be more robust to label noise than HPS, which emphasizes the role of the score function.
we provide additional experiments with adversarial noise models that more ag- gressively reduce the coverage rate. Such adversarial cases are more pathological and less likely to occur in real-world settings, unless facing malicious attacker.
In Appendix 1
3.2 REGRESSION
Similarly the classification experiments, we study two types of noise distributions.
Response-independent noise. We consider an additive noise of the form: = Y 2, where e a parameter that allows control the noise level. The noise component
random variable sampled from the following distributions. (1) Symmetric light tailed: standard normal distribution; (2) Symmetric heavy tailed: t-distribution with one degree of freedom; (3) ysymme r i c: standard gumbel distribution, normalized to have zero mean and unit variance; and (4) Biased: positive noise formulated as the absolute value of #2 above.
Response-dependen noise. Analogously to the class-dependent noise from Section 3.1 we de- fine more challenging noise models as follows. (1) Contractive this corruption pushes the ground truth response variables towards their mean. Formally, Y, Y. (Y, 1 Σ Y)) U, where U a random uniform variable defined on the segment [0,0.5], and n is the number of calibration points. (2) Dispersive: this noise introduces some form of dispersion effect the ground truth response, which takes the opposite form of the contract ractive model, given by
Y, - Y; - - V.)
Having defined the noise models, we turn to describe the data generating process. We simulate a 100-dimensional whose entries are sampled independently from a uniform distribution on the segment [0, 5]. Following Romano et al. (2019), the response variable is generated as follows:
(4) where X is the mean of the vector X, and Pois(A) is the Poisson distribution with mean A. Both Mi and 1/2 are i.i.d. standard Gaussian variables, and U is a uniform random variable on [0. 1]. The right-most term in (4) creates a few but large outliers. Figure A2 in the appendix illustrates the effect of the noise models discussed earlier on data sampled from
Y ~ Pois(sin (XX) + 0.1) + 0.03 X 7)1 + 25 1/2 1 {U < 0.01),
We apply conformal prediction with the CQR score for each noise model as follows 1 First, we fit a quantile random forest model on 8, 000 noisy training points; we then calibrate the model
In our experiments, we use the original score from Romano et al, 2209 that can have negative values in contrast to the score defined in (3) as the former is more likely to be used in practice. Formally, the score
apply CQR (zr, v) max (fa, (ar) y.y Ganc (x))-

---

Under review as a conference paper at ICLR 2023
3.0
Coverage
90
2.5
Length
80
Calib set
2.0
noisy clean nominal
1.5
contractive
dispersive
contractive
dispersive
Noise
Noise
Figure 4: Dispersive versus contractive noise regression experiment. Performance of conformal prediction intervals with target coverage 1 90%, using noisy training set and noisy calibration set. Left: Marginal coverage; Right: Length of predicted intervals. The results are evaluated over independent experiments and the gray bar represents the interquartile range.
using 2, 000 fresh noisy samples; and, lastly, test the performance on additional 5, 000 clean, ground truth samples. The results are summarized in Figures 3 and A Observe how the predic- tion intervals tend to be conservative under symmetric rim, both for light- and heavy-tailed noise distributions, asymmetric ric, and di apersivve corruption models. Intuitively, this is because these noise models increase the variability of Y; in Example 3 we prove this formally for any symmetri independent noise model, whereas here show this result holds more generally even for response-dependent noise. By contrast, the prediction intervals constructed under the b ased and coontrcctive corruption models tend under-cover the response variable. This should not surprise us: following Figure(A2[c), the biased noise shifts the data 'upwards', and, consequently, the prediction intervals are undesirably pushed towards the positive quadrants. Analogously, the cont centractive ivee corruption model pushes the data towards the mean, leading to intervals that are narrow. Figure A5 in the appendix illustrates the scores achieved when using the different noise models and the 90% th empirical quantile of the CQR scores. This figure supports the behaviour
we see Figures A3 3 and A4 over-coverage is achieved when Qnoicy larger than Gelean and under-coverage is obtained when Inoisy is smaller.
In Section A2.7 of the Appendix study the effect of the predictive model the coverage prop- erty, for all noise models. To this end, we repeat similar experiments to the ones presented above, however, now fit the predictive model clean training data; the calibration data remains noisy. We also provide an additional adversarial noise model that reduces the coverage rate, but is unlikely appear in real-world settings. Figures A3 and A4 in the appendix depict similar behaviour for most noise models, except the biased noise for which the coverage requirement is not violated. This can be explained by the improved estimation of the low and high conditional quantiles, these are fitted on clean data and thus less biased.
REAL DATA EXPERIMENTS
4.1 REGRESSION: AESTHETIC VISUAL RATING
In this section, present a real-world application with continuous response, using Aesthetic Visual Analysis (AVA) data set, first presented by Murray et al.) (2012). This data set contains pairs of images and their aesthetic scores the range of 10, obtained by approximately 200 annotators. Following Kao et al. (0155) Talebi & Milanfar 20:18;; Murray et al. (2012), the task is to predict the average aesthetic score of given test image. Therefore, we consider the average aesthetic score taken over all annotators as the clean, ground truth response. The noisy response is the average aesthetic score taken over 10 randomly selected annotators only.
We examine the performance of conformal prediction using both CQR and the residual magnitude score-the score from Section 2.3 with û(x)) transfer learning approach to fit the predictive model. Specifically, for feature extraction, we use a VGG-16 model-pre- ces---pe-trinnn trained the ImageNet data set set-whose last (deepest) fully connected layer removed. Then, we feed the output the VGG-16 16 model to a linear fully connected layer to predict the response. We trained two different models: quantile regression model for CQR and
We follow Talebi & Milanfar (2018) and take
8

---

Under review as a conference paper at ICLR 2023
96
3.0
94
Coverage
noisy clean
Length
2.8
nominal
2.6
2.4
88
Residual magnitude
CQR
Residual magnitude Method
CQR
Method
Figure 5: Results for real-data regression experiment: predicting aesthetic visual rating, Per- formance of conformal prediction intervals with 90% marginal coverage based on a VGG-16 model using noisy training set. We compare the residual magnitude score and CQR methods with both noisy and clean calibration sets. Left: Marginal coverage; Right: Interval length. The results are evaluated over 30 independent experiments and the gray bar represents the interquartile range.
classic regression model for conformal with residual magnitude score. The models are trained on 34, 000 noisy samples, calibrated on 778 noisy holdout points, and tested on 7, 778 clean samples. Further details regarding the training strategy are in Appendix [A2.3]
Figure Soureepppee portrays the marginal coverage and average interval length achieved using CQR and resid- ual magnitude scores. As a point of reference, this figure also presents the performance the two conformal methods when calibrated with clean calibration set; as expected, the two perfectly attain 90% coverage. By constant, when calibrating the same predictive models with a noisy calibration set, the resulting prediction intervals tend be wider and to over-cover the average aesthetic scores.
4.2 CLASSIFICATION OBJECT RECOGNITION
We return to the classification experiment in Section | The CIFAR-I0H data set contains the same 10,000 images as CIFAR-10, but with labels from single annotator instead of majority vote of 50 annotators. We fine-tune ResNet18 model pre-trained on the clean training set of CIFAR- which contains 50,000 samples. Then we randomly select 2,000 observations from CIFAR- 10H for calibration. The test set contains the remaining 8,000 samples, but with CIFAR-10 labels.
Figure illlutraates results obtained by applying conformal prediction with the APS score. We can see that (i) we obtain the exact desired coverage when using the clean calibration set; and (ii) when calibrating noisy data, the constructed prediction over-cover the clean test labels. This is because the sets tend to be larger when calibrating on noisy data, as seen in Figure A6
DISCUSSION
Related work. Conformal prediction was first proposed by Vladimir Vovk and collaborators (Vovk
cet al. 1999; 2005). Recently there has been body of work studying the statistical properties of conformal prediction (Lei et al.
2018 Barber 2020) and its performance under deviations from
exchangeability (Tibshirani et al.
2019 Podkopaev & Ramdas 2021] Barber et al.] 2022). Label
noise independently of conformal prediction has been well-studied; see, for example Angluin &
Laird 1988); Tanno et al. (209)); Frénay & Verleysen (2013). To our knowledge, conformal predic- tion under label noise has been previously analyzed. The closest work ours is that Cauchois et al. (2022) studying conformal prediction with weak supervision, which could be interpreted as type of noisy label.
Future directions. Our work raises many new questions. First, one can try and define a score function that is more robust to label noise, continuing the line of Gendler et al. (022)); Frénay & Verleysen (2013); Cheng et al. (2022). Second, an important remaining question is whether or not conformal risk control (Angelopoulos et al. 202 (022) more generally is also robust to label noise. Lastly, it would interesting to analyze the robustness of alternative conformal methods such as cross-conformal and jackknife+ (Vovk] 2015 Barber al. 2021) that do not require data-splitting.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Görkem Algan and Iikay Ulusoy. Label noise types and their effects on deep learning. arXiv preprint arXiv:2003. 10471, 2020.
Anastasios N Angelopoulos and Stephen Bates. A gentle introduction conformal prediction and distribution-fiee uncertainty quantification. arXiv preprint arXiv:2107.07511, 2021.
Anastasios N. Angelopoulos, Stephen Bates, Emmanuel J. Candès, Michael Jordan, and Lihua Lei. Learn then test: Calibrating predictive algorithms to achieve risk control. arXiv preprint, 2021. arXiv:2110.01052.
Anastasios Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Conformal risk control. arXiv preprint 2rXiv:2208.028144 2022.
Dana Angluin and Philip Laird. Learning from noisy examples. Machine Learning, 2(4))343-370, 1988.
Javed Aslam and Scott Decatur. On the sample complexity of noise-tolerant learning. Informa- tion Processing Letters, (194)::89-195, 1996.
Rina Foygel Barber. Is distribution-fie frree inference possible for binary regression? arXiv:2004.09477, 2020.
Rina Foygel Barber, Emmanuel Candès, Aaditya Ramdas, and Ryan J Tibshirani. Predictive inference with the jackknife+.. The Annals of Statistics, 49(1):486 507,2021,
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. Conformal prediction beyond exchangeability. arXiv preprint arXiv:2202.13415. 2022.
Ruairidh M Battleday, Joshua C Peterson, and Thomas L Griffiths. Capturing human categorization of natural images by combining deep networks and cognitive models. Nature communications, 11(1):1-14, 2020.
Maxime Cauchois, Suyash Gupta, Alnur Ali, and John Duchi. Predictive inference with weak supervision. arXiv preprint arXiv:2201.08315, 2022.
Chen Cheng, Hilal Asi, and John Duchi. How many labelers do you have? a closer look at gold- standard labels. arXiv preprint arXiv:2206. 02.222266.244,, 2022.
Benoît Frénay and Michel Verleysen. Classification in the presence of label noise: survey, IEEE transactions on neural networks and learning systems, 25(5):845-869 2013.
Asaf Gendler, Tsui- Wei Weng. Luca Daniel, and Yaniv Romano. Adversarially robust conformal prediction. In International Conference on Learning Representations, 2021.
Simon Jenni and Paolo Favaro. Deep bilevel learning. In Proceedings of the European conference on computer vision (ECCV), pp. 618-633. 2018.
Ishan Jindal, Matthew Nokleby, and Xuewen Chen. Learning deep networks from noisy labels with dropout regularization. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pp. 967-972. IEEE, 2016.
Yueying Kao, Chong Wang, and Kaiqi Huang. Visual aesthetic quality assessment with regression model. In 2015 IEEE International Conference on Image Processing (ICIP), pp. 1583-1587. IEEE, 2015.
Yonghoon Lee and Rina Foygel Barber. Binary classification with corrupted labels. Electronic Journal of Statistics, 16(1):1367 - 1392, 2022.
Jing Lei, James Robins, and Larry Wasserman. Distribution- prediction sets. Journal of the American Statistical Association, 108(501):278-225) 2013.
Jing Lei, Max G Gell, Alessandro Rinaldo, Ryan J. Tibshirani. and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113 1524):1094-1111, 2018.
10

---

Under review as a conference paper at ICLR 2023
Xingjun Ma, Yisen Wang, Michael E Houle, Shuo Zhou, Sarah Erfani, Shutao Xia, Sudanthi Wijew- ickrema, and James Bailey. Dimensionality-dri -rivee learning with noisy labels. In International Conference Machine Learning, pp. 3355-3364 PMLR, 2018.
Naila Murray, Luca Marchesotti, and Florent Perronnin. Ava: large-scale database for aesthetic visual analysis. In 2012 IEEE conference on computer vision and pattern recognition, pp. 2408- 2415. IEEE, 2012.
Joshua Peterson, Ruairidh M Battleday, Thomas Griffiths, and Olga Russakovsky. Human uncertainty makes classification more robust. In Proceedings of the IEEE/CVE International Conference on Computer Vision, pp. 9617-9626, 2019.
Aleksandr Podkopaev and Aaditya Ramdas. Distribution-fre uncertainty quantification for classi- fication under label shift. In Uncertainty in Artificial Intelligence, pp. 844 853-553. PMLR, 2021.
Yaniv Romano. Evan Patterson, and Emmanuel Candès. Conformalized quantile regression. In Advances in Neural Information Processing Systems, volume 32, pp. 3543-3553, 2019.
Yaniv Romano, Matteo Sesia, and Emmanuel Candès. Classification with valid and adaptive cover- age. Advances in Neural Information Processing Systems, volume 33, pp. 3581-3591 2020.
Pulkit Singh, Joshua C Peterson, Ruairidh M Battleday, and Thomas L Griffiths. End-to-end deep prototype and exemplar models for predicting human behavior. arXiv preprint arXhv:2007.08723, 2020.
Hossein Talebi and Peyman Milanfar. NIMA: Neural image assessment. IEEE transactions on image processing, 27(8))3998 4011, 2018.
Ryutaro Tanno, Ardavan Sacedi, Swami Sankaranarayanan, Daniel C Alexander, and Nathan Silber- man. Learning from noisy labels by regularized estimation of annotator confusion. P Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 11244-11253, 2019.
Ryan Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal pre- diction under covariate shift. In Advances in Neural Information Processing Systems, volume 32, pp. 2530-2540. 2019.
Vladimir Vovk. Cross-conformal predictors. Annals of Mathematics and Artificial Intelligence, 74 (1-2):9-28, 2015.
Vladimir Vovk, Alexander Gammerman, and Craig Saunders. Machine-leaming applications of algorithmic randomness. In International Conference on Machine Learning, pp. 444-453, 1999.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in Random World. Springer, New York, NY, USA, 2005.
Yilun Xu, Peng Cao, Yuqing Kong, and Yizhou Wang. L.dmi: A novel information-theoreiiic theoretic loss function for training deep nets robust to label noise. Advances in neural information processing systems, 32, 2019.
Bodi Yuan, Jianyu Chen, Weidong Zhang, Hung-Shuo Tai, and Sara McMains. Iterative cross learning on noisy labels. In 2018 IEEE Winter Conference on Applications of Computer Vision (WACV), pp. 757-765. IEEE, 2018.
11

---

Under review as a conference paper at ICLR 2023
Appendices
A1
MATHEMATICAL PROOFS
Theorem
Our assumption states that
P(Stest S t) S P(stess S t).
Note that the probability is only taken over Steat. Since Inoisy constant (measurable) with respect to this probability, have that, for any (0, 1),
PP(Seest I Qnoisy) 2 Pl S @noisy) 2 - ar.
This implies that Yest Euoiay (Xrest) with probability least a, completing the proof of the lower bound.
Regarding the upper bound, by the same argument,
1 12 + +
P(stest S quoisy) S (Stest S quoisy) u susl- a
A1.1 APS SCORE
Lemma A1. Let fy(x) y be any classifier that ranks the classes in the same order as the oracle model, i.e., one satisfying, for all + y',
fx)x) 2 f - (x) N (z).
(AI)
Let be the (deterministic) APS conformal score with model f.
s(x, Σ fx)) ( (f) fz())/)
w'EY
Consider the corruption function Allp, Then,
P(s(X, P((()) s
Proof of Lemmal A7 For notational convenience, assume the classes are ordered such that (x( decreasing in y. Fix x E X, let Ph = P(Y = k X = x) and let us use the shorthand
f = P( = k X = x). Finally, draw XXY, from their joint distribution
Notice that in this context, the assumption (Al simply states that मे is sorted from greatest to least. Furthermore, by the defiittion Hlip.
* (1 - (K 1)e/K) + (1 pa)eppaeKKKK p& - + t/K.
(A2)
This implies that मं and p% have the same ordering, and therefore, that the entries pv are also decreasing in In the ensuing argument, this fact will be crucial. Starting with the law of total probability,
#A (s(x, (s( ((s((, Y) < t X = x)) Σ KEY
5t)
Σ #
(A3)
kss(z,R)
Take k* (k: f1/:ifk
the proof becomes trivial by noticing that P(s(æ, Y) <
X X = x) < P(s(z, Y) < X = x) and applying the tower property. Therefore, we
continue the proof in the that k. 1. Because s(x, k) is monotone in k. rewrite the last expression as
#
mk-
k=1
12

---

Under review as a conference paper at ICLR 2023
Applying AA2 and using the fact that P& is sorted in decreasing order yields
nR = -
Σ Pk khekK
Σ pk k* k</K
Σ k=1
Pk
Next we will critically use the fact that p is sorted from greatest to least. This sorting implies that (p) +... +p. pk) k/K K for all (if this failed at any k, we would have (pi +... < which impossible). Applying this fact at the k th index,
K'' E
Pk K²/K
Pk
Pkr
(A4)
as the term multiplied by is negative. Reversing the steps from A3 one can rewrite the limits of sum as an indicator function, which by law of total probability yields the CDF of the scores,
Σ Pk= A=
Σ Pk =
Σ p&l (s(X, t st kEY
(A5)
(zs(
We have so far proved that
((s( Y) St x x P(s(2, Y) St X z);
taking expectations on both sides yields the conclusion,
P(s(X, F) () S P(s(X, 1)
Proof of Example|
7 To complete the proof of the lower bound it suffices to show that ((s(X,)) S
t) 2 P(s(X, Y) < t). We prove this in Lemma Al
For the coverage upper-bound, combining
A4 and
A5
witness that
st st
Σ pk +
k"/K Σ
Pk
k=
= P(s(x, Y) s x
+
k"/K
km
We can lower-bound this expression by realizing that k² /K Ek= Pss takes values no lower than - -KK- 1)/K. Therefore,
K-1 P(s( St {t x).
P(s(r. f) st
= x K
Applying the tower property and noting that by the standard conformal argument Vork at. (2005). gives ((s(z, f) < 2 1 a 1/(n +1 yields
K --1 P(s(x,, Y)
a n+1
+
K
A1.2
HPS SCORE
Proof of Example For proof with the HPS function, we consider the following corruption model:
Opp (v)
y Y
w.p -
(A6)
clse,
where Y" uniformly drawn from the set {1, ...,..
K} \ Y. This is the same as g" Hip, but rescaled so
that in g flp corresponds e(K - -1)/ KK in dipp.
13

---

Under review as a conference paper at ICLR 2023
Consider the corrupted oracle nonconformity score s(z, y) = - P(Y X). By definition of this
score function, we can explicitly write the probability mass functions of á, and 8, as follows:
( =
p( |
= [x)] and
K
P =t x) = (1
- x1)
j=1
Note that these two distributions are supported on the same discrete set, D - 1,..., K.. Applying the definition of our corruption model and rearranging yields
K
P(Ý x)
K- P( xj(x) + K-1
(A7)
Using this fact and the law of total probability, we can write
K
P (s; S g) - P (3, 4 = ΣΣ
= xi) 1 t= P |
EDD 159
1=1
(A8)
eK Σ1 K
K x 1 P(Y P(Y - K
P(Y =
LED 15q
eK
1 K-j
K
1
K
K
LED 159
K-1
where the last step holds because each summand is nonzero at exactly one value of
To prove the lower bound, we will show that IP (s; 5 - P (&s S <g) 2 0. It suffices to show that each summand in the last line of (A8) is positive. This is trivially true when i > 1 - e/(K 1)
because by (A7), we have that inf, P(Y j X) 2 e/(K
1). and thus q 1. To complete the c/(K [K - 1) and S 1 - 1/K, then
proof, our goal is to show that i < 1
1 K-I l
1
2
1 K
K
K-IE
Rearranging terms in the above expression gives
1
2 t.
K
This is implied directly by combining the two bounds 5 1 1 -e/(e/(K 1) and < 1/K. This completes the proof of the lower bound.
To prove the upper bound, we need to show that
eK min([1/(1 9)),
P(s: S q)
P( q)
K-I
The last line of A8
can be rewritten as
eK
t
1 eK
1 1- K-1
1
cK
K
l[te D: st
K
K
K
K -
1
K
K
K
EED
K
LED
154
EK²
K-
K-1 K.
K
k-
where the inequality upper-bounded the cardinality by K and the last term by 0.
To recover the statement in the main paper, one can rewrite this final expression with e(K - 1)/K substituted in wherever the term appears. Rearranging terms then gives the result.
n
14

---

Under review as a conference paper at ICLR 2023
A1.3 CONFUSION MATRIX
The confusion matrix noise model more realistic than the uniform flip. However, there exists score function that causes conformal prediction to fail for any non-identity confusion matrix. We define the corruption model as follows: consider matrix T in which (T), = PP( =j
w.p. Ti.9
confusion (v)
K
w.p. TKy-
Example 5. Let Euoiey be constructed in Recipe function gonnfusion, Then,
with any score function and the corruption
P (Yrest E Euniny (Xurst) 2 1-aa
and only for all classes
j E {l....,KK K}.
Σ - 1'11 j)PP(3 2) St j).
The proof is below. In words, the necessary and sufficient condition for the noise distribu- tion/confusion matrix P(Y I j) to place sufficient mass on those classes j' whose quantiles which are larger than P(s (tssty=) j). However, without assumptions on the model and score, the conditional probabilities are unknown, so is impossible to say which noise distributions will preserve coverage.
Proof.
By law of total probability, P(s S () = (P(s S =]] = S
But under the noisy model, we have instead that
K
= -
P(3 .) = - -
j=1
We can write
K K
F(s S -)-P(s = Σ
Σ
wy = Y -
j=13'=1
Combining the sums and factoring, the above display equals
K (P(Y (V0==11==J(<<111> -P
Wj
1=1
We can factor this expression as
- -( 1
Σ
StpPostt|y = +) P(
P(s K
j'1
The stochastic dominance condition holds uniformly over all choices of base probabilities w, if and only if for all j E [K].
F(Ý j' Σ
- j)P - - P(s
Notice that the left-hand side of the above display is convex mixture of the quantiles PP5 S Y j') for j' E [K]. Thus, the necessary and sufficient condition is for the noise distribution P(Ý =' Y 1) to place sufficient mass those classes j' whose quantiles which are larger than P(s < t = But of course, without assumptions on the model and score, the latter are unknown, is impossible say which noise distributions will preserve coverage.
15

---

Under review as a conference paper at ICLR 2023
A1.4 CQR SCORE
Proof of 3 We will show that ( S q x < ((s S q = z). Notice that we
will only prove for the where 9 0 since according to the score function, for 9 S 0 both probabilities are equal to zero. Formally,
(3 1 X = x) P (max (x) - Y Z,Y + - Aos (x)) 5 X - x)
P (Rar (x) Y 7 S q, 2 Jan. (I) S X ==x) x)
P (Rar, (I)) S + 2 aa, (z) + = x)
P(Y + Z 2 dons (x) + X - x) P(Y + Z S Unc (x) - q X = =x).
Similarly,
= x= P(
Jon. (x) + X = x) - PY s Jos (z) - X = z).
x
According to Lemma A2
1- (Y + 2 Done (z) X = PP
+ + amw (z) q X =) x)
S 1 - P (Y 2 aanc (1) + X = r) P (Y < aN. (x) 9 X x),
under the assumption that
jay (z) 91/2(()) aan. (z),
where (1)) is the true median of Y X = x. By the law of total probability this inequality holds also without conditioning on X.
L
Lemma A2. Suppose Y has density that is unimodal and symmetric around 0 and Z is symmetric, i.e. has the same distribution as- ZZ. Suppose further that Y and Z are independent. Then for any q 0,
P(Y 7 -1) P(Y S 5-9)
and
P(Y + ++222)2 2 P(Y 2 g)
Proof of Lemma A2
P(Y + < -9) = (( + +2 - = =]]
P(Y S - +)+ + 1
PP s -q+ z)
2
2
1
P(Y S -q) +
(P(Y - 2) P(V s -
+ (P(YY= s -q+ 2) - P(Y S -1)) 2
2
1
P(Y s (q) +
(P(Y S -4+2) P(Y s -q))
(P(Y s -9) - PPY s -q 2))
2
2
1
PP( S -q) +
TP-- < < - 2)
2 P(
< Y $ 4)
20
2 P(Y < -
Above, the expectations are over z 2 which we take to be a random variable with the same distribution ZZ. The final inequality follows from the fact that the density of Y is unimodal. The proof for the upper tail is similar and omit it.
16

---

Under review as a conference paper at ICLR 2023
A1.5
NORMALIZED RESIDUAL MAGNITUDE SCORE
Proof of Example Equation 2.3 directly implies
P E X = /(()) = = < X 21)((x) > ( x
since ((x) > 0 and both probabilities are X-conditional. Furthermore, since we using the oracle
model Y X =r. this is identical to the statement
IP(
RM test
2
P test 5)..
The above statement says that the clean score distribution stochastically dominated by the noisy score distribution. Since quoisy is independent of RM and SRM: we know
P P(Stest I quoisy) 2
P(RRM test
S Imoiay) 2 11-ac a.
This completes the argument.
The following is direct corollary of Example 4
Corollary 3. Suppose the Y; are drawn L.I.D. Y, = + Zi Assume there exist constants e and C such that
IP Y. -XX] 1t) 2 1 ceepp(-CC and + -, s <1-cep((--C)
Then
P(s 5 2
There is nothing special about the sub-Gaussiar tail decay in the above corollary; any tail decay conditions will work if they can be chained together.
A1.6 DISTRIBUTION-FREE RESULTS
Proof of Proposition 7 For convenience, assume the existence of probability density functions and for Y and Y respectively (these be taken to be probability mass functions if ) is discrete). Also define the multiset of Y values E (Yı,.., Y.) and the corresponding multiset of Y values É. Take the set
A = (v p(v) p(v)).
Since Y * Y, we know that the set A is nonempty and P( E E) The adversarial choice of score function will be s(x, y) fy A"); puts high mass wherever the ground truth label is more likely than the noisy label. The crux of the argument is that this design makes the quantile smaller when it is computed on the noisy data than when computed on clean data, as we next show.
Begin by noticing that, because s(x, y) is binary, Getean is also binary, and therefore qelean >/< Gelean = 1. Furthermore, Gclean if and only if [ n nAl < [(n 1) - aa]l Thus, these events are the same, and for any E (0, 1].
P (Qolean
2 t) =
< [(n 1 1)(1-a)])
By the definition of A, we have that P (EENA) < ((++1)(1111))) > >P(EnA) |nn < +(n+1)(1
a)]). Chaining the inequalities, get
PP (gelean 21) P(( < [(n 1)(1 a]1) = PĀ 2 t). 1)(1-a)1)
Since S1+1 is measurable with respect to and É, we can plug it in for t, yielding the conclusion.
17

---

Under review as a conference paper at ICLR 2023
Remark 1. In the above argument, if one further assumes continuity of the (ground truth) score function and P(Y E A) = IP(Y E A) + for
p p= inf {p' > 0 BinomCDF(n, 61, [(n + 1)(1 -)] -1) < BinomCDF(n, 62 + + [(n + 1)(1 - a)] - 1)
n
then
P[(8+11 S <)) < - a.
In other words, the noise must have some sufficient magnitude in order to disrupt coverage.
Proof of Corollary ! identically equal to 1.
This consequence of the TV bound from Barber et al. (2022) with weights
Unfortunately, getting such TV bound requires case by case analysis. It's not even straightfor- ward to get TV bound under strong Gaussian assumptions.
Proposition 2 (No general TV bound), Assume Y =2) and Y y + Z. where Z o(). Then DY Y) = 1.
Proof.
2
- dr 0 1.
A2 ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS
A2.1 SYNTHETIC CLASSIFICATION ADVERSARIAL NOISE MODELS
In contrast with the noise distributions presented in Section 3.1 models to intentionally reduce the coverage rate.
here we construct adversarial noise
1. Most frequent fus ion: we extract from the confusion matrix the pair of classes with the highest probability to be confused between each other, and switch their labels until reaching total probability of In cases where switching between the most common pair is not enough to reach e, we proceed by flipping the labels of second most confused pairs of labels, and on.
2. Wrong to right: wrong predictions during calibration cause larger predictions sets during test time. Hence making the model think it makes less mistakes then actual during calibration can lead to under-coverage during test time. Here, we first observe the model predictions over the calibration set, and then switch the labels only of points that were misclassified. We switch the label to the class that is most likely to be the correct class according to the model, hence making the model think was correct. We switch a suit- able amount of labels in order to reach total switching probability of (this noise model assumes there are enough wrong predictions in order to do so).
3. Optimal adversarial: we describe here an algorithm for building the worst possible label noise for a specific model using specific non-con non-conformity score. This noise will decrease the calibration threshold at most and as result, will cause significant under- coverage during test time. To do this, we perform an iterative process. In each iteration we calculate the non-conformity scores of all of the calibration points with their current labels. We calculate the calibration threshold as in regular conformal prediction and then, from the points that have a score above the threshold, we search for the one that switching its label reduce its score by most. We switch the label of this point the label that gives the lowest score and then repeat the iterative process with the new set labels. Basically, at every step make the label swap that will decrease the threshold by most.
18

---

Under review as a conference paper at ICLR 2023
Neural network classifier
Neural network classifier
Clean
HPS
APS
Noise type
Most frequent confusion
nominal
Wrong right
Optimal adversarial HPS
Optimal adversarial APS
0.85 Coverage
0.90
1.0
1.1
1.2
1.3
Average set size
Figure AI: Effect label noise on synthetic multi-class classification data. Performance of conformal prediction sets with target coverage 1 90%. using noisy training set and noisy calibration set with adversarial noise models. Left: Marginal coverage; Right: Average size of predicted sets. The results are evaluated over 100 independent experiments.
In these experiments apply the same settings described in Section 3.1 of the main manuscript and present the results Figure AT We can see that the optimal adversarial noise causes would expect. The nost-freeuunt-conful
the largest decrease in coverage decreases the neural network coverage to approximately 89%. The wrong-to-right noise de- creases the coverage around 85% with the HPS score and around 87% with the APS score. This gap is expected as this noise directly reduces the HPS score. We can see that the optimal worst case noise for each score function reduces the coverage to around 85% when using that score. This is in fact the maximal decrease in coverage possible theoretically, hence it strengthens the optimally of our iterative algorithm.
noise
A2.2 SYNTHETIC REGRESSION: ADDITIONAL RESULTS
Here we first illustrate in Figure A2 the data we generate in the synthetic regression experiment and the different corruptions we apply.
In Section 3.2 of the main manuscript apply formance of conformal prediction using CQR score with noisy training and calibration sets. Here construct
realistic noise models and examine the per-
experiments using the settings, however train the models using clean data instead noisy data. Moreover, we apply an additional adversarial noise model that differs from those presented in Section 3.2 in the sense that it designed to intentionally reduce the coverage level.
Wrong to right: an adversarial noise that depends on the underlying trained regression model. In order to construct the noisy calibration set we switch 7% the responses as follows: we randomly swap between outputs that are not included in the interval predicted by the model and outputs that are included.
Figures A3 and A4 depict the marginal coverage and interval length achieved when applying the different noise models. We that the adversarial wrong to right noise model reduces the coverage rate to approximately 83%. Moreover, these results are similar to those achieved in Sec- tion 3.2 except for the conservative coverage attained using biased noise, which can be explained by the more accurate low and high estimated quantiles.
Lastly, in order to explain the over-coverage under-coverage achieved for some of the different noise models, as depicted in Figures B and we present Figure A5 the CQR scores and their 90%' th empirical quantile. Over-coverage is achieved when the noisy scores are larger than the clean ones, for example, in the symmetric heavy tailed case, and under-coverage is achieved when the noisy scores smaller.
19

---

Under review as a conference paper at ICLR 2023
Clean
Symmettrc heavy-tailed nokse
2.2
2.4
2.6
2.8
2.0
22
2.4
2.5
3.0
X
(a)
(b)
Asymmetric
Biased noise
-1
-1
-2
-2
2.0
22
3.0
(c)
(d)
Contractive noise
Dispersive noise
2.2
2.0
2.8
2.0
22
2.4
2.0
30
(e)
(f)
Figure A2: Illustration of the generated data with different corruptions. (a): Clean samples.
(b): Samples with symmetric heavy-tailed noise. (c): Samples with asymmetric noise. (d): Samples
with biased noise. Noise magnitude is set to 0.1. (e): Samples with contractive noise. (f): Samples with dispersive noise.
nominal
8
---- clean length
symmetric heavy-tail
Coverage
96
symmetric light-tail
Length
asymmetric
biased
92
2
0.0
0.01
0.0
0.01
1.0
Noise Magnitude
Noise Magnitude
Figure A3: Response-independent noise. Performance of conformal prediction intervals with tar- get coverage 90%, using clean training and noisy calibration set. Left: Marginal coverage; Right: Length of predicted intervals (divided by the average clean length) using symmet- ric, asymmetric and biased noise with varying magnitude. Other details Figure
20

---

Under review as a conference paper at ICLR 2023
100
90
2.5
Coverage
Length
80
2.0
60
nominal
1.5
dlean
contractive
dispersive
Wrong to right Noise
clean
contractive
dispersive
Wrong to right Noise
Figure A4: Response-dependent noise. Performance of conformal prediction intervals with tar- get coverage 90%, using a clean training set and noisy calibration set. Left: Marginal coverage; Right: Length of predicted intervals. The results are evaluated over 50 independent ex- periments.
Scores
Scores symmetric heavy-tailed noise
500
400
Geenn
noisy
400
300
4eteon
300
Qralay
200
200
100
0
-2
(a)
(b)
Scores biased noise
Scores contractive noise
500
clean
500
400
noisy
noisy
400
Aceann
Gelean
nakky
300
notey
200
200
100
-2
(c)
(d)
Figure A5: Illustration of the CQR scores. (a): Clean training and calibration sets. (b): Symmetric heavy-tailed noise. (c): Biased noise. Noise magnitude is set to 0.I. (d): Contractive noise. Other
details are as in Figure 3
A2.3 REGRESSION: AESTHETIC VISUAL RATING
Herein, we provide additional details regarding the training of the predictive models for the real world regression task. explained in Section 4.1 we trained two different models this exper- iment. The first is quantile regression model for CQR. Here we trained the model for 70 epochs using 'SGD' optimizer with batch size of 128 and an initial learning rate 0.001 decayed every 20 epochs exponentially with a rate of 0.95 and frequency of 10. We applied dropout regular- ization to avoid overfitting with rate 0.2. The second model is a classic regression model for conformal with residual magnitude scores. Here trained the model for 70 epochs using 'Adam' optimizer with a batch size of 128 and an initial learning rate of 0.00005 decayed every 10 epochs exponentially with rate of 0.95 and frequency of 10. The dropout rate in this case is 0.5.
21

---

Under review as a conference paper at ICLR 2023
1.30
clean noisy
Average size
1.25
1.20
1.15
1.10
1.05
Figure A6: Effect of label noise CIFAR-10. Distribution of average prediction sizes 30 independent experiments evaluated on CIFAR-10H test data using noisy and clean labels for calibration. Other details are in Figure T
A2.4 CLASSIFICATION: OBJECT RECOGNITION EXPERIMENT
Here we provide additional results of the classification experiment with CIFAR-IOH explained in Section 4.2 We apply conformal prediction with the APS score. The marginal coverage achieved when using noisy and clean calibration sets are depicted in Figure D Figure A6 illustrates the average prediction set sizes that are larger when using noisy data for calibration and thus lead to higher coverage level.
22


Reviews:
[{"review_id": "u7CRGAFWtpw", "reviewer": "Reviewer_tBnf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper addressed an interesting question: is conformal prediction (CP) robust to label noise? They explored several situations including both regression and classification cases. They also constructed the corresponding theories to support their claim. The authors also included experiments on both synthetic and real examples, demonstrating the robustness of conformal prediction. The paper is easy to follow, and the writing is fluent. ", "summary_of_the_review": "The topic that analyzing whether conformal prediction is trustful when label noise exists is important. Oveall, the authors provide solid study to address this question. ", "strength_and_weaknesses": "1.\tI have some concerns with the assumption of Section 2.1. The labels of images are not usually randomly corrupted. For example, dogs are often misclassified as cats, and vice versa. The confusion matrix case looks more reasonable. However, it is not supported by any theoretical results. \n\n2. The second formula in Section 2.1 involves \\hat{\\pi}_y(x), which is never mentioned before use. Similarly, I can guess the meaning of \\hat{C}_{\\rm noisy}^{\\rm APS} in proposition (1). The authors should define the notations before use.\n\n3. In Figures 1, 2, 4, and 5, there are some bars between distributions. The authors didn’t explain what they mean. The authors only mentioned the error bar in the caption of Figure 3. \n\n4. Possible typos: \n1) The second formula of section 2.1: \\hat{\\pi}_y(x)_y. The last subscript y looks redundant. \n2) The last sentence of the second last paragraph of section 3.1: \"be more robust to label noise then HPS\". Should it be \"than\"?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "gCbrzsGVnF", "reviewer": "Reviewer_mtdD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper focuses on the situation where the training data are corrupted by noise, which often happens in practice, and evaluates to what extent these nuisances affect the uncertainty quantification based on the conformal prediction. The main conclusion is that one should not worry in practical cases. ", "summary_of_the_review": "1) The reference to the probability distribution at play is quite confusing.\n   - In Equation 1, P refers to the tensorized probability over the calibration and test data.\n   - The same P is used in equation 2, however C_noisy involves the corrupted label that does not follow the same distribution\n   - The same P also defined the oracle classifier P(tilde Y | X) where no other calibration data are involved.\n\n2) Why is the assumption that access to the oracle classifier is reasonable in any way? It is not testable (oracle is never available) and this seems to be equivalent to the trained model classifying perfectly any noisy data. In that case, it seems quite natural that building a conformal prediction set based on a perfect classifier will behave perfectly. I am not sure to understand the insights/meaning of this result.\n\n3) Taking into account variation in the labels due to noise, seems to be a special case of distribution shift. How does the current contribution differ from the conformal prediction that accounts for such a shift? Also, the label noise seems to not affect a conformal set whose underlying model is invariant to slight variation in the labels. Does this relate to a conformal set based on stability assumptions? \n\n4) Some points on the Proofs.\nIn the proof of Lemma A1, the authors might want to clarify a bit formally “hat f be a classifier that ranks the classes in the same order as the oracle model” and also how is this precisely used in the proof. Seems to be in the monotonicity assumption but it is unclear and hard to follow.\nSimilarly, the proof of proposition 5 is very unclear. Y and tilde Y are discrete random variables, assuming a density for their distribution is a bit too strong here. Also, the Proposition talks about any tilde Y not equal to Y (in distribution) but the proof assumes a substantially strong hypothesis. For example, the set A can be empty depending on p and tilde p. The design of the adversarial score is also unclear: the set A is independent of the input data x (but this is ok) and also independent of any output y. Then the sequence of s(x_i, y_i) are not exchangeable (and so not valid scores) since the score is invariant wrt to the data. The rest of the proof is also very confusing.\n", "strength_and_weaknesses": "The topic of the paper is highly interesting and relevant to the AI/ML community. \nMy main concern is that the text as written is quite confusing and I am not sure I understand the significance of their results. The assumptions seem to be very strong and unverifiable, contrary to some of the (over) claims in the text. See more details below.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SkLuOLUWHx", "reviewer": "Reviewer_snZB", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies whether a coverage set is still valid under label noise. They study both regression and classification cases. Empirically, they demonstrated in some experiments that constructing coverage sets based on examples with corrupted labels is still valid as long as the noise is benign (not too adversarial). Theoretically, several noisy labeled cases are studied, for example, in 2.1, a commonly used corruption model is used to show their point, and in 2.2, a shifted noise is added for the regression model, where the noise is symmetric unimodal, e.g. standard normal. They also show in 2.4 that when noise is not benign, the coverage sets built upon noisy examples may not be valid anymore. Lastly, synthetic and real experiments are shown.", "summary_of_the_review": "See comments above.", "strength_and_weaknesses": "Strength. The writing is quite clear. The topic is interesting as corrupted labels are commonly seen in real data sets. The discussion of whether some standard techniques based on well-specified models are applicable in general to real noisy data is always appealing. \n\nWeakness. However, this paper is insufficient in several aspects:\n1. The biggest concern of mine is that this paper only presents in all positive cases, the coverage set is valid (>= 1-alpha). However, one of the most important aspects of conformal prediction is to show the tightness of the coverage. One can always return a valid coverage set by applying a trivial one. One missing part is the analysis of how much the noise inflated the coverage set.\n\n2. The second concern of mine is that the theoretical results are built upon a very simple noise mechanism. For instance, the unimodal assumption is kind of strong. Also, the assumption on Z is not very commonly seen, more explanation is appreciated.\n\n3. The empirical result on real data is too simple. More datasets in large scale should be discussed. \n\n4. One minor point, in practice, domain shift is also commonly seen. It would be interesting to see some discussion on that.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AgV1nLy_qqp", "reviewer": "Reviewer_DjSE", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the robustness of conformal prediction to label noise, characterizing when and how it is possible to construct uncertainty sets that correctly cover the unobserved noiseless ground truth labels.", "summary_of_the_review": "The idea of studying the robustness of conformal prediction to label noise is relatively novel. However, The paper does not provide much explanation for how the findings in this paper can be applied to existing noise-label learning methods. Moreover, the adopted datasets are relatively small.", "strength_and_weaknesses": "Strength: This paper studies a very important problem and tries to provide some theoretical results about the label noise learning tasks.\n\nWeakness: The paper does not provide much explanation for how the findings in this paper can be applied to existing noise-label learning methods.\nThe adopted datasets are relatively small, there are real-world noise datasets such as Clothing1M and Webvision that are widely used for noisy label learning but are not adopted in this paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject