Adversarially Robust Conformal Prediction
Authors: Asaf Gendler
Tsui-Wei Weng
Luca Daniel
Yaniv Romano
Venue: ICLR 2022 Poster (2022)
Keywords: Conformal Prediction
Adversarial Robustness
Randomized Smoothing
Uncertainty Estimation
Calibration

Abstract: Conformal prediction is a model-agnostic tool for constructing prediction sets that are valid under the common i.i.d. assumption, which has been applied to quantify the prediction uncertainty of deep net classifiers. In this paper, we generalize this framework to the case where adversaries exist during inference time, under which the i.i.d. assumption is grossly violated. By combining conformal prediction with randomized smoothing, our proposed method forms a prediction set with finite-sample coverage guarantee that holds for any data distribution with $\ell_2$-norm bounded adversarial noise, generated by any adversarial attack algorithm. The core idea is to bound the Lipschitz constant of the non-conformity score by smoothing it with Gaussian noise and leverage this knowledge to account for the effect of the unknown adversarial perturbation. We demonstrate the necessity of our method in the adversarial setting and the validity of our theoretical guarantee on three widely used benchmark data sets: CIFAR10, CIFAR100, and ImageNet.

Published as a conference paper at ICLR 2022
ADVERSARIALLY ROBUST CONFORMAL PREDICTION
Asaf Gendler', Tsui-Wei Weng", Luca Daniel?, Yaniy Romano"
1 Deparrmeen of Electrical and Computer Engineering, Technion - Issrall Institute of Technology
2 Deparimeet of Electrical Engineering and Computer Science, Massachusetts Institute of Technology
ABSTRACT
Conformal prediction a model-agnostic tool for constructing prediction sets that are valid under the common i.i.d. assumption, which has been applied to quan- tify the prediction uncertainty of deep net classifiers. In this paper, we generalize this framework to the case where adversaries exist during inference time, under which the i.i.d. assumption is grossly violated. By combining conformal pre- diction with randomized smoothing, our proposed method forms prediction set with sample coverage guarantee that holds for any data distribution with l2- norm bounded adversarial noise, generated by any adversarial attack algorithm. The core idea is to bound the Lipschitz constant the non-conformity score by smoothing with Gaussian noise and leverage this knowledge to account for the effect of the unknown adversarial perturbation. We demonstrate the necessity of our method in the adversarial setting and the validity of our theoretical guarantee on three widely used benchmark data sets: CIFARIO, CIFAR 100, and ImageNet.
INTRODUCTION
Deep neural net classifiers have achieved tremendous accomplishments over the last several years. Nevertheless, the increased deployment of these algorithms in real-world applications, especially ones that can be life-threatening like autonomous driving, raises major concerns about their reli- ability (Heaven] 2019). To alleviate these issues, it is important to develop techniques that allow the users assess the uncertainty in predictions obtained by complex classifiers, revealing their limitations.
Conformal prediction (Vovk et al. 2005) is simple yet powerful tool for generating prediction sets whose size reflects the prediction uncertainty. Specifically, suppose we are given n training examples ((X,, Y.) with feature vector X; Rd discrete and unordered class label YıE {1, .., L} V. and any learning algorithm that aims at predicting the unknown Yn- of a given test point X Under the assumption that the training and test examples sampled exchangeably-e.2g they may be drawn i...d-from an unknown distribution Pxy, conformal prediction algorithms construct a distribution-fir prediction set C (Xn+1) S y guaranteed contain the test label Yn+1 any desired coverage probability 1 - E (0,
P P|Yn+1 E (Xn+1)) 1-
(I) be 90% 95%. Note that
For example, common set the desired coverage level
the coverage probability IP [Y=+1 E (X,+1) is marginal because it is taken over all the training examples {(X,, YO) and the test point Xn+1- The key idea of conformal prediction to fit classifier on the training set and use this model to assign non-conformity scores for held-out data points. These scores reflect the prediction error of the underlying classifier, where, loosely speaking, smaller prediction error would lead to the construction of smaller and more informative sets.
However, the sets constructed by the vanilla conformal method may not have the right coverage when the training and test points violate the exchangeability assumption (Cauchois et al., 2020 Gibbs & Candès) 2021; Tibshirani et al. 2019 Podkopaev & Ramdas 2021 Guan & Tibshirani,
2019), which is hardly satisfied by real data in practice distribution shift happens frequently (Koh)
et al. 2021). In particular, we consider the potential threat adversarial attacks (Goodfellow et al.
2015 Szegedy al. 2014; Carlini & Wagner, 2017) carefully crafted human- iimernnipprropptible noise perturbations that drives the fitted model to err at test (inference) time. Such noise perturbations can introduce a large and arbitrary distribution shift that is extremely hard to estimate. In this setting, the

---

Published as a conference paper at ICLR 2022
0.9
Marginal Coveraze
0.8
1.50-
0.7
Average
1.25
-o-Niiaal Level
0.75
Vanili Fast
Vanilla Fast
Our Mathoud (Bscy) antaal
Janili Clean Fet
Vinila Ca vertaatt Test
Our Methed Teal
Figure Marginal coverage (i.e., the percent of test labels that are included the prediction sets) and average set-size obtained by vanilla conformal prediction (Vanilla CP) and our RSCP method, evaluated on the test set of CIFARIO. We use VGG-19 classifier and set the nominal coverage level to be (1 a) 0.9. See Section 5 and Supplementary Section S8 for more details.
prediction sets constructed by the vanilla conformal approach are often invalid, i.e., do not satisfy ( illustrated in Figure Following that figure, while this method achieves the desired 90% coverage when applied to clean test data, the empirical coverage obtained when applying the same method adversarial test examples falls dramatically below 90%, about 30%.
Therefore, is the main motivation of this work to construct prediction sets that are robust to adver- sarial attacks. We formalize this requirement follows:
P (Y E Co Cx(())))) 21
where X,+1 X,+1 + e is the test adversarial example, and ||e||p < 6 is norm-bounded adver- sarial perturbation. Note that we use the notation C5 to distinguish between the new setting from the exchangeability
for which 5 = 0. Crucially, any Pxy, any adversarial perturbation of magnitude bounded by 6, and regardless of the choice or accuracy of the underlying classifier. At the same time, wish C3 be small as possible.
require (2) to hold in finite samples, for
To realize (2) with the desired coverage, we propose to combine randomized smoothing (Duchi et al., 2012 Cohen et al., 2019 Salman al. 2019) with the vanilla conformal prediction procedure, and hence we name our technique Randomly Smoothed Conformal Prediction (RSCP). Randomized smoothing allows to bound the Lipschitz constant of any non-conformity score function by con- volving it with the Gaussian distribution function. Leveraging this bound, we show how to modify conformal prediction and rigorously construct prediction sets that account for the adversarial per- turbation. Figure illustrates that our proposed RSCP approach successfully attains the desired coverage level whereas the vanilla conformal method fails. Observe that RSCP constructs slightly larger prediction sets, reflecting the increased uncertainty induced by the adversarial noise.
The contributions of this paper are two-fold: (i) We propose, for the first time, a new conformal prediction method that can account for the potential adversarial threats during inference time. Our RSCP method, described in Section 3 is model aggostic in that it can work with any classifier and non-conformity score, scalable since the smoothing many i.i.d. Gaussian noise realizations, and robust against any fg-norm bounded adversarial attack. (ii) We prove that the prediction sets constructed by RSCP are valid in the sense of (2), and, in Section 5] support this theoretical result with numerical experiments on CIFARIO, CIFAR100, and ImageNet data sets.
be done by Monte Carlo integration with
CONFORMAL PREDICTION
Since the focus of this paper is on how to adapt the vanilla conformal prediction method to the adver- sarial setting, in this section, give background conformal prediction. While focus here classification problems, the method of conformal prediction can also be applied to regression tasks. The vanilla conformal prediction can be divided into two categories: the split conformal prediction
2

---

Published as a conference paper at ICLR 2022
and the full conformal prediction. The first one involves data splitting while the second one structs valid sets without splitting the data but at the cost of a sigmificant increase in computational complexity at test time (Papadopoulos et al., 2002, Papadopoulos 2008 Vovk et al. 2005). To avoid prohibitive computation complexity, in this paper we focus only on split conformal prediction.
This method starts by splitting the training data into disjoint subsets: a proper training set Ia S [l....,n} and a calibration set Teal {L.. [L..... ... Iu. Then, classifier f(x) [0. 1"a is fit to the proper training set, estimating the conditional class probabilities P(Y = y X = x] for all y E y. the case of deep net classifiers, which is the focus of this work, this may be the output of the softmax layer. Next, we compute non-conformity score S: S (X; Y2) E IR for each calibration point {(x,, Ye This score expresses how well the model prediction f(X) is aligned with the true label Y. where a lower score implies better alignment. For example, the score from Vovk et al. (2005): Lei al. (2013) is given by
S -lr.y)=1-f(m))
where f (z),, e [0, is the yth entry in the vector f (x). Another example is the score proposed by Romano et al. (2020b), which can be expressed
S (a.
Σ (m) I (f()), > f00,,) (x), V'EY
(4)
where I is the indicator function and is random variable distributed uniformly over the segment [0, 1]. We refer to the score from 33 as HPS as it was shown to construct homogeneous prediction sets. Analogously, we refer to 4 as APS since it tends to yield adaptive prediction sets that reflect better the underlying uncertainty across sub-populations; see Romano et (2.20))) for more details. Given the desired coverage level a, the prediction set for new test point Xn41 is formulated as
C (X++11)= = { E y : S (Xn+1. S Qi-a (15:)ier))
(5)
where
Qi-a ((St)ieza) == the (1 - a)) (1 1
1
1
[Zeal] th empirical quantile of (Si)iEz.
(6)
1 +
is the score positioned [nn+ 11 (1-a) a)] in the sorted array of calibration scores St, i Teal- In plain words, in (5) we sweep over all possible labels y E y and include in C (Xx+11) ) the 'guessed' la- bels y whose scores S (Xx++..) 3) are smaller than most of the calibration scores $ (X,, Y.). Since the calibration and test points are drawn exchangeably from Pxy and f is fixed, the score 5 5(x,11, 8) for the guess y Yn+1 fall anywhere in the sorted array of calibration scores with equal proba- bility. This property guarantees that the prediction set (5) satisfies (I) see Vovk et al. (2005).
RANDOMLY SMOOTHED CONFORMAL PREDICTION
In this section, we introduce our proposed RSCP framework for constructing prediction sets that are valid in the adversarial regime. Recall that an adversarial attack can lead to a significant distribu- tional shift between the clean calibration points and the corrupted test example X = Xx+1 + 6, thus violating the fundamental exchangeability assumption of the split conformal procedure. Focus- ing on the guess y = Yn-1, i, an effective attack would result in larger non-conformity score for the corrupted test point S(X,+1,, 3) compared to that of the clean input S(Xn+1: y). Therefore, a naive comparison of S S(X y) to the same threshold Q1 from (6). which neglects the increased un- certainty caused by the adversarial perturbation, will result in prediction set that may not achieve the desired coverage, as already illustrated in Figure [ To address this, we should compare the test score to an inflated threshold, larger than Qi-a. which rigorously accounts for the effect of the adversarial noise. This is the core idea behind our proposal described in detail below; see Figure 2
3.1 ADVERSARIALLY ROBUST CALIBRATION
Suppose we are given a non-conformity score function Š for which we can bound by how much its value could be increased due to the adversarial noise ||e||2 < 8 added to Xn-1- Formally, we require the score Š to satisfy the following relation:
$(Xn+1,v) $ (Xn+1,9) Ma. Vy V,
3

---

Published as a conference paper at ICLR 2022
Q M,
Scoree K,Ruaky)=QQ..
Scorel (uuaky)> 0.
Clean Text Point
Adversurial
llskyeC(x))
Quart
Foint
BuskyæC[x)
100
Also, Sooro(XX,
(X, (u.
50
But, Score [..c
R-x+8
Scores
Husky (x))
Figure 2: Schematic demonstration of the effect of an adversarial noise on vanilla split conformal prediction, along with proposed solution. The vanilla conformal set C(X) and our RSCP set (X) are generated as described in (5) and (). respectively. The black arrows point to the values of the non-conformity scores that correspond to the clean (left) and adversarial (right) test points, which are further marked by the vertical purple lines.
where MM 2 0 is constant that a function of 6, such that Ms, M2, for 51 2 82 and M₁ for 5 = 0. In essence, would like 7 to hold for the smallest possible Ms. We denote this score function by Š to emphasize that it must satisfy 7 distinguishing it from existing non-conformity
scores S, e.g., (3 4 see Section 3.2 2 for a concrete and very general framework for designing $ for which the constant Ms can be easily derived. Importantly, Ms serves as a bridge between the observed score S ((x++1,)) and the unobserved one S(X,+1, y) for fixed y E y. Leveraging this property, we propose to construct a prediction set robust to norm-bounded adversarial attack by applying the following decision rule:
Co = ty E y: :V: S 11-a(1$i) + Ma).
(8)
where S; = Š(x;, Y,). In contrast the vanilla split conformal approach (5), the prediction set defined above is generated by comparing the test score to an inflated threshold Q1-a + M2. as illustrated in Figure Notice that the level of inflation is affected by the magnitude of the adversarial perturbation as well as the robustness of S, i.e., the value of Ma. A larger perturbation implies larger inflation, and more robust score S implies smaller inflation. The theorem below states that the constructed prediction set 8 is guaranteed to contain the unknown target label Yn+1 with probability of at least 1 a, for any distribution PxY, sample size score function Š that satisfies 7 and adversarial perturbation of magnitude 8 generated by any attack algorithm. The proof of this and all other results can be found in Section of the Supplementary Material.
Theorem 1. Assume that the samples {(X,, Y are drawn exchangeably from some unknown distribution Pxy. Let Xa+1 = Xa+1 + be a clean test example Xa+1 with an additive corruption of an fz-norm bounded adversarial noise ||e||z I 5. Then, the prediction set C. (xnn1) defined in satisfies
P (Ynti E Co((nn))) al
Before presenting our framework to construct scores that rigorously satisfy Z). we pause to prove lower bound on the coverage that the vanilla split conformal could attain in the adversarial setting.
Theorem 2. Under the assumptions Theorem with S in place of S, satisfies
/
the prediction set C (xx,, +1) defined in applied
P Yntz e c(Xn+1)) 2T,
where
== max (1:))
Q1-a (eT.)) -
Ms}
Note that 7 can be simply computed by running a grid search on the sorted array of calibration scores. It is important observe that in contrast to Theorem which guarantees at least coverage for any user-specified level a, the worst coverage level 7 of the vanilla split conformal not controlled explicitly, i.e., is known only after looking at the training and calibration data. Observe also that,
4

---

Published as a conference paper at ICLR 2022
by construction, I 1 - (see Supplementary Section ST and equality is met in special case where 5 = 0, i.c. no attack is performed. In this special case, Mí = by definition, and both Theorem and 2 converge to the classic coverage guarantee of the vanilla conformal algorithm.
3.2 THE RANDOMLY SMOOTHED SCORE
To apply the robust calibration procedure presented above, we need to have access to a constant M2 that satisfies 7 for a given non-conformity score function. In general, this constant unknown for modern deep neural net classifiers well as for complex non-conformity scores, such as the one defined in (4). what follows, we present novel framework that takes inspiration from the literature randomized smoothing (Duchi et al. 2012 Cohen al. 2019: Salman et al. 2019), offering a theoretically grounded mechanism to bound the Lipschitz constant of any scoring function derived from any black-box classifier. Concretely, we suggest constructing a new score from the base score S as follows:
(x, v) = -E-1EEum (S (5 + v,y)))
(10)
where Š is a "smoothed" version of the base score S, obtained by averaging the value of S (x + y) over many independent samples v ~ N (0,, Ia drawn from the multivariate normal distribution, and then applying & -- the inverse of the cumulative distribution function (CDF) of the standard normal distribution. The thype-parameter stronger smoothing. (In Section Figure 3 and Supplementary Section S5. we discuss the effect of this parameter the statistical efficiency of the overall calibration procedure.) Assuming that the base score function S(x, y) E [0, 1] for any given (I, y), which holds for most non-conformity scores in multi-class classification problems, we can invoke well-known result from the random- ized smoothing literature (Salman et al. 2019 Lemma 2) and get the following upper-bound for the smoothed score:
controls the level of smoothing, where a larger implies
3(8m+1.8) S $ (Xm+1.1) v) + | s S (X y) +
(11)
Importantly, [1 holds for every y E y, hence rigorously satisfying the relation 7 for the choice of M3 = 8/0. Armed with S, we can invoke Theorems 1
and and construct an adversarially robust prediction set by following (8) lower bound the coverage of the vanilla split conformal procedure.
Corollary Let S be the randomly smoothed score function (00) and set Ms 8/0. The prediction 2 1 a, and the worst coverage of
set defined in (8) satisfiex TP (Yu+1 CC CC(x
(5) given
by IP |Y c(xn=1) T, where max
7' Q (r (Q:,o((8:) 4
The above leads to two possible use-cases of our proposal. In the first, domly smoothed conformal prediction procedure (RSCP) (8) and construct valid prediction sets at any desired level, bearing in mind that these sets are likely to be larger due to the increased uncer- tainty induced by the adversarial perturbation. In the second case, we can deploy the vanilla split conformal algorithm with a smoothed version of the base score, providing important information about the worst coverage that might be obtained under an adversarial attack.
implement ran-
In practice, the smoothed score cannot be evaluated explicitly as requires to compute the expec- tation in (TO). However, this smoothed score can be easily estimated by averaging over many i.i.d. Gaussian noise realizations in [lgorithm[[] see Section 5.1 and Supplementary Section S5.2 for more details about the effect of this approximation on the coverage and set-size. Here, an interesting future direction is to develop a high probability bound for the smoothed score approximation error and integrate it with our method.
Monte Carlo fashion (Cohen al.) 2019, Section 3.2), as described
4 RELATED WORK
4.1 CONFORMAL PREDICTION UNDER DISTRIBUTION SHIFT
Previous work offers several generalizations of the vanilla conformal prediction framework to the case of distribution shift between the training and the test points, however, none of them addresses
5

---

Published as a conference paper at ICLR 2022
Algorithm 1 RSCP: Randomly Smoothed Conformal Prediction
Input: Data {(x,, ==) a test point Xn+1 corrupted by adversarial noise of energy 8; learning algorithm A:; a base non-conformity score S; and coverage level 1 1-a.
1: Split the training data into 2 disjoint subsets In and Tcal.
2: Train a classifier using A on all samples from Iu. i.e., f (X) + A (.EEE))
3: Draw Vij ii.dd N (0a; (Q)) Ta), where Teat and j 1, ..... Mas and compute:
S --
(-11-
S s + uzj. K.), for all i Teal-
(12)
11
4: Compute Q1-a (1=a(((:)iEzaa) == the (1 a) (1+ |+|2al) th empirical quantile of ( Hezan
5: Construct a prediction set for Xn+1:
8 (x = 3 ey ( S QQiaa((3) +
Output: A prediction set Co (X for the unobserved test label Yn-1-
the adversarial setting specifically. Cauchois et al. (2020) suggested a method to construct valid sets when the test distribution of the non-conformity scores is in an f-divergeence ball around their train- ing distribution. While this approach shares the idea of inflating the value of 1- the f-divergence measure is notoriously difficult to estimate in practice (Nguyen et al. 2010 Tsybakov (2099 and thus less applicable compared to our approach, which focuses on the addition of bounded l ad- versarial noise (see Supplementary Section SS22 for a comparison between the methods). [iibs & Candés (202)) generalized the vanilla conformal prediction approach to an online setting where the data generating distribution varies over time by modifying the threshold adaptively new labeled points are being observed, such that the long-term empirical coverage frequency would be at least a-a. This is of course different from our approach that works offiiee and assumes the same data generating process but with the addition of malicious small perturbation induced by an attacker. Tibshirani et al. (2019) studied the case of covariate shift and offered a weighted version of con- formal prediction to address it. In this setting, the shift is only in Px while Pyjx remains intact. Podkopaev & Ramdas (202I) modified this method to tackle the label-shift case, in which Pxly re- mains the same but Py varies between train and test time. Both approaches differ from ours, which handles a full distributional shift induced by the adversarial perturbation. Lastly, Hechtlinger et al. (2188) suggested non-con con-conformity score that empirically tends to be more robust to adversarial attacks, replacing the classifier's 's class probability estimates of Y X with a density estimator that approximates the conditional distribution of X | In contrast not supported by a theoretical guarantee for attaining the desired coverage in the adversarial setting.
RSCP approach, this method is
4.2 CERTIFIED ADVERSARIAL ROBUSTNESS
A different but related line of research is known as 'robustness certification'. Here, the goal is to provide an Ep radius around a test point, in which no adversarial perturbations exist, i.c, the predicted label provably remains the same inside this radius. Currently, one of the mainstream approaches in robustness certification through randomized smoothing, which was proposed in (Lecuyer al.
2019 Li et al. 2019 Cohen et al., 2019) to provide an analytic form of robustness certificate. More formally, given base classifier f(x:), one can construct smoothed classifier according to the following decision rule:
1 = argmax, (x + v)], NN(,,
(13)
In contrast to the base classifier, the smoothed classifier can be supported by rigorous l certi- fication radius around the test point X,+1 = x. It is self-evident that our work is different from we not aiming to deliver robustness certificate for given classi- fier over some test point; instead, we construct a valid prediction set whose size can vary with r. However, both works make use of the randomized smoothing technique, sharing related set of ideas.
robustness certification,

---

Published as a conference paper at ICLR 2022
For example, practical evidence shows that for the smoothed model 13) to correctly classify the test point X, X,+1, the base classifier f needs to consistently label the noisy sample N DoalleeXnnnn (Xn-1, o² as Yn+1 (Cohen et al., 2019) Section 3.3). Training the base classifier without accounting for the future smoothing operation would not necessarily satisfy this requirement, and, as consequence, would lead to a very small certification radius. We note that this observation is also relevant to our setting, where we found that using a classifier that is not robust to Gaussian perturbations results in prediction sets that are often large and thus uninformative. More details are provided in Section of Supplementary Material. One way to improve the certified radius by training the base classifier on the labeled training pairs {NV (Xi, to the one used for smoothing. Later, [Salman et al. (2019) further improved the robustness guarantee through adversarial training, where the adversary generates a bounded perturbation via the method of SMOOTHADY-an adversarial attack designed specifically against smoothed classifiers. A more recent work by [Salman et al. (2020) suggested adding a denoising pre- pre-processing layer preceding the classifier, to remove the Gaussian noise used in randomized smoothing. In our experiments, we find that the training strategy proposed in Lecuyer al. (2019) works well in practice and results in relatively small prediction sets, although a better training scheme-suse as the one from Salman ee al. (019)) (Salman al. (2020) could be easily combined with our method and may further improve the overall statistical efficiency.
la, i E Ia as Lecuerr et al. 2211)), where is equal
5 EXPERIMENTS
In this section, we evaluate the performance of our proposed methods on three bench- mark image classification data sets: CIFARIO. CIFAR100 (Krizhevsky) 2009), and ImageNet ILSVRC2012 (Deng et al. 2009), which are described in Supplementary Section S2 methods follows. First, we fit model on the entire training set. Then, we split the remaining data into two equally sized disjoint subsets, one is used for calibration and the second for testing. The calibration is done using the two base non-conformity scores mentioned in Section 2 i.e., HPS B) and APS Next, we attack each point in the test set by adding to it an adversarial perturbation whose fn-norm is bounded by I Lastly, for each adversarial test point, we construct a prediction set using three different conformal methods (described below), asking for a nominal coverage level of - a. Given the constructed sets, we test the validity of each method by reporting the marginal coverage rate, and the statistical efficiency by computing the average size of the prediction sets. We repeat this process 50 times by randomly assigning data points to form the calibration and test sets.
We evaluate
In our experiments, we compare three different approaches: (i) vanilla split conformal prediction implemented with the two base-scores (HPS and APS), denoted by Vanilla CP; (ii) vanilla split conformal prediction with our proposed smoothed version of the base scores, denoted by CP+SS; and (iii) the proposed randomly smoothed conformal prediction (see Algorithm [], denoted by RSCP. Our experiments show that Vanilla CP constructs invalid prediction sets whose marginal coverage is way below the desired level. The smoothed score improves robustness and coverage but still does not achieve the nominal coverage rate. The prediction sets constructed by our RSCP approach achieve the desired coverage level, aligning with our theoretical guarantees.
5.1 IMPLEMENTATION DETAILSS
Models For all data sets, we choose ResNet (He et al. 2016) to be the base architecture of the deep net classifier and fit two different models for each data set: one on clean training points and the second on points that are augmented with Gaussian noise of standard deviation o that equal the smoothing parameter from 10). The former is used to explore the effect of adversarial examples on the validity of Vanilla CP. The latter training strategy improves the robustness of the classifier and, consequence, reduces the size of the prediction sets constructed by CP CSSSS and RSCP methods, as discussed in Section [.2 and Supplementary Section S4] For CIFAR16 10 and ImageNet data sets, we use the pre-trained ResNet-1 10 and ResNet-50 models from Cohen al. (2019). and for CIFAR100 we fit our own ResNet-110 model as the latter data set is not studied by Cohen et al. (2019), please see Supplementary Section [S3 for additional details on the training procedure. See also Supplementary Section (ariionnS8oo similar experiments in which we choose DenseNet (Iandola et al.) 2014 and VGG (Simonyan & Zisserman
2014) to be the base architectures.
See Supplementary Section
S9 for additional experiments evaluated clean data points.
7

---

Published as a conference paper at ICLR 2022
30.
Base
Avangge Set Size
Marginal Coverage
0.95
Averoge Set Size
2.7
25-
2.5
Base Score APS
0.92
HPS
15
0.91
1/81/6
1/41/3
1/2
128
236
512
1024
8
30
32
64
120
256
512
1024
Mym Nic
The effect of a the size of RSCP's predic- tion sets. The results corre- spond the CIFAR10) 100, with 0.125 and n, = 256.
Figure 3:
Figure The effect of the number of noise realizations n, (used to estimate the smoothed score) on the marginal coverage (left) and size (right) of prediction sets constructed by RSCP. The results correspond to the CIFARIO data set, where we set and a to be equal to 0.125 and 0.25, respectively.
Attack algorithm For Vanilla CP. we generate adversarial noise using the projected gradient descent (PGD) attack (Madry et al. 2018), which is one of the strongest white-box attacks known in the literature to construct & bounded adversarial examples. For the other two methods that make of randomized smoothing (CP+SS and RSCP), apply SMOOTHADV (Salman et al. (219)) variation of PGD that is tailored for smoothed classifiers. For CIFARIO and CIFARTOO, we attack the test points with adversarial perturbation of energy d 0.125, and for ImageNet
larger perturbation of magnitude = 0.25. Both choices lead to significant reduction in the test accuracy of the base classifier, as summarized Supplementary Section S6
Choosing for smoothing Recall Corollary and observe that the coverage guarantee holds for any choice of the smoothing level a. This parameter is intimately connected to the accu- racy/robustness trade-off (Cohen al., 2019) Section 4): a large a will reduce the Lipschitz stant M, = 8/a. however, may also reduce the accuracy of the base classifier (even if fitted on noisy samples). Similar to previous work on randomized smoothing (Cohen et al. 2019. Salman et al. 2019), we treat as a hyper-parameter of our method which can be tuned, for example, by choosing a that produces the smallest sets by volidaaaiiatnnn [ In practice, we find that setting 20 in (10) yields informative prediction sets, as illustrated in Figure 3 This figure also demon- strates the accuracy/robustness trade-off discussed above: the size of the prediction sets reduces for 1/8 < M1 < 1/2, and increases for M3 > 1/2. See Supplementary Section SS. for additional experiments that study the effect of a on the marginal coverage and average set-size for all data sets.
Choosing the number Monte Carlo iterations Following Algorithm [ the smoothed score is evaluated by replacing the expectation (10) with the empirical mean (1)) averaging over n, i.i.d. Gaussian noise samples. This similar to the approach Cohen et al. (2019 Section 3.2) used for find that our method is fairly robust to the choice of nd, and using more than n, = 256 realizations barely affects the marginal coverage and average set-size. This phenomenon demonstrated in Figure CIFAR10; see Supplementary Section [S.22 for additional experiments that illustrate the influence of n, on CIFAR 100 and ImageNet. Therefore, in our experiments we nı, 256 both for CIFARIO and CIFAR 100, and nt 64 for ImageNet due to limited GPU memory footprint; see Supplementary Section S7 for a discussion about the computational complexity including the running time of RSCP.
approximating the smoothed classifier defined in [3). In experiments,
5.2 RESULTS
Figure 5 presents the marginal coverage obtained by Vanilla CP, CP+SS, and RSCP for the three data sets. As can be seen, Vanilla CP fails to construct valid prediction sets in the presence of adversarial noise. For instance, consider the choice of HPS as the non-conformity score, and observe that the average coverage for CIFAR10, CIFAR 100, and ImageNet is 27.27%, 29. 29.24%, and 38.02 08,0 respectively; all are much smaller than the desired 90% level, emphasizing the necessity of
2 Note that our objective is different from that of certified robustness that seeks for that leads to a large radius in which the prediction is certifiably robust.
8

---

Published as a conference paper at ICLR 2022
CIFAR100
Ima Imaggele
CIFARI0O
ImageNed
0.95
Base
Marginal Coveraee
0.90
Aurerag Size
2.5
15
HPS
40
0.80
CP Worst Coverage
0.75
APS - HPS
0.40
0.35
ominal Level
0.25
CP 55
RSCP
RSCP
vanilo CP
CP -5
HSCP
Vanilla CP
55
RSCP
Vanitla CP
55
Vanill CP
R307
Vanilla
Vanill
CP
Figure 5: Marginal coverage (left) and average set-size (right) obtained by different conformal meth- ods. The target coverage level is 90%.
our proposal. When using the same vanilla split conformal procedure, however with the smoothed version of the base non-conformity score (i.e., CP+SS), we get major improvement in terms of coverage. Here, for the smoothed version of the HPS score, the average coverage levels obtained for CIFARIO, CIFARI00, and ImageNet closer to 90% and are equal to 86.78% 87.10%, and 88. 88.12%, respectively. This serves as evidence that the new smoothed score is more robust to adver- sarial attacks. Moreover, since we can derive the Lipschitz constant of the smoothed score, we can invoke the worst coverage bound from Theorem 2 As illustrated, the (average) worst coverage is indeed below the empirical coverage level obtained by CP+SS. While this lower bound is close to the empirical one (for both scores), there exists gap between the two that can be possibly reduced by designing a better algorithm tailored attack the smoothed score. By contrast, our RSCP method generates valid prediction sets whose coverage is slightly above the nominal level, supporting our theoretical guarantee.
Figure also presents the average set-size constructed by all three methods. Observe that CP+SS generates larger sets compared to Vanilla CP since relies on more robust classifier that leads to better coverage at cost of lower accuracy; see Supplementary Table Observe also that RSCP constructs larger sets than those of CP CPSSS due to the inflated threshold used in the calibration, accounting for the effect of the adversarial noise. In addition, the sets obtained by the APS score are larger than those of HPS. This can be explained by (i) the coverage plots: the marginal coverage obtained when using the smoothed APS score tends be larger than that of the smoothed HPS; and (ii) it is known that the APS score tends to construct larger sets even in the noiseless case since it aims constructing sets of 1 a coverage across different sub-populations; see Supplementary Section S11 for an experiment that illustrates this as well as Romano et al. (202bb).
6 CONCLUSIONS AND FUTURE WORK
In this paper, we generalized the technique of conformal prediction the adversarial setting and introduced a model agnostic, scalable, and simple method for constructing valid prediction sets to multi-class classification problems, accounting for the adversarial noise. Our experiments show that our RSCP method is most effective when combined with robust classifiers, e.g., ones that are fitted by augmenting Gaussian noise the training data. However, this often leads degradation in test accuracy, a limitation that is not unique to our work. In fact, this is matter of ongoing research in the robustness certification literature, and note that any new development that front (e.g., Salman et al. (2020) could be easily integrated with our method as demonstrated in Supplementary Sec- tion $10 An exciting future direction could be to extend the guarantees we provided beyond the assumption that the adversarial noise is f--norm bounded and consider different smoothing and cali- bration techniques that can handle the lg. f1, and fo cases (Lee et al. 2019 Teng et al. 2019 Zhang et al. 2019). Other directions could be to explore the use of our method to improve robustness to adversarial attacks in regression problems and to provide conditional validity guarantees of the style suggested by Vovk 2012).

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
A.G. and Y.R. were partially supported by the 2020 Zuckerman Fund, Technion Center for Ma- chine Learning and Intelligent Systems (MLIS Grant No. 2029967), and the ISRAEL SCIENCE FOUNDATION (grant No. 729/21). Y.R. thanks the Career Advancement Fellowship. Technion, for providing research support. Y.R also thank Stephen Bates for his comments on an earlier version of this manuseript.
ETHICS STATEMENT
The ability to communicate the predictive uncertainty of any classifier by constructing prediction sets of valid coverage is crucial to assess the performance machine learning algorithms (Holland) 2020), improve their reliability, and avoid unwanted discrimination (Romano al.) 2020a). Our proposed method further enriches the existing uncertainty quantification toolbox, by providing a rigorous form of robustness adversarial perturbations. For example, one can promote fairness in high-stakes applications (in addition to robustness) by integrating RSCP within the framework of equalized coverage (Romano al., 2020a). Here, we stress that the validity of our methods relies on the exchangeability assumption between the clean training and test points, and on the knowledge of the f2- 2--bound of the attack. If one these assumptions violated, the sets that RSCP constructs may not have the right coverage. Therefore, it is recommended to assess whether the above assumptions are reasonable when using the proposed methods.
REPRODUCIBILIIT STATEMENT
Python package that implements our methods and code reproduce our experiments are available at ht hhtttps://// /ttp:://qttttt thub. com/ Asa AsafgendlerrRsst
Complete proofs of the theorems presented this paper can be found in Supplementary Section [ST] A complete description of the data sets used in our experiments, including pre-processing steps, can be found in Supplementary Section S2 The details about the models used in our experiments and how they were trained are provided in Supplementary sections $3 and S8
REFERENCES
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In IEEE Symposium on Security and Privacy (SP), pp. 39-57. IEEE Computer Society, 2017.
Maxime Cauchois, Suyash Gupta, Alnur Ali, and John Duchi. Robust validation: Confident predictions even when distributions shift. arXiv preprint arXiv:2008. 042000 2020.
Gilad Cohen, Guillermo Sapiro, and Raja Giryes. Detecting adversarial samples using influence functions and nearest neighbors. In Proceedings of IEEE/CVF Conference on Computer Vision and Patter Recognition, pp.
2020.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. International Conference on Machine Learning, pp. 1310-1320. PMLR, 2019.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hicrarchical image database. In IEEE conference 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.
Reuben Feinman, Ryan R Curtin, Saurabh Shintre, and Andrew B Gardner. Detecting adversarial samples from artifacts. arXiv preprint arXiv: 2017.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. The limits of distribution-free conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2):455-483 2021.
Isaac Gibbs and Emmanuel Candès. Adaptive conformal inference under distribution shift, arXiv preprint arXiv:2 106.00/70 2021.
10

---

Published as a conference paper at ICLR 2022
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. star, 1050:20, 2015.
Leying Guan and Rob Tibshirani. Prediction and outlier detection in classification problems. arXiv preprint arxiv:1905 1905.0439, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Douglas Heaven. Why deep-learning ais are so easy to fool. Nature, 5747777):163-166, 2019.
Yotam Hechtlinger, Barnabás Póczos, and Larry Wasserman. Cautious deep learning. arXiv preprint arXiv:1805.094600 2018.
Matthew J Holland. Making learning more transparent using conformalized performance prediction. arXiv preprint arXiv:2007.04488, 2020.
Forrest landola, Matt Moskewicz, Sergey Karayev, Ross Girshick, Trevor Darrell, and Kurt Keutzer. Densenet: Implementing efficient convnet descriptor pyramids. arXiv preprint 1rXiv:1404.1880 1869, 2014.
Pang Wei Koh, Shiori Sagawa, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, Tony Lee, et al. Wilds: A benchmark of in-the-wild distribution shifts. In International Conference on Machine Learning, pp. 5637-
5664. PMLR, 2021.
A Krizhevsky. Learning multiple layers of Tront, 2009.
features from tiny images. Master's thesis, University of
Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In JEEE Symposium on Security and Privacy (SP), pp. 656-672. IEEE, 2019.
Guang-He Lee, Yang Yuan, Shiyu Chang. and Tommi Jaakkola. Tight certificates of adversarial ro- bustness for randomly smoothed classifiers. Advances in Neural Information Processing Systems, 32:4910 4921, 2019.
Jing Lei, James Robins, and Larry Wasserman. Distribution-fies prediction sets. Journal of the American Statistical Association, 108(501):278-277, 2013.
Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. Advances in Neural Information Processing Systems, 02:9464-9474 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference Learning Representations, 2018
Jan Hendrik Metzen, Tim Genewein, Volker Fischer, and Bastian Bischoff. On detecting adversarial perturbations. arXiv preprint (tXiv:1702.04267 2017.
XuanLong Nguyen, Martin J Wainwright, and Michael Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions Information Theory, (111))5847-5861 2010.
Harris Papadopoulos. Inductive conformal prediction: Theory and application to neural networks. In Tools in Artificial Intelligence. IntechOpen, 2008
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.
Alcksandr Podkopaev and Aaditya Ramdas. Distribution free uncertainty quantification for classi- fication under label shift. arXiv preprint arXiv:2103.03333, 2021.

---

Published as a conference paper at ICLR 2022
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Ad- vances Neural Information Processing Systems, 32:3543-355 3553,,55,2220 2019.
Yaniv Romano, Rina Foygel Barber, Chiara Sabatti, and Emmanuel Candès. With malice toward none: Assessing uncertainty via equalized coverage. Harvard Data Science Review, 2, 2020a.
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive cover- age. Advances in Neural Information Processing Systems, 33:3581-3591, 2020b.
Hadi Salman, Greg Yang. Jenry Li. Pengchuan Zhang, Huan Zhang, llya Razenshteyn, and Sébastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. In Pro- ceedings of the 33rd International Conference Neural Information Processing Systems, pp- 11292-11303, 2019.
Hadi Salman, Mingjie Sun, Greg Yang. Ashish Kapoor, and J Zico Kolter. Denoised smoothing: A provable defense for pretrained classifiers. Advances in Neural Information Processing Systems, 33, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference Learning Representations, ICLR 2014, 2014.
Jiaye Teng, Guang-He Lee, and Yang Yuan. & adversarial robustness certificates: randomized smoothing approach, 2019.
Ryan Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal predic- tion under covariate shift. Advances in Neural Information Processing Systems, 32:2530-2540, 2019.
Alexandre B Tsybakov. Introduction to Nonparametric Estimation. Springer, Dordrecht, 2009.
Springer series in statistics.
Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian conference on machine learming, pp. 475-490. PMLR, 2012.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer Science Business Media, 2005.
Dinghuai Zhang, Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Filling the soap bubbles: Efficient black-box adversarial certification with non- non-gaussian smoothing, 2019.
12

---

Published as a conference paper at ICLR 2022
SUPPLEMENTARY MATERIAL: ADVERSARIALLY ROBUST CONFORMAL PREDICTION
S1 SUPPLEMENTARY PROOFS
In this section, we prove Theorem ! and Theorem presented in Section of the main manuscript.
Proof of theorem]
7 From the definition of the prediction set 8
P Yut1 E Co(8n+1)] = IP ((xm+1, Xu+1) S Q2-a + Ms]
(using
P (Xn+1, (Xtt1), + M3 - Q1-a ((5i) (Si)ietw) + Ms
P (Xm+1, Yn+1) s (1-a(15)) )
where the last inequality follows from the validity of the prediction set constructed by the vanilla split conformal procedure since Yi), i E {Teal U fn 1}} exchangeable (Vovk et al. 2005); see also (Romano et al. 2019 Lemma 2).
Proof of theorem]
2 From the definition of the prediction in 5):
Yu+1 E EC(xn+1) = P (X 2ot1,, Y241) I Q1 )eew))
(using 7
2 P 3 (X + Ma s Q1-a (15i) (5:)))))))
P
(X 1n S Q1-a (1 )exma) - Md
(using the definition of r, defined in (9)
M 2 P S (X Y S Q- ((:) sETwa]
where, similarly to the proof of Theorem Lemma 2).
I the last inequality follows from (Romano et al. 2019
Lastly, we show that < 1 - From the definition of r in (
r' Qr. (e.))) ) S Q1-0 seIm) -M }
7 max
r'= Q. (15: k5T s -Q--a ((
S max
S2
DATA SETS
Overview We evaluate our methods on three widely used image classification data sets: CIFARIO. CIFAR 100 (Krizhessky 2009), and ImageNet (Deng et al. 2009). The CIFARIO data set consists of 60,000 RGB color images of size x 32 corresponding to 10 different classes, with 6,000 images per class. In this data set, there are 50,000 training images and 10,000 test images. The CIFAR100 data set identical in structure to CIFAR1O, except it has 100 classes containing 600 images each. Overall, this data consists of 50,000 training images and 10,000 test images. In our experiments, we use the entire training set for fitting the classifiers and split the rest 10,000 points into two sets of equal size (calibration and test) 50 times. We use the ILSVRC2012 version of the ImageNet data set. Here, the training set consists of 1.2 million color RGB images of different sizes, corresponding to 1,000 class labels. To construct calibration and test sets, randomly split the 50,000 images the ILSVRC2012 validation set into calibration and test sets of equal size, for 50 times. We the entire II SVSV222012 training set for fitting the predictive models.
13

---

Published as a conference paper at ICLR 2022
Pre-processing The CIFARIO and CIFARIO0 images normalized by (i) subtracting the train- ing images mean value, equals to [0.4914, 0.4822, 0,4465], and (ii dividing the result by the images standard deviation, equals to [0.2023, 0.1994, 0.2010]. The ImageNet images first re-scaled to a size of 256 x 256. Then, the central 224 x 224 pixels are taken and normalized by subtracting the mean value of the training images [0.485, 0.456, 0.406] and dividing the result by their standard deviation, given by [0.229, 0.224, 0.225].
S3 MODELS
As described in Section 5.1 of the main manuscript, for CIFARIO and ImageNet data sets, we use the pre-trained ResNet-110 and ResNet-50 models from [Chhen et al. (2019). We use the models that were trained on clean training points, as well as models that were trained on Gaus- sian augmented training points. These models are downloaded from https: /ttp::://ithuli hig.tttubb.... com/ locus lab/ smoothing This link also provides the full details on how the models were trained.
Since the CIFARI00 data set was not studied by Cohen et al. (2019), we fit our own models by modifying the software package available at https: / /tt/ttttubbbb www./o//r/paaeeo pytorch-clasee fictionn Specifically, we fit a residual network of depth 110 (ResNet- 110) by augmenting the training data with random crops of size 32 (after applying zero padding of size 4) and random horizontal flips. The images are normalized as explained in Section S2 For convenience, we added the normalization in Section [.1 of the main manuscript, we fit two models: one on clean training points and another on points that are augmented with Gaussian noise of standard deviation o that is equal the one used for smoothing. The models are trained using the stochastic gradient descent optimizer with a momentum term of 0.9 for 164 epochs, using a batch size of 128 points. The learning rate starts at 0.1 and is multiplied by factor of 0.1 at epochs 81 and 122. A weight decay regularization of 10-4 added the loss function. We train the models using Pytorch, on single Nvidia GEFORCE GTX 1080 Ti GPU.
pre-processing layer to the fitted model. As explained
S4 WHY DOES TRAINING WITH GAUSSIAN NOISE IMPORTANT?
As stated in Section 4.2 of the main manuscript, while our method can work with any base classifier f. in practice. we require f to have some degree of robustness in order to construct small prediction sets. Figure demoossrtsss that our RSCP procedure constructs valid but very large prediction sets when deployed with standard classifier, fitted without augmenting Gaussian noise to the CIFARI0 training points. Here, the average size of the prediction sets is equal to 9, a trivial result for the CIFARIO 10 data set that has only 10 classes. In this experiment, we use o 0.5 for smoothing, an attack of magnitude 8 = 0.12., and nt = 256 Gaussian noise samples for estimating the smoothed score.
10-
Marginal Coverage
Average Size
0.8
7.5
Score
APS
HPS
0.6
5
Nominal Level
0.4
2.5
0.2
Vanilla CP
CR 3+$5 5s
RSCP
Vanilla CP
CP + 55
RSCP
Figure S6: The importance of using robust models. Marginal coverage (left) and average set-size
(right) obtained by different conformal methods. The target coverage level is 90%.
14

---

Published as a conference paper at ICLR 2022
S5
HYPER PARAMETERS
S5.1 INFLUENCE OF THE VALUE OF
Herein, we extend the discussion from Section 5.1 of the main manuscript and study the effect of the choice of the hyper-parameter used compute the smoothed score. Specifically, repeat the same experiment described in the context of Figure for all data sets. Figure[S7] Segure[7|show shows how the ratio between and affects the average set-size and the average coverage obtained by our RSCP method. In this experiment, we use an adversarial perturbation of magnitude 5 0.125 for CIFARIO 10 and CIFARION and magnitude 5 0.25 for ImageNet. As can be seen, a ratio of a / works well for all data sets and the two non non-conformity scores.
CIFARI0
CIFAR100
ImageNet
0.99
Marginal Coverage
0.97
0.97
0.96
0.95
0.95
0.93
0.94
0.93
0.93
2
Mg 6/a
CIFAR10
CIFAR100
ImageNet
80
3.5
Average Set Size
25
3
20
40
2
2
Mg 5/a
HPS
Figure S7: The effect a on the marginal coverage (top) and size (bottom) of prediction sets con- structed by RSCP. Here, ô and n, are fixed and equal to 0.1 and 256 for CIFARIO and CIFAR100, and 0.25 and 64 for ImageNet.
S5.2 INFLUENCE THE VALUE OF n2s
As explained Section 5. of the main manuscript, the smoothed score is evaluated by replacing the expectation (10) with the empirical mean (12). averaging over i.i.d. Gaussian noise samples. Figure S8 shows the effect of the value of n, on the average set-size and the average coverage obtained by RSCP method for all data sets. Following that figure, averaging more than n, 256 noise samples (or even n, = 64) barely affects the empirical coverage and size the constructed sets.
15

---

Published as a conference paper at ICLR 2022
CIFAR10
CIFAR100
ImageNet
Marginal Coverage
0.95
0.93
0.94
0.94
0.93
0.92
0.92
0.91
8
32
64
128
256
512
1024
16
32
64
128
256
512
1024
2
8
16
32
64
128
256
CIFAR10
CIFAR100
ImageNet
19
60
Average Size
2.7
17
2.5
40
16
2.3
15
20
2.1
14
8
16
32
128
256
512
1024
16
32
64
128
256
512
1024
8
16
32
64
128
256
Base Score
APS
HPS
Figure S8: The effect of the number of noise realizations nt (used estimate the smoothed score) on the marginal coverage (top) and size (bottom) of prediction sets constructed by RSCP. Here, and a are fixed and equal to 125 and 0.25 for CIFARIO and CIFARI00, and to 0.25 and 0.5 for ImageNet respectively.
S6 EFFECT OF THE ADVERSARIAL ATTACKS
As stated in Section 5.1 of the main manuscript, in all of our experiments, we use an attack of 0.25 for ImageNet. Table S] illustrates the effect of such adversarial perturbations on the test accuracy of the models used in the experiments presented in Section of the main manuscript well as in Supplementary Section [S5.] and Supplementary Section [88 that is presented hereafter. The PGD attack leads to a significant reduction in the test accuracy of models that fitted without Gaussian noise augmentation (i.e., O). By contrast, the models that are trained with Gaussian noise are more robust, as the decrease in test accuracy is smaller when attacked by SMOOTHADV, This, however, comes at the expense of an accuracy reduction on the clean test points.
la magnitude 5 0.125 for CIFARIO and CIFAR 100, and
S7 COMPUTATIONAL COMPLEXITY
Following Algorithm T. at test time, computational complexity of RSCP dominated by number of calls to the predictive model, required to compute the smoothed score for each of the L
When evaluating the test accuracy of the models trained with Gaussian noise, add Gaussian noise with the standard deviation the test point since we find this approach to improve the accuracy.
16

---

Published as a conference paper at ICLR 2022
The influence of the adversarial attacks used in our experiments on the classifiers' test accuracy.
Table S1:
Architecture
Training
CIFARIO
CIFARIO0
ImageNet
Clean Test
Adversarial Test
Clean
Adversarial Test
Adversarial
RosNet
89.94%
26.7%
71.03%
12.19%
75.69%
19.59%
0.0625
87.13%
68.96%
64.58%
41.17%
0.125
81.69%
67.84%
58.06%
41.95%
0.25
75.19%
65, 18%
50.73%
40.82%
68.58%
56.32%
0.375
44.23%
37.14%
0.5
63.84%
57.34%
39.0%
33.68%
61.04%
53.09%
0.75
31.75%
28.
47.99%
44.41
25.57%
23.56%
47.73%
42.89%
DonseNet
95.42%
23.28%
77.07%
4.29%
0.25
80.09%
70.89%
52.69%
42.47%
93.1%
54.96%
72.17%
23.12%
0.25
78.88%
69.82%
48.57%
39.54%
possible labels y E y. The number of calls to the predictive model for creating a set for a single test image is n2. and the number of classes L only affects the number of scores that need to be calculated using the model predictions. The training involves fitting a classifier, and the calibration requires computing the smoothed non-conformity scores for all calibration points, where both steps can be performed only once.
Table S2 summarizes the average runtime for constructing prediction set using Vanilla CP, CP+SS, and RSCP with the HPS score function (3). for a single image, where the average is taken over 100 realizations. We present the results obtained by two different implementation strategies of our methods: 'single mode' and 'batch mode'. The 'single' implementation repeats the following two steps for n, times: (i) augment the input image one realization of Gaussian noise, and (ii) feed this noisy image to the neural net model. The 'batch' implementation is more efficient since parallelizes the inference step as follows: (i) augment n, noise realizations to the same input image, and (ii) pass all these noisy realizations together (as one batch) to the neural net model. We follow the exact same setup from the experiments used to create Figure of the main manuscript. Specifically, nt, 256 for CIFARIO and CIFAR100, and n., 64 for ImageNet. The runtimes are evaluated using Pytorch, on single Nvidia GEFORCE GTX 1080Ti GPU.
Following Table S2] we can see that when using the batch implementation the inference time of CP+SS and RSCP is approximately 3-4 times larger than Vanilla CP. Also, the runtimes of CP+SS and RSCP are almost identical, since the only difference between the two is the threshold used to construct the prediction sets.
Inference time (seconds) for constructing a prediction set for single image using different conformal prediction methods.
Table S2:
Dataset Vanil 1a CP
CP+S8
RSCP
Single
Batch
Single
Batch
CIFARIO
0.019336
4.820160
0.030831
4,920013
0.030856
CIFAR 100
0.017984
5.981254
0.030915
5.9370026
0.030892
ImageNet
0.097539
1.288073
0.424692
1.134275
0.435865
S8 RESULTS WITH DENSNET AND VGG MODELS
In this section, we study the performance of our method when applied with DenseNet (Tandola et al.] 2014) and VGG (Simonyan & Zisserman, 2014) models the CIFAR10 and CIFARTO TO0 data sets,
17

---

Published as a conference paper at ICLR 2022
as opposed to experiments presented thus far that use only ResNet (He et al. 2016) classifiers. The experiments here follow the protocol described in Section [ of the main manuscript. We use the same attack algorithms and magnitude 5 0.125 in the ResNet- 10 experiments for CIFARIO and CIFAR100. As for the hyper-parameters of our methods, we choose o = 0.25 for smoothing, and n 256 for estimating the smoothed score. Figure [59 compares the coverage and size of the prediction sets constructed by combining ResNet-110, VGG, or DenseNet with Vanilla CP, CP+SS, and RSCP. As can be seen, the difference between the three models is minor in terms of coverage for all calibration methods in both data sets. We can also see that our theoretical guarantees hold: for CP+SS, the worst coverage bound below the empirical coverage obtained, and RSCP yields valid prediction sets in contrast to the two other methods. In terms of size, the difference between ResNet and DenseNet is minor, while VGG constructs larger sets, especially on CIFAR 100.
Figure 1 of the main manuscript presents the results obtained by applying the VGG models to the CI data set, using the HPS score. In that figure, we additionally tested the vanilla conformal method on the clean test points, to show the validity of this method when applied to clean test data that satisfy the exchangeability assumption.
Turning to the technical details about the training procedure. For each architecture, we fit two mod- els: one on clean training points and the second on points that are augmented with Gaussian noise, as explained in Section 5.1 and Supplementary Section S3 All the models are trained our local server. The DenseNet architecture consists of 100 layers with growth rate of 12 and a compression rate of 2. We use the same data augmentation and normalization described in Supplementary sec- tions S2] and S3 The models are trained using stochastic gradient descent with a momentum term that equals 0.9, batch size of 64, and a total of 300 epochs. The learning rate starts at 0.1 and is multiplied by a factor of 0.1 at epochs 150 and 225. We also use a weight decay regularization that equals 10-4. The VGG architecture consists of 19 layers with batch normalization. We use the same data augmentation and normalization from Supplementary sections SS2 and S3] The VGG models are trained using stochastic gradient descent: a momentum of 0.9, batch size of 128, for a total of 164 epochs. We set the initial learning rate to be equal to 0.1 and multiplied by a factor of 0.1 at epochs 81 and 122. We also use a weight decay regularization, which equals 10 10-4, The ResNet models are trained explained in Supplementary Section $3 Pytorch, on a single Nvidia GEFORCE GTX 1080 Ti GPU.
We train all the models using
Densehet
ResNet
VGG
DenseNet
ResWet
VGG
0.85
25.
Base Score
APS HPS
Coverage
0.85
0.90
40
4
Average Sot Spe
20
CP455 Worst Coverage
0.80
HPP
0.4
10-
0.5-
Level
0.2
0.1
Vesiita CP
GP 55
Vanilla CP
Cp 55
Rsop
Varilla CP
cp +555
Roop
RSCP
55
RScP
55
Vadita
Vadita
Vasita
Denseliet
ResNeet
VG6
2.5
DenseNet
Reshet
VGG
Marginal Coveraa
0.90
ES APS HPS
Bave Score
0.85
0.8D-
Averae Set Stze
CP Worst Coverage
0.75
APS
HP5
0.8
Level
0.2
Vinila op
Reror
Vantla cP
CP ss
iscr
Vanila ep
cP.. +5
Vanuta oP
ss
Rece
PSOP
Vonila
Vanils
Figure S9: A comparison between ResNet, VGG, and DenseNet models, deployed to the CIFARIO (bottom) and CIFAR 100 (top) data sets. Marginal coverage (left) and average set-size (right) ob- tained by different conformal methods. The target coverage level is 90%.
18

---

Published as a conference paper at ICLR 2022
S9 RESULTS ON CLEAN DATA
In this section, we study the performance of our methods in a situation where no adversarial attack is performed. We follow the setup from Figure [5) of the main manuscript, and compare the three methods of interest (Vanilla CP, CP+SS, and RSCP) on the three data sets, using the same models, smoothing parameter a, and the number of noise realizations ft. Importantly, in contrast to 3 the results that are presented in Figure(SIO clean test points that are not corrupted by adversarial noise. Following that figure, both Vanilla CP and CP+SS achieve the desired coverage of 90%. which stands in line with the theoretical guarantee of split conformal prediction; see also Theorem 2 By contrast, RSCP results in higher coverage rate than the desired one, since this method always accounts for the uncertainty induced by a possible attack even if not applied. Moving to the average set-size, notice that all the methods perform similarly to the case where the test data is corrupted, manuscript. Specifically, the average size of the sets constructed by CP+SS is larger than that of Vanilla CP, possibly due smoothed model that is used to make the predictions. However, it is important to stress that CP+SS has a significantly smaller drop in coverage in the adversarial setting. We also note that the average size of the sets constructed by RSCP is larger than those of CP+SS due to the inflation of threshold Q 1-
obtained by applying these three methods on
depicted in Figure 5 of the main
As concluding remark, we iterate here the discussion from Section 3.2 of the main manuscript, displaying the two possible use-cases of our proposal. In the first, one can implement RSCP and construct valid prediction sets at any desired level of coverage, while bearing in mind that these sets are likely to be larger even if no attack is performed. In the second case, one can deploy CP-SS, guaranteeing that the sets will have the desired coverage in the case where no attack is performed while providing important information about the worst coverage that might be obtained under an adversarial attack. Moreover, we believe that practice these two use-cases can be combined via the following two-step procedure to improve statistical efficiency: (i) apply method for detecting
whether given test point is corrupted by an adversarial noise (c.g., Metzen et al. 2017; Feinman et al. 2017 Cohen et al. (020); and (īi) if an attack is detected, apply the RSCP method to construct a valid prediction set, otherwise use the vanilla CP or CP+SS since these methods are less conservative.
CIFAR10
CIFAR100
ImageNet
CIFARI0
CIFAR100
ImageNet
0.975
Marginal Coverage
2.5
15.
Average Set Size
0.950
Base Score
APS HPS
10
0.925
Nominal Level
1.5
20
0.900
0.875
Vanilla CP
CP 55
RSCP
Vanilia CP
CP + 55
RSCP
Vanilla CP
CP + S5
RSCP
Vanilla CP CP + S5 RSCP
Vanilla CP
CP + ss
RSCP
Vanilla @P
CP + 55
RSCP
Figure S10: Performance clean data. Marginal coverage (left) and average set-size (right) ob-
tained by different conformal methods. The target coverage level is 90%.
S10 RESULTS WITH AN ADVERSARIALLY MODEL
In this section, we study the performance of our methods, integrated with the adversarial train- ing scheme of Salmmnn et al. 2019) that was shown to improve the robustness to the specific SMOOTHADV attack we applied at test time. This new, more robust, predictive model replaces the one we used in Section (see also Supplementary Section S3 which fitted merely by adding Gaussian noise to the training points. Recall that the SMOOTHADV attack has two parameters: the magnitude of the noise and the smoothing strength o. Here, we use a training procedure that is ideal in the sense that it has access to the same é used for attacking the model, and the same used
19

---

Published as a conference paper at ICLR 2022
to compute the smoothed score. We perform this experiment only the CIFARI0 data set and fit a ResNet- model using the code provided by Salman et al. (2019). Their software package is this link
available at hhtpp:: /tttthtttt.uu com/ Hadisalman/ wttassaaaanammoosaiaaeeaa also provides the full details on how the models are trained.
The results depicted in Figure STT which follows the exact experimental protocol used to create Figure of the main manuscript. That figure compares two versions of CP+SS: the first implemented with a model fitted on Gaussian augmented data, and the second implemented with the adversarially trained model of Sallmn et al. 2019). As can be seen, the latter model achieves a slightly better coverage, closer the desired one with the HPS score, while achieving slightly worse coverage with the APS score. For both scores, however, this model improves the statistical efficiency. Interestingly, even in this optimistic case, CP+SS does not attain the desired coverage perfectly. It is also important to stress that if the new model would be attacked by different and more effective attack, the coverage can possibly drop even further. It is worth noting that this experiment supports our discussion from Section 6 arguing that any new development for improving adversarial robustness could be easily integrated with our method to improve the overall performance.
0.90
2-
Marginal Coverage
0.89
Average Set Size
Base Score HPS
1.8
0.87
Nominal Level
0.86
1.4
0.85
Adversarial
Caussian
Figure S11: Results using adversarially trained model. Marginal coverage (left) and average set-size (right) obtained by CP+SS on the CIFARIO dataset with two different models. The target coverage level is 90%.
S11 HPS vs. APS
In this section, we discuss the difference between the APS and HPS non-conformity scores and demonstrate the advantages that APS has over HPS. Romano et al. (2020b) carefully argued that while conformal prediction methods-which use the HPS score are guaranteed to achieve the marginal coverage criterion (T). they may fail to achieve the stronger and more informative notion of conditional coverage, defined as
P|r++1 (x) =
(S14)
In plain words, the above statement requires the coverage to hold for specific observation X I, and not merely on average over all test points. While it is known that conditional coverage cannot be achieved in finite samples without imposing strong regularity conditions and/or modeling assumptions (Foygel Barber et al.] 2021 Vovk 2012). it was shown by Romano et al. (2020b) that the APS score performs better in terms conditional coverage compared to the HPS score. fact, Romano al. (2020b) rigorously showed that by combining the APS score with an oracle classifier that has access to the true conditional class probabilities Py one can exactly satisfy (S14).
To demonstrate the advantage of APS in the adversarial setting, we repeat the experiment from Figure 5 of the main manuscript and present the coverage and the average set-size, conditional on each of the 10 classes of the CIFARI0 data set. Following Figure S12 the APS prediction sets achieve a steady coverage across all classes, close to the desired level for the CP CP+SS, while the coverage rates of HPS vary greatly. Moreover, the latter method tends to undercover the labels of the
20

---

Published as a conference paper at ICLR 2022
samples that belong classes 2-5. One can also that the size of the prediction sets constructed by APS varies across the different classes, and therefore better reflecting the prediction uncertainty. This stands in contrast with the sets constructed via the HPS score, whose sizes are or less constant for all class labels.
0.9
C SS
Marginal Coverage
0.8
Base Score
APS
HPS
0.7
Nominal Level
0.96
RSCP
0.92
0.88
3
7
8
Class
2.5
+ SS
Average Set Size
2
1.5
Base Score APS HPS
+
3
RSCP
2
1
2
5
8
9
Class
Figure S12: Comparison between HPS and APS. Marginal coverage (top) and average set-size (bot- tom) obtained by different conformal methods for each the classes of CIFARIO separately, The target coverage level is 90%.
S12 COMPARISON WITH CAUCHOIS ET AL. (2020)
As discussed in Section the task of reliably handling distribution shifts between the calibration and the test points has been studied in the literature of conformal prediction. However, none of the existing methods addresses our special setup, for which a full distributional shift is induced by an adversarial attack. Perhaps the closest work to ours is that of Cauchois et al. (2020). They present calibration framework construct robust prediction sets, given that the f-divergence between the test distribution and the calibration distribution of the non-conformity scores is bounded by fixed value p. Since / unknown in practice, they propose method to estimate it from the data and use this approximation inflate the threshold Qi-a. that the constructed sets will be robust to 'natural' distributional shifts. This is in contrast to our method that assumes that an unknown additive adversarial noise is added the test points, and, such, it is impossible estimate p in this case from the training/calibration data.
To demonstrate this, follow the experimental protocol from Section 5 to compare methods with Cauchois et al. (2020). We estimate p by applying Cauchois et al. (2020) Algorithm 1), and then construct prediction sets for the test points that corrupted by adversarial perturbations of
21

---

Published as a conference paper at ICLR 2022
magnitude 8 0.125 We the same attacks detailed in Section 5 and evaluate this method over 50 random splits of the CIFAR10 dataset. We compare the marginal coverage and average set RSCP approach with matching to the one used to augment the training points, and set n = 256. We make this comparison with four different ResNet models: one that is trained on clean data (in this case perform RSCP with 0.25 for smoothing), and three that are trained on points augmented with Gaussian noise, each one with a different
sizes achieved by their method
As can be seen, while our method achieves the desired cov- erage, no matter which base model is used (at the expense of larger prediction sets), the method of Cauchois al. (2200) fails when using model trained on clean points: the empirical coverage is below the desired coverage (Figure SS The same happens with the o = 0.0625 and = 0.125 models; see figures ST33 and ST.3c When using more robust classifier-traneedd with a 0.25 Cauchois et al. (2020) achieves the desired coverage in practice, although it is not supported by theoretical guarantee; see Figure [TT3d] Interestingly, for this model, while the two methods con- struct prediction sets that achieve the desired coverage, our RSCP method-
The results depicted in Figure 513
uses smoothed scores- constructs smaller sets with the choice of HPS as the base score, and the same size sets with the APS score.
*We thank the authors of Cauchoii al. 2020) for sharing their code with us.
As stated in Section S6 we add Gaussian noise the test points when applying these models to calculate the non-conformity scores.
22

---

Figure S13: Comparison with Cauchois et al. 2020). Marginal coverage (left) and average set- size (right) obtained by different conformal methods on the CIFARIO dataset with three different ResNet-110 models. The target coverage level is 90%. (a) model trained clean training points, Published as a conference paper at ICLR 2022
10
Marginal Coverage
Avarage Sat Si20
7.5
Base Score APS HPS
0.6
Nominaa
0.4
Cauchoos et.
RSCP
RSCa
Vanila
Vanilla
Cauchoil et
Averaga Set Size
HPS
Nominnal
Marg
0.0
1.5
Cauchols at.
RSCP
R5C
Vanilla
Varilla
Cauchols et
(b)
Marginal Coverage
0.95
Average Set Size
2.5
Base Score HPS
0.90
Nominal Level
0.80
VaniBa CP
Caucitai at
RSCP
RSCP
Vanilla
Cairchois
0.95
Marginal Coverage
Avarage Set Size
Base Score
APS HPS
0.85
Caucheis at
RSCP
RSCP
Vanilaa
Vanillo
Cauchin et
(d)
(b) model trained on points augmented by Gaussian noise with a 0.0625, (c) model trained on points augmented by Gaussian noise with 0.125, (d) model trained points augmented by Gaussian noise with σ = 0.25.
23


Reviews:
[{"review_id": "x9NVY7NGTkc", "reviewer": "Reviewer_oSbg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The framework proposed in the work considers an important direction in the study of the applicability of conformal prediction in settings beyond the i.i.d. scenario. For safety-critical applications, it is important to build robust ways of quantifying uncertainty as certain failures could have disastrous consequences. The authors consider a popular setting where test data contains adversarial examples with bounded $\\ell_2$-norm. For a modified procedure to work, the non-conformity scores have to satisfy a certain property, and the authors propose a way to incorporate any ``base'' score into the framework via randomized smoothing. I was wondering whether the authors could comment a bit more on the following questions:\n\n--- Q1: While it is intuitive that getting robust prediction sets comes at the cost of larger prediction sets, I couldn't find a simulation that considers a null case. That is, a comparison of vanilla conformal against a robustified version proposed in this work in the setting where adversarial examples are not present, and thus i.i.d. assumption is sensible (i.e. vanilla conformal would have reasonable marginal coverage). Is it indeed the case that such simulation was not present in the paper? The reason is that one reasonable requirement for the prediction sets is their ``actionability'', i.e., it is hard to assess how actionable prediction sets of size 30 are in 100-classes classification problem.\n\n--- Q2: Regarding computational complexity. It is clear that at the inference stage, for constructing a prediction set, it is necessary to perform sampling of perturbed input $n_S$ times for each class (as the authors point out in the Appendix S7). Are there any specific settings (i.e., pair of model architectures, datasets) that the authors have numbers for? It is interesting how computationally feasible the framework is.\n  \n--- Q3: I was wondering whether the authors can comment a bit more on the sensitivity of the smoothed scores to using approximations obtained via sampling. A partial answer is presented in S5.2 where some figures are presented for average set sizes and coverage. But it seems that if the original non-conformity scores are bounded, then it is possible to look at the sizes of the confidence intervals for the quantities that are being approximated.\n\n--- A side note: equation 8 might contain a typo. it seems that $\\tilde X_{n+1}$ (an observed feature vector) should be stated in place of $X_{n+1}$ (an unobserved one).\n\nIn general, the work is well-written equipped with important parts of (relevant) literature review and well-designed simulation studies.", "summary_of_the_paper": "Quantifying predictive uncertainty is critical for various real-world applications of ML models. Post-hoc ``wrapper-style'' procedures for uncertainty quantification, which can be built on top of any black-box model and thus do not require modifications of training algorithms, are of great value due to a, typically, high number of engineering tweaks used during the model development stage. For example, (split) conformal prediction modifies an underlying point prediction model, which outputs the top-ranked label only, into a set-valued predictor that instead outputs a set of labels. Under the i.i.d. (or more generally, exchangeability) assumption, the resulting sets are provably valid (in terms of coverage) with guarantees being marginal over calibration and test data. \n\nViolation of the i.i.d. assumption invalidates the inference, and adaptations to some structured distribution shifts have been proposed recently in the literature. The current work focuses on a setting where adversarial examples might be present at the test stage. Vanilla conformal is based on considering a collection of candidate prediction sets, parameterized by a single parameter, which is tuned/calibrated using a held-out set for performing set-valued predictions on test data. The authors propose correction of vanilla conformal, which essentially boils down to inflating the threshold in a way that guarantees robustness against adversarial examples with bounded $\\ell_2$-norm (using randomized smoothing), where inflation results in outputting larger the prediction sets. ", "summary_of_the_review": "The current work represents a solid piece of work that takes a step forward towards robust conformal prediction. Within the context of CP under distribution shifts, prior works studied settings where structured/constrained shifts are present. This work focused on a different setting which hasn't been covered in conformal literature before where at the test stage adversarial examples invalidate the vanilla CP. The reasons for lowering the score include: limited theoretical contributions, a limited study of the types of adversarial examples, unaddressed questions stated in the main review.\n\n**Update after rebuttal**\n\nI would like to thank the authors for the detailed responses. Taking into account the general contribution of this work and points mentioned in this and other reviews, I tend to keep the current score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gRvEj3HrEkf", "reviewer": "Reviewer_t8Jp", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I like the proposed idea of using randomized smoothing to construct a non-conformity score that forms a prediction set with a finite-sample coverage guarantee under adversarial noise on the features. The paper is also written in a clear way which gives enough background knowledge to readers who are not familiar with the field of conformal prediction. The motivation of introducing randomized smoothing into the score function was very well illustrated, and the theorems 1 and 2 provided convincing results of the effectiveness of the proposed approach. \n\nI have one major concern of the experimental section. Since the comparison was only done with the non-robust conformal prediction approach, I am wondering if it is possible to compare to other robust CP methods such as those mentioned in Section 4.1. In particular, the authors mentioned that this work \"handles a full distributional shift induced by the adversarial perturbation\". But my understanding is that this work considers only the perturbation on the feature X while P(Y|X) remains intact. It would be helpful if the authors can clarify on this point. \n\nA minor point, there is a typo in Eq. (8), where it should be \\tilde{S}(\\tilde{X}_{n+1}, y).", "summary_of_the_paper": "This paper generalized a data-splitting conformal prediction approach to the adversarial attack setting by combining conformal prediction with randomized smoothing, which yields a prediction set with finite sample coverage guarantee under an l2-norm bounded adversarial noise. The effectiveness of the proposed methods was demonstrated on the CIFAR10, CIFAR100, and ImageNet datasets, showing a significant increase in the coverage size compared to the vanilla conformal prediction method.", "summary_of_the_review": "Overall I like the idea proposed in this paper. Their theoretical and experimental results demonstrated the effectiveness of the proposed approach. My major concern is about comparing with other robust conformal prediction methods in the experimental section. It would be helpful if the authors can provide insights on this.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "VsE_B8IKPg", "reviewer": "Reviewer_m5fr", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**:\n1. This paper considers an under-explored problem, i.e., conformal prediction under adversarial perturbations.\n2. The paper is easy to follow.\n\n**Concerns**:\n1. (novelty on theoretical guarantee) The novelty on the theoretical result is less significant; the correctness of the main theorem is heavily dependent on the condition of a non-conformity score in (7). In particular, finding the Lipschitz constant M_\\delta is the challenging problem and actively researching area (as the paper pointed out), especially the score function is a highly non-linear neural network and an input is high-dimensional. However, given the score function that satisfies (7), constructing a conformal prediction set is relatively straightforward (even though I agree that it's a new result). \n\n2. (preciseness on theoretical guarantee) The statement of Corollary 1 needs to be described more precisely, considering the fact that the literatures of conformal prediction are trying to be rigorous on making the theoretical guarantee; Corollary 1 requires randomly smoothed score function, but we cannot evaluate this function due to the expectation without approximation (as described in the paper). In this case, it would be more appropriate to say \"the prediction set is asymptotically valid\" or consider the samples required for approximating the expectation as a part of sample complexity analysis for the proposed prediction set. I think the latter making this paper theoretically more interesting and novel. \n\n3. (comparison) The most closely related work is Cauchois et al. (2020), but the comparison is missing. The related work section points out the limitation of this work, i.e., \"the f-divergence measure is notoriously difficult to estimate in practice\"); however the proposed approach of Cauchois et al. (2020) is actually evaluated on CIFAR10 and ImageNet; in particular, the core part of this approach is convex optimization, so could be computationally not expensive. Finally, the results of Cauchois et al. (2020) is similar to the results of this paper, so the comparison looks necessary.\n\n4. (CP+SS v.s. RSCP) I think it's not easy to say that RSCP is better than CP+SS; I understand that RSCP satisfies the coverage criterion, but that criterion is satisfied only for the next single example in a usual setup---the probability in (1) is taken over all calibration examples and (X_{n+1} , Y_{n+1}). If the constructed prediction set is conditioned on one fixed calibration set and evaluated over multiple testing examples, the empirical coverage probability of the standard conformal prediction is around the nominal level \\alpha (see Figure 2 in Tibshirani et al. (2019)). In this sense, it's unclear whether RSCP is better than CP+SS. If the paper wants to claim that RSCP is better than CP+SS, I think PAC-style prediction set definition is required (e.g., [R1], [R2], [R3], or [R4]), which construct a prediction set conditioned on a fixed calibration set for correctness guarantee. \n\n* [R1] https://arxiv.org/abs/1209.2673\n* [R2] https://arxiv.org/abs/2001.00106\n* [R3] https://arxiv.org/abs/2101.02703\n* [R4] https://arxiv.org/abs/2106.09848\n\n\n5. Other comments\n- The description on conformal prediction is not precise; the paper said it requires i.i.d. but exchangeability is enough. Moreover, it can be applied to regression.\n- Related to the above, is the i.i.d. assumption in Theorem 1 necessary? Is the proposed approach only applicable to classification? \n- \"however, none of them addresses the adversarial setting specifically\" and \"Both approaches differ from ours, which handles a full distributional shift induced by the adversarial perturbation\": I think they are strong or incorrect since the adversarial setting is a special case of covariate shifts. \n\n", "summary_of_the_paper": "This paper tackles the conformal prediction problem under adversarial perturbations, where the conventional exchangeability is violated. The proposed approach combines the non-conformity score with randomized smoothing and the standard conformal prediction. The proposed approach is evaluated over three different image benchmarks (i.e., CIFAR10, CIFAR100, and ImageNet) and demonstrated its efficacy by comparing the naive conformal prediction and the naive conformal prediction with the randomly smoothed non-conformity score. ", "summary_of_the_review": "Overall, this paper handles an interesting and timely problem, but the theoretical and empirical results are less significant compared to the known literatures as described in the main review; I lean to reject, but willing to discuss to adjust my understanding.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0stWudOQRmc", "reviewer": "Reviewer_Cuc8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers the conformal prediction problem in an adversarial setting, which is new and important in my perspective. It is very well-written, which I enjoyed reading. The idea of using randomized smoothing to construct a robust conformity score is quite novel and theoretically sound for conformal prediction, despite the techniques it used are well-known in the field of adversarial robustness. The empirical studies clearly demonstrate the vulnerability of standard conformal prediction method in the presence of adversarial examples, which support the motivation of the paper. Nevertheless, I have the following general questions for the authors:\n\n1. In Figure 5, you show the marginal coverage against adversarially-perturbed inputs for different methods. How about the marginal coverage for normal examples? \n\n2. The method “CP + SS” is not able to satisfy the desired coverage. Is this because the base classifier is trained to be robust against Gaussian noise instead of against worst-case adversarial perturbations? I am wondering whether you could achieve the coverage by using the conformity scores outputted by an adversarially-robust classifier?\n\n3. One of the evaluation criteria for conformal prediction you used is average set size. Based on Figure 5, it seems that HPS based method outperforms APS based method by a large margin. But you mentioned in Section 2 that “APS reflect better the underlying uncertainty across sub-populations”. Do you have any empirical results supporting this? In general, how to decide which method to use if we want to deploy the conformal predictors you proposed.\n", "summary_of_the_paper": "This paper proposes a generic method to construct conformal prediction sets in an adversarial setting. Since standard conformal prediction method assumes an i.i.d. assumption for training and testing input, its generated prediction sets for adversarial examples will not satisfy the coverage guarantee. Build upon on randomized smoothing, the paper then proposes a new non-conformity score and raise the threshold to account for the adversarial transformations. It then proves that the prediction sets constructed by the proposed method satisfy the coverage guarantee for worst-case scenarios. Empirical evaluations are also performed on benchmark datasets, which justify the effectiveness of their method.\n", "summary_of_the_review": "Overall, I think the paper is well-written and reach the acceptance bar of ICLR. Both theoretical and empirical results support the main claim of the paper. Therefore, I vote an accept for this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of producing distribution-free prediction sets using conformal prediction that are robust to test-time adversarial perturbations of the input data. The authors point out that these perturbations could be label and covariate dependent, and hence different from covariate-shift handled in Tibshirani et al 19, the label-shift handled in Podkopaev and Ramdas 21, and the f-divergence shifts of Cauchois et al 2021. 

The authors propose a relatively simple idea that has appeared in other literatures like optimization but appears to be new to the conformal literature: (i) use a smoothed (using Gaussian noise on X, and inverse Gaussian CDF) nonconformity score function, in order to control its Lipschitz constant, (ii) utilize a larger score cutoff than the standard 1-alpha quantile of calibration scores employed in conformal prediction. The observation that point (i) alone lends some robustness to adversarial perturbations of the data is interesting. As several experiments in the paper and responses to reviewers show, this comes at the (apparently necessary) price of larger prediction sets. 

I read through all the comments and also the supplement. The authors have responded very well to all the reviewers questions/concerns, adding significant sections to their supplement as a result. Three reviewers are convinced, but one remaining reviewer requested additional experiments to compare with Cauchois et al (in addition to all the others already produced by the authors originally and in response to reviewers). However, the authors point out that the code in the aforementioned paper was not public, but they were able to privately get the code from the authors during the rebuttal period. At this point, I recommend acceptance of the paper even without those additional experiments, since it is not the authors' fault that the original code was not public. Nevertheless, I suggest to the authors that, if possible, they could add some comparisons to the camera-ready since they now have the code.

I congratulate the authors on a nice work, a very solid rebuttal, and also the astute reviewers on pointing out various aspects that could be improved. 

Minor point for the authors (for the camera-ready): I would like to comment on the Rebuttal point 4.4 in the supplement, which then got further discussed in the thread. The reviewer points out four references [R1-R4]. I will add one more to the list [R5] https://arxiv.org/pdf/1905.10634.pdf (Kivaranovic et al, appeared in 2019, published in 2020). I think the literature reviews in this area are starting to be messy, and all authors need to do a better job. Clearly, the original paper of Vovk et al already establishes various types of conditional validity (and calls it PAC-style guarantee), produces guarantees that others in this area produce, and it appears that much recreation of the wheel is occurring. For eg, [R2, R4] do not cite [R5], despite [R5] appearing earlier and being published earlier, and having PAC-style guarantees and experiments with neural nets, etc. However, in turn, [R5] do not cite Vovk [R1], but [R2, R4] do cite [R1]. (And [R3] does not seem to be relevant to this discussion of conditional validity?) In any case, I am not sure any of these papers need citing since the current paper does not deal with conditional validity. If at all, just one sentence like "Conditional validity guarantees, of the styles suggested by Vovk [2012], would be an interesting avenue for future work".
Decision: Accept (Poster)