# Approximating Full Conformal Prediction at Scale via Influence Functions

Javier Abad1 2, Umang Bhatt 1 3, Adrian Weller 1 3, Giovanni Cherubin 4

###### Abstract

Conformal prediction (CP) is a wrapper around traditional machine learning
models, giving coverage guarantees under the sole assumption of
exchangeability; in classification problems, for a chosen significance level
$\varepsilon$, CP guarantees that the error rate is at most $\varepsilon$,
irrespective of whether the underlying model is misspecified. However, the
prohibitive computational costs of “full” CP led researchers to design
scalable alternatives, which alas do not attain the same guarantees or
statistical power of full CP. In this paper, we use influence functions to
efficiently approximate full CP. We prove that our method is a consistent
approximation of full CP, and empirically show that the approximation error
becomes smaller as the training set increases; e.g., for $10^{3}$ training
points the two methods output p-values that are $<10^{-3}$ apart: a negligible
error for any practical application. Our methods enable scaling full CP to
large real-world datasets. We compare our full CP approximation (ACP) to
mainstream CP alternatives, and observe that our method is computationally
competitive whilst enjoying the statistical predictive power of full CP.

##  1 Introduction

Conformal prediction (CP) is a post-hoc approach to providing validity
guarantees on the outcomes of machine learning (ML) models; in classification,
an ML model wrapped with “full” CP outputs prediction sets that contain the
true label with (chosen) probability $1-\varepsilon$, under mild distribution
assumptions. Unfortunately, full CP is notoriously computationally expensive.
Many have proposed alternative methods to avoid the full CP objective; these
include: split (or “inductive”) CP (Papadopoulos et al. 2002), cross-CP (Vovk
2012), jackknife+ (Barber et al. 2021), RAPS (Angelopoulos et al. 2020), CV+
(Romano, Sesia, and Candes 2020). While these methods have shown practical
promise, they do not attain the same validity guarantee as full CP or its
statistical power (e.g., prediction set size). Recent work optimized full CP
for ML models that support incremental and decremental learning by speeding up
the leave-one-out (LOO) procedure required for the prediction set calculation
(Cherubin, Chatzikokolakis, and Jaggi 2021); however, this approach may not
scale to complex models such as neural networks.

Method | Prediction set
---|---
ACP | bird, cat, deer, frog
SCP | bird, deer, frog
RAPS | bird, cat, deer, dog, frog
CV+ | bird, cat, deer, dog, frog

Method | Prediction set
---|---
ACP | auto, cat, frog, horse, truck
SCP | auto, deer, frog, truck
RAPS | plane, auto, bird, deer, frog, ship, truck
CV+ | plane, auto, deer, frog, horse, truck

Method | Prediction set
---|---
ACP | cat, deer, frog, horse
SCP | cat, deer, dog, frog, horse, truck
RAPS | cat, deer, dog, frog, horse, truck
CV+ | cat, deer, dog, frog, horse

Figure 1: Prediction sets generated by CP methods ($\varepsilon=0.2$) for
CIFAR-10 examples. Our method (ACP) yields prediction sets that (1) contain
the true label and (2) are the smallest. ACP approximates well full CP in
large training sets, such as CIFAR-10, inheriting its statistical power.

Herein, we first discuss how to approximate the full CP objective. We focus on
full CP for classification, and optimize it for ML models trained via ERM
(e.g., logistic regression, neural networks). The key insight we leverage is
that, for each test point, full CP: (i) retrains the underlying ML model on
the additional test point, and (ii) performs a LOO procedure for each training
point. We observe we can approximate both steps, and avoid retraining each
time, by using first order influence functions (Hampel 1974). We term our
method Approximate full Conformal Prediction (ACP), and we prove finite-sample
error guarantees: as the training set grows, ACP approaches full CP. We then
show that a stronger regularization parameter for training the underlying ML
model improves the approximation quality.

We empirically demonstrate that ACP is competitive with existing methods on
MNIST (LeCun 1998), CIFAR-10 (Krizhevsky, Nair, and Hinton 2009), and US
Census (Ding et al. 2021). Unlike full CP, ACP scales to large datasets for
real-world ML models (logistic regression, multilayer perceptrons, and
convolutional neural networks). Performance-wise, ACP is consistently better
than existing alternatives in terms of statistical power: it attains the
desired error rate $\varepsilon$ with tighter prediction sets; Figure 1 shows
on CIFAR-10 examples where, unlike other methods, ACP learns smaller
prediction sets that still contain the true label.

##  2 Preliminaries

We describe full CP, and then introduce influence functions, our main
optimization tool.

###  2.1 Notation and full CP

Consider a training set $Z=(X,Y)\in(\mathcal{X}\times\mathcal{Y})^{N}$. For a
test object $x\in\mathcal{X}$ and a chosen significance level
$\varepsilon\in[0,1]$, a CP returns a set
$\Gamma^{\varepsilon}_{x}\subseteq\mathcal{Y}$ containing $x$’s true label
with probability at least $1-\varepsilon$. This guarantee (validity) holds for
any exchangeable distribution on $Z\cup\\{(x,y)\\}$. Since the error rate of a
CP is guaranteed by validity, a data analyst only needs to control the
tightness (efficiency) of its prediction set; average
$|\Gamma^{\varepsilon}_{x}|$ is a common efficiency criterion (Vovk et al.
2016). Efficiency is controlled by improving the underlying model that CP
wraps.

##### Underlying model.

A CP can be built around virtually any ML model $\theta$. We assume the
underlying model is trained via ERM by minimizing the risk:
$R(Z,\hat{\theta})\equiv\frac{1}{N}\sum_{z_{i}\in Z}\ell(z_{i},\hat{\theta})$;
$\ell(z,\theta)$ is the loss of the model at a point $z$, which we assume to
be convex and twice differentiable in $\theta$. This assumption holds for many
popular loss functions. Let
$\theta_{Z}\equiv\operatorname*{argmin}_{\hat{\theta}\in\Theta}R(Z,\hat{\theta})$
be the ERM solution; we assume $\theta_{Z}$ to be unique, and discuss
relaxations in Section 7.

##### Nonconformity measure.

The underlying model is used to construct a nonconformity measure, which
defines a CP. A nonconformity measure is a function
$A:(\mathcal{X}\times\mathcal{Y})\times(\mathcal{X}\times\mathcal{Y})^{N}\rightarrow\mathbf{R}$
which scores how conforming (or similar) an example $(x,y)$ is to a bag of
examples $\bar{Z}$. We focus on the two most common ways of defining
nonconformity measures (and, hence, CP) on the basis of a model: the deleted
and the ordinary scheme (Vovk, Gammerman, and Shafer 2005).

##### Full CP (deleted).

Consider example $\hat{z}$ and a training set $Z$. The nonconformity measure
can be defined from the deleted (LOO) prediction:
$A(z_{i},Z)=\ell(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})$, for
all $z_{i}\in Z\cup\\{\hat{z}\\}$. Computing this nonconformity measure
requires training the model on $Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}$. This
scheme computes the loss at a point after removing it from the model’s
training data.

Algorithm 1 shows how the nonconformity measure is used in full CP. For a test
point $x$, CP runs a statistical test for each possible label
$\hat{y}\in\mathcal{Y}$ to decide if it should be included in the prediction
set $\Gamma^{\varepsilon}_{x}$. The statistical test requires computing a
nonconformity score $\alpha_{i}$ by running $A$ for each point in the
augmented training set $Z\cup\\{(x,\hat{y})\\}$; then, a p-value is computed,
and a decision is taken based on the threshold $\varepsilon$. This algorithm
is particularly expensive. Crucially, for each test point, and for every
candidate label, one needs to retrain the underlying ML model $N+1$ times.

##### Full CP (ordinary).

A computationally faster scheme is achieved by taking the loss at the point:
$A(z_{i},Z)=\ell(z_{i},\theta_{Z\cup\\{\hat{z}\\}})$. We refer to this as the
ordinary scheme (Algorithm 3). This method is inherently faster than the
deleted approach, as it only requires training one model per test example and
candidate label. However, the ordinary scheme generally leads to less
efficient predictions (Section 5).

##### Optimizing CP.

The complexity of full CP depends on: (i) the number of training points $N$,
and (ii) the number of labels $|\mathcal{Y}|$. Optimizing w.r.t.
$|\mathcal{Y}|$ is necessary for regression settings, where full CP is not
applicable directly; this was done, for specific choices of nonconformity
measures, by Papadopoulos, Vovk, and Gammerman (2011); Nouretdinov, Melluish,
and Vovk (2001); Lei (2019); Ndiaye and Takeuchi (2019); Ndiaye (2022). Our
work focuses on optimizing w.r.t. $N$; this enables applying full CP
classification to large datasets. Future work may combine our optimizations
and CP regression strategies to obtain faster regressors on large training
sets (e.g., Cherubin, Chatzikokolakis, and Jaggi 2021).

###  2.2 Influence functions

Influence functions (IF) are at the core of our proposal. For a training
example $z_{i}\in Z$, let
$I_{\theta}(z_{i})=-\frac{1}{N}H_{\theta}^{-1}\nabla_{\theta}\ell(z_{i},\theta)$
be the influence of $z_{i}$ on model $\theta$, where
$H_{\theta}=\nabla^{2}_{\theta}R(Z,\theta)$ is the Hessian; by assumption,
$H_{\theta}$ exists and is invertible. A standard result by Hampel (1974)
shows that:

$\theta_{Z\setminus\\{z_{i}\\}}-\theta\approx-I_{\theta}(z_{i}).$ (1)

$I_{\theta}$ says how much $z_{i}$ affects $\theta$ during training. We can
apply influence functions for computing the influence of a point $z_{i}$ on
any functional. In our work, we are interested in the influence on the loss
function at a point $z$. Let
$I_{\ell}(z,z_{i})=\nabla_{\theta}\ell(z,\theta)^{\top}I_{\theta}(z_{i})$.
Then, similarly to above, we have

$\ell(z,\theta_{Z\setminus\\{z_{i}\\}})-\ell(z,\theta)\approx-
I_{\ell}(z,z_{i}).$ (2)

Algorithm 1 Full CP

1: for $x$ in test points do

2: for $\hat{y}\in\mathcal{Y}$ do

3: $\hat{z}=(x,\hat{y})$

4: for $z_{i}\in Z\cup\\{\hat{z}\\}$ do

5:
$\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}}=\operatorname*{argmin}_{\hat{\theta}\in\Theta}R(Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\},\hat{\theta})$

6: $\alpha_{i}=\ell(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})$

7: end for

8:
$p_{(x,\hat{y})}=\frac{\text{\\#}\\{i=1,...,N+1\,:\,\alpha_{i}\geq\alpha_{N+1}\\}}{N+1}$

9: If $p_{(x,\hat{y})}>\varepsilon$, include $\hat{y}$ in set
$\Gamma^{\varepsilon}_{x}$

10: end for

11: end for

Algorithm 2 Approximate full CP (ACP)

1:
$\theta_{Z}=\operatorname*{argmin}_{\hat{\theta}\in\Theta}R(Z,\hat{\theta})$

2: for $x$ in test points do

3: for $\hat{y}\in\mathcal{Y}$ do

4: $\hat{z}=(x,\hat{y})$

5: for $z_{i}\in Z\cup\\{\hat{z}\\}$ do

6: $\tilde{\alpha}_{i}=$ Approximate via Eq. 3 or 4

7: end for

8:
$p_{(x,\hat{y})}=\frac{\text{\\#}\\{i=1,...,N+1\,:\,\tilde{\alpha}_{i}\geq\tilde{\alpha}_{N+1}\\}}{N+1}$

9: If $p_{(x,\hat{y})}>\varepsilon$, include $\hat{y}$ in set
$\Gamma^{\varepsilon}_{x}$

10: end for

11: end for

Figure 2: Full CP (left) and our proposal, ACP, (right). In ACP, the
underlying ML model is only trained once, and nonconformity scores are
approximated via influence functions in Line 6.

##  3 Approximate full Conformal Prediction

Our proposal (ACP) hinges on approximating the nonconformity scores via IF. We
describe our approach, and prove theoretical results on its consistency and
approximation error.

###  3.1 Approach

The bottleneck of running full CP is the computation of the nonconformity
scores
$\alpha_{i}=\ell(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})$. Each
score is determined by computing the loss of the model at point $z_{i}\in
Z\cup\\{\hat{z}\\}$ after adding point $\hat{z}$ and removing point $z_{i}$
from the model’s training data $Z$. There are two ways to approximate
$\alpha_{i}$ via IF: we can approximate the contribution of adding and
removing the points to the learned model $\theta_{Z}$, and then evaluate its
loss at $z_{i}$ (indirect approach), or we can directly approximate the
contribution of the points on the loss function (direct approach). We describe
both below.

##### Indirect approach.

We can use Equation 1 to approximate model
$\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}}$ and then compute its loss.
That is, let
$\tilde{\theta}_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}}\equiv\theta_{Z}+I_{\theta_{Z}}(\hat{z})-I_{\theta_{Z}}(z_{i})$.
Then:

$\alpha_{i}\approx\ell(z_{i},\tilde{\theta}_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})\,.$
(3)

##### Direct approach.

We can directly compute the influence on the loss. Let $\theta_{Z}$ be a model
trained via ERM on the entire training set $Z$. The direct approximation for
the score is:

$\displaystyle\alpha_{i}$
$\displaystyle\approx\tilde{\ell}(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})\equiv\ell(z_{i},\theta_{Z})+I_{\ell}(z_{i},\hat{z})-I_{\ell}(z_{i},z_{i}).$
(4)

$I_{\ell}(z_{i},\hat{z})$ and $-I_{\ell}(z_{i},z_{i})$ are the influence of
including point $\hat{z}$ and excluding $z_{i}$ (Equation 2). Algorithm 2
(ACP) shows how both approaches enable approximating full CP.

ACP gives a substantial speed-up over full CP. In contrast to full CP, ACP has
a training phase, in which we: compute the Hessian, the gradient for each
point $z_{i}$, and provisional scores $\ell(z_{i},\theta_{Z})$ for $z_{i}\in
Z$. For predicting a test point $\hat{z}$, it suffices to compute its
influence by using the Hessian and gradients at $z_{i}$ and $\hat{z}$, which
is cheap, and update the provisional scores (see time complexities in Table
4). This enables ACP to scale to large real-world datasets such as CIFAR-10
(Section 5). As a reference, running full CP for the synthetic dataset
(Section 4) with 50 features, 1000 training points, and 100 test points took
approximately 5 days, whereas ACP took less than 1 hour (CPU time with an
Intel Core i7-8750H).

###  3.2 Theoretical analysis

In this section, we establish the consistency of ACP: its approximation error
gets smaller as the training set grows. Further, we study its finite-sample
validity, and how the underlying model’s regularization parameter affects its
approximation error. The consistency of ACP for the indirect approach comes
from a result by Giordano et al. (2019). Proving consistency for the direct
approach requires a condition, which we state in the next part as a
conjecture.

#### Direct approximation is better than indirect

We conjecture that the direct approach approximates better than the indirect
one. Intuitively, it is much easier to approximate the loss at a point
(direct) than to estimate the effect of a training point on the model weights,
which lay in a high-dimensional space (indirect). We observed this conjecture
to hold consistently across a number of simulations (Section 4). Formally:

######  Condition 1.

Assume that the loss $\ell$ is convex and differentiable. Then the direct
method (Equation 4) is a better approximation than the indirect one (Equation
3). That is, let
$\alpha_{i}=\ell(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})$;
then:

$|\tilde{\ell}(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})-\alpha_{i}|\leq|\ell(z_{i},\tilde{\theta}_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})-\alpha_{i}|\,.$

Without 1, we can prove consistency for the indirect approach, but not for the
direct approach.

#### Consistency of ACP

We show that ACP is a consistent estimator of full CP. We establish this
equivalence in the most generic form possible: we demonstrate that
nonconformity scores produced by Algorithm 2 approximate those produced by
full CP. In turn, the p-values (and, consequently, error rates) of the two
methods get increasingly closer.

Our result is an extension of the work by Giordano et al. (2019), who showed
that IF consistently estimate a model’s parameters in a LOO setting. This
result holds under a set of assumptions (1 in Appendix B), which Giordano et
al. (2019) showed to hold for a variety of settings; e.g., they hold when $Z$
are well-behaved IID data and $\ell(\cdot,\theta)$ is an appropriately smooth
function. Note that 1 limits the set of applicable nonconformity measures,
e.g., by assuming them to be continuously differentiable.

######  Theorem 2 (Consistency of approximate full CP).

Under 1 and 1, let
$\alpha_{i}=\ell(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})$, and
suppose $\ell$ is $K$-Lipschitz. For every $N$ there is a constant $C$ such
that for every $z_{i}\in Z\cup\\{\hat{z}\\}$:

$|\tilde{\ell}(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})-\alpha_{i}|\leq
KC\frac{\max\\{C_{g},C_{h}\\}^{2}}{N}\,,$

for finite constants $C_{g},C_{h}$ s.t.
$\sup\limits_{\theta\in\Theta}\frac{1}{\sqrt{N}}||\nabla_{\theta}\ell(z,\theta)||_{2}\leq
C_{g}$ and
$\sup\limits_{\theta\in\Theta}\frac{1}{\sqrt{N}}||\nabla^{2}_{\theta}\ell(z,\theta)||_{2}\leq
C_{h}$.

This result gives a finite-sample bound for the error of the direct approach
for ACP; the error of the indirect approach is also bounded as a byproduct of
the same proof. We conclude that, as $N$ grows, ACP’s scores get increasingly
closer to those produced by full CP. We evaluate this in Section 4.

#### Validity of ACP

Lin, Trivedi, and Sun (2021) state that finite-sample validity is not
guaranteed when the LOO is estimated with IF since they cannot be exactly
computed. They exemplify this issue in the Discriminative Jackknife (Alaa and
Van Der Schaar 2020), which approximates the IF using Hessian-Vector-Products
(Pearlmutter 1994).

Although we alleviate part of the issue by computing the exact Hessian, we
cannot guarantee that our LOO estimation is exact. Basu, Pope, and Feizi
(2021) also summarize several issues with using IF in deep learning.
Nevertheless, ACP still inherits the high efficiency of full CP, and we
observe that validity holds in practice (Section 5). Future work can prove if
the approximate scores follow the same distribution as the true ones and,
consequently, if exchangeability still holds.

#### Relation to regularization parameter

By extending a result by Koh et al. (2019), we investigate the effect of the
ERM regularization parameter on ACP’s approximation error. This result makes
fairly simplistic assumptions (Section B.2).

######  Theorem 3 (Approximation goodness w.r.t. regularizer).

Suppose the model is trained via ERM with regularization parameter $\lambda$.
Under the assumptions of Proposition 5, Assumption 2, and neglecting
$\mathcal{O}(\lambda^{-3})$ terms, we have the following cone constraint
between the true nonconformity measure
$\alpha_{i}=\ell(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})$ and
its direct approximation
$\tilde{\ell}(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})\equiv\ell(z_{i},\theta_{Z})+I_{\ell}(z_{i},\hat{z})-I_{\ell}(z_{i},z_{i})$,
where
$g(\lambda)=(1+\nicefrac{{3\sigma_{max}}}{{2\lambda}}+\nicefrac{{\sigma_{max}^{2}}}{{2\lambda^{2}}})$,
and $\sigma_{max}$ is the maximum eigenvalue of the Hessian $H$:

$\ell(z_{i},\theta_{Z})+I_{\ell}(z_{i},\hat{z})-g(\lambda)I_{\ell}(z_{i},z_{i})\leq\alpha_{i}\leq\tilde{\ell}(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}}).$

##  4 Experiments on synthetic data

We study the properties of ACP outlined in Section 3.2 on synthetic data
(Appendix C); the underlying model is logistic regression with cross-entropy
loss. Results are averaged across 100 test points.

##### Direct and indirect approximation.

We empirically evaluate 1, which claims that the direct method (Equation 4) is
never worse than indirect (Equation 3). Figure 3 shows the absolute distance
between full CP and ACP’s nonconformity scores as a function of the training
set size. Results confirm that direct is always better than indirect, although
the two get close for large $N$. Importantly, the nonconformity scores
produced by ACP get increasingly better at approximating those of full CP as
the training set grows (cf. Theorem 2). We shall now focus on the direct
approach.

Figure 3: Comparison between direct and indirect approximations. We show the
difference between the nonconformity scores of full CP and their approximation
as a function of the training set size, averaged across 100 test points. These
results support that the direct method is never worse than the indirect (1),
and that both approximate full CP increasingly better (Theorem 2). The
standard deviation for the direct approach (blue) is negligible.

##### Approximation goodness.

We evaluate how well ACP approximates full CP, under various parameter
choices, as the training set grows. Figure 4(a) shows the difference between
the nonconformity scores of full CP and ACP as the number of features ranges
in 5-100. The number of features does impact the IF approximation, although
the error becomes negligible as the training set increases. Theorem 3 shows
that, unsurprisingly, a larger $\lambda$ (i.e., stronger regularization)
implies better approximation. We confirm this in Figure 4(b). Our analysis
focuses on the approximation error between nonconformity scores; yet, we
remark that a small error between scores implies a more fundamental
equivalence between full CP and ACP: their p-values should also have a small
distance.

(a)  Vary $\\#$ of features

(b)  Vary regularization

(c)  P-values difference

(d)  Validity

Figure 4:  Difference in nonconformity scores for different numbers of
features (4(a)) and for various regularization strengths (4(b)). The
differences in scores are averaged across 100 test points. We also report the
difference between p-values (4(c)) and error rate (4(d)).

Figure 4(c) compares full CP and ACP’s p-values. The difference is smaller
than $10^{-3}$ with a training set of $600$, and it becomes negligible with
$N=10k$ training examples. Observe that in CP the p-value is thresholded by
the significance value $\varepsilon$ to obtain a prediction (Algorithm 1 ). As
practitioners are generally interested in values $\varepsilon$ with no more
than 2 decimals of precision (e.g., $\varepsilon=0.15$), we argue that an
approximation error smaller than $10^{-3}$ between p-values is more than
sufficient for any practical application. Figure 4(d) compares the error rate
(for $\varepsilon=0.1$) between full CP and ACP. We observe that, after 500
training points, the two methods have the same error.

##  5 Experiments with real data

We compare mainstream CP alternatives with ACP on the basis of their
predictive power (efficiency). Because of its computational complexity, it is
infeasible to include full CP in these experiments. Nevertheless, given the
size of the training data, the consistency of ACP (Theorem 2), and the results
in Section 4, we expect ACP to perform similarly to full CP.

###  5.1 Existing alternatives to Full CP

There are several alternative approaches to CP for classification. In this
work, we compare ACP with:

  * •

Split (or “inductive”) Conformal Prediction (SCP) (Papadopoulos et al. 2002)
works by dividing the training set into proper training set and calibration
set. The model is fit on the proper training set, and the calibration set is
used to compute the nonconformity scores.

  * •

Regularized Adaptive Prediction Sets (RAPS) (Angelopoulos et al. 2020), is a
regularized version of Adaptive Prediction Sets (APS) (Romano, Sesia, and
Candes 2020). APS constructs Generalized inverse quantile conformity scores
from a calibration set adaptively w.r.t. the data distribution. RAPS uses
regularization to minimize the prediction set size while satisfying validity.

  * •

Cross-validation+ (CV+) (Romano, Sesia, and Candes 2020) exploits a cross-
validation approach while constructing the conformity scores similarly to APS.
CV+ does not lose predictive power due to a data-splitting procedure, but it
is computationally more expensive.

##### Datasets.

We select datasets to illustrate the performance of ACP in various scenarios:
a simple classification problem with images (MNIST (LeCun 1998)), a more
complex setting (CIFAR-10 (Krizhevsky, Nair, and Hinton 2009)), and a binary
classification with tabular data (US Census (Ding et al. 2021)); details in
Section C.2.

Method | Prediction set
---|---
ACP (D) | bird, cat, deer, dog, frog, horse
ACP (O) | plane, bird, cat, deer, dog, frog, horse
SCP | plane, bird, cat, deer, dog, frog, horse
RAPS | plane, bird, cat, deer, dog, frog, horse, truck
CV+ | plane, auto, bird, cat, deer, dog, frog, horse

(a)  Test image and prediction set ($\varepsilon=0.05$)

(b)  Prediction set size (ACP)

(c)  Prediction set size (all)

Figure 6: Prediction set for a fixed $\varepsilon$ (6(a)), and prediction set
size w.r.t. $\varepsilon$ for ACP (6(b)) and comparing methods (6(c)). For
each method,
${\color[rgb]{0.94140625,0.5,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0.94140625,0.5,0.5}\bigstar}$
is the highest $\varepsilon$ for which the prediction set includes the true
label; higher is better. We also show the AUC in the interval
$\varepsilon\in[0,0.2]$; lower is better.

###  5.2 A warm-up example

We run an illustrative experiment for a CIFAR-10 test point picked uniformly
at random. We consider a neural network with 3 layers of 100, 50, and 20
neurons; we refer to this network as MLPC. Section C.3 gives implementation
details.

Figure 6(a) shows the prediction set for a fixed $\varepsilon=0.05$; we
observe that, while all the methods output the true label, the prediction set
of ACP (deleted) is the tightest (i.e., more efficient). We also report how
the prediction set size changes w.r.t. $\varepsilon$, for ACP (Figure 6(b))
and for all methods (Figure 6(c)). As a way of comparing the curves, we
include the AUC for the interval $\varepsilon\in[0,0.2]$. ACP (deleted and
ordinary) have the smallest AUC. Finally, for each method we report the
highest $\varepsilon$ for which the prediction set contains the true label. A
higher value indicates that, for this test example, the method would still be
accurate with an $\varepsilon$ larger than $0.05$, which would correspond to
tighter prediction sets. Once again, ACP (deleted and ordinary) have the
largest values. We show similar instances in Section E.2. In the next part, we
observe this behavior generalizes to larger test sets.

We observe an unstable behavior in the predictions of RAPS and CV+: their
prediction set size considerably oscillates as $\varepsilon$ increases. The
reason is that their prediction sets are not guaranteed to be nested; that is,
$\varepsilon>\varepsilon^{\prime}$ does not imply that the prediction sets
$\Gamma^{\varepsilon}\subseteq\Gamma^{\varepsilon^{\prime}}$. Specifically,
because RAPS and CV+ use randomness to decide whether to include a label in
the set, the true label may appear and then disappear for a smaller
significance level. This may not be desirable in some practical
applications.111RAPS allows a non-randomized version, although with a more
conservative behavior and considerably larger prediction sets. The prediction
set for ACP and SCP monotonically decreases with $\varepsilon$, by
construction.

###  5.3 Experimental setup

We evaluate the methods for five underlying models: three multilayer
perceptrons with architectures (neurons per layer): 20-10 (MLPA), 100 (MLPB)
and 100-50-20 (MLPC); logistic regression (LR); and a convolutional neural
network (CNN). In experiments with MNIST and CIFAR-10, the dimensionality is
first reduced with an autoencoder (AE) in all settings except the CNN. We
defer implementation details to Section C.3-C.4.

Considering these five settings enables comparing the methods both for
underparametrized regimes (e.g., LR) and for better performing models (e.g.,
CNN). Note that CP’s guarantees hold regardless of whether the underlying
model is misspecified. Further, observe that most of these models are non-
convex, where the ERM optimization problem does not have a unique solution;
this contradicts the IF assumption (Section 2). Nonetheless, our empirical
results show that ACP works well – it performs better than the other
proposals; in Section 7 we discuss relaxations of this assumption.

###  5.4 Results

For each experiment and method, we report averaged metrics over 100 test
points; we also run statistical tests to check if differences are
(statistically) significant.

##### Prediction set size.

We measure efficiency as the average prediction set size. We report this as a
function of $\varepsilon$, discretized with a step $\Delta\varepsilon=0.01$.
Figures 7(a) and 7(b) show the average prediction set size in MNIST and
CIFAR-10 for MLPC. ACP (deleted and ordinary) consistently outperform all
other methods; deleted is better than ordinary. ACP is significantly more
efficient than RAPS and CV+. SCP and ACP (O) perform similarly on MNIST, but
their difference is remarked on CIFAR-10; this suggests that SCP is a cheap
effective alternative to ACP on relatively easier tasks. Section E.3 reports
results for the rest of the models and for the US Census, showing similar
behavior.

(a) MNIST

(b) CIFAR-10

Figure 7: Average prediction set size as a function of the significance level $\varepsilon$ in MNIST (7(a)) and CIFAR-10 (7(b)) for MLPC. Smaller prediction set size indicates better efficiency.  | US Census
---|---
Model | ACP (D) | ACP (O) | SCP | RAPS | CV+
MLPA | $.301$ | $\mathbf{.281}$ | $.302^{\dagger}$ | $.318^{*\dagger}$ | $.374^{*\dagger}$
MLPB | $.306$ | $\mathbf{.304}$ | $.351^{*\dagger}$ | $.351^{*\dagger}$ | $.377^{*\dagger}$
MLPC | $\mathbf{.273}$ | $.275$ | $.280$ | $.299^{*\dagger}$ | $.324^{*\dagger}$
LR | $.276$ | $.276$ | $.284^{*\dagger}$ | $\mathbf{.183}$ | $.344^{*\dagger}$
| MNIST
Model | ACP (D) | ACP (O) | SCP | RAPS | CV+
MLPA | $\mathbf{.252}$ | $.253$ | $.261$ | $.299^{*\dagger}$ | $.322^{*\dagger}$
MLPB | $\mathbf{.220}$ | $.230$ | $.233$ | $.266^{*\dagger}$ | $.277^{*\dagger}$
MLPC | $\mathbf{.198}$ | $.231$ | $.230^{*}$ | $.258^{*\dagger}$ | $.267^{*\dagger}$
LR | $.385$ | $.386$ | $\mathbf{.379}$ | $.438^{*\dagger}$ | $.467^{*\dagger}$
CNN | $\mathbf{.175}$ | $.182$ | $.237^{*\dagger}$ | $.197^{*\dagger}$ | $.199^{*\dagger}$
| CIFAR-10
Model | ACP (D) | ACP (O) | SCP | RAPS | CV+
MLPA | $1.261$ | $\mathbf{1.259}$ | $1.281^{*\dagger}$ | $1.311^{*\dagger}$ | $1.373^{*\dagger}$
MLPB | $1.385$ | $\mathbf{1.364}$ | $1.397^{\dagger}$ | $1.416^{*\dagger}$ | $1.514^{*\dagger}$
MLPC | $\mathbf{1.226}$ | $1.250$ | $1.327^{*\dagger}$ | $1.377^{*\dagger}$ | $1.475^{*\dagger}$
LR | $\mathbf{1.409}$ | $1.411$ | $1.419$ | $1.436^{*\dagger}$ | $1.476^{*\dagger}$
CNN | $\mathbf{.976}$ | $1.108$ | $1.019$ | $1.110^{*}$ | $1.467^{*\dagger}$
Table 1:  Efficiency AUC ($\varepsilon\in[0,0.2]$). The table indicates that
differences in the AUC are statistically significant as compared to ACP (D)
($*$) and ACP (O) ($\dagger$).

##### Efficiency AUC.

We use an $\varepsilon$-independent metric to aid this comparison: the area
under the curve (AUC) of the prediction set size in the interval
$\varepsilon\in[0,0.2]$; a smaller AUC means better efficiency. ACP (deleted
or ordinary) prevails on all methods, datasets, and model combinations (Table
1). An exception is LR on US Census, where RAPS has a better efficiency than
ACP and SCP; simpler tasks and models may be well served by the
computationally efficient RAPS. Welch one-sided tests (reject with p-value
$<0.1$) confirm that both deleted and ordinary ACP are better than RAPS and
CV+; they further show that either deleted or ordinary ACP are better than SCP
on most tasks. We refer to Section 7 for directions to improve ACP’s
performance.

##### Validity.

As a way of interpreting why ACP performed better than the other methods, we
measure their empirical error rate with a fixed $\varepsilon=0.2$. Indeed,
whilst all methods guarantee a probability of error of at most $\varepsilon$,
a more conservative (i.e., smaller) empirical error may correspond to larger
prediction sets. Table 2 shows the difference between the expected and the
observed error rate on CIFAR-10 (i.e., $\varepsilon-\hat{\varepsilon}$). We
observe that ACP achieves an error rate close to the significance level in
most cases; this indicates this method fully exploits its error margin to
optimize efficiency.222Note a randomized version of full CP, called smooth CP,
ensures the error rate is exactly $\varepsilon$ (instead of “at most
$\varepsilon$”). Herein, we use the standard, conservatively valid definition
per Algorithm 1.  SCP shows a similar behavior. On the other hand, RAPS and
CV+ are more conservative and tend to commit fewer errors. This means that
RAPS and CV+ generate unnecessarily large prediction sets that, despite
including the true label on average, result in lower efficiency. This behavior
is consistent with analogous experiments on the US Census and MNIST datasets.

Model | ACP (D) | ACP (O) | SCP | RAPS | CV+
---|---|---|---|---|---
MLPA | $0.01$ | $0.01$ | $0$ | $0.05$ | $0.09$
MLPB | $0.02$ | $0.03$ | $0.04$ | $0.05$ | $0.13$
MLPC | $-0.01$ | $0$ | $0.02$ | $-0.03$ | $0.09$
LR | $0$ | $0.03$ | $-0.01$ | $0.02$ | $0.04$
CNN | $-0.01$ | $0.01$ | $-0.01$ | $0.04$ | $0.10$
Table 2:  Difference between the expected error ($\varepsilon=0.2$) and the empirical error rate on CIFAR-10. A positive value indicates a conservative prediction set: the method could output tighter prediction sets without losing validity; a negative value is a validity violation, which may be due to statistical fluctuation (100 test points).  | MNIST | CIFAR-10
---|---|---
Model | ACP (D) | ACP (O) | SCP | ACP (D) | ACP (O) | SCP
MLPA | $\mathbf{.057}$ | $.059$ | $.068^{*}$ | $\mathbf{1.796}$ | $1.832$ | $1.849$
MLPB | $\mathbf{.032}$ | $.041$ | $.043^{*}$ | $\mathbf{1.967}$ | $2.050$ | $2.132^{*}$
MLPC | $\mathbf{.012}$ | $.040$ | $.044^{*}$ | $\mathbf{1.728}$ | $1.843$ | $1.878^{*}$
LR | $.187$ | $.189$ | $\mathbf{.183}$ | $\mathbf{2.269}$ | $2.280$ | $2.332$
CNN | $\mathbf{.002}$ | $.002$ | $.002$ | $\mathbf{1.186}$ | $1.645$ | $1.235$
Table 3:  Fuzziness of ACP and SCP on MNIST and CIFAR-10. A smaller fuzziness
corresponds to more efficient prediction sets. The table indicates that
differences in fuzziness are statistically significant as compared to ACP (D)
($*$) and ACP (O) ($\dagger$).

##### P-values fuzziness.

Average prediction set size is a coarse criterion of efficiency: small
variations in the algorithm may lead to substantially different prediction
sets. An alternative efficiency criterion is fuzziness (Vovk et al. 2016),
which measures how p-values distribute in the label space. Of the methods we
considered, fuzziness can only be measured for ACP and SCP (RAPS and CV+ do
not produce p-values). For every test point $x$, and computed p-values
$\\{p_{(x,\hat{y})}\\}_{\hat{y}\in\mathcal{Y}}$, fuzziness is the sum of the
p-values minus the largest p-value:
$\sum_{\hat{y}\in\mathcal{Y}}p_{(x,\hat{y})}-\max_{\hat{y}\in\mathcal{Y}}p_{(x,\hat{y})}$;
a small fuzziness is desirable. In Table 3, we observe that ACP (D) has a
consistently better fuzziness than ACP (O) and SCP. We observe statistical
significance of the results for 3 models in MNIST, and 2 models in CIFAR-10.
Results for the US Census (Appendix D) are similar. As previously observed in
Table 1, SCP performs better in logistic regression (MNIST); this makes it a
good alternative for simpler underlying models.

##  6 Related work

Full CP (Vovk, Gammerman, and Shafer 2005) is notoriously expensive. Many
alternatives have been proposed. Arguably the most prominent are SCP (Vovk,
Gammerman, and Shafer 2005), CV+ (Romano, Sesia, and Candes 2020), RAPS
(Angelopoulos et al. 2020), Cross-CP (Vovk 2012), aggregated CP (Carlsson,
Eklund, and Norinder 2014), APS (Romano, Sesia, and Candes 2020), and the
jackknife (Miller 1974; Efron 1979). We compared ACP with the former three.
Unlike full CP, all the above methods have weaker validity guarantees or they
tend to attain less efficiency.

Cherubin, Chatzikokolakis, and Jaggi (2021) introduced exact optimizations for
full CP for classification. Their method saves an order of magnitude in time
complexity for many models, but is alas only applicable to models supporting
incremental and decremental learning (e.g., k-NN). Crucially, it is unlikely
extendable to neural networks

The closest in spirit to our approach is the Discriminative Jackknife (DJ) by
Alaa and Van Der Schaar (2020), which uses IF to approximate jackknife+
confidence intervals for regression (Barber et al. 2021). We note several
differences between ACP and DJ, besides their different goals (classification
vs regression). While DJ approximates LOO w.r.t. the parameters, we introduce
a direct approach to approximate the nonconformity scores in Equation 4.
Whereas DJ only does decremental learning, which allows them to exploit
Hessian-Vector-Products (Pearlmutter 1994), approximating full CP requires us
to do both incremental and decremental learning (Algorithm 2). We also prove
that our approximation error decreases w.r.t. the size of the training set.

##  7 Conclusion and Future Work

Full CP is a statistically sound method for providing performance guarantees
on the outcomes of ML models. For classification tasks, CP generates
prediction sets which contain the true label with a user-specified
probability. Unfortunately, full CP is impractical to run for more than a few
hundred training points. In this work, we develop ACP, a computationally
efficient method which approximates full CP via influence functions; this
strategy avoids the numerous recalculations that full CP requires. We prove
that ACP is consistent: it approaches full CP as the training set grows. Our
experiments support the use of ACP in practice.

There are many directions to improve ACP. For example, we assumed that the ERM
solution is unique. While our approximation works well in practice, it would
be a fruitful endeavour to relax this assumption; initial work towards this
was done for IF by Koh and Liang (2017). Another direction is to build
nonconformity scores on the studentized scheme, a middle way between deleted
and ordinary (Vovk et al. 2017); this may further improve ACP’s prediction
power. Future work can investigate when 1 holds, and they can try to apply
Theorem 2 to get direct error bounds on the coverage gap.

Finally, while we scale full CP to relatively large models, computing and
inverting the Hessian becomes very expensive as the number of parameters
increases. Recent tools to approximate the Hessian, like the Kronecker-
factored Approximate Curvature (K-FAC) method (Martens and Grosse 2015; Ba,
Grosse, and Martens 2017; Tanaka et al. 2020), might help further scale ACP to
larger models like ResNets.

In conclusion, ACP helps scaling full CP to large datasets and ML models, for
which running full CP would be impractical. Although split-based approaches
like SCP and RAPS are less expensive to run, they do not attain the same
efficiency as ACP. This makes the adoption of our method particularly
appealing for critical real-world applications.

## Acknowledgments

UB acknowledges support from DeepMind and the Leverhulme Trust via the
Leverhulme Centre for the Future of Intelligence (CFI), and from the Mozilla
Foundation. AW acknowledges support from a Turing AI Fellowship under grant
EP/V025279/1, The Alan Turing Institute, and the Leverhulme Trust via CFI. GC
acknowledges support from The Alan Turing Institute. The authors are grateful
to Volodya Vovk, Pang Wei Koh and Manuel Gomez Rodriguez for useful comments
and pointers.

## References

  * Alaa and Van Der Schaar (2020) Alaa, A. M.; and Van Der Schaar, M. 2020.  Discriminative Jackknife: Quantifying Uncertainty in Deep Learning via Higher-Order Influence Functions.  In _Proceedings of the 37th International Conference on Machine Learning_ , ICML’20. JMLR.org.
  * Angelopoulos et al. (2020) Angelopoulos, A. N.; Bates, S.; Jordan, M.; and Malik, J. 2020.  Uncertainty Sets for Image Classifiers using Conformal Prediction.  In _International Conference on Learning Representations_.
  * Ba, Grosse, and Martens (2017) Ba, J.; Grosse, R. B.; and Martens, J. 2017.  Distributed Second-Order Optimization using Kronecker-Factored Approximations.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings_. OpenReview.net.
  * Barber et al. (2021) Barber, R. F.; Candès, E. J.; Ramdas, A.; and Tibshirani, R. J. 2021.  Predictive inference with the jackknife+.  _The Annals of Statistics_ , 49(1): 486 – 507.
  * Basu, Pope, and Feizi (2021) Basu, S.; Pope, P.; and Feizi, S. 2021.  Influence Functions in Deep Learning Are Fragile.  In _International Conference on Learning Representations_.
  * Carlsson, Eklund, and Norinder (2014) Carlsson, L.; Eklund, M.; and Norinder, U. 2014.  Aggregated Conformal Prediction.  In _IFIP Advances in Information and Communication Technology_ , volume 437, 231–240.  ISBN 978-3-319-12567-1.
  * Cherubin, Chatzikokolakis, and Jaggi (2021) Cherubin, G.; Chatzikokolakis, K.; and Jaggi, M. 2021.  Exact Optimization of Conformal Predictors via Incremental and Decremental Learning.  In Meila, M.; and Zhang, T., eds., _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , 1836–1845. PMLR.
  * Ding et al. (2021) Ding, F.; Hardt, M.; Miller, J.; and Schmidt, L. 2021.  Retiring Adult: New Datasets for Fair Machine Learning.  In Beygelzimer, A.; Dauphin, Y.; Liang, P.; and Vaughan, J. W., eds., _Advances in Neural Information Processing Systems_.
  * Efron (1979) Efron, B. 1979.  Bootstrap Methods: Another Look at the Jackknife.  _Annals of Statistics_ , 7: 1–26.
  * Giordano et al. (2019) Giordano, R.; Stephenson, W.; Liu, R.; Jordan, M.; and Broderick, T. 2019.  A swiss army infinitesimal jackknife.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , 1139–1147. PMLR.
  * Hampel (1974) Hampel, F. R. 1974.  The influence curve and its role in robust estimation.  _Journal of the american statistical association_ , 69(346): 383–393.
  * Koh and Liang (2017) Koh, P. W.; and Liang, P. 2017.  Understanding black-box predictions via influence functions.  In _International Conference on Machine Learning_ , 1885–1894. PMLR.
  * Koh et al. (2019) Koh, P. W. W.; Ang, K.-S.; Teo, H.; and Liang, P. S. 2019.  On the accuracy of influence functions for measuring group effects.  In _Advances in Neural Information Processing Systems_ , 5254–5264.
  * Krizhevsky, Nair, and Hinton (2009) Krizhevsky, A.; Nair, V.; and Hinton, G. 2009.  CIFAR-10.
  * LeCun (1998) LeCun, Y. 1998.  The MNIST database of handwritten digits.  _http://yann. lecun. com/exdb/mnist/_.
  * Lei (2019) Lei, J. 2019.  Fast exact conformalization of the lasso using piecewise linear homotopy.  _Biometrika_ , 106(4): 749–764.
  * Lin, Trivedi, and Sun (2021) Lin, Z.; Trivedi, S.; and Sun, J. 2021.  Locally Valid and Discriminative Prediction Intervals for Deep Learning Models.  In Ranzato, M.; Beygelzimer, A.; Dauphin, Y.; Liang, P.; and Vaughan, J. W., eds., _Advances in Neural Information Processing Systems_ , volume 34, 8378–8391. Curran Associates, Inc.
  * Linusson et al. (2014) Linusson, H.; Johansson, U.; Boström, H.; and Löfström, T. 2014.  Efficiency Comparison of Unstable Transductive and Inductive Conformal Classifiers.  In _AIAI Workshops_.
  * Martens and Grosse (2015) Martens, J.; and Grosse, R. 2015.  Optimizing Neural Networks with Kronecker-Factored Approximate Curvature.  In _Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37_ , ICML’15, 2408–2417. JMLR.org.
  * Miller (1974) Miller, R. G. 1974.  The jackknife-a review.  _Biometrika_ , 61: 1–15.
  * Ndiaye (2022) Ndiaye, E. 2022.  Stable Conformal Prediction Sets.  In _International Conference on Machine Learning_ , 16462–16479. PMLR.
  * Ndiaye and Takeuchi (2019) Ndiaye, E.; and Takeuchi, I. 2019.  Computing full conformal prediction set with approximate homotopy.  _Advances in Neural Information Processing Systems_ , 32.
  * Nouretdinov, Melluish, and Vovk (2001) Nouretdinov, I.; Melluish, T.; and Vovk, V. 2001.  Ridge regression confidence machine.  In _ICML_ , 385–392. Citeseer.
  * Papadopoulos et al. (2002) Papadopoulos, H.; Proedrou, K.; Vovk, V.; and Gammerman, A. 2002.  Inductive Confidence Machines for Regression.  In Elomaa, T.; Mannila, H.; and Toivonen, H., eds., _Machine Learning: ECML 2002_. Berlin, Heidelberg: Springer Berlin Heidelberg.
  * Papadopoulos, Vovk, and Gammerman (2011) Papadopoulos, H.; Vovk, V.; and Gammerman, A. 2011.  Regression conformal prediction with nearest neighbours.  _Journal of Artificial Intelligence Research_ , 40: 815–840.
  * Pearlmutter (1994) Pearlmutter, B. A. 1994.  Fast exact multiplication by the Hessian.  _Neural computation_ , 6(1): 147–160.
  * Pedregosa et al. (2011) Pedregosa, F.; Varoquaux, G.; Gramfort, A.; Michel, V.; Thirion, B.; Grisel, O.; Blondel, M.; Prettenhofer, P.; Weiss, R.; Dubourg, V.; Vanderplas, J.; Passos, A.; Cournapeau, D.; Brucher, M.; Perrot, M.; and Duchesnay, E. 2011.  Scikit-learn: Machine Learning in Python.  _Journal of Machine Learning Research_ , 12: 2825–2830.
  * Romano, Sesia, and Candes (2020) Romano, Y.; Sesia, M.; and Candes, E. 2020.  Classification with Valid and Adaptive Coverage.  _Advances in Neural Information Processing Systems_ , 33: 3581–3591.
  * Shafer and Vovk (2008) Shafer, G.; and Vovk, V. 2008.  A tutorial on conformal prediction.  _Journal of Machine Learning Research_ , 9(Mar): 371–421.
  * Tanaka et al. (2020) Tanaka, H.; Kunin, D.; Yamins, D. L.; and Ganguli, S. 2020.  Pruning neural networks without any data by iteratively conserving synaptic flow.  In Larochelle, H.; Ranzato, M.; Hadsell, R.; Balcan, M.; and Lin, H., eds., _Advances in Neural Information Processing Systems_ , volume 33, 6377–6389. Curran Associates, Inc.
  * Vovk (2012) Vovk, V. 2012.  Cross-conformal predictors.  _Annals of Mathematics and Artificial Intelligence_ , 74.
  * Vovk et al. (2016) Vovk, V.; Fedorova, V.; Nouretdinov, I.; and Gammerman, A. 2016.  Criteria of efficiency for conformal prediction.  In _Symposium on conformal and probabilistic prediction with applications_ , 23–39. Springer.
  * Vovk, Gammerman, and Shafer (2005) Vovk, V.; Gammerman, A.; and Shafer, G. 2005.  _Algorithmic learning in a random world_.  Springer Science & Business Media.
  * Vovk et al. (2017) Vovk, V.; Shen, J.; Manokhin, V.; and Xie, M.-g. 2017.  Nonparametric predictive distributions based on conformal prediction.  In _Conformal and Probabilistic Prediction and Applications_ , 82–102. PMLR.

##  Appendix A Additional information about ACP

###  A.1 Ordinary Full CP and ACP

1: for $x$ in test points do

2: for $\hat{y}\in\mathcal{Y}$ do

3: $\hat{z}=(x,\hat{y})$

4:
$\theta_{Z\cup\\{\hat{z}\\}}=\operatorname*{argmin}\limits_{\hat{\theta}\in\Theta}R(Z\cup\\{\hat{z}\\},\hat{\theta})$

5: for $z_{i}\in Z\cup\\{\hat{z}\\}$ do

6: $\alpha_{i}=\ell(z_{i},\theta_{Z\cup\\{\hat{z}\\}})$

7: end for

8:
$p_{(x,\hat{y})}=\frac{\text{\\#}\\{i=1,...,N+1\,:\,\alpha_{i}\geq\alpha_{N+1}\\}}{N+1}$

9: If $p_{(x,\hat{y})}>\varepsilon$, include $\hat{y}$ in prediction set
$\Gamma^{\varepsilon}_{x}$

10: end for

11: end for

Algorithm 3 Full CP - Ordinary

Algorithm 3 shows the Full CP algorithm constructed for a nonconformity
measure defined on an ordinary scheme. ACP with the ordinary prediction can be
defined similarly to the deleted one as follows. Once again, we can use the
direct or indirect approach.

##### Indirect approach.

Let
$\tilde{\theta}_{Z\cup\\{\hat{z}\\}}\equiv\theta_{Z}+I_{\theta_{Z}}(\hat{z})$.
Then:

$\alpha_{i}\approx\ell(z_{i},\tilde{\theta}_{Z\cup\\{\hat{z}\\}})\,.$ (5)

##### Direct approach.

$\displaystyle\alpha_{i}$
$\displaystyle\approx\tilde{\ell}(z_{i},\theta_{Z\cup\\{\hat{z}\\}})$
$\displaystyle\equiv\ell(z_{i},\theta_{Z})+I_{\ell}(z_{i},\hat{z})$ (6)

Observe that the only difference w.r.t. ACP (deleted) is that here we only
need to add the influence of $\hat{z}$; that is, we do not need to remove the
influence of $z_{i}\in Z\cup\\{\hat{z}\\}$. This spares the very costly LOO
procedure of retraining the model, which makes this method significantly more
computationally efficient.

###  A.2 Time complexity: Full CP Vs ACP

Predicting $m$ test points via full CP in an $l$-label classification setting
costs $\mathcal{O}(nlm(T_{n}+P))$, where $T_{n}$ is the cost of training a
model on $n$ training points, and $P$ is the cost of making a prediction with
it.

The ACP procedure is split into two steps: training and prediction. Training
costs $\mathcal{O}(T_{n}+H_{n}+n(G_{n}+P))$, where $H_{n}$ and $G_{n}$ are the
costs of computing the Hessian inverse and a gradient, respectively. We denote
the dependency on the training set size with the subscript $n$. Computing a
prediction for $m$ points costs $\mathcal{O}(lm(G_{n}+nI_{n}+P))$, where
$I_{n}$ is the (usually small) cost of computing the influence; this gives an
order speed-up over CP.

| Train | Predict
---|---|---
Full CP | N/A | $nlm(T_{n}+P)$
ACP | $T_{n}+H_{n}+n(G_{n}+P)$ | $lm(G_{n}+nI_{n}+P)$
Table 4: Time complexities for full CP and ACP.

As an illustrative example, let us assume a standard classification problem
with $l$ labels, a training set with size $N$, and a smaller test set $M$,
where we fit a 3-layers neural network. The full CP algorithm would retrain
the model $l\times N$ times per each test point in $M$. This is infeasible for
relatively large datasets with, e.g., more than $1000$ points, either in the
training or the test set. Conversely, ACP only needs to train the model once,
compute the Hessian inverse and the $N$ gradients (training step). Although
inverting the Hessian requires $\mathcal{O}(W^{3})$ operations, this is
expected to be significantly faster than full CP’s retraining procedure for
this standard scenario. ACP only needs access to the gradient of the test
point to inexpensively compute the IF (prediction step).

We measured the running times in the synthetic dataset (Appendix C) with 50
features, 1000 training points, and 100 test points. As indicative figures,
running full CP in this setting took approximately 5 days, whereas ACP took
less than 1 hour (CPU times with an Intel Core i7-8750H).

###  A.3 Space complexity

ACP requires storing the Hessian inverse, i.e., $\mathcal{O}(W^{2})$ with $W$
being the number of parameters, and one gradient per training point, i.e.,
$\mathcal{O}(nW)$. Full CP stores the full training set.

###  A.4 Additional discussion on the nonconformity score

Any nonconformity measure
$A:(\mathcal{X}\times\mathcal{Y})\times(\mathcal{X}\times\mathcal{Y})^{N}\rightarrow\mathbf{R}$
defines a conformal predictor (CP); given an example $x\in\mathcal{X}$ and a
significance level $\varepsilon$, this predictor generates a set that contains
the true label $y\in\mathcal{Y}$ with probability $1-\varepsilon$. The
intuition here is that $y$ will have a value that makes the pair $(x,y)$
conform with the previous examples; the validity is therefore conditioned on
the training set. The nonconformity score is simply a measure of how different
a new example is from old examples. In a general setting, the nonconformity
measure is arbitrary; the validity guarantees always hold, e.g., a random
score will still generate valid prediction sets, although likely with low
efficiency. Whether a function $A$ is an appropriate nonconformity score will
always be open to discussion since it greatly depends on the context (Vovk,
Gammerman, and Shafer 2005).

ACP (Algorithm 2) restricts the nonconformity score to be the loss at a point.
Although the instance-wise loss might be suboptimal, the underlying algorithm
is arbitrary. Shafer and Vovk (2008) point out that the score choice is
relatively unimportant and that the critical step in the CP framework is
determining the underlying classifier. It is therefore not expected that ACP
degrades its efficiency by using the loss as score as long as the wrapped
classifier is appropriate.

##  Appendix B Proofs

###  B.1 ACP consistency

We first declare the following set of assumptions introduced and thoroughly
discussed by Giordano et al. (2019).

######  Assumption 1.

  * •

For all $\theta\in\Theta$ and all $z_{i}\in Z$,
$\nabla_{\theta}\ell(z_{i},\theta)$ is continuously differentiable in
$\theta$.

  * •

For all $\theta\in\Theta$, the Hessian $H_{\theta}$ is non-singular with
$\sup_{\theta\in\Theta}||H_{\theta}^{-1}||_{op}<\infty$.

  * •

$\exists$ finite constants $C_{g},C_{h}$ s.t.
$\sup\limits_{\theta\in\Theta}\frac{1}{\sqrt{N}}||\nabla_{\theta}\ell(z,\theta)||_{2}\leq
C_{g}$ and
$\sup\limits_{\theta\in\Theta}\frac{1}{\sqrt{N}}||\nabla^{2}_{\theta}\ell(z,\theta)||_{2}\leq
C_{h}$.

  * •

Let $h(\theta)=\nabla^{2}_{\theta}\ell(z,\theta)$. There exists
$\Delta_{\theta}>0$ and a finite constant $L_{h}$ such that
$||\theta-\theta_{Z}||_{2}\leq\Delta_{\theta}$ implies that
$\frac{||h(\theta)-h(\theta_{Z})||_{2}}{\sqrt{N}}\leq
L_{h}||\theta-\theta_{Z}||_{2}$.

To prove Theorem 2 we exploit the following result by Giordano et al. (2019):
Let
$\tilde{\theta}_{Z\setminus\\{z_{i}\\}}=\theta_{Z}-I_{\theta}(z_{i},z_{i})$ be
the approximation of $\theta_{Z\setminus\\{z_{i}\\}}$ obtained from Equation
1.

######  Theorem 4 (Consistency of $\tilde{\theta}_{Z\setminus\\{z_{i}\\}}$
(Giordano et al. 2019)).

Under 1, for every $N$ there is a constant $C$ s.t., for every $z_{i}\in Z$:

$\displaystyle||\tilde{\theta}_{Z\setminus\\{z_{i}\\}}-\theta_{Z\setminus\\{z_{i}\\}}||_{2}$
$\displaystyle\leq C\frac{||g||^{2}_{\infty}}{N^{2}}$ $\displaystyle\leq
C\frac{\max\\{C_{g},C_{h}\\}^{2}}{N}$

(Note, the result by Giordano et al. is stated more generally for the case of
leave $k$ out; we only report its LOO version. Also, the general case requires
2 further assumptions, which we omit as they are always satisfied for LOO.)

We now restate and prove the consistency of ACP.

See 2

###### Proof.

First, from Theorem 4 (Giordano et al. 2019) we have that, for every $N$ there
exists constants $C$ and $C^{\prime}$ such that:

$\displaystyle||\theta_{Z\cup\\{\hat{z}\\}}-I_{\theta}(z_{i})-\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}}||_{2}\leq
C\frac{\max\\{C_{g},C_{h}\\}^{2}}{N}$
$\displaystyle||\theta_{Z\cup\\{\hat{z}\\}}-I_{\theta}(\hat{z})-\theta_{Z}||_{2}\leq
C^{\prime}\frac{\max\\{C_{g},C_{h}\\}^{2}}{N}\,;$

observe that the second expression is obtained by removing $\hat{z}$ from the
training data of a model trained on $Z\cup\\{\hat{z}\\}$.

Fix $z_{i}\in Z\cup\\{\hat{z}\\}$.

$\displaystyle|\tilde{\ell}(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})-\ell(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})|$
$\displaystyle\leq|\ell(z_{i},\tilde{\theta}_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})-\ell(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})|$
$\displaystyle=|\ell(z_{i},\tilde{\theta}_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})-\ell(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})|$
$\displaystyle\leq
K||\tilde{\theta}_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}}-\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}}||_{2}$
$\displaystyle=K||\theta_{Z}+I_{\theta}(\hat{z})-I_{\theta}(z_{i})-\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}}||_{2}$
$\displaystyle\leq
K||\theta_{Z\cup\\{\hat{z}\\}}-I_{\theta}(z_{i})-\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}}||_{2}+||\theta_{Z\cup\\{\hat{z}\\}}-I_{\theta}(\hat{z})-\theta_{Z}||_{2}$
$\displaystyle\leq K(C+C^{\prime})\frac{\max\\{C_{g},C_{h}\\}^{2}}{N}$

First step applies 1, third step uses Lipschitz continuity, fourth step uses
triangle inequality, and the final step uses Theorem 4. ∎

###  B.2 Dependence on the regularization parameter $\lambda$

Our result on the effect of the regularization parameter on the approximation
error of ACP (Theorem 3) is an extension of a result by Koh et al. (2019) on
the approximation error of IF for LOO.

#### Background on result by Koh et al. (2019)

The LOO loss can be written as

$\ell(z_{i},\theta_{Z\setminus\\{z_{i}\\}})=\ell(z_{i},\theta_{Z})-I_{\ell}^{*}(z_{i},z_{i})\approx\ell(z_{i},\theta_{Z})-I_{\ell}(z_{i},z_{i})\,,$

where $I_{\ell}^{*}(z_{i},z_{i})$ is defined to be the true influence of
training point $z_{i}\in Z$ on the loss of the model at $z_{i}$. For
simplicity, we omit the arguments of $I_{\ell}$ when clear from the context.
In the following, we assume $\theta$ is the minimizer of an ERM problem with
regularization parameter $\lambda$.

Koh et al. (2019) decompose the influence function error into Newton-actual
error ($E_{A}$) and Newton-influence error ($E_{I}$):

$I^{*}_{\ell}-I_{\ell}=E_{A}+E_{I}$

with $E_{A}\equiv I_{\ell}^{*}-I_{\ell}^{\mathcal{N}}$, and $E_{I}\equiv
I_{\ell}^{\mathcal{N}}-I_{\ell}$ . Here $I_{\ell}^{\mathcal{N}}$ is the Newton
approximation of the true influence $I_{\ell}^{*}$.

Koh et al. (2019) show that $E_{A}$ decreases with
$\mathcal{O}(\frac{1}{\lambda^{3}})$, and they observed that its value tends
to be negligible in practice.

######  Proposition 5 (Koh et al. (2019)).

Assume that $\ell$ is $C_{f}$-Lipschitz and that the Hessian is
$C_{H}$-Lipschitz. Further, assume the third derivative of $\ell$ exists and
that it is bounded in norm by $C_{f,3}$. The influence on the self-loss is
such that:

$I_{\ell}(z_{i})+E_{f,3}\leq
I^{\mathcal{N}}_{\ell}(z_{i})\leq\left(1+\frac{3\sigma_{max}}{2\lambda}+\frac{\sigma_{max}^{2}}{2\lambda^{2}}\right)I_{\ell}(z_{i})+E_{f,3}(z_{i})\,.$

Furthermore:

$|E_{f,3}(z_{i})|\leq\frac{C_{f,3}C^{3}_{\ell}}{6(\sigma_{min}+\lambda)^{3}}\,.$

#### Extension to ACP

If we assume $E_{A}$ to be negligible, we obtain that $I^{*}_{\ell}\approx
I^{\mathcal{N}}_{\ell}$. Further, ignoring $O(\lambda^{-3})$ terms,
Proposition 5 gives:

$I_{\ell}\leq I^{*}_{\ell}\leq g(\lambda)I_{\ell}\,,$

that is (by subtracting each term from $\ell(z_{i},\theta_{Z})$):

$\ell(z_{i},\theta_{Z})-g(\lambda)I_{\ell}(z_{i},z_{i})\leq\ell(z_{i},\theta_{Z\setminus\\{z_{i}\\}})\leq\ell(z_{i},\theta_{Z})-I_{\ell}(z_{i},z_{i})=\tilde{\ell}(z_{i},\theta_{Z\setminus\\{z_{i}\\}})\,.$

Note, however, that this result only applies to the LOO loss. We use the
following simplifying assumption to extend the above result to ACP.

######  Assumption 2.

For all $z_{i}$ and $\hat{z}$:

$I^{*}_{\ell}(z_{i},\hat{z})\approx I_{\ell}(z_{i},\hat{z})$

We can now restate and prove our result.

See 3

###### Proof.

Koh et al. show that (ignoring $O(\lambda^{-3})$ terms):

$I_{\ell}(z_{i})\leq
I^{\mathcal{N}}_{\ell}(z_{i})\leq\left(1+\frac{3\sigma_{max}}{2\lambda}+\frac{\sigma_{max}^{2}}{2\lambda^{2}}\right)I_{\ell}(z_{i})\,.$

(For a definition of all the terms please refer to Section B.2.) Ignoring
$O(\lambda^{-3})$ terms, we apply this to the loss:

$\ell(z_{i},\theta_{Z})-g(\lambda)I_{\ell}(z_{i},z_{i})\leq\ell(z_{i},\theta_{Z\setminus\\{z_{i}\\}})\leq\ell(z_{i},\theta_{Z})-I_{\ell}(z_{i},z_{i})$

We apply this to the augmented training set $Z\cup\\{\hat{z}\\}$ (now $z_{i}$
ranges in $Z\cup\\{\hat{z}\\}$):

$\ell(z_{i},\theta_{Z\cup\\{\hat{z}\\}})-g(\lambda)I_{\ell}(z_{i},z_{i})\leq\ell(z_{i},\theta_{Z\cup\\{\hat{z}\\}\setminus\\{z_{i}\\}})\leq\ell(z_{i},\theta_{Z\cup\\{\hat{z}\\}})-I_{\ell}(z_{i},z_{i})\,.$

By using Assumption 2, replace $\ell(z_{i},\theta_{Z\cup\\{\hat{z}\\}})$ with
$\ell(z_{i},\theta_{Z})+I_{\ell}(z_{i},\hat{z})$. This concludes the proof. ∎

##  Appendix C Experimental details

###  C.1 Synthetic data (Section 4)

We generate synthetic data for a binary classification problem using scikit-
learn’s make_classification() (Pedregosa et al. 2011). We sample points from
four Gaussian-distributed clusters (two per class).

###  C.2 Real data (Section 5)

Follows a brief description of the datasets we used and of their pre-
processing.

  * •

MNIST: we use 60,000 images for training and 10,000 for testing from the MNIST
dataset (LeCun 1998) – from which we take the first 100 test points. The 28×28
grayscale images represent handwritten digits between 0 and 9. In all settings
except the CNN, these images are standardized in the interval $[0,1]$ by
dividing the pixel intensities by $255$.

  * •

CIFAR-10: we use 50,000 images for training and 10,000 for testing from the
CIFAR-10 dataset (Krizhevsky, Nair, and Hinton 2009) – from which we take the
first 100 test points. These correspond to images from 10 mutually exclusively
classes. We also standardize them in the interval $[0,1]$ (except in setting
CNN).

  * •

US Census: we use the ACSIncome data for the state of New York from the US
Census dataset (Ding et al. 2021). Each data point represents an individual
above the age of 16, who reported usual working hours of at least 1 hour per
week in the past year, and an income of at least $100. Ten features
characterize each point, and the task consists of predicting whether the
individual’s income is above $50,000. We split the dataset of 103,021 points
and keep the 90% (92,718) for training. We take 100 test points from the
remaining.

###  C.3 Implementation details

We use dense layers with Rectified Linear Units (ReLU) as nonlinear activation
functions in all the models. Settings MLPA, MLPB and MLPC are based on
multilayer perceptrons with different widths and depths, LR uses logistic
regression, and CNN a convolutional neural network. All models are trained
with Adam for a maximum of 200 epochs. We fix a learning rate of 0.001,
minibatches of size 100, and an early stopping based on a 20% validation
split. We also set a regularization $\lambda=10^{-5}$. We use a cross-entropy
loss function.

We use an autoencoder (AE) to reduce the dimensionality of MNIST and CIFAR-10
for settings MLPA, MLPB, MLPC, and LR. The AE uses a symmetric encoder-decode
architecture with two dense layers of 128 and 64 neurons, separated by dropout
with $p=0.2$ and ReLU activations.

We now give specific details of each setting:

  * •

MLPA: two layers, the first with 20 and the second with 10 neurons. The
embedding size for the AE is 8.

  * •

MLPB: one layer with 100 neurons. Embedding size of 16.

  * •

MLPC: three layers with 100, 50, and 20 neurons. Embedding size of 32.

  * •

LR: embedding size of 8.

  * •

CNN: two convolutional layers with 16 and 32 kernels of size 5, respectively.
They include a ReLU activation and max-pool layer with kernel size 4. A
multilayer-perceptron makes the classification.

###  C.4 Design choices for the methods

Here we comment on some design choices that we made when including the
competing methods.

  * •

SCP: we fix a calibration split of 20%, as advised in (Linusson et al. 2014).
We obtain the nonconformity scores by fitting the model in the proper training
set and computing the loss for the calibration data.

  * •

RAPS: we fix a calibration split of 20%. We use the randomized version of the
algorithm, and we do not allow zero sets (i.e., we use the default version in
(Angelopoulos et al. 2020)). The randomized version, although slightly
unstable, provides a less conservative coverage. The parameters “kreg” and
“lamda” are picked in an optimal fashion that minimizes the prediction set
size. We therefore compare ACP to the most efficient version of RAPS.

  * •

CV+: we set $K=5$ as the number of folds for the cross-validation.

For ACP, we add a damping term of $\lambda=0.01$ to the Hessian to enforce
positive eigenvalues. This is equivalent to an l2-regularisation.

##  Appendix D Fuzziness comparison

Table 5 shows the fuzziness of ACP and SCP on the US Census dataset. Results
match the behavior observed for MNIST and CIFAR-10 (Section 5).

| US Census
---|---
Model | ACP (D) | ACP (O) | SCP
MLPA | $.1086$ | $\mathbf{.0844}$ | $.1121^{\dagger}$
MLPB | $\mathbf{.1144}$ | $.1366$ | $.2173^{*}$
MLPC | $\mathbf{.0733}$ | $.0768$ | $.0741$
LR | $\mathbf{.0781}$ | $.0782$ | $.0885$
Table 5: Fuzziness of ACP and SCP on US Census. A smaller fuzziness
corresponds to more efficient prediction sets.
∗Differences in the fuzziness are statistically significant compared to ACP
(D). †Differences are significant compared to ACP (O).

##  Appendix E Further results

###  E.1 Additional experiments with synthetic data

We run additional experiments on synthetic data to further support the theory
in Section 3.2. Specifically, we show how ACP’s p-values approximate Full CP’s
as the training set increases, for different numbers of features and
regularization strengths. We also compute the Kendall tau distance between the
p-values rankings.

Figure 8: Additional experiments on synthetic data. We further support that
ACP generates the same p-values as full CP as the training set increases.

###  E.2 Additional motivating examples

We include additional motivating examples with specific instances from
CIFAR-10 and MNIST for setting MLPC.

$\varepsilon=0.2$ Method Prediction set ACP (D) bird, cat, deer, frog ACP (O)
bird, cat, deer, frog SCP bird, deer, frog RAPS bird, cat, deer, dog, frog CV+
bird, cat, deer, dog, frog

Figure 9: Prediction set size as a function of $\varepsilon$ for a specific
instance from CIFAR-10. We indicate with a star the point ($\varepsilon$) at
which each method starts containing the true label. ACP (D) and ACP (O) are
the fastest, meaning that they include the true label earlier than the rest of
methods (i.e., at higher $\varepsilon$). For a typical significance
$\varepsilon=0.2$, the prediction sets generated by both methods are the
smallest that contain the true label. RAPS and CV+ are more conservative,
while SCP fails to include it.

$\varepsilon=0.2$ Method Prediction set ACP (D) auto, cat, frog, horse, truck
ACP (O) auto, cat, frog, horse, truck SCP auto, deer, frog, truck RAPS plane,
auto, bird, deer, frog, ship, truck CV+ plane, auto, deer, frog, horse, truck

Figure 10: Additional motivating example in CIFAR-10. For a typical
significance $\varepsilon=0.2$, ACP (D) and ACP (O) yield the smallest
prediction sets that contain the true label. ACP (D) and ACP (O) are the first
to consider the true label.

$\varepsilon=0.2$ Method Prediction set ACP (D) cat, deer, frog, horse ACP (O)
cat, deer, frog, horse SCP cat, deer, dog, frog, horse, truck RAPS cat, deer,
dog, frog, horse, truck CV+ cat, deer, dog, frog, horse

Figure 11: Additional motivating example in CIFAR-10. For a typical
significance $\varepsilon=0.2$, all methods include the true label, ACP (D)
and ACP (O) yielding the smallest prediction sets. ACP (D) and ACP (O) are the
first to consider the true label.

$\varepsilon=0.01$ Method Prediction set ACP (D) 7 ACP (O) 7 SCP 4, 7, 8 RAPS
4, 7, 8 CV+ 1, 7

Figure 12: Additional motivating example in MNIST. For a typical significance
$\varepsilon=0.01$, all methods include the true label, ACP (D) and ACP (O)
yielding the smallest prediction sets. ACP (D) and ACP (O) are also the first
to consider the true label.

$\varepsilon=0.01$ Method Prediction set ACP (D) 2 ACP (O) 1, 2, 3, 5, 6, 7,
8, 9 SCP 1, 2, 7 RAPS 1, 2, 6, 7 CV+ 2, 3, 6

Figure 13: Additional motivating example in MNIST. For a typical significance
$\varepsilon=0.01$, all methods include the true label, ACP (D) yielding the
smallest prediction sets. ACP (D) is the first method to consider the true
label, followed by CV+. ACP (O) builds the largest set and is the slowest to
consider the true label.

###  E.3 Additional curves

Figure 14 plots the average prediction set size w.r.t the significance
$\varepsilon$ for all combinations of settings (MLPA, MLPB, MLPC, LR, CNN) and
datasets (MNIST, CIFAR-10, US Census).

MNIST (MLPA)

MNIST (MLPA)

CIFAR (MLPA)

CIFAR (MLPA)

US Census (MLPA)

US Census (MLPA)

MNIST (MLPB)

MNIST (MLPB)

CIFAR (MLPB)

CIFAR (MLPB)

US Census (MLPB)

US Census (MLPB)

MNIST (MLPC)

MNIST (MLPC)

CIFAR (MLPC)

CIFAR (MLPC)

US Census (MLPC)

US Census (MLPC)

MNIST (LR)

MNIST (LR)

CIFAR (LR)

CIFAR (LR)

US Census (LR)

US Census (LR)

MNIST (CNN)

MNIST (CNN)

CIFAR (CNN)

CIFAR (CNN)

Figure 14: Average prediction set size w.r.t the significance level
$\varepsilon$ for all settings and datasets. We show both the full curve and
the corresponding to the interval of interest $\varepsilon\in[0,0.2]$