Verifiably Robust Conformal Prediction
Authors: Linus Jeary
Tom Kuipers
Mehran Hosseini
Nicola Paoletti
Venue: NeurIPS 2024 poster (2024)
Keywords: Conformal Prediction
Adversarial Attacks
Distribution Shift
Formal Verification
Primary area: safety_in_machine_learning
TL;DR: We introduce two verifiably robust conformal prediction frameworks that are robust against adversarial perturbations and always guaranteed to return the desired coverage in the presence of such adversarial attacks.

Abstract: Conformal Prediction (CP) is a popular uncertainty quantification method that provides distribution-free, statistically valid prediction sets, assuming that training and test data are exchangeable. In such a case, CP's prediction sets are guaranteed to cover the (unknown) true test output with a user-specified probability. Nevertheless, this guarantee is violated when the data is subjected to adversarial attacks, which often result in a significant loss of coverage. Recently, several approaches have been put forward to recover CP guarantees in this setting. These approaches leverage variations of randomised smoothing to produce conservative sets which account for the effect of the adversarial perturbations. They are, however, limited in that they only support $\ell_2$-bounded perturbations and classification tasks. This paper introduces VRCP (Verifiably Robust Conformal Prediction), a new framework that leverages recent neural network verification methods to recover coverage guarantees under adversarial attacks. Our VRCP method is the first to support perturbations bounded by arbitrary norms including $\ell_1$, $\ell_2$, and $\ell_\infty$, as well as regression tasks. We evaluate and compare our approach on image classification tasks (CIFAR10, CIFAR100, and TinyImageNet) and regression tasks for deep reinforcement learning environments. In every case, VRCP achieves above nominal coverage and yields significantly more efficient and informative prediction regions than the SotA.

Verifiably Robust Conformal Prediction
Linus Jeary' Department Informatics King's s College London, UK linus. jeary@kalkkkk ac
Tom Kuipers"
Department of Informatics King's s College London, UK tom. kuiperskkel ac.
Mehran Hosseini
Nicola Paoletti
Department of Informatics King's s College London, UK mehran www..hossseecccccc
Department of Informatics King's s College London, UK nicola. pwoletti@kcl.cco
Abstract
Conformal Prediction (CP) is a popular uncertainty quantification method that provides distribution-free, statistically valid prediction sets, assuming that training and test data are exchangeable. such a case, CP's prediction sets are guaranteed cover the (unknown) true test output with user-specified probability. Nevertheless, this guarantee is violated when the data is subjected to adversarial attacks, which often result in significant loss of coverage. Recently, several approaches have been put forward to recover CP guarantees in this setting. These approaches leverage variations of randomised smoothing produce conservative for the effect of the adversarial perturbations. They are, however, limited in that they only support éz-bounded perturbations and classification tasks. This paper introduces VRCP (Verifiably Robust Conformal Prediction), a new framework that leverages recent neural network verification methods recover coverage guarantees under adversarial attacks. Our VRCP method is the first to support perturbations bounded by arbitrary norms including l, f2. and foc. well regression tasks. We evaluate and compare our approach image classification tasks (CIFARIO, CIFARIO0, and TinylmageNet) and regression tasks for deep reinforcement learning environments. In every case, VRCP achieves above nominal coverage and yields significantly more efficient and informative prediction regions than the SotA.
which account
Introduction
Conformal Prediction (CP) (Vovk al. 2005 Angelopoulos and Bates 2021) is a popular uncertainty quantification method. In essence, is wwwel-agnosteeeeeeo distribution-fn free framework that allows one construct prediction sets that are guaranteed to include the true (unknown) output with probability greater than where E (0, 1) is user-specified miscoverage/error rate. In other words, for test point (æx+1, \n+1), CP seeks to construct a prediction C(xx41) such that the following coverage (a.k.a. validity) guarantee holds:
1...)..--11 (b+11 C(#n+1)) 2
(1)
Importantly, the above guarantee holds when the calibration data, used to construct C( (1m,4)), and the test point are exchangeable (a special case is when calibration and test data are i.i.d.).
Authors contributed equally.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Vanilla
VRCP
VRCP C
RSCP
RSCP (PTT)
1000
Freusey
Fressacy
Frequacc
Frequcccy
1000
Se1S
Figure 1: Distribution of prediction set sizes for vanilla conformal prediction (vanilla CP) which violates Eq. ( well as for our proposed robust algorithms (VRCP-I and VRCP-C) along with the SotA (RSCP+ and RSCP+ (PTT), see Section B on the CIFAR1O dataset. As we observe, VRCP-I and VRCP-C closely resemble the spread of vanilla CP prediction set sizes, whilst the SotA falls short of achieving this. Here we use an adversarial perturbation of radius e = 0.02, eπror rate a = 0.1, number of splits Plplits 50 and smoothing parameter (used in RSCP+ and RSCP+ (PTT) σ 2e.
When exchangeabilitty is violated, e.g., in the presence of test-time distribution shifts, CP's coverage guarantee (I) ceases to hold, and we cannot rely on the prediction sets it produces. In this work, we address shifts induced by adversarial perturbations on the test inputs. In particular, focus perturbations in the form of additive E, -bouuddddd noise.
To recover guarantees under adversarial inputs, the general mechanism is to inflate the prediction set to permit larger degrees of uncertainty. However, special care must be taken to avoid producing overly large even trivial sets i.c. those containing all possible outputs such sets do not provide any useful inference.
Contributions We propose CP framework that provides statistically valid prediction sets despite the presence of é -y-uuunded adversarial perturbations inference time. Formally, for any adversarially perturbed test point Øn pn-1 + ö, our method produces udversarially robust sets C. that enjoy
the following guarantee:
Plan+1 E C.(ā++1)) 2 1 a Ag s.t. ||0|, S.
While CP uses underlying predictor f. often neural network (NN), to construct prediction regions, the novelty of our approach to leverage NN verification algorithms to compute upper and lower output bounds of f(x') for any x' (x) (æ' || æ1Ip c)- We these bounds inflate the CP regions, resulting in provably robust and efficient prediction sets. To the best of our knowledge, this is the first work that combines NN verification algorithms and CP construct adversarially robust prediction sets. We call our method VRCP (Verifiably Robust Conformal Prediction).
Recent work (discussed in Section 3) achieves adversarially robust coverage using probabilistic methods, specifically, randomised smoothing (Cohen et al. 2019). Our approach overcomes some of the theoretical and empirical drawbacks of these prior methods, which are restricted to classification tasks with l no-m bounded guarantees and are overly conservative in practice.
Thanks to our verification- based approach, VRCP is the first to extend adversarially robust conformal prediction to regression tasks and the first to go beyond fn-morm bounded guarantees. Section 4 we introduce two versions of VRCP that apply verification at calibration and inference time, respectively. Further, in Section [ we empirically validate our theoretical guarantees and demonstrate a direct improvement over previous work in terms of prediction set efficiency (i.e., average set size) compared to prior work. Fig. ssowss an extract our results on CIFAR 10, demonstrating that VRCP yields more informative (tighter) prediction regions, trend that observe experimentally across all our benchmarks.
2 Preliminaries
We denote with R,, the set of positive real numbers. Vectors x E Rd are shown in bold italic and scalars x E R in italic typeface. We denote the norm used to make I&d normed vector space by I| This could for instance be é1, l2. or foo-norm. Whenever specific norm is intended, we indicate it using an index, e.g., 11-1/2 indicates the fo-nrmm We denote the e-ball around point æ E Rd with respect to the used norm by (x).

---

2.1 Conformal Prediction
We provide brief overview of the inductive (or split) vanilla CP approach. Suppose we have dataset D containing pairs (z, y) sampled i..d. from an (unknown) data data-generating distribution over a feature space X C IRd and label space Y such that D = { vi).....,, .......,mm..... ( ymm)
We partition the dataset into disjoint training and calibration sets Pwain and Deal, letting (Deall- We fit a predictor f on Drain and define score function S (X x Y) - I as some notion of prediction error, such S(æ, y) fa) y/ when f is regressor, or S(x, f is a classifier with f(-) being y' 's predicted likelihood.
1 f(x),, when
After applying the score function to all calibration points, we construct the score distribution as F (n+1) + Ex= 6,,/n+1, where 5, the Dirae distribution with parameter s, 8; S Vi) and 8e represents the unknown score (potentially infinite) of the test point.
Given miscoverage/error rate a and test point (I++11 " by including all labels that appear sufficiently likely w.r.t. the score distribution: C(æn+1) = {y E Y S(x++1,9) S (f)) where Q1 (F)) is the a quantile of F. This set satisfies the marginal coverage guarantee in Eq. if the test point and the calibration points are exchangeable.
define the prediction set C(
2.2 Adversarial Attacks
Neural networks have been shown to be vulnerable to adversarial attacks, i.c. small changes to their input that jeopardise the prediction (Szegedy et al. 2014) Biggio and Roli 2018). This notion can be formally defined as maximising
adversarial objective function (e.g., the loss of the true label) subject to | # I c. Alternatively, it can be defined as finding an adversarial example & E Rm" such that | = S e and I[ ()) - yll 2 for a given neural network f Rd + R
2.3 Neural Network Verification
Various approaches have been proposed to verify the robustness of NNs against adversarial attacks.
These approaches can be divided into complete and incomplete algorithms. Given neural network f. verifier is complete if it allows computing exact bounds f and f for the image (B, {f(')) : x' E (x)), i.e., such that
min (f(z'), z' (.,
max (f(z')) (x)
(3)
where min and max are computed coordinate-wise for vector-valued NNs. A verifier is incomplete, but sound, if it computes bounds that are valid but not exact, i.e., such that:
< min (s(z'), fT (
max (f(z')) a e'EB.(
Our results are verifier-agnostic, meaning that they are valid for any verifier that can produce exact bounds (as in Eq. (3)) or conservative bounds (as in Eq. 4 depending on the completeness or incompleteness of the verifier used. The fastest and simplest way to compute the bounds in Eq. (4)
to propagate the bounds on the input B, (a)) through the network compute the output bounds. Several methods based on this approach have been proposed (Gowal et al.) 2018 Wang et al. 2018 Zhang et al., 2018a [Batten et al. 2024 Lopez et al. 2023). At the expense of fast computation speed, these methods may result in loose bounds in Eq. (4). On the other hand, several complete methods (Pulina and Tacchella| 2010 Katz et al., 2017; Hosseini and Lomuscio 2023) for NN verification have been put forward. Even though these methods compute exact bounds, their downside is their high computational cost.
Related Work
Adversarially Robust Conformal Prediction Gendler al. (2021) introduced an algorithm called Randomly Smoothed Conformal Prediction (RSCP) that integrates randomised smoothing (Duchi al. 2012: Cohen et al. 2019 Salman al., 2019) with CP provide robust coverage under adversarial attacks. RSCP replaces the CP score function S(æ, y) with a smoothed score
S(æ y) obtained by averaging the values of S(x v, y) over RMC realisations of Gaussian noise
3

---

vector ~ o for given smoothing level σ. To correct for potential ég nn-morm bounded e perturbations inference time, the critical value computed over the smoothed scores is inflated by e/o. This method produces empirically sound results, but the provided formal guarantees were found to be invalid in a later work (Yan al. 2023). as discussed below.
Provably Robust Conformal Prediction Yan et al. (002)) address the issue with the robustness guarantee of Gendler et al. (2021) by correctly bounding the estimation error caused by the Monte- Carlo sampling used when generating the smoothed scores. The bound introduces an additional hyperparameter 3 such that they now find the Q1 11 of smooth calibrated scores and inflate by Hoeffding's s bound 1n(0)//2mw before correcting by e/o. Furthermore, the smoothed scores the test points are decreased by an empirical Bernstein bound. This further inflation of the critical value and deflation of smooth scores for each test point often cause their amended algorithm, so-called RSCP+, to generate trivial prediction sets.
To address this issue, the authors introduce two methods to improve the efficiency of RSCP+. Firstly, they use robustly calibrated training (RCT), training-time regularisation technique that penalises NN parameters that contribute high scores for the true label. Our approach assumes that the underlying classifier is given; hence, we do not evaluate RCT in our experiments.
Secondly, they implement post-training transformation (PTT), which aims to decrease the values of the smoothed calibration scores that lie between Q1-a (the critical value of the base scores) and Q1-a (that of the smoothed scores). To this purpose, they transform the CDF of the smoothed scores by composing learned ranking and sigmoid transformations with hyperparameters b and T using holdout set Phold sampled i.ddd from Deat. PTT however is not theoretically guaranteed to improve the average set sizes computed by RSCP+ and, in many cases, its efficacy is largely dependent how representative the sampled holdout set is of the calibration set. We demonstrate the effect of PTT's sample dependence empirically in Section 5.1
Probabilistically Robust Conformal Prediction Ghosh et al. (2023) also focus the adversarial setting but maintain relaxed form of robust coverage, where input perturbations ô are drawn from specific distribution and only a proportion of such perturbations are sought to be covered. In contrast, we do not make assumptions about the noise distribution, and we account for any e-bounded perturbation.
All the works discussed here rely on randomised smoothing Duchi et al. (2012) and as such are limited to the Eg- norm. In contrast, our VRCP approach relies on NN verifiers, can be used with any f--norms supported by the verification method, and does not require smoothing hyperparameters or holdout sets.
4 Verifiably Robust Conformal Prediction (VRCP)
In this section, we formally introduce two variants of VRCP. Both methods allow us to construct adversarially robust prediction sets at inference time.
The first variant, VRCP via Robust Inference (VRCP-I), employs NN verification at inference time compute lower bound of the score for the given test input (best-case score), thereby obtaining more conservative regions. The calibration procedure is computed as in standard CP. The second variant, VRCP via Robust Calibration (VRCP-C), instead uses NN verification at calibration time to derive upper bounds for the calibration scores (worst-case), thereby obtaining a more conservative calibration threshold (critical value). This allows us to use the regular scores inference time, without requiring NN verification.
4.1 Verifiably Robust Conformal Prediction via Robust Inference (VRCP-I)
Given calibration set Deat. test input 1. and score function S(:;),, we compute the prediction set for 2o41 as follows.
We are aware of related contemporaneous work by Zargarbashi et al. 2024 However, at the time of submission, neither the manuscript the code available.

---

1. For each E Y we compute,
(In+1, v) 3 ((ns)()))))
inf
S(a'
(5)
The robust prediction set is then defined as
( = {v s (In+1, S (1)a(F))
(6)
Below, we show that we are able to maintain the marginal coverage guarantee from Eq. 2 for any -n-norm bounded adversarial attack.
Theorem 1.
Let Ān+1 = In+1 + ô for a clean test sample 2n+1 and ||ô|| S e. The prediction set a.
(Z(nn)) defined in Eq. (6 satisfies Wa+1 C. (T
Proof. We obtain that
P Pl Ce(2n+1)] =P [ (m++1,b++1) S Q1-a(F)]
PP
inf (aa,,)n+1+= S (Q)=a(F)
by Eq. (5)
(B.1))
IP (((nt11,94t))) S QI-a(F)) 2 1
4.2 Verifiably Robust Conformal Prediction via Robust Calibration
Given a calibration set Deal, a test input #n+11 and score function .), we compute the robustly calibrated prediction set for #x+1 as follows.
1. We compute the upper-bound calibration distribution as:
800
7
where s.
sup of (m.))
S(z' y1).
(7)
(n 1)
n
i=1
2. The robust post-calibration prediction set is then defined as
C.(xn+1) = b S(xn+1, v) S Q1-a(F") }}.
(8)
Theorem 2. Let #n+1 -.+1 + 8 for a clean test sample I4 and [|ö||p S e. The prediction set (T()n)1) defined in Eg. satisfies TP [u++1 (G 2 a.
Proof. We have that
P Plyn+1 E C.(2n = S( 1n+1 S 5Q1-0 (FT)]
5(in Q1-a ({ (are S(l', y "
u UnSo))
P
sup 5(0', Qi-a (f x'EB.(a))
u (00) }
P
sup
S(x'
i=1
21-a
Let PT denote the distribution of (æ: T y) where x: T argsup x' (m) S(x', v)) and (æ, y) ~ P. The final inequality above holds since equivalent to constructing a CP prediction set using n ii.d realisations of p and evaluating it on #n+1 ~ PT, The resulting set will include the true test output yn+1 with probability at least 1 a.
4.3 Computation of score bounds
Classification In the classification setting, we use the score function proposed in (Lei et al. Gendler et al. 2021):
2013
S(x, y) 1 f(z),)
(9)
5

---

where f(z)y E (0, is the model-predicted likelihood for label In this setting, to compute s and S (required by VRCP-I and VRCP-C, respectively), it suffices to use NN verification algorithms to derive the output bounds for (x)). Specifically, in VRCP-I, for test input In+1 and for each y E Y we derive - (xn+1, as
(#n+1. -1 fZ
(10)
where f(xn+1), denotes the upper bound computed by the neural network verifier for the model- predicted likelihood of label E Y and input I-
In VRCP-C, for each calibration point (ar, yi) compute 8 (2:, M/3)
( V1) 1 1=((x;)) f())))
(11)
where f( denotes the lower bound of the model output for label y; given input æ;.
Regression In the regression tasks, we follow the conformalized quantile regression (CQR) method- ology proposed by (Romano al., 2019). We train quantile regressors fow.. and fauig. to estimate the Olow a/2 and Otiggh 1 a/2 quantiles of y In CQR, we use the following score function:
S(x; v) - max {S (ax) - y: y - Soun (a))-
(12)
Unlike classification, where the label space is discrete, we cannot construct the region explicitly by enumerating all possible outputs y. Instead, the prediction region for a given test point ((x++1) constructed implicitly. by adjusting the quantile predictions by the critical value of the calibration
distribution Q1-a(F (F), ); as follows:
C(xn+1) [Saw (2n+1) - Qi-a Sana (xn+ 1) + Qi-a(F)
(13)
In both VRCP-CO C and VRCP-I, the score function leverages NN verifier to derive the bounds over the upper and lower quantiles of the model. In VRCP-C CC we compute the worst-case calibration scores as:
(a:, yt) = max {ST (m.) Vi V/ Salu (x:))-
(14)
In VRCP-I for classification, for each output we check inclusion in C, by using the best-case score s-. As explained above, explicit enumeration is infeasible for regression, and so we construct our robust region by replacing predicted quantiles in Eq. [3) with their conservative approximations, as follows:
(e(xn+1)
[ (In+1) Q1-a (F), (xn-1) + QI)
(15)
The above-defined region is equivalent to enumerating all possible outputs y. and for each, considering the best-case score s- max (fot (xx+1) y, y form (x=+1)} A proof is available in Appendix|3 A
nice property of both VRCP-I and VRCP-C that they guarantee that they only increase the size of the prediction set for any input æ compared to vanilla CP, thus will always attain at least as much coverage as the vanilla CP procedure. Moreover, as we show in Section [5] both algorithms do not trivially inflate the size of the prediction sets and maintain similar distribution of set sizes. This formalised in the Proposition [ which proved Appendix A
Proposition 1. Let C(x)) and (a)) be the prediction sets obtained using vanilla CP and VRCP (using VRCP-I or VRCP-C), respectively. For any input æ. we have that C(x)) C (.))
Evaluation
We evaluate VRCP-I and VRCP-C on classification (image) and regression (RL) benchmarks, and compare them against the SotA approaches on each benchmark. For all the networks used, we did not perform adversarial training we assume that the attack budget is unknown at training time. Nonetheless, both our approaches can benefit from adversarial training, as it results in models that more verifiable and have tighter bounds for the same attack budget
Code for the experiments is available at: https://gituub..o//ddt/laaaa
Robust CP

---

5.1 Classification Experiments
We evaluate each method using a nominal coverage of 0.9 and report the 95% confidence intervals for coverage and average set sizes computed over 50 splits (Nuplits = 50) of the calibration, holdout and test set.
Bounds We use the verification library auto LiRPA (Xu et al. 2020a to compute the output bounds for f(x)) required in Eq. (0) and Eq. 11 for VRCP-1 and VRCP-C respectively. In particular, two SotA GPU APU-parallelised incomplete NN verification algorithms, CROWN Zhang et al. (2018b) and a-CROWN Xu et al. (020b). In brief, CROWN performs linear bound propagation and a-CROWN employs a branch-and-bound algorithm to tighten the CROWN bounds at the expense of slower verification times. Therefore, we use CROWN to compute the output bounds for the TinylmageNet model and a-CROWN for the smaller CIFAR10 and CIFARION models.
Our CIFARIO I0 model with a-CROWN takes R 0.5s per image to compute bounds with e = 0.03, whereas our larger CIFARIO0 model takes R 7.2s with 0.02. Comparatively, computing the smoothed scores takes R 0.09s per image to compute on both models under the same respective e values. The largest model for the TinyImageNet dataset uses CROWN to compute bounds at a rate of = 0.2s per image whereas the smoothed scores take Rs 0.24s. All measurements are made with respect to the hardware details listed in Appendix
Attacks We use the PGD attack algorithm (Madry et al. 2017), which is popular white-box attack algorithm to generate adversarial inputs with respect to either the Eg or -nomm.
Models For all datasets, we train a CNN model on training set images with random crop and horizontal flip augmentations. Full model details are outlined the appendix.
Hyperparameters RSCP+ based approaches use = 2e, B 0.001 and those with PTT use [Dhotal = 500, b = 0.9 and T = 1/400. For PGD, we choose a step size of 1/255 and compute 100 steps for each attack. For CIFARIO and CIFAR100 [Duaia| 50,000 and for TinylmageNet [Puain| = 100,000. For all datasets [Deal = 4,500 and (Diesl = 5,000.
Results In Table D benchmark both our methods against the baseline vanilla CP (which is agnostic of the attack), RSCP+ and RSCP+ with PTT. At inference time, images are attacked using PGD generate f2-norm bounded attacks with e 0.02 for CIFARI00 and TinyImageNe and == 0.03 for CIFAR1O.
In all domains, the vanilla CP method fails to construct valid prediction sets with nominal marginal coverage, as expected. RSCP+ maintains robust marginal coverage but produces trivial prediction sets in all settings due to the highly conservative inflation of the threshold with respect to the calibration scores. Using PTT improves RSCP+'s 's performance but introduces significant variance in the set sizes: in many cases, PTT still produces trivial prediction sets and is heavily dependent on the sampled holdout set for RSCP+ to generate useful predictions.
Both of our methods have minimal sample dependence, demonstrated by very small variability in coverage and size over the 50 splits. We obtain prediction sets with substantially smaller average sizes than the other robust approaches, and hence, they provide more informative uncertainty esti- mates. VRCP-I provides slightly more efficient regions than VRCP-C. Still, it implics additional computational overhead at inference time because it requires computing bounds via NN verification for each test sample. In contrast, in VRCP-C, bounds are computed only once at calibration time. On the other hand, in an environment where we may want to change for different test points at inference time, VRCP-I would be a sound choice, while VRCP-C would require re- re-calibration.
Effect of increasing adversarial noise Fig. shoshows the impact of inereasing across all evaluated robust methods. Our methods consistently produce smaller average set sizes with minor sample dependence, and simultancously provide a more conservative marginal coverage than RSCP+ (PTT). We remark that, unlike RSCP+, we do not require a holdout set or any score function transformations.
Effect of increasing Monte-Carla samples Fig. 2ajdisps the influence of the TMc hyperparame- ter the RSCP+ based methods with respect to our CIFARIO 10 model. Whilst increasing samples
7

---

Table Marginal Coverage and Average Set Sizes for different methods CIFARIO, CIFARI00
and Tiny ImagneeeN All results record 95% confidence interval with Aspplis = 50, a = 0.1, 2e,
AMC 1024, c 0.03 for CIFARIO and 0.02 otherwise.
CIFARIO
CIFARI00
TinyImageNet
Method
Coverage
Size
Coverage
Size
Coverage
Size
Vanilla
0.87840.002
1.721=0.008
0.890=0.002
6.702=0.058
0.88640.000
38.200
RSCP+
1.00000.000
10.000=0.0000
I. 1.000+0.000
100.000+0.000
1.000+0.000
200.000=0.000
RSCP+ (PTT)
0.983+0.008
8.357=0.780
0.925=0.010
26.375#9.675
0.931+0.013
90.64 20.64442200663
VRCP-I
0.986+0.00
4.451=0.01
0.971=0.001
22.530=20.10
0.958+0.001
72.486+0.311
VRCP-C
0.995+0.000
5.02100.010
0.983=0.000
23.676+0.131
0.965=00.001
77.761#0.352
1.00
Marginal Coverage
0.98
Average Set
0.96
VRCP-1
0.95
VRCP-C
BSCP
RSCP (PTT)
256
612
1024
2018
4096
256
512
1024
2048
4006
RMC
(a) Varying 7IME for Pespiis
50, 0.03, 0.1, and 2c.
0.98
Marginal Chverage
Average Set.
8
0.94
VRCP-C
0.92
RSCP1
(PTT)
2
0.90
0.01
0.02
0.03
0.04
0.05
0.01
0.02
0.03
0.01
0.06
(b) Varying value Neplis 50, 2e,
0.1, and MMC = 1024.
Figure 2: Marginal Coverage and Average Set Sizes CIFAR100 with 95% confidence intervals.

---

improves the performances of randomised smoothing approaches, we incur large computational overhead when computing the smoothed scores. our experiments in Table we fix MMC 1024 which is four times larger than the value for VMC used in previous work (Gendler et al. 2021 Yan
al. 2023) as a trade-off between prediction quality and computation.
Beyond f2-norm bounded attacks Table demon- strates that both of our methods generalise to other Ep- bounded perturbations other than for when p 2 which RSCP+ is limited to. In particular, we examine the Loc. where even small can cause misclassification. We experiment using CIFAR10 and use e = 0.001. PGD used to generate fae bounded adversarial examples.
Table 2: Marginal Coverage and Average Set Sizes for perturbations with respect the -orm on the CIFARIO dataset. All results record 95% confidence interval with Neplits = 50, a = 0.1 and = 0.001.
CIFARIO
Set size distribution From Fig. I we can visually examine the sample dependency issue that the PTT in- troduces. In the splits where the holdout set allows the PTT to make an informative transformation, RSCP+ is able to make quite reasonable predictions, otherwise, RSCP+ just returns trivial sets. This clearly an un- desirable property and adds significant variance to the predictions.
Method
Coverage
Size
Vanilla
0,872=0.002
1.737=0.007
VRCP-I 0.947=0.00) VRCP-C
2.262+0.008
0.931#0.001
2.342+0.008
Both of our methods increase the spread of the average set sizes to account for the presence of adversarial examples whilst still maintaining consistent distribution.
5.2 Regression Experiments
We evaluate our VRCP framework on regression tasks from the PettingZoo Multi-Particle Environ- ment (MPE) library Terry et al. (202T) for deep reinforcement learning. these environments, the world is a 2D space containing n agents (of which some may be adversarial) and m landmarks, which are defined as circles of fixed radii. The position of the landmarks fixed, and agents traverse the space according to second-order motion laws. We evaluate our method on three tasks:
Adversary The good agents must to reach specific goal landmark whilst avoiding the adversaries. We use good agents, adversary and 2 landmarks.
Spread All agents collaborate and minimise the distance each landmark. We set the number of agents and landmarks equal to 3.
Push In this task, there is single good agent, adversary and landmark. The task is for the adversary maximise the distance between the landmark and the good agent.
In our experiments, for data-generation we select 5,000 random initial world configurations and, for each, simulate 25 Monte-Carlo trajectories of length & = 5. The regression task for all environments predict the upper and lower quantiles of the total cumulative reward over the i steps, given as input the initial world state. As in the classification experiments, we partition the dataset into the |Dirain 1,000, [Deal] = 2,000 and [Drest 2,000.
following partitions:
For computing the bounds, we use CROWN N Zhang et al. (2018b) with boundeed perturbations. To generate the adversarially perturbed test points, we use the Fast Gradient Sign Method given in (Goodfellow et al. 2015).
As seen in Table both VRCP methods recover the marginal coverage guarantees in the presence of adversarial perturbations, whereas vanilla CP fails drastically after e = 0.02. We note that the performance of VRCP-C and VRCP-I are similar, although VRCP-I tends to produce more conservative intervals (without sacrificing efficiency).
Limitations
VRCP's scalability depends on that of the underlying neural network verifier. We evaluated VRCP on small to medium-sizze sized neural networks. For large networks, existing complete verification methods

---

Table Marginal coverage and average interval lengths for each MPE regression task for various
perturbations bounded by an 20 noom. All results record a 95% confidence interval with splits 50.
Perturbation
0.01
0.02
0.04
Method
Coverage
Length
Coverage
Length
Coverage
Length
Adversary
Vanilla
0.871#0.006
0,480=0.006
0.834+0.007
0,484+0.006
0.745=0.009
0,490#0.006
VRCP-1
0.928=0.004
0.605#0.006
0.951=0.003
0.67340.006
0.985=0.002
0.855#0.006
VRCP-C
0.910=0.005
0.534+0.006
0.923+0.005
0.606+0.0066
0.966#0.003
0.806*0.005
Vanilla
0.86410.005
0.595+0.005
0.83440.00
0.602+0.005
0.768+0.006
0.612+0.005
Sproad
VRCP-I
0.929 004
0.690=0.006
0,95840. 000
0.769=0.006
0,991 +0.001
0.992+0.006
VRCP-C C
0.908+0.005 0.5
0.663=0.006
0.935+0.004 004
0.762+0.005
0.977+0.002 002
1,054=0.006
Vanilla
0.891
0.643#0.006
0.875+0.007
0.646#0.006
0.841
0.652+0.006
Puoh
VRCP-1
0.917=0.006
0.687#0.0066
0,934=0.005
0,961=0.003 0.72
0.800#0.006
VRCP-C 0.905#0.005
0.674+0.006
0,910=0.005
0.711+0.005
0.924#0.005
0.795+0.005
would become computationally infeasible, while incomplete methods would produce bounds that are too loose to be useful. However, it is important to note that since VRCP is agnostic of the specific verification tool used, it would directly benefit from any future advances in neural network verification. Thus, as neural network verification tools continue to evolve and improve, so does VRCP.
7 Conclusion
We introduced Verifiably Robust Conformal Prediction (VRCP), a novel framework that leverages conformal prediction and neural network verification to produce prediction sets that maintain marginal coverage under adversarial perturbations. We presented two variants: VRCP- C, which applies verification at calibration time, and VRCP-I, which applies verification at inference time.
Extensive experiments classification and regression tasks demonstrated that VRCP recovers valid marginal coverage in the presence of l,, f2, and -norm bounded adversarial attacks while producing more accurate prediction sets than existing methods. VRCP is the first adversarially robust CP framework supporting regression tasks and perturbations beyond the f--norm, achieving strong results without relying on probabilistic smoothing or posthoc corrections. VRCP's thcoretical guarantees and empirical performance showcase the potential of leveraging verification tools for uncertainty quantification of machine learning models under attack.
Acknowledgments and Disclosure of F Funding
This work is supported by the "REXASI-PRO" H-BU project, call HORIZONN-LL--20--HUUNNN 01-01, Grant agreement ID: 101070028.
References
V. Vovk, A. Gammerman, and G. Shafer, Algorithmic learning in random world. Springer, 2005, vol. 29.
A. N. Angelopoulos and S. Bates, "A gentle introduction conformal prediction and distribution-free free uncertainty quantificationn" arXiv preprint arXiv:2107.07511, 2021.
J. Cohen, E. Rosenfeld, and Z. Kolter, "Certified adversarial robustness via randomized smoothing." in international conference on machine learning. PMLR, 2019, pp. 1310-1320.
C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, J. Goodfellow, and R. Fergus, "Intriguing properties of neural networks," " in 2nd International Conference on Learning Representations, ICLR, 2014.
B. Biggio and F. Roli, "Wild patterns: Ten years after the rise of adversarial machine learning," Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018, pp. 2156.
10

---

S. Gowal, K. Dvijotham, R. Stanforth er al., "On the effectiveness of interval bound propagation for training verifiably robust models," 2018, arXiv preprint arXiv:1810.12715.
S. Wang, K. Pei, J. Whitehouse, Yang, and S. Jana, "Formal security analysis of neural networks using symbolic intervals," in USENIX Security Symposium. USENIX Association, 2018, pp. 1614.
H. Zhang, T.-W. Weng, P.-Y. Chen, C.-J. Hsich, and L. Daniel, "Efficient neural network robustness certification with general activation functions," in Advances in Neural Information Processing Systems, NuerIPS, 2018.
B. Batten, M. Hosseini, and A. Lomuscio, "Tight verification of probabilistic robustness in bayesian neural networks," in The 27th International Conference on Artificial Intelligence and Statistics, AISTATS, vol. 238, 2024.
D. M. Lopez, S. W. Choi, H. Tran, and T. T. Johnson, "NNV 2.0: The neural network verification tool," in Computer Aided Verification - 35th International Conference, CAV, ser. Lecture Notes in Computer Science, C. Enea and A. Lal, Eds., vol. 13965. Springer, 2023, pp. 397-412.
L. Pulina and A. Tacchella, "An abstraction-refineeent approach to verification of artificial neural networks," in Computer Aided Verification, 22nd International Conference, CAV, ser. Lecture Notes in Computer Science, vol. 6174. Springer, 2010, pp. 243-257
G. Katz, C. W. Barrett, D. L. Dill, K. Julian, and J. Kochenderfer, "Reluplex: An efficient SMT solver for verifying deep neural networks," in Computer Aided Verification 29th International Conference, CAV, Lecture Notes in Computer Science, vol. 10426. Springer, 2017, pp. 97-117.
M. Hosseini and A. Lomuscio, "Bounded and unbounded verification of rnn masebased agents in non- deterministic environments," in International Conference on Autonomous Agents and Multiagent Systems, AAMAS. IFAAMAS, 2023, pp. 2382-2384.
A. Gendler, T.-W. Weng, L. Daniel, and Romano, "Adversarially robust conformal prediction," in International Conference Learning Representations, 2021.
J. C. Duchi, P. L. Bartlett, and M. Wainwright, "Randomized smoothing for stochastic optimization." SIAM Journal on Optimization, vol. 22, no. 2. pp. 674-701, 2012.
H. Salman, J. Li, I. Razenshteyn, Zhang, H. Zhang, S. Bubeck, and G. Yang, "Provably robust deep learning via adversarially trained smoothed classifiers," Advances in neural information processing systems, vol. 32, 2019.
G. Yan, Y. Romano, and T.-W. Weng, "Provably robust conformal prediction with improved efficiency." in The Twelfth International Conference on Learning Representations, 2023.
S. Ghosh, Y. Shi, T. Belkhouja, Y. Yan, J. Doppa, and B. Jones, "Probabilistically robust conformal prediction," in Uncertainty in Artificial Intelligence. PMLR, 2023, pp. 681-690.
S. H. Zargarbashi, M. S. Akhondzadeh, and A. Bojchevski, "Robust yet efficient conformal prediction sets," in 4/st International Conference on Machine Learning, ICML., ser. Proceedings of Machine Learning Research, vol. 235. PMLR, 21-27 Jul 2024, pp. 17 123-17 147.
J. Lei, J. Robins, and L. Wasserman, "Distribution-F free prediction sets," Journal of the American Statistical Association, vol. 108, no. 501, pp. 278-287, 2013.
Y. Romano, E. Patterson, and E. Candes, "Conformalized quantile regression," " Advances in neural information processing systems, vol. 32, 2019.
K. Xu, Z. Shi, H. Zhang, Y. Wang. K.-W. Chang, M. Huang, B. Kailkhura, X. Lin, and C.-J. Hsich, "Automatic perturbation analysis for scalable certified robustness and beyond," Advances in Neural Information Processing Systems, vol. 33, 2020.
H. Zhang, T.W. Weng, P.-Y. Chen, C.-J. Hsieh, and L. Daniel, "Efficient neural network robustness certification with general activation functions," Advances neural information processing systems, vol. 31, 2018

---

K. Xu, H. Zhang, S. Wang, Y. Wang, S. Jana. X. Lin, and C.-J. Hsich, "Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers," arXiv preprint arXiv:201 I. 13824, 2020.
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu, "Towards deep learning models resistant to adversarial attacks," arXiv preprint 1.Xx::/706606033 2017.
J. Terry, B. Black, N. Grammel, M. Jayakumar, A. Hari, R. Sullivan, L. S. Santos, C. Dieffendahl, C. Horsch, R. Perez- Vicente al., "Pettingzoo: Gym for multi-agent reinforcement learning," Advances in Neural Information Processing Systems, vol. 34, pp. 15 032-15 043, 2021.
I. J. Goodfellow, J. Shlens, and C. Szegedy, "Explaining and harnessing adversarial examples," 2015.
12

---

A
It suffices to show that Additional Proof Details
Here we prove Proposition regarding the prediction sets obtained from VRCP-I and VRCP-C
Proof of Proposition 7 To prove C( C (x()) for VRCP-I suffices to observe that
C.(x) ty e s (x, v) - Q1-a
U
{y MEYY Y: S(x', v) s QI-a(F)}
U
C(x') 2 C(z).
(mu+))
To prove the same for VRCP-C, we observe that since Q1-a (F 2 Q1-a(F), we have that C.(x)) fy Y S(x, v) s Qı-a(F))) (uEY S(x,y) )) S Q Qı-a(F)) C(x).
Next, we prove the validity of the VRCP-I region for the regression case, defined in Eq. 15
Proof. It suffices to show that all E Ce( = [ J + g) satisfy s (x y) max {f- y.y } S g and all & C. (1n+1) do not. For simplicity notation, we abbreviated fang (Ia+1) with f form (In+1) with f and (F) with q.
Assume y E Cc(xn+1). We divide the proof into two cases:
1. s (2n+1,8) = f+ - which implies that E [f+ -
+ 2
fl - S for = ff 1l_ which is clearly satisfied.
2. (In+1,8) = fT. which implies that E 1 +1= T , + g). It suffices to show that y - for y f which is clearly satisfied.
Finally, show that & (x implies s-(x qi if y f- q. have that (#n+1.9) = f q. Similarly, if f +. we have that s (In+1, y) y g.
B Model Details
All experimental results were obtained from running the code provided in our GitHub repository on server with 2x Intel Xeon Platinum 8360Y (36 cores, 72 threads, 2.4GHz), 512GB of RAM and an NVIDIA A40 48GB GPU, All pre-trained models as well as the training scripts are also provided in the GitHub repository. In summary, the models' train and test performances provided in Tables and
Table 4: Train and test accuracies (%) for the classifications models on CIFARIO, CIFARI00, and ImageNet datasets. It should noted that the model's s accuracy has no effect on VRCP's validity and only affects the efficiency of the prediction sets (more accurate models, tighter prediction regions)
Metric
CIFARIO
CIFARI00 Tiny IinyImaeeNet
Train Top-5
98.77
90.49
78.44
Train Top-1
77.80
67.12
52.81
Test Top-5
98.27
82.87
55.72
Test Top-1
76.52
55.73
29.65
B.1 Classification
CIFARIO We use convolution layers with average pooling and dropout, followed by 2 linear layers. ReLU activations across all layers.
CIFARI00 We use 1 convolution layer with average pooling, 2 further convolution layers with average pooling and dropout followed by 2 linear layers. ReLU activations across all layers.
13

---

TinyImageNet We use 4 convolution layers with dropout followed by 2 linear layers with dropout. Leaky ReLU activation function with 0.1
For all models we train using images augmented with random crop with 4 pixels of padding and random horizontal flip. We standardise the TinyImageNet models with μ 0.5 and 0.5 overall 3 RGB channels.
As previously mentioned, we do not make any assumptions during training about the perturbations we expect to see at inference time. As such, unlike the existing SotA methods, we do not train on smoothed or adversarially attacked images.
All models are trained for 200 epochs with a batch size of 128 using the stochastic gradient descent optimiser with momentum set to 0.9. We also employ weight decay of 5 x 10 and cosine annealing learning rate scheduler.
B.2 Regression
For the MPE datasets, we train Deep Q-Net policies for the RL tasks for the sole purposes of generating the appropriate datasets and provide these policies the GitHub repository.
The model used for the quantile regressors is a simple linear architecture consisting of 3 layers, separated with ReLU activation functions and dropout. We trained the model to estimate the a and 1 a-22 quantiles, where a = 0.1, as in the other experiments.
The exact parameters for the RL policies can be found in the config files within the GitHub repository, however have little bearing on the efficiency of our results, being used only for the data-generating process. The quantile regressors each trained for 400 epochs, with a learning rate of 10 dropout of 0.1 and a decay of 10
Table 5: Train and test loss for the regression models in the adversary, spread, and push environments.
Metric Adversary
Spread
Push
Train Test
0.066
0.075
0.075
0.051
0.053
0.068
14

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Claims made in the abstract and introduction are supported by results in Section 5
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals motivation long as is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Covered in Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification,
asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't I acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Covered in Section
Guidelines:
15

---

The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
All relevant details provided in Section Appendix
B and in our GitHub repository,
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-sous source models, it may be that access to the model is limited in some way (e.g.. to registered users). but it should be possible for other researchers to have some path to reproducing or verifying the results.
Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
All code used for experiments is available in our GitHub repository.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
16

---

Please see the NeurIPS code and data submission SodeSoummssiinnnn
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce ct/pbbicc/ the results. See the NeurIPS code and data submission guidelines (https
guides/Codeeuuee issiissinnn wwabbbiisssooooooooooooo onsioniyl) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Hyperparameters for experiments are all provided in Section 5 and model details are provided in Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
All experiments in Section 5 provide a 95% confidence interval taken over 50 splits.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard enror of the mean.
It is OK to report 1 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of eπrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
17

---

8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory. time of execution) needed reproduce the experi- ments?
Answer: [Yes]
Justification:
Compute resources discussed in Section 5 and Appendix B
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide amount compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code Ethics
Question:
Answer: [Yes]
Justification: statements.
We have reviewed the CoE and deemed that our work fully aligned with the
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there a special consideration due laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no significant societal impact of the work provided outside of the fact that we provide robust approach to defend against adversarial attacks.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, improvement in the quality of generative models could be used generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
legitimate to point out that
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
18

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our approach provides defences for adversarial attacks and our methods are exploitable by design.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model implementing safety filters.
Datasets that have been seraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer:
[Yes]
Justification: All credit is given to authors of any assets used as citation in the paper in the README file of the GitHub repository. Relevant licenses are also included in the same repository.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi wersswithhhdde thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information
available online, the authors are encouraged reach out the asset's
creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The model details are included in Appendix B and documentation on how to reproduce results and train the models is given in the README file in the GitHub repository.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
19

---

The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable), You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Not relevant to our work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should paid least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Sub- jects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Not relevant to our work.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
20


Reviews:
[{"review_id": "xJxizNQ31Z", "reviewer": "Reviewer_cbGx", "summary": "This submission proposes VRCP, a framework for verifiably robust conformal prediction under Lp-bounded adversarial attacks. The framework integrates existing bound propagation tools for verification of conformal predictions. Two variants, VRCP-I that triggers bound computation at inference time and VRCP-C that triggers bound computation at calibration time, are proposed. VRCP-I has inference overhead but the set size is smaller. Experiments on CIFAR10, CIFAR100, and a regression task demonstrate the effectiveness.", "questions": "See weaknesses.", "limitations": "Yes, authors discuss the limitations in the last paragraph of the main text.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The submission introduces a feasible method to turn well-studied neural network verifiers into conformal prediction verifiers. The method is sound in theory and is also verified empirically. This is a novel contribution to the field.\n\n2. Compared to existing verifiably robust conformal prediction methods, VRCP has superior empirical performance especially when compared to randomized smoothing, demonstrating its practical value.\n\n3. Presentation is generally great and easy to follow.", "weaknesses": "1. The framework is relatively straightforward. The foundation is some probability relaxations that can be intuitively derived. I would not view this intuitiveness as a weakness. However, it would be great if the authors could discuss some extensions and optimizations, e.g., proof sharing for VRCP-C, alternative but more verification-friendly score function design, etc.\n\n2. Some in-depth discussion could benefit the submission. Concretely, why does VRCP work with different Lp norms? Does the benefit come from the existing verifier's flexibility? Does the bound tightness differ with different Lp norms? Why does the method surpass RSCP?\n\n3. The experimental setup is not very clear: What is the model's normal accuracy? Could you provide more background on the setup of regression experiments especially the physical meaning of the reward bound and nominal performance? The setting is not very common in the literature.\n\nMinor:\nLine 129-130: the lengthy sentence seems to be lacking a period or comma.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 1. The framework is relatively straightforward. The foundation is some probability relaxations that can be intuitively derived. I would not view this intuitiveness as a weakness. However, it would be great if the authors could discuss some extensions and optimizations, e.g., proof sharing for VRCP-C, alternative but more verification-friendly score function design, etc.\n\nAs you correctly mention, our methods rely on the output bounds computed by the NN verifier. Thus, the same features of NN architectures that are friendly for verification will be beneficial to our methods. For example, using transformations and activation functions with low Lipschitz constants would result in tighter bounds with linear bound propagation approaches. \nWe address the question regarding verification-friendly non-conformity score functions in (1) of the global review.\n\n> 2. Some in-depth discussion could benefit the submission. Concretely, why does VRCP work with different Lp norms? Does the benefit come from the existing verifier's flexibility? Does the bound tightness differ with different Lp norms? Why does the method surpass RSCP?\n\nRegarding the first two questions, the existing verification methods indeed grant VRCP's ability to extend to other $\\ell^p$ norms. These methods theoretically provide verification for perturbations bounded by any $\\ell^p$ norm, although in practice, often only the most common $\\ell^p$ norms are implemented ($\\ell^1, \\ell^2$ and $\\ell^{\\infty}$).\n    \nThe bounds' tightness differs with different $\\ell^p$ norms because, for the same epsilon bound, the epsilon-bounded $\\ell^1$ ball is strictly smaller (in volume) than the corresponding $\\ell^2$ ball, which is in turn smaller than the $\\ell^{\\infty}$ ball. Hence, for larger values of $p$, we will see larger input regions and looser output bounds. \n\nWe address the question regarding the intuition behind VRCP’s improved empirical performance to RSCP+ in (2) of the global review.\n\n> 3. The experimental setup is not very clear: What is the model's normal accuracy? Could you provide more background on the setup of regression experiments especially the physical meaning of the reward bound and nominal performance? The setting is not very common in the literature.\n\nFor the classification experiments, the test accuracies of the models are:\n\n|Accuracy/Model|CIFAR10|CIFAR100|TinyImageNet|\n|---|---|---|---|\n|Top-5 Test|98.27%|82.87%|55.72%|\n|Top-1 Test|76.52%|55.73%|29.64%|\n\nIt should be noted that the accuracy of the model has no effect on VRCP's validity and only affects the efficiency of the prediction sets (more accurate models, tighter prediction regions).\n\nFor the regression experiments, the train and test losses of the models are:\n|Loss/Environment|Adversary|Spread|Push|\n|---|---|---|---|\n|Train|0.066|0.075|0.075|\n|Test|0.051|0.053|0.068|\n\nIn terms of the reward bound, we have scaled the total cumulative reward between the range [0, 1] and thus the prediction intervals are also taken over this range. We will clarify this in the updated paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JDGAwHjaID", "reviewer": "Reviewer_iDUp", "summary": "The paper provides a verifiably robust conformal prediction method via neural network verification. It considers two paradigms for considering the perturbation either at the calibration stage or the inference stage. They also consider the validity of method for both classification and regression.", "questions": "Please refer to the weakness part. Overall, I do not have many concerns about the paper's soundness. If the authors can provide more insights into comparisons between randomized certification and deterministic certification in robust conformal prediction, it would be beneficial to the community. Basically, the authors need more support of why NN verification-based conformal prediction is worthy besides it can provide a general $\\ell_p$ norm guarantee.", "limitations": "discussed in Sec 6.1", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well written. I believe people with other background can also understand it well.\n2. The methods work for me. It is clear that NN verification provides a lower/upper bound of the logits, which are transformed to certified bound for conformity scores.", "weaknesses": "1. Novelty: I understand that it is a new angle that combines NN verification and conformal prediction to provide a certifiably robust conformal prediction framework, but I wonder technically, can we do more about the combination. For example, can we have new conformity score adapted to NN verification that can provide tighter bound? Or at least empirically, we can analyze what types of conformity scores are more suitable for randomized certification? What are more suitable for deterministic certification (NN verification).\n\n2. What is the intuition that the method can outperform RSCP+ in Table 1? Since usually randomized smoothing provides better certification than NN verification, then coming to the conformal prediction context, what makes the difference?\n\n3. Missing related work: Kang, Mintong, et al. COLEP: Certifiably Robust Learning-Reasoning Conformal Prediction via Probabilistic Circuits. ICLR 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 1. Novelty: I understand that it is a new angle that combines NN verification and conformal prediction to provide a certifiably robust conformal prediction framework, but I wonder technically, can we do more about the combination. For example, can we have new conformity score adapted to NN verification that can provide tighter bound? Or at least empirically, we can analyze what types of conformity scores are more suitable for randomized certification? What are more suitable for deterministic certification (NN verification).\n\nWe address the question regarding verification-friendly non-conformity score functions in **Part 1** of the **Global Rebuttal**.\n\n> 2. What is the intuition that the method can outperform RSCP+ in Table 1? Since usually randomized smoothing provides better certification than NN verification, then coming to the conformal prediction context, what makes the difference?\n\nWe address the question regarding the intuition behind VRCP’s improved empirical performance to RSCP+ in **Part 2** of the **Global Rebuttal**.\n\n> 3. Missing related work: Kang, Mintong, et al. COLEP: Certifiably Robust Learning-Reasoning Conformal Prediction via Probabilistic Circuits. ICLR 2024.\n\nWe will add this to the related work of the updated manuscript. We understand that this paper introduces a learning-reasoning framework (COLEP) that integrates the original RSCP (Gendler et al. 2021) to provide adversarially robust conformal prediction sets by using auxiliary models and probabilistic circuits. This work is complementary to ours because VRCP can be directly applied to COLEP in place of RSCP.\n\n> Please refer to the weakness part. Overall, I do not have many concerns about the paper's soundness. If the authors can provide more insights into comparisons between randomized certification and deterministic certification in robust conformal prediction, it would be beneficial to the community. Basically, the authors need more support of why NN verification-based conformal prediction is worthy besides it can provide a general $\\ell_p$ norm guarantee.\n\nWe addressed this question in detail above. We would also like to note that VRCP provides more benefits as listed below:\n\n- Other existing robust CP approaches introduce additional dependencies, such as the need for a hold-out set or a large number of samples (used for randomized smoothing) \n- VRCP supports regression tasks without requiring any modifications, unlike the existing approaches\n- VRCP supports arbitrary $\\ell^p$ norms", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7k7gkhuTaT", "reviewer": "Reviewer_gWvg", "summary": "The authors propose a novel method to recover coverage guarantees for conformal predictions in the presence of adversarial attacks. Unlike previously proposed approaches, the authors directly leverage verifiable methods for NN to compute prediction scores. Through empirical tests, the authors prove the benefit of the proposed approach against attacks bounded by different norms.", "questions": "See Weaknesses", "limitations": "Limitations are discussed", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Empirical results support the benefit of the proposed approach against vanilla CP, RSCP+ \n\n2. The proposed approach seems to be robust across different values of the adversarial perturbation\n\n3. The approach is well-described and the coverage guarantees are supported by theoretical arguments", "weaknesses": "1. In the paper, the authors focus on PDG. However, the literature offers more advanced and sophisticated attacks. It would be beneficial to assess the robustness of the proposed approach against other type of attacks. \n\n2. Since it is not specified in the paper, I assume the ML model under attack has not been trained using adversarial training. The reader might wonder whether the benefit of the proposed approach remains valid in the presence of an adversarially trained model. Concerning the latter case, will vanilla CP still violate the coverage guarantees?\n\n3. Figure 2 is hard to read. Which curve represents the proposed approach, and which one represents the benchmarks?\nConcerning Figure 2a: Why does the coverage go to one as the magnitude of the adversarial perturbation goes to one? Perhaps it is because all the methods converge to a trivial prediction set. However, this should be clearly explained in the text.\nConcerning Figure 2b: Why does the coverage decrease as a function of the number of samples?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> 1. In the paper, the authors focus on PDG. However, the literature offers more advanced and sophisticated attacks. It would be beneficial to assess the robustness of the proposed approach against other type of attacks.\n\nWith regard to the chosen attack methods, we evaluate PGD in the case of classification tasks and FGSM for the regression task. We chose PGD as it remains a popular choice within existing literature on robust CP approaches, and so as to be consistent and draw fair comparisons against the RSCP/+ methods. In theory, however, our approach is agnostic to the adversarial attack algorithm used to perturb the inputs, as it ensures robustness to any $\\ell^p$ bounded adversarial attacks.\n\n> 2. Since it is not specified in the paper, I assume the ML model under attack has not been trained using adversarial training. The reader might wonder whether the benefit of the proposed approach remains valid in the presence of an adversarially trained model. Concerning the latter case, will vanilla CP still violate the coverage guarantees?\n\nWe appreciate that we should have been clearer about the adversarial training aspect, and your assumption is correct in that we do not use adversarial training. Whilst an adversarially trained model is more reliable on adversarial inputs, using one in combination with vanilla CP doesn't guarantee robust coverage. For this to hold, we would require the adversarially trained model to guarantee prediction invariance for every input and the corresponding $\\epsilon$-bounded region around it, which is not the case. Our VRCP method would provide valid prediction regions instead. We will clarify this point further in the paper.\n\n> 3. Figure 2 is hard to read. Which curve represents the proposed approach, and which one represents the benchmarks? Concerning Figure 2a: Why does the coverage go to one as the magnitude of the adversarial perturbation goes to one? Perhaps it is because all the methods converge to a trivial prediction set. However, this should be clearly explained in the text. Concerning Figure 2b: Why does the coverage decrease as a function of the number of samples?\n\nPerhaps confusingly, the legend for all the plots can be seen in the 3rd figure due to an oversight in figure placement. We will update the manuscript to include the legend more clearly below the figures.\n\nAs the reviewer pointed out, in Figure 2a, coverage and prediction set size increase for larger epsilon due to the robust methods including more classes within their prediction sets to account for the stronger potential perturbation. This trend converges to trivial prediction sets and a coverage of 1. Note that in our experiments with $\\epsilon=0.05$, VRCP-I has an empirical coverage of $1$ but does not produce trivial prediction sets (its average set size is $8.52$ against a maximum of $10$).\n\nIn Figure 2b, we observe that increasing the number of Monte-Carlo samples used in RSCP+ methods improves their prediction set efficiency. The higher the number of samples used for randomised smoothing, the lower the effect is of the Hoeffding/Bernstein bound required to correct for sampling error.\n\nWe will add both of these discussions to the main text to improve clarity.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their useful comments. 

Here we respond to the common feedback amongst all the reviews.

---

## Part 1. Verification-Friendly Non-Conformity Score Functions

We agree that investigating verification-friendly score functions is a great idea for future work. We use $1-f_y(x)$ as the score function, as we find this to be, for classification tasks, the most popular choice across the literature, including existing randomised smoothing approaches. This function happens to be verification-friendly because it is completely linear and does not introduce further over-approximations. Score functions that introduce over-approximation (e.g., where there are multiple expressions to bound) would make our approach more conservative and possibly favour randomised smoothing approaches.

---

## Part 2. The intuition behind VRCP's Improved Empirical Performance to RSCP+

In the RSCP+ approach, the robustness guarantee is dependent on a number of factors that affect performance, listed below:

- The size of the Lipschitz constant $\sigma/\epsilon$.
- The size of the Hoeffding/Bernstein bounds used to correct for sampling error when estimating the mean of their smoothed scores.
- The representativity of the holdout set w.r.t. the rest of the calibration distribution (when using PTT).

Both VRCP-C and VRCP-I methods perform agnostically of the aforementioned factors and thus exhibit improved efficiency where RSCP/+ falls short.

Meta-review: This paper considers the problem of providing valid prediction sets using conformal prediction in the presence of adversarial perturbations. This is an active research area and the paper makes a good contribution by approaching this problem through the lens of neural network verification tools and is applicable to both classification and regression tasks (demonstrated by experiments).

The reviewers' appreciated the new ideas in the paper but also raised some good questions. Authors' responses were satisfactory to address those questions.

Therefore, I recommend accepting the paper and strongly encourage the authors' to incorporate all the discussion in the camera copy to further improve the paper.
Decision: Accept (poster)