Locally Valid and Discriminative Prediction Intervals for Deep Learning Models
Authors: Zhen Lin
Shubhendu Trivedi
Jimeng Sun
Venue: NeurIPS 2021 Poster (2021)
Keywords: Deep Learning
Local Validity
Conformal Prediction
Uncertainty Quantification
Prediction Interval

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.

Locally Valid and Diseriminative Prediction Intervals for Deep Learning Models
Zhen Lin
Shubhendu Trivedi MIT
University of Illinois at Urbana-Champale Urbana, IL 61801
Cambridge, MA 02139 shubhendu@csail miitttai........................ edu
edu
Jimeng Sun
University of Illinois at Trbana-Champplr Urbana, IL 61801 j jmmeg@illinois. edu
Abstract
Crucial for building trust in deep learning models for critical real-world appli- cations is efficient and theoretically sound uncertainty quantification, a task that continues to challenging. Useful uncertainty information expected 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 DI. 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 assump- tions. Moreover, many methods are expensive or require substantial modifications to the base neural network. Building upon recent advances conformal predic- tion B3 [33] and leveraging the classical idea of kernel regression, propose Locally Valid and Discriminative prediction intervals (LVD), a simple, efficient and lightweight method 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 quan- tification methods, while offering additional benefits in scalability and flexibility.
1 Introduction
Consider a training set Smain {(X,, Y and a test example (XN+1, YN+1), drawn i.i.d from an arbitrary joint distribution P. with (X,, Y)) X for some S gd and y R. We are interested in the problem of predictive inference: On observing Sman and X our task is to construct prediction interval (PI) estimate C(XN+1) that contains the true value of YN+1 with (pre-specified) high probability.
'Several 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 (NcurIPS 2021).

---

(Marginally) Valid but not discriminative
Not valid but discriminative
Conditionally valid discriminative
Y (Pesponne)
Y (/Reaaa Feaegooni
Y Pressponng
missed
covered 90% Pl
X (Input)
X (Inuut)
X (Input)
Figure 1: Illustration of possible (good and bad) Pls. The PI on the left is valid, as it covers 90% of the data. It is however only marginally valid, not reflecting the poor model prediction near the red cluster. The middle PI is discriminative, and reflects the high error near the red cluster, but its coverage rate is much lower than the target (thus not valid). The PI on the right addresses both challenges by stretching "just enough" near the cluster, making it not only discriminative, but also conditionally valid. We seek to construct PIs of the last type, but constructing exact conditionally valid PIs in a distribution- ffreee setting is theoretically impossible. We thus relax this goal by instead aiming for local validity (more details in Section ..
The construction of actionable PIs involves two general challenges: First, Ö' should be valid, meaning that if the specified probability is - a, we expect ((X++1) to cover YN+1 at least 1 of the time. Moreover, C' should be discriminative i.e., expect C(XN+1) be narrower for confident cases and vere-versa. The width of the PI Č x+1+ thus quantification of the uncertainty. Figure [illustrates these notions, with more details in Section 2.2 and 2.3
While deep learning (DL. models have demonstrated impressive performance over range of complicated tasks and data modalities, it has remained difficult to quantify the uncertainty for their predictions. For DL predictions be actionable, uncertainty information is however indispensable, especially in domains like medicine and finance 22] 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 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 DI..
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 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
sense
experiments) [2] [ 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 powerful approach for constructing valid Pls. The most popular split conformal methods usually leverage prediction errors from a hold-out set to construct C(X N441), ), which would be valid if future data point 1 YN+1)
follows the same distribution as data in the hold-out set. This framework is particularly suitable for deep learning due its distribution-free -fee nature, and has motivated many recent uncertainty quantification efforts in deep learning for both classification and regression tasks [ 23 3 I...
However, most conformal methods are only marginally valid (25 40 21 4. Moreover, less-than- meticulous applications to DL can break distributional assumptions and theoretical validity, as in
the case of [ (see discussion in Appendix). We however seek to construct a PI conditioning on the input (similar to the third PI in Fig. []. Some recent advances ( 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), simple uncertainty estimation method for deep learning which combines recent advances 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 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 [3]. LVD addresses several challenges to satisfy the other three requirements. The code to replicate all our results can be found at https: //tp::://ttttiu www./oo//c/../// com/zlin7/LVD
2
Preliminaries
2.1 Learning Setup and Assumptions
We assume data and response pairs () Y) X' 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 PrJx. respectively, Further, will define Z; := (X;, Y,) for concision.
Assuming that we already have an algorithm (with all the training protocols folded in), such Deep Neural Network (DNN), that provides a mean estimator j. (x) X' + V. Given a target coverage level 1 E (0, 1). our task is to also construct a prediction interval estimator function Co (z) X + {subset of y) that has the validity and discrimination properties as defined below.
2.2
Validity (Frequentist Coverage)
There are several (related) notions for Pl to be valid marginal, conditional, and local. Given target level 1 - a, we say Co has the marginal coverage guarantee (or, equivalently, is marginally valid) if
P[YN+1 E (x(xN=1) 2 -a
(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 X A more desirable, albeit stronger, property would be conditional coverage at oc
P(YN+1 E (x
=} 2 1 a for almost all X.
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 completely missed. Unfortunately,
impossible to achieve distribution free finite- sample conditional coverage (Eq. 2 in non-trivial way. Indeed, it is known that faitee estimated C. (x) cannot achieve conditional coverage, unless it produces infinitely wide prediction intervals 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 considerable freedom 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 X X R and center x' X, like the relaxation given in [33]
[P(YN+I E Ca(x')) xxx 21-a
(3)
[
with the probability (P in the integral) taken over all training samples and YN+1. with (XN=1,YN+1) ~ P = Px x Here Px is just the distribution re-weighted by the ker- nel with center x', defined by d=)
de (x) K (x',ax x). Instead of choosing x' beforehand, if we dy
let the center be XN+1 and fold the integral into IP like [13,, we arrive at the definition of local coverage:
(4) Here the probability integrates over all training data and an additional (KN+1, YN41) ~ P defined above. Intuitively, this definition means Co (X is valid "on average" within a small neighborhood
P(NN-1 E (x(X)))))NNHI 1000:1==1/0000 2-21-a.

---

of XN+1. Note that Eqs. and 2 reduce to Eq. 4 with K being constant and delta functions, respectively, In the rest of the paper, we will call Co marginalyloondtiinallllaaalll valid if it satisfies Eq. 2 respectively, and we will pursue sinite-sample local validity.
2.3 Discrimination
The idea of discrimination is simple: If the error of our prediction A(z) is high for an input æ, the PI should be wide, and vice versa. Formally, following M. we require
E[[(C(=)) 2 E[W(C(z')) < E[e(y, ((x) 2
(5)
Here the expectation is taken over the training data, W is measure of the width of the PI, and f is loss function such as MSE. This property can be verified (as shown in Section 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 Ô could "save" some width when the expected risk is low. However, it only makes sense 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., 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 distribution-fres setting). As noted in Section | our method should also run fast and not affect the performance of underlying neural network model p NN.
3 Method: Locally Valid Disciminative Prediction Intervals (LVD)
Overview: We first train a deep neural network (DNN) j.N (if not already given), followed by a post-hoc training of an appropriately chosen kernel function K. Specifically, we learn K in a non-pan aa-aaaramttic kernel regression setting using embeddings from the deep learning model while optimizing for the underlying distance metric that the kernel function leverages. Both these steps explicated in more detail in Section 3.1 Armed with NN we proceed to utilize 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.2h. We then show the finite-sample local validity and asymptotic conditional validity in Section 3.4
3.1 Training
At the onset, we partition Syain of N data points into two sets Sembed and Sconformal- We will denote Semted as {2.) and Sconformal as { //n- where m = N n. Sembed is used to learn an embedding function f and kernel K, and Sconformal is used for conformal prediction.
[Optional] Training an Embedding Function: Instead of training deep kernel in kernel regres- sion 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 NNN X + ) 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 pre-trained N.N Then, we remove the last layer of J.NN and produce an embedding function X' AR.h for some positive integer h. If the original model j. j.' is good, usually such embedding provides rich and discriminative representation of the input (as will be verified empirically Section 4).
Training the Kernel: Fixing the embedding funtion f, we perform leave-one-out Nadaraya-Wand Watson kernel regression with learnable Gaussian kernel on Sembed
24 14
KKR_ Ejtije Uj Kz))))zz))
(6)
Ejtiseta Ke(T),,,))
where Kr(I,, 2;) = (f(()))) vV2
and [n] := (l,...,,2 n...
(7)
Here .(...) ) a Mahalanobis distance parameterized by a positive-semidefinic matrix W > 0, which is learned. To avoid solving expensive semi-definite program, instead of working with W directly.

---

we work with a low-rank matrix A E Raxk such that W = ATA, yielding the following equivalent distance formulation:
d(f(2;), f(z,)) = [I(((()))) (x))))I²
(8)
This parameterization of K is similar that in 42 Finally, to train K, minimize the MSE loss.
Residual Collection: In this step, we take the trained embedding function and kernel, denoted as Kr for simplicity, and apply it on Sconfomal- Vi [m]]. we compute and collect the absolute residual,
R. Un+i - Dn+el
the distribution of which is used for Pl construction. It is important to remark that ÿ does not have to be gkRR The main purpose of the previous step is to train the K, and ý could still be obtained through the original DNN ÿ NN (z:). any estimator not trained on Spaformal- As result, the accuracy can only improve (if g kKR turns out to be a better mean estimator
3.2 Inference
Before proceeding further, we recall a useful definition and fix some necessary notation. For distribution with cumulative density function (cdf) F defined on the augmented real line IR U {-oc, ) the quantile function is defined as ((a, F) = (a). This definition is the same for
finite distribution like the empirical distribution. Suppose the empirical distribution consists of Ri...., Rm. then denote the empirical distribution / and the empirical quantile Q(a, F) as:
F
ÖR.
and ()a inf ((r)
(10)
where (n(r)= fr 2 R). Note that we treat {R, Jm as an unordered list. Besides, Rd can be too, and can repeat. Finally, we can assign weights RG, and define the quantiles for a weighted distribution:
m
m
wión
where
m =1
(11)
Split Conformal: Before presenting the detailed construction of the PI in LVD, it would be particu- larly instructive to first consider a special case. Specifically, when K returns a constant number for any (I,, Zy), 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 given by:
{ y YER:: UN+1l Q (1-a,
1 m +
800
Rg
(12)
Because the residuals (im) U (RN+1) are i.i.d., RN+1 's ranking among them is uniformly distributed. We cannot know Ry+1, follows that Čaplit is (1 a) marginally valid (25]
use instead to be "safe" (Vr E 8 (r) 0). It
Local Conformal: In order to achieve the local coverage property, all we need to do to re-weigh
the residuals. Following the approach in [3 we arrive at the following suitable notion of PI:
y E R: 1N+Il & Q 1-a [WN+100 +
Wn-tdR ))
OLVD (XVD((N+1)=F =
(13)
Fe(I,,NN+) where W/ = 2N + Em Fe(Ints:2N=))
(14)
In other words, we first assign weights to {R.} based on the similarity between {Xn+s} and XN+1 using Kr, and then set the width to be the weighted quantile Note that with 8 ÖLV CLVD(X (XN+1) will be infinitely wide if data is scarce around X XN+1. However, as argued in this desired.
As will be shown in the Appendix, K is often preferable because of the distance information encodes.
5

---

3.3 Implementation Details
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 K (((())), ((a))
f In order to optimize for A, we treat as a usual linear layer in a neural network and perform gradient descent.
Smoothness Requirement: the context of obtaining locally valid prediction intervals, a potential Satrryyy--attonnnn Watson kernel regression framework is that the K3 will not mean- ingfully learn the similarity of any input with itself. For example, we can arbitrarily define (r, In the context of only regression, the fitted function's performance
drawback of using the Nadaraya-
to be any value, including will not change as long as there are no two identical z;. With the Gaussian kernel, this issue is somewhat mitigated. However, during the training, the K(x;: 24) can still be too high compared with K ( v; + c), resulting in a less meaningful definition for local coverage. We could then enforce a regularization by replacing the i in Eq. with
1/ V- Kr + E Sitjjelm My (r 0. KKR
where V_,
Σ Vj-
(15)
x.) + }z(ee((M) KF(
This can be considered explicit bias term towards the (leave-one-out) sample mean. Empirically, we observe that enforcing this requirement crucial obtain meaningful and tight intervals. We direct the reader to the Appendix for a detailed ablation on its utility.
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 subset B₂ points {x, } to predict ys. The total complexity O B2hk) where 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(Brhk) to O + hk) by storing Ar, instead of A and I separately.
Complexity:
Denoting the number of parameter of the base NN P, since DL models are usually overparameter- ized, the additional training time for each descent could be comparable or shorter than training the base NN (depending on the relation between P and Byhk and the additional inference time would be much shorter than that of the base NN model. In addition, most of these factors (especially B₂) can be easily parallelized. The full procedure summarized below in Algorithm
Algorithm LVD
Input:
Smain A set of observations {2, = (X,, Y a: Parameter specifying (local) target coverage XN+1: Unseen data point
Output: A locally valid PI, (X Training:
[Optional] Randomly split Suain into Sembed and Sconformal- Denote Sconformal as (2n-1) mm [Optional] Train NN regression model j NN on Sembed-
Remove the last layer of NNN to get an embedding function Train A on ((eebeed) in a Nadaraya-Wand Watson kernel regression setting, with kernel Kr(11,02) e --IAA(f(=))-((
Collect residuals RG Mh4i On-el for [m]
Inference:
m
Compute PI as (a(N1)))
V lV 1N+1 SQ 1 +Σ wn-
KF(I,, where Wj- Kr(ENH1,NNH) E #x(
In practice, since f is already rell-trained, the training of Kr converges very fast.

---

3,4 Theoretical Guarantees
We conclude this section by showing that CLVD provides the local coverage property. We adapt Theorem 5.1 in I and results in 33 to our setting. The detailed proof is deferred to the Appendix:
Theorem 3.1. Conditional on XN+L the PI obtained from Algorithm
CLV (XN+1), satisfies
P(YN+1 E CLVD (XN+1))XNNH = x 12 ar for any x'
(16)
where the probability is laken over all the training samples i.dd -P-xxxx xxx, and (NN+1, YN+1)
with distribution NN41| XN41
Xxx=1 and YN+1|XN41 Pyix. Here P Xx+1
Px
means the
do x (x) (xx(x) de (x(XN+1,T).
localized distribution with
dx
With some regularity assumptions like in (22), we can also obtain asymptotic conditional coverage:
Theorem 3.2. With appropriate assumptions, CLVD is asymptotically conditional valid.
The detailed assumptions, formal statement, and proof of Theorem
deferred to the Appendix.
Roughly speaking. Theorem 3.1 tells us that the response Y of new data point sampled "near" XN+1 will fall in our PI with high probability. Theorem furrtherr states that, under suitable assumptions and enough data, CLVD also covers YN+1 (i.e., no re-sampling) with high probability.
Remark:
Experiments
Baselines: We compare LVD with the following baselines (with qualitative comparison in Table I
1. Discriminative Jackknife (DJ) (.. which claims be both discriminative and marginally valid
but is neither (See Appendix C
2. Deep Ensemble (DE) 220.. which trains an ensemble of networks to estimate variance and mean.
3. Monte-Carte 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 forward propagation of probabilities before a backward computation of gradients.
5. Conforanlized Quantile Regression (CQR) [29], an efficient (narrow PI) marginally valid confor- mal method that takes quantile predictors instead of mean predictors. This comes with huge cost: one needs to retrain the predictor for each if more than one coverage level is desired. 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 - a like in
4.1 Synthetic Data
We will first examine the dynamics of different uncertainty methods with synthetic data. The formula we use is the same as in [I: y 2 + e. Here, e (N(0, 42), and x comes from Uni finfl-1,, 1] with probability 0.9, and half-normal distribution on [1, oo) with o = 1 with probability 0.1. We used this Px to illustrate local validity. The results are shown in Figure We observe that LVD, CQR. MADSplit, and DJ all achieve close to 90% coverage. However, LVD gives more meaningful discriminative predictive band: Specifically, near the boundaries, it will give us wider intervals (sometimes co) because there is little similar data around, which is desirable for local validity. Although CQR and MADSplit can discriminative, they are still only marginally valid, so we can see that despite the varying width, they actually get narrower when & is more eccentric, which is clearly an issue. DJ essentially gives Pls of constant width, as estimated from the quantile of the residuals. DE also does not give meaningful uncertainty estimates, giving almost constant PIs that
7

---

Table 1: Features of different methods. CQR and MADSplit achieve strict finite-sample marginal coverage. Unlike LVD, no baseline is locally valid. LVD, MADSplit and CQR are discriminative, DJ is not, and DE/CMDP/PBP post-hoc methods, LVD and MADSplit have reasonable overhead, DJ's overhead is usually ((N) where N is the number of training data (and extremely large memory consumption). CQR is not post-hoc because its Pl may not contain j NN (X).
supposed to be but usually fail to in our experiment. Among the
LVD
MADSplic
CQR
DE
MCDP
PBP
Valid Discriminative
Local
Marginal
Marginal
no guarantee
X sometimes X
X
X sometimes X N/A
sometimees
Post-hoe Overhead (if post-boc)
X N/A
Low
Low
Very High
N/A
(Covered 93.0%)
MAC (Covered 58.0%)
(oovered 67.0
(Covored 98.2%)
23
DE (Covered 66.0%)
MCDP (Covered 16.0%)
P52 (Covtned 37.0%)
missed
covered
90% Pl
-10
Figure 2: LVD. CQR and MADSplit achieve marginal coverage. Although without theoretical guarantee, DJ usually marginally covers in practice with near constant width (not discriminative). DE, MCDP and PBP do not show validity as expected. Among valid Pls, only LVD tries to capture the less representative points by wider Pls, arguably showing the most useful discriminative pattern.
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 valio") [4]
4.2 Real Datasets
Table 2: Size of each dataset. Size of the test set is in parenthesis.
Yacht
Housing
Energy
Bike
Kin8nm
Concrete
QM8
QM9
308 (62) 506 (101) 768 (154) 17379(3476) 8192 (1638) 1030 (206) 21786 (4357) 133719 (26744)
We will be using series of standard benchmark datasets in the uncertainty literature 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) ( Kin&nm 16 We also use QM8 (16 sub-tasks) and QM9 (12 sub-tasks) 28 30 27 as examples of more complicated datasets. each experiment, 20% of the data is used for testing. The sizes of datasets used are shown in Table [] We use the same DNN model for all baselines, which has 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.
The evaluation 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 dre-nef sub-samples, including those with extreme Ys. For discrimination, to verify Eq. [5] which
Evaluation Metrics:
"Sometimes it may be possible to calibrate Bayesian methods (2) 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 Gaussian process and predicts zero variance near known data.
8

---

is a prediction task, we compute the AUROC of using the PI width to predict whether the absolute residual in the top half of all residuals. AUROC alone is misleading, however, as bad predictor can easily be discriminative (e.g., by randomly adding to both its prediction and PI width huge constant). Therefore, we also report the mean absolute deviation (MAD), defined as >M 19 26
A
Table 3: Marginal coverage rate (MCR) and tail coverage rate (TCR) (coverage rate for left and right 10% tail for test label) with target at 90%. represents not-applicable models (see Section 4.2). Coverage rates not significantly lower than target at p 0.05 are in bold (good). Note that the too high is not better. For example, MCDP either greatly over- or under-covers with MCR
either 100% or well below 90%.
MCR
LVD
MADSplit
CQR
DJ
DE
MCDP
PBP
Yacht
96.822.2
82.4:7.11
91.5+:4.7
95.0:t:211
22.71::00
87.4:t4.2
80.2:+10.8
Housiin
9..
90.6.13.5
91.7.1333
97.6.114
96.011.9
100.0:10.0
8.1.14.3
Energy
9..041.66
90.3412.22
96
98.0::277
100.0:10.00
7.2.5-.99
Bike
90.4=0.8
89.9+00.6
89,8+0.7
95.2-+0.66
100,0+00.0
71.9=
0.6=0.22
Kin8am
98.0=0.66
90.0-1:.88
90.2++0.6
94.7::0.44
100.0:0.11
100.0:1:0.0
100.0::0.00
Concrete
9.34
88.81:2888
88.51:2.3
98.0:1..6
97.81100
100.0:10.0
3.3
QM8
92.6=0.9
90.0=t0.7
90.0+t0.6
100.0:0..0
1
90.3::0.6
90.0::0.2
90.0:10.3
60.7=:46.8
TCR
LVD
MADSpli
CQR
DJ
DE
MCDP
PBP
Yacht
9.251
65.44123.8
77.74:1..3
76.2.199
1,5:1499
50.0:19.8
70.0:1:4.3
Housing
96.224.4
87.6+28.8
82.948.2
90.0:::.2
81.9449.7
100.0::0.00
1.0233.0
Energy
86.8+588
18.4+10.9
13.5+112.0
90.0:1:.55
95.8-6.3
100.0:1:000
9.7=12.7
Bike
9..2
89.2.1.3.5
58.71:7.3
85.6:13..3
100.0:10.00
49.9:10.00
0,0:2:.0
Kin8nm
9..2+1.6
86.4:22.66
85.2422.2
88.1+118.
99,9+-0.3
100.0:1:0.0
100.0+:0.0
Concrete
97.1
83.9:7733
65.4166.2
95.6:::.66
91.7:1:488
100.0::0.0
3.4
QM8
9.
86.3.1..44
80.0.1..9
100.0.10.00
QM9
2..7
86.1::3.0
79.718.9
60.3-46.5
Table 4: At 0.05, AUROCS (in predicting error being greater than 50% percentile) that are significantly higher than 50%, and mean absolute deviations (MAD) significantly lower than the second-best, are in bold. LVD, MADSplit and CQR are consistently discriminative, but CQR sometimes incurs high MAD. DJ is not discriminative, whereas other methods occasionally demonstrate discrimination but usually have high MADs as well.
AUROC
LVD
MADSplit
CQR
DJ
DE
MCDP
PBP
Yachi
83.5.15.8
77.7.9.0
849114
50.0.1
59.8
47.2
8..818.8
Housing
59.2:18.5
62.0-18.3
62.5:16.7
49.6.15.9
60.0-6.8
42.5.7.88
3.64--366
Energy
73.54633
72.945.6
72.1482
57.548.1
16.1+11.0
54.6+:555
48,2426
Bike
68.2=11.0
71.7#8.5
84.8=33.5
45.8+6..
86.2+
94.3+=1.0
1,0
Kin8aa
60.3::1.1
60.4:1199
60.0:12.11
49.312222
50.5
54.1
53.6
Concrete
64.0.16.1
63.8115.7
66.0.1..1
46.2.149
5..9
51.913.55
3..7
QM8
71.3:19.4
73.5::6.8
65.5-10.3
91.7+1669
QM9
62.7::3.6
64.9::355
55.0=14.4
56.8+-28.4
MAD
LND
MADSplit
CQR
DJ
DE
MCDP
PBP
Yocht
1.90=0.48
1.90-20.48
3.55=0.85
10.15::0.84
11.25=0.81
10.92-20.73
1.80=2030
Housing
3.31=0.53
3.31-:..33
3.44-0.33
3.69=0.33
4.42
6.04:1:0.54
7.94=1997
Energy
2.99:10.75
3.44=1004
3.19:1..1
3.79.1.31
8.12-10.59
11.66:12.24
Bike
0.04-0.03
0.04-10.03
3.34
0.05-10.03
3.37
124.57-12.68
162.2112.58
Kin8nm
0.07=0.00
0.0740.00
0.08-0.01
0.09=0001
0.19+:0.11
0.18::0:00
0.22-00112
Concrese
5.44=0.53
5.44:20.53
6.21=1005
5.58=0.58
7.22+20.76
13.75::0.69
20.59:3.57
QM8
0.01=0.01
0.01:10.11
0.03-0.02
3.28-15.12
QM9
3.69=9.09
3.69
32.11=50.42
268.324335.01
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 breakdown each sub-task in the Appendix.
Results: For validity, as shown in Table 3, LVD achieves marginal coverage empirically, as well as MADSpli 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 too low). [19 also report mixed results on marginal validity with existing uncertainty quantification methods for DL. To
is worth noting that MADSplit, despite the theoretical guarantee, misses on the Yacht dataset, because the
MAD -reediicttor predicts a "negative" absolute residual for some subset of the data, thus creating extremely narrow Pls, even after requiring the prediction to be positive and the "practitioner's '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 kind of similarity that is never used in the uncertainty quantification process.
For discrimination (Table D. LVD is generally in the top two while maintaining the lowest MAD almost always. MADSplit has the same MAD as LVD (using the same ),, and has similar AUROC as LVD despite explicitly modeling MAD. Other baselines occasionally show 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 the high model error (epistemic uncertainty).
Scalability: For the largest dataset, QM9, the extra inference time of LVD inference time of the original NN is 0.65 vs. 0.75 second per 1000 sample 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 (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 K₃ finishes in very few iterations, resulting in < 5% overhead of the total training time. Note that MADSplit will take strictly 2 1x time in total because it needs to train second model to predict residuals. Like MADSplit, CQR needs to train at least one quantile predictof but it needs to train new predictor for every a, which is a huge cost.
Conclusion
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 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 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.
Acknowledgments
This work is in part supported by National Science Foundation award SCH-201445 IIS 1418511 1, CCF- 1533768, 10344994,79, the National Institute of Health award NIH RO1 TO01NS107291400 and R56HL The authors also thankful to Andrew Gordon Wilson and three anonymous reviewers for their comments to help improve this work.
We use the full Soonforal for PI construction, as the inference time is short enough without sampling.
"hha is, if one is willing to have mean estimate outside the PI occasionally and consider CQR hoct-hoc.
10

---

References
[1] Ahmed Alaa and Mihaela Van Der Schaar. Discriminative Jackknife: Quantifying Uncertainty in Deep Learning via Higher- Order Influence Functions. Hal Daumé III and Aarti Singh. editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 165-174. PMLR, 2020.
[2] Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete problems in ai safety, 2016.
[3] Anastasios Angelopoulos. Stephen Bates, Jitendra Malik, and Michael I. Jordan. Uncertainty sets for image classifiers using conformal prediction. CoRR, abs/2009. 14th/2009.1419,, 2020.
[4] Rina Foygel Barber, Emmanuel Candès, Aaditya Ramdas, and Ryan J Tibshirani. Predictive inference with the jackknife+. The Annals of Statistics, 49(1):48--507 2021.
[5] Rina Foygel Barber, Emmanuel J. Candès, Aaditya Ramdas, and Ryan J. Tibshirani. The limits of distribution-free conditional predictive inference. arXiv, abs/1903.04684, 2020.
[6] Samyadeep Basu, Philip Pope, and Soheil Feizi. Influence Functions in Deep Learning Are Fragile, 2021.
[7] M. J. Bayarri and O. Berger. The Interplay of Bayesian and Frequentist Analysis. Statistical Science, 19(1):58- 80, 2004.
[8] Anthony Bellotti. Constructing normalized nonconformity measures based on maximizing predictive efficiency. In Alexander Gammerman, Vladimir Vovk, Zhiyuan Luo, Evgueni Smirnov, and Giovanni Cherubin, editors, Proceedings of the Ninth Symposium on Conformal and Probabilistic Prediction and Applications, volume 128 of Proceedings of Machine Learning Research, pages 41-54. PMLR, 09-11 Sep 2020.
[9] The boston housing dataset. 2021-05-27.
http://lib. statt cmu. wdt.eaaaaaattttbostoo Accessed:
[10] Hadi Fanaee-T and Joao Gama. Event labeling combining ensemble detectors and background knowledge. Progress in Artificial Intelligence, pages 1-15, 2013.
[11] Adam Fisch, Tal Schuster, Tommi S. Jaakkola, and Regina Barzilay. Efficient conformal prediction via cascaded inference with expanded admission. In International Conference on Learning Representations, 2021.
[12] Yarin Gal and Zoubin Ghahramani. Dropout as a Bayesian approximation: Representing model uncertainty in deep learning. In 33rd International Conference on Machine Learning, ICML 2016, 2016.
[13] Leying Guan. Conformal prediction with localization. arXiv,
2020.
[14] László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. Distribution- Free Theory of Nonparametric Regression. Springer Science & Business Media, 2006.
[15] José Miguel Hernández-Lobato and Ryan P. Adams. Probabilistic backpropagation for scalable learning of bayesian neural networks. In Francis R. Bach and David M. Blei, editors, Proceed- ings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Conference Proceedings, pages 1861-1869. JMgR.org, 2015.
[16] Kin family of datasets. httt:://ww..s..tronttooooo. cessed: 2021-05-27.
html Ac-
[17] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.

---

[18] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1885-1894. PMLR, 06-11 Aug 2017.
[19] Benjamin Kompa, Jasper Snoek, and Andrew Beam. Empirical frequentist coverage of deep learning uncertainty quantification procedures. CoRR, abs/2010.03039, 2020.
[20] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances Neural Information Processing Systems, 2017.
[21] Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry Wasserman. Distribution-Fre Predictive Inference for Regression. Journal of the American Statistical Association, 2018.
[22] Jing Lei and Larry Wasserman, Distribution-free prediction bands for non-parametric regression. Journal of the Royal Statistical Society: Series (Statistical Methodology). 76(1):71-966 2014.
[23] Zhen Lin, Cao Xiao, Lucas Glass, M. Brandon Westover, and Jimeng Sun. SCRIB: set-classifier with class-specific risk bounds for blackbox models. CoRR, abs/2103.03395,, 2021.
[24] Elizbar Nadaraya. Nonparametric Estimation of Probability Densities and Regression Curves. Kluwer Academic Publishers, 1989.
[25] Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In Tapio Elomaa, Heikki Mannila, and Hannu Toivonen, editors, Machine Learning: ECML 2002, pages 345-356, Berlin, Heidelberg. 2002. Springer Berlin Heidelberg.
[26] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019.
[27] Raghunathan Ramakrishnan, Pavlo Dral, Matthias Rupp, and Anatole von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific Data, 1, 2014.
[28] Raghunathan Ramakrishnan, Mia Hartmann, Enrico Tapavicza, and O. Anatole von Lilienfeld. Electronic spectra from tddft and machine learning in chemical space. The Journal of Chemical Physics, 143(8):08411) 2015.
[29] Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. In H. Wallach, Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[30] Lars Ruddigkeit, Ruud van Deursen, Lorenz C. Blum, and Jean-Louis Reymond. Enumeration of 166 billion organic small molecules in the chemical universe database gdb- 17. Journal of Chemical Information and Modeling, 52(1 (112:))22222888 2875, 2012. PMID: 23088335.
[31] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 19956)1199-11988 2014.
[32] Sul and Flena Chow. Globalchem: A content variable store for chemistry! com SttSSSssssieeggiaallaaaaaa
2021.
[33] Ryan J. Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal prediction under covariate shift, 2020.
12

---

[34] Athanasios Tsanas and Angeliki Xifara. Accurate quantitative estimation of energy performance of residential buildings using statistical machine learning tools. Energy and Buildings, 49:560-
567, 2012.
[35] Bike sharing data set. http:////rcabeeeeeeccc......eaaa Dataset Accessed: 2021-05-27.
[36] Concrete compressive strength data set.
concreetercmppeesssvvetttttteee Accessed: 2021-05-27.
[37] Energy efficiency data set. https: efficiency Accessed: 2021-05-27.
[38] Yacht hydrodynamics data set. hydrodynamics Accessed: 2021-05-27.
uci htt.://ww............/////atttaa
[39] Vladimir Vovk. Conditional validity inductive conformal predictors. Steven C. H. Hoi and Wray Buntine, editors, Proceedings of the Asian Conference on Machine Learning, volume 25 of Proceedings of Machine Learning Research, pages 475-490, Singapore Management University, Singapore, 04-06 Nov 2012. PMLR.
[40] Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer US, 2005.
[41] Geoffrey S. Watson. Smooth regression analysis. Sankhyā: The Indian Journal of Statistics, Series A (1961-2002) 26(4):359-37) 372, 1964.
[42] Kilian Q Weinberger and Gerald Tesauro. Metric learning for kernel regression. Marina Meila and Xiaotong Shen, editors, Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, volume 2 of Proceedings of Machine Learning Research, pages 612-619, San Juan, Puerto Rico, 21-24 Mar 2007. PMLR.
[43] Max Welling and Yee Whye Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th International Conference on Machine Learning, ICML 201 2011.
[44] Andrew Gordon Wilson and Pavel Izmailov. Bayesian deep learning and a probabilistic perspective of generalization. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria- Florina Balcan, and Hsuan-Tiee Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[45] Kevin Yang, Kyle Swanson, Wengong Jin, Connor Coley, Philipp Eiden, Hua Gao, Angel Guzman-Peree Timothy Hopper, Brian Kelley, Miriam Mathea, Andrew Palmer, Volker Settels, Tommi Jaakkola, Klavs Jensen, and Regina Barzilay. Analyzing Learned Molecular Representa- tions for Property Prediction. Journal of Chemical Information and Modeling, (970)3337,33388 2019.
[46] L.-C. Ych. Modeling of strength of high-performance concrete using artificial neural networks. Cement and Concrete Research, 28(12):1797-188)) 1998.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Section 2.2
(C) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The "exception"
might Theorem 3.2 The space is too limited so Theorem 3.2 is clearly stated and proved in Appendix in section "Proofs". Another reason for its brevity in the main text is that this is an asymptotic property which is not fully enclosed by the scope of our paper. (b) Did you include complete proofs of all theoretical results? [Yes] Full proofs in Appendix in section "Proofs". Same comment as the previous question.
If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Yes] https://gitthb. com/
Zlin7/LVD
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] In the Appendix due to space constraint.
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes]
(d) Did you include the total amount compute and type resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] We reported the most expensive experiment (QM9). Other experiments run very fast even on personal laptop.
you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] We only used public data and codes. We do our best in listing the licenses in the Appendix (Section "Data").
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes] We provide our own code at wtthtps: //gi thub. com/ 21in7/LViI
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [Yes] We only used public data and codes. We do our best explaining this in the Appendix (Section "Data").
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applica-
ble? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board
(IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "TSgO2umePU6", "reviewer": "Reviewer_nv6c", "summary": "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\n\n\n*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:\n\nhttps://www.stat.cmu.edu/~ryantibs/papers/conformal.pdf ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Main comments:\nI like the combination of kernel regression and split conformal inference. Overall, I found the method compelling and backed by a solid theoretical argument, though I found the experimental results somewhat limited, both in terms of the interval construct methods that were evaluated, deep learning models, and datasets. There also is a semantic confusion (see above) around confidence vs prediction intervals that warrants addressing. \n\nAdditionally, the method relies on the assumption that neural nets (i.e. the embedding function) learns a mapping such that \"similar\" inputs end up mapping near to each other in this new space. I believe there is a lot of evidence in the literature for this assumption but it is worth making this assumption explicit.\n\n\n### Detailed comments:\n\n__Originality__: The work is original and combines two ideas to produce a novel uncertainty quantification procedure for deep learning models. Note, however, very similar ideas have been explore for non-deep learning models in the statistical literature, e.g.:\n\nhttps://www.tandfonline.com/doi/abs/10.1080/01621459.2012.751873\n\n__Quality__: The experiments are of high quality and I offer some suggestions for strengthening them below:\n\n- The investigation into conditional coverage is limited to tail coverage and, given it is listed as one of the central contributions of the paper, I would like to see more empirical evaluations where other, non-tail subsamples are evaluated. \n\n- Given the close relationship between kernel methods and Gaussian Processes, it would be nice to include a GP in this comparison. Given the size of some of the datasets, I appreciate GPs could be expensive but it would be nice to see the comparison of how a 90% posterior interval from a GP performs.\n\n- Evaluations on other kinds of architectures (e.g. CNNs) would also greatly strengthen the results.\n\n- Prior evaluations of marginal coverage properties of Bayesian and non-Bayesian deep learning models should be acknowledged:\n\nhttps://arxiv.org/abs/2010.03039\n\n__Clarity__: The work is clearly presented and I found text and experiments easy to follow.\n\n__Significance__: The work addresses an important topic and will be of interest to applied and theoretical researchers.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}, {"review_id": "ObIPRYwAcnp", "reviewer": "Reviewer_nQpG", "summary": "The paper focuses on quantifying predictive uncertainty through conformal prediction framework. While classic conformal guarantees are marginal (over calibration and test data), the authors aim to take a step forward towards conditional validity, which is itself an important question as typically a user prefers an uncertainty set that is conditional on a given input.", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "A question of conditional validity for the conformal framework has received a lot of attention over the past years. On the theory and clarity side, the paper contains significant flaws. I believe that even formalizing the problem, e.g., validity in section 2.2 requires revisiting. The writing can also be improved substantially as the paper contains a large number of typos. Examples include (there are many more):\n1. Links to the equations are entered manually instead of using hyperlinks (line 87 --> \"E.q. 2\", lines 101 and 103).\n2. Line 112 --> missing fullstop. \n3. I believe that the citation given on line 93 is incorrect. \n4. Equations are parts of the sentences (punctuation is needed).\n5. In general, it is important to differentiate between confidence and prediction intervals not to introduce confusion. Authors focus on the latter while referring to the former. \n\nFinally, regarding the empirical evaluation, I am not convinced that presented simulations illustrate the conditional validity of the proposed procedure. Conditional validity is easy to study at least through simulated examples (see, for example, Romano et al. \"Classification with Valid and Adaptive Coverage\", which is in the classification setting but might point out relevant ideas).\n\nUnfortunately, the current work seems not to be ready to be accepted to the conference. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The question of uncertainty quantification has a huge impact on the applicability of ML models in real-world settings and thus is receiving a lot of attention in the research community these days. Unfortunately, the current work does not clearly explain the limitations of the proposed procedure, and the comparison with alternative frameworks is questionable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "HQYzh3FgTD", "reviewer": "Reviewer_bNhT", "summary": "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.\n\nThe 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$).", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "On the whole I was quite impressed with this paper. The authors write clearly throughout. Experimental setup is reasonable, and Figure 1 in particular provides a succinct picture for their motivation.\n\nI was left with a few questions and suggestions:\n\n1/ How does the smoothness requirement affect the confidence interval estimates? It would be interesting to repeat the procedure of say Table 3 and 4 as an ablation study to determine its necessity.\n\n2/ It would be helpful to explicitly define Mean Absolute Deviation (MAD) in Section 4.2. \n\n3/ Pearce et al. ICML 2018 directly measures the Mean Prediction Interval Width instead of the MAD, as a measure of discrmination. I'd be curious to see that added as a sub-table of Table 4 (perhaps in the Appendix), to compare the two evaluation metrics.\n\nMiscellaneous comments, typos:\n\n1/ It looks like references 18, 19 are duplicates of each other.\n\n2/ Line 221: \"Conforamlized Quantile Regression\".\n\n--\n\nUpdate: I thank the authors for their response, and for pointing me to Tables 7-10 in the Appendix in particular. After reading through their response, and the other reviewers' comments, I maintain my recommendation that the paper be accepted.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors adequately addressed limitations and potential negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "9OPwNSfZogn", "reviewer": "Reviewer_kPFV", "summary": "This paper considers the problem of providing prediction intervals in the deep learning setting, leveraging the recent work \"Conformal prediction with localization\" by Guan [2019]. The prediction intervals provided by this framework are simultaneously marginally valid, as well as conditionally valid in a certain sense, unlike other conformal methods. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The empirical study done by the paper is extensive and has not been done before. However, the paper **significantly** overstates the novelty in terms of theory and methodology. The main algorithm and theoretical results heavily rely on the work of Guan [2019, 2021], as can be verified by looking at the proof in Appendix A. In particular, the conditional-style coverage result (equation (4) or Theorem 3.1) is not novel. The way the paper is written strongly indicates otherwise. I expand further on this point in the 'Writing' section below. **I strongly suggest that the authors transparently discuss the relationship to Guan's work, starting with a citation in the abstract.** I request the authors to correct me if I am missing some important theory developed in this paper which was not present in Guan's work, in which case I will reconsider my assessment.\n\n_Strong empirics_:\n\nAs far as I know Guan's proposed method of localization, although having very nice theoretical properties, has not been empirically validated in an extensive study. This paper provides such a study for real world datasets for deep learning models; Section 4 confirms that the localization framework leads to discriminative prediction intervals that are marginally valid as well as have better conditional performance. The authors have considered many standard real world datasets, compared their approach to multiple other UQ methods (conformal and non-conformal), and used multiple meaningful evaluation metrics. They comment also on the time required for training and prediction of their method vs other methods. \n\n_Methodology_: \n\nThis paper discusses learning an adaptive kernel based on the Nadaraya-Watson estimator. Guan's paper considered the localization function or kernel as fixed; thus learning the kernel using data is a new methodological contribution.\n\nOnce the kernel is learnt, from what I can tell the conformalization technique is exactly the same as Guan's paper, and so are the theoretical guarantees. Is there further development regarding the conformal methodology or theory itself which I have missed? \n\n_Writing_: \n\nThe writing is clear and easy to follow. However, I feel that there are two significant issues which make the writing unscholarly to the extent that it has affected my overall score.\n\n- **The paper seems to significantly downplay the dependence of their methodology and theory on Guan's paper.** The first mention of Guan's paper appear in passing in Section 2.2, which I found very strange. Lines 54-56: \"... most conformal methods are only marginally valid [24, 37, 19, 4]. We however seek to construct a CI conditioning on the input.\" Is there a reason for not discussing the work of Guan [12] in this context? To a reader, it appears that this paper proposes a new solution to the conditional validity problem, whereas in fact the solution used is exactly the one proposed by Guan. Similarly lines 58-66 incorrectly suggest that the method proposed by the authors is new and this problem has not been solved before. Line 286 \"This paper introduces LVD, the first locally valid and discriminative CI estimator for DL\" also suggests that the conformal methodology is new. \n\n- The standard terminology for intervals that cover the output Y_{N+1} in _all_ of the conformal literature is ‘prediction intervals’, whereas ‘confidence intervals’ would attempt to cover some parameter of the distribution of Y, such as E[Y_{N+1} \\mid X_{N+1}]. It seems that the authors have made a deliberate choice to use the term confidence intervals. Could the authors clarify the reason for this choice? If there is a strong reason, I suggest the authors discuss this in the paper. Else, I suggest to use 'prediction intervals' as is done in other papers on conformal. \n\n_Additional minor comments on writing and related works_: \n- The abstract is quite long, and contains many finer details and terminologies. These can be postponed to the introduction or discussion sections. I suggest streamlining the abstract and focusing on the 'big picture' to reach a wider audience. \n- Line 39: “Post-hoc methods are ideal because ...”. While this is common, I believe it is not a necessary property of post-hoc methods.\n- Line 50: “Such methods usually use the prediction errors from a hold-out set to ...” Such ‘split’ conformal methods are currently popular due to their efficiency and validity despite their simplicity. However the statement of the authors is a misrepresentation of the well-developed body of conformal prediction where many methods that use all of the data exist: full conformal in Vovk’s 2005 book, cross-conformal [2], jackknife+ [3], and out-of-bag conformal methods [4]. \n- The paper [1] is highly relevant and should be cited somewhere.\n- Eq. (4): Should X have a \\tilde above it? \n- Line 112: Missing period ‘.’ after closing parenthesis. \n- Line 146: The definition of R_i may be somewhat abrupt for readers unfamiliar with conformal prediction\n\n[1] https://arxiv.org/abs/1905.10634 \n\n[2] http://proceedings.mlr.press/v91/vovk18a.html\n\n[3] https://arxiv.org/abs/1905.02928\n\n[4] https://arxiv.org/abs/1910.10562 ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't think the method has any serious limitations more than other conformal methods. The authors briefly mention this in Sec 2.2. ", "review_text": "", "extra_scores": {"needs_ethics_review": "Yes", "ethics_review_area": ["Research Integrity Issues (e.g., plagiarism)"], "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three reviewers indicated acceptance, two of them with clearly positive scores. Their main arguments in favor of this paper were good methodological contributions, convincing experiments, clarity of motivation and arguments, and a convincing rebuttal that added many details and addressed most points of criticism. On the other hand, there was one clearly negative review, but during the discussion period, the other members of the review committee (including myself)  had the impression that the authors' rebuttal addressed all these pints of criticism in a detailed and convincing way. So I recommend acceptance of this paper.
Decision: Accept (Poster)