Provably Robust Conformal Prediction with Improved Efficiency
Authors: Ge Yan
Yaniv Romano
Tsui-Wei Weng
Venue: ICLR 2024 poster (2024)
Keywords: Conformal prediction
randomized smoothing
adversarial robustness
Primary area: general machine learning (i.e., none of the above)

Abstract: Conformal prediction is a powerful tool to generate uncertainty sets with guaranteed coverage using any predictive model, under the assumption that the training and test data are i.i.d.. Recently, it has been shown that adversarial examples are able to manipulate conformal methods to construct prediction sets with invalid coverage rates, as the i.i.d. assumption is violated. To address this issue, a recent work, Randomized Smoothed Conformal Prediction (RSCP), was first proposed to certify the robustness of conformal prediction methods to adversarial noise. However, RSCP has two major limitations: (i) its robustness guarantee is flawed when used in practice and (ii) it tends to produce large uncertainty sets. To address these limitations, we first propose a novel framework called RSCP+ to provide provable robustness guarantee in evaluation, which fixes the issues in the original RSCP method. Next, we propose two novel methods, Post-Training Transformation (PTT) and Robust Conformal Training (RCT), to effectively reduce prediction set size with little computation overhead. Experimental results in CIFAR10, CIFAR100, and ImageNet suggest the baseline method only yields trivial predictions including full label set, while our methods could boost the efficiency by up to $4.36\times$, $5.46\times$, and $16.9\times$ respectively and provide practical robustness guarantee.

Published as a conference paper at ICLR 2024
PROVABLY ROBUST CONFORMAL PREDICTION WITH IMPROVED EFFICIENCY
Ge Yan CSE, UCSD geyan@ucsd.edu
Yaniv Romano ECE, Technion
Tsui-Wei Weng HDSI, UCSD
yrrmmmn@techhion ac
wwnggucsd edu
ABSTRACT
Conformal prediction is powerful tool generate uncertainty sets with guaranteed coverage using any predictive model, under the assumption that the training and test data are i.i.d. Recently, has been shown that adversarial examples are able manipulate conformal methods to construct prediction sets with invalid coverage rates, as the i.i.d. assumption violated. To address this issue, a recent work, Randomized Smoothed Conformal Prediction (RSCP), was first proposed to certify the robustness of conformal prediction methods to adversarial noise. However, RSCP has two major limitations: (i) its robustness guarantee is flawed when used in practice and (ii) it tends to produce large uncertainty sets. To address these limitations, we first propose novel framework called RSCP+ to provide provable robustness guarantee in evaluation, which fixes the issues in the original RSCP method. Next, we propose novel methods, Post-Training Transformation (PTT) and Robust Conformal Training (RCT), to effectively reduce prediction set size with little computation overhead. Experimental results CIFARIO, CIFARI00 and ImageNet suggest the baseline method only yields trivial predictions including full label set, while our methods could boost the efficiency by up 4.36x, 5.46x, and 16.9x respectively and provide practical robustness guarantee.
INTRODUCTION
Conformal prediction (Lei & Wasserman, 2014; Papadopoulos et al., 2002; Vovk al., 2005) has been a powerful tool to quantify prediction uncertainties of modern machine learning models. For classification tasks, given a test input + it could generate a prediction set C(En-1) with coverage guarantee:
Plyn+1 E C( 2 1-a, a,
(1)
where y is the ground truth label and desirable in safety-critical applications like autonomous vehicles and clinical applications. In general, is common to set the coverage probability ground truth label to be contained in the prediction set with high probability. It is also desired to have the smallest possible prediction sets C(x.+11) as they are more informative. In this paper, we use the term "efficiency" to compare conformal prediction methods: we say conformal prediction method more efficient if the size of the prediction set is smaller.
user-specified target coverage. This property is
a be high, e.g. 90% or 95%, as we would like the
Despite the power of conformal prediction, recent work (Gendler et al., 2021) showed that conformal prediction is unfortunately prone to adversarial examples- that is, the coverage guarantee in Eq. (I) may not hold anymore because adversarial perturbation on test data breaks the i.i.d. assumption and thus the prediction set constructed by vanilla conformal prediction becomes invalid. To solve this problem, Gendler et al. (2021) proposes new technique, named Randomized Smoothed Confor- mal Prediction (RSCP), which is able to construct new prediction sets C, (Tx++) that is robust to adversarial examples:
(2) where Ex+1 denotes a perturbed example that satisfies ||ăn+1 - In+ill2 S c and e > 0 is the perturbation magnitude. The key idea of RSCP is to modify the vanilla conformal prediction procedure with randomized smoothing (Cohen et al., 2019; Duchi et al., 2012; Salman et al., 2019) so that the impact of adversarial perturbation could be bounded and compensated.
P(y++1 E C. (ă 11

---

Published as a conference paper at ICLR 2024
Avg. Size of C on CIFAR 10
RSCP limitations
Our solutions
Baseline:
4 LI HPS
return all class labels (trivial resuit)
(1; Flawed robustness certification
RSCP+
(sec
Ours: guaranteed robustness & high efficiency
Large prediction set efficiency)
PTT + RCT
(scc 4)
2-
Figure I: An overview of this work: We address two limitations of RSCP (Gendler et al., 2021) by proposing RSCP+ (Sec. 3) PTT RCT (Sec. 4), which enables the first provable and efficient robust conformal prediction. As we show in the experiments in Sec. 5, our proposed method could provide useful robust prediction sets information while the baseline failed.
However, RSCP has two major limitations: (1) the robustness guarantee of RSCP is flawed: RSCP introduces randomized smoothing to provide robustness guarantee. Unfortunately, the derived guarantee is invalid when Monte Carlo sampling is used for randomized smoothing, which is how randomized smoothing is implemented in practice (Cohen et al., 2019). Therefore, their robustness certification is invalid, despite empirically working well. (2) RSCP has low efficiency: The average size of prediction sets of RSCP is much larger than the vanilla conformal prediction, shown in our experiments (Fig. D.1).
In this paper, we will address these two limitations of RSCP to allow efficient and provably robust conformal prediction by proposing a new theoretical framework RSCP+ in Sec. 3 to guarantee robustness, along with two new methods (PTT & RCT) in Sec. 4 to effectively decrease the prediction set size. We summarize our contributions below:
We first identify the major issue RSCP robustness certification and address this issue by proposing
theoretical framework called RSCP+. The main difference between RSCP+ and RSCP is that our RSCP+ uses the Monte Carlo estimator directly as the base score for RSCP, and amends the flaw of RSCP with simple modification the original pipeline. To our best knowledge, RSCP+ the first method to provide practical certified robustness for conformal prediction.
2. We further propose two methods improve the efficiency of RSCP+: scalable, training- free method called PTT and a general robust conformal training framework called RCT. Empirical results suggest PTT and RCT are necessary for providing guaranteed robust prediction sets.
3. We conduct extensive experiments on CIFARIO, CIFARI00 and ImageNet with RSCP+, +, PTT and RCT. Results show that without our method the baseline only gives trivial pre- dictions, which are uninformative and useless. In contrast, our methods provide practical robustness certification and boost the efficiency of the baseline by up to 4.36x CIFAR10, 5.46x on CIFARIOO and 16.9x on ImageNet.
BACKGROUND AND RELATED WORKS
2.1 CONFORMAL PREDICTION
Suppose D = ((z,, y1) | is an i.i.d. dataset, where E Rp denotes the features of ith sample and V: E [K] := (1...., K} denotes its label. Conformal prediction method divides into two parts: a training set Diran = [xx ) and calibration set Deal D Dmiin The training set Dmain is utilized to train classifier function #(r): : R² + [0, 1]K Given classifier म, con-ooofrrmity score function S(z.9) y) 1º [K] + is defined for each class y based on classifier's prediction (xx). Next, the calibration set Daal is utilized to calculate threshold which is the (1 - a)(1 + 1 Dea) empirical quantile of calibration scores (S(x, y) (x. Given a test sample Fz conformal prediction construct prediction set C(Ent15 7) as:
C(En41;7) (k: [K] ((Int1,k) TT
2

---

Published as a conference paper at ICLR 2024
where
7 == QI-ia((( y) (aw)ED))
and (D()c denote the p(1 + c/lDh empirical quantile of the calibration scores. In the remainder of the paper, we may omit the parameter T and write the prediction set simply as C(x) when the context is clear. Conformal prediction ensures the coverage guarantee in Eq. (1) by showing that the score corresponding to the ground truth label bounded by r with probability a, i.e. (( 3n++) 7)
Note that the above conformal prediction pipeline works for any non-conformity score S(x, y). but the statistical efficiency of conformal prediction affected by the choice of non-conformity score. Common non-confornity scores include HPS (Lei et al., 2013; Sadinle et al., 2019) and APS (Romano al., 2020):
SHPS (x.
v) (x
f,((1), (X
E y'E[K]
(y (x)
(S)
where u is a random variable sampled from a uniform distribution over [0, 1].
2.2 RANDOMIZED SMOOTHED CONFORMAL PREDICTION
To ensure the coverage guarantee still holds under adversarial perturbation, Gendler et al. (2021) proposed Randomized Smoothed Conformal Prediction (RSCP), which defines a new non-conformity score 5 that can construct new prediction sets that are robust against adversarial attacks. The key idea of RSCP to consider the worst-case scenario that Š may be affected by adversarial perturbations:
S(än+1. y) S S(xn+1, v) Mc, Vy E [K]
(6)
where 1n+1 denotes the clean example, Tn+1 denotes the perturbed example that satisfies || In+1ll ll2 e and M, is a non-neee non-negative constant. Eq. (6) indicates that the new non non-conformity score S on adversarial examples may be inflated, but fortunately the inflation can be bounded. Therefore, to ensure the guarantee in Eq. (2) is satisfied, the threshold r in the new prediction set needs to be adjusted to Tadj defined as Tadj + M, to compensate for potential adversarial perturbations, and then C. can be constructed as follows:
Ce(2; {k E [K]] 5(x,k) S Tadi),
(7)
where is any test example. From Eq. (6), the validity of C. could be verified by following derivation:
yn+1 E ((I++1) = 5(x.+1, Mn+1) S ((in+1, Bn+1) S Tadj = Yn+1 E CC(nn)))
(8)
Thus, the coverage guarantee in Eq. (2) is satisfied. To obtain a valid M.. Gendler et al. (2021)
proposed to leverage randomized smoothing (Cohen et al., 2019; Duchi et al., 2012) to construct S. Specifically, define
Š(z, v) - --1 [SRs v)] and SRS(I, 3) EB-N((..21, +, 6,
where 8 is a Gaussian random variable, the standard deviation of 8 which controls the strength of smoothing, and 4 --(( is Gaussian inverse edf. We call SRs(2, y) the randomized smoothed score from base score S(z, y). Sps(z, y) is the smoothed version of S(z, y) using Gaussian noise on the input æ. Since $ is defined on the interval [0, 1]. the base score S must satisfy S(x, v) E [0. 1). One nice property from randomized smoothing (Cohen et al., 2019) is that it guarantees that Š is Wo+1) S(xm41 11n+1
Lipschitz continuous with Lipschitz constant 3. ie. [8(ä.+1 Fa41 have
1. Hence, we
| - #ntille S = S(T 1.0+1.30+1) S S S(ant), Mn+1)
(10)
which is exactly Eq. (6) with M. = &. Therefore, when using in conformal prediction, the threshold should be adjusted by:
Tadj = T + σ
(11)
3

---

Published as a conference paper at ICLR 2024
3 CHALLENGE 1: ROBUSTNESS GUARANTEE
In this section, we point out flaw in the robustness certification of RSCP (Gendler et al., 2021) and propose new scheme called RSCP+ + to provide provable robustness guarantee in practice. As we discuss in Sec. 2.2, the key idea of RSCP is introducing new conformity score S that satisfies Eq. (10), which gives an upper bound to the impact of adversarial perturbation. However, in practice, S is intractable due to expectation calculation in SRs. A common practice in randomized smoothing literature is:
Step 1: Approximate SRS by Monte Carlo estimator:
NMc
Sas , y)
Σ
S(x + 6
+(x+ v), 1O),
(12)
NMC
Step 2: Bound the estimation error via some concentration inequality.
In RSCP, however, Step 2 is missing, because bounding the error simultaneously on the calibration set is difficult, as discussed in Appendix A.I. We argue that the missing error bound makes the robustness guarantee of RSCP invalid in practice.
To address this issue, we propose elegant and effective approach, RSCP+, fill in the gap and provide the guarantee. In particular, the intrinsic difficulty in bounding Monte Carlo error inspires us avoid the estimation. Thus, in RSCP+ we propose a new approach to incorporate the Monte Carlo estimator Sgs directly as the (non- Jeonforiiy score, which could directly calculated, unlike SRS- Here, one question may arise is: Can randomized score (e.g. SRS) be applied in conformal prediction and maintain the coverage guarantee? The answer is yes: as we discuss in Appendix A.2, many classical (non-) )conformity scores (c.g. APS (Romano et al., 2020)) are randomized scores, and the proof' for them are similar to the deterministic scores, long the i.i.d property between calibration and test scores is preserved. Therefore, our Sgs is legit (non-) noon-)oonformity score.
The challenge of using Šgs is to derive inequality similar to Eq. (10), i.e. connect and Sks (Zn+1: y) (the grey dotted line in Fig. 2), so that we can bound the impact from adversarial noises and compensate for it accordingly. To achieve this, we use SRs as a bridge (as shown in Fig. 2),
y)
and present the result in Theorem
(hard calculate exactly)
Algorithm RSCP +: Generate provably robust prediction set.
S Pear)
Input :Input image #e+1 calibration set Deat, target
RSOP bound [Eq. (15)
Hoeflding's bound [Eq. (14))
Hoeffding's bound
coverage level a, e, a.
[q3(13]]
Output :uurratted robust prediction set C++
Calculate calibration scores with randomized
Ses Pe.))
smoothing(See B) :
Thm. 1: Bound the impact advemarial parturbation Sys
Calculate threshold TMC as I+1/|Dal
1-a-20 empirical quantile
construct Cf (x) (can be calculated via MC sampling)
calibration scores;
Calculate conformity score for each class with randomized
Sus: RS score defined Eq. (9).
Susi Monte Carlo score defined Eq. (12).
smoothing (ās(a k0
(uus): Clean test example. Rat1 Perturbed input.
Calculate prediction set C,' with Eq. (17).
Figure 2: Diagram illustrating our RSCP+. (Left) (1) The dotted line shows our target: bound
Monte-Carlo estimator score Sps under perturbation; (2) The orange arrow denotes the bound of the randomized smoothed score SRS under perturbation, given by (Gendler et al., 2021); (3) The grey arrows denote Hoeffding's 's inequality connecting randomized smoothed score SRs and Monte Carlo estimator score ŠRS. The target (1) could be derived by (2) (3). (Right) RSCP+ algorithm.
Theorem 1. Let (#n+ (n-1) be the clean test sample and Zn+1 be perturbed input data that satisfies ||ā - xn+ill22 S Then, with probability 1 1828
Ses(#n41, Vn+1)
bioee( S +b - vn+1) + b1oo((3)] + =].
where (Boee(())
-In8 2Ne
NMc is the nunber of Monte Carlo examples, T is standard Gaussian cdf.
is smoothing strength and Sas is the Monte Carlo score defined in Eq. (12).
4

---

by Eq. (A.9), both with probability - B. Mcanwhile, by plugging in the definition of S, Eq. (10) is Published as a conference paper at ICLR 2024
Proof of Theorem 1. The main idea of the proof is connecting (2s(#n+1: Bn+1) and
Sks 11,+1 Un++1) via the corresponding SRS, shown in Fig. 2. By Hoeffding's inequality (See Appendix A.3 for further discussion), we have
Sps(Fnt1, S (In+11 Un+1) ) + (1t)
(13)
by Eq. (A.8) and
(R Bm+1) 2 (T (0+1111/+1))) (Hoer(3)
(14)
equivalent to
Φ -- [SRS( v++1 S + (SRs (vn+1, Un++1 e
(15)
Combining the three inequalities above and applying union bound gives:
(R 11+1) S 1 [Rs (In+1 Ma+1)] =
Eq. (13)
SRS( (1 S Φ (xn+ Mn+1) + bHoet] + E
with prob. 1
(16)
Eq. (14)
SRs(Fn+1 Mx+11) - biteer (3) + [
Un-1) + (3))
with prob. 1 28
with probability 1 2,3, which proves Theorem 1.
Remark. The bound Theorem could be further improved using Empirical Bernstein's 's inequality (Maurer & Pontil, 2009). We found in our experiments that the improvement is light on CIFAR10 and CIFARIOO, but could be significant on ImageNet. For more discussion see Appendix A.3.3.
With Theorem 1, we could construct the prediction set accordingly and derive the robustness guarantee in Corollary 2 in the following.
Corollary 2. (Robustness guarantee for RSCP+) The RSCP+ prediction set
C. (#n+1; = k E [K] Ses (is((n+11k)) (1 < + { b (3) + {}} (17) satisfies robust coverage guarantee in Eq. (2), i.e. PP E C. (Tn+1i 2 1 a. Here, the threshold TMC is calculated according to Eq. (4) with S = Sns and replaced by 1 28, i.e. TMC = =Q (1Spstt v) ().
Proof of Corvllary 2. Since we have TMC Q1-at22 ((Sps (1, (). conformal prediction
guarantees coverage on clean examples:
P[SRs(En+i Mn+1) S TMC] 2 1 - + 2,3.
(18)
Plug Eq. (18) into Eq. (16) in Theorem and apply union bound, we get
{ (ass(an1:: vn-1) ( < +b Φ [TMC + (5) + []] 2 - a.
IP
(19)
4 CHALLENGE 2: IMPROVING EFFICIENCY
So far, we have modified RSCP to RSCP+ that can provide a certified guarantee in Sec. 3. However, there exists another challenge directly applying RSCP+ often leads to trivial prediction sets that give the entire label set, as shown in our experiment Tabs. and 2. The reason is that RSCP is conservative: instead of giving an accurate coverage as vanilla CP, RSCP attains a higher coverage due to its threshold inflation (Eq. (11)), and thus gives a larger prediction set on both clean and perturbed data. We define conservativeness of RSCP as the increase in the average size prediction sets after threshold inflation: Appendix A.4 where we give formal definition. Since RSCP+ is modified from RSCP, it's expected to inherit the conservativeness, leading to trivial predictions. To address this challenge and make RSCP+ useful, in this section, propose address this problem by modifying the base score with two new methods: Post Training Transformation (PTT) and Robust Conformal Training (RCT).
5

---

Published as a conference paper at ICLR 2024
4.1 POST-TRAINING TRANSFORMATION (PTT)
Intuition. We first start with a quantitative analysis of the conservativeness by threshold inflation. As an approximation the conservativeness, we measure the coverage gap between inflated coverage 1 aajj and target coverage OC:
agap (1 (adaad) - (1 a) = a Cladj
(20)
Next, we conduct a theoretical analysis on agaa- Let 2 (t) be the cdf of score S(z, y), where (xr Pay. For simplicity, suppose (t) is known. Recall that in conformal prediction, the threshold r is the minimum value that satisfies the coverage condition:
{ (P(a)))- s (1 (1-).
argmin ERR
(21)
Notice that P. (a..))~PP (5(z, v) S t is exactly + (t), we have:
Φ (T)
(22)
Suppose the threshold is inflated as Tadj = T + Me. Similarly, we could derive Oadj = =Ta((T)))
=
(T Mc) by Eq. (11). Now the coverage gap O'aap can be computed as:
Ogap
Ordjj
$ $ + M.) $ (T(()) Mc
(23)
The last step is carried out by the linear approximation of Dg: g(x + 2) g(x) x (x)
Key idea. Eq. (23) suggests that we could reduce argap by reducing the slope of Ø3 near the original threshold t, i.e. (T) This inspires us to the idea: can we perform a transformation on S to reduce the slope while keeping the information in it? Directly applying transformation on is not a valid option because it would break the Lipschitz continuity of S in Eq. (10): for example, applying a discontinuous function on Ó may make it discontinuous. However, we could apply transformation Q on the base score S, which modifies Š indirectly while preserving the continuity, as long as the transformed score, Q S, still lies in the interval [0, 1]. The next question is: how shall we design this transformation @? Here, we propose that the desired transformation Q should satisfy the following two conditions:
1. (Slope reduction) By applying Q. should reduce the slope (T)(T), thus decrease the coverage gap O'gap- Since we are operating on base score S, we approximate this condition by reducing the slope (T). (T) We give a rigorous theoretical analysis of a synthetic dataset and an empirical study on real data justify the effectiveness of this approximation in Appendices B.6 and B.7, respectively.
2. (Monotonicity) Q should be monotonically non-decreasing. could be verified that under this condition, (Q . S) is equivalent to S in vanilla CP (See our proof in Appendix B.5). Hence, the information in S is kept after transformation Q.
These two conditions ensure that transformation without losing the information in the original base score. With the above conditions in mind, we design two-step transformation Q by composing (I) ranking and (II) Sigmoid transformation on base score S, denoted as Q Qaig Qrank. We describe each transformation below.
could alleviate the conservativeness of RSCP
Transformation (I): ranking transformation Qrank- The first problem we encounter is that we have knowledge about the score distribution & in practice, which makes designing transformation difficult. To address this problem, we propose a simple data-driven approach called ranking transfor- mation to turn the unknown distribution & into uniform distribution. With this, could design the following transformations on it and get the analytical form of the final transformed score distribution
@o..- For ranking transformation, we sample an i.i.d. holdout set Dhoidou = ((rt, Di) } Nuatoo from Pxy. which is disjoint with the calibration set Deal. Next, scores {S(x, (x.g) Dr are calculated on the holdout set and the transformation Crank is defined as:
i=1
r[s; (5 (x.))) Pratue))
Grank (s)
Dholdout

---

Published as a conference paper at ICLR 2024
Here, r(z; H) denotes the rank of x in set H, where ties are broken randomly. We want to emphasize that this rank is calculated on the holdout set Dholden for both calibration samples and test samples. We argue that the new score Qankk S is uniformly distributed,whiee is a well-known result in Mrristics(Kuchihhook 2020). See more discussion in Appendix B.3.
Transformation (II): Sigmoid transformation 2ag- After ranking transformation, we get a uniformly distributed score. The next goal is reducing (T) For this, we introduce Sigmoid transformation Qig. In this step, a sigmoid function & is applied on S:
Qsi(()) o [(s b)/T1
where 6, I' are hyper-parameters controlling this transformation. Due space constraint, discuss more details of Sigmoid transformation in Appendix B.4, where we show that the distribution of transformed score & Qamos is the inverse of Sigmoid transformation 2 (Eq. (B.2)), and by setting a and properly small, the Sigmoid transformation could reduce (r))
Summary. Combining ranking transformation and sigmoid transformation, we derive new (non- Jeonformity score SPrr
SPTT (ar, u) -QQig Qrank (2,,
(24)
could be verified that Sprr (2, y) E [0. 1] for any S thanks to the sigmoid function, hence we could plug in S SpTT(x; (x. y) into Eq. (9) as base score. Additionally, SPTT (I., v) is monotonically non-decreasing, satisfying the monotonicity condition described at the beginning of this section. We provide rigorous theoretical study on PTT over synthetic dataset in Appendix B.7. Additionally, we craft a case in Appendix B.8 where PTT may not improve the efficiency. Despite this theoretical possibility, we observe that PTT consistently improves over the baseline in experiments.
4.2 ROBUST CONFORMAL TRAINING (RCT)
While our proposed PTT provides a training-free approach to improve efficiency, there is another line of work (Einbinder al., 2022b; Stutz al., 2021) studying how train a better base classifier for conformal prediction. However, these methods are designed for standard conformal prediction instead robust conformal prediction considered in our paper. this section, we introduce a training pipeline called RCT, which simulates the RSCP process in training to further improve the efficiency of robust conformal prediction.
Conformal training. Stutz et al. (2021) proposed a general framework to train a classifier for conformal prediction. It simulates conformal prediction in training by splitting the training batch B into a calibration set Bea and a prediction set Bpeed then performing conformal prediction on them. The key idea is to use soft surrogate sr and c(x: y/: 70fft to approximate the threshold 7 and prediction set C(z; r), making the pipeline differentiable: 7 Q (f y) (a.y)e R.)). where Q (H) denotes the q(1 + 1 qquantile of set H derived by smooth sorting (Blondel al., 2020; Cuturi et al., 2019), and c(x, ys 70fft) o 70th
Sp(a)))) where ((z) = 1/(1 + is the sigmoid
function and temperature Tirin a sepper-prramete. We introduce more details Appendix C.I.
Step 1: Split 8' into
Stop 2: Compute non- conformity score S.
Step 3: Compute zauft and adjust soft to sddj soft
B..1 and Byre.
Calibration Hr..
Sae(Nrai Yrat)
5 Yea))
soft
Prediction set Byre
Chooeeee Pore)
5(x Spre)
e (Apprrr Yprei soff
(r + 27 (c)
4.1: Calculating class- wise prediction set
Step 4.2: Computing training objective [Fq. 26)
Figure 3: Pipeline of our proposed Robust Conformal Training (RCT) method.
7

---

Published as a conference paper at ICLR 2024
Incorporating RSCP into training. Inspired by Stutz et al. (2021), propose to incorporate RSCP (Gendler et al., 2021) (and of course, RSCP+ + since the major steps are the same) into the training stage as shown in Fig. 3. We adopt soft threshold S and soft prediction c(z, 7 from Stutz et al. (2021), and add randomized smoothing 8 and threshold adjustment Tadj - + _ to the pipeline in RSCP. Next, need to examine the differentiability of our pipeline. The threshold adjustment and Gaussian inverse cdf + step in the calculation of S is differentiable, but the gradient of SRS = [B (,), S(x + 6. y) is difficult to evaluate, as the calculation of S(x, y) involves a deep neural network and expectation. Luckily, several previous works (Salman et al., 2019; Zhai et al., 2020) have shown that the Monte-Carlo approximation works well in practice:
Nusin
VoE6-NN0..21,)512 6,y)
0,y)
+0,
(25)
Nurii
With these approximations, the whole pipeline becomes differentiable and training could be performed by packppropagation. For the training objective, we use the same loss function:
L(r, Ug) = (elnss(c(xr, y; T ==)) Maa)) + Absise (c(ar, y;
(26)
where classification loss Letass (c(x, y: 750ft ygi) 1 c(2, ygu: r*"),, size loss U y: +
max(0, Ey= c(2, y; r K), Vgt denotes the ground truth label, c(æ,, y; T0hh denotes the soft prediction introduced in Stutz et al. (2021), x is a hyper-parameter.
Remark. Since the methods we proposed in Sec. 4 (PTT and RCT) are directly applied to base scores, they are orthogonal to the RSCP+ we proposed in Sec. 3. That is to say, PTT and RCT not only work on RSCP+ but also work on original RSCP as well. Nevertheless, we argue that RSCP+ with PTT/RCT would be more desirable in practice since it provides guaranteed robustness which the original purpose of provable robust conformal prediction. Hence, we will focus on this benchmark in the experiments section in the main text. However, we also provide experiment results on RSCP + PTT/RCT as an empirical robustness benchmark in Appendix D.2, which shows that our PTT and RCT are not limited to our RSCP+ scheme.
5 EXPERIMENTS
In this section, we evaluate our methods in Secs. 3 and 4. Experiments are conducted on CIFARIO. CIFARI00 (Krizhevsky et al., 2009) and ImageNet (Deng et al., 2009) and target coverage is set a 0.9. We choose perturbation magnitude c 0.125 on CIFARIO and CIFAR100 and c 0.25 on ImageNet.
Evaluation metries and baseline. We present the average size of prediction sets Ct (x) as key metric, since the robustness is guaranteed by our theoretical results for RSCP+ (CorollCyy 2). For the baseline, we choose the vanilla method from Gendler al. (2021), where HPS and APS are directly applied as the base score without any modifications.
Model. We choose ResNet-1 10 (He et al., 2016) for CIFARIO and CIFAR and ResNet-50 (He et al., 2016) for ImageNet. The pre-trained weights are from Cohen et al. (2019) for CIFARIO and ImageNet and from Gendler et al. (2021) for CIFAR100.
Hyperparameters. In RSCP+, choose 8 0.001 and the number of Monte Carlo examples NMC = 256. For PTT, we choose b = 0.9 and T = 1/400 and we discuss this choice in Appendix B.4. The size of holdout set Dholtoul 500. We discuss more experimental details in Appendix D.
5.1 RESULTS AND DISCUSSION
Tab. and Tab. 2 compare the average size of prediction sets on all three datasets with our RSCP+ benchmark. Specifically, the first row shows the baseline method using base scores in Gendler et al. (2021) directly equipped with our RSCP+. Note that the baseline method gives trivial prediction sets (the prediction set size total number of class, which is totally uninformative) due to its conservativeness. Our methods successfully address this problem and provide a meaningful prediction set with robustness guarantee.
8

---

Published as a conference paper at ICLR 2024
Base score
HPS
APS
Method Dataset
CIFARIO
CIFARI00
CIFARIO
CIFAR100
Baseline (Gendler et al., 2021)
10
100
10
100
PTT (Ours)
2.294
26.06
2.685
21.96
PTT+RCT (Ours)
2.294
18.30
2.824
20.01
Improvement over baseline: PTT Improvement over baseline: PTT RCT
4.36
3.84x
3.72x
4.35x
4.36
5.46x
3.54X
5.00
Table 1: Average prediction set (c)) size of RSCP+ on CIFARIO and CIFARI00. For CIFARIO and CIFARI00, c = 0.125 and / = 0.25. Following Gendler et al. (2021), we take Napli 50 random splits between calibration set and test set and present the average results (Same for Tab. 2). We could see that the baseline method only gives trivial predictions containing the whole label set, while with PTT PTT RCT can give informative and compact predictions.
Method Base score
HPS
APS
Baseline (Gendler al., 2021)
1000
1000
PTT (Ours)
1000
94.66
PTT Bemstein (Ours)
59.12
70.87
Improvement over baseline: PTT
10.6x
Improvement over baseline: PIT Bernstein
16.9
14.1x
Table 2: Average prediction set (C+ (z)) size of RSCP+ on ImageNet. For ImageNet, e 0.25 and a 0.5. The ImageNet dataset is more challenging and our PTT only works for APS score, but we find by applying the improvement with Empirical Bernstein's bound (denoted as "PTT + Bernstein") we discussed in Appendix A.3.3, we could largely reduce the size of prediction sets.
NMC Average size of prediction sets C
256
512
1024
2048
4096
2.294
2.094
1.954
1.867
1.816
Table Average size vs. Number of Monte Carlo samples NMC. The experiment conducted on CIFARIO dataset with PTT method. The base score is HPS. It could be seen that by increasing the number Monte Carlo examples, could further improve the efficiency of RSCP+, at the cost of higher computational expense.
Why the baseline gives trivial results under RSCP+? The key reason is conservativeness RSCP is conservative compared vanilla conformal prediction, and the challenging task of giving guaranteed robustness makes the situation worse. The result is that: without the boost of our PTT and RCT methods, the predictor is conservative that it gives the whole label set guarantee robustness, which is not the goal of users. This again justifies the necessity of our methods.
Impact of number of Monte Carlo samples NMC- In Tab. 3, we study how the number of Monte Carlo samples (NMc) influences the average size. It could be observed that the average size decreases as more Monte Carlo samples are taken. This is expected as more Monte Carlo samples reduce the error and provide a tighter bound in Eqs. (13) and (14). Therefore, trade-off between prediction set size and computation cost needs to be considered in practice, since increasing NvIC also significantly boosts the computation requirement.
6 CONCLUSION
This paper studies how to generate prediction sets that are robust to adversarial attacks. We point out that the previous method RSCP (Gendler et al., 2021) has two major limitations: flawed ro- bustness certification and low efficiency. We propose new theoretically sound framework called R which resolves the flaw RSCP and provides a provable guarantee. We also propose a training-free and scalable method (PTT) and robust conformal training method (RCT) to significantly boost the efficiency of RSCP. We have conducted extensive experiments and the empirical results support our theoretical analysis. Experiments show that the baseline gives trivial prediction sets (all class labels), while our methods are able to provide meaningful prediction sets that boost the efficiency of the baseline by up 4.36x on CIFAR 10, 5.46x CIFAR 100, and 16.9x ImageNet.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
This work supported in part by National Science Foundation (NSF) awards CNS-1730158, ACI- 1540112, ACI-1541349, OAC-1826967, OAC-2112167, CNS-2100237, CNS-2120019, the University of California Office of the President, and the University of California San Diego's California Institute for Telecommunications and Information TechnologyQQualcomm Institute. Thanks CENIC for the G. Yan and T.-.. Weng are supported by National Science Foundation under Grant No. 2107189 and 2313105. Romano was supported by the Israel Science Foundation (grant No. 729/21). Y. Romano also thanks the Career Advancement Fellowship, Technion, for providing research support.
100Gbps networks.
REPRODUCIBILITY STATEMENT
We provide the training details of RCT, hyperparameters, and other details of our experiments in Appendix D. The code is released on http://giibbboooo/////t//ttt///a Robust Conformal-Predictte
10

---

Published as a conference paper at ICLR 2024
REFERENCES
Anastasios Angelopoulos, Stephen Bates, Jitendra Malik, and Michael Jordan. Uncertainty sets for image classifiers using conformal prediction. arXiv preprint arXiv:2009. 1000099114999 14193, 2020.
Osbert Bastani, Varun Gupta, Christopher Jung. Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Practical adversarial multivalid conformal prediction. Advances in Neural Information Processing Systems, 35:29362-2995 2022.
Mathieu Blondel, Olivier Teboul, Quentin Berthet, and Josip Djolonga. Fast differentiable sorting and ranking. In International Conference Machine Learning, pp. 950-959. PMLR, 2020.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pp. 1310-1320. PMLR, 2019.
Marco Cuturi, Olivier Teboul, and Jean-Philippe Vert. Differentiable ranking and sorting using optimal transport. Advances in neural information processing systems, 32, 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255, leee, 2009.
John C Duchi, Peter L Bartlett, and Martin J Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal Optimization, 22(2):674-701, 2012.
Bat-Sheva Einbinder, Stephen Bates, Anastasios N Angelopoulos, Asaf Gendler, and Yaniv Romano. Conformal prediction is robust to label noise. arXiv preprini arXiv:2209. 14295, 2022a.
Bat-Sheva Einbinder, Yaniv Romano, Matteo Sesia, and Yanfei Zhou. Training uncertainty-aware
classifiers with conformalized deep learning. arXiv preprint 22t.:2205000877,, 2022b.
Asaf Gendler, Tsui-Wei Weng, Luca Daniel, and Yaniv Romano. Adversarially robust conformal prediction. In International Conference on Learning Representations, 2021.
Subhankar Ghosh, Yuanjie Shi, Taha Belkhouja, Yan Yan, Jana Doppa, and Brian Jones. Probabilisti- cally robust conformal prediction. In Uncertainty in Artificial Intelligence, pp. 681-690. PMLR, 2023.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedingy of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Arun Kumar Kuchibhotla. Exchangeability, conformal prediction, and rank tests. arXiv preprint N.Nv::0005.00095 2020.
Jing Lei and Larry Wasserman. Distribution-free prediction bands for non non-parametric regression. Journal of the Royal Statistical Society: Series (Statistical Methodology), 76(1):71-96, 2014.
Jing Lei, James Robins, and Larry Wasserman. Distribution-fice prediction sets. Journal of the American Statistical Association, 108(501):788-277, 2013.
Andreas Maurer and Massimiliano Pontil. Empirical bernstein bounds and sample variance penaliza- tion. arXiv preprini arXiv:0907.3740) 2009.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In European Conference on Machine Learning, pp. 345-356 Springer, 2002.
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems, 33:3581-3591, 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):233-244 2019.

---

Published as a conference paper at ICLR 2024
Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. Advances in Neural Information Processing Systems, 32, 2019.
David Stutz, Ali Taylan Cemgil, Arnaud Doucet, al. Learning optimal conformal classifiers. arXiv preprint arXiv:21 10.09192, 2021.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in random world. Springer Science Business Media, 2005.
Runtian Zhai, Chen Dan, Di Hc, Huan Zhang, Boqing Gong, Pradeep Ravikumar, Cho-Jui Hsich, and Liwei Wang. Macer: Attack-free and scalable robust training via maximizing certified radius. arXiv preprint arXiv:200100237. 2020.
12

---

Published as a conference paper at ICLR 2024
APPENDIX
A Further discussion on RSCP+ in Sec 3
14
A.I Why bounding Monte Carlo estimation error is difficult for original RSCP?
14
A.2 Does the coverage guarantee of conformal prediction hold for randomized scores?
14
A.3 Discussion on Theorem
15
A.4 More discussion on conservativeness of RSCP and RSCP+
18
Further discussion on PTT method Sec 4.1
B.1
Exchangebility of rank-transformed scores
19
B.2 Concerns on additional data
19
B.3 Ranking transformation turns score distribution into uniform distribution
19
B.4 Design choice of Sigmoid transformation
20
B.5 Discussion on monotonicity condition
20
B.6 Empirical evidence for coverage gap reduction by PTT
B.7 Theoretical analysis of PTT on a 1-D synthetic dataset
22
B.8 Case study: potential failure mode of PTT
26
C Further discussion on Robust Conformal Training in Sec 4.2
28
C.1 Details of Conformal Training (Stutz al., 2021)
28
C.2 Details of Robust Conformal Training (RCT)
29
Experimental details and extensive studies Sec 5
30
D.1 Experimental details
30
D.2 Empirical results on RSCP benchmark
................................
30
D.3 Experiments with different and Ø.
32
D.4 Abalation study
32
D.5
Standard deviation of experiment results
32
D.6
Extended study on the impact of NMC
D.7
Impact of T
34
D.8
Computational overhead our methods
35
E Other related works in robust conformal prediction
36
13

---

Published as a conference paper at ICLR 2024
A FURTHER DISCUSSION ON RSCP+ IN SEC 3
A.1 WHY BOUNDING MONTE CARLO ESTIMATION ERROR IS DIFFICULT FOR ORIGINAL RSCP?
As we discussed in the main text, in the calculation of the conformity score of RSCP, Monte-Carlo estimation for SRS is required which introduces estimation error. However, in the original work (Gendler et al., 2021), the error bound for this is not introduced. Below discuss why this kind of bound is difficult to be applied in RSCP context.
The main difficulty lies in the threshold calculation step: denote (,) the p(1 + 1/ 1/ quantile of set H and recall that Fajj + Q1-a((S(x, (x.g)e 2 depends on every example in the calibration set. This means that to derive non-trivial bound for Tadj- we need to bound the error on the whole set simultaneossly, which is difficult. For example, there are 10000 samples in the calibration set and each example is bounded with confidence level of 0.999, then the confidence level for threshold Tadj would be (..999)100001 4.5 x 10-5! To obtain a reasonable confidence level for Tadj- practitioners have use much smaller calibration set much higher confidence level, which may significantly hurt the performance.
A.2 DOES THE COVERAGE GUARANTEE OF CONFORMAL PREDICTION HOLD FOR RANDOMIZED SCORES?
In the proof of Corollary 2, utilize the coverage guarantee of conformal prediction clean examples, i.e. Eq. (18). A natural question is, does the coverage guarantee of conformal prediction still hold when a randomized score (like Sas we introduced) is applied?
We argue the answer is yes. Randomized conformity scores have been used in multiple previous works, e.g. APS by Romano et al. (2020) and RAPS by Angelopoulos et al. (2020). The theory they presented is slightly different from our case, but the key idea is the same. Below, we present a proof for Eq. (18) under our settings. Similar results could be found in (Angelopoulos et al., 2020; Romano et al., 2020).
Lemma A.1. Assume that Deal = {<),,,:)}= y:) 1 is an i.i.d. sampled calibration set, (In+1, yn+1) is from test example which is independently sampled from the same distribution. The score of example is
S, = SRs( Mi) = Now _j= S(x; + 8ej, 9:), Vi 1,2.... n + 1, where all Monte-Carlo noises d.j are i.i.d. sampled from N(0, o² I21,), independent from other variables. Then, { are i.i.d. distributed.
Proof. Note that the randomness of score S; comes from the data (I;, v/) and the Monte-Carlo noise diy. From assumption, (zt, yı) are i.i.d. across the calibration set and test sample, and the noise ōij are also drawn i.i.d. independent of other variables. Since S; is a function of (æ,, y:) and Noc this leads to the conclution that {S: |++ are i.i.d. distributed. {ō;z J=1
Lemma A.2. Suppose (S, i.i.d. distributed random variables. Tue is the g(1 1/n)-th empirical quantile of {S, 1i= Le.
1i [}} 2 q(1 + )
TMC min,
Then, IP(S441 TMC) 2 q.
Proof. We define the following indicator variables:
4 81
These variables have the following two properties:
1. {I 11t identically distributed. Thus, EI EI2 EI This follows from the i.i.d. property of (5, and symmetricity.
14

---

Published as a conference paper at ICLR 2024
2. I (n - [(n + 1) Suppose order S, from the smallest to the largest: S S 9z ... I $4.+1 Then, from the definition of 4, we know that Lgi, -o- 13ul
(there could not be [n 1)g] values smaller than them), giving this property.
With these two properties, we could derive
x+1
n+1
E
Σ
E4
(n + 1)LEn+1
(property 1)
and
n+1
S (n + 1) [(n+
(property 2)
I (n + 1)(1 - 9)-
Hence, E11+11 S 1 From the definition of TMC. we have
|i S; S TMC H ž [n(1 + )4l = [(n + 1)g]-
Hence, Sa+1 TMC indicates Ki S < Sn+1l H 2 (n + 1)4], Lut1 = 1. Therefore,
P(S,+1 TMC) P(Sn+1 > TMc)
2 P(I+t1 =1)
El,+1 29
gives the conclusion.
Remark. The i.i.d. condition could be replaced by a weaker condition of exchangeability From this lemma, it could be seen that the i...d. property of scores enough for the coverage guarantee of conformal prediction.
Proposition A.1. Under the conditions of Lemma 1, P[BRs(In+1, (n+++)))))) S TMcl 2 1 + 23, where Tae is the (1 a + 21 + 1/ni-th empirical quantile of calibration scores. This exactly Eq. (18)
Proof. Let 1- a + 28. Applying Lemma and 2 gives the result.
A.3 DISCUSSION ON THEOREM
In this section, we first introduce two concentration inequalities: Hoeffding's 's inequality and Empirical Bernstein's 's inequality (Maurer & Pontil, 2009). Then we explain how to utilize Hoeffding's 's inequality derive bounds in the proof of Theorem and how we could use Empirical Bernstein' 's inequality to improve the bound.
A.3.1 HOEFFDING'S S INEQUALITY AND EMPIRICAL. BERNSTEIN'S S INEQUALITY
Lemma A.3. (Hoeffding's 's Inequality) Let X1, ,x be i.i.d. random variables bounded by the
interval [0, 1]. Let X = = E X3, then for any 2 0
P(X EX t) < 2k12
(A.1)
and
PÆX - X 2 1) S 2kd
(A.2)
Corollary AA.. From Hoeffding's 's Inequality, we argue that with probability at least - 3,
< (1 = =/ log3
EX
(A.3)
2k
X EX < (Hoe((3)
(A.4)
15

---

Published as a conference paper at ICLR 2024
-oog Proof. Plugging t (3 -- into Eq. (A.2) gives
PEX X bHeef) S 3,
(A.5)
leading to Eq. (A.3) immediately. Similarly, we could get Eq. (A.4).
Lemma A.5. (Empirical Bernstein Inqquality) Under the condition of Lemma A.3, with probability
least
2V log
7log 3 3(k: - 1)
X bBem (B V)
(A.6)
where V is the sample variance of X1,
.... Xk. i.e.
V Σj= j=1 X?
(2 x2)²
(A.7)
A.3.2 APPLYING HOEFFDING'S INEQUALITY TO DERIVE EQ. (13) AND EQ. (14)
With Hoeffding's inequality, we can prove Eq. (13) and Eq. (14): Let X; S(xn+1 + 8, Ve+1).
Note that Sps 11 9h+11) NMC ENMc X; X and EX SRS (In+1; Da++)) can apply Corollary A.4 and get
(Rs(Ta+1,Ber Sus (In+11 Un+1) S (3)) with probability at least which exactly Eq. (13). Similarly, we could get
(A.8)
Sas (as(#n1 Bn+1) 2 (1 (B))
(A.9)
with probability at least
3, which exactly Eq. (14).
A.3.3 USE EMPIRICAL BERNSTEIN'S INEQUALITY TO IMPROVE EQ. (14)
In practice, the predictor takes potentially perturbed input ēn+1 from the user, then generates batch of Gaussian noise and computes corresponding SRs- Therefore, we could utilize the variation information from Monte Carlo samples to improve Eq. (14). Following the recommendation by (Zhai al., 2020), we use Empirical Bernstein's inequality to provide a tighter bound. Below we show the details.
Let X, S(īn+1 + 84, 31+1). Note that Sks (T Bn+1) Ses (Tn+1: 1n+1), we can apply Lemma A.5 and get
NNC X₁ = X and EX
Na::
Sus(En+1, Vn+1) Sus (Tn Un+1) I byem (3,V). V),
(A.10)
with probability at least B. With this inequality, we can derive Theorem A.6 and Corollary A.7 which are the counterparts Theorem and Corollary 2.
Theorem A.6. Let (In+1, Bn+1) be the clean test sample and Ānt1 be perturbed input data that satisfies ||ān+1 Intill2 S c. Then, with probability 233
Ses(ān+1 1n+1) brem (3, < Φ Φ
(5RSs 1n++1) + (Hoe{(3)] + =
where (B)
-In 2NNcc
brem (3,V)
2n Nuc [V
7ln 2
V sample variance of Sas-
3(M
Corollary A.7. Let the prediction set
C+ (Tn+1s TMC) { E [K] (as(5n
bremn (
( (TMC (3)
C+ (#n+1; TMc) satisfies robust coverage guarantee in Eq. (2), i.e. P(ynt1 E (f
1
16

---

Published as a conference paper at ICLR 2024
Proof. Replace Eq. (14) with Eq. (A.10), the remaining proofs are the same the proof of Theorem and Corollary 2.
Compare Corollary 2 and Corollary A.7, we that with Empirical Bernstein's inequality, we replace the (3) on the left-hand side with b (3, V), which could be computed at test time. it's natural ask if we can also improve Eq. (13) with Empirical Bernstein's 's equality. Unfortunately, in practice, the predictor cannot access In++1 (the clean example corresponding to the input), hence we could not do Monte Carlo sampling and calculate variance use Empirical Bernstein's 's equality. Therefore, we stick to Hoeffding's s inequality for Eq. (13).
17

---

Published as a conference paper at ICLR 2024
Reduced conservativeness
T adj
t
add
① RSCP without threshold inflation
Set inflation by threshold inflation ("consorvativeness" manuscript)
Figure A.I: Density plot of (non)-conformitt scores. (Left) The prediction of RSCP could be decomposed into two parts: (1) Base part generated by vanilla conformal prediction ((C(z)), or RSCP before threshold inflation) and (2) Set inflation by threshold inflation (conservativeness). (Right) By reshaping the cdf, our method could reduce the second part, even without re-ranking the samples. This also gives an intuitive motivation for why we want reduce the slope cdf near the threshold (i.e. reduce the density near the threshold).
A.4 MORE DISCUSSION ON CONSERVATIVENESS OF RSCP AND RSCP+
In Section we motivate our PTT methods by discussing the conservativeness of the RSCP method. In this section, we provide formal definition of conservativeness of RSCP and RSCP+, and discuss how our PTT and RCT methods could reduce this conservativeness.
Definition A.1. For a conformal predictor that generates robust prediction C.(x), we define its conservativeness as:
cons. := Ez-P,
(A.11)
where C(x) is the prediction set by vanilla conformal prediction generated with the same conformity score, and Pz is the distribution of clean input x.
Remark. The predictor here could be RSCP or RSCP+. By this definition, conservativeness measures the increase in the average size of prediction sets, when we try make the predictor robust to adversarial perturbations.
With this definition, we could study the efficiency robust conformal prediction methods by decomposing the average prediction set size into two parts: (1) The average size of vanilla conformal predictions C(x), using same conformity score and (2) the conservativeness. See Fig. A. where give intuitive illustration of these two parts. Fig. A. also provides intuitive idea of why should reduce the slope of score edf (i.e. reducing the probability density as shown in the figure) near the threshold to reduce conservativeness.
Empirical study. We conduct an empirical study into these two parts on the CIFARI0 10 dataset, with HPS as the non-conformity score. The results are shown in Tab. A.1. In order show better comparison, we choose the RSCP benchmark because the baseline only gives trivial results on RSCP+. As shown in the table, our PTT method has similar average size for the first part but reduced the conservativeness significantly. This verifies the intuition we get from Fig. A.1.
18

---

Published as a conference paper at ICLR 2024
Avg. Size of robust predictions [C,(2)
Avg. vanilla CP with random-
cons.
ized smoothing score [Caz)]
Baseline
2.108
1.482
0.626
PTT 1.779
1.468
0.311
Size reduction
0.329
0.014
0.315
Table A.I: Comparison of conservativeness: Our PTT method largely reduces the conservativeness of RSCP.
Dataset
CIFARIO
CIFAR100
ImageNet
Average size
10
100
1000
Table B.I: Baseline results with holdout set Dholduut added calibration set.
B FURTHER DISCUSSION ON PTT METHOD IN SEC 4.1
B. EXCHANGEBILITY RANK-TRANSFORMED SCORES
In the ranking transformation discussed in Sec, 4.1, we introduce the ranking transformation Drank- concern on this transformation will be, since both test scores and calibration scores rely on this holdout set, would the guarantee of conformal prediction be broken as they no longer independent? Here, we show that the guarantee still holds as the ranking transformation keeps the exchangeability between scores. Denote P. Qrank (S(, U:)) the calibration scores and Pa+1 = Qrank (In+11, (In++119++1)) We want to show that PL, P2, Pn+1 are exchangeable. For any permutation P. P.zi" P P.nt1 consider its pdf, have
PP,, Pip Pinti (2,, ,4n+1)
= / PPa,Pezi Plups Presse (t1, t2. An+1 D)p (DydD
II PPi.) Drossa (ty D)P Drussun (D)dD
(B.1)
(Given Drokdout
D, the scores become conditionally i.i.d.)
n+1
II 1=1
Pryl Prosson (t, D) (D)dD
-P Pa (11, 12, lnt1).
Thus, after the ranking transformation, the scores are exchangeable, hence satisfy the condition of conformal prediction.
B.2 CONCERNS ON ADDITIONAL DATA
As we discussed in Sec. 4.1, our PTT method requires an additional holdout set. order to address the concern that our PTT benefits from using more data, added the holdout set to the calibration set for the baseline method, so that the number of additional data samples will be the same for our PTT and baseline. With this modification, found that the baseline still gave trivial prediction set with all labels.
B.3 RANKING TRANSFORMATION TURNS SCORE DISTRIBUTION INTO UNIFORM DISTRIBUTION
Theorem B.8. (Qrmk o S)x y) is discrete random variable, Distoee |Dentorr with equal probability.
which takes values
This result well-known in statistics and we refer to Corollary Kuchibhotla (2020) that presented similar results, and Section 2.4 in Kuchibhotla (2020) for the proof.
19

---

Published as a conference paper at ICLR 2024
1.0
10
0.8
0.8
0.6
0.6
0.0
Figure B.1: Comparison of score edf before(left) and after(right) Sigmoid transformation. The red dotted line denotes the desired coverage 1 1- a. The left figure shows the edf of uniformly distributed score after the ranking transformation. The right figure shows edf of (S). We could see that Sigmoid transformation greatly reduced the slope near threshold (r = Φ 2--(1 a), corresponding to the intersection of the red line and the blue curve).
B.4 DESIGN CHOICE OF SIGMOID TRANSFORMATION
As we discussed in the main text, our goal is to design a monotonically increasing transformation that reduces the slope I's (T). After ranking transformation, the distribution of scores is turned into uniform distribution, i.e. + (t) Sigmoid transformation, the edf becomes
Recall that Quig = & [(s b)/7). Thus, after applying
Ona es
2xig
(B.2)
and the derivative becomes
Qup am (2 = 2 1000(1))
(B.3)
The slope at the threshold is
V QmL
Dzig 2ug (7)
D'ig -a)]
① eup ems (T) -1 a)
(B.4)
b
(Definition of Qug)
By choosing b 1 a, the right hand side equals /. Hence, with T large enough, we could achieve our goal of reducing 4 2 2.m as discussed above.
B.5 DISCUSSION ON MONOTONICITY CONDITION
In Sec. 4.1, we introduced two conditions for our desired transformation. One of these is the monotonicity condition which requires the transformation to be monotonically increasing. this section, discuss the reason we designed this condition and verify that the PTT we proposed satisfies this condition.
Monotonicity ensures transformed scores keep the information. By applying the transformation, we hope the new score could become more robust to adversarial perturbations while maintaining the performance on clean examples. The monotonicity condition ensures this by the following theorem:
Theorem B.9. For a monotonically non-decreasing transformation Q, the new score Q o S is equivalent to S in vanilla conformal prediction, i.e. they generate the same prediction set on all examples.
Proof. Denote the threshold and prediction set generated by original score S as Ty and C (æ)) Denote the threshold and prediction set generated by score Q S TooS and @oS (x:). From
20

---

Published as a conference paper at ICLR 2024
the construction of the prediction set in vanilla conformal prediction (Eq. (3)), to show two prediction sets are identical, we only need to show
(z. v) Ts Q 5(x, S TQ.S
(B.5)
Recall that the threshold is calculated as a1 + 1/1Daall empirical quantile of calibration scores. Suppose for original score S, Ts is the conformity score of i-th calibration example, i.e. Ts = ( Vs). We argue that TQ-s is also from i-th calibration example, i.e. TQss Q S(r; because monotonically non-decreasing transformation does change the order of calibration scores. Then Eq. (B.5) becomes
S(x, v) S S(ma,)))) - Q S(x, (1r v) S Q $(11.3))
(B.6)
This could be directly derived since Q is monotonically non-decreasing.
PTT satisfies monotonicity condition. In order to verify this, we need show both 2rank and Qui are monotonically non-decreasing. For Qrank, rank function is non-decreasing. For Qsg. the Sigmoid function ø non-decreasing, hence Qsig is also non-decreasing for any > 0.
B.6 EMPIRICAL EVIDENCE FOR COVERAGE GAP REDUCTION BY PTT
In Sec. 4.1, we propose a transformation called PTT which satisfies slope reduction and monotonicity conditions. In Appendix B.7, analyze 1-D synthetic example and thcoretically show that our PTT satisfying the two conditions could alleviate the conservativeness RSCP. In this section, we study PTT empirically and show that our PTT satisfying these two conditions could reduce derivative & (T), thus reduce coverage gap Ogap. We apply PTT on the CIFARIO dataset and compare the empirical CDF of S, as shown in Fig. B.2. To make comparison easier, we present the inverse of edf. Note that
D's(T) 0'sl05' a = [(05 -(1-a)] a)
(Ds(T) 1-
1)
(B.7)
Hence, we could compare (T) by comparing ($ ($5)) )(( - a), the derivative of + at target coverage (1 a). Higher $3 - a)) means lower (T). As we could see in Fig. B.2, the transformed score Sprr has a higher derivative at 1 1 a = 0.9, thus 4')(T) is reduced.
150
SNTT
Syce
1.50
1.25
0.75
1.00
0.50
0.25
0.50
0.25
0.00
0.90
0.92
-0.50
(a) APS
(b) HPS
Figure B.2: Empirical inverse edf of Š on CIFARI0 test set, with base score HPS and APS. Comparing
two base scores: the original score S and our transformed score Sprts we see the derivative at 1 = 0.9 is larger for Sprr, indicating its (T))) is smaller.
21

---

Published as a conference paper at ICLR 2024
B.7 THEORETICAL ANALYSIS OF PTT ON A 1-D SYNTHETIC DATASET
In Sec. 4.1, we proposed PTT which applies a transformation on the base score to reduce conservative- In this section, provide theoretical analysis of our PTT method. Without any assumption on the data distribution, the analysis would be difficult. Hence, we construct a I-D synthetic dataset and analyze our PTT method on it.
Settings. Consider a 1-D binary classification problem where x E [-0.5, 0.5] and E {-1,1}. Suppose P(y = 1) P(y = 1) = 0.5 and
(U5. 0). (U 0.5),
y = -1; y 1.
x
Assume we use a linear model as the base model, where
x + 0.5,
x E [-0.5, 0.5):
a(x,y= 1)
1,
0.5;
0,
< -0.5.
and -1o--=-))=11-mm Note that under this setting the score distribution @surs is uniform. The reason is the ranking transformation Prank involves a sampling process and makes the analysis difficult. Since the purpose of introducing 2 make the score uniformly distributed, directly construct uniformly distributed score, so that we can omit Quank in the following analysis.
We study the HPS score here: SHPs ( =1
Remark.
Analysis. Note that under this setting, the two classes y and y -1 are actually symmetric. Therefore, in the analysis below, we focus on the class y -1. Denote hs(x) as the smoothed score Eq. (9) for class y = with base score S:
hs(2) & 5(x, y = o1;))
= (E8~N((000)) S(x + 6, -.)=
(B.8)
In this case, we could derive a close form expression for Otgap. (T)(T) and average size. Theorem B.10. For any monotonically non-decree non-decreasing base score S, the coverage gap Oguup is
gap a + + 1.
The average size is
(L (C(())
[2h (Tads) + 11
Tadj E (hs(-0..),hs(0.3))) Tadi E (hs(0.5), oc).
2
The derivative is (T) = K/(-25
We defer the proof to Appendix B.7.1. With Theorem 1. we could study how our transformation could help reduce average size. For S SHPs, have Surs (z, y -1)
f y
-1) = f(I, y = 1) and we could derive hs.. (r) and h's,,, (I) by Eq. (9). Next, we consider applying transformation @ on HPS. Under simplifying assumptions, we get: hsw (x) 2+0.5-b
assumptions and the derivation process, please Appendix B.7.1. Notice that both SHPS and our transformed score Sprr is monotonically increasing. Thus, could apply Theorem B.10 by plugging in corresponding S and derive the metrics interested in. We show results for different a in Tab, B.2.
and h's.,, (x: 1. For more details
Conclusions
By this example, we could see
1. The coverage gap Ggap reflects the conservativeness of RSCP. As could see in Tab. B.2, Ogpp is a good indicator of conservativeness of predictor. By reducing aggap we could make the average size smaller.
22

---

Published as a conference paper at ICLR 2024
2. O (T((T) Mc is good approximation for Ggap- In this case, M, 5. From Tab. B.2, could that Ogap = (T)(T) á. except for some cases where Ogaap upper-bounded by 10% (because agap S a.. This supports our linear approximation Eq. (23).
3. Our PTT could reduce the derivative (T)(T). Therefore, PTT is able to reduce the coverage gap agpp and improve efficiency.
4. By applying the Sigmoid transformation, the score converges to optimal score when
T + 0. See Appendix B.7.2 for formal statement and proof.
Base
[7))
Ckgap
Avg. Size
Conservativeness
Score
SuPs
0.07916
7.98%
0.98
0,08
0.01
SPrT
0.02
2.00%
0.92(-6.12%)
0.02
SμPs
0.2503
10.00%
1.15
0.25
0.001
Sprt
0.02
2.00%
0.92(-20.00%)
0.02
Surs 0.7916
10.00%
1.62
0.72
0.0001
SptT 0.02
2.00%
0.92(-43.21%)
0,02
Table B.2: Results for the 1-D synthetic example, comparing HPS SaPs and our transformed score Sprr- is set to 0.01 for all cases. The improvement relative to the baseline is shown in parentheses. From the results, could be seen that our transformation consistently reduce Ogap and average set size for different a.
B.7.1 PROOFS
In this section, we discuss the details the illustrative example. First, we present the derivation of Theorem B.10. Then discuss how apply Theorem B.10 to calculate metrics in Tab. B.2 for HPS SuPs and our transformed score Sprr-
Proof of Theorem B.10. Recall that hs(x) & 5(x,y=-1;o) Lemma B.11. If base score monotonically non-decreasing w.r.t. n, the hs(x)) is monotonically non-decreasing w.rl.
Proof. Suppose we have Φ1 I T2. From the monotonicity of S and the fact that the smoothing operation (5 well ④ preserve the monotonicity, we have
S(x d,y -) S S(z2 + 6, - -1), E
= Es-N10.07) [S(z) + &, -1] s ES-A(10,0)) [S(22 + 6,y 11]
hs((1) hs(22).
(B.9)
Lemma B.12. For any monotonically non-decreasing base score S, the function of is:
0,
( (-xx, hs(-0.))
(t(() = 2h 1 (t) +
t E
(B.10)
1,
I E (0s(
Proof.
gg(t) P(Š t)
P(Š(z,y= -1:0) stly = -1)
(Symmetricity)
P(hs(#) |1 y-11
P(x (t)
(Monotonicity of h(x))
(0,
e (-o0, hs( te (hs(-0.5), (0);;
= (t) +1,
(Distribution of x)
(B.1la)
1,
t (0s( oc).
23

---

Published as a conference paper at ICLR 2024
With Lemmas B.11 and B.12, we can prove following results: Theorem B.10. For any monotonically non-decreasing base score S, the coverage gap agaap is
gap a + gg (Tal) 1.
The average size is
R a )) Psu (c(x1)
22g (Fads) + +1,
Tadj E hns
2
Tadj E (0s().5), oc).
The derivative is ('((T)
Rig( 87'
Proof. By Eq. (22) and Lemma B.12 and note that - a < 1, we have a= 2 +1,
(5(())
(B.
which gives:
T hs( a
2
(B.13)
The coverage gap Orgapi
gup a addj
P (m.n)~PP (-1 $ Cc(z) 1 1)
(Symmetricity)
a P[S(1,, y =-1 > radj y
= a 1 -1
(B.14)
and the average size B( ey [x(x) can calculated as:
B( P(-1 1 C.(x)) + IP(1 E C.(x))
2P(hs(()) S Tadj)
(B.15)
21p(x S hig (Tadi)
( 22h (Tad)) + 1,
Tadj E (hs(-005), (O.5))
2
Tadj E (0.5) oo).
By Eqs. (B.12) and (B.13), the derivative can also be computed as
(T)(T) 2(h)')(T))
(B.16a)
M₂(-2)
Eq. (B.16a) is derived by the derivative of the inverse function:
[-)) (2)
(B.17)
Derivation of Tab. B.2. With Theorem B. we could study related metrics for HPS SHPS and our transformed score SPTT, only need to calculate hg(x)) and (2)).. By Eq. (9), derive:
h S (x) = SuPs (I,, y = -1;0)
Eg~N(0.02) Sups (I y = -1]
क -1
A(r + o, y = 1)e v dō
V2
(B.
s)+
-(r-a.3)²
e
25
8
25
/2T
0.5 r
0.5 T
I
0.5
+ (x + 0.5)
Tb
-
24

---

Published as a conference paper at ICLR 2024
hssss (z) could be computed by the chain rule:
Mssuss (x)
{ -1 [BomN(0.02) SHrs + y, = - -]]]
dr
(i- [BonN(a.O) Surs (r + S,y = -1]]
d Sa + 8, -1)
BS.N((0,07)
dx
(Ø- [BS Sups( 6,y -1]
BB-A((0,0)) [[(-0SSat850s]
(B.19)
Note that HPS satisfies the monotonicity condition, hence we could apply Theorem B.10 and Lemma B.12 by plugging in h = Sus (z). Next, we consider how to apply our transformation Q on HPS. In order to simplify the analysis, we make two assumptions:
1. We skip the ranking transformation which involves sampling a holdout set, therefore SPrT Quig S. We argue that in this case the HPS is already uniformly distributed and the ranking step is not necessary.
2. In the sigmoid transformation, where Qaig S ol ( function,
we let T - 0. For the sigmoid
<(x) 1 11,
4 0, b); x (T 0, 0,
(B.20)
1te 0,
Therefore, by taking the limit T + 0, the transformed score Sprr could be written as:
SpIT(2, v) = 0 I.
SHPs (x. v)
(B.21)
SHPs v) >
With these assumptions, we could apply Eq. (9), which gives:
hsm (I) SpIT(E, - 0;
-1)
= Es~N((, (1(=)dy=1)26)
+ [E5~((0.0 (626-0-0.5)
b x 0.5
Φ [
r + 0.5
(B.22)
and
hssm
(B.23)
Similar to SHPS, SprT is also monotonically increasing, thus we can apply Theorem B.10 and Lemma B.12 to get the results.
B.7.2 OPTIMALITY OF OUR PTT
Below we show that in this case, our transformed score could achieve the smallest derivative & (T) among all the base scores S with the same threshold т.
Theorem B.13. Among all monotonically increasing scores S with the same threshold t and 0 <
S(1 -1) < 1, (T) the sign function.
) is minimized by S(1; y -1) sgn(t + 2), where sgn(x) 1(x 2 0)
25

---

Published as a conference paper at ICLR 2024
Proof. From Theorem B.10, could that ('((7) k3(-3)- Hence, minimizing (')(F) is equivalent to maximizing k-(--2) From definition of h, we have
d. dx
d Φ [BS S(x + 6, -1]] hs(a)
= dr
D ('0-1[6o-vioo0) S(x 0,y - -1]]]
d EsLN(O,0 S(x + 0, -1). (Chain rule, derivative of inverse function)
dx
(B.24)
The second term
d
S(x + b, -1) (BmN((..0))
dx
d 1
S(x + E, 11)d
dx 2 d 1
(m-2)²
20 S(t, y -1dtt
(Let 6)
dx 2
1e-Ry? 20
S(1, y = - 11ddt
2
dx
1x-0 62a 20
02 e
S(1, y -1)dt
2
(a-1)
S(t. y = -1)at {
0
l 1-
(a-t)²
202
20
S(t
1)dt
2
0²
0c
00
12-2)2
0
dl
(0 5 S(1, = -1) 1)
2
g²
(B.25)
Note that the equality holds when S(t, -1 sgn(t - 2)) Plug
2 we get
de Es-Nio, 8(-g + d,y =
1's(-
2
o' 4 -- 1 (0,02) 3 + + -1]]
Es-N10,00) S( 3 + = -1)
(B.26)
4 (s(--)) -
Recall that hg(-g)) (Eq. (B.13), the denominator just E' (T(),, which a constant given T. The numerator is maximized by S(t, y -1 sgn(t + 4), giving the conclusion.
Remark. Note that the optimal base score is attained by applying our transformation on the HPS score, with I and T as in Eq. (B.20). This supports the asymptotic optimality of our transformation. 2
B.8
CASE STUDY: POTENTIAL FAILURE MODE OF PTT
A natural question would be: when will the PTT fail to boost the efficiency? Here, we provide special case where PTT will fail to boost efficiency. Suppose the data distribution is the same as we defined in the settings part of Appendix B.7. For the base score, let
0.5 + o(1),
x v -0.5; E -0.5,0.5)
Sa(r,y= = -1) = x 0.5,
(B.27)
0.5 o(1),
0.5,
and $s(x,y=11 S,(z, = 1). That is to say, the conformity score is slightly in favor the wrong class when (-0.5, 0.5). Here, we introduce ignorable small deviation (o(1)) so that
26

---

Published as a conference paper at ICLR 2024
the score will be above(below) the PTT threshold for v -0.5 and 2 0.5. Let 1 = b 0.5, by Eq. (B.21), the PTT score will be
{1. x - ---00-00.
SPTT
(B.28)
[0, E (-0.5, (0.5,
Similar to Appendix B.7.1, we could derive the smoothed scores:
hss (x) (1, y
-1)
0.6)
0.5)
2tr
0.5
0.5
0.5
0.5
+ (xr + 0.5)
$
$
2
0
2
0
(B.29)
and
So (x) = Sppr(2 -1)
- [SSNNi0 (0+65-0.5) + [05
-- (BSnN(0 (05---05) (-n565-440.5)
0.5
0.5
Since the scores no longer monotonically increasing, cannot directly apply Theorem B. to get closed-form solution. However, we could numerically calculate the CDF $ g. threshold know the smoothed score function. We choose the inflation level = 0.01 across experiments, and report the results Tab. B.3. The results show that for a = 0.3, the PTT method is worse than the original score. This indicates that theoretically, for specific base score, the PTT method could amplify the error and produce larger set.
and the average size (2())
However, this kind of failure mode is not observed in our experiments in Sec. 5, We argue that despite being theoretically possible, the failure case shown in this section requires (1) a carefully designed base score and (2) specific choice of 1 a and Henee, the chance that it happens in practice rare.
Base Score
Avg. Size
Conservativeness
S,
-0.620
0.512
0.012
SPrT
-1.245
0,504
0.004
Si
-0.464
0,529
0.029
0.2
Sprr
-0.536
0.511
0.011
Si -0,302
0.525
0.025
0.3
SPrT
-0.169
0.529
0.029
Table B.3: Results for the failure case study. Note that the average size increased after PTT when 0.3.
27

---

Published as a conference paper at ICLR 2024
1.0
S
S
0.2
SPIT
0.8
SPTT
0.6
0.0
0.4
-0.2
0.2
0.0
-0.50
-0.25
0.00
0.25
0.50
-0.4
-0.2
0.0
0.2
(a) Smoothed score 5.
(h) CDF af smoothed
g-
Figure B.3: Comparison between original score S. and PTT score SprT when = 0.3. (Left) Smoothed scores. (Right) CDF of smoothed scores. The red dotted line denotes the coverage level 1 - 0.5. The intersection between the dotted line and the CDF curve is the threshold т. From the figure, we could intuitively see that the CDF of the PTT score has larger derivative the threshold.
C FURTHER DISCUSSION ON ROBUST CONFORMAL TRAINING IN SEC 4.2
C.I DETAILS OF CONFORMAL TRAINING (STUTZ ET AL., 2021)
Conformal training (Stutz al., 2021) simulates calibration and prediction process on mini-batches during training. In training, each batch B is split into two subsets: calibration set Beal and prediction set Bpeed The threshold r calculated based on Beat, and the prediction sets C(x;; T) are generated for samples in Bpeed- Under this setting, S is function of trainable parameters 8. To emphasize this, we denote the base score as (a y) in this section. In order to perform back poock--rppggttinn to update 8, Stutz al. (2021) proposed to calculate soft threshold 7 and soft prediction set c(x, r="l)) as differentiable approxiamation of threshold 7 and prediction set (xr). We discuss the details next.
Soft threshold softt The calculation of threshold involves calculating a specific quantile of given set, which is not differentiable. To address this problem, smooth sorting methods (Blondel al., 2020; Cuturi al., 2019) are utilized to get smoothed version of quantile:
soft = Q (1S 3) (a.i))...)
(C.1)
where (5t0(()) denotes the q(1 + quantile of set H derived by smooth sorting.
Soft prediction set c(x, yi s00t In the prediction stage, Stutz et al. (2021) introduced a class-wise prediction function c(2, y) [0. 1] which represents the probability that label y included in the prediction set of x. The prediction set could now be represented as the collection of class-wise predictions: C(x) {y E [K] c(1, y)}- Using this notation, the vanilla conformal prediction (Angelopoulos et al., 2020) could be expressed as:
(1. 0.
So v) T; So 3) >
Chard (z, y:
which requires to perform hard-thresholding w.r.t. threshold r. Stutz et al. (2021) proposed to replace Chord by smooth version:
son So(r, v)
c(x, y 800t)
(C.2)
T Tiain
where d(2) 1/(1 t 2) the sigmoid function and temperature Train a Syper--arameter.
28

---

Published as a conference paper at ICLR 2024
C.2 DETAILS OF ROBUST CONFORMAL TRAINING (RCT)
In this section, we discuss some design details of Robust Conformal Training (RCT), We first introduce some problems suggested by Stutz et al. (2021) and show how avoid those problems.
Different from the conformal prediction method we introduce in Sec. 2.1, Stutz et al. (2021) used slightly different convention, where C(X;7') {k [K] S (" y) 2 J'} and threshold r' is calculated as the a<1 + 1/ L/aDell) Deaal)-quuatile of calibration scores. For example, S' (z, y) for THR (Sadinle al., 2019) and (z y) log म (x) for THRLP. We argue that these two conventions are actually equivalent. Let S(z y) -S (x. y) and = -T', we see now is the a1 =/lDeal)-qquattii of calibration scores and C(X:T)
(2)
[k E [K] S(X, I T}. which is consistent with the notations we introduce. For the consistency of notations, we make some modifications to the notations in Stutz et al. (2021) by swapping their signs in the rest of this section.
Regarding the choice of (non)-conformity score for training. Stutz al. (2021) mentioned gradient diminishing problem when using THR: STHR = -ty(x). Thus, they proposed to add a logarithm function to mitigate this problem, i.c. using THRLP: STHRLP doesn't work when we try to incorporate RSCP into the scheme: RSCP requires the base score choose to take value in [0, 1]. which is not true for SIHR and STHRLP- To solve this problem, HPS as the base score: since the difference between HPS and THR is only a constant, these two scores actually equivalent in the context of conformal training (Stutz et al., 2021). HPS takes value the interval [0, I]. which satisfies the requirement of RSCP. A potential problem with this choice is: suggested by Stutz et al. (2021), using HPS as the base score would cause gradient diminishing. Fortunately, we observe that the Gaussian inverse edf step 4- plays similar role to the logarithm function in Stutz et (2021), which alleviates the diminishing gradient problem and leads to successful training.
log Fy (z). However, this choice
29

---

Published as a conference paper at ICLR 2024
D EXPERIMENTAL DETAILS AND EXTENSIVE STUDIES IN SEC 5
In this section, we discuss more details of our experiments Sec. 5, and provide extensive empirical studies on the RSCP+ and PTT RCT methods we proposed.
D.1 EXPERIMENTAL DETAILS
Robust conformal training. For robust conformal training, Stutz et al. (2021) suggested, we freeze the backbone of the base model and train the last linear layer after randomly reinitializing Regarding the base score for training, see Appendix C.2 which discusses and CIFAR 100, standard data augmentation is applied which includes random flips and crops. In SGD with momentum 0.9 and Nesterov gradient. Weight decay is set 0.0005. We finetune the model for Nopoct: = 150 epochs and scale the learning rate down by 0.1 at epoch 60, 90 and 120. In Eq. (25), we choose Numin 8. For other hypee-paramettes, see Tab. D.1.
choice. For CIFARIO
training,
Dataset CIFARTO
Batch size
Learning rate
Tuiin in Sec. 4.2 0.1
Size weight
K in Eq. (26)
500
0.05
CIFARION 100
100
0.005
0.01
Table D.I: Hyperparameters setting for robust conformal training on CIFARIO and CIFARIO0.
Dataset split For RCT training, the training set of CIAFRIO and CIFAR100 is utilized. For evaluation, we split the validation set into three subsets: Dooldou for ranking transformation in Sec. 4.1, 1, Deal for calibration, and Drea for evaluation refer to Tab. D.2. We want to point out one thing that in all experiments we employ the random calibration-tess split suggested by Gendler et al. (2021). That means we fix training set Durain and holdout set Dholdout. while randomly split the remaining data into Deal and Drest for N 50 times. For each random split, calibration performed on Deal, and prediction results are evaluated on Drest- For fair comparison, calibration is performed on Droidou U Deat), as they do not need this holdout set. All the metrics we present the average of Napin 50 experiments.
results. For the size of each subset, please
add the holdout set to the calibration set for the baseline method (i.e.
Dataset
training
holdout
calibration
test
CIFARIO
50000
500
4750
4750
CIFARTO0
50000
500
4750
4750
ImageNet
500
24750
24750
Table D.2: Spilt each dataset. Note that on ImageNet we only experiment PTT method which training-free, therefore, the training set for ImageNet is omitted.
D.2 EMPIRICAL RESULTS ON RSCP BENCHMARK
In this section, we present experiment results under the original RSCP benchmark (Gendler et al., 2021). As point out in the main text, their approach is flawed in robustness guarantee, but still serves as a simple empirical benchmark. For empirical robustness with RSCP, we follow the evaluation of Gendler al. (2021) which uses SmoothAdv (Salman et al., 2019) to generate adversarial examples and examines the coverage and average size on these examples.
The results are shown in Tabs. D.3 and D.4. First, we could see that all methods achieve coverage above a 90% under SmoothAdy attack, suggesting that our methods preserve the empirical robustness of Gendler et al. (2021). Compared with the baseline, our methods are closer to vanilla CP and have smaller coverage gap Oggap- Next, focusing average prediction set size, which the key metric evaluating the efficiency of conformal prediction, our methods provide reduction up to 31.12%, 25.80% and 48.80% CIFAR10. CIFAR 100, and ImageNet respectively. Note that PTT method provides the first result on the ImageNet dataset to improve the size of robust conformal prediction without training. The conformal training methods in prior work (Einbinder et al., 2022b;
Results.
30

---

Published as a conference paper at ICLR 2024
Vanilla CP
RSCP Ours
3.0
Vanilla CP
RSCP Ours
0.9
90% guarantes
2.5
Improv. 30%
Improv.
29%
2.0
Coverage
0.6
Average Set
1.5
0.3
Invalid
1.0
0.5
0.0
0.0
clean test set
adv test set
clean test set
adv test set
(a)
(b)
Figure D.I: Comparison of vanilla conformal prediction (Vanilla CP) (Romano et al., 2020), vanilla RSCP (Gendler et al., 2021) and our proposed method PTT + RCT with RSCP on (a) coverage guarantees and (b) average prediction size on CIFARIO. Our methods achieve better (smaller) average set size than RSCP while satisfying coverage guarantees on the adversarial test set. Note that Vanilla CP does not achieve the desired 90% coverage guarantees on the adversarial test set. The non-conformity score applied here is APS (Romano et al., 2020).
CIFARIO
CIFAR
APS
HPS
APS
HPS Average size 1
Method
Coverage Average size
Coverage
Average size 1
Coverage
Average size J
Coverage
Baseline
95.68%
2.751
54%
2,108
93.53%
16.19
93.43%
14.30
(Gendler at. 2021)
PTT (Ours)
92.06%
2.202 19.99.990 969))
90.90%
1.779 (-15.61 %)
91.26%
12.78 (-21.06%)
90.87%
10.78 (-24.62%)
(-31.12%)
(-11.57%)
(-25.80
Table D.3: Coverage and average size on CIFAR 10 and CIFAR 100 with RSCP. Results are presented adversarial examples generated by SmoothAdv(Salmmn
al., 2019) with magnitude 0.9 and the smoothing strength
0.125. The target coverage is 1 improvement relative to the baseline is shown in parentheses and the best results are bold. Our method consistently gives prediction sets with smaller sizes, and it can be seen that the robustness of RSCP holds empirically.
0.25. The
APS Coverage Average size |
HPS
Method
Coverage Average size
Baseline(Gendler et al., 2021)
95.36%
51.72
94.12%
16.64 8.52 (-48.80%
PTT (Ours)
91.17%
30.20 (-41.61% %)
90.53%
Table D.4: Coverage and average set size results for ImageNet with RSCP. Results presented on adversarial example with magnitude e = 0.25, target coverage a = 0.9 and o = 0.5. The improvement relative to the baseline is shown in parentheses.
Stutz et al., 2021) require training, which might be costly when the base model is large and does not scale to larger datasets like ImageNet.
RSCP
RSCP+
C
0.125
0.25
0.5
0.125
0.25
0.5
Baseline
2.108
3.303
5,759
10
10
10
PTT
1.779
2.578
4.222
2.152
3.269
5.559
PIT+RCT
1.864
2.642
4.245
2.152
3.413
5.603
Table D.5: Average size for different on CIFAR10 dataset, with RSCP and RSCP+. Our methods consistently improve over the baseline.
31

---

Published as a conference paper at ICLR 2024
RSCP
RSCP+
0.125
0.25
0.5
0.125
0.25
0.5
Baseline
1.999
2.108
2.573
3.78
10
10
10
10
PTT
1.622
1.779
2.244
3.434
3.341
2.152
2.916
4.663
PIT+RCT
1.705
1.864
2.296
3,473
3.282
2.152
3.059
4.735
Table D.6: Average size for different CIFAR10 dataset, with RSCP and RSCP+. Our methods consistently improve over the baseline.
D.3 EXPERIMENTS WITH DIFFERENT AND O.
In this section, we extend our experiment on the CIFARIO dataset to different and a. We conduct experiments under two settings: (1) We fixed
2- and used c = 0.125, 0.25, 0.5. The results are in Tab. D.5 (2) We fixed 0.125 and tried a 0. 12,, 0.25, 0.5, 1. The results are in Tab. D.6. Both experiments are carried out the CIFARIO 10 dataset with HPS score. For the RSCP+ benchmark, we apply the Empirical Bernstein's 's improvement introduced in Appendix A.3.3. Other hyperparameters are the same the experiments methods consistently give a smaller average size, compared with the baseline (Gendler et al., 2021). This supports our claim that methods could improve the efficiency, for both RSCP and RSCP+.
present in Sec. 5. From Tabs. D.5 and D.6, we could see that our
D.4 ABALATION STUDY
In this section, we study the necessity of robust conformal training introduced in Sec. 4.2 by comparing with Conformal Training (ConfTr)(Stutz et al., 2021). The experiments are carried out using the original RSCP benchmark, so we introduce RSCP (Gendler et al., 2021) as baseline. As illustrated in Tab. D.7, ConfTr generates up to 66.08% larger prediction set than no conformal training. which is undesired, while with our RCT, we can reduce the size up to 17.52%, which supports the necessity of our RCT method. The reason may that conformal training is not specifically crafted for randomized smoothing.
APS
HPS
Training Method
Coverage
Average size |
Coverage
Average size J
Baseline(Cohen et al., 2019)
95.68%
2.751
93.54%
2.108
ConfTr(Stutz et al., 2021)
90.21% %
3.509 (+27.55%)
90.39%
3.501 (+66.08%)
RCT (Ours)
93.15%
2.269 (-17.52%)
91.25%
1.929 (-8.49% %)
Table D.7: Ablation study: We compare our robust conformal prediction (RCT) with conformal training (ConfTr) (Stutz al., 2021) on CIFARIO dataset. It could be seen that applying ConfTr to train a base classifier for RSCP results in performance even worse than the baseline which uses the original weights by Cohen al. (2019), supporting the necessity of our method.
D.S STANDARD DEVIATION OF EXPERIMENT RESULTS
In this section, we present the standard deviation of our experiment results.
Base score
HPS
APS
Dataset
CIFARIO
CIFAR
CIFARIO
CIFAR 100
Baseline (Gendler et al., 2021)
10
100
10
100
PTT (Ours)
2.294 + 0.051
26.06 15.48
2.685 + 0.037
21.96 + 1.055
PTT+RCT (Ours)
2.294 + 0.051
18.30 1.08
2.824 + 0.047
20.01 0.94
Table D.8: Average size of RSCP+ on CIFAR10 and CIFAR100. with standard deviation. For CIFAR10 and CIFARI00, e = 0.125 and a = 0.25. For the large standard deviation with PTT on CIFAR10 using HPS as base score, the reason the predictor gives a trivial prediction during 50 tests. We argue that the probability is small and could be alleviated by applying RCT or increasing the number of Moute Carlo samples.
32

---

Published as a conference paper at ICLR 2024
Base score
HPS
APS
Baseline (Gendler et al., 2021)
1000
1000
PTT (Ours)
1000
94.66 1 130.97
PTT + Bemstein (Ours)
59.12 - 135.87
70.87 3.69
Table D.9: Average size of RSCP+ on ImageNet. with standard deviation. For ImageNet, 0.25
and a = 0.5. Some entries in the table have large standard deviations. The reason is the predictor gives trivial prediction during 50 tests. We argue that the probability is small and could be alleviated by increasing the number of Monte Carlo samples.
APS
HPS
Method
Coverage
Average size +
Coverage
Average size +
Baseline
95.68% + 0.30%
2.751 0.031
93.54% = 0.48%
2.108 + 0.036
(Gendler et al., 2021)
PTT (Ours)
92.06% + 0.40% 91.15% + 0.48%
2.202 = 0.029
90.90% = 0.61%
1.779 + 0.029 1.864 0.027
PTT RCT (Ours)
1.895 0.033
91.19% = 0.51%
Table D.10: Coverage and average size on CIFAR 10 with RSCP with standard deviation.
APS
HPS
Method
Coverage
Average size |
Coverage
Average size |
Baseline
93.53% + 0.44%
16.19 0.47
93.43% + 0.47%
14.30 0.43
(Gendler et al., 2021)
PTT (Ours)
91.26% + 0.55% 91.07% + 0.59%
12.78 + 0.34
90.87% + 0.61%
10.78 + 0.36
PTT + RCT (Ours)
12.32 + 0.38
90.83% + 0.58%
10.61 + 0.32
Table 1: Coverage and average size on CIFAR 100 with RSCP with standard deviation.
APS
HPS
Method
Coverage
Average size |
Coverage
Average size |
Baseline
95.36% + 0.14%
51.72 + 0.819
94.12% = 0.21%
16.64 + 0.387
(Gendler et al., 2021)
PTT (Ours)
91.17% + 0.19%
30.20 + 0.609
90.53% + 0.23%
8.52 + 0.175
Table 1.12: Coverage and average set size results for ImageNet with RSCP with standard deviation.
D.6 EXTENDED STUDY ON THE IMPACT OF NMC
NMC
128
256
512
1024
CIFARIO0
39.95
26.06
13.60
12.43
ImageNet
1000
59.12
19.68
10.34
Table D.13: Average size vs. Number of Monte Carlo samples NMC- The experiment conducted with PTT method. The base score is HPS. could be seen that by increasing the number of Monte Carlo examples, we could further improve the efficiency of RSCP+, at the cost of higher computational expense.
In Sec. 5, study the impact of the number of Monte Carlo samples NMc RSCP+ + the CIFAR1O dataset. this section, we extend the study to CIFARI00 and ImageNet. As shown in Tab. D.13, the average size could be reduced by increasing the number of Monte Carlo examples.
33

---

Published as a conference paper at ICLR 2024
D.7 IMPACT OF T
In this section, we conduct an empirical study on the impact of hyperparameter in PTT. We choose the CIFARIO dataset with HPS the base score. The results are shown in Fig. D.2. It could be that when choosing 7' large enough, our method is not sensitive to the choice of T.
2.7
Average
2.6
2.5
2.4
2.3
2.2
25
50
100
200
400
800
1600
T
Figure D.2: Average size of prediction set vs. different T.
34

---

Published as a conference paper at ICLR 2024
D.8 COMPUTATIONAL OVERHEAD OF OUR METHODS
In this section, we discuss the computational overhead of our methods, PTT and RCT. The overhead could be divided into two parts: training and test-time cost.
Training cost. Our PTT method is training-freet hence it doesn't 't introduce any cost for training. For RCT, we compare the training time of RCT and ConfTr (Stutz et al., 2021) on the CIFARIO dataset. For both of the methods, the last linear layer is finetuned for Neooch 150 epochs on NVIDIA V100 GPUs. RCT takes around minutes while ConfTr takes around 50 minutes. We argue that this computational overhead stems from randomized smoothing: training base model for randomized smoothing requires sampling a batch of examples for each training example (Cohen et al., 2019; Salman et al., 2019; Zhai et al., 2020), which significantly increases the computational expanse.
Test-time cost. During test time, our RCT method is equivalent vanilla RSCP (Gendler et al., 2021). No additional expense is needed. For PTT, since transformation is applied on base score $ test time, there would be computational overhead: see Fig. D.3. Diving deeper into each step.
1.2
RSCP
1.0
0.8
Time/ms
0.6
0.4
0.2
0.0
HPS
APS
Figure D.3: Score computation time for each example CIFAR10 dataset. Comparing vanilla RSCP (RSCP) and RSCP with our training-free transformation (ours), it could be seen that the computational overhead is about 10%. Note that our robust conformal training method does not introduce additional computational cost at the test stage. The experiment is performed on 2 NVIDIA V100 GPU.
could see that the computational cost for each example is O(NMc log Drotdout |) for ranking transformation and O(NMc K') for sigmoid transformation. Therefore, the overall cost would be (NNMc log Droldouel). We emphasize that this cost does not scale with the cost of the base model, which is desirable because enables users to employ arbitrarily large base models without increasing the computational overhead of PTT.
35

---

Published as a conference paper at ICLR 2024
E OTHER RELATED WORKS IN ROBUST CONFORMAL PREDICTION
Besides Gendler et al. (2021), there are other related works that studied robust conformal prediction (Einbinder al., 2022a: Ghosh al., 2023; Bastani al., 2022). Bastani et al. (2022) focused on an online setting where the defender could interact with the attacker and collect information on adversarial distribution from history inputs, which is different from our setting which assumes the defender does not have information on the distribution of adversarial noises, except the assumption that they have limited norm. Ghosh et al. (2023) studied probabilistically robust conformal prediction. Formally, they studied the following guarantee:
Px E C(ān+1 = In+1 + 8)} 2 1 - at
(E.1)
As Ghosh et al. (2023) pointed out, this could be regarded as a relaxed version of the adversarial robust coverage guarantee defined in Eq. (2): probabilistically robust conformal prediction provides guarantee for perturbation following specific distribution, while our RSCP provide adversarial robustness guarantee for any perturbation that satisfies ||ō||2
36

---

Published as a conference paper at ICLR 2024
F
TABLE OF SYMBOLS
Symbol
Description
C(x)
Prediction set input æ
(7++1,8x+1)
Test imput and corresponding label
Pzy
Joint distribution of input a and label y Perturbed test input
Ent1
a
Target level of coverage
Magnitude of adversarial noise
(x)
RSCP prediction set with noise level
D Durin
Training dataset
D cal
Calibration dataset
Probability output of classifier
S
(Non-jconformity score function
Randomized smoothed score defined by RSCP (Gendler et al., 2021)
Threshold of vanilla conformal prediction
Tadj
Adjusted threshold introduced by RSCP (Gendler et al., 2021)
d
Cumulative density function standard Gaussian distribution Randomized smoothed score defined in Eq. (9)
Srs
SrS
Monte Carlo estimator for SpS
Smoothing strength of randomized smoothing The p(1 + 1/ -empirical quantile of set H Prediction set of RSCP+ with noise level e Coverage gap introduced by RSCP (Gendler et al., 2021)
(H)
(xr)
Ogga
Cumulative density function of Š Transformation on base conformity score Number of Monte-Carke examples used in RCT
Q
N Nuain
NMc
Number of Monte Carlo examples in calibration and test stages Number random calibration-test split in evaluation
N pli
b, T
Hyper-parameters of Sigmoid transformation
Table F.1: Symbol table
37


Reviews:
[{"review_id": "ptRPVzmBco", "reviewer": "Reviewer_Tjzn", "summary": "This paper identifies two limitation of Randomized Smoothed Conformal Prediction (RSCP): (1) its robustness guarantee is questionable in practical applications; (2) it often yields large uncertainty sets. To address the first problem, the paper propose a novel framework called RSCP+ to provide provable robustness guarantee. For the second issue, the paper introduces two innovative techniques: Post-Training Transformation (PTT) and Robust Conformal Training (RCT), reducing prediction set size.", "questions": "1. The Theorem 1 in [R1] provides a guarantee for RSCP prediction set; moreover, I didn't find noticeable coverage violation in empirical results. Thus, I'm confused why you refine the non-conformity score to bound the estimation error?\n\n2. Can you share the result of PTT+RCT of RSCP+ on ImageNet?\n\n3. Can you conduct additional experiments on the impact of number of Monte Carlo on RSCP+?\n\n4. Considering sigmoid transformation, how you determine the optimal value for $T$.\n\n5. Although PTT and RCT successfully improve efficiency (as shown by empirical results), I don't understand your statement that the coverage gap $\\alpha_{gap}$ reflects the conservativeness of RSCP. Can you provide more theoretical or empirical explanation?\n\n6. In Section 4, the paper points out that RSCP and RSCP+ is conservative: RSCP gives a larger prediction set on both clean and perturbed data; this conservativeness then passes on to RSCP+, as supported by Table 1 and Table 2. However, the complementary results in Appendix I don't strongly indicates RSCP is conservative: for example, on Cifar-10, RSCP generates prediction sets of average size 2.751 based on APS. Is it improper to say that RSCP+ is conservative simply because it builds upon RSCP?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This approach is novel and theoretically sound for conformal prediction. This paper considers the conformal prediction in an adversarial setting where exchangeability is violated; thus traditional methods fail to guarantee coverage. The authors improves RSCP by adjusting its non-conformity score and bounds the estimation error. \n\n2.  This approach is theoretically grounded and computationally efficient. This paper designs two post-training transformation functions: Ranking Transformation and Sigmoid Transformation, aim at minimizing $\\alpha_{gap}$ by reducing the slope of $\\Phi_{\\tilde{S}}(\\tau)$.\n\n3. Inspired by conformal training, the authors propose robust conformal training to enhance efficiency at training stage. Empirical results show that this method is efficient.", "weaknesses": "1. RSCP+ fail to construct informative prediction sets independently: it tends to give the whole prediction sets (include all classes) as observed on Cifar-10, Cifar-100, ImageNet.\n\n2. RSCP+ generates relatively large prediction sets on dataset such as ImageNet even with PTT, limiting its application.\n\n3. The impact of number of Monte Carlo on RSCP+ remains ambiguous, since the experiment is only conducted on Cifar-10.", "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": "J3CryG5MTs", "reviewer": "Reviewer_mH5T", "summary": "This paper tackles the problem of robust conformal prediction under adversarial perturbations. The authors study the RSCP framework, a combination of randomized smoothing and conformal prediction, proposed previously, and 1) identify a technical flaw in RSCP's certification guarantee due to the Monte Carlo estimation of the non-conformity score. 2) propose a modified RSCP (RSCP+) framework that circumvents this issue to provide a solid certificate in practice, and 3) propose two new techniques for improving the efficiency of the prediction sets based. The first one (PTT) is a training-free method for computing the non-conformity scores, based on a simple yet effective transformation. The second (RCT) is a training-based approach to improve the robust conformal training of the base classifier itself. Combining PTT+RCT, the authors evaluate their new RSCP+ framework on a variety of network architectures and datasets, showcasing their effectiveness.", "questions": "- The PTT method requires another set of held-out, independent of the calibration set. In order for a fair comparison with vanilla RSCP+, would it make sense to have the combined holdout and calibration sets as the baseline calibration set for vanilla RSCP+? This would eliminate any notion of PTT improvement coming from having access to more data, rather than the transformation.\n\n- How were the adversarial examples constructed? is it vanilla PGD? or similar to the SmoothAdv [Salman et al., 2019] paper?\n\n- How well does the RSCP+ framework perform on unperturbed data? are the prediction sets also trivial for clean data?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper tackles an important subject: uncertainty quantification via conformal prediction in the presence of adversarial perturbations\n- The paper is well written for the most part (see Weaknesses for some comments), and the authors go into great lengths to provide details, as seen by the dense Appendix. Technical contributions look sound to me.\n- The paper correctly identifies a technical flaw in a prior framework (RSCP), and presents a correction based on the Hoeffding bound to establish a sound framework: RSCP+\n- The proposed efficiency enhancing techniques (PTT and RCT) seem to perform well in practice.\n- The authors verify their results on three vision benchmarks: CIFAR10, CIFAR100, and ImageNet", "weaknesses": "- The paper, to its credit, tackles three different techniques, which has unfortunately degraded the reading experience. The proposed techniques have little to do with each other, and jumping between them was a bit hard to grasp in the first few reads. Having to fit all this in the page limit certainly does not help the authors. There is also an over reliance on the Appendix, which made the reading experience very choppy. I am not sure what is the best way to tackle this frankly.\n\n- One thing I found missing was that, if the original RSCP framework is flawed (due to practical limitations of having to rely on Monte Carlo sampling to estimate the non-conformity scores), then why does it still work well in practice? The explanation in Appendix A makes it seem like the method will yield catastrophic results, but that does not seem to be the case. It would greatly improve the motivation for this work if this part is properly explained, preferably in the main text, as it is key to the main motivation for this work.", "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": "y0YfA61Cvb", "reviewer": "Reviewer_SvdF", "summary": "This paper studies the robust conformal prediction with the existence of adversarial noise. The authors first point out that the existing method **RSCP** has two major limitations in practice, and then propose a new framework named **RSCP+** to address two issues. To further reduce the size of the prediction set, this paper also develops two methods, PTT and RCT. Plenty of experiments are conducted to verify the effectiveness of RSCP+.", "questions": "1. Is the ranking-transformation technique proposed in your paper or already proposed in previous work? If the latter, the citation should be added.\n\n2. Why does the Sigmoid transformation require uniformly distributed scores?\n\n3. For the ranking transformation, the new score $Q_{rank}\\circ S_i$ is uniformly distributed when we consider the randomness from both $S_i$ and the hold-out set. In this vein, the new calibration scores $Q_{rank}\\circ S_{i}: i=1,...,n$ and the test score $Q_{rank}\\circ S_{n+1}$ are no longer independent. How can we guarantee the validity of RSCP+?\n\n4. Is there any particular reason why the regression problem is not considered?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The background of this problem is well illustrated.\n\n2. The framework of RSCP+ is more efficient compared with the existing RSCP. The novelty of this method is also significant.\n\n3. Two specific methods PTT and RCT make this new framework more practical.", "weaknesses": "Overall, I think this submission is a good paper, but I have the following concerns.\n\n**1. The literature review is not sufficient and complete.**\n\nFor the conformal prediction with adversarial noise, this author discussed only one related work Gendler et al. (2021). However, I find that a published work [1] is closely related to this problem. The authors should clarify the differences between the submission and [1]. In addition, [2] and [3] are also related works.\n\n**2. The difference between RSCP+ and RSCP should be discussed earlier.**\n\nAs the most important contribution of this paper, the algorithmic design of RSCP+ appears until Page 4. It would be better to summarize the main idea or unique part of RSCP+ in the Introduction.\n\n**3. The empirical comparison to [1] and [2] should be added to the experiments.**\n\n[1] Ghosh, Subhankar, Yuanjie Shi, Taha Belkhouja, Yan Yan, Jana Doppa, and Brian Jones. \"Probabilistically robust conformal prediction.\" In Uncertainty in Artificial Intelligence, pp. 681-690. PMLR, 2023.\n\n[2] Bastani, Osbert, Varun Gupta, Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. \"Practical adversarial multivalid conformal prediction.\" Advances in Neural Information Processing Systems 35 (2022): 29362-29373.\n\n[3] Einbinder, Bat-Sheva, Stephen Bates, Anastasios N. Angelopoulos, Asaf Gendler, and Yaniv Romano. \"Conformal Prediction is Robust to Label Noise.\" arXiv preprint arXiv:2209.14295 (2022).", "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": "ndgkRQJfzG", "reviewer": "Reviewer_y2Uk", "summary": "This paper proposes three main improvements over RSCP. It first built upon RSCP and use a high probability bound for the smoothed score approximation, in order to provide a more rigorous coverage guarantee in the adversarial setting. Then, it provides two tricks to improve the efficiency of the prediction sets. The first involves a general pipeline to modify the conformity score. The second is re-training the base model by mimicking the conformal prediction steps. The results suggest that the final method works better than the RSCP baseline.", "questions": "1. Is the intuition behind slope reduction that we \"zoom in\" to the nonconformity score around its 1-\\alpha quantile? My intuition is that this essentially \n\ta. Section D.2 seems to be constantly flipping/inconsistent between maximizing/minimizing - are these mistakes?\n\tb. While the coverage guarantee always holds, are there cases where the PTT transform hurts the efficiency? For example, it seems like the optimality proof hinges on the unfiorm distribution, and if the noise is adversarial to this sigmoid transformation can PTT actually inflate more? It's just a bit difficult to imagine a transformation is dominating the original score.\n2. How do we choose $T$ in practice? Obviously we have to fixed it ex-ante to avoid breaking the i.i.d. condition? In fact, given the proof/theorem, what prevents us from using $T=\\infty$?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The problem (first identified in the RSCP paper itself) about the missing step of high-probability bound is real, and this paper provides a good solution.\n2. The PTT steps are quite interesting and could work with any nonconformity score (although it's not clear whether the efficiency is always improved).", "weaknesses": "1. It seems like RCT is not making too much difference, and it requires retraining the model. While it is an interesting idea, I wouldn't say the experiment supports that this helps, and is kind of distracting from the main idea of the paper.\n\n2. It is unclear how to select $T$ (and to some extend $\\sigma$).\n\n3. Missing discussion of potential failure mode (see Q1)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)