# Verifiably Robust Conformal Prediction

Linus Jeary
Department of Informatics
King’s College London, UK
<EMAIL_ADDRESS>
&Tom Kuipers∗
Department of Informatics
King’s College London, UK
<EMAIL_ADDRESS>
Mehran Hosseini
Department of Informatics
King’s College London, UK
<EMAIL_ADDRESS>
&Nicola Paoletti
Department of Informatics
King’s College London, UK
<EMAIL_ADDRESS>
Authors contributed equally.

###### 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.

##  1 Introduction

Conformal Prediction (CP) (Vovk et al., 2005; Angelopoulos and Bates, 2021) is
a popular uncertainty quantification method. In essence, it is a model-
agnostic, distribution-free framework that allows one to construct prediction
sets that are guaranteed to include the true (unknown) output with probability
greater than $1-\alpha$, where $\alpha\in(0,1)$ is a user-specified
miscoverage/error rate. In other words, for a test point
$(\bm{x}_{n+1},y_{n+1})$, CP seeks to construct a prediction set
${C}(\bm{x}_{n+1})$ such that the following coverage (a.k.a. validity)
guarantee holds:

$\mathbb{P}_{\bm{x}_{n+1},y_{n+1}}[y_{n+1}\in{C}(\bm{x}_{n+1})]\geq 1-\alpha.$
(1)

Importantly, the above guarantee holds when the calibration data, used to
construct ${C}(\bm{x}_{n+1})$, and the test point are exchangeable (a special
case is when calibration and test data are i.i.d.).

When exchangeability is violated, e.g., in the presence of test-time
distribution shifts, CP’s coverage guarantee (1) 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, we
focus on perturbations in the form of additive $\ell^{p}$-bounded 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 or even trivial
sets – i.e. those containing all possible outputs – as such sets do not
provide any useful inference.

Figure 1: Distribution of prediction set sizes for vanilla conformal
prediction (vanilla CP) which violates Eq. 2, as well as for our proposed
robust algorithms (VRCP–I and VRCP–C) along with the SotA (RSCP+ and RSCP+
(PTT), see Section 3) on the CIFAR10 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 $\epsilon=0.02$, error rate $\alpha=0.1$, number of splits
$n_{\text{splits}}=50$ and smoothing parameter (used in RSCP+ and RSCP+ (PTT))
$\sigma=2\epsilon$.

#### Contributions

We propose a CP framework that provides statistically valid prediction sets
despite the presence of $\ell^{p}$-bounded adversarial perturbations at
inference time. Formally, for any adversarially perturbed test point
$\tilde{\bm{x}}_{n+1}=\bm{x}_{n+1}+\delta$, our method produces adversarially
robust sets $C_{\epsilon}$ that enjoy the following guarantee:

$\mathbb{P}[y_{n+1}\in C_{\epsilon}(\tilde{\bm{x}}_{n+1})]\geq
1-\alpha\quad\forall\delta\ \text{ s.t. }\
\lVert\delta\rVert_{p}\leq\epsilon.$ (2)

While CP uses an underlying predictor $f$, often a neural network (NN), to
construct prediction regions, the novelty of our approach is to leverage NN
verification algorithms to compute upper and lower output bounds of
$f(\bm{x}^{\prime})$ for any $\bm{x}^{\prime}\in
B_{\epsilon}(\bm{x})=\\{\bm{x}^{\prime}:\lVert\bm{x}^{\prime}-\bm{x}\rVert_{p}\leq\epsilon\\}$.
We use these bounds to 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 to 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
$\ell^{2}$-norm 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 $\ell^{2}$-norm bounded guarantees. In Section 4, we introduce two
versions of VRCP that apply verification at calibration and inference time,
respectively. Further, in Section 5, 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. 1 shows an extract of our results on CIFAR10, demonstrating that VRCP
yields more informative (tighter) prediction regions, a trend that we observe
experimentally across all our benchmarks.

##  2 Preliminaries

We denote with $\mathbb{R}_{+}$ the set of positive real numbers. Vectors
$\bm{x}\in\mathbb{R}^{n}$ are shown in bold italic and scalars
$x\in\mathbb{R}^{n}$ in italic typeface. We denote the norm used to make
$\mathbb{R}^{n}$ a normed vector space by $\lVert\cdot\rVert$. This could for
instance be $\ell^{1},\ell^{2}$, or $\ell^{\infty}$ norm. Whenever a specific
norm is intended, we indicate it using an index, e.g., $\lVert\cdot\rVert_{2}$
indicates the $\ell^{2}$-norm. We denote the $\epsilon$-ball around a point
$\bm{x}\in\mathbb{R}^{n}$ with respect to the used norm by
$B_{\epsilon}(\bm{x})$.

###  2.1 Conformal Prediction

We provide a brief overview of the inductive (or split) vanilla CP approach.
Suppose we have a dataset $\mathcal{D}$ containing pairs $(x,y)$ sampled
i.i.d. from an (unknown) data-generating distribution over a feature space
$X\subseteq\mathbb{R}^{m}$ and label space $Y$ such that
$\mathcal{D}=\\{(\bm{x}_{1},y_{1}),\dots,(\bm{x}_{m},y_{m})\\}$.

We partition the dataset into disjoint training and calibration sets
$\mathcal{D}_{\text{train}}$ and $\mathcal{D}_{\text{cal}}$, letting
$n=|\mathcal{D}_{\text{cal}}|$. We fit a predictor $f$ on
$\mathcal{D}_{\text{train}}$ and define a score function $S:(X\times
Y)\to\mathbb{R}$ as some notion of prediction error, such as
$S(\bm{x},y)=\|f(\bm{x})-y\|$ when $f$ is a regressor, or
$S(\bm{x},y)=1-f(\bm{x})_{y}$ when $f$ is a classifier with $f(\cdot)_{y}$
being $y$’s predicted likelihood.

After applying the score function to all calibration points, we construct the
score distribution as
$F=\nicefrac{{\delta_{\infty}}}{{(n+1)}}+\sum_{i=1}^{n}\nicefrac{{\delta_{s_{i}}}}{{n+1}}$,
where $\delta_{s}$ is the Dirac distribution with parameter $s$,
$s_{i}=S(\bm{x}_{i},y_{i})$ and $\delta_{\infty}$ represents the unknown score
(potentially infinite) of the test point.

Given a miscoverage/error rate $\alpha$ and a test point
$(\bm{x}_{n+1},y_{n+1})$, we define the prediction set $C(\bm{x}_{n+1})$ by
including all labels that appear sufficiently likely w.r.t. the score
distribution: $C(\bm{x}_{n+1})=\\{y\in Y:S(\bm{x}_{n+1},y)\leq
Q_{1-\alpha}(F)\\}$, where $Q_{1-\alpha}(F)$ is the $1-\alpha$ quantile of
$F$. This set satisfies the marginal coverage guarantee in Eq. 1 if the test
point and the calibration points are exchangeable.

###  2.2 Adversarial Attacks

Neural networks have been shown to be vulnerable to _adversarial attacks_ ,
i.e., 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 an adversarial objective function (e.g., the loss of the true
label) subject to $\lVert\bm{x}-\bm{x}^{\prime}\rVert\leq\epsilon$.
Alternatively, it can be defined as finding
$\bm{x}^{\prime}\in\mathbb{R}^{m}$, such that
$\lVert\bm{x}-\bm{x}^{\prime}\rVert\leq\epsilon$ and $\lVert
f(\bm{x}^{\prime})-y\rVert\geq\delta$ for a given neural network
$f:\mathbb{R}^{m}\mapsto\mathbb{R}^{n}$.

###  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 (see related work for more details). Given a neural
network $f$, a verifier is _complete_ if it allows computing exact bounds
$\bm{f}^{\perp}$ and $\bm{f}^{\top}$ for the image
$f(B_{\epsilon}(\bm{x}))=\\{f(\bm{x}^{\prime}):\bm{x}^{\prime}\in
B_{\epsilon}(\bm{x})\\}$, i.e., such that

${f}^{\perp}=\min_{\bm{x}^{\prime}\in
B_{\epsilon}(\bm{x})}\\{f(\bm{x}^{\prime})\\},\quad{f}^{\top}=\max_{\bm{x}^{\prime}\in
B_{\epsilon}(\bm{x})}\\{f(\bm{x}^{\prime})\\},$ (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:

${f}^{\perp}\leq\min_{\bm{x}^{\prime}\in
B_{\epsilon}(\bm{x})}\\{f(\bm{x}^{\prime})\\},\quad{f}^{\top}\geq\max_{\bm{x}^{\prime}\in
B_{\epsilon}(\bm{x})}\\{f(\bm{x}^{\prime})\\}.$ (4)

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
LABEL:eq:Approximate_Bounds is to propagate the bounds on the input
$B_{\epsilon}(\bm{x})$ through the network to 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.

##  3 Related Work

#### Adversarially Robust Conformal Prediction

Gendler et al. (2021) introduced an algorithm called Randomly Smoothed
Conformal Prediction (RSCP) that integrates randomised smoothing (Duchi et
al., 2012; Cohen et al., 2019; Salman et al., 2019) with CP to provide robust
coverage under adversarial attacks. RSCP replaces the CP score function
$S(\bm{x},y)$ with a smoothed score $\widetilde{S}(\bm{x},y)$ obtained by
averaging the values of $S(\bm{x}+\bm{v},y)$ over $n_{\text{MC}}$ realisations
of a Gaussian noise vector $\bm{v}\sim\mathcal{N}(0,\sigma^{2}I)$, for a given
smoothing level $\sigma$. To correct for potential $\ell^{2}$ norm-bounded
$\epsilon$ perturbations at inference time, the critical value computed over
the smoothed scores is inflated by $\epsilon/\sigma$. This method produces
empirically sound results, but the provided formal guarantees were found to be
invalid in later work (Yan et al., 2023), as discussed below.

#### Provably Robust Conformal Prediction

Yan et al. (2023) 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 $\beta$ such that they now find the
$Q_{1-\alpha+2\beta}$ of smooth calibrated scores and inflate by Hoeffding’s
bound $\sqrt{\nicefrac{{-\ln(\beta)}}{{2n_{\text{MC}}}}}$ before correcting by
$\epsilon/\sigma$. Furthermore, the smoothed scores of 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 causes
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), a
training-time regularisation technique that penalises NN parameters that
contribute to 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 a post-training transformation (PTT), which aims to
decrease the values of the smoothed calibration scores that lie between
$Q_{1-\alpha}$ (the critical value of the base scores) and
$\widetilde{Q}_{1-\alpha}$ (that of the smoothed scores). To this purpose,
they transform the CDF of the smoothed scores $\widetilde{S}$ by composing a
ranking transformation and a sigmoid transformation with hyperparameters $b$
and $T$. These transformations are learned using a holdout set
$\mathcal{D}_{\text{hold}}$ sampled i.i.d from $\mathcal{D}_{\text{cal}}$ PTT
is not theoretically guaranteed to improve the average set sizes computed by
RSCP+ and, in many cases, introduces an additional dependence on the data,
namely on how representative the sampled holdout set is of the calibration
set. We empirically demonstrate the effect of PTT’s sample dependence in
Section 5.1.

#### Probabilistically Robust Conformal Prediction

Ghosh et al. (2023) also focus on the adversarial setting but maintain a
relaxed form of robust coverage, where input perturbations $\delta$ are drawn
from a 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 $\epsilon$-bounded perturbation.

All the works111At the time of submission, we are aware of a potentially
related contemporaneous work titled “Robust Yet Efficient Conformal Prediction
Sets”. However, neither the manuscript nor the code are available. discussed
here rely on randomised smoothing Duchi et al. (2012) and as such are limited
to $\ell^{2}$-norm. In contrast, our VRCP approach relies on NN verifiers, can
be used with any $\ell^{p}$-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 to compute a 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 at inference time, without requiring NN
verification.

###  4.1 Verifiably Robust Conformal Prediction via Robust Inference (VRCP–I)

Given a calibration set $\mathcal{D}_{\text{cal}}$, a test input
$\bm{x}_{n+1}$, and score function $S(\cdot,\cdot)$, we compute the prediction
set for $\bm{x}_{n+1}$ as follows.

  1. 1.

For each $y\in Y$ we compute,

${s}^{\perp}(\bm{x}_{n+1},y)\leq\inf_{\bm{x}^{\prime}\in
B_{\epsilon}(\bm{x}_{n+1})}S(\bm{x}^{\prime},y).$ (5)

  2. 2.

The robust prediction set is then defined as

$C_{\epsilon}(\bm{x}_{n+1})=\\{y:{s}^{\perp}(\bm{x}_{n+1},y)\leq
Q_{1-\alpha}(F)\\}.$ (6)

Below, we show that we are able to maintain the marginal coverage guarantee
from Eq. 2 for any $\ell^{p}$ norm-bounded adversarial attack.

######  Theorem 1.

Let $\tilde{\bm{x}}_{n+1}=\bm{x}_{n+1}+\delta$ for a clean test sample
$\bm{x}_{n+1}$ and $\lVert\delta\rVert_{p}\leq\epsilon$. The prediction set
$C_{\epsilon}(\tilde{\bm{x}}_{n+1})$ defined in Eq. 6 satisfies
$\mathbb{P}\left[y_{n+1}\in C_{\epsilon}(\tilde{\bm{x}}_{n+1})\right]\geq
1-\alpha.$

###### Proof.

We obtain that

$\displaystyle\mathbb{P}\left[y_{n+1}\in\hat{C}(\tilde{\bm{x}}_{n+1})\right]$
$\displaystyle=\mathbb{P}\left[{s}^{\perp}(\tilde{\bm{x}}_{n+1},y_{n+1})\leq
Q_{1-\alpha}(F)\right]$
$\displaystyle\geq\mathbb{P}\left[\inf_{\bm{x}^{\prime}\in
B_{\epsilon}(\tilde{\bm{x}}_{n+1})}S(\bm{x}^{\prime},y_{n+1})\leq
Q_{1-\alpha}(F)\right]$ by Eq. 5
$\displaystyle\geq\mathbb{P}\left[S(\bm{x}_{n+1},y_{n+1})\leq
Q_{1-\alpha}(F)\right]\ \geq\ 1-\alpha.\qed$

###  4.2 Verifiably Robust Conformal Prediction via Robust Calibration

Given a calibration set $\mathcal{D}_{\text{cal}}$, a test input
$\bm{x}_{n+1}$, and score function $S(\cdot,\cdot)$, we compute the robustly
calibrated prediction set for $\bm{x}_{n+1}$ as follows.

  1. 1.

We compute the upper-bound calibration distribution as:

${F}^{\top}=\frac{\delta_{\infty}}{(n+1)}+\sum_{i=1}^{n}\frac{\delta_{{s}^{\top}_{i}}}{n+1}\text{,
where }{s}^{\top}_{i}\geq\sup_{\bm{x}^{\prime}\in
B_{\epsilon}(\bm{x}_{i})}S(\bm{x}^{\prime},y_{i}).$ (7)

  2. 2.

The robust post-calibration prediction set is then defined as

$C_{\epsilon}(\bm{x}_{n+1})=\\{y:S(\bm{x}_{n+1},y)\leq
Q_{1-\alpha}({F}^{\top})\\}.$ (8)

######  Theorem 2.

Let $\tilde{\bm{x}}_{n+1}=\bm{x}_{n+1}+\delta$ for a clean test sample
$\bm{x}_{n+1}$ and $\lVert\delta\rVert_{p}\leq\epsilon$. The prediction set
$C_{\epsilon}(\tilde{\bm{x}}_{n+1})$ defined in Eq. 8 satisfies
$\mathbb{P}\left[y_{n+1}\in C_{\epsilon}(\tilde{\bm{x}}_{n+1})\right]\geq
1-\alpha.$

###### Proof.

We have that

$\displaystyle\mathbb{P}\left[y_{n+1}\in
C_{\epsilon}(\tilde{\bm{x}}_{n+1})\right]$
$\displaystyle=\mathbb{P}\left[S(\tilde{\bm{x}}_{n+1},y_{n+1})\leq
Q_{1-\alpha}\left({F}^{\top}\right)\right]$
$\displaystyle\geq\mathbb{P}\left[S(\tilde{\bm{x}}_{n+1},y_{n+1})\leq
Q_{1-\alpha}\left(\left\\{\sup_{\bm{x}^{\prime}\in
B_{\epsilon}(\bm{x}_{i})}S(\bm{x}^{\prime},y_{i})\right\\}_{i=1}^{n}\cup\\{\infty\\}\right)\right]$
$\displaystyle\geq\mathbb{P}\left[\sup_{\bm{x}^{\prime}\in
B_{\epsilon}(\bm{x}_{n+1})}\\!\\!\\!S(\bm{x}^{\prime},y_{n+1})\leq
Q_{1-\alpha}\left(\left\\{\sup_{\bm{x}^{\prime}\in
B_{\epsilon}(\bm{x}_{i})}S(\bm{x}^{\prime},y_{i})\right\\}_{i=1}^{n}\\!\\!\\!\cup\\{\infty\\}\right)\right]$
$\displaystyle\geq 1-\alpha$

Let $P^{\top}$ denote the distribution of $({\bm{x}}^{\top},y)$ where
${\bm{x}}^{\top}=\text{argsup}_{\bm{x}^{\prime}\in
B_{\epsilon}(\bm{x})}S(\bm{x}^{\prime},y)$ and $(\bm{x},y)\sim P$. The final
inequality above holds since it is equivalent to constructing a CP prediction
set using $n$ i.i.d realisations of $P^{\top}$ and evaluating it on
${\bm{x}}_{n+1}$ $\sim P^{\top}$. The resulting set will include the true test
output $y_{n+1}$ with probability at least $1-\alpha$. ∎

###  4.3 Computation of score bounds

#### Classification

In the classification setting, we use the score function proposed in (Lei et
al., 2013; Gendler et al., 2021):

$S(\bm{x},y)=1-f(\bm{x})_{y},$ (9)

where $f(\bm{x})_{y}\in(0,1)$ is the model-predicted likelihood for label $y$.
In this setting, to compute ${s}^{\perp}$ and ${s}^{\top}$ (required by VRCP–I
and VRCP–C, respectively), it suffices to use NN verification algorithms to
derive the output bounds for $f(\bm{x})$. Specifically, in VRCP–I, for a test
input $\bm{x}_{n+1}$ and for each $y\in Y$ we derive
${s}^{\perp}(\bm{x}_{n+1},y)$ as

${s}^{\perp}(\bm{x}_{n+1},y)=1-{f(\bm{x}_{n+1})}^{\top}_{y},$ (10)

where ${f(\bm{x}_{n+1})}^{\top}_{y}$ denotes the upper bound computed by the
neural network verifier for the model-predicted likelihood of label $y\in Y$
and input $\bm{x}_{n+1}$.

In VRCP–C, for each calibration point $(\bm{x}_{i},y_{i})$ we compute
${s}^{\top}(\bm{x}_{i},y_{i})$ as

${s}^{\top}(\bm{x}_{i},y_{i})=1-{f(\bm{x}_{i})}^{\perp}_{y_{i}},$ (11)

where ${f(\bm{x}_{i})}^{\perp}_{y_{i}}$ denotes the lower bound of the model
output for label $y_{i}$ given input $\bm{x}_{i}$.

#### Regression

In the regression tasks, we follow the conformalized quantile regression (CQR)
methodology proposed by (Romano et al., 2019). We train quantile regressors
$f_{\alpha_{\text{low}}}$ and $f_{\alpha_{\text{high}}}$ to estimate the
$\alpha_{\text{low}}=\alpha/2$ and $\alpha_{\text{high}}=1-\alpha/2$ quantiles
of $y\mid\bm{x}$. In CQR, we use the following score function:

$S(\bm{x},y)=\max{\\{f_{\alpha_{\text{low}}}(\bm{x})-y,y-f_{\alpha_{\text{high}}}(\bm{x})\\}}.$
(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 $C(\bm{x}_{n+1})$ is constructed
implicitly, by adjusting the quantile predictions by the critical value of the
calibration distribution $Q_{1-\alpha}(F)$, as follows:

$C(\bm{x}_{n+1})=\left[f_{\alpha_{\text{low}}}(\bm{x}_{n+1})-Q_{1-\alpha}(F),f_{\alpha_{\text{high}}}(\bm{x}_{n+1})+Q_{1-\alpha}(F)\right]$
(13)

In both VRCP–C and VRCP–I, the score function leverages an NN verifier to
derive the bounds over the upper and lower quantiles of the model. In VRCP–C,
we compute the worst-case calibration scores as:

${s}^{\top}(\bm{x}_{i},y_{i})=\max{\\{{f}^{\top}_{\alpha_{\text{low}}}(\bm{x}_{i})-y_{i},y_{i}-{f}^{\perp}_{\alpha_{\text{high}}}(\bm{x}_{i})\\}}.$
(14)

In VRCP–I for classification, for each output we check inclusion in
$C_{\epsilon}$ by using the best-case score $s^{\bot}$. As explained above,
explicit enumeration is infeasible for regression, and so we construct our
robust region by replacing predicted quantiles in Eq. 13 with their
conservative approximations, as follows:

$C_{\epsilon}(\bm{x}_{n+1})=\left[{f}^{\perp}_{\alpha_{\text{low}}}(\bm{x}_{n+1})-Q_{1-\alpha}(F),{f}^{\top}_{\alpha_{\text{high}}}(\bm{x}_{n+1})+Q_{1-\alpha}(F)\right]$
(15)

The above-defined region is equivalent to enumerating all possible outputs
$y$, and for each, considering the best-case score
${s}^{\perp}(\bm{x}_{n+1},y)=\max{\\{{f}^{\perp}_{\alpha_{\text{low}}}(\bm{x}_{n+1})-y,y-{f}^{\top}_{\alpha_{\text{high}}}(\bm{x}_{n+1})\\}}$.
A proof is available in Appendix A.

A nice property of both VRCP–I and VRCP–C is that they guarantee that they can
only increase the size of the prediction set for any input ${\bm{x}}$ 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 a similar
distribution of set sizes. This is formalised in the LABEL:prop:Containment,
which is proved in Appendix A.

######  Proposition 1.

Let $C(\bm{x})$ and $C_{\epsilon}(\bm{x})$ be the prediction sets obtained
using vanilla CP and VRCP (using VRCP–I or VRCP–C), respectively. For any
input $\bm{x}$, we have that $C(\bm{x})\subseteq C_{\epsilon}(\bm{x})$.

##  5 Evaluation

We evaluate VRCP–I and VRCP–C on classifiation (image) and regression (RL)
benchmarks, and compare them against the SotA approaches on each benchmark.

###  5.1 Classification Experiments

We evaluate each method using a nominal coverage of $1-\alpha=0.9$ and report
the 95% confidence intervals for coverage and average set sizes computed over
50 splits ($n_{\text{splits}}=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(\bm{x})$ required in LABEL:eq:lbClassScore and Eq. 11 for
VRCP–I and VRCP–C respectively. In particular, we use two SotA GPU-
parallelised incomplete NN verification algorithms, CROWN Zhang et al. (2018b)
and $\alpha$-CROWN Xu et al. (2020b). In brief, CROWN performs linear bound
propagation and $\alpha$-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 TinyImageNet model and
$\alpha$-CROWN for the smaller CIFAR10 and CIFAR100 models.

Our CIFAR10 model with $\alpha$-CROWN takes $\approx 0.5$s per image to
compute bounds with $\epsilon=0.03$, whereas our larger CIFAR100 model takes
$\approx 7.2$s with $\epsilon=0.02$. Comparatively, computing the smoothed
scores takes $\approx 0.09$s per image to compute on both models under the
same respective $\epsilon$ values. The largest model for the TinyImageNet
dataset uses CROWN to compute bounds at a rate of $\approx 0.2$s per image
whereas the smoothed scores take $\approx 0.24$s. All measurements are made
with respect to the hardware details listed in Appendix B.

#### Attacks

We use the PGD attack algorithm (Madry et al., 2017), which is a popular
white-box attack algorithm to generate adversarial inputs with respect to
either the $\ell^{2}$ or $\ell^{\infty}$ norm.

#### Models

For all datasets, we train a CNN model on training set images with random crop
and horizontal flip augmentations. We do not perform adversarial training as
we assume that the severity $\epsilon$ of the attack is unknown at training
time. Full model details are outlined in the appendix.

#### Hyperparameters

RSCP+ based approaches use $\sigma=2\epsilon$, $\beta=0.001$ and those with
PTT use $|\mathcal{D}_{\text{hold}}|=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
CIFAR10 and CIFAR100 $|\mathcal{D}_{\text{train}}|=50{,}000$ and for
TinyImageNet $|\mathcal{D}_{\text{train}}|=100{,}000$. For all datasets
$|\mathcal{D}_{\text{cal}}|=4{,}500$ and
$|\mathcal{D}_{\text{test}}|=5{,}000$. For methods that don’t rely on PTT, we
use $\mathcal{D}_{\text{cal}}\cup\mathcal{D}_{\text{hold}}$ as the calibration
dataset.

#### Results

In Table 1, we 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 to generate $\ell^{2}$ norm-bounded
attacks with $\epsilon=0.02$ for CIFAR100 and TinyImageNet, and
$\epsilon=0.03$ for CIFAR10.

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 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, as demonstrated by a 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 estimates.
VRCP–I provides slightly more efficient regions than VRCP–C. Still, it implies
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 $\epsilon$ for different test
points at inference time, VRCP–I would be a sound choice, while VRCP–C would
require re-calibration.

Table 1: Marginal Coverage and Average Set Sizes for different methods on
CIFAR10, CIFAR100 and TinyImageNet. All results record a 95% confidence
interval with $n_{\text{splits}}=50$, $\alpha=0.1$, $\sigma=2\epsilon$,
$n_{\text{MC}}=1024$, $\epsilon=0.03$ for CIFAR10 and $\epsilon=0.02$
otherwise.

| CIFAR10 | CIFAR100 | TinyImageNet
---|---|---|---
Method | Coverage | Size | Coverage | Size | Coverage | Size
Vanilla | 0.878±0.002 | 1.721±0.008 | 0.890±0.002 | 6.702±0.058 | 0.886±0.002 | 38.200±0.252
RSCP+ | 1.000±0.000 | 10.000±0.000 | 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.644±20.063
VRCP–I | 0.986±0.000 | 4.451±0.011 | 0.971±0.001 | 22.530±0.107 | 0.958±0.001 | 72.486±0.311
VRCP–C | 0.995±0.000 | 5.021±0.010 | 0.983±0.000 | 23.676±0.131 | 0.965±0.001 | 77.761±0.352

#### Effect of increasing adversarial noise

Fig. 2(a) shows the impact of increasing $\epsilon$ across all evaluated
robust methods. Our methods consistently produce smaller average set sizes
with minor sample dependence, and simultaneously 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.

(a) Varying the value of $\epsilon$ for $n_{\text{splits}}=50$,
$\sigma=2\epsilon$, $\alpha=0.1$, and $n_{\text{MC}}$ = 1024.

(b) Varying $n_{\text{MC}}$ for $n_{\text{splits}}=50$, $\epsilon=0.03$,
$\alpha=0.1$, and $\sigma=2\epsilon$.

Figure 2: Marginal Coverage and Average Set Sizes on CIFAR100 with 95%
confidence intervals.

#### Effect of increasing Monte-Carlo samples

Fig. 2(b) displays the influence of the $n_{\text{MC}}$ hyperparameter on the
RSCP+ based methods with respect to our CIFAR10 model. Whilst increasing
samples improves the performances of randomised smoothing approaches, we incur
a large computational overhead when computing the smoothed scores. In our
experiments in Table 1 we fix $n_{\text{MC}}=1024$ which is four times larger
than the value for $n_{\text{MC}}$ used in previous work Gendler et al.
(2021)Yan et al. (2023) as a trade-off between prediction quality and
computation.

Table 2: Marginal Coverage and Average Set Sizes for $\epsilon$ perturbations with respect to the $\ell^{\infty}$ norm on the CIFAR10 dataset. All results record a 95% confidence interval with $n_{\text{splits}}=50$, $\alpha=0.1$ and $\epsilon=0.001$. | CIFAR10
---|---
Method | Coverage | Size
Vanilla | 0.872±0.002 | 1.737±0.007
VRCP–I | 0.947±0.001 | 2.262±0.008
VRCP–C | 0.931±0.001 | 2.342±0.008

#### Beyond $\ell^{2}$ norm bounded attacks

Table 2 demonstrates that both of our methods generalise to other $\ell^{p}$
bounded perturbations other than for when $p=2$ which RSCP+ is limited to. In
particular, we examine the $\ell^{\infty}$, where even a small $\epsilon$ can
cause misclassification. We experiment using CIFAR10 and use $\epsilon=0.001$.
PGD is used to generate $\ell^{\infty}$ bounded adversarial examples.

#### Set size distribution

From Fig. 1 we can visually examine the sample dependency issue that the PTT
introduces. 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 is clearly an
undesirable property and adds significant variance to the predictions.

Both of our methods increase the spread of the average set sizes to account
for the presence of adversarial examples whilst still maintaining a consistent
distribution.

###  5.2 Regression Experiments

We evaluate our VRCP framework on regression tasks from the PettingZoo Multi-
Particle Environment (MPE) library Terry et al. (2021) for deep reinforcement
learning. In 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 is fixed, and agents
traverse the space according to second-order motion laws. We evaluate our
method on three tasks:

  * •

Adversary The good agents must try to reach a specific goal landmark whilst
avoiding the adversaries. We use 2 good agents, 1 adversary and 2 landmarks.

  * •

Spread All agents collaborate and minimise the distance to each landmark. We
set the number of agents and landmarks equal to 3.

  * •

Push In this task, there is a single good agent, adversary and landmark. The
task is for the adversary to 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
$k=5$. The regression task for all environments is to predict the upper and
lower quantiles of the total cumulative reward over the $k$ steps, given as
input the initial world state. As in the classification experiments, we
partition the dataset into the following
partitions:$|\mathcal{D}_{\text{train}}|=1{,}000$,
$|\mathcal{D}_{\text{cal}}|=2{,}000$ and
$|\mathcal{D}_{\text{test}}|=2{,}000$.

For computing the bounds, we use CROWN Zhang et al. (2018b) with
$\ell^{\infty}$-bounded perturbations. To generate the adversarially perturbed
test points, we use the Fast Gradient Sign Method as given in (Goodfellow et
al., 2015).

Table 3: Marginal coverage and average interval lengths for each MPE
regression task for various $\epsilon$ perturbations bounded by an
$\ell^{\infty}$ norm. All results record a 95% confidence interval with
$n_{\text{splits}}=50$.

| Perturbation | $\epsilon=0.01$ | $\epsilon=0.02$ | $\epsilon=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–I | 0.928±0.004 | 0.605±0.006 | 0.951±0.003 | 0.673±0.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.006 | 0.966±0.003 | 0.806±0.005
Spread | Vanilla | 0.864±0.005 | 0.595±0.005 | 0.834±0.005 | 0.602±0.005 | 0.768±0.006 | 0.612±0.005
VRCP–I | 0.929±0.004 | 0.690±0.006 | 0.958±0.003 | 0.769±0.006 | 0.991±0.001 | 0.992±0.006
VRCP–C | 0.908±0.005 | 0.663±0.006 | 0.935±0.004 | 0.762±0.005 | 0.977±0.002 | 1.054±0.006
Push | Vanilla | 0.891±0.006 | 0.643±0.006 | 0.875±0.007 | 0.646±0.006 | 0.841±0.008 | 0.652±0.006
VRCP–I | 0.917±0.006 | 0.687±0.006 | 0.934±0.005 | 0.721±0.006 | 0.961±0.003 | 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

As seen in Table 3, both VRCP methods recover the marginal coverage guarantees
in the presence of adversarial perturbations, whereas vanilla CP fails
drastically after $\epsilon=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).

##  6 Limitations

VRCP’s scalability depends on that of the underlying neural network verifier.
We evaluated VRCP on small to medium-sized neural networks. For large
networks, existing complete verification methods 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 on classification and regression tasks demonstrated that
VRCP recovers valid marginal coverage in the presence of $\ell_{1}$,
$\ell_{2}$, and $\ell_{\infty}$-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 $\ell_{2}$ norm, achieving strong results without
relying on probabilistic smoothing or posthoc corrections. VRCP’s theoretical
guarantees and empirical performance showcase the potential of leveraging
verification tools for uncertainty quantification of machine learning models
under attack.

## Acknowledgments and Disclosure of Funding

This work is supported by the “REXASI-PRO” H-EU project, call HORIZON-
CL4-2021-HUMAN-01-01, Grant agreement ID: 101070028.

## References

  * Vovk et al. (2005) V. Vovk, A. Gammerman, and G. Shafer, _Algorithmic learning in a random world_. Springer, 2005, vol. 29.
  * Angelopoulos and Bates (2021) A. N. Angelopoulos and S. Bates, “A gentle introduction to conformal prediction and distribution-free uncertainty quantification,” _arXiv preprint arXiv:2107.07511_ , 2021.
  * Cohen et al. (2019) J. Cohen, E. Rosenfeld, and Z. Kolter, “Certified adversarial robustness via randomized smoothing,” in _international conference on machine learning_. PMLR, 2019, pp. 1310–1320.
  * Szegedy et al. (2014) C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. J. Goodfellow, and R. Fergus, “Intriguing properties of neural networks,” in _2nd International Conference on Learning Representations, ICLR_ , 2014.
  * Biggio and Roli (2018) B. Biggio and F. Roli, “Wild patterns: Ten years after the rise of adversarial machine learning,” in _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_ , 2018, pp. 2154–2156.
  * Gowal et al. (2018) S. Gowal, K. Dvijotham, R. Stanforth _et al._ , “On the effectiveness of interval bound propagation for training verifiably robust models,” 2018, arXiv preprint arXiv:1810.12715.
  * Wang et al. (2018) S. Wang, K. Pei, J. Whitehouse, J. Yang, and S. Jana, “Formal security analysis of neural networks using symbolic intervals,” in _USENIX Security Symposium_. USENIX Association, 2018, pp. 1599–1614.
  * Zhang et al. (2018a) H. Zhang, T.-W. Weng, P.-Y. Chen, C.-J. Hsieh, and L. Daniel, “Efficient neural network robustness certification with general activation functions,” in _Advances in Neural Information Processing Systems, NuerIPS_ , 2018.
  * Batten et al. (2024) 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\.
  * Lopez et al. (2023) 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.
  * Pulina and Tacchella (2010) L. Pulina and A. Tacchella, “An abstraction-refinement 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.
  * Katz et al. (2017) G. Katz, C. W. Barrett, D. L. Dill, K. Julian, and M. J. Kochenderfer, “Reluplex: An efficient SMT solver for verifying deep neural networks,” in _Computer Aided Verification - 29th International Conference, CAV_ , ser. Lecture Notes in Computer Science, vol. 10426. Springer, 2017, pp. 97–117.
  * Hosseini and Lomuscio (2023) M. Hosseini and A. Lomuscio, “Bounded and unbounded verification of rnn-based agents in non-deterministic environments,” in _International Conference on Autonomous Agents and Multiagent Systems, AAMAS_. IFAAMAS, 2023, pp. 2382–2384.
  * Gendler et al. (2021) A. Gendler, T.-W. Weng, L. Daniel, and Y. Romano, “Adversarially robust conformal prediction,” in _International Conference on Learning Representations_ , 2021.
  * Duchi et al. (2012) J. C. Duchi, P. L. Bartlett, and M. J. Wainwright, “Randomized smoothing for stochastic optimization,” _SIAM Journal on Optimization_ , vol. 22, no. 2, pp. 674–701, 2012.
  * Salman et al. (2019) H. Salman, J. Li, I. Razenshteyn, P. 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.
  * Yan et al. (2023) G. Yan, Y. Romano, and T.-W. Weng, “Provably robust conformal prediction with improved efficiency,” in _The Twelfth International Conference on Learning Representations_ , 2023.
  * Ghosh et al. (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.
  * Lei et al. (2013) J. Lei, J. Robins, and L. Wasserman, “Distribution-free prediction sets,” _Journal of the American Statistical Association_ , vol. 108, no. 501, pp. 278–287, 2013.
  * Romano et al. (2019) Y. Romano, E. Patterson, and E. Candes, “Conformalized quantile regression,” _Advances in neural information processing systems_ , vol. 32, 2019.
  * Xu et al. (2020a) K. Xu, Z. Shi, H. Zhang, Y. Wang, K.-W. Chang, M. Huang, B. Kailkhura, X. Lin, and C.-J. Hsieh, “Automatic perturbation analysis for scalable certified robustness and beyond,” _Advances in Neural Information Processing Systems_ , vol. 33, 2020.
  * Zhang et al. (2018b) H. Zhang, T.-W. Weng, P.-Y. Chen, C.-J. Hsieh, and L. Daniel, “Efficient neural network robustness certification with general activation functions,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * Xu et al. (2020b) K. Xu, H. Zhang, S. Wang, Y. Wang, S. Jana, X. Lin, and C.-J. Hsieh, “Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers,” _arXiv preprint arXiv:2011.13824_ , 2020.
  * Madry et al. (2017) A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu, “Towards deep learning models resistant to adversarial attacks,” _arXiv preprint arXiv:1706.06083_ , 2017.
  * Terry et al. (2021) J. Terry, B. Black, N. Grammel, M. Jayakumar, A. Hari, R. Sullivan, L. S. Santos, C. Dieffendahl, C. Horsch, R. Perez-Vicente _et al._ , “Pettingzoo: Gym for multi-agent reinforcement learning,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 15 032–15 043, 2021.
  * Goodfellow et al. (2015) I. J. Goodfellow, J. Shlens, and C. Szegedy, “Explaining and harnessing adversarial examples,” 2015.

##  Appendix A Additional Proof Details

Here we prove Proposition 1 regarding the prediction sets obtained from VRCP–I
and VRCP–C.

###### Proof of Proposition 1.

To prove $C(\bm{x})\subseteq C_{\epsilon}(\bm{x})$ for VRCP–I it suffices to
observe that

$\displaystyle C_{\epsilon}({\bm{x}})=\\{y\in Y:{s}^{\perp}({\bm{x}},y)\leq
Q_{1-\alpha}(F)\\}$ $\displaystyle\supseteq\bigcup_{\bm{x}^{\prime}\in
B_{\epsilon}({\bm{x}}_{n+1})}\\{y\in Y:S({\bm{x}^{\prime}},y)\leq
Q_{1-\alpha}(F)\\}$ $\displaystyle=\bigcup_{\bm{x}^{\prime}\in
B_{\epsilon}({\bm{x}}_{n+1})}C(\bm{x}^{\prime})\supseteq C(\bm{x}).$

To prove the same for VRCP–C, we observe that since
$Q_{1-\alpha}({F}^{\top})\geq Q_{1-\alpha}(F)$, we have that

$C_{\epsilon}({\bm{x}})=\\{y\in Y:S({\bm{x}},y)\leq
Q_{1-\alpha}({F}^{\top})\\}\supseteq\\{y\in Y:S({\bm{x}},y)\leq
Q_{1-\alpha}(F)\\}=C(\bm{x}).\qed$

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 $y\in
C_{\epsilon}(\bm{x}_{n+1})=[f^{\bot}-q,f^{\top}+q]$ satisfy
${s}^{\perp}(\bm{x}_{n+1},y)=\max{\\{f^{\bot}-y,y-f^{\top}\\}}\leq q$ and all
$y\not\in C_{\epsilon}(\bm{x}_{n+1})$ do not. For simplicity of notation, we
abbreviated ${f}^{\top}_{\alpha_{\text{high}}}(\bm{x}_{n+1})$ with $f^{\top}$,
${f}^{\perp}_{\alpha_{\text{low}}}(\bm{x}_{n+1})$ with $f^{\bot}$ and
$Q_{1-\alpha}(F)$ with $q$.

Assume $y\in C_{\epsilon}(\bm{x}_{n+1})$. We divide the proof into two cases:

  1. 1.

${s}^{\perp}(\bm{x}_{n+1},y)=f^{\bot}-y$, which implies that
$y\in[f^{\bot}-q,\frac{f^{\top}+f^{\bot}}{2}]$. It suffices to show that
$f^{\bot}-y\leq q$ for $y=f^{\bot}-q$, which is clearly satisfied.

  2. 2.

${s}^{\perp}(\bm{x}_{n+1},y)=y-f^{\top}$, which implies that
$y\in[\frac{f^{\top}+f^{\bot}}{2},f^{\top}+q]$. It suffices to show that
$y-f^{\top}\leq q$ for $y=f^{\top}+q$, which is clearly satisfied.

Finally, we show that $y\not\in C_{\epsilon}(\bm{x}_{n+1})$ implies
${s}^{\perp}(\bm{x}_{n+1},y)>q$: if $y<f^{\bot}-q$, we have that
${s}^{\perp}(\bm{x}_{n+1},y)=f^{\bot}-y>q$. Similarly, if $y>f^{\bot}+q$, we
have that ${s}^{\perp}(\bm{x}_{n+1},y)=y-f^{\top}>q$. ∎

##  Appendix B Model Details

All experimental results were obtained from running the code provided in the
supplementary material on a 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
supplementary material.

###  B.1 Classification

#### CIFAR10

We use 2 convolution layers with average pooling and dropout, followed by 2
linear layers. ReLU activations across all layers.

#### CIFAR100

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.

#### TinyImageNet

We use 4 convolution layers with dropout followed by 2 linear layers with
dropout. Leaky ReLU activation function with $a=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 $\mu=0.5$ and $\sigma=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
a weight decay of $5\times 10^{-4}$ and a 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 in the supplementary material.

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 $\alpha/2$ and $1-\alpha/2$ quantiles,
where $\alpha=0.1$, as in the other experiments.

The exact parameters for the RL policies can be found in the config files
within the supplementary material however have little bearing on the
efficiency of our results, being used only for the data-generating process.
The quantile regressors are each trained for 400 epochs, with a learning rate
of $10^{-5}$, dropout of 0.1 and a decay of $10^{-5}$.


11institutetext: Atal Bihari Vajpayee Indian Institute of Information
Technology and Management, Gwalior, MadhyaPradesh, India 11email:
<EMAIL_ADDRESS>
# Effect of intervention policies in an agent based spatial epidemic model of
Gwalior††thanks: This work was carried out at ABV- IIITM Gwalior, India with
funding from SERB, DST, Govt. of India

W. Wilfred Godfrey  0000-0002-0720-2647

###### Abstract

Covid-19 has ravaged the entire world and it may not be the last such to
ravage the world. COMOKIT [3] is an agent based spatial modeling tool to study
the effect of covid -19 in a geographical area by creating heterogenous
synthetic agents and their behaviours. This paper presents comokit based case
study on Gwalior region with respect to various intervention policies to curb
the spread of the disease.

###### Keywords:

COMOKIT, Multi-Agent Systems Spatial Modeling Geographical Information System

##  1 Introduction

###  1.1 Background

What is the effect on the pandemic in a semi urban area such as Gwalior with
both the rural and urban population. How does the disease dynamics vary with
different intervention policies in the context of Gwalior region. As the
disease dynamics is explored, the effect of disease regulatory policies on the
covid spread is also observed and checked.

A spatial approach towards measures on containing the disease spread is very
useful since it is not possible to microexamine the spatial effect from the
data that is available in the public domain. The other factors that have an
effect in the disease spread are the social, cultural, polical in nature which
are also difficult to mathematically model and assess. Within this context,
agent based modeling approach is a feasible option to incorporate the many
details of real world into its simulation model and perform the necessary
experimentations.

There have been a large number of models that have been proposed in the recent
times varying from systems to study the macro effect of the pandemic to the
systems to study micro effect of the pandemic. Agent based system help study
the micro effect of the pandemic by modeling individual human entities, their
simple and compound behaviours so as to construct and study the complex
phenomenon that evolves.

COMOKIT (COVID-19 Modelling Kit) [9] is an agent based near-realistic spatial
framework. The major submodels included in the COMOKIT are

  1. 1.

Person to person transmission sub-model

  2. 2.

Environmental transmission sub-models

  3. 3.

Human mobility sub-model

  4. 4.

Policy intervention sub-model

###  1.2 Objectives

The objectives of this work are as follows:

  1. 1.

To present the results on applying the agent based COMOKIT model on the
various rural to urban regions in and around around Gwalior

  2. 2.

To present the results on applying the agent based COMOKIT model on the
various rural to urban regions in and around Gwalior with various covid
restrictions.

The rest of the work is organized as follows. Section 2 presents a literature
survey with the literature gap in this direction. Section 3 presents some of
the statistics and details with respect to the covid-related scenario in
Gwalior. Section 4 presents the COMOKIT model as well as the results obtained
by applying the COMOKIT model on the gis maps of Gwalior followed by
concluding remarks in section 5.

##  2 Related Work

This section discusses about COMOKIT model as well as various works carried
out in literature using COMOKIT model.

###  2.1 COMOKIT (COVID-19 Modelling Kit)

COMOKIT (COVID-19 Modelling Kit) [9] is an agent based model developed to aid
the Government of Vietnam in making intervention based decisions with respect
to small towns of around 10000 inhabitants. The model comprises of spatially
dependent, interconnected and individual agents with private attributes such
as age, gender, employment and disease status. Each agent is fit with an
agenda which is a set of activity which is dependent on its private
attributes. Buildings are special type of entities, includes hospitals to
contain sick and critical diseased agents.

An agent based simulation is executed over several ”steps” with each step
representing 1 hour. Contagious agents with conditional probability infect
susceptible ones within same building. Special agents called Authority agents
test inhabitants for infection.

###  2.2 Literature related to COMOKIT

Gaudou et al [9, 8] have presented the COMOKIT model and also performed
experiments to explore the potential of the model. Brugiere et al. [5] have
presented an O.D.D. description of the COMOKIT model. The ‘ODD’ (Overview,
Design concepts, and Details) protocol standardizes descriptions of
individual-based and agent-based models. Chapuis et al.[7] have studied the
effect of COMOKIT with respect to non-pharmaceutical interventions for
reducing the spread of covid-19 with cases such as COMOKIT Azur and COMOKIT
Camps on the transmission of covid in refugee camps. Chapuis et al.[6] further
studied the effect of morpho-functional organization of cities on the spread
of COVID-19. COMOKIT Albatross [11] was one of the first country-scale
application of COMOKIT in the Netherlands using data for the construction of
individuals’ agendas accounting for covid variants, vaccination intervention,
better dashboard for visualizing data etc.

###  2.3  Literature related to Agent based systems for India

Narassima et al.[13] have modeled the COVID-19 transmission dynamics using an
agent based approach for Telangana and India [13], [narassima2021agent] using
synthetic population. Klein et al.[12] have provided a projection of estimates
of infection for India based on IndSim, an agent based system. Shubhada et al.
[2] used an agent based simulator for studying effect of covid-19 pandemic in
Bengaluru and Mumbai. Suryavanshi et al. [16] have used an agent based
approach to study the effect of the disease in a generic city of population
around 10000 parameterizing their model on Kolkata city. Bharat et al. [4]
have examined the effect of interventions with the characteristics of the city
of Pune, Maharashtra using an agent based model.

Among these only [16] and [2] are spatio-temporal models.

##  3 Methodology

|
---|---
(a)Gwalior District | (b)Northern Gwalior
Figure 1: The Gwalior District and the Northern part of Gwalior district comprising Ghatigaon and Morar blocks wihin the yellow contour region. |
---|---
(a)Gwalior City Locations Map | (b)Gwalior City Population Map
|
(a)Gwalior City Roads map | (b)Gwalior City Buildings map
Figure 2: The Gwalior city maps with with the Northern part Gwalior district
within yellow contour

###  3.1 About Gwalior

Gwalior district is located in the Northern Madhya Pradesh. It comprises of
four tehsils with Gwalior (formerly, Gird), Bhitarwar in the North and Dabra
(formerly, Pichore), Chinour in the South. The district of Gwalior also
comprises of four community development blocks viz. Ghatigaon (Barai), Morar
in the North and Dabra, Bhitarwar in the South. The city of Gwalior is in the
region connecting the two Northern blocks, ie. made of regions from the
Ghatigaon and Morar blocks.

The population of Gwalior district as per 2011 census is 20,32,036. The
population of Gwalior city is 10,69,276.

Figure 1 (a) and (b) show the Gwalior District and the Northern region of
Gwalior district within yellow contour. Figure 1 (a), (b) ,(c) and (d) show
the Gwalior city details such as administrative map, population map, city
roads map and city buildings map. The location map and city roads map have
been overlaid on satellite images.

###  3.2 GIS map sources

The GIS maps were obtained from various sources on the Internet Although the
COMOKIT model required only the buildings shape file. The buildings shape file
is obtained from the Openstreetmap dataset[14]. The population tiff files were
obtained from Humanitarian data exchange [10]. The administrative areas shape
files were downloaded from the global administrative dataset [15].

###  3.3 Models Used

In India, various measures such as school closures, complete lockdown and home
containment were implemented at various instances to control the spread of the
virus across the large population. Same measures were also implemented in the
Gwalior region. This experiment compares the three measures such as school
closure, home containment and no containment for the spatial map of Gwalior
versus the number of deaths.

Further, the following containment actions were compared with No containment,
Realistic lockdown with 10% of essential workers and 20 daily tests, Family
containment when positive member and Dynamic spatial lockdown versus the
number of deaths. The dynamic spatial lockdown strategy factors in the overall
deaths in a geographical region to take decisions on various containment
measures to minimize the destruction in an uncertain environment.

In the third set of experiments for containment policy decision making, the
effect of partial testing, mass testing, no testing and no policy were used
for comparision. The partial testing scenario is more realistic due to the
lack of resources and lack of willingness in people to participate in mass
testing.

###  3.4 Workflow

The preparation and execution workflow performed within the COMOKIT
environment are as follows:

  1. 1.

Preparation of data

  2. 2.

Setting program environment

  3. 3.

Models

####  3.4.1 Preparation of data

The tutorial on using the COMOKIT to create a case study in [1] was followed
by performing the following steps.

  1. 1.

Import the study area into GAMA softare.

  2. 2.

Generate the build environment and satellite image

  3. 3.

Retrieve the GoogleMap data with Qgis.

  4. 4.

Use the GoogleMap data to assign types to buildings

####  3.4.2 Setting up program environment

The epidemiological parameters of the COMOKIT model are setup through the
parameter variables in Mode/Parameters.gaml. The paramters are listed under
various heads such as Epidemiological parameters, Population parameters,
Synthetic agenda parameters and Building type parameters. The epidemiological
parameters given are further grouped under a. Environmental contamination
dynamics b. Human to human transmission dynamics c. Hospitalization and
severity d. Testing and mask wearing. The synthetic agent population
generation dynamics is set through population parameters. The behaviour of the
synthetic agents over time flow is caliberated using synthetic agenda
generator and activity file. For the experiments conducted, the default
parameters were used.

####  3.4.3 Models

The following gaml files under policy comparision component in the comokit
modeling kit were executed with the Gwalior spatial map.

  1. 1.

Comparison of three measures

  2. 2.

Comparison of containments

  3. 3.

Comparison of realistic actions

##  4 Results and Analysis

The software used for the experimentation was the Gama spatial agent modeling
tool and the comokit covid 19 modeling toolkit. The experiments were run for
around 5500 cycles.

Figure 3 shows that all the three containment measures do not differ much in
their effect in the long run with more or less similar peaks for the Gwalior .

Figure 4 compares four different strategies for reducing disease spread. This
figure shows that distinct differences between different containment
strategies. The no containment strategy shows an immediate peak of the disease
in the region. Realistic lockdown strategy is relatively better than the no-
containment strategy. The family containment and dynamic spatial lockdown
strategies if fully effected show the best possible response for the spatial
map of Gwalior.

Figure 5 compares four realistic actions which include tests. Among the four,
Limited tests with late lockdown is only as good as having no policy for the
region. The mass testing and household quarantine of confirmed cases is the
best strategy but not practical. Not performing any testing but ensuring that
the risky people stay at home is still a better strategy than no policy and
late lockdown policies.

From figures 3, 4 and 5, it can be inferred that while mass testing really
proves beneficial, dynamic spatial lockdown and sincere family containment on
a member becoming positive are also better measures for containing the disease
spread.

Figure 3: A Comparison of the three measures Figure 4: A comparison of the
containments Figure 5: A comparison of realistic actions

##  5 Conclusion

This paper presented some of the results obtained by using spatial data of
Gwalior, India as input to the COMOKIT spatial modelling kit. The experiments
to make policy decisions were executed and the results have been presented. On
comparision, the results show that dynamic spatial containment strategy works
well. This work can be further enhanced by altering the parameters used in the
simulation framework to match with the realworld. A comparision of the
obtained results with the realworld variations may further help in
investigating identifying any other factors that may have contributed to the
disease spread as it happened.

##  6 Acknowledgement

The author acknowledges DST-SERB for funding the work reported in this paper.

## References

  * [1] 5 minutes tutorial to create a complete case study in comokit. https://www.youtube.com/watch?v=sQI63mgtYi4, accessed: 2022-01-17
  * [2] Agrawal, S., Bhandari, S., Bhattacharjee, A., Deo, A., Dixit, N.M., Harsha, P., Juneja, S., Kesarwani, P., Swamy, A.K., Patil, P., et al.: City-scale agent-based simulators for the study of non-pharmaceutical interventions in the context of the covid-19 epidemic. Journal of the Indian Institute of Science pp. 1–39 (2020)
  * [3] Alexis Drogoul: COMOKIT (CoVid19 Modeling Kit) .  https://comokit.org/  (2020)
  * [4] Barat, S., Parchure, R., Darak, S., Kulkarni, V., Paranjape, A., Gajrani, M., Yadav, A.: An agent-based digital twin for exploring localized non-pharmaceutical interventions to control covid-19 pandemic. Transactions of the Indian National Academy of Engineering 6(2), 323–353 (2021)
  * [5] Brugière, A., Chapuis, K., Choisy, M., Drogoul, A., Gaudou, B., Larmande, P., Philippon, D., Taillandier, P.: Odd description of the comokit model. Ecological Modelling 221(23), 2760–8 (2010)
  * [6] Chapuis, K., Taillandier, P., Gaudou, B., Brugière, A., Drogoul, A., Araldi, A., Fusco, G.: Using the comokit model to study the impact of the morpho-functional organization of cities on the spread of covid-19. In: 6th International Workshop on Agent-Based Modelling of Urban Systems (ABMUS@ AAMAS 2021). pp. 61–65 (2021)
  * [7] Chapuis, K., Taillandier, P., Gaudou, B., Quang, N.H., Brugière, A., Drogoul, A.: Comokit: a brief synthesis of the gama supported agent-based framework to study npi against covid-19. In: GAMA Days 2021 (2021)
  * [8] Drogoul, A., Taillandier, P., Gaudou, B., Choisy, M., Chapuis, K., Quang, N.H., Nguyen-Ngoc, D., Philippon, D., Brugière, A., Larmande, P.: Designing social simulation to (seriously) support decision-making: Comokit, an agent-based modelling toolkit to analyse and compare the impacts of public health interventions against covid-19. Review of Artificial Societies and Social Simulation-RofASSS (2020)
  * [9] Gaudou, B., Huynh, N.Q., Philippon, D., Brugière, A., Chapuis, K., Taillandier, P., Larmande, P., Drogoul, A.: Comokit: A modeling kit to understand, analyze, and compare the impacts of mitigation policies against the covid-19 epidemic at the scale of a city. Frontiers in public health 8 (2020)
  * [10] Humanitarian data exchange, HDX contributors: OCHA’s Centre for Humanitarian Data retrieved from https://data.humdata.org/ .  https://centre.humdata.org/  (2017)
  * [11] Kim, S., Rasouli, S., Chapuis, K., Bhamidipati, S., Brugière, A.: Comokit-albatross: An agent-based, activity-based model on covid-19 simulation. In: GAMA Days 2021 (2021)
  * [12] Klein, E., Lin, G., Tseng, K., Schueller, E., Kapoor, G., Laxminarayan, R.: Covid-19 for india updates. Center for Disease Dynamics, Economics, and Policy and Johns Hopkins University, USA (2020)
  * [13] Narassima, M., Jammy, G.R., Sankarshana, A., Pant, R., Anbuudayasankar, S., Choudhury, L., Yeldandi, V., Singh, S., John, D.: An agent-based model to assess covid-19 spread and health systems burden in telangana state, india. medRxiv (2020)
  * [14] OpenStreetMap contributors: Planet dump retrieved from https://planet.osm.org .  https://www.openstreetmap.org  (2017)
  * [15] Robert J. Hijmans: GADM, the Database of Global Administrative Areas .  https://gadm.org/  (2009)
  * [16] Suryawanshi, G., Madhavan, V., Mitra, A., Chakrabarti, P.P.: City-scale simulation of covid-19 pandemic and intervention policies using agent-based modelling. arXiv preprint arXiv:2104.01650 (2021)