Provably Reliable Conformal Prediction Sets in the Presence of Data Poisoning
Authors: Yan Scholten
Stephan Günnemann
Venue: ICLR 2025 Spotlight (2025)
Keywords: Conformal prediction
Certifiable robustness
Adversarial robustness
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: We propose the first efficient method for making conformal prediction sets more reliable against data poisoning and label flipping attacks.

Abstract: Conformal prediction provides model-agnostic and distribution-free uncertainty quantification through prediction sets that are guaranteed to include the ground truth with any user-specified probability. Yet, conformal prediction is not reliable under poisoning attacks where adversaries manipulate both training and calibration data, which can significantly alter prediction sets in practice. As a solution, we propose reliable prediction sets (RPS): the first efficient method for constructing conformal prediction sets with provable reliability guarantees under poisoning. To ensure reliability under training poisoning, we introduce smoothed score functions that reliably aggregate predictions of classifiers trained on distinct partitions of the training data. To ensure reliability under calibration poisoning, we construct multiple prediction sets, each calibrated on distinct subsets of the calibration data. We then aggregate them into a majority prediction set, which includes a class only if it appears in a majority of the individual sets. Both proposed aggregations mitigate the influence of datapoints in the training and calibration data on the final prediction set. We experimentally validate our approach on image classification tasks, achieving strong reliability while maintaining utility and preserving coverage on clean data. Overall, our approach represents an important step towards more trustworthy uncertainty quantification in the presence of data poisoning.

Published as a conference paper at ICLR 2025
PROVABLY RELIABLE CONFORMAL PREDICTION SETS IN THE PRESENCE OF DATA POISONING
Yan Scholten, Stephan Günnemann
Department of Computer Science & Munich Data Science Institute Technical University of Munich {y. sy.scheleen, 8. guennemann e @etmm.dc de
ABSTRACT
Conformal prediction provides model-agnostic and distribution-free uncertainty quantification through prediction sets that are guaranteed to include the ground truth with any user-specified probability. Yet, conformal prediction not reliable under poisoning attacks where adversaries manipulate both training and calibra- tion data, which can significantly alter prediction sets in practice. As a solution, we propose reliable prediction
(RPS): the first efficient method for construct- ing conformal prediction sets with provable reliability guarantees under poisoning. To ensure reliability under training poisoning, we introduce smoothed score func- tions that reliably aggregate predictions of classifiers trained on distinct partitions of the training data. To ensure reliability under calibration poisoning, construct multiple prediction sets, each calibrated on distinct subsets of the calibration data. We then aggregate them into a majority prediction set, which includes a class only if it appears in majority of the individual sets. Both proposed aggregations mit- igate the influence of datapoints in the training and calibration data on the final prediction set. We experimentally validate our approach image classification tasks, achieving strong reliability while maintaining utility and preserving cov- erage clean data. Overall, our approach represents important step towards more trustworthy uncertainty quantification in the presence of data poisoning.'
INTRODUCTION
Conformal prediction has emerged as powerful, -odel-agnostic framework for distribution-free uncertainty quantification. By constructing prediction sets calibrating hold-out data, it transforms any black-box classifier into a predictor with formal coverage guarantees, ensuring its prediction sets cover the ground truth with any user-specified probability (Angelopoulos & Bates, 2021). This makes highly relevant for safety-critical applications like medical diagnosis (Vazquez & Facelli, 2022), autonomous driving (Lindemann et al., 2023), and flood forecasting (Auer et al., 2023).
However in practice, noise, incomplete data or adversarial perturbations can lead to unreliable pre- diction sets (Liu al., 2024). In particular data poisoning where adversaries modify the training or calibration data (e.g. during data labeling) can significantly alter the prediction sets, resulting in overly conservative or empty sets (Li et al., 2024). This vulnerability can undermine the practical utility of conformal prediction in -afety-critical applications, raising the research question:
How can we make conformal prediction sets provably reliable in the presence of data poisoning?
As solution, we propose reliable prediction sets (RPS): the first efficient method for constructing prediction sets more reliable under data poisoning where adversaries can modify, add and delete dat- apoints from training and calibration sets. Our approach consists of two key components (Figure I): First (i), we introduce smoothed score functions that reliably aggregate predictions from classifiers trained on distinct partitions of the training data, improving reliability under training poisoning. Sec- ond (ii), we calibrate multiple prediction sets on disjoint subsets of the calibration data and construct majority prediction set that includes classes only when majority of the independent prediction sets agree, improving reliability under calibration poisoning. Using both strategies (i) and (ii), RPS effectively reduces the influence of individual datapoints during training and calibration.
Project page: https:/ /wwww//wwwoooooo///.oo ci t.. t.m.mm den.de//ann /rel i aabl con formal 1 -predi prediction in

---

Published as a conference paper at ICLR 2025
(i) Reliable CP under training poisoning
(ii) Reliable CP under calibration poisoning
Train
[i(x)
Smoothed score
Calibrate
Ci(x)
Majority prediction set
Test image
Training partitions
+ fi
squiree!
function
Calibration part.
Pi
[squiree)
P2 + J22 cur
18 29
Pa
+
{marmot, squireef}
(Mr(x)
P3 f
marmot
P3 T
(ear, (carmmarmot)
(qqiirel)
squirel
marriot
+ squiree!
Pc TT (spurred)
Figure 1: Conformal prediction (CP) is not reliable under poisoning (orange) of training and calibra- tion data, undermining its practical utility in safety-critice applications. As solution, propose reliable prediction sets (RPS): A novel approach for constructing more reliable prediction sets. We (i) aggregate predictions of classifiers trained distinet partitions, and (ii) merge multiple predic- tion sets (y sz y) 2 J calibrated on separate partitions into majority prediction set that includes classes only if a majority of the prediction sets C, agree. This way RPS reduces the influ- ence of datapoints while preserving the coverage guarantee of conformal prediction on clean data.
We further derive certificates, i.e. provable guarantees for the reliability of RPS under worst-case poi- soning. We experimentally validate the effectiveness of our approach image classification tasks, demonstrating strong reliability under worst-case poisoning while maintaining utility and empiri- cally preserving the coverage guarantee of prediction sets on clean data. Our main contributions are:
We propose reliable prediction (RPS) the first scalable and efficient method for making conformal prediction more reliable under training and calibration poisoning.
We derive novel certificates that guarantee the reliability of RPS under worst-case data poisoning
attacks, including guarantees against label flipping attacks.
We thoroughly evaluate our method and verify our theorems on image classification tasks.
2 RELATED WORK
Prediction set ensembles. Ensembles of prediction sets are studied in the uncertainty set litera- ture beyond machine learning (Cherubin, 2019; Solari & Djordjilović, 2022; Gasparin & Ramdas, 2024), e.g. to reduce the effect of randomness. Our work instead proposes method to improve the reliability of conformal prediction under worst-case training and calibration poisoning.
Conformal prediction under evasion. Most works regarding reliable conformal prediction focus on evasion threat models, i.c. adversarial perturbations of the test data. They typically build upon randomized smoothing (Cohen et al., 2019) to certify robustness against evasion attacks (Gendler et al., 2022: Yan et al., 2024; Zargarbashi et al., 2024), or use neural network-specific verification (Jeary et al., 2024). Ghosh al. (2023) introduce a probabilistic notion an alternative to worst- case evasion attacks. Unlike prior work on evasion, we consider poisoning threat models.
Conformal prediction under poisoning. Despite emerging poisoning attacks (Li al., 2024), the few existing attempts to improve reliability consider other reliability notions. Most works only cer- tify the coverage guarantee under calibration poisoning (Park et al., 2023; Zargarbashi et al., 2024; Kang et al., 2024). Others study calibration poisoning empirically (Einbinder et al., 2022), under specific label noise (Penso & Goldberger, 2024), consider distribution shifts between calibration and test data (Cauchois et al., 2020). Zargarbashi et al. (2024) consider modifications to the cali- bration data, but their threat model does not support adversarial data insertion or deletion. Overall, none of the existing approaches considers pointwise reliability of prediction sets under threat models where adversaries can modify, add or remove datapoints from both training and calibration data.
Robustness certification against data poisoning. Most certification techniques for robust classi- fication under poisoning consider other threat models, specific training techniques or architectures (Rosenfeld et al., 2020; Tian et al., 2023; Sosnin et al., 2024). The strongest guarantees also partition the training data and aggregate predictions of classifiers trained on each partition (Levine & Feizi, 2021: Wang et al., 2022; Rezaei al., 2023). However, all of the prior works only guarantee robust classification and are not directly applicable to certify conformal prediction since prediction sets (1) contain multiple classes, and (2) can be manipulated via poisoning during training and calibration.
2

---

Published as a conference paper at ICLR 2025
3 BACKGROUND AND PRELIMINARIES
We focus on classification tasks defined on an input space X R for a given finite set of classes
)' (1..... :.). We model prediction set predictors functions C X - 2", which provide prediction sets as subsets C(x) S y' of the classes y for any given datapoint x E X.
Exchangeability. Conformal prediction is model-agnostic and distribution-free method for con- structing prediction sets. It only requires that calibration and test points are exchangegable, which means that their joint distribution is invariant under permutations. In this paper, we adopt the stan- dard assumption (e.g. in image classification) that datapoints are i..d.. which implies exchangeabil- ity. Specifically, we assume three datasets with datapoints sampled i.idd from the same distribution D over X' x Y: training set Dirain, calibration set Deatib (( V/ ) and test set Drest-
Conformal prediction. Conformal prediction transforms any given black-box classifier : - y into a prediction set predictor. We focus on split conformal prediction (Papadopoulos et al., 2002; Lei et al., 2018), the most widely used variant in machine learning. First, one trains a classifier on the training set and defines score function s(x, y) that measures conformity between samples x and classes y. For example, homogeneous prediction sets (HPS) use the class probabilities of a given soft classifier, sz, y) fy (a:) (Sadinle et al., 2019). Then, computes conformal scores S=(s(x; ys)) for samples of the calibration set Dealib using the score function s. Finally, one construct prediction sets with the following coverage guarantee (Vovk et al., 1999; 2005):
Theorem 1. Given user-specified coverage probability 1 1-c a E (), test sample (In+1, 9x+1)) E Drest exchangeable with Dealsh, and score function s, we can construct the following prediction set
C(In+1) = {y E EV: s(En-1. v) 2 T)
which fulfills the following marginal coverage guarantee
Prlys+1 E C(In+1)) 21-a
for T = Quant( an S). Specifically, the threshold I is chosen as the an -quattile of the conformal scores S for a fmitte-smmpl corrected significance level on [a(n 1) 1j/n.
4 DESIDERATA FOR RELIABLE CONFORMAL PREDICTION
First we want to outline the desired properties that reliable conformal prediction should exhibit, setting clear goals for how uncertainty should be captured by prediction sets under data poisoning.
Data poisoning. While exchangeability may hold for the data distribution D in theory, the labeled data Di- = (D train Deats)) can be poisoned to alter prediction sets practice. We formalize this threat model, i.c. the strength of poisoning attacks, ball centered around labeled data:
Brar. (D:) = [Di 8(Dirain. Dirain) I T₁, 8(Dcatib Deats)) S {re}
(1)
where 8 is a distance metric between datasets, and rz, To are the radii for training and calibration sets, respectively. Specifically, we define as the number of inserted or deleted datapoints and label flips, modeling feature modification
two perturbations (deletion and insertion): 8(D1, D2)
[Di e D21 - [F(D, D2)1 where A e B (A \ B) U (B \ A) is the symmetric set difference between sets A and B, |S| denotes the cardinality of set S. and F(D,, D2) represents the set of datapoints with label flips F(D,, (2)=(x 3y (z. y1 y1 Di \ D2, 3y (æ, U2)E D2 D1)- }- Note that we count label flips only once, and feature perturbations can be of arbitrary magnitude.
Reliability under data poisoning. Given a datapoint x E X' and a prediction set C(x) C y, we define reliability of conformal prediction sets under data poisoning follows:
Definition 1 (Reliability). We assume that reliability is compromised if adversaries can remove or add a single class from or to the prediction set C(x) under our threat model (Equation 1). Specif- ically, we call prediction sets coverage reliable if adversaries cannot shrink prediction sets C(x) by removing classes, and size reliable if adversaries cannot inflate prediction sets C(x) by adding classes. We further call coverage and size reliable prediction sets robust.
Note that while the coverage guarantee (Theorem 1) provides a marginal guarantee over the entire distribution, our notion of coverage reliability is pointwise, i.e. applies to each prediction set C(x)).
3

---

Published as a conference paper at ICLR 2025
Accordingly, we propose the following novel desiderata for reliable conformal prediction:
Desiderata for reliable conformal prediction under data poisoning
I:
Reliable conformal prediction must provide marginal coverage (Theorem 1) for clean data.
II: Reliable prediction sets must be small (comparable to sets without reliability guarantees), III: Reliable conformal prediction must provably ensure reliability of prediction sets (Defini- tion 1) under data addition, deletion, modification and label flipping (Equation 1) up to a radius that meets the application's 's needs and safety requirements.
IV: Algorithms for constructing reliable prediction sets must be flexible enough to allow for increased reliability given larger training and calibration sets.
Algorithms for constructing reliable prediction sets and their guarantees must be compu- tationally efficient, scalable, and reproducible.
While desideratum I requires marginal coverage (Theorem 1), desideratum II ensures small sets, and together they prevent that reliability can be achieved trivially by predicting empty or full sets. desideratum III ensures that reliability must be certifiable, i.e. provable guarantee under worst-case poisoning. desideratum IV requires that algorithms can increase reliability as more data becomes available since practical risks often increase with more data. Finally, desideratum V ensures effi- ciency in deployment, where reproducibility requires stability under recomputation.
5 RELIABLE CONFORMAL PREDICTION SETS
Guided by our desiderata for reliable conformal prediction we introduce reliable conformal predie- tion sets (RPS): the first method for provably reliable conformal prediction under training and cal- ibration poisoning (Figure 1). The first component of RPS (i) reliably aggregates classifiers trained on kt disjoint partitions of the training data. The second component of RPS (ii) constructs reliable prediction sets by merging sets calibrated separately on k. disjoint partitions of the calibration data. Intuitively, larger k; increases reliability against training poisoning and larger ke increases reliability against calibration poisoning. We provide detailed instructions in Algorithm and Algorithm 2.
5.1 CONFORMAL SCORE FUNCTIONS RELIABLE UNDER TRAINING DATA POISONING
First, our goal is to derive a conformal score function that is reliable under poisoning of training data. This is challenging since the score function also has to quantify agreement between samples and classes, and maintain exchangeability of conformal scores between calibration and test data. To overcome this challenge we propose to (1) partition the training data into he disjoint sets, (2) train separate classifiers each partition, and (3) design a score function that counts the number of classifiers voting for a class given sample æ. Since deleting or inserting one datapoint from or into the training set only affects single partition and thus a single classifier, this procedure effectively reduces the influence of datapoints on the score function.
Training data partitioning. To prevent that simple reordering the datasets affects all partitions simultaneously, we have to partition the training data in a way that is invariant to its order. To achieve this we assign datapoints to partitions by using a hash function directly defined on r. For example for images, we use the sum of their pixel values. This technique that has been previously shown to induce certifiable robustness in the context of image classification (Levine & Feizi, 2021). Given a deterministic hash function / X + Z we define the i-th partition of the training set
p { my) Derasn h(z,) (mod kt))
Then we deterministically train k, classifiers f(6) X + y' on all partitions Pf...., Pt, separately.
Smoothed score function. Now we define our score function that measures agreement between sample x and class by counting the number of classifiers f()) voting for class y given x::
(x)
k. (x)(())=)))
s(x, v)
with xy(x)) K4 Σ
DE (.)
where (x)x)) is the percentage of classifiers voting for class y given sample x, and K is the number of classes. Note that we introduce the additional softmax over class distribution xt <<x) to prevent overly large prediction sets in practice (desideratum II, see Section 7).
4

---

Published as a conference paper at ICLR 2025
Algorithm 1 Reliaale conformal score function
Algorithm 2 Reliable conformal prediction sets
Input: Divaen, kt. deterministic training algo. T
Input: D Panksb hes S, a, 2n+1
I: Split Dtrain into by disjoint partitions P.
1: Split Peatá into he disjoint partitions P.
P { yj) DDirainn h(xx)) (mod k)}
P. = {(zz V/
Deote' l((2;) = i (mod ke))
2: for to do
2: for i = to k. de
3: Train classifier f T(P:) on partition P.
3: Compute scores S,=(s(2); V/) ke) ge
4: Compute On, -quantile т, of scores S,
4: Construct the voting function
5: Construct prediction set for quantile 7
(2(2))= 1,
ke Σ (1 (z) y}
C((Ia+1) = {y s y) 2 7
5: Smooth the voting function
6: Construct majority vote prediction set
s(a, 3) = <-((x)/ /(E ())())
C (fm+1)= E. { ((reCC((n++))) > ((a))
Output: Reliable conformal score function 8
Output: Reliable conformal prediction set CM
For any function to be considered a valid score function for conformal prediction it has to maintain exchangeability of conformal scores between calibration and test data (Angelopoulos et al., 2021). Lemma 1, The smoothed score function in Equation 2 is a valid conformal score function.
Proof. We one function score all points independent of other datapoints and which dataset they belong to (and where in the dataset). Thus, given exchangeable data, scores computed by our smoothed score function remain exchangeable. Therefore of Equation 2 a valid score function. D
Lemma implies that the coverage guarantee (Theorem 1) holds on clean data when using our smoothed score function (desideratum I). Intuitively, our score function quantifies uncertainty by the number of votes from multiple classifiers (instead of the logits of one classifier). As long as clas- sifiers are trained on isolated partitions we can reduce the influence of datapoints on the conformal scores. We summarize instructions for the smoothed score function in Algorithm 1.
5.2 MAJORITY PREDICTION SETS RELIABLE UNDER CALIBRATION DATA POISONING
Now we derive prediction sets reliable against calibration poisoning. This is challenging since the prediction sets must also achieve marginal coverage clean data (desideratum I) without inflat- ing set size (desideratum II). We propose to (1) partition the calibration data into he disjoint sets, (2) compute separate prediction sets based on the conformal scores on each partition, and (3) merge the resulting prediction sets via majority voting. This improves reliability since adversaries have to poison multiple partitions to alter the majority vote. We further show that such majority prediction sets achieve marginal coverage, and do not grow too much in size in practice (Section 7).
Calibration data partitioning. We partition the calibration data as follows: Given hash function h we define the i-th partition of the calibration set as P = ((T)) yj) E Deeath : h(T,) = i (mod k.) }- We then use (potentially reliable) conformal score function (;=(s(a,, 8;) (z) WE on each partition P.S. We can then determine the On, -quantiles of the separate conformal scores, = Quant(a,,; S,),, where n. is the size of the i-th partition, n, = |P
compute the conformal scores
Majority prediction sets. Now we propose prediction sets, which are provably reliable under cal- ibration poisoning. Given a new datapoint In+1 E Drest we construct he prediction sets for each partition (Ix+1) = {y : s(xx+1.1) 1)) 2 ) We then construct a prediction set composed of all classes that appear in the majority of independent prediction sets (see instructions in Algorithm 2):
(
kc My E C,(x++1)) > f(a)
C (M(+1)1)
y Σ
(3)
with quantile function +(a:) max fxr E [ < a} for [kc] (o.... inverse of the CDF F of the Binomial distribution Bin(ke, 1-a) Intuitively, we select the required majority + +(a) such that the sum over k. Bernouli random variables 1 E C((xn+1)) (each with success probability at least 1 (v) at most F(a) with probability at most a. Note that for k.
(o,...,,k.),,.... kc), where f(a) is the
we have f(a) 0, for which CM amounts to vanilla conformal prediction. Notably, such majority prediction sets achieve marginal coverage on clean data (Proof in Appendix D):
Theorem 2. Given any conformal score function and test sample (In+1, Vn+1) E Dtest exchange- able with D Deatih. the majority prediction set (Equation 3) constructed from sets calibrated on disjoint partitions- achieves marginal coverage on clean data: Pr(yn+ E CM (In+1)) 1 1-a.
5

---

Published as a conference paper at ICLR 2025
Proof sketch. Since each prediction set C, fulfills marginal coverage, Pr(y Cx(2++1)] 1 a, the probability of the sum over Bernoulli random variables 1 [3n+11 E (2 1) being larger than +(a) is at least 1 a (due to the selection of (())). Thus we have Pr[yn-1 E C (2n+1)) ) 2 o.
Note that majority voting is also used in the context of merging uncertainty sets (Gasparin & Ram- das, 2024), but their approach comes without reliability guarantees (see discussion in Appendix D). Importantly, Theorem 2 guarantees marginal coverage for any conformal score function. This holds especially for our smoothed score function (Equation 2). As consequence, majority prediction sets based on the smoothed score function achieve marginal coverage (desideratum I).
6 PROVABLE GUARANTEES FOR RELIABLE CONFORMAL PREDICTION SETS
After introducing reliable prediction sets (RPS), we derive certificates for their reliability as defined in Definition and required by desideratum III. We consider the threat model Br..,. (D:) where ad- versaries can insert, delete and flip labels for up to r, training and re calibration points (Section 3). In the following treat training poisoning, then calibration poisoning, and finally poisoning of both.
6.1 GUARANTEES FOR SMOOTHED SCORING FUNCTION UNDER TRAINING POISONING
We begin with the reliability of the smoothed scoring function under training poisoning (r, r)= Let C(r,,+ )- E 8(1,+1 1: y) 2 } be prediction set for using conformal prediction (Section 3) under the clean dataset DD with smoothed score function 8.
test point x derived
Our goal is to bound the prediction set C(x.+1) derived under any poisoned dataset Dj E Br. This requires that we bound score function s and quantile т. We start with the score function:
Lemma 2.
We can upper bound the score function for any Dj Br..r as follows:
3(0, v)
max USTIS (, - I4
with
[ (x) + ........ +x(2++Ax))
(4)
Di=1 T
E, A,=0
Proof in Appendix E. Although optimizing softmax func- tions typically leads to non-convex optimization problems, the problem in (4) reduces to a discrete optimization prob- lem that be solved efficiently (desideratum V). We derive algorithms computing lower and upper bounds in rz steps, presenting the upper bound in Algorithm 3. In- tuitively, in each step we greedily redistribute i, probability mass from the current class ÿzy with the largest probability
Algorithm 3 Greedy algorithm for upper bounding the smoothed score function
Input: Score function s, x. y, k2, Ft.
1: [m (x),...... TT (x))
2:
1
do
3:
ÿ = argmax, juyy Tg
4:
Hg f min(max((e)) 77 1 1/k2, 0), 5: My +- minnmmax(rr) + k2, 0),
mass to the target class y. We repeat this process until we have redistributed the entire probability mass "t We present the lower bound algorithm and proofs in Appendix E.
Output: 3(x, /( eT
Given lower and upper bounds z; 2(x;, vi) and य = s(1i, yi) on the conformal scores for all points (I4, yi) E Dentib in the calibration set, we can directly determine the worst-case quantiles:
Quant(a,: (=))
== =uuant(a;, {-))
Finally we need to identify (1) the class within the prediction set that received the fewest votes from
the classifiers (6) and (2) the class outside the prediction set that got most votes from the classifiers:
argmin (z(x))
argmax TTyxx)
vEC(#n+1)
Then we can provide the following guarantees (Proof in Appendix E):
Theorem 3. Given r.=0, the conformal prediction set ((r+1) derived with the smoothed score function under any poisoned dataset Drerrr is coverage reliable, i.e. ((xx+1) 2 C(In41), if 8 ( y) 2 F, and size reliable, i.e. C(xn+1) C C(xn+1), if (x, <I.
Intuitively. if class y cannot be removed from C(zn+1) (y added), adversaries cannot remove (add) any other class and thus the prediction sets are coverage (size) reliable.

---

Published as a conference paper at ICLR 2025
6.2 GUARANTEES FOR MAJORITY PREDICTION SETS UNDER CALIBRATION POISONING
Now we analyze reliability of our majority prediction sets under calibration poisoning (r:=0, ro>0). Let Cad (In+1) be the majority prediction set for new test point In+1 derived under the clean dataset Dj using any deterministic conformal score function s. Intuitively. if adversaries cannot remove (add) a class from the majority prediction set by removing (adding) it from (to) re individual prediction sets, the majority prediction set remains coverage (size) reliable even in the worst case. This is since adversaries can perturb at most r. calibration partitions under our threat model. To determine whether adversaries can remove or add classes, we have to count minimum and maximum i=1
support Σド= 1 E (z(xn+1)) for classes in and outside of the majority set:
Ai iy ((
m
min VECR
m
max DECM
Σ 1 E (((nt))
Using each support we can provide the following guarantees (Proof in Appendix E):
Theorem 4. Given r==0 and deterministic score function s. the majority prediction set CM (In+1) derived under any dataset Di E Br. (Di) is coverage reliable, i.e. CM (In+1) 2 CM (In-1); ) if m - Te > f(a), and size reliable, i.e. CM (In-1) C CM (In+1). if m + Ta I f(a). provided that the smallest calibration partition it is large enough P -
rr 11.
Note that the last condition ensures that the calibration partitions large enough such that worst- case adversaries cannot delete datapoints to prevent us from computing the majority prediction sets.
6.3 PROVABLE RELIABILITY GUARANTEES FOR RPS UNDER GENERAL DATA POISONING
Finally, we consider poisoning of training and calibration data (ry > 0, re > 0).
Coverage reliability. To ensure coverage reliability we have to show that all classes E C.M are guaranteed to be in the majority prediction set under worst-case poisoning. The majority prediction set CM contains class y only if it appears in majority of f(x) individual prediction sets C. Under calibration poisoning, adversaries can remove classes from T. individual prediction sets. Intuitively, the number of prediction sets reliable under training poisoning By must be large enough such that even under calibration poisoning, the number of prediction sets containing the class is still larger than the threshold, By re > (o:). This leads to the following guarantee (Proof in Appendix E):
Theorem 5. Let By denote the number of prediction sets C, (CI....,Cuy for which we can guarantee y E C, under re poisoned training datapoints. If By -re >> +(aa) for all E CM (In+1) then the majority prediction set coverage reliable under any dataset Dr E Brire(Di) provided that the smallest calibration partition i" is large enough 1--1-re- re ( 1).
Size reliability. To ensure size reliability we have to show that all classes y & C.M are guaranteed to stay outside of the majority prediction set under worst-case poisoning. The majority prediction set CM does not contain a class y if it appears in less than or equal to f(a)) individual prediction sets C. Under calibration poisoning adversaries can add classes r. prediction sets in the worst-case. Intuitively, if we can guarantee that Ty prediction sets C₂ do not contain the class y under training poisoning, most hig Ty prediction sets contain the class under worst-case training poisoning. This number of prediction sets containing the class in the worst-case must be small enough such that even if adversaries add the class to Te prediction sets, the majority prediction set does not contain the class, he -y + rc S f(a). This leads to the following guarantee (Proof in Appendix E):
Theorem 6. Let "ty denote the number of prediction sets C, E (CI,..., C,. for which we can guarantee y & C, under Tı poisoned training datapoints. Ifke-Ty+r S for all & CM (In+1) then the majority prediction set is size reliable under any dataset Dt E Br.r. (Di), provided that the smallest calibration partition i" is large enough |P 1 re _ 1).
Note that we can efficiently compute numbers 3, and Ty as described in Subsection 6.1 by comput- ing the worst-case quantiles and verifying v) F and 5(x, y) < т. respectively. Our overall certification approach is efficient in practice (desideratum V) as we discuss in Appendix E and ex- perimentally demonstrate in the next section.

---

Published as a conference paper at ICLR 2025
7 EXPERIMENTAL EVALUATION
In this section we evaluate our reliable prediction sets and their worst-case guarantees, demonstrating their effectiveness in analyzing and improving reliability of conformal prediction under poisoning. We compare three settings (calibration poisoning, training poisoning, and poisoning of both) by computing the following prediction sets: (a) majority prediction sets merging multiple homogeneous prediction sets calibrated on each partition, (b) conformal prediction sets using our smoothed score function, and (c) majority prediction sets using our smoothed score function.
Datasets and models. We train ResNet18, ResNet50 and ResNet101 models (He et al., 2016) on SVHN (Netzer al., 2011), CIFARIO and CIFARI00 (Krizhevsky et al., 2009). The datasets contain images with 3 channels of size 32x32, categorized into 10, 10 and 100 classes, respectively. Unless stated otherwise, we show results for R8 on CIFARIO and coverage level 1 - a 0.9 in this section and provide additional experimental results in Appendix B.
Experimental setup. We randomly select 1,000 images of the test set for calibration and use the remaining 9,000 datapoints for testing. To account for randomness in model initialization and cali- bration set sampling, we train 5 classifiers with different initializations and validate each of them on 5 different calibration splits. We report mean and standard deviation (shaded areas in the plots). We refer Appendix A for the full experimental setup including detailed reproducibility instructions.
Evaluation metrics. We report three reliability ratios: The ratios of test datapoints whose prediction sets are, according to our worst-case analysis, coverage reliable (classes cannot be removed), size reliable (classes cannot be added), or robust (classes cannot removed or added). Empirical coverage refers to the ratio of datapoints whose prediction sets cover the ground truth label of the test set. We also report the average size of the prediction sets computed on the test set.
(b)
Reliab. ratio (%)
Reliab. ratio %
robust
robust
75
75
coverage reliable size reliable
Reliab. ratio
75
covenge relisble
size reliable
50
cinverage roliable
rehost
50
25
size reliable
25
25
5
2
10
Calib. set radius re
Training set radius rt
Poisoning radius To Te
Figure 2: Worst-case reliability guarantees across three scenarios: (a) poisoning of the calibration
data, (b) poisoning of the training data, and (c) poisoning of both datasets. Our guarantees against coverage attacks are stronger when training data is poisoned, whereas for calibration attacks our method offers stronger guarantees for size reliability. Notably, even under strong adversarial condi- tions where both datasets can be poisoned we still provide non-trivial reliability guarantees.
(a) Reliability of majority prediction sets under calibration poisoning. Majority prediction sets demonstrate strong reliability guarantees against calibration set poisoning in empirical evaluations (Figure 2 a). Specifically, we construct majority prediction sets by merging k2=22 homogencous prediction sets, each calibrated on separate calibration partitions, resulting in an empirical coverage of 90.2% and an average set size of 0.94. When up to r datapoints in the calibration set are poisoned, our method guarantees that over 93% of the prediction sets remain reliable against worst- case coverage attacks. The guarantees against set size attacks are even stronger: Even if r.=15 datapoints are poisoned we still guarantee that over 87% of the prediction sets remain size reliable.
(b) Reliability of smoothed score function under training poisoning. The setting of training set poisoning is considerably more challenging since adversaries can simultaneously manipulate the quantiles during calibration and the scores at inference. We compute conformal prediction sets using our smoothed score function on k; 100 training partitions, resulting in empirical coverage of 90.7% and average set size of 3. 18 (Figure b). Despite strong adversaries, our reliable prediction sets still manage to provide non-trivial reliability guarantees under worst-case perturbations. Specifically, when up to r. = 4 datapoints in the training set are poisoned, our method guarantees that over 34% of the prediction sets remain reliable against worst-case coverage attacks.
8

---

Published as a conference paper at ICLR 2025
(c) Reliability of RPS under training and calibration poisoning. By far the most challenging set- ting constitutes adversaries that manipulate both training and calibration data. We compute majority prediction sets using our smoothed score function on =000 training partitions and k==40 cali- bration partitions, resulting in empirical coverage of 92% and average set size of 3.41 (Figure c). Notably, under poisoning of up Ft 3 training and re = calibration points, our method still guarantees that over 31 % of the prediction sets remain reliable against worst-case coverage attacks.
(b)
Avg. set size
Avg. Set size
Avg. set size
3
a=d.1
20
10
20
10
20
Number of partitions k
Number of partitions kre
Num. partitions hs = kc
Emp. coverage
Emp. coverage
Emp. coverage
95
95
95
90
90
90
0.05
10
15
20
10
20
10
15
20
Number of partitions ke
Number of partitions
Num. partitions ky kc
Figure 3: Average set size and empirical coverage in all three different experiment settings (a-c).
Notably, our reliable prediction sets yield valid coverage guarantees without becoming too large.
Average set size. In Figure 3 (top row) we study the average set size. Notably, our majority predic- tion sets yield strong guarantees (Figure 2 a) without any significant increase in size (Figure 3 a): the average prediction set size remains below 1, which even holds for 42=40 (a=0.1). Interestingly, the size increases with more training partitions, creating tade-off between reliability and utility of the prediction sets. Practitioners have to fine-tune this trade-off depending on the application' 's sensi- tivity. Additionally, we study set sizes different datasets under calibration poisoning (setting (a)): On CIFAR100 the average set size remains below for Kc < 26, demonstrating that our majority prediction sets scale well to datasets with more classes (Figure 4 (1)). Overall, we empirically find that our reliable prediction sets do not become too large in size (desideratum IT).
Empirical coverage. In Figure 3 (bottom row) empirically validate the coverage guarantee (Theorem 2) on clean data (desideratum I). In Subsection B.1 we provide additional empirical evi- dence that, while concentration around the nominal level 1 a naturally decreases for smaller sets, majority prediction sets are again closely concentrated around the nominal coverage level.
Minimal number of classifiers. We observe increasing empirical coverage and sizes when using only 22= or 3 classifiers (spikes in Figure 3). Intuitively, a small number of classifiers makes the smoothed score function less stable during calibration. In practice, sufficient number of classifiers is required to achieve consistent majority vote consensus and reliability. Notably, our analysis shows that four classifiers are already sufficient to prevent excessively large prediction sets.
Softmax ablation study. We found that smoothing the voting function with a softmax (Section 5) avoids overly large prediction sets and overcoverage practice. To demonstrate this we conduct an experiment (Figure 4 (2, 3)) for varying numbers of training partitions k, where we compare conformal prediction with our smoothed score function s against using the voting function æ only.
Computational efficiency. Training the classifiers takes most of the time (statistics in Appendix A). Note, however, that while having to train more classifiers, each one is trained on a subset of the training data, which can speed up the training process. Inference with the ResNet18 models takes between 2 and 10 seconds on CIFAR10. Constructing the conformal prediction sets takes at most 0.5 seconds for the entire test set. Computing certificates for majority prediction sets takes less than a second, and around one minute when computing guarantees under training and calibration poison- ing. Overall, found that reliable prediction sets are computationally efficient (desideratum V).

---

Published as a conference paper at ICLR 2025
(I)
Avg. set size
Emp. coverago
Avg. set size
7
withoott softmax
CIFARIOO CIFARIO
95
SVHN
sothmax
90
5
15
20
10
20
10 15
20
Num. partitions KG ke
Num. partitions k kc
Num. partitions k2
ke
Figure 4: (I): Average prediction set size of majority prediction sets across three different datasets.
(2,3): Softmax ablation study for empirically justifying smoothing of the voting function (a 0.05).
DISCUSSION
Reproducible prediction sets. Score functions in the literature are not just unreliable but some also depend randomization to break ties (Romano al., 2020). While randomization at inference changes prediction sets by at most one class (Angelopoulos et al., 2021), different prediction sets for the same input may not be desirable from reliability standpoint, violating desideratum V. For example, a differential diagnosis for two patients with identical health should not yield different results. As remedy, we propose to make randomized score functions reproducible (Appendix C).
Limitations. Although RPS computationally scales to larger settings, training on subsets of larger datasets such as CIFAR or ImageNet comes with accuracy loss, which also affects the utility of our smoothed score function (details in Appendix B). This accuracy loss is an open challenge in the general certifiably robust classification literature and beyond the scope of this paper.
Minimal calibration set size for majority prediction sets. Recall that desideratum VI requires that the reliability of prediction sets must increase for larger calibration sets. Our majority prediction sets fulfill this desideratum by construction since increasing the number of partitions k. will decrease the influence of datapoints. However, we need enough data to construct our prediction sets: due to the sample correction, the calibration partitions cannot become arbitrarily small. If the hashing function would distribute all calibration images into equally-sized partitions of size n/ke, we would need at least n 2 ke ( - 1) calibration points in total (Proof in Appendix D). Notably, this relationship is linear: given fixed coverage probability of 1 - increasing the calibration partitions by a factor of only requires k-times larger calibration sets, which realistic for all commonly used image classification datasets and coverage probabilities used in the literature.
Training poisoning discussion. Under the assumption exchangeability, adversarics cannot com- promise the coverage guarantee of Theorem by poisoning training data. This holds because confor- mal scores are computed using a fixed classifier (post-training). However, in practice, the exchange- ability assumption may not always hold: Adversaries could exploit knowledge of the calibration set to manipulate the training process, causing the classifier to perform differently on the (known) cal- ibration set than on unseen test data. Moreover, even if exchangeability holds, adversaries can still affect individual prediction sets: For example, they could manipulate the training process to degrade the utility of the score function. significantly altering the resulting prediction sets. This underscores again the need for point-wise coverage and size reliability as we introduce in Definition 1.
9 CONCLUSION
We introduce reliable prediction sets (RPS), a novel method designed to improve pointwise relia- bility of conformal prediction sets in the presence of data poisoning and label flipping attacks. By leveraging smoothed score functions and a majority voting mechanism, RPS effectively mitigates the influence of adversarial perturbations during both training and calibration. We provide theo- retical guarantees that RPS maintains stability under worst-case data poisoning, and demonstrate the effectiveness of our approach image classification tasks. Overall, approach represents an important contribution towards more reliable uncertainty quantification in practice, fostering the trustworthiness in real-world scenarios where data integrity cannot be guaranteed.
10

---

Published as a conference paper at ICLR 2025
REPRODUCIBILITY STATEMENT
We ensure reproducibility by documenting all hyperparameters and experimental setups in App. A. We also provide code along with detailed reproducibility instructions via the following project page: ht https: www. as cit tum, de het..dd/dmm//ellablll. iable conforma --reed ct con/..
ACKNOWLEDGMENTS
The authors want to thank Jan Schuchardt, Lukas Gosch, and Leo Schwinn for valuable feedback on the manuscript. This work has been funded by the DAAD program Konrad Zuse Schools of Excellence Artificial Intelligence (sponsored by the Federal Ministry Education and Research). The authors of this work take full responsibility for its content.
REFERENCES
Anastasios N Angelopoulos and Stephen Bates. A gentle introduction conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.07511 2021.
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncer- tainty sets for image classifiers using conformal prediction. In ICLR. OpenReview.net, 2021.
Andreas Auer, Martin Gauch, Daniel Klotz, and Sepp Hochreiter. Conformal prediction for time series with modern hopfield networks. NeurIPS, 2023.
Philip J Boland, Harshinder Singh, and Bojan Cukic. Stochastic orders in partition and random testing of software. Journal of applied probability, 39(3):555-56 2002.
Maxime Cauchois, Suyash Gupta, Alnur Ali, and John C. Duchi. Robust validation: Confident predictions even when distributions shift. CoRR, 0wt/2208.042667 2020.
Giovanni Cherubin. Majority vote ensembles of conformal predictors. Machine Learning, 108(3): 475-488, 2019.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning, pp. 1310-1320. PMLR, 2019.
Bat-Sheva Einbinder, Stephen Bates, Anastasios N. Angelopoulos, Asaf Gendler, and Yaniv Ro- mano. Conformal prediction is robust label noise. CoRR, abs/2209. 14295, 2022.
Matteo Gasparin and Aaditya Ramdas. Merging uncertainty sets via majority vote. arXiv preprint arXiv:2401.09379, 2024.
Asaf Gendler, Wei Weng, Luca Daniel, and Yaniv Romano. Adversarially robust conformal prediction. In ICLR. OpenReview.net, 2022.
Subhankar Ghosh, Yuanjie Shi, Taha Belkhouja, Yan Yan, Jana Doppa, and Brian Jones. Proba- bilistically robust conformal prediction. In UAI, volume 216 of Proceedings of Machine Learning Research, pp. 681-690. PMLR, 2023.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. CVPR, pp. 770-778. IEEE Computer Society, 2016.
Linus Jeary, Tom Kuipers, Mehran Hosseini, and Nicola Paoletti. Verifiably robust conformal pre- diction. CoRR, abs/2405.1194. 2024.
Mintong Kang, Zhen Lin, Jimeng Sun, Cao Xiao, and Bo Li. Certifiably byzantine-robust federated conformal prediction. In /CML. OpenReview.net, 2024.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Jing Lei, Max G'Slll, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113 1943):199411111,, 2018.
11

---

Published as a conference paper at ICLR 2025
Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defenses against general poisoning attacks. In ICLR. OpenReview.net, 2021.
Yangyi Li, Aobo Chen, Wei Qian, Chenxu Zhao, Divya Lidder, and Mengdi Huai. Data poisoning attacks against conformal prediction. In Forty-first International Conference on Machine Learn- ing. 2024.
Lars Lindemann, Matthew Cleaveland, Gihyun Shim, and George J. Pappas. Safe planning in dy- namic environments using conformal prediction. IEEE Robotics Autom, Lett., 86):511165513,, 2023.
Ziquan Liu, Yufei Cui, Yan Yan, Xu, Xiangyang Ji, Xue Liu, and Antoni B. Chan. The pitfalls and promise of conformal inference under adversarial attacks. In ICML.. OpenReview.net, 2024.
Ilya Loshchilov and Frank Hutter. SGDR: stochastic gradient descent with warm restarts. In ICLR (Poster). OpenReview.net, 2017.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Baolin Wu, Andrew Y Ng, et al. Reading digits in natural images with unsupervised feature learning. In NIPS workshop deep learning and unsupervised learning, pp. 4. Granada, 2011.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In ECML, volume 2430 of Lecture Notes in Computer Science, pp. 345- 356. Springer, 2002.
Sangdon Park, Osbert Bastani, and Taesoo Kim. Acon2: Adaptive conformal consensus for provable blockchain oracles. In USENIX Security Symposium, pp. 3313-3330 USENIX Association, 2023.
Coby Penso and Jacob Goldberger. A conformal prediction score that is robust label noise. CoRR, abs/2405.0266 08.448.,,668, 2024.
Keivan Rezaei, Kiarash Banihashem, Atoosa Malemir Chegini, and Soheil Feizi. Run-off election: Improved provable defense against data poisoning attacks. In ICML, volume 202 of Proceedings of Machine Learning Research, pp. 29030-29050. PMLR, 2023.
Yaniv Romano, Matteo Sesia, and Emmanuel Candès. Classification with valid and adaptive coverage. In NeurlPS, 2020.
Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and J. Zico Kolter. Certified robustness to label- flipping attacks via randomized smoothing. In ICML, volume 119 of Proceedings of Machine Learning Research, pp. 8230-8241. PMLR, 2020.
Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):223-225 2344, 2019.
Aldo Solari and Vera Djordjilović. Multi split conformal prediction. Statistics Probability Letters, 184: 109395, 2022.
Philip Sosnin, Mark Niklas Müller, Maximilian Baader, Calvin Tsay, and Matthew Wicker. Certified robustness to data poisoning in gradient- based training. CoRR, abs/2406.05670, 2024.
Wenpin Tang and Fengmin Tang. The poisson binomial distribution-old & new. Statistical Science, 38(1):108-11 2023.
Zhiyi Tian, Lei Cui, Jie Liang, and Shui Yu. A comprehensive survey poisoning attacks and countermeasures in machine learning. ACM Comput. Surv., 55(8): 16::16666:6633 2023.
Janette Vazquez and Julio C. Facelli. Conformal prediction in clinical medical sciences. J. Heal. Informatics Res,, 63)):241-252, 2022.
Vladimir Vovk. Conditional validity of inductive conformal predictors. Mach. Learn., 92(2-3): 349-376, 2013.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world, volume 29. Springer, 2005.
12

---

Published as a conference paper at ICLR 2025
Volodya Vovk, Alexander Gammerman, and Craig Saunders. Machine-learinng applications of al- gorithmic randomness. In ICML, pp. 144-453. Morgan Kaufmann, 1999.
Wenxiao Wang, Alexander Levine, and Soheil Feizi. Improved certified defenses against data poi- soning with (deterministic) finite aggregation. In ICML, volume 162 of Proceedings of Machine Learning Research, pp. 22769-22783. PMLR, 2022.
Ge Yan, Yaniv Romano, and Tsui-War Weng. Provably robust conformal prediction with improved efficiency. In ICLR. OpenReview.net, 2024.
Soroush H Zargarbashi, Mohammad Sadegh Akhondzadch, and Alcksandar Bojchevski. Robust yet efficient conformal prediction sets. arXiv preprint arXiv:2407.09160 2024.
13

---

Published as a conference paper at ICLR 2025
APPENDIX OVERVIEW
In this appendix we provide additional results, details on our experimental setup and prove theoreti- cal results outlined in the following:
A Full experimental setup and reproducibility details
15
Additional results for reliable prediction sets
16
Reproducible prediction sets
21
D Proofs for reliable prediction sets (Section 5)
22
Proofs for reliability certificates (Section 6)
23
14

---

Published as a conference paper at ICLR 2025
A FULL EXPERIMENTAL SETUP AND REPRODUCIBILITY DETAILS
We provide details on the experimental setup to ensure reproducibility of our results.
Datasets. The datasets use for evaluation are described in Section 7 (SVHN (Netzer et al., 201 1), CIFARIO 10 and CIFARI00 (Krizhevsky et al., 2009)) and are publicly available. We use the torchvi- sion library to load the d We normalize images before training, and compute dataset mean and standard deviation on each training partition separately to ensure models are trained on isolated partitionn, which is required by our method to improve reliability.
Training details. We train all models with stochastic gradient descent (learning rate 0.01, momen- tum 0.9, weight decay 5e-4) for 400 epochs using early stopping if the training accuracy does not improve for 100 epochs. We further deploy cosine learning rate scheduler (Loshchilov & Hutter, 2017). We use batch size of 128 during training and 300 inference. To ensure that our guarantees against
hold we require that the training process is deterministic, which not only involves fixing the random seed for data augmentation but also ensuring that the internal training processes deterministic (Levine & Feizi, 2021). We also sort the training data in each partition to ensure that training is invariant w.r.t. the order of the training data (Levine & Feizi, 2021).
Image preprocessing. We determine dataset-wide mean and standard deviation dynamically on ery training set partition separately once before training to ensure that each classifier is trained on an isolated partition. We subsequently normalize all images in one partition with the corresponding values. We also augment the training set with random crops (padding of 4 pixels) and random hori- zontal flips (but we perform the data augmentation in deterministic, reproducible way across runs). Note that mean and standard deviation are computed before data augmentation.
Hardware details. We train ResNet18 models on a NVIDIA GTX 1080TI GPU, and the ResNet50 and ResNet101 models on a NVIDIA A100 40GB. We perform inference of all models on NVIDIA GTX 1080TI GPU, and compute certificates on a Xeon E5-2630 v4 CPU,
Reproducibiliity To ensure reproducibility we use random seeds for all randomized functions, this especially includes the dataset preprocessing, model training and calibration splits. We provide all random seeds and detailed reproducibility instructions along with our code.
Training time details. The average runtime statistics for training ResNet18 models on CIFAR-10 and SVHN are follows. Training single ResNet18 model on CIFAR-10 10 takes approx. 2.6 hours, while training 100 models requires total of 2.4 hours, with each individual model taking approx. 1.5 minutes. For SVHN, single ResNet 88 model takes 1.5 hours to train, and training 100 models requires total of 1.6 hours, with each model training taking around 58 seconds. For CIFAR 100, single ResNet18 model takes 3 hours to train, and training 100 models requires total of 2.27 hours, with each model training for around 1.4 minutes.
hhtpp:://prerrrh.ogg//tttto////s /nnelleee/iie....eee Index htm1
15

---

Published as a conference paper at ICLR 2025
B ADDITIONAL RESULTS FOR RELIABLE PREDICTION SETS
In this section, we expand on the experimental results by providing further analyses and complemen- tary results. Figure 5 shows the worst-case reliability guarantees for the SVHN dataset under the three different poisoning scenarios (in the same settings as described in the main paper). We again observe that our method provides reliable prediction sets even under worst-case poisoning attacks. Complementary to the main section, Figure shows the average set size and empirical coverage in all three different experiment settings (a-c) on the SVHN dataset.
Figure 7 (1) shows the average set sizes of the three different architectures (ResNet18, ResNer50, ResNet101) on the CIFARIO dataset when using majority vote prediction sets with the smoothed score function (third experimental setting). Interestingly, using the ResNet18 model yields the best results, which we attribute to the fact that models trained on subsets of the training set require less capacity to learn the data distribution, and the reduced size prevents overfitting, Figure 7 (2,3) show the softmax ablation study for empirically justifying the smoothing of the voting function (a = 0.1).
In the main plots in Section 7, we only considered the diagonal re = for the reliability ratios. In Figure 8, we show the reliability ratios for coverage reliability, size reliability, and robustness for all combinations of r. and for the CIFAR 10 dataset 1k,=100, 400 a=1.1). Reliability ratios are generally higher for larger re. which indicates that RPS is more reliable under calibration poisoning-
In Figure 9 we provide additional results for ResNet18 on the CIFAR100 dataset under calibration poisoning. We show the empirical coverage, average set size, and reliability guarantees for the 8 model. We observe that our method provides reliable prediction sets even under calibra- tion poisoning attacks on the CIFAR100 dataset (showing that majority prediction sets generally scale to datasets with significantly more classes).
Figure 10 shows the relationship between reliability of ResNet18 and the number of partitions under calibration poisoning for SVHN, CIFARIO, and CIFARIO0. For training poisoning. guarantees become non-trivial for kg = 100 partitions as shown in the main text. Note that size reliability reduces again if the number of calibration partitions becomes too large. The main reason for this is that a minimum number of calibration points is required to construct prediction sets (due to the sinite-sample correction, as already discussed in Section 8). As the number of calibration points per partition decreases with more partitions, adversaries could remove points from partitions to prevent us from constructing prediction sets in the first place (see theoretical analysis in Appendix D).
As mentioned in Section 8, training on subsets of larger datasets such as CIFARI00 or ImageNet comes with accuracy loss, which affects the utility of our smoothed score function. Specifically, when splitting the training set of CIFAR100 into 10 partitions, each individual classifier achieves an accuracy of approximately 30% (in contrast to at least 70% when trained on the entire dataset). This causes inconsistencies between the classifiers, which affects the utility of the score function, eventually leading to excessively large prediction sets. Figure 11 (a) shows that the average set size is above 42 for 10 partitions. When using 100 partitions, the average set size is 42.96, indicating low utility. Future learning algorithms could further improve performance under training poisoning for larger datasets with more classes, ultimately boosting robustness and reliability in machine learning.
In additional experiments (Figure 11) training randomly initialized models from scratch as for all other plots in the paper). Note that in this case the reliability guarantees hold for the fine-tuning dataset only, not for the dataset used for pretraining. Interestingly, Figure 11 (1) shows that the average set size in experiments with pretrained models is significantly reduced, indicating that the models benefit from pretraining on ImageNet (although the average size still remains high for 100 partitions on CIFAR100 16). Further, Figure 11 (2-3) show reliability guarantees under both training and calibration poisoning for the CIFAR1O dataset when using pretrained ResNet18 model (3) compared to training from scratch (2). We observe that reliability increases significantly when compared to the reliability of model that was randomly initialized and trained from scratch. Notably, this means that improving the classifier's performance under partitioning of the training data will also improve the reliability of prediction sets and thus provides an interesting direction for future work, e.g. by applying recent improvements in the certifiable robustness literature (Wang al., 2022; Rezaci et al., 2023). We also believe that studying poisoning in fine-tuning settings is promising future research direction, especially given the proliferation of pretrained models in practice.
we finetune classifiers pretrained on ImageNet (instead of
16

---

Published as a conference paper at ICLR 2025
Finally, provide additional results for reliable prediction sets for the following evaluation metrics: (1) the ratio of empty sets, (2) the ratio of full sets, (3) the singleton ratio (ratio of sets containing single class), and (4) the singleton hit ratio (empirical coverage of singleton predic- tion sets). Figure 12 shows results for the CIFARIO dataset, and Figure 13 shows results for the SVHN dataset, for all three evaluation settings (a-c) described in Section 5.
(b)
(c)
Reliab. ratio (%)
Reliab. ratio (%
Reliab. ratio (%)
75
75
coverage
75
cowerage reliable
size reliable
sizce reliable
50
50
civerrage
25
sino raliable
25
25
5
1 2
Calib. set radius Te
Training set radius
Poisoning radius
Figure 5: SVHN: Worst-case reliability guarantees across three scenarios: (a) poisoning of the
calibration data, (b) poisoning of the training data, and (c) poisoning of both datasets.
Avg. set size
a=0.00
Avg. set size
o=0.08
Avg. set size
o
ow40.1
a-dd.1
a=+0.1
1.25
1.5
1.00
1.0
20
20
Number of partitions k
Number of partitions kt
Num. partitions kr ke
Emp. coverage
Emp. coverage
Emp. coverage
95
95
90
90
--0.1
co00.05
1.50.05
10
20
10
20
10
20
Number of partitions ke
Number of partitions kg
Num. partitions hr = k.
Figure 6: Avg, size and empirical coverage in all three settings (a-c) the SVHN dataset.
Avg. set size
ResNert8
Emp. coverage
with withhrar woftmot
Avg. set size
with sothmox
3
ResNert0 ResNNet10
withoot
95
2
90
10
15
20
5
10
15
20
5
10
15
20
Num. partitions h; k.
Num. partitions h2 = kc
Num. partitions k2 = ko
Figure 7: (1): Different models on CIFAR10. (2.3): Softmax ablation study for empirically justify-
ing smoothing of the voting function (here with = 0.1) on CIFAR10.
17

---

Published as a conference paper at ICLR 2025
(3)
Radius ft
Radius rt
Radius
0.2
m
0.1
0.2
5
5
Radius Te
Radius Te
Radius Te
Figure 8: CIFARIO, & = 100, k. = 40, = 0.1, (1): Coverage reliability ratio, (2): Size reliability
ratio, (3): Robustness ratio (with with all radii combinations).
(2)
Emp. coverage
Reliab. ratio (%
Avg. set size
15
o-20
coverage reliable
10
size refiable
50
5
10 15
20
10
15
20
10
15
Number of partitions he
Number of partitions
Calib. set radius Te
Figure 9: Additional results for ResNet18 on CIFAR100 under calibration poisoning: (1): Empirical
coverage, (2): Average size, (3): Reliability guarantees.
(1)
AUCRC
15
coverae reliable size relisble
AUCRC
15
coverage caliable
AUCRC
15
cowerage relisble size reliable
size noliable
10
10
10
0
10
15 20 25 30
35
5 10 15 20
25 30 35
5
10
15 20
25 30 35
Number of partitions Ke
Number of partitions Ke
Number of partitions kc
Figure 10: Relationship between reliability and the number of partitions under calibration poisoning for ResNet18 on (1): SVHN, (2): CIFAR1O, and (3): CIFAR 100. Here, AUCRC stands for the area under the certifiable reliability curve the corresponding reliability types.
Reliab. ratio %
Avg. set size
not prstarined pretzained
robust
robust
75
reliable
Reliab. ratio
reliable
50
50
25
25
25
1
5
10
15
Number partitions k;
Poisoning radius Ft Fc
Poisoning radius Yy = Te
Figure 11: (1): Average set size using the smoothed score function on CIFAR100, comparing pre- trained vs. non-pretrained models. (2-3): Reliability certificates under both training and calibration poisoning 10, comparing reliability of randomly initialized ResNet18 models (2) (as in Figure c) against the reliability of pretrained models that are only fine-tume tine-tuned on CIFAR10 (3).
18

---

Published as a conference paper at ICLR 2025
(b)
Sing. hit ratio
Sing. hit ratio
Sing, hit ratio
95
90
10
15
20
10
15
20
10
15
20
Number of partitions k.
Number of partitions kr
Num. part. k lic
Singleton ratio
Singleton ratio
Singleton ratio
0.5
0.5
0.5
-000.5
a=0005
9=0055
0.0
0.0
0.0
5
10
15
20
5
10
15
20
5
10
15
20
Number of partitions lic
Number of partitions ky
Num. part. his
ke
Empty set ratio
1.0
Empty set ratio
1.0
1.0
Full set ratio
0.5
0.5
0.5
5
15
15
20
15
20
Number of partitions hi
Number partitions 1y
Num. part. 13g
1.0
1.0
1.0
Full set ratio
Full set ratio
Full set ratio
-000.5
9-111
0.5
0.5
0.5
0.0
0.0
0.0
1
5
10
15
20
5
10
15
20
5
10
15
20
Number of partitions kic
Number of partitions ke.
Num.
part. hi
Ko
Figure 12: Various metrics for RPS in the three experiment settings (a-c) for ResNet18 on CIFAR1O.
19

---

Published as a conference paper at ICLR 2025
(b)
Sing. hit ratio
Sing. hit ratio
Sing, hit ratio
95
90
10
15
20
10
15
20
10
15
20
Number of partitions k.
Number of partitions k
Num. part. k Ric
Singleton ratio
Singleton ratio
Singleton ratio
0.5
0.5
0.5
-000.5
0=0005
-000.5
0-00.11
0.0
0.0
0.0
5
10
15
20
5
10
15
20
5
10
15
20
Number of partitions lic
Number of partitions ky
Num. part. hi
ke
Empty set ratio
1.0
Empty set ratio
1.0
Empty set ratio
1.0
0.5
0.5
0.5
5
15
15
20
10
15
20
Number of partitions he
Number partitions 1y
Num. part. 1g
1.0
1.0
1.0
Full set ratio
Full set ratio
Full set ratio
-000.5
9-111
0.5
0.5
0.5
0.0
0.0
0.0
1
5
10
15
20
5
10
15
20
5
10
15
20
Number of partitions ki
Number of partitions ke
Num.
part. hi
Ko
Figure 13: Various metrics for RPS in the three experiment settings (a-c) for ResNet18 on SVHN.
20

---

Published as a conference paper at ICLR 2025
B.1 STUDY OF STATISTICAL EFFICIENCY OF MAJORITY PREDICTION SETS
Empirical coverage is random variable following Beta distribution concentrated around the nom- inal coverage level (Vovk, 2013). Here we conduct additional experiments to provide empirical evidence that the majority prediction sets are again closely concentrated around the nominal cover- age level. We train ResNet18 classifier on CIFAR10 and calibrate homogeneous prediction sets (Sadinle et al., 2019) for the nominal coverage level of prediction sets on &c 10 and & 20 partitions, respectively. Finally, prediction sets using the majority voting scheme described in Section 5. We repeat this process 100 times and compute the empirical coverage for each run. We then plot the empirical coverage for each run in Figure 14. As we partition the calibration set, the concentration naturally decreases for smaller prediction sets, leading to overcoverage. Interestingly, we observe that the majority pre- diction sets are again closely concentrated around the nominal coverage level, providing empirical evidence that majority prediction sets statistically efficient.
= 0.9. Then we compute the smaller
merge the smaller
hip 10
kip = 20
1.00
1.00
Empirical coverage
Empirical coverage
0.95
0.95
0.90
0.90
0.85
0.85
0.80
0.80
HPS
Smaller HPS
Majority
HPS
Smaller HPS
Majority
Figure 14: Concentration of empirical coverage for vanilla HPS, HPS for each partition, and the majority prediction sets. We use k. 10 partitions for the left plot, and k. 20 partitions for the right plot. Majority prediction sets are again closely concentrated around the nominal coverage level, providing empirical evidence that majority prediction sets statistically efficient.
C REPRODUCIBLE PREDICTION SETS
There are conformal score functions that rely on random variables, e.g. for ensuring exact coverage by breaking ties. For example, adaptive prediction sets (APS) sum over class probabilities of classes with probability least fy(x):: s(I, u. -
[f< (()))))/((()))///)>)))) (a)), where f is soft classifier and E [0. 1] uniform random variable (Romano et al., 2020). Conformal prediction sets are then formed by C(In+1) {s(#n+1, Un+1, 9) 2 7). where un+1 [0, 1].
Although randomization at inference changes prediction sets by at most one class (Angelopoulos al., 2021), generating different prediction sets for the same input may not be desirable from reliability standpoint and violates desideratum V. For example, a differential diagnosis for two pa- tients with identical health parameters should not yield different results. As a solution, we propose reproducible score functions: Instead of drawing from random variable, we propose to compute pseudorandom numbers by hashing the sum of the image's pixel values and initialize the pseudo- random number with the hash. We found that this is enough to break ties in practice while ensuring determinism required by our reliability guarantees. Note that our score functions with pscudo- randomization are valid since they maintain exchangeability the numbers depend solely the data itself (not its position in the dataset or other datapoints).
We analyze this in Figure 15 (with a=0.5)) Without randomization APS results in large sizes (2) despite tight coverage (1). Randomization leads to smaller sets but also compromises reproducibil- ity. With beeudo-randomization APS is reproducible with tight coverage and small prediction sets.
21

---

Published as a conference paper at ICLR 2025
Emp. coverage
Avg. set size
95
AFS without randomization
qundomized
90
reprodacible APS (ouns)
randomizzd randomization
repcoducible APS (ours)
15
20
10 Number of partitions kc
Number of partitions ke
Figure 15: Comparing APS without and with randomization against reproducible version.
D PROOFS FOR RELIABLE PREDICTION SETS (SECTION 5)
Recall the definition of the majority prediction from Section 5:
Rc My E C,(En+1)) > f(a)
(2n+1) y
with +(a)=max for E [Re] F(x) S at, where is the CDF of the Binomial distribution Bin(ki,, a) and [kc] = (0....,ko k.). In the following, denote a ((a) for simplicity.
Theorem 2. Given any conformal score function s and test sample (E441.9n41) E Dtest exchange-
able with Dealih the majority prediction set (Equation 3) constructed from sets calibrated disjoint partitions - achieves marginal coverage on clean data: Pr(yn+1 CM (In+1)) 1-0.
Proof. Define the event di - 1 [1n441 E C,(++11)3 The main argument is that the events and Φ are independent for i * j. This holds since the prediction sets C, and Cj are constructed on disjoint partitions of a calibration set of independent datapoints and are thus independent. This allow us to use an argument of Gasparin & Ramdas (2024) about majority voting in the context of uncertainty
sets: Specifically, di are independent Bernoulli random variables with pt = Pr(ø; = 1] 2 a by construction. Further define the random variable
Sk. Σ 1 (IIn41)).
First consider the special case ps Sk. ~ Bi, - a). Thus we have:
for all i. Then Sk, is a Binomial random variable,
he
Pr(yo+1 E C. (xx+ Pr
1 [8n+t E C,(xn+1))>> 7
(5)
Pr SSk. > fl
(6)
1 Pr [Sk. S
(7)
1 F(A)
(8)
Sa
> 1
(9)
In the general case of p: a we have that Sk. is distributed as a Poisson binomial random variable, Sk_ ~ PB [pI..... Ps..). However, holds that - P; > (1 - a) ar, which implies that the Poisson binomial distribution is stochastically larger than the Binomial distribution (Boland et al., 2002; Tang & Tang, 2023). See (Gasparin Ramdas, 2024) for details. Intuitively, this means that the probability Pr [St. f] can only increase in the general case where p:
n
22

---

Published as a conference paper at ICLR 2025
Extended discussion. In the context of uncertainty sets, Gasparin & Ramdas (2024) proved that merging independent uncertainty sets via majority voting can retain their 1-a marginal coverage in general. However, note that their construction actually violates the marginal coverage guarantee: They define the threshold in their majority set as sup fx E R F(x) S a} (in contrast to our threshold f max(2 E [&e] Fax) I a)). The problem with their construction is that F()) > due to the definition of the supremum and the definition of the binomial CDF:
Lar Σ
) a))
ke
F(r:ke, - a)
This means f+ which leads to smaller majority sets that violate the coverage guarantee since Pr[Sk, q
due Fq)) > a. Beyond that, we propose method for improving the reli- ability of conformal prediction against worst-case poisoning attacks (by partitioning the calibration set), and derive reliability guarantees.
Minimal calibration set size for majority prediction sets. Recall that desideratum VI (Section 4) requires that the reliability of prediction sets must increase for larger calibration sets. Our majority prediction sets fulfill this desideratum by construction since increasing the number of partitions kic will decrease the influence of datapoints. However, we need enough data to construct prediction sets: due to the finite-samll correction, the calibration partitions cannot become arbitrarily small. This naturally bounds the number of partitions kg for a fixed calibration size n (and thus reliability):
Proposition 1. Let i" arg (1....kk |P denote the partition of smallest size. Given cover- age probability a, we can construct prediction sets for partition i provided that P. ( -)).
Proof. In general, constructing prediction sets given calibration points requires, due to the finite sample correction, that 0 S On =
1//n holds (otherwise we cannot compute quantiles).
We have: 0 < [n(n + 1) 1j/n + 1 - [a(n + 1)] @ < a(n + holds since the l.h.s. a natural number.
- -1 n, where (1)
Thus we need n 2 equally subsets of size n. then need at least 2 k ( - 1) datapoints. If the partitions
datapoints in our calibration set. If we partition the calibration data into
not equally-sized, then require for the smallest partition i* that |P& ( 1) holds.
E PROOFS FOR RELIABILITY CERTIFICATES (SECTION 6)
Algorithm Greedy algorithm for upper bounding the Algorithm 4 Greedy algorithm for lower bounding the smoothed score function
smoothed score function
Input: Score function I, y, k, Ft
Input: Score function y. Ks Tt
1: π = [ (I), ......,,((( xx)]]
1: (m)...... TK Tx(x))
2: for i = 1 to r. do
2: for 1 do
3: if F. 0 then
3: I argmax f Tg
4: Tý + min(max [ 1 ke, 0),
4:
+
5: clse
5: Ty + min FT 1/ke, 0),
6:
argmin Vis TTy
Output: 3(x,y) v) = ex (2 e
7:
Ty min(max(TF
/h, 0),
8: = argmax 4T
9: Tt +- min(max(T,, + 1/he,, 0),
Output: s(x.8) e / et
Let C(#n+1)= y : s(xn+1.y) 2 be prediction set for test point 1,41 derived using conformal prediction (Section 3) under the clean dataset D, and with the smoothed score function s.
23

---

Published as a conference paper at ICLR 2025
Lemma 2. We can upper bound the score function for any Di Breae (Di) follows:
(x,
max
with
== (T) + A (x()) Axl
(10)
05A,51 A,E (0. by "...., Eim A,=0
Σ e*
Proof. Since adversaries can insert or delete at most 7t datapoints, we know at most Tt training partitions can be affected in the worst-case. Thus at most ry of kg classifiers change their prediction.
This holds analogously for the lower bound on the smoothed score function:
s(x,1))
min OSTiS1 f (0.1111 F, ..... Σ
with
[ (ax) A.,. Fx +Ax]
(11)
e
iml
Proposition 2. Algorithm 3 and Algorithm solve the discrete optimization problems in Equation 10 and Equation 11, respectively. The optimal solutions represent the worst-case bounds on the score function under any poisoned dataset DD E Br. (Di).
Proof. In the worst-case, the adversary controls at most 7, partitions, which means the adversary controls the predictions of at most r, classifiers and can consequently change most It probability mass in the vote-distribution over classes V, which is exactly what the two optimization problems model. We now distinguish between the two cases:
For the upper bound 5(2, y), the worst-case adversary redistributes the probability mass from the classes with the largest probability masses to the target class y. which is the worst-case upper bound since it maximizes the numerator and minimizes the denominator.
For the lower bound =(x; y). the worst-case adversary redistributes the probability mass from the target class to the class with the largest probability mass. If the target class has 0 remaining probability mass, then the probability from the smallest class with probability mass larger than 0 is redistributed to the class with most of the probability mass. This is the worst-case lower bound since it minimizes the numerator and maximizes the denominator.
The argument holds since the space we optimizing over is discrete, (x) {0, t ...,, k=1 Both worst-cases exactly what the Algorithms in Algorithm and Algorithm 4 compute. O
R.
Clearly, both greedy algorithms need r; iterations terminate (due to the for loop).
Theorem 3. Given r,=0, the conformal prediction set ((E+1)) derived with the smoothed score function under any poisoned dataset Dre (Dr) is coverage reliable, i.e. ((xn+1) 2 C(In41),
if 12 2 F, and size reliable, i.e. Č(xx+1) C C(xn+1), (xx
Proof. We consider training set poisoning. In the worst case, adversaries perturb at most v. training partitions. Thus, the worst-case quantiles are given by:
Quant (an; {=))
=uant(a.,;; [z)
where 2(xi,, yi) and 3(2;, M&) are lower and upper bounds the scores for all points (I 81.) E Deatis in the calibration set. We treat coverage and size reliability separately:
Coverage reliability: We consider prediction set coverage reliable if no class can be removed from the set. If adversaries cannot remove the "weakest" class y with the fewest votes Ty among all classes y E C(x,+1) from the prediction set, then adversaries also cannot remove any other class since they would need even more adversarial budget. In the worst-case, the lowest score for sample and class is given by s (z, y). Thus, if this lowest score still larger than or equal to the worst-case quantile т, then the weakest class cannot be removed and the prediction set is coverage reliable.
24

---

Published as a conference paper at ICLR 2025
Size reliability: We consider prediction set size reliable if no class can be added to the set. If adversaries cannot add the "strongest" class y with the most votes ny among all classes y & C(an+1) into the prediction set, then adversaries also cannot add any other class since they would need even more adversarial budget. In the worst-case, the largest score for sample x and class y is given by (x,T). T). Thus, if this largest score is still smaller than the worst-case quantile I, then the strongest class cannot be added and the prediction set is size reliable.
Theorem 4, Given r0=0 and deterministic score function the majority prediction set C. (In+1) derived under any dataset Di Br...(D) is coverage reliable, i.e. CM (In+1) 2 CM (xn-1), if m- Te F(a), and size reliable, i.e. CM (zn-1) C CM (In+1), ), if m + Te S +(a). provided that the smallest calibration partition it is large enough [P; - To ( -1)
Proof. Coverage reliability: In the worst-case, adversaries control at most re calibration partitions and thus can change the support Ei= 1y E (Z for classes E CM (Im+1) by at most Te- If removing Te from the support m the class with the least support is not enough to remove the class, m
Te > f, then the majority prediction set remains coverage reliable.
Size reliability: In the worst-case, adversaries control at most T. calibration partitions and thus can change the support Σ Iy E (2n+1)) for classes & C. (#n+1) by at most Te- If adding To to the support îा of the class with the most support is not enough to add the class, m7 ro S f, then the majority prediction set remains size reliable.
This only holds if the smallest calibration partition i" is large enough I 2 (1 - 1) under an attack, otherwise the adversary could prevent us from computing the majority prediction set in the first place by deleting datapoints from partition i".
A
Theorem 5. Let By denote the number of prediction sets C, E (CI...., Cr. for which we can guarantee y E C, under poisoned training datapoints. If By -Te- > =((a) for all E CM (In+1) then the majority prediction set is coverage reliable under any dataset Di E Br (Di), provided that the smallest calibration partition i is large enough P Te 2 ( 1).
Proof. If there is a single class y E CM (In+1) for which we cannot guarantee that more than prediction sets contain y under Tz poisoned training and r. poisoned calibration points, then the majority prediction set is not coverage reliable in the worst-case. Thus showing 8y-re>$ for all
y E C.M (In+1) as explained in the main text sufficient condition for coverage reliability.
LI
Theorem 6. Let "hy denote the number of prediction sets C. {CI,..., Ck,} for which we can guarantee y & C, under T1 poisoned training datapoints. 1 ((a) all y & CM (In+1) then the majority prediction set is size reliable under any dataset Di E Br. (Di), provided that the smallest calibration partition i is large enough 1 Te (2 1)).
Proof. If there is single class y & CM (xn-1) for which we cannot guarantee that less than (or equal to) ê prediction sets do not contain y under rt poisoned training points and re poisoned calibration points, then the majority prediction set is not size reliable in the worst-case. If 7f denotes the number of prediction sets for which we can guarantee y & C, under rt poisoned training datapoints, then k. - is the number of prediction sets for which we cannot guarantee & C₁ (this entails the number of prediction sets with y E C.). Under consideration of additional calibration poisoning, we cannot guarantee y & C, for k - 7v + тe prediction sets. In the worst case, he Tv + re prediction sets will contain the class. In other words, he 7/ + Te I T for all y & C (Im+1) is a sufficient condition for size reliability.
Computational complexity. For the training-poisoning certificates have compute the algo- rithm for all n calibration points. Assuming we recompute the argmax every time, the certificates can be computed in O(nr, K) (where K is the number of classes). Regarding our cnlibratiionpoisonniii certificates, the terms m. 777 can be computed efficiently in O(K,,) steps. To compute guarantees in the general case, we mainly need to compute the terms B,, and Ty for all K classes y E y. This in- volves computing the worst-case quantiles (O (O K)) for each prediction set ke and the worst-case score ()). Thus overall the guarantees can be computed in O OKKii C. Pr,K)) O (K2
25


Reviews:
[{"review_id": "LhYRgbih0j", "reviewer": "Reviewer_1V8P", "summary": "They introduce a method called \"reliable prediction sets\" that constructs conformal prediction reliable sets under poisoning attacks. They consider both training and calibration data poisoning. In order to achieve robustness against training poisoning, they partition training data into different parts and train a classifier on each part, and then aggregate the predictions from these classifiers to derive a smooth conformal score function.\n\nFurthermore, in order to be reliable against calibration poisoning, they calibrate multiple prediction sets on disjoint subsets of the calibration data and construct a majority prediction set that includes classes that are included in the majority of the independent prediction sets.\n\nTheir guarantees show that:\nUnder training poisoning, they show the conformal prediction set derived with smoothed score function is both size reliable and coverage reliable.\nFurthermore, for calibration poisoning, they show under some conditions their majority prediction set method is coverage and size reliable.\n\nFinally, they show the effectiveness of their approach experimentally, showing their method achieves reliability while maintaining utility on clean data.", "questions": "In equation 2, it might be good to remind the reader that K is the number of classes. \n\n I was confused by Definition 1, I think here you mean that the adversary flips y_i for some examples x_i, and then as a result, the prediction set C(x_{n+1}) might inflate or shrink. Is this correct?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I think overall, the idea of partitioning the training data and training different classifiers and aggregating their predictions is pretty natural and has been in around for both differential privacy and robustness against poisoning attacks. But anyways, they are the first to study it in the context of conformal prediction.", "weaknesses": "I think overall, the idea of partitioning the training data and training different classifiers and aggregating their predictions is pretty natural and has been in around for both differential privacy and robustness against poisoning attacks. But anyways, they are the first to study it in the context of conformal prediction.", "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": "aUTBGQlnzK", "reviewer": "Reviewer_HznX", "summary": "This paper proposes reliable prediction sets (RPS) as an efficient method for constructing conformal prediction sets under training and calibration data poisoning. The proposed approach has two components: to improve reliability under training data poisoning, authors introduce smoothed score functions that reliably aggregate predictions from classifiers trained on distinct partitions of the training data; and to improve reliability under calibration data poisoning, authors calibrate multiple prediction sets, each calibrated on distinct subsets of the calibration data, and construct a majority prediction set. Authors propose a desiderata for reliable conformal prediction, and derive certificates for the reliability of prediction sets under worst-case data poisoning attacks. The paper presents empirical evaluation of the method on image classification tasks.", "questions": "Is there any reason why full experiments for CIFAR-100 and ImageNet were not included? I appreciate the paper mentions the limitation in terms of accuracy loss, and I understand if full training can be expensive but I still believe there is value in showing limited results here, especially under calibration poisoning. It will be good to understand performance and the various desiderata in these relatively harder datasets with larger number of classes.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written, organized, and easy to follow for the most part. \n2. The paper is technically sound. I appreciate the paper clearly lays out the desiderata for reliable conformal prediction sets under data poisoning in the beginning. The claims regarding RPS are well supported by theory and empirical evaluation. \n3. The paper presents important results that can contribute toward improving the reliability of conformal prediction sets under data poisoning attacks in real scenarios.", "weaknesses": "1. It would help to show comparison with baselines in the empirical evaluation. I see there is some comparison with APS to understand the effect of randomization; however, it would be interesting to see worst-case reliability analysis comparison with existing conformal prediction methods, and discussing how RPS fares in the different desiderata.\n2. Relationship of reliability with number of partitions: the paper briefly discusses how the number of partitions (and dataset size) will affect the reliability of prediction sets; however, I did not seem to find experiments that analyze this relationship. It would help to demonstrate this relationship in order to better understand the utility of prediction sets in different scenarios.\n3. Section 6 can be made more readable and the notation becomes slightly hard to follow at times. \n\n\n\n**Minor comments:**\n1. L176: typo, Desideratum VI -> Desideratum IV\n2. L300: equation reference should probably be (5) \n3. L350: typo, coverave -> coverage", "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": "8lqHBsxvO0", "reviewer": "Reviewer_AjMN", "summary": "This work studies robustness of conformal prediction to poisoning in a threat model that allows insertion and deletion which is a limitation of the other studies e.g. zargarbashi et al, 2024. For training the authors propose to divide the training data into $k_t$ disjoint sets so that by definition any poisoning will at worst break one model. This robustness approach was previously studied in image classification as well. The conformity score function is the softmax over the votes of each classifier on each class. While the conformal guarantee is safe w.r.t. poisoning in the training process, calibration data can be poisoned as well. The authors remedy that by a similar approach of dividing the calibration set, and producing prediction sets from each calibration group, and running a majority vote-based decision on the final output. \n\nOverall I don’t count section 5.1 as a novel approach tailored to conformal prediction. However it is an smart approach to reduce the poisoning effect on set size. However showing that Section 5.2 is a valid approach is an important contribution.", "questions": "1. The definition of $\\hat{\\tau}$ is unclear to me. Can you elaborate? What is this capturing? Why the iteration variable is called $x$? Does it have any correlation with covariates?\n2. I can not understand why poisoning in training data can influence the coverage reliability. Since the coverage is only dependent to calibration set the guarantee should not break with a poisoned model (CP is guaranteed with black-box model). Then why Fig. 2-b shows a decay on coverage reliable. In general there are no comprehensive discussions on what coverage reliability and coverage guarantee have in difference. So from the conformal guarantee changes in the training data should have no influence in the “marginal” coverage of the prediction sets. However I think this reliability is defined per point. Is that so? In case yes please update the manuscript to draw this difference line in a more clear way. \n3. I think the set-size reliability is misleading to show (at least as a solid line) for calibration poisoning. Under calibration poisoning the guarantee is already invalid and with an invalid guarantee by definition it is not important if the set sizes are small or not. Even in some cases expanding set sizes can be considered as an alert to the defender that the calibration set is invalid.\n4. In Fig 3. I can not understand the jumps in the beginning of the x axis for empirical coverage? What is the reason behind that intuitively? I see a quick explanation in lines 473-475 but isn’t it due to the missing randomization in the score function?\n\nIf the points in questions and weaknesses are provided I would be happy to increase my score.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The other works designed to make CP robust to poisoning are not considering insertion and deletion in their threat model. This makes this work unique. Also their approach however repeated from the poisoning literature, still is novel to be adapted to conformal prediction framework. \n\nThe score function designed by the authors is interesting and novel. It also can have interesting properties beyond the score of robustness. The interesting outcome of this is that it enables them to provide the guarantees on the set size which is novel.\n\nThe paper is theoretically solid. I think the theorems are well defined, and the results are quite far from obvious. Therefore I see this as a strong work.\n\nThe writing is also in a good shape; the story of the paper is easy to follow. However a strong recommendation is to add a discussion on differences between normal conformal coverage guarantee and coverage reliability.", "weaknesses": "**Writing.**  I expect the threat model to be mentioned more clearly in the introduction. Until the related work I did not understood that the authors are addressing a poisoning model different from zargarbashi et al 2024. I strongly suggest the authors to mention that in their threat model addition and deletion of data points is allowed which is a limitation of zargarbashi et al 2024 either in the introduction or in the corresponding section in related works.\n\n**Wrong background.** The definition of the conformal prediction in Theorem 1 is not correct. Either you define the scores as capturing agreement between the data and the label (e.g. directly using softmax) then the for test points you add labels with scores above the threshold and the threshold is the $\\alpha_n = \\lfloor\\alpha(n+1)-1\\rfloor$ or the quantile is as authors specified in line 135, where the score should be non-conformity $1 - f_y(x)$ and the labels with score lower that the threshold should be picked. \n\n**Unnecessary, and unclear desiderata.** Although I agree on desiderata no. 1, 2, and 3, I still think that computational efficiency is not a necessity. Also if no. 4 means that there is an strict increasing requirement, then it contradicts the assumption of adding datapoints can be invariant to the final result. Other than that what is the concrete definition of providing small prediction sets? Is it in comparison to the same model trained on clean data? or is it in comparison to vanilla setup?\n\n**Discrete score.**  Although the score is float, it is discrete with fixed number of possibilities. However working in practice there are corner cases where ties can become problematic. You need to add a random noise to the score in Eq. 2 which I think does not change that much in the efficiency of the output but simply avoids these small chances of failure. \n\n**Study of statistical efficiency.** The empirical coverage is not always $1 - \\alpha$. This is on it’s own a random variable sampled from a Beta distribution concentrated around the nominal guarantee. This concentration is increased by the number of calibration points. The first question that is not addressed here is that how breaking the calibration set to smaller calibration sets influence this concentration? For sure it should decrease due to smaller calibration sets, while some of this can be remedied by the majority prediction set. Do you have any intuition on how this is affected? At least I expect a discussion on the lowerbound of this in the limitations of the work.\n\n**Typos.** Sentence at the end of line 250 is grammatically wrong. Typos are seen in lines 349 (title). \n\n**Suggestions.** The intuition behind the proof of Theorem 2. is non-trivial. I would recommend the authors to add a short sketch of proof or an intuition on what is deciding the parameter of majority vote set in the manuscript.", "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 (Spotlight)