Locally Valid and Discriminative Prediction Intervals for Deep Learning Models
Year: 2021

Abstract:
Crucial for building trust in deep learning models for critical real-world applications is efficient and theoretically sound uncertainty quantification, a task that continues to be challenging. Useful uncertainty information is expected to have two key properties: It should be valid (guaranteeing coverage) and discriminative (more uncertain when the expected risk is high). Moreover, when combined with deep learning (DL) methods, it should be scalable and affect the DL model performance minimally. Most existing Bayesian methods lack frequentist coverage guarantees and usually affect model performance. The few available frequentist methods are rarely discriminative and/or violate coverage guarantees due to unrealistic assumptions. Moreover, many methods are expensive or require substantial modifications to the base neural network. Building upon recent advances in conformal prediction [13, 33] and leveraging the classical idea of kernel regression, we propose Locally Valid and Discriminative prediction intervals (LVD), a simple, efficient and lightweight method to construct discriminative prediction intervals (PIs) for almost any DL model. With no assumptions on the data distribution, such PIs also offer finite-sample local coverage guarantees (contrasted to the simpler marginal coverage). We empirically verify, using diverse datasets, that besides being the only locally valid method for DL, LVD also exceeds or matches the performance (including coverage rate and prediction accuracy) of existing uncertainty quantification methods, while offering additional benefits in scalability and flexibility.

text: Crucial for building trust in deep learning models for critical real-world applications is efficient and theoretically sound uncertainty quantification, a task that continues to be challenging. Useful uncertainty information is expected to have two key properties: It should be valid (guaranteeing coverage) and discriminative (more uncertain when the expected risk is high). Moreover, when combined with deep learning (DL) methods, it should be scalable and affect the DL model performance minimally. Most existing Bayesian methods lack frequentist coverage guarantees and usually affect model performance. The few available frequentist methods are rarely discriminative and/or violate coverage guarantees due to unrealistic assumptions. Moreover, many methods are expensive or require substantial modifications to the base neural network. Building upon recent advances in conformal prediction [13, 33] and leveraging the classical idea of kernel regression, we propose Locally Valid and Discriminative prediction intervals (LVD), a simple, efficient and lightweight method to construct discriminative prediction intervals (PIs) for almost any DL model. With no assumptions on the data distribution, such PIs also offer finite-sample local coverage guarantees (contrasted to the simpler marginal coverage). We empirically verify, using diverse datasets, that besides being the only locally valid method for DL, LVD also exceeds or matches the performance (including coverage rate and prediction accuracy) of existing uncertainty quantification methods, while offering additional benefits in scalability and flexibility.

heading: 1 Introduction
text: Consider a training set Strain = {(Xi, Yi)}Ni=1 and a test example (XN+1, YN+1), all drawn i.i.d from an arbitrary joint distribution P , with (Xi, Yi) ∈ X × Y for some X ⊆ Rd and Y ⊆ R. We are interested in the problem of predictive inference: On observing Strain and XN+1, our task is to construct a prediction interval (PI) 1 estimate Ĉ(XN+1) that contains the true value of YN+1 with a (pre-specified) high probability.
1Several recent deep learning papers use “Confidence Interval” and “Prediction Interval” interchangeably. We stick to the conventional statistical usage.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
The construction of actionable PIs involves two general challenges: First, Ĉ should be valid, meaning that if the specified probability is 1− α, we expect Ĉ(XN+1) to cover YN+1 at least 1− α of the time. Moreover, Ĉ should be discriminative i.e., we expect Ĉ(XN+1) to be narrower for confident cases and vice-versa. The width of the PI Ĉ(XN+1) is thus quantification of the uncertainty. Figure 1 illustrates these notions, with more details in Section 2.2 and 2.3.
While deep learning (DL) models have demonstrated impressive performance over a range of complicated tasks and data modalities, it has remained difficult to quantify the uncertainty for their predictions. For DL predictions to be actionable, uncertainty information is however indispensable, especially in domains like medicine and finance [2]. Apart from requiring validity and discrimination as discussed earlier, two additional challenges exist specifically for DL models. Obviously, any uncertainty estimation method needs to finish reasonably fast to be useful, so the third challenge is scalability. The fourth challenge is accuracy: The uncertainty estimation should not decrease the prediction accuracy of the DL model. Post-hoc methods are ideal because they usually do not interfere with the base NN prediction at all. These four requirements together constitute a set of essential desiderata for uncertainty quantification in DL.
Existing uncertainty estimation methods for DL rarely address more than one or two of the above requirements. Credible intervals given by posteriors of approximate Bayesian methods such as [43, 15], deep ensemble [20, 44] and Monte-Carlo dropout [12] are not valid in the frequentist sense [7]. Most existing methods also interfere with the original model design, loss function and/or training, which could be expensive and decrease the model performance (as verified in our experiments) [12, 1, 7, 20].
To address these requirements, we leverage recent advances in conformal prediction and the classical idea of kernel regression. Conformal prediction, pioneered by Vovk [40], is a powerful approach for constructing valid PIs. The most popular split conformal methods usually leverage prediction errors from a hold-out set to construct Ĉ(XN+1), which would be valid if a future data point (XN+1, YN+1) follows the same distribution as data in the hold-out set. This framework is particularly suitable for deep learning due to its distribution-free nature, and has motivated many recent uncertainty quantification efforts in deep learning for both classification and regression tasks [1, 23, 3, 11]. However, most conformal methods are only marginally valid [25, 40, 21, 4]. Moreover, less-thanmeticulous applications to DL can break distributional assumptions and theoretical validity, as in the case of [1] (see discussion in Appendix). We however seek to construct a PI conditioning on the input (similar to the third PI in Fig. 1). Some recent advances ([13, 33]) examine the possibility of “approximately” conditionally valid PIs. While these methods cannot be directly applied to DL due to efficiency and performance considerations, their methodological and theoretical contributions serve as major inspirations for us to develop a highly flexible and practical method.
Summary of Contributions: We propose Locally Valid Discriminative Prediction Intervals (LVD), a simple uncertainty estimation method for deep learning which combines recent advances in conformal prediction and the classical idea of kernel regression. LVD applies to almost all DL models, and is the first method that satisfies all four aforementioned requirements: • Validity: LVD has frequentist coverage guarantee (not just marginal, but approximately conditional).
• Discrimination: The width of the PIs given by LVD adapts to the risk/uncertainty level of XN+1. • Scalability: LVD is lightweight, adding limited overhead to the base DL model. • Accuracy: LVD is post-hoc without requiring model retraining, and does not affect the base
performance of the DL model. We must note that while the theoretical foundation for guaranteeing "validity" is mostly based on [13], LVD addresses several challenges to satisfy the other three requirements. The code to replicate all our results can be found at https://github.com/zlin7/LVD.

heading: 2 Preliminaries

heading: 2.1 Learning Setup and Assumptions
text: We assume data and response pairs (X,Y ) ∈ X × Y have a joint distribution denoted P , with the marginal distributions of Y and X and the conditional distribution Y |X denoted as PY , PX , and PY |X , respectively. Further, we will define Zi := (Xi, Yi) for concision. Assuming that we already have an algorithm (with all the training protocols folded in), such as a Deep Neural Network (DNN), that provides a mean estimator µ̂NN (x) : X 7→ Y . Given a target coverage level 1− α ∈ (0, 1), our task is to also construct a prediction interval estimator function Ĉα(x) : X 7→ {subset of Y} that has the validity and discrimination properties as defined below.

heading: 2.2 Validity (Frequentist Coverage)
text: There are several (related) notions for a PI to be valid – marginal, conditional, and local. Given target level 1−α, we say Ĉα has the marginal coverage guarantee (or, equivalently, is marginally valid) if
P{YN+1 ∈ Ĉα(XN+1)} ≥ 1− α (1) where the probability is taken over the training data and (the unseen) (XN+1, YN+1).
A limitation of marginal coverage is that it is not conditioned on XN+1. A more desirable, albeit stronger, property would be conditional coverage at 1− α:
P{YN+1 ∈ Ĉα(XN+1)|XN+1 = x} ≥ 1− α for almost all x ∈ X . (2) Here the probability is taken over the training data and YN+1 (with XN+1 fixed). It is thus clear that conditional coverage implies marginal coverage but not the other way around. Indeed, a Ĉα with marginal coverage property only implies a 1 − α chance of being accurate on average across all data points (marginalizing over XN+1) i.e. there might be a sub-population in the data for which the coverage is completely missed. Unfortunately, it is impossible to achieve distribution-free finitesample conditional coverage (Eq. 2) in a non-trivial way. Indeed, it is known that a finite-sample estimated Ĉα(x) cannot achieve conditional coverage, unless it produces infinitely wide prediction intervals in expectation under any non-discrete distribution P [39, 22, 5]. It is thus reasonable to instead seek approximate conditional coverage. As might be apparent, there is considerable freedom in defining an appropriate notion of “approximate”, depending on specific tasks and domains. However, a sufficiently general-purpose and natural notion involves using a kernel function K : X × X 7→ R and a center x′ ∈ X , like the relaxation given in [33]:∫
P{YN+1 ∈ Ĉα(x′)|XN+1 = x}K(x, x′)dPX(x)∫ K(x, x′)dPX(x) ≥ 1− α (3)
with the probability (P in the integral) taken over all training samples and YN+1, with (XN+1, YN+1) ∼ P̃ = P̃X × PY |X . Here P̃X is just the distribution re-weighted by the kernel with a center x′, defined by dP̃X(x)dx ∝ dPX(x) dx K(x
′, x). Instead of choosing x′ beforehand, if we let the center be XN+1 and fold the integral into P like in [13], we arrive at the definition of local coverage:
P{ỸN+1 ∈ Ĉα(XN+1)|XN+1 = x′} ≥ 1− α. (4)
Here the probability integrates over all training data and an additional (X̃N+1, ỸN+1) ∼ P̃ defined above. Intuitively, this definition means Ĉα(XN+1) is valid “on average” within a small neighborhood
of XN+1. Note that Eqs. 1 and 2 reduce to Eq. 4 with K being constant and delta functions, respectively. In the rest of the paper, we will call Ĉα marginally/conditionally/locally valid if it satisfies Eq. 1/2/4 respectively, and we will pursue finite-sample local validity.

heading: 2.3 Discrimination
text: The idea of discrimination is simple: If the error of our prediction µ̂(x) is high for an input x, the PI should be wide, and vice versa. Formally, following [1], we require
E[W (Ĉ(x))] ≥ E[W (Ĉ(x′))]⇔ E[`(y, µ̂(x))] ≥ E[`(y′, µ̂(x′))]. (5)
Here the expectation is taken over the training data, W is a measure of the width of the PI, and ` is a loss function such as MSE. This property can be verified (as shown in Section 4) by checking how well W (Ĉ(x)) could predict the magnitude of the error. Discrimination could be considered a measure of efficiency, as a good Ĉ could “save” some width when the expected risk is low. However, it only makes sense to compare efficiency if all else is equal (i.e. two marginally valid PIs estimators with the same error). Note that although discrimination could be related to conditional/local validity, they are not the same - e.g., a PI that is always infinitely wide is conditionally valid, but not discriminative.
Our goal is to achieve both local validity and discrimination without making any assumptions about the underlying distribution P (i.e., in a distribution-free setting). As noted in Section 1, our method should also run fast and not affect the performance of underlying neural network model µ̂NN .

heading: 3 Method: Locally Valid Disciminative Prediction Intervals (LVD)
text: Overview: We first train a deep neural network (DNN) µ̂NN (if not already given), followed by a post-hoc training of an appropriately chosen kernel function K. Specifically, we learn K in a non-parametric kernel regression setting using embeddings from the deep learning model while optimizing for the underlying distance metric that the kernel function leverages. Both of these steps are explicated in more detail in Section 3.1. Armed with µ̂NN , we proceed to utilize a hold-out set to collect prediction residuals, which are used with the learned K (along with its distance metric) to build the final PI for any datum at inference time (Section 3.2). We then show the finite-sample local validity and asymptotic conditional validity in Section 3.4.

heading: 3.1 Training
text: At the onset, we partition Strain of N data points into two sets - Sembed and Sconformal. We will denote Sembed as {Zi}ni=1 and Sconformal as {Zn+i}mi=1, where m = N − n. Sembed is used to learn an embedding function f and a kernel K, and Sconformal is used for conformal prediction. [Optional] Training an Embedding Function: Instead of training a deep kernel in a kernel regression directly, which can be prohibitively expensive, we split the training task into two steps: training the (expensive) DNN, and training the kernel K. Specifically, we first train a DNN mean estimator µ̂NN : X 7→ Y to solve the supervised regression task with the mean squared error (MSE) loss. Note that µ̂NN can be based on any existing model. Moreover, this step could be skipped if we are already provided with a pre-trained µ̂NN . Then, we remove the last layer of µ̂NN and produce an embedding function f : X 7→ Rh for some positive integer h. If the original model µ̂NN is good, usually such an embedding provides a rich and discriminative representation of the input (as will be verified empirically in Section 4).
Training the Kernel: Fixing the embedding funtion f , we perform leave-one-out Nadaraya-Watson [24][14][41] kernel regression with a learnable Gaussian kernel on Sembed:
ŷKRi = ∑ j 6=i,j∈[n] yjKf (xi, xj)∑ j 6=i,j∈[n]Kf (xi, xj)
(6)
where Kf (xi, xj) = K(f(xi), f(xj)) = 1 σ √ 2π e −d(f(xi),f(xj)) σ2 and [n] := {1, . . . , n}. (7)
Here d(·, ·) is a Mahalanobis distance parameterized by a positive-semidefinite matrix W 0, which is learned. To avoid solving an expensive semi-definite program, instead of working with W directly,
we work with a low-rank matrix A ∈ Rh×k such that W = ATA, yielding the following equivalent distance formulation:
d(f(xi), f(xj)) = ‖A(f(xi)− f(xj))‖2. (8)
This parameterization of K is similar to that in [42]. Finally, to train K, we minimize the MSE loss.
Residual Collection: In this step, we take the trained embedding function and kernel, denoted as Kf for simplicity, and apply it on Sconformal. ∀i ∈ [m], we compute and collect the absolute residual,
Ri = |yn+i − ŷn+i|, (9)
the distribution of which is used for PI construction. It is important to remark that ŷ does not have to be ŷKR. The main purpose of the previous step is to train the K, and ŷ could still be obtained through the original DNN ŷ = µ̂NN (x), or any estimator not trained on Sconformal. As a result, the accuracy can only improve (if ŷKR turns out to be a better mean estimator)2.

heading: 3.2 Inference
text: Before proceeding further, we recall a useful definition and fix some necessary notation. For a distribution with cumulative density function (cdf) F defined on the augmented real line R ∪ {−∞,∞}, the quantile function is defined as Q(α, F ) = F−1(α). This definition is the same for a finite distribution like the empirical distribution. Suppose the empirical distribution consists of R1, . . . , Rm, then we denote the empirical distribution F̂ and the empirical quantile Q(α, F̂ ) as:
F̂ = 1
m m∑ i=1 δRi and Q(α, F̂ ) = inf r F̂ (r) ≥ α (10)
where δR(r) = 1{r ≥ R}. Note that we treat {Ri}mi=1 as an unordered list. Besides, Ri can be ±∞, and can repeat. Finally, we can assign weights to Ri, and define the quantiles for a weighted distribution:
F̃ = m∑ i=1 wiδRi where m∑ i=1 wi = 1. (11)
Split Conformal: Before presenting the detailed construction of the PI in LVD, it would be particularly instructive to first consider a special case. Specifically, when K returns a constant number for any (xi, xj), we recover the well-known “split conformal” method [25, 40, 21], which uses the 1−α quantile of the residuals as the PI width. Following our setup, the split conformal PI is given by:
Ĉsplitα (XN+1) = { y ∈ R : |y − ŷN+1| ≤ Q ( 1− α, 1
m+ 1
( δ∞ +
m∑ i=1 δRi
))} . (12)
Because the residuals {Ri}i∈[m] ∪ {RN+1} are i.i.d., RN+1’s ranking among them is uniformly distributed. We cannot know RN+1, so we use ∞ instead to be “safe” (∀r ∈ R, δ∞(r) = 0). It follows that Ĉsplitα is (1− α) marginally valid [25]. Local Conformal: In order to achieve the local coverage property, all we need to do is to re-weigh the residuals. Following the approach in [13], we arrive at the following suitable notion of PI:
ĈLVDα (XN+1) = { y ∈ R : |y − ŷN+1| ≤ Q ( 1− α, ( wN+1δ∞ + m∑ i=1 wn+iδRi ))} (13)
where wj = Kf (xj , xN+1) Kf (xN+1, xN+1) + ∑m i=1Kf (xn+i, xN+1) . (14)
In other words, we first assign weights to {Ri} based on the similarity between {Xn+i} and XN+1 using Kf , and then set the width to be the weighted quantile . Note that with δ∞, ĈLVDα (XN+1) will be infinitely wide if data is scarce around XN+1. However, as argued in [13], this is desired.
2As will be shown in the Appendix, ŷKR is often preferable because of the distance information it encodes.

heading: 3.3 Implementation Details
text: Parameterization and Training: Since A is intricately linked to the computation of the weights assigned by the Gaussian kernel K (Eq. 8), it is implemented as K(f(xi), f(xj)) = e−||A(f(xi)−f(xj))|| 2
. In order to optimize for A, we treat it as a usual linear layer in a neural network and perform gradient descent.
Smoothness Requirement: In the context of obtaining locally valid prediction intervals, a potential drawback of using the Nadaraya-Watson kernel regression framework is that the Kf will not meaningfully learn the similarity of any input with itself. For example, we can arbitrarily define Kf (x, x) to be any value, including∞. In the context of only regression, the fitted function’s performance will not change as long as there are no two identical xi. With the Gaussian kernel, this issue is somewhat mitigated. However, during the training, the K(xi, xi) can still be too high compared with K(xi, xi + ), resulting in a less meaningful definition for local coverage. We could then enforce a regularization by replacing the ŷi in Eq. 6 with
ŷ′KRi = y−iKf (xi, xi) +
∑ j 6=i,j∈[n] yjKf (xi, xj)
Kf (xi, xi) + ∑ j 6=i,j∈[n]Kf (xi, xj)
where y−i = 1 n− 1 ∑
j 6=i,j∈[n]
yj . (15)
This can be considered an explicit bias term towards the (leave-one-out) sample mean. Empirically, we observe that enforcing this requirement is crucial to obtain meaningful and tight intervals. We direct the reader to the Appendix for a detailed ablation on its utility.
Complexity: To facilitate training, we use stochastic gradient descent instead of gradient descent with batch size denoted as B1. Furthermore, if the dataset size is prohibitively large, we can also randomly sample a subset of B2 points {xj}j 6=i to predict ŷi. The total complexity is O(B1B2hk) where h and k, defined earlier, denote the dimensionality of the embedding before/after it is multiplied by A. Note that B2 = O(1) or o(N). The inference time for each data point can be improved from O(B2hk) to O(B2k + hk) by storing Axj instead of A and xj separately.
Denoting the number of parameter of the base NN as P , since DL models are usually overparameterized, the additional training time for each descent could be comparable or shorter than training the base NN (depending on the relation between P and B2hk)3, and the additional inference time would be much shorter than that of the base NN model. In addition, most of these factors (especially B2) can be easily parallelized. The full procedure is summarized below in Algorithm 1.
Algorithm 1 LVD Input: Strain: A set of observations {Zi = (Xi, Yi)}Ni=1 α: Parameter specifying (local) target coverage rate XN+1: Unseen data point Output: A locally valid PI, Ĉα(XN+1). Training:
[Optional] Randomly split Strain into Sembed and Sconformal. Denote Sconformal as {Zn+i}mi=1 [Optional] Train a NN regression model µ̂NN on Sembed. Remove the last layer of µ̂NN to get an embedding function f Train A on f(Sembed) in a Nadaraya-Watson kernel regression setting, with kernel Kf (x1, x2) = e−||A(f(x1)−f(x2))|| 2
Collect residuals Ri = |yn+i − ŷn+i| for i ∈ [m] Inference:
Compute PI as Ĉα(XN+1) = { y ∈ R : |y − ŷN+1| ≤ Q ( 1− α,wN+1δ∞ +
m∑ i=1 wn+iδRi )} where wj = Kf (xj , xN+1)
Kf (xN+1, xN+1) + ∑m i=1Kf (xn+i, xN+1)
3In practice, since f is already well-trained, the training of Kf converges very fast.

heading: 3.4 Theoretical Guarantees
text: We conclude this section by showing that ĈLVDα provides the local coverage property. We adapt Theorem 5.1 in [13] and results in [33] to our setting. The detailed proof is deferred to the Appendix:
Theorem 3.1. Conditional on XN+1, the PI obtained from Algorithm 1, ĈLVDα (XN+1), satisfies
P{ỸN+1 ∈ ĈLVDα (XN+1)|XN+1 = x′} ≥ 1− α for any x′ (16)
where the probability is taken over all the training samples i.i.d.∼ P = PY |X×PX , and (X̃N+1, ỸN+1) with distribution X̃N+1|XN+1 ∼ PXN+1X and ỸN+1|X̃N+1 ∼ PY |X . Here P XN+1 X means the localized distribution with dP XN+1 X (x)
dx ∝ dPX(x) dx Kf (XN+1, x).
With some regularity assumptions like in [22], we can also obtain asymptotic conditional coverage:
Theorem 3.2. With appropriate assumptions, ĈLVD is asymptotically conditional valid.
The detailed assumptions, formal statement, and proof of Theorem 3.2 are deferred to the Appendix.
Remark: Roughly speaking, Theorem 3.1 tells us that the response Y of a new data point sampled “near” XN+1 will fall in our PI with high probability. Theorem 3.2 further states that, under suitable assumptions and enough data, ĈLVD also covers YN+1 (i.e., no re-sampling) with high probability.

heading: 4 Experiments
text: Baselines: We compare LVD with the following baselines (with a qualitative comparison in Table 1):
1. Discriminative Jackknife (DJ) [1], which claims to be both discriminative and marginally valid but is neither (See Appendix C). 2. Deep Ensemble (DE) [20], which trains an ensemble of networks to estimate variance and mean. 3. Monte-Carlo Dropout (MCDP) [12], a popular bayesian method for NN that performs Dropout
[31] at inference time for the predictive variance estimate. 4. Probabilistic Backpropagation (PBP) [15], a successful method to train Bayesian Neural Networks
by computing a forward propagation of probabilities before a backward computation of gradients. 5. Conforamlized Quantile Regression (CQR) [29], an efficient (narrow PI) marginally valid confor-
mal method that takes quantile predictors instead of mean predictors. This comes with a huge cost: one needs to retrain the predictor for each α if more than one coverage level is desired. 6. MAD-Normalized Split Conformal (MADSplit) [21, 8], a variant of the well-known split-conformal method that requires an estimator for the mean absolute deviation (MAD), and performs conformal prediction on the MAD-normalized residuals.
In our experiments, PIs for non-valid methods are obtained from the quantile functions of the posterior for target coverage 1− α like in [1].

heading: 4.1 Synthetic Data
text: We will first examine the dynamics of different uncertainty methods with synthetic data. The formula we use is the same as in [15, 1]: y = x3 + . Here, ∼ N (0, 42), and x comes from Unif [−1, 1] with probability 0.9, and half-normal distribution on [1,∞) with σ = 1 with probability 0.1. We used this PX to illustrate local validity. The results are shown in Figure 2. We observe that LVD, CQR, MADSplit, and DJ all achieve close to 90% coverage. However, LVD gives a more meaningful discriminative predictive band: Specifically, near the boundaries, it will give us wider intervals (sometimes ∞) because there is little similar data around, which is desirable for local validity. Although CQR and MADSplit can be discriminative, they are still only marginally valid, so we can see that despite the varying width, they actually get narrower when x is more eccentric, which is clearly an issue. DJ essentially gives PIs of constant width, as estimated from the quantile of the residuals. DE also does not give meaningful uncertainty estimates, giving almost constant PIs that
cover well below 90%. For Bayesian methods, MCDP behaves much like a Gaussian Process (as claimed in [12]), with low coverage rate, whereas PBP is mildly discriminative and not valid4.

heading: 4.2 Real Datasets
text: We will be using a series of standard benchmark datasets in the uncertainty literature [1, 29, 15], including: UCI Yacht Hydrodynamics (Yacht) [38], UCI Bikesharing (Bike) [35], UCI Energy Efficiency (Energy) [37], UCI Concrete Compressive Strength (Concrete) [36], Boston Housing (Housing) [9], Kin8nm [16].We also use QM8 (16 sub-tasks) and QM9 (12 sub-tasks) [28, 30, 27] as examples of more complicated datasets. In each experiment, 20% of the data is used for testing. The sizes of datasets used are shown in Table 2. We use the same DNN model for all baselines, which has 2 layers, 100 hidden nodes each layer, and ReLU activation for the non-QM datasets. For QM8 and QM9, we use the molecule model implemented in [45] and apply applicable baselines. Missing baselines (“–” in the tables) are either too expensive (i.e. time and/or memory) or require a significant redesign of the training and NN, which is beyond the scope of this paper.
Evaluation Metrics: The evaluation is based on validity and discrimination. For validity, we check the marginal coverage rate (MCR) and the tail coverage rate (TCR), which is defined as the coverage rate for data whose Y falls in the top and bottom 10%. The motivation behind TCR is that if our local validity is very close to conditional validity, then LVD’s coverage rate would be above target in any pre-defined sub-samples, including those with extreme Y s. For discrimination, to verify Eq. 5, which
4Sometimes it may be possible to calibrate Bayesian methods [29]. However, one needs to calibrate the entire posterior for the Bayesian method to makes sense. Moreover, from our experiments, it is impossible to do this in MCDP, when it behaves like a Gaussian process and predicts zero variance near known data.
is a prediction task, we compute the AUROC of using the PI width to predict whether the absolute residual is in the top half of all residuals. AUROC alone is misleading, however, as a bad predictor can easily be discriminative (e.g., by randomly adding to both its prediction and PI width a huge constant). Therefore, we also report the mean absolute deviation (MAD), defined as ∑M i=1 |ŷi−yi|
M .
We repeat all experiments 10 times and report mean and standard deviations. For QM8 and QM9, we report the average numbers across all sub-tasks, with a breakdown on each sub-task in the Appendix.
Results: For validity, as shown in Table 3, LVD achieves marginal coverage empirically, as well as MADSplit5 , CQR, and DJ. However, for tail coverage rate, only LVD consistently covers at or above target coverage rates. For the larger datasets, both coverage rates tend to get close to 90% for LVD. DE, MCDP, and PBP do not achieve meaningful coverage (either too high or too low). [19] also report mixed results on marginal validity with existing uncertainty quantification methods for DL. To 5It is worth noting that MADSplit, despite the theoretical guarantee, misses on the Yacht dataset, because the MAD-predictor predicts a “negative” absolute residual for some subset of the data, thus creating extremely narrow PIs, even after requiring the prediction to be positive and the “practitioner’s trick” mentioned in [29].
further test for local validity, we also examine the average coverage rate conditioned on the presence of certain functional groups for the QM9 dataset (detailed results are relegated to the appendix). LVD achieves empirical validity for these groups as well, even though functional groups define a kind of similarity that is never used in the uncertainty quantification process.
For discrimination (Table 4), LVD is generally in the top two while maintaining the lowest MAD almost always. MADSplit has the same MAD as LVD (using the same µ̂NN ), and has a similar AUROC as LVD despite explicitly modeling MAD. Other baselines occasionally show a significant discriminative property, but usually have much higher MAD. Despite training an ensemble of models, DE incurs huge prediction errors in many datasets. As noted earlier, AUROC alone is misleading if the MAD is high: MCDP and CQR seem highly discriminative on the Bike dataset, mostly due to the high model error (epistemic uncertainty).
Scalability: For the largest dataset, QM9, the extra inference time of LVD vs. inference time of the original NN is 0.65 vs. 0.75 second per 1000 samples6 on an NVIDIA 2080Ti GPU. MADSplit on the other hand takes 0.93 second overhead in the most optimized case. That said, any method that finishes within O(1) multiple of the original NN model is usable in practice. For LVD, extra vs. original training time is about 1.5 vs. 0.75 second per 1000 samples, but because the f is already highly informative, the training of the kernel Kf finishes in very few iterations, resulting in < 5% overhead of the total training time. Note that MADSplit will take strictly ≥ 1× time in total because it needs to train a second model to predict residuals. Like MADSplit, CQR needs to train at least one quantile predictor7, but it needs to train a new predictor for every α, which is a huge cost.

heading: 5 Conclusion
text: This paper introduces LVD, the first locally valid and discriminative PI estimator for DL, which is also scalable and post-hoc. Because LVD is both valid and discriminative, it can provide actionable uncertainty information for the real world application of DL regression models. Moreover, it is easy to apply LVD to almost any DL model without any negative impact on the accuracy due to its post-hoc nature. Our experiments confirm that LVD generates locally valid PIs that cover subgroups of data all other methods fail to. It also exceeds or matches the performance in discriminative power while offering additional benefits in scalability and flexibility. We foresee that LVD can enable more real-world applications of DL models by providing users actionable uncertainty information.

heading: Acknowledgments
text: This work is in part supported by National Science Foundation award SCH-2014438, IIS-1418511, CCF-1533768, IIS-2034479, the National Institute of Health award NIH R01 1R01NS107291-01 and R56HL138415. The authors are also thankful to Andrew Gordon Wilson and three anonymous reviewers for their comments to help improve this work.
6We use the full Sconformal for PI construction, as the inference time is short enough without sampling. 7That is, if one is willing to have mean estimate outside the PI occasionally and consider CQR post-hoc.

Review summaries:
The authors the Locally Valid and Discriminative (LVD) method to construct confidence intervals. The idea has three steps. (1) First is to take the embeddings from a neural network and train a kernel regression model on the task, learning a Gaussian kernel $K$. (2) Second is to, on a separate held-out "conformal" set, compute the residuals between the model and ground truth labels. (3) Third is to, at inference time, compute the empirical desired $(1-\alpha)$ interval on the "conformal" set residuals, where each residual is re-weighted according to $K(x', x)$ where $x'$ is the query of interest. LVD has the appealing property that it is compatible with any (potentially pre-trained) deep learning model, with no further further training necessary.  The authors prove that under appropriate assumptions LVD achieves *local coverage*, i.e. coverage not only marginal over the entire feature space, but at a particular query $x$. Empirically they demonstrate that LVD improves upon popular neural network predictive uncertainty methods on the well-known UCI datasets. They evaluate in terms of Mean Absolute Deviation, Marginal Coverage Rates, and Tail Coverage Rates (which is defined as the coverage rate for the left and right 10% of the tails of labels $y$).

The authors propose a new method for locally valid (e.g. marginal coverage guarantees) and discriminative prediction* intervals by connecting two ideas: kernel regression and conformal inference. They evaluate their method on a suite of small to medium scale regression tasks and find that the proposed approach is locally valid   *note that the authors refer to these intervals as _confidence_ intervals which I believe to be an error. CIs seek to cover a population parameter, which for regression would be the true, unknown, and underlying mean function (which can only be assessed via a simulation). What the authors propose are _prediction_ intervals which seek to cover draws from this distribution and are inclusive of distributional noise, c.f. this reference for more:  https://www.stat.cmu.edu/~ryantibs/papers/conformal.pdf