Conditional Coverage Estimation for High-quality Prediction Intervals
Authors: Ziyi Huang
Henry Lam
Haofeng Zhang
Venue:  (2021)

Abstract: Deep learning has achieved state-of-the-art performance to generate high-quality prediction intervals (PIs) for uncertainty quantification in regression tasks. The high-quality criterion requires PIs to be as narrow as possible, whilst maintaining a pre-specified level of data (marginal) coverage. However, most existing works for high-quality PIs lack accurate information on conditional coverage, which may cause unreliable predictions if it is significantly smaller than the marginal coverage. To address this problem, we propose a novel end-to-end framework which could output high-quality PIs and simultaneously provide their conditional coverage estimation. In doing so, we design a new loss function that is both easy-to-implement and theoretically justified via an exponential concentration bound. Our evaluation on real-world benchmark datasets and synthetic examples shows that our approach not only outperforms the state-of-the-arts on high-quality PIs in terms of average PI width, but also accurately estimates conditional coverage information that is useful in assessing model uncertainty. 

Under review as a conference paper at ICLR 2021
CONDITIONAL COVERAGE ESTIMATION FOR HIGH- QUALITY PREDICTION INTERVALS
Anonymous authors Paper under double-blind review
ABSTRACT
Deep learning has achieved ofate-of-the-art performance to generate high-quality prediction intervals (PIs) for uncertainty quantification in regression tasks. The high-quality criterion requires Pls to be as narrow as possible, whilst maintaining a pre-specified level of data (marginal) coverage. However, most existing works for high-quality PIs lack accurate information on conditional coverage, which may cause unreliable predictions if it is significantly smaller than the marginal cover- age. To address this problem, we propose a novel end-to-end framework which could output high-quality PIs and simultaneously provide their conditional cov- erage estimation. In doing so, we design a new loss function that is both easy- to-implement and theoretically justified via an exponential concentration bound. Our evaluation real-world benchmark datasets and synthetic examples shows that our approach not only outperforms the sate-of-the-asse on high-qualin PIs in terms of average PI width, but also accurately estimates conditional coverage information that is useful assessing model uncertainty.
INTRODUCTION
Prediction interval (PI) is poised play an increasingly prominent role in uncertainty quantifica- tion for regression tasks (Khosravi et al. 2010 2011 Galván et al.] 2017 Rosenfeld et al.] 2018
Tagasovska Lopez-Paz, 2018 2019] Romano al. 2019; Wang al. 2019 Kivaranovic al., 2020). A high-quality PI should be as narrow as possible, whilst maintaining a pre-specified level of data coverage or marginal coverage (Pearce al., 2018). Compared with Pls obtained based on coverage-only consideration, the "high-quality" criterion is beneficial in balancing between marginal coverage probability and interval width. However, the conditional coverage given a feature, which is critical for making reliable context-based decisions, is unassessed and missing in most existing works on high-quality Pls. In the presence of heteroskedasticity and model misspecification, the be very different from the conditional coverage at given point, which af- marginal coverage decision-making making task that relies on the uncertainty information provided by the fects the downstream decision PI. Our main goal is meaningfully incorporate and assess conditional coverages in high-quality Pls.
Conditional coverage estimation is challenging for two reasons. First is that the natural evaluation metric of conditional coverage error, an L distance between the estimated and ground-truth con- ditional coverages, is difficult to compute it requires obtaining the conditional probability given feature x, which is arguably as challenging as the regression problem itself. Our first goal in this paper to address this issue by developing a new metric called calibration- conditional cov- erage error for conditional coverage estimation measurement. Our approach is inspired from the calibration notion in classification (Guo et al.] (017). The basic idea is relax conditional coverage at any given point to being averaged over all points that bear the same estimated value. An estima- tor satisfying the relaxed property is regarded as well-calibrated. In regression, calibration-bas conditional coverage error provides middle ground between the enforcement of marginal cover- age (lacking any conditional information) and conditional coverage (computationally intractable). Compared with conditional coverage, this middle grouund metric be viewed "dimension duction" " of the conditioning variable from the original sample space to the space [0, 1]. so that we can easily discretize compute the empirical metric values.

---

Under review as a conference paper at ICLR 2021
The second challenge is the discontinuity in the above metrics that hinders efficient training of Pis that are both high-quality and possess reliable conditional coverage information. To address this, design a new loss function based on combination of the high-quality criterion and a coverage assessment loss. The latter can he flexibly added as a separate module to any neural network (NN) used train Pls. is based
empirical version of tight upper bound on the coverage error in terms of a Kullback-Leible (KL) divergence, which can be readily employed for running gradient descent. We theoretically show how training with our proposed loss function attains this upper- bounding value via a concentration bound. We also demonstrate the empirical performance of our approach in terms of PI quality and conditional coverage assessment compared with benchmark methods.
Summary of Contributions: (1) We identify the conditional coverage estimation problem as new challenge for high-quality Pis and introduce a new evaluation metric for coverage estimation. (2) We propose an end-to-end algorithm that can simultaneously construct high-quality PIs and generate conditional coverage estimates. In addition, we provide theoretical justifications the effectiveness of our algorithm by developing concentration bounds relating the coverage assessment loss and con- ditional coverage error. (3) By evaluating benchmark datasets and synthetic examples, empir- ically demonstrate that our approach not only achieves high performance on conditional coverage estimation, but also outperforms the state-of-the-art algorithms high-quality PI generation.
2 EVALUATING CONDITIONAL COVERAGE FOR HIGH- HIGH-QUALITY PIS
Let X X' and Y E y C R be random variables denoting the input feature and label, where the pair (X, Y) follows an (unknown) ground-truth joint distribution (X,, Y). Let +(Y ()) be the conditional distribution of Y given X. We are given the training data D == { y:), i 1,2,.... .n) where (Iz, Wi) are i.idd. realizations of random variables (X, Y). A PI refers to an interval [L(x)) Ux)) where L. U are two functions mapping from X' to y trained on the data D. [xx),, (x)] is called a PI at prediction level 1 - a (0 S & S 1) if its marginal coverage is not less where with respect new test point
than 1 a, i.e. P[Y E (L(X),
(X,Y)~ ~T.
We say that [L(x), (x)) is of high-quality if its marginal coverage attains pre-specified target prediction level and has a short width on average. In particular, a best-quality PI at prediction level a is an optimal solution to the following constrained optimization problem:
min (X) L(X)] subject to P|Y E L.U
UJ 2-
(2.1)
The high-quality criterion has been widely adopted in previous work (see Section 6). However, this criterion alone may fail to carry important model uncertainty information at specific test points. Consider a simple example where x Uniform(0. 1).
0 for E [0, 0.95] and w/æ ~ Uniform[0, 1] for x E (0.95, 1]. Then according to equation 2.1 a best-quality 95% PI is precisely L(x)= (x) 0 for all æ [0, 1]. This PI has nonconstant coverage if we condition at different points (1 for x E [o, 0.95] and for x E (0.95, 1)), and can deviate significantly from the overall coverage 95%. More examples to highlight the need of obtaining conditional coverage information can be found in our numerical experiments in Section 5.1
To mitigate the drawback of the high-quality criterion, we define:
Definition 2.1 (Conditional Coverage and Its Estimator). The conditional coverage associated with PI [L(z), (z)] is A(z) := P|Y E [L(X), U, x] for a.e. x X, where taken with respect to (Y) For a (conditional) coverage estimator P, which is a measurable function from X' to [0, 1), we define its L conditional coverage error (C.Ep) as
CF = |PlY e (I(X).
p(x)) LP(X)
where the LP-romm is taken with respect to the randommess of X (1 S S +00).
Note that evaluating CE relies approximating the conditional coverage A(x), which can be as challenging as the original prediction problem. To address this, we leverage the similarity of estimating A(x) generating prediction probabilities in binary classification, which motivates to
2

---

Under review as a conference paper at ICLR 2021
borrow the notion of calibration in classification. This idea is based on relaxed error criterion by looking at the conditional coverage among all points that bear the same coverage estimator value, instead of conditioning at any given point. The resulting error metric then only relies on probabilities conditioned on variables a much lower-dimensional space [0, 1] than X. To explain concretely, introduce "perfect-calibrated coverage estimator" as:
Definition 2.2 (Perfect Calibration). A coverage estimator P is called a perfect-calibrated coverage estimator associated with [Lx,,, (())] if it satisfies
P(x) = PPY E [L(X), (X)),, P(X)) - P(x)]. a.e. P(x) E (0,
(2.2)
where a.e. is with respect the probability measure on [0, 1] induced by the random variable P(X).
Equation 2.2 means that point x with conditional coverage estimate P(x) p has average coverage of precisely among all points in X' that possess the same conditional coverage estimated value. That is, the average coverage of the PI restricted on the subset {a E X' P(x) = p} should be precisely p. Corresponding Definition 2.2 we define:
Definition 2.3 (Calibration-bass) based Error). An L (1 S p +oo) calibration- conditional coverage error, or coverage error for short (CE,), of coverage estimator P is:
C= ||lL [IXX), ((()) P(X) 20(00
(2.3)
where L -r-norm is taken with respect to the randomness of P(X).
In the above definition the conditional probability PLY E [L(X), U, P(X)] is measur- able function of random variable P(X), say 7 (P(X)) By change of variable,
= -%o 17(1) 1Pd (())()
C - (1xx) -
P
=
(2.4)
LP(X)
where (x) is a probability distribution of P(X) on [0, 1]. Here, CEE,, only requires estimating (t) for t [0, 1]. which can be done easily by discretizing [0, 1] for empirical calculation. We call the empirical T.P calibration-basee conditional coverage error F.C.pp. More details of this empirical
error can be found in Appendix A.4
calibration- error CEE,, provides a middle ground between the enforcement of marginal coverage and conditional coverage. The ground-truth conditional coverage is perfectly calibrated, but not vice versa. However, we enforce the perfect calibration criterion for coverage estimator to hold when restricted any measurable subset in X, then the choice of estimator will reduce uniquely to the conditional coverage (Definition A..I and Lemma A.2). In this sense, CEE, is an error metric that is natural relaxation of C'Ep, and although less precise, CEp is computationally much more tractable than Cp
Evaluation Metric for Coverage Estimator. We use ECE, as the primary evaluation metric to measure the quality of a coverage estimator. A high ECE, value of a coverage estimator indicates an unreliable coverage estimation while small ECE, value indicates that the coverage estimator close to the perfect-calibrated property. Ideally, an effective algorithm should output a coverage estimator with small ECF; value.
METHODOLOGY
We propose a novel end-to-en algorithm, named coverage assessment network (CaNet), to simulta- neously generate a coverage estimator along with the high-quality PI. As illustrated in Figure [ our CaNet consists of two major modules: (1) predictor module and (2) coverage assessment mod- ule (Ca-Module). The predictor module provides the upper and lower bound of the estimated Pls. Meanwhile, the Ca-Module is added to the output layer to access the conditional coverage infor- mation of PIs from the predictor module. Our model is jointly optimized by three loss functions: coverage assessment loss LCA. intervals width loss L7w, and coverage probability loss Lcp. Ben- efited from these powerful modules, the CaNet can generate and validate the coverage estimator at the same time without any requirement for further post-processing steps.
3

---

Under review as a conference paper at ICLR 2021
Output layer:
4 Aneeurons.....
Predictor module
L(x)
Sort
LIW, LCP
1/2
U(x)
Pxx)
LCa
Softmax
1 - (x)
Coverage module
Figure 1: The framework of our proposed coverage assessment network (CaNet).
Coverage Assessment Module. Our Ca-Module consists of two neurons fully connected to last hidden layer to estimate the conditional coverage. After passing through the softmax activation function, it outputs two-point probability distribution P(z), P(x) where P(x:) is the coverage estimator of the PI from the predictor module. Our Ca-Module can be easily integrated into the output layer of deep neural networks estimate their conditional coverage.
Loss Function Design and Tuning Procedure. Our loss function is a sum of the predictor loss and much possible,
the coverage loss. The predictor loss aims narrow the prediction intervals while maintaining specified marginal coverage of data. Inspired by (Khosravi et al. 2010 2011 Pearce et al., 20188) Rosenfeld (IW) loss Liw and coverage probability (CP) loss LCP:
2018), our predictor loss formed by the
intervals width
LIW 1 n
(U())) L(xi)),
(3.1)
LCP Σ Ki CP
kis
(3.2)
where k; indicates whether each data point has been captured by the Pls: k; = 1 if [(x;) S v < U(x;) and k; 0 otherwise. i; is soft version of k; which is defined as: i a (>s(U(z;) (As(3i - L(x))),, where Å3 2 0 a tunable parameter and (t)) == Ite is the sigmoid function. Therefore, LCP is a soft version of CP that can be used for gradient descent. Associated with the Ca-Module, introduce coverage assessment loss LCa to estimate the conditional coverage:
LCA = - Σ k; Log((())) + (1 k;) log(1 -P(x)))
(3.3)
We will show in Section that the expectation of coverage assessment loss LC provides an upper bound for both the conditional coverage error DDeiiitionn2.1 and calibration-based conditional cov- erage error (Definition 2.3). Hence, minimizing Le contributes the recovery of the conditional coverage. In order to run gradient- based methods, we replace the discrete indicator (k, 1 - k,) in LCA with its soft version (k,, 1 -kk):
LcA = Σ (kg Log(( + (1- R;)) log(1 P(xx))
(3.4)
Our total loss function for the CaNet defined
Total Loss Lrw + >1 LCP) + 12
(3.5)
where A 2 0, A2 2 O are tunable parameters. We propose an aasy-to-implemen yet effective tuning procedure pick up these parameters. Please refer to Appendix D for more algorithm details.
Deep Ensembles. Following previous research (Lee et al. 2015 Lakshminarayanan et al. 2017
Pearce al. 2018) Fort et al. 2019 Ovadia al.) 2019 Gustafsson et al.] 22020; Pearce et al. 2020). we apply the deep ensemble technique to provide more robust and better results. During the training period, with the same hyperparameters λ₁ 2, m networks trained with different

---

Under review as a conference paper at ICLR 2021
initializations. The prediction results from i-th network are denoted as: (L,)), P.(x), (.())). Finally, the output from CaNet is:
Lower bound Upper bound
L
U = Σ Li=1 U,
(3.6)
Coverage estimator
P = E 1 P;
4 THEORETICAL ANALYSIS
In this section, we provide theoretical insights that minimizing LCa equivalent to minimizing a tight upper bound of the conditional coverage error and thus can recover the true conditional cover- age. To achieve this, we first prove that both C and CEEp are bounded above by the expectation of a Bellbackk-eebblee divergence-type random variable K1 (X)). Then we show that Lca is an empirical counterpart of (x and establish a concentration bound between LC and [X)]. [L(X), U( U, X = x] be the conditional coverage in A(x)
Theorem 4.1. Let A(x) = IP|Y E
Definition 2.1 Let K (z) = A(x) log
+(1 (1 A(x)) log [-A(x
Then
P(z)
P(x)
ap/2
CEe S CE V ( [(((X))
1 +00
where Up = 1, S S and ap 3. V2 S p S +oG Moreover, the inequality is attainable if. e.g., P(x) equals the conditional coverage A(x).
From Theorem 4.1 we see that minimizing E (xr) is equivalent to minimizing a tight upper bound for the coverage error. For every x, (xx) is the Kullback-Leibler divergence between the distribu- tions represented by (P(x), 1 P(x)) and (A(z), - A(x)). K(x) Ko(#) + K (ar), where Ko(x) = A(x) log(A(z) + (1 1L--A A(x)) log(1 - A(x)) and K1 = -A(x) log( (())) - (1
(xx)) log(1 P(x)). Minimizing [X)] over is equivalent to minimizing (X), The type of results Theorem 4.1 that bounds an L" conditional coverage error a Kullback-Leibler type error is new as far as we know. Next, to show LCs approximates (X)], we need the following assumptions:
Assumption 4.2. The four classes of functions ([T(s), P(x), 1- Pxx)) output by the neural network (NN) in Figure I have finite VC dimensions, say they are bounded above by Vo.
Assumption 4.2 holds for wide range of NNs (e.g.. Theorem 8.14 in Anthony & Bartlett (209))
Theorem in Bartlett et al. (2019)). In particular, it holds for the one we adopt in the experiments (where we use the ReLU-activated NN to construct th,, = 1, 2, 3, 4; see Section 5):
Theorem 4.3. Suppose v,, i 2,2,3, are the using the ReLU activation function. Then Assumption 4.2 holds. Moreover, suppose the NN has W parameters and U computation units (nodes). Then Vo OWUU).
output neurons of the NN in Figure
Assumption 4.4. log( ((()))))))))))))))))))))))))(( < M, |log(1 P(x))) < M for all x and P.
This natural assumption in practice because log(P and log(1 P())) are replaced by log( ((x) + +) and log(1 f(x) + +) respectively to avoid explosion when implementing the algo- rithm. In particular, in our experiments in Section 5, e = 0.1% and thus M = 14. Let
F [f< v) = [vE[L(=),U((0] : L, U are output by the NN),
G (p(x) P is output by the NNJ.
Theorem 4.5. Suppose Assumptions 4.2 and 4.4 hold. The training data D {1zi, W:), 1,2, nn where (2,, v:) are i.i.d. samples ~ n. Recall that the (hard) coverage estimator assess-
ment loss ICA= = Σ (f(,, log( (P)))))())))))))))))))())))))( + (1 -f(1,, (() log(1 P(x:))) Then for
any 0, we have
sup - [[Kx
21 SCe
I6M
ter_PeG
where C* only depends on Vo in Assumption 4.2
5

---

Under review as a conference paper at ICLR 2021
Theorem 4.5 shows that the coverage assessment loss approximates B[K( well with expo- nential tail bound. The difficulty in analyzing Theorem 4.5mm lies in the fact that the hypothesis classes in Assumption 4.2 (which
constructed by the NN) different from the hypothesis class used in I-CA- To overcome this difficulty, we use the theory of VC-suhgraph classes to connect the VC dimension among multiple hypothesis classes, including the class of 4/s, the four classes of output functions, and F, log G. Then we establish the covering number bound for the class F and log G, and finally prove Theorem 4.5 To conclude, minimizing E[K1 over P is equivalent to mini- mizing E K (X)]. which in turn is minimizing a tight upper bound for the coverage assessment loss. Our coverage assessment loss empirically approximates R well, so that its minimization can ultimately reduce the conditional coverage error.
EXPERIMENTS
Experimental Setup. We empirically verify the effectiveness of our proposed CaNet on both syn-
thetic examples and benchmark regression datasets. These datasets have been widely used for the
evaluation of methods in regression tasks HHernández-Lobal & Adams (2015) 5 Gal & Ghahramani
2016 Lakshminarayanan et al., 2017 Rosenfeld al. [2088] Pearce et 2018 2018/ZZu et al.] [219))- In addition, we adopt the same experimental procedure in Pearce et al. (2018) for data normaliza- tion and dataset splitting. To avoid overfitting, we apply simple network architecture with only 2 hidden layers and each hidden layer has 64 neurons. For each hidden layer, the ReLU activation function is applied to capture the non-linear features. We empirically set the ensemble number m to 5, as the smallest number leading to a stable prediction results. Please refer to Appendix E for implementation details, including those for baseline algorithms.
Evaluation Metrics. To evaluate the conditional coverage estimation of our CaNet, we exam- ine the quality of our Ca-Module measured by the empirical coverage error ECE; over a par- tition A. A is constructed by equally dividing the width of [0. 1] into M sub-intervals. The value of depends on the size the dataset, which is determined by the following strategy: . In addition, we also report the /W and
M = min [te number of data in validation/500 CP, where IW = E (U;, L(x))) (.quation and CP E,=1 ky, (equation 3.2 to show the effectiveness of our predictor module under the high-quality criteria.
1,20
5.1
CONDITIONAL COVERAGE ON SYNTHETIC EXAMPLES
1.0
0.6
0.50
0.5
3.00
6.5
0.0
0.5
-31
4A
0.75
Saves hound
1.5
-2.0
-1.
+1.
08
20
(a) 81
0.1 (0,1))
(b) 82 0.1|x| N(01
E3
0.1|x|
X
Figure 2: Prediction and conditional coverage 95% PIs on synthetic examples. (a) CP 0.95, IW = 0.40, ECE; 0.62%. (b) CP = 0.96, !W = 0.40, ECE, 0.12%. (c) CP 0.95, IW 0.50, ECE, 0.65%. The predicted coverage estimation from CaNet highly consistent with the conditional coverage under different noise settings.
In this section, we conduct a series of experiments on synthetic examples to directly compare our prediction results with the ground-truth conditional coverage. In these examples, the conditional coverage can be analytically calculated under the known data distribution. Figure compares the conditional coverage with predicted coverage under the following settings: x Uniform| 2 and y| is drawn from fa (x) = sin( xr) + (2),, x E [-2, 2] where
e (x) 0.1 N 1), $2(x)) [x1 N(O, 1),
Ea(x) 0.1|pc] x 14.

---

Under review as a conference paper at ICLR 2021
[ 1) is the standard Gaussian variable and t is the standard t random variable with degrees of freedom. Then, the conditional coverage in Definition 2.1 can be analytically calculated as:
1
PIY e (XXX), (z) sin(c)) - P.(((a) sin(
NNKCDE
QRF
SCL
QD-Ens
CaNet: A2 = 0.1 19 for all dalasets
Dataset
CP
IW
CP
SW
CP
IW
CP
/W
CP
/W
ECE;
A
Ag
Boston
0.95
1.54
0.92
1.16
0.95
1.44
1.38%
6.0
1800
Concrete
0.95
1.85
0.99
2.53
0.96
1.54
0.94
1.09
0.95
1.13
0.24%
6.5
1001
Energy
0.97
0.97
0.47
0.99
0.37
0.76%
Kin8am
0.99
2.76
0.99
3.27
0.94
1.20
0.96
1.25
0,95
1.04
1.32%
3.6
300
Plant
0.95
0.88
0.97
1.05
0.95
0.88
0.95
0.86
0.95
0.84
0.38%
3.3
700
Protein
0.93
1.98
0.98
2.42
0.95
2.81
0.95
2.27
0.95
2.26
0.41%
8.3
300
Wine
0.96
2.64
0.93
3.18
0.96
3.44
0.92
2.33
0.95
2.59
0.42%
19
1100
Yacht
0.96
0.98
0.16
Table I: Evaluation metrics of different models on benchmark datasets. The CP values are marked in blue if they meet the 95% prediction level. The best IW results, marked in bold, are achieved by models with the smallest IW value among those that meet the 95% prediction level. Our model outperforms the baseline algorithms on high-quality PI generation. Meanwhile, it provides accurate coverage estimation on real-world datasets.
Kin8om:
0.1
300 ECE;
Plant: 0.1
Às
700 ECE;
Protein:
0.1º,
A1
CP
IW
A
CP
IW
CP
IW
ECE,
1.9
0.83
0.73
1.54%
1.4
0.80
0.56
1.23%
4,8
0.82
1.56
0.82%
2.1
0.85
0.77
1.50%
0.84
0.62
1.36%
5.1
0.86
1.70
0.71%
2.3
0.87
0.80
1.47%
0.85
0.63
0.86%
5.4
0,88
1.79
1.25%
2,4
0.88
0.84
1.21%
1.8
0.86
0.64
1.36%
5.6
0.90
1.84
1.04%
0.90
0.87
1.50%
0.51%
0.91
2.9
0.91
0.89
0.50%
2.4
0.91
0.75
1.15%
6.5
0.92
2.07
1.36%
3.1
0.92
0.94
0.49%
2.6
0.92
0.80
1.29%
7.0
0.93
2.11
1.23%
3.4
0.94
1.00
0.82%
3.0
0.94
0.83
0.23%
7.8
0.94
2.13
0.99%
3.6
0.95
1.04
1.32%
3.3
0.95
0.84
0.38%
8.3
0.95
2.26
0.41%
3.8
0.96
1.06
1.25%
0.96
0.89
0.80%
9.3
0.96
2.36
0.52%
Table 2: ECE, results of our model on benchmark datasets with different coverage probabilities. Our CaNet achieves robust performance on real-world datasets at different prediction levels.
where F; is the cumulative distribution function of (0, 0.1²) for 1, NO0 (0.1x)²) for i = 2, and 0a1|a] & for 3. As shown in Figure 2 the conditional coverages of high-quality PIs at different points diverge among each other and they deviate from the marginal coverage. Thus, having access to the marginal coverage for the whole dataset not sufficient for decision making, which highlights the need of conditional coverage. In addition, the predicted coverage estimator of our model is highly consistent with the conditional coverage on all of the synthetic examples. These results confirm that our CaNet accurately estimate the conditional coverage on noisy datasets.
5.2 PERFORMANCE OF PIs ON BENCIMARK DATASETS
In this section, we compare the predictor module of our CaNet on real-world benchmark datasets with following baseline algorithms: (1) nearest-neighhors kernel conditional density estimation
(NNKCDE) (Dalmasso al. 2020). (2) quantile regression forest (QRF) (Meinshausen 2006),
(3) split conformal learning (SCL) (Lei et al. 2018) and (4) the quality-driven PI method (QD-Ens)
comparison since we share the same experiment setup. Table (ibble[rree reports the results of C., 7W and ECE, for generating PIs at 95% prediction level on benchmark datasets. We employed the criteria in Pearce et al. (2018) to evaluate the performance of Pls: the best IW is achieved by the model with the smallest /W value among those with CP 2 95%. As can be seen, our model achieves the best performance on PI generation under the high-quality criteria. With special consideration interval width quality, obtains the smallest average interval width (IW) while maintaining high coverage probability (CP 2 95%) on all datasets.
PPaaree et al., al., 2018). We quote the results from (Pearce et al. 2018)
7

---

Under review as a conference paper at ICLR 2021
5.3 PERFORMANCE OF COVERAGE ESTIMATOR ON BENCHMARK DATASETS
Coverage for 95% Pls. We use ECE, to evaluate the coverage estimation performance on real- world datasets as the conditional coverage is unknown. As shown in Table [ the ECE; on all experiments are generally around or less than 1%, with better performance on larger datasets. The coverage estimators produced by CaNet have small ECE1 values, which
very close to the perfect-calibrated coverage estimators (Definition 2.2). Compared with ECE; values obtained from the state-of- of-the-art art algorithms in classification tasks (Guo al. 2017: Kull et al. 2019), the ECE, values from CaNet are similar and sometimes less than their post-calibrate ECE, results (usually around 1% 3%), even though the size of most regression datasets are smaller than the classifica- tion datasets. These results further demonstrate that our CaNet can accurately estimate the coverage information of 95% high-quality PIs on real-world regression tasks.
Coverage for PIs at Different Prediction Levels. We conduct multiple experiments on different PI prediction levels to show the robustness of our CaNet. By only modifying the parameter Å in Equation 3.3 our Ca-Module could get access to different levels of coverage probability. Table 2 reports the CP. IW and ECE, values from the CaNet at different benchmark datasets. Results for more datasets can be found in Appendix [.] As can be seen, all ECE, values in Table fairly small (~ 1%), demonstrating the stability of our proposed model. Thus, our CaNet can provide accurate coverage estimation on PIs at different prediction levels. These results demonstrate the robustness of our CaNet on real world datasets, further suggesting its broad applicability.
prediction levels on three
RELATED WORK
Prediction Interval Estimation. High-quality Pls, which can be viewed via a constrained optimiza- tion problem where the constraint concerns marginal coverage and the objective is the PI width, has been extensively studied in Khosravi et al. (2010; 2011;; Galván et al. 2017); Pearce et al. (2018); Rosenteld et al. 2018); Zhang et al. (2019) Zhu et al. 2019). Such intervals are in the same spirit the highest density intervals in statisties [Box & Tiao 201T). While powerful, these approaches could not directly provide the conditional coverage information investigated in this work. Coverage- only criteria, on the other hand, focus solely on coverage satisfaction as the guarantee. These ap- proaches include conformal learning (CL) and its conditional variants (Vovk et al.) [2005] 2009; Lei
& Wasserman, 2014; Lei al. 2015, 2018 Kuchibhotla & Ramdas] 2019, Romano et al. 2019]
Barber et al.) 2019a b). CL is desirably distribution- or model-free, and in many cases enjoys finite-
sample guarantees. However, unlike high-quality Pls, they do not explicitly account for the interval width as quality metric. We also mention conditional density estimation (Holmes et al. [007 Du-
tordoir et al. 2018 Izbicki & Lee| 2016: Dalmasso et al., 2020; Freeman et al. 201 7| Izbicki et al. 2017) and closely relatedly quantile regression (Koenker & Hallock] 2001 Meinshausen, (006) as
Pl construction approaches by converting from the estimated conditional quantile function. These approaches focus on the quality of conditional distribution/quantiie. instead of the high-quality cri- terion only. In this work, we use deep learning to construct high-quality PIs (Khosravi et al.) 2010 Pearce et al. 2018 Kivaranovic al. 2020).
Uncertainty Measurement in Deep Learning. The Bayesian framework offers principled ap- proaches for model uncertainty measurement by computing the posterior distribution over the NN parameters (MacKay 1992] Neal 2012). These approaches can also be used to construct Pls. How- ever, they provide a different perspective from the frequentist view taken in this paper, and they focus on the parameter uncertainty of the NN instead of the coverage over a test point. In addi- tion, exact Bayesian inference is computationally intractable for deep neural networks, making less practical to implement. Gal & Ghahramani (2016) applied a Monte Carlo dropout method to proxy the inference. Directly generated from the networks, softmax response is also commonly used for uncertainty measurement deep learning models (Bridle 1990 Lakshminarayanan al.) 2017 Geifman et al. 2018 Sensoy et al., 20188 Ozbulak et al. 2018). Moreover, Niculeseu- & Caruana (2005) showed that NNs typically produce well-calibrated probabilities binary clas- sification tasks without the need of any post-hoc techniques. In this paper, we also follow this line of work and use the softmax output to access the model uncertainty information.
8

---

Under review as a conference paper at ICLR 2021
7 CONCLUSION
In this paper, we identify and investigate the conditional coverage estimation problem for high- quality Pls, which is critical for risk-based decision making regression fields. To address the challenge, propose an end-to-end algorithm with two powerful modules: coverage assessment module and predictor module. Benefited from these powerful modules, our model can generate and validate the coverage estimator without any requirement for further procesrogsssing steps. In addition, we conduct theoretical analysis to show the effectiveness of our proposed model. Exper- imental results synthetic examples and benchmark datasets further demonstrate that model can robustly provide accurate coverage estimation while simultaneously producing a high-quality PL Moreover, Ca-Module can be easily integrated into other Seep-learning-Dee baged algorithms to get access to their coverage information, opening up more opportunities for broad applications. In the future, will extend our work by conducting comparison studies with Bayesian methods.
REFERENCES
Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations. Cambridge University Press, 2009.
Rina Foygel Barber, Emmanuel Candes, Auditya Ramdas, and Ryan J Tibshirani. The limits of distribution-Fi conditional predictive inference. arXiv preprint 3XXiv:990300484 2019a.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. Predictive inference with the jackknife+.. arXiv preprint 1905.0990. 2019b.
Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC-dimension and pscudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1-17, 2019.
George EP Box and George Tiao. Bayesian inference in statistical analysis, volume 40. John Wiley & Sons, 2011.
John S Bridle. Probabilistic interpretation of feedforward classification network outputs, with rela- tionships to statistical pattern recognition. In Neurocomputing, pp. 227-236. Springer, 1990.
Niccolò Dalmasso, Taylor Pospisil, Ann Lee, Rafael Izbicki, Peter Freeman, and Alex Malz. Conditional density estimation tools in python and with applications photometric redshifts and likelihood-free cosmological inference. Astronomy and Computing, 30:100362, 2020.
Vincent Dutordoir, Hugh Salimbeni, James Hensman, and Mare Deisenroth. Gaussian process con- ditional density estimation. In Advances in neural information processing systems, pp. 2385- 2395, 2018
Stanislav Fort, Huiyi Hu, and Balaji Lakshminarayanan. Deep ensembles: A loss landscape per- spective. arXiv preprint 19X.v:191..02757, 2019.
Peter E Freeman, Rafael Izbicki, and Ann B Lee. A unified framework for constructing, tuning and assessing photometric redshift density estimates in selection bias setting. Monthly Notices of the Royal Astronomical Society, 468(4):4556-4555 2017.
Yarin Gal and Zoubin Ghahramani. Dropout bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pp. 1050-1059, 2016.
Inés M Galván, José M Valls, Alejandro Cervantes, and Ricardo Aler. Multi-objective evolutionary optimization of prediction intervals for solar energy forecasting with neural networks. Information Sciences, 118:363-382. 2017.
Yonatan Geifman, Guy Uziel, and Ran El- Yaniv. Bias-reduced uncertainty estimation for deep neural classifiers. In International Conference Learning Representations, 2018.

---

Under review as a conference paper at ICLR 2021
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1321-1330. JMLR. org, 2017.
Fredrik K Gustafsson, Martin Danelljan, and Thomas B Schon. Evaluating scalable bayesian deep learning methods for robust computer vision. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition Workshops, pp. 318-319, 2020)
José Miguel Hernández-Lobato and Ryan Adams. Probabilistic backpropagation for scalable learn- ing of bayesian neural networks. In International Conference on Machine Learning, pp. 1861- 1869, 2015.
Michael P Holmes, Alexander G Gray, and Charles Lee Isbell Jr. Fast nonparametric conditional density estimation. In Proceedings of the Twenty-Third Conference Uncertainty in Artificial Intelligence, pp. 175-182, 2007.
Rafael Izbicki and Ann B Lee. Nonparametric conditional density estimation in high-dimensional regression setting. Journal of Computational and Graphical Statistics, 25(4):1297-1316, 2016.
Rafael Izbicki, Ann B. Lee, and Peter E. Freeman. Photo-z estimation: An example of nonparamet- ric conditional density estimation under selection bias. Ann. Appl. Stat., 11(2))698-724, 06 2017. doi: 10.1214/16-AAAS001 URL https:://ooiiiiio wtg. 214/16 AOAS1013
Abbas Khosravi, Saeid Nahavandi, Doug Creighton, and Amir F Atiya. Lower upper bound estima- tion method for construction of neural network-based based prediction intervals. IEEE transactions on neural networks, 22(3):337-345 2010.
Abbas Khosravi, Sacid Nahavandi, Doug Creighton, and Amir F Atiya. Comprehensive review of neural network- prediction intervals and new advances. IEEE Transactions on neural nehworks, 22(9):1341 1341-1356.11 2011.
Danijel Kivaranovic, Kory D Johnson, and Hannes Leeb. Adaptive, distribution-free prediction intervals for deep networks. In International Conference on Artificial Intelligence and Statisties, pp. 4346-4356, 2020.
Roger Koenker and Kevin Hallock. Quantile regression. Journal of economic perspectives, 15(4): 143-156, 2001.
Michael R Kosorok. Introduction to empirical processes and semiparametric inference. Springer Science & Business Media, 2007.
Arun Kuchibhotla and Aaditya Ramdas. Nested conformal prediction and the generalized 2019.
jackknife+. arXiv preprint
Meelis Kull, Miquel Perello Nieto, Markus Kängsepp, Telmo Silva Filho, Hao Song, and Peter Flach. Beyond temperature scaling: Obtaining well-calibrated multi-class probabilities with dirichlet calibration. In Advances Neural Information Processing Systems, pp. 12295-12305. 2019.
Ananya Kumar, Percy S Liang, and Tengyu Ma. Verified uncertainty calibration. In Advances in Neural Information Processing Systems, pp. 3787-3798, 2019.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Informaiinn Processing Systems, pp. 6402-6413, 2017.
Stefan Lee, Senthil Purushwalkam, Michael Cogswell, David Crandall, and Dhruv Batra. Why m heads are better than one: Training a diverse ensemble of deep networks. arXiv preprint arXiv: 151 1.063 14, 2015.
Jing Lei and Larry Wasserman. Distribution-fie prediction bands for non non-maraettric regression. Journal of the Royal Statistical Society: Series (Statistical Methodology). 76(1):71-8)) 2014.
10

---

Under review as a conference paper at ICLR 2021
Jing Lei, Alessandro Rinaldo. and Larry Wasserman. A conformal prediction approach explore functional data. Annals of Mathematics and Artificial Intelligence, 74(1-2):29 43, 2015.
Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113 (523):1094-1111, 2018.
David JC MacKay. Bayesian methods for adaptive models. PhD thesis, California Institute of Technology, 1992.
Pascal Massart. Concentration inequalities and model selection, volume 6. Springer, 2007.
Nicolai Meinshausen. Quantile regression forests. Journal of Machine Learning Research, 7(Jun): 983-999, 2006.
Radford M Neal. Bayesian learning for neural networks, volume 118. Springer Science & Business Media, 2012.
Alexandru Niculescu-Mizil and Rich Caruana. Predicting good probabilities with supervised learn- ing. In Proceedings of the 22nd International Conference Machine Learning, pp. 625-632, 2005.
Jeremy Nixon, Mike Dusenberry, Linchuan Zhang, Ghassen Jerfel, and Dustin Tran. Mcasuring calibration in deep learning. arXiv preprint arXiv: 1904000904 2019.
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. In Advances Neural Information Process- ing Systems, pp. 13991 1-1 14002, 2019.
Utku Ozbulak, Wesley De Neve, and Arnout Van Messem. How the softmax output is misleading for evaluating the strength of adversarial examples. arXiv preprint arXiv:1811.08577 2018.
Tim Pearce, Mohamed Zaki, Alexandra Brintrup. and Andy Neely. High-quality prediction intervals for deep learning: A distribution-fiee ensembled approach. arXiv preprint arXiv:1802.07166 2018.
Tim Pearce, Felix Leibfried, and Alexandra Brintrup. Uncertainty in neural networks: Approxi- mately bayesian ensembling, In International conference on artificial intelligence and statistics, pp. 234-244. PMLR, 2020.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. In Advances in Neural Information Processing Systems, pp.
2019.
Nir Rosenfeld, Yishay Mansour, and Elad Yom-Tov. Diseriminative learning of prediction intervals.
In International Conference on Artificial Intelligence and Statistics, pp. 347-355, 2018.
Murat Sensoy, Lance Kaplan, and Melih Kandemir. Evidential deep learning to quantify classifica- tion uncertainty. In Advances Neural Information Processing Systems, pp. 3179-3189, 2018
Eduardo D Sontag. VC dimension of neural networks. NATO ASI Series F Computer and Systems Sciences, 168:69-96. 1998.
Natasa Tagasovska and David Lopez-Paz. Frequentist uncertainty estimates for deep learning. arXiv preprint arXiv:1811.0000 2018.
Natasa Tagasovska and David Lopez-Paz. Single-model uncertainties for deep learning. In Advances in Neural Information Processing Systems, pp. 6417-6428, 2019.
Aad W Van der Vaart and Jon A Wellner. Weak Convergence and Empirical Processes with Appli- cations to Statistics. Springer, 1996.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer Science & Business Media, 2005.
11

---

Under review as a conference paper at ICLR 2021
Vladimir Vovk, Ilia Nouretdinov, Alex Gammerman, et al. On-line predictive linear regression. The Annals of Statistics, 37(3):1566 1590, 2009.
Bin Wang, Jie Lu, Zheng Yan, Huaishao Luo, Tianrui Li, Yu Zheng, and Guangquan Zhang. Deep uncertainty quantification: machine learning approach for weather forecasting. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 2087-2095. 2019.
Haozhe Zhang, Joshua Zimmerman, Dan Nettleton, and Daniel Nordman. Random forest predic- tion intervals. The American Statistician, pp. 1-15, 2019.
Lin Zhu, Jiaxing Lu, and Yihong Chen. HDI-forest: highest density interval regression forest. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 4468 4474. AAAI Press, 2019.
12

---

Under review as a conference paper at ICLR 2021
This Appendix presents further results and discussions and it consists of five parts. Appendix A gives more detailed properties on coverage estimator and coverage error. Appendix B contains the mathematical argument for Theorem 4.1 Appendix C
discusses how to achieve Assumption 4.2 and the proof of Theorem 4.3 and 4.5 Appendix [ presents our algorithm details as a supplement to Section Appendix Billustrates experimental details and more experimental results.
A FURTHER DETAILS ON COVERAGE ESTIMATOR AND COVERAGE ERROR
A.1 COVERAGE PROBABILITY TYPES OF PIs
Zhang et al. (2019) introduce the following four coverage probability types of Pls. In general. most of the coverage in PIs considered in the literature falls into one of these types.
Type P[Y E UXX]] (marginal coverage);
Type II: PlY E [L(X), (X)]] U] (conditional coverage given the Pl);
Type III: P.Y E (X)]), xx] (conditional coverage given X = x:);
Type IV: P(V E ([(X). U, xz] (conditional coverage given the PI and X = 2).
Note that in high-quality criteria, only Type II coverage is considered in the constraint but Type IV coverage is lacking. Since Type I and III are not considered in our paper, for simplicity Type II coverage is called the marginal coverage, and Type IV coverage is called the conditional coverage in Definition 2.1
Throughout Appendix. we let A(x) == P|Y (())), U, x| denote the conditional coverage in Definition 2.1 Moreover, since we only concern Type II and IV coverage in this work, we make the following convention. Throughout the Appendix A P and E should be understood as probability and expectation conditional on I, U. So for A(r), we could simply write A(x) == P|Y E [L(X), UX))||X x and omit "conditional on L, U
A.2 THE TERMINOLOGY "PERFECT-CALLIRATTE"
The terminology "perfect-calibrated" is borrowed from the confidence calibration in classification tasks. We first review the name of "confidence" in classification.
Confidence calibration is the problem of predicting probability estimates representative of the true correctness likelihood (Guo et al. (017). Intuitively, an reliable confidence should reflect the true correctness likelihood of the prediction (Kumar et al. 2019). For example, given 100 predictions, each with confidence of 0.8, we expect that 80 should be correctly classified (Guo et al. 2017).
Now let & be the prediction of any models, which is map from X' to V, trained on the data D. According to their definition, the "best" confidence map P should be the true probability of correct- ness:
((x) E. ((())) is conect for Y X x= = sr), Va X
(A.1)
in regression tasks and "correctness" of PI is naturally defined the success of coverage on the outcome Y. Then the right hand side of Equation A.T becomes
which is a measureable function from to J0. 1]. In particular, we consider
E M(X) is comect for y hh, X x|
E[1 (xx) =
P|Y E U(x)),(X) =].
which is the conditional coverage in our Definition 2.1 In addition, Guo et al. (017)) introduce the perfect-calibrated confidence as follows:
IP-Y =YIÝ, P= p E E [0,
where Y is the class prediction and Y Y means that the predicted and true class label coincide. Obviously, if P(X) = (X) YJX), i.e., the "best" confidence, then the above equality holds.
Transferring this idea into Pls. we can naturally define the calbect-c coverage estimator as
p E[1x(X) is correct for y [L, U, P pl PlY e which is the conditional coverage in our Definition 2.2
U, P = pl, Vp E [0, 1).
13

---

Under review as a conference paper at ICLR 2021
A.3 DETAILS ON COVERAGE ESTIMATOR
A perfect-calibrate coverage estimator inherits some properties of a conditional coverage. For example, both of them have the following interpretation: If have 1000 testing points for Pl, each with the same conditiioal/peffcct-aaiiine correctly covered by the PI. Note that the conditional coverage is uniquely defined, but perfect- calibrated coverage estimator is not necessarily so. Moreover, we have the following facts: (a) The conditional coverage always perfect-calibrated, but not vice versa. (b) perfect-calibrated coverage estimator can be viewed as an averaged conditional coverage. (c) A perfect-calibrated coverage estimator less "informative" than the conditional coverage.
coverage 0.9, then approximately 900 of them are
perfect-calibrated coverage estimator is an averaged conditional coverage. Let İ be a (gen- eral) coverage estimator. We have
P|Y [4(X), P(x)]
=P(Y e (
PY E (L(X), E (-
P|X E P P-)((()))
SeEP (P(x)) E Ex = t][[X e dt)
PiX P-1(())
StEP-1((E)) A(U)P(X E de)
P[X E P-)()()))
Suppose is perfect-calibrated coverage estimator. Then we have
P(x) (Ee(-1(())) A())((X E di)
P(X P-1((()))
which implies that P(x:) is weighted average of A(I) over the set p~1(((x:)) with weights based on the marginal distribution of X.
A conditional coverage is perfect-calibrated. If P(x) A(x), then A(I) A(x) for any t A (A(x())) so
S(EA-1(A))) A(t)P[X dt] A(x) SEA ((A()) P[X dt] E P(XEA=((A(z)))
A(x).
P|X E A-
This shows that A(x) must be perfect-calibrater coverage estimator. Another way to this is taking conditional expectation given A(X) = p in the Definition 2.1 Then we get
p E[A(X) = p]
= =[[PYY E [L(X), U(X)))(() = pl
= =P[Y E [L(X),
pl by the tower property.
A perfect-calibrated coverage estimator may be less informative and may not be the condi- tional coverage. Suppose we have a PI [T.(X), UX)] at the exact prediction level of a, i.e., P|Y E (XX)),U(X)] =1 - a. Then the constant coverage estimator
((x) a, Vr X
can be viewed an average coverage estimator over the entire space X. It is a perfect-calibrated coverage estimator since by definition,
IP e (x(X), - = P|Y e [X(X), =
P(x).
But it is not conditional coverage in general (e.g., the second synthetic example in Section 5).
Now we give an extension of the definition of "perfect-calibrated" coveraag estimator, allowing it to be defined on any measurable subsets.
14

---

Under review as a conference paper at ICLR 2021
Definition A.1. A coverage estimator P is called perfect-calibrarce coverage estimator measurable subset S X with P(S) > associated with [L(x), Ux)) it satisfies
P E (X))
= P(x), X S]: a.e. P(x) E [0,
(A.2)
where a.e. is with respect the probability measure [0, induced by the random variable P(X)ls. Note that the conditional probability space standard: (8,Fs {AnS A
FJ, F) == P(A)S)).
(As our convention in Section A.1 we will omit "conditional on L, U for simplicity.)
Lemma A.2. (a) A coverage estimator is the conditional coverage if and only it is perfect- calibrated coverage estimator on any positive-probabliiy measurable subset S of X. (b) Suppose P is a perfect-calibrated coverage estimator on two disjoint pestiiveproobability mea- surable subsets Sr. S2. Then P is perfect-calibrated coverage estimator on S U2.
Proof. (a) The proof can be found in Lemma A.4
(b) We note that by law of total probability,
PI
p. X, Si US
p, -PlY e [XXX),(X))])((() - X S|PPX E ( S US
+ + [[(X),,((X)])(x))====))))) = S s,) E e US
-p[[X- E SiI(() -, x E (2) P(X E = US.)
=p.
Hence P is caliecct coverage estimator S U.2.
Lemma A.2 a) is motivated from theoretical point of view. It provides guidance that in order to well resemble the conditional coverage, an estimator should be perfect-calibrated on as many subsets on the feature space possible.
A.4 DETAILS ON COVERAGE ERROR
In Section 2, we have introduced CEEp to quantify the discrepancy between coverage estimator and cerfect-calibrated coverage estimator, and C'Ex, quantify the discrepancy between a coverage estimator and the conditional coverage. We note that by Hölder's inequality
CE S CE. for 1 Isps q 2 +00.
A larger value of corresponds to larger CE value. Continuing Definition A.1
we can further
introduce the calibration- based conditional coverage error on measurable subset follows:
Definition A.3. An LP p S +00) calibration based conditional coverage error, or coverage error for short, of a coverage estimator P on a measurable subset C X with P(S) is defined
as:
CE = |PLYY
(A.3)
(P(S)
where -P-norm is taken with respect to the randommess of P(X) on the conditional probability space (S,Fs == (AnS: A E F),P((An = =(ASS))). In particular, we have CEp- (2)
Lemma A.4. A coverage estimator P is the conditional coverage if and only if its coverage error CEp(S) = for any measurable subset S C X with P(S) 0. In particular. coverage esti- mator is the conditional coverage if and only if it is cerfect-calibrated coverage estimator on any measurable subset S of X with TP(S) O.
15

---

Under review as a conference paper at ICLR 2021
Proof. We first show that the conditional coverage is perfect-calibraee. Taking conditional expec-
tation given (A(X) = p.X E S} in the Definition 2.1 Then we get
p E[A(X))A(X) - p. E E
E[P[Y [L(X), U()))((X)) = p, X e. E
= P/Y [[(X), = P. E S] by the tower property.
So A(x) is perfect-calibrated coverage estimator any measurable subset S with P(S) > 0.
Hence (SE = for any measurable subsets S C X with P(S) >
On the other hand, similarly to Section A.3
express
JIEP- A(t)P[X dt)
P(x), P[Y E -
P[X E P-1(P(x)) nS]
Suppose P(x) is not the conditional coverage, then P[P(X) * A(X)) > 0. Without loss of
generality, assume P[P(X) A(X)] > 0. Let S. = { X : P(x) A(z)) Note that Sp t {o
P(x)= A(x) + #). Since P(S,) > 0, there exists a no such that = far E X P(x) > A(x) + ) and P(S) 0.
Then for x E S, we have
JEE--CPCOnns A(t)) dt)
heep" 1 dt] P(xx) no
no
P-
P(X E P- (-)((()))
Then we have
CEp(S) 2 CE((S)
0
n1
(S) 0, which is contradiction. Hence P(z) is the conditional coverage.
Next, we describe in detail how to discretize the right-hand-siee of equation 2.4 for empirical cal-
culation. We construct discrete version of (2.2) and then introduce an empirical counterpart of C'Ep 2.3 which we refer to as L empirical calibration- based conditional coverage error ECEp,
The ideas behind these are natural extensions of the classification case (Guo et al., 2017 Kull et al.)
2019 Kumar al. 2019: Nixon et al. 2019) into PIs.
We consider the following partition A of [0, 1]. Let [0, be divided into M intervals Im
(am-11, [m]] (m = 1, ... MM where = ag S 01 .... aM = 1. Let Bn, = 1, 1,...,... P(x;)= E ]m i.e., the set (bin) of indices é of samples whose prediction coverage estimator P(x;) falls into the interval I,. Note that coverage estimators that are close to each other will fall into the same interval. The coverage probability (i.e., the proportion of successful coverage) in Bm is defined
cp(Bm) = [Bm BE
1
Σ [EELL()))
(A.4)
The average estimated coverage in Bn defined as:
cove(B..)
Σ P(aa)
(A.5)
Bm
sEBm
where P(z;) is the coverage estimator for sample i. cm( and cove(Bm) approximate the left and right hand sides of (2.2) respectively in the interval Im- A perfect-calibrated coverage estimator
should satisfy ep( B,,)) = cove( (,,)) for all m {1..... .M). The diagram of cp(Bm) versus cove Bm)) for all m E (1...., .M) is called the reliability diagram in some literature (Guo et al. 2017)
Based on the partition A, we can introduce an empirical version CE (which we refer to as FCFF, as:
16

---

Under review as a conference paper at ICLR 2021
Definition A.5.
The L empirical calibration-basa conditional coverage emorr (ECE,) of erage estimator P is defined as
Ep = [[(p((m(t)) cove (mtt))))=122 mllee
(A.6)
where the IP is the standard p-norm in IR" and Buat)) is the bin containing sample Equivalently,
B
ECE3
|cp( Bm) - cove(Bm))
1sp < +00.
n
m==1
ECE,2
max mm=1,,..
(m)) - cove((m)))
Note that Ep is discontinuous and cannot be used easily for training with gradient-based meth- ods. Therefore, we use the coverage assessment loss Lca introduced in Section for conditional coverage estimation.
Finally, we give some explanations about why the conditional coverage error CEE, cannot be used easily for training. Unlike LC which is unbiased and provides guaranteed estimation accuracy for K|K (X)] (Theorem 4.5). it is in general not easy to establish an empirical calculation for C'E'p Take CE2 as an instance. heuristic argument is to use
h4 P(x)))²
71
to approximate
CE B[JA(X) -()=) P(X)
where h; = 0 or 1 indicates whether each data point has been captured by the PIs; see Section 3
Unfortunately, ò is in general not an unbiased estimator of CE2 due to the following observations:
B[g] = El(ki P(x1))
= [[(k: P(x:))
= E E[k]| 2P(x)) + P()))
= E 2PPm P(x1)
= E
A(x1) - ((z))) P(x1)?]
E A(x1) 2P(22 ) P(x)) + E[A(x1) - A(x1)
A(X) -()(() )
Hence B(0] * CE unless A(X) 0 or 1 almost surely. Note that the gap B[A(X) - = does not depend on n and thus not vanish as n grows. To obtain a reasonable estimator for CEp. one need more information about A(x) besides the marginal coverage [[A(X)). However, this information is usually hard to obtain locally because of the nature of (possibly high-dimensional) feature space. In fact, this has led us to the idea of "dimension reduction" of the sample space the space [0, and the definition of Ep.
B MATHEMATICAL DEVELOPMENTS FOR THEOREM 4.1
This section proves Theorem we show that both coverage error and conditional coverage error are tightly bounded above by the expectation of Kullback-Leibler divergence-type random vari- able K2 (z). This means that minimizing E [{[{(X) (X)] can recover the true conditional coverage and effectively reduce the coverage error. The proof consists of several inequalities regarding coverage enrors and their relations. We first begin with the following connection between C C.Ep, and CFp..
17

---

Under review as a conference paper at ICLR 2021
Theorem B.1. For any Pl and its associated P, the L" coverage envor is always less than or equal to the LP conditional coverage error, i.e..
CE S
CEp, CE
s to0
Proof. We note that the function + ||| is a convex function. We also note that o ((((X) C (X) where (Y) represents the --filld generated by a random variable Y.
CE =E A(X) P(x)
-E
BAA(z) - P(X) PIP(X))(X)]
B[A(E) P(X))P(X))
>F
by Jensen's inequality
E[Lyeeux),cxx) |(x)/"] P(x))
=E
by the tower property
=CE
Therefore we have
CE S CEp. s toc.
Next we have the following bounds on L conditional coverage error:
Theorem B.2. The L conditional coverage error is bounded above by power function of the L conditional coverage error. Formally,
CE S CE v1 t00,
where op 1, S P and op
2 Sp +00.
Proof. By Hölder's inequality,
CE S CE2, if 52
Since
0 [A(x) - P(x) $1,
then,
-(=)) & AA(x) - P( vp22
and thus
CE p = E[A(()) P(X) B(IA(X) $( Vp
Next, recall that
A(x)
+(1 A(x)) log - A(x)
K(x) = A(x) log
P(x)
P(x)
Ko(x) A(x:) log A(x)) + A(=)) log(1 A(x)),
Ki Kx(x) A(x) log( P(x)) - (1- A(x)))) log(1 P(x)).
Theorem B.3. The L conditional coverage error is bounded above by the expectation of K(x) Formally,
[(((X))
0,/2
CE2
where Oep defined in Theorem B.2
18

---

Under review as a conference paper at ICLR 2021
Proof. For any fixed æ, consider two random variables with Bernoulli distributions:
W1 {
w.p. A(x),
w.p. A(x).
W w.p. P(x))
w.p. 1 - P(x).
Let P: be the distribution of W, It follows from Pinsker's inequality, e.g., Theorem 2.16 in (Massart 2007). that
|P - Paliv - 1 2 (P))
where TV denotes the total variation distance and K denotes the KL divergence. Since Pe is the Bernoulli distribution, we can express it as
A(x) P(x)1 S 1 K(x)
Taking expectation, we obtain
E [(A(X) P(X) [[]( [[((())
Hence,
CF2 S )
0./2
Combining Theorem B.I
B.2 and
B.3
we immediately conclude that:
Theorem B.4 (Restated Theorem
CE S CE s CE s (HE(K()))
ap/2
VI
where Opp is defined in Theorem B.2 conditional coverage A(x).
Moreover, all inequalities are attainable, egg, if P(x) is the
C JUSTIFICATION OF ASSUMPTION 4.2 AND MATHEMATICAL
DEVELOPMENTS FOR THEOREM 4.5
In this section, we analyze the rationality of Assumption 4.2 and build essential ingredients for proving Theorem 4.3 and 4.5 The difficulty in analyzing Theorem 4.5) lies in the fact that the hypothesis classes in Assumption 4.2 (which constructed by the NN) different from the hypothesis class used LCA. To overcome this difficulty, we use the theory of VC-subgraph classes to analyze the connection between the VC dimension of the two hypothesis classes.
C.1 REVIEW OF THE VC DIMENSION
For self-contained purpose, we first review the definition of the VC-subgraph class and VC dimen- sion.
Definition C.1. Consider an arbitrary collection (xz,... FnA of points in set X and a collection of subsets of X. We say that C shatters - In if all 2" possible subsets of {xI,... ,nn can be written C is the smallest n. fofor which no set of size n {-z,... }n is shattered by C. IfC shatters sets of arbitrarily large size, we set V(C)- co. We say that C is VC-class if VC) oc.
= C n {II,... ,Inn for some C' E C. The VC dimension (C) of the class
In some literature, the VC dimension VCC) of the class C is alternatively defined as the largest for which there exists set of size n ( _n) shattered by C, i.e. is the value in definition C.I minus 1. We more formally define the VC dimension by the growth function follows:
19

---

Under review as a conference paper at ICLR 2021
Definition C.2. Define the nthh shatter coefficient (or growth function) of C as
[e(n) = max
A= In) for some C E CH
Then
V(C) == inf(n: I[((n) < ).
f:X- - IR, the subset of X x R given by {(x,1) : 1 {()) is the (open) subgraph of f. A collection F of measurable real functions on the sample space is VC-subgraph class or VC-class, the collection of all subgraphs of functions in F forms a VC-class of sets (as sets in X x RR. Let V(F) denote the VC dimension of the set of subgraphs of F.
Definition C.3. For a function
Lemma C.4. In Definition C.3
the open subgraph of f. {(x,() : [(x),, can be replaced by
the close subgraph {(x,)) 1)
S. {(x)), ) the close supergraph {(x,1) : 2 f(x) or the open
supergraph {(x,t) :t > fx)) All of them lead the equivalent definition of the VC-class and the equal VC dimension.
Proof. This result follows from Lemma 9.33 and Lemma 9.9(iv) in Kosorok (2007).
For indicator functions of sets, we have the following equivalence.
Lemma C.5. For any class C of sets in set X, the class Fc of indicator functions of sets in C is VC-class if and only if C is VC-class. Moreover, whenever at least one of C or Fe is VC-class, the respective VC dimensions are equal.
Proof. This is Lemma 9.8 in Kosorok 2007 Note that the sets of C. are in X' while the subgraphs of functions of Fe are in x R.
C.2 JUSTIFYING ASSUMPTION
We first restate the assumption:
Assumption C.6 (Restated Assumption ).2 The four classes of functions ([)() P(x), 1 P(z)) output by the neural network (NN) in Figure have finite VC dimensions, say they are bounded above by Vo-
In Figure 1, the output four neurons of the NN are denoted as (L(x), U(r), 1())), We further let (1h (x), (2(x), vz(x), vb(()) denote the pre-activated values of (L()) P(z)). In other words,
L(x) (x),
U(x) (ax,
P(x) = softmax (o) = (Va(2z) - (z)()))
1 P(x) = () (1 (x) v>)())),
where is the sigmoid function. Let the function classes
Hi {L(x): L is output by the the NN).
H2 = {U(z)) U is output by the the NN),
g (P(x): P is output by the NN).
1- g = (1 P(x)) P is output by the NN}.
Assumption 4.2 holds for a wide range of NNs, in particular the one we adopt in the experiments (where we use the ReLU-activated NN construct th;, i 1, 4 see Section 5). Our first result is to concretely show that the four NN outputs above, Hi. Ho, G and 1 - G, under the ReLU setting, all have finite VC dimensions and thus satisfy Assumption 4.2
Theorem C.7 (Restated Theorem 4.3 Suppose V,,i 1, 2. 4 are the pre-activated output
rons of the NN in Figure 7 Jusingg the ReLU activation function. Then Assumption 4.2 holds. More- over, suppose the NN has W parameters and U computation units (nodes). Then Vo O(WU).
20

---

Under review as a conference paper at ICLR 2021
Proof. First, look at L(x) and (x)). Note that the class of dy (i = 1, is constructed by NN with the ReLU activation function. Therefore by Theorem in Bartlett et al. (2019) (see also C.8 below),
(((h))) = O(WU) < 00; V((v)))= = O(WU) <0.
By Lemma 9.9 (i) in Kosorok (0007) we have
V(Hi) V(fmin(V1,, v/2)3) S v(for)) V O(WU) < 00.
By Lemma 9.9 (ii) in Kosorok (2007), have
((H2) V((maxx(11) (1)1, ((())) + + ((v=2) 1 O(WU) <
Next, we look at P(x) and P(x). We add an additional neuron after the layer where 1/3, the stand. This neuron is defined as th = th dh which is a linear combination of 4/s and th4- Note that the class 4 is constructed by a NN with the ReLU activation function and linear activation function (by adding one unit and two parameters in the originial NN). Therefore by Theorem 8 in Bartlett et al. (2019).
v({vs}) O(WU) <0
By Lemma 9.9 (viti) in Kosorok (007)) we have
V(G) = (((o())))) s v((v5)) = O(WU) < <0. since a is a monotone function. Again, by Lemma 9.9 (viii) in Kosorok (2007), we have
V(1 - 9) V(g) = OWWU) < cc.
since 1 / monotone function.
We also list some results for other activations here. From these results, and using the same argument as above, we see that Assumption 4.2 holds similarly for all these activations.
Lemma C.8. Suppose the class of functions is constructed by a NN with W parameters and U units with activation functions that are piecewise polynomials with at most pieces and of degree at most Then it has VC dimension O(WU log((d 1)p)).
Proof. This is Theorem 8 in Bartlett al. 2019).
Note that the activation functions in Lemma C.8 include in particular the ReLU activation and linear activation.
Lemma C.9. Suppose the class of functions is constructed by a NN with W parameters with binary as well as linear activation function. Then it has VC dimension O(W?).
Proof. This Theorem 5 in Sontag 1998).
Lemma C.10. Suppose the class of functions is constructed by a NN with W parameters and U
units with activation function that is the standard sigmoid function (except that the output unit being a linear threshold unit). Then it has VC dimension O(W2U?).
Proof. This Theorem 8.13 Anthony & Bartlett 2009)
C.3 CONNECTIONS AMONG DIFFERENT HYPOTHESIS CLASSES
To prove Theorem 4.5 we need to study several building blocks the relations between different hypothesis classes. Our first observation is:
Theorem C.11. Suppose V(g)
+00.
Then all of the following classes have VC dimension
S (G):
1 - G : (1
P(x) P is output by the NN).
G' = log(g) = {log( {log(P(x)) is output by the NN).
log(1 9) (log(1 P(x))) P is output by the NN).
21

---

Under review as a conference paper at ICLR 2021
Proof. The result follows from Lemma 9.9 (viii) in Kosorok (2007) since all of the transformations are monotone functions.
Our second observation is about
F= {f(x v) (e(((()).U(()) : L, U are output by the NN).
Note that the domain of functions in JF is different from the domain of functions in H, (2 = 1, as includes the outcome space. Below we derive a result that connects the VC dimension of Hi with that of F.
Theorem C.12. Suppose V(H)) - V. (i 1,2). We have that
V(1 F) - V(F)= v 10(Vo 1) < 400
where
- F = (1 f(x,)) F}.
Proof. The first inequality follows from Lemma 9.9 (viii) in Kosorok (0077). We consider the following two classes:
= (Tus)) L E H1. E R).
F2 = (1o()2 : U H2. E R].
Since the functions in Fi are all indicator functions, by Lemma C.5
((Fi) = ((t((z,t) L(x) S LE LE HH,,
Note that the latter is the VC dimension of the close supergraphs of all functions in H4. Then by Definition C.3 and Lemma C.4. we have
V([((z,t) ((x) St) LE H4.t R)) = V(H4)
Therefore we have
V(Fi V((H)) S Vo
Similarly,
V(F2) v(Hb) S Vo
Note that we can write By the definition of growth functions,
[)((5(0) = Lt(
11=(m)= ==
max (x1.2)) he (2m (8m)
| |1 (lm.e LE H1, U E H2H
max
[((T)o))sm II (Smm L E HiH
(x1.20) y 8mm
((11(1))2mm" (2m))) :: UU H2}
(21.9)),- (3mm
=I (m)) (m)
2(V--1)
em
Vo=
for all m 2 Vo where the last inequality is due to the Sheurh lemma. Taking m 10(V- - 1),
we obtain
2(V--1) = (10c) (10c)2(6-1)) < v-0 2m
em
VO -1
Combining the above inequality, we have
mm(m) < n
This shows that V(F) < m 10(V - 1).
22

---

Under review as a conference paper at ICLR 2021
C.4 PROOF OF THEOREM 4.5
This subsection proves Theorem 4.5 Recall that
== (((()(()) L, U are output by the NN),
G (P(x) P is output by the NNJ.
:'==log(9) (log(P(x)) P output by the NN).
Let F,,,F, denote the covering number, i.c., the minimal number of balls {g llg A(LEPIQ) <() of radius needed cover the set F. We need the following bounds:
Lemma C.13. Suppose F is class of functions f X x + V(F). For every 0 < <cl,
10, 1] with finite VC dimension
(1) +
sup log N(c,F, - K2
Q
where the constant K2 depends ((F) only.
Proof. It follows from Theorem 2.6.7 in Van der Vaart & Wellner (1996) that there exists a universal constant K such that
sup Ne,, (V(F) V(F) (
v(F)-
Q
for any 6 < 1. Since
1 (
log ( 11). 14 =0<
2 max
have
log Ne,, < K3 (V(F) 1) log
K₂
Q
where K3 = (F and K₂ = K3 + V(F) - only depending on V
We remark that a similar result can also be obtained for the class 1 F by Theorem C.12
Lemma C.14. Suppose a class of functions P : + [0, with a finite VC dimension Vg) and log( P())) S M. Let G' = (log(P) P E G). for every 0 < e < 1,
suplog N L L - K₂
where the constant K2 depends V(g) only.
Proof. First note that @(t) := log(t) VC-class with VC dimension < (G) by Lemma 9.9 (viii) in Kosorok 2007 The rest of the proof similar C
) is monotone function. Hence = flog (P) P E g) is
We remark that similar result can also be obtained for the class log(1 9) by Theorem C.11
Next we restate Assumption 4.4
Assumption C.15 (Restated Assumption 4.4 and P.
log (P(x)) S M, log((1 - P(x)) S M for all x
As discussed Section 4, this a natural assumption practice because log( P(x))) and log(1
P(x)) are replaced by log( P(x) + c) and log(1 P(x) +) respectively to avoid explosion when implementing the algorithm. In particular, in experiments in Section 5, 0.1 and thus
M = 14.
We now ready prove Theorem 4.5
23

---

Under review as a conference paper at ICLR 2021
Theorem C.16 (Restated Theorem 4.5 Suppose Assumptions 4.2 and 4.4 hold. The training data
= {(0,, Yi), i 1,2, ... . where (o ys) are i.i.d. samples ~ т. Recall that the (hard)
coverage estimator assessment loss is
Lea --
Σ
(ogg + (1 (ar, log(1 P(aii))
Then for any t > O, we have
n2a
P
sup JEF,PEG
-LAA- - [X]] 21) SC''
1812
where C* only depends on Vo in Assumption 4.2
Proof.
Note that E[f v.)le
A(z;) for any fixed L and U. Taking expectation on LC we
have
E[Lca] = E EEaaL 22, v.,]
((4)))o((] - P(a))))
E
log(())))(()))))
= (X)]
We consider the first part A(x) log P(x)). The second part can be done using the same argument. Note that by Theorem 9.15 in Kosorok 22007), we have
sup log N(MM, F. G¹, (()) I suplog N(c/2, (Q)) + suplog NCMM/22
Consider the class 1 + 2M F G' = 1 2nd
(J log((()))) f F, F, E G'} which
consists of functions taking values in [0, 1]. We have
sup N(e,
2M F g', (())))))
2
sup log N(2, F G', (QQ))
I suplog Ne.,F, (.2(())) + sup (e,
1/e
<K₂
where the last inequality follows from Lemma C.13 and Lemma C.14 and K2 only depends on
V(F) and VG)). (Recall that we have shown V(G S V(G) in Lemma C.14) Moreover, by
Theorems C.I and C.12 we can claim that K₂ only depends on Vo. This inequality shows that 22d F g satisties the conditions in Theorem 2.14.10 in Van der Vaart & Wellner (1966) and
thus for every 5 > 0 and > O,
p(a vs) Eio(œ, v)] 2t) < CCPivvo 2nt2
sup
zur F
n
where U ((-
< 1 and the constants C' and D depend on K2 and å only. Let 6 = 1 - U. Note
that
2(vnt)2 + D(Vntt) s -(Vnt)2 + (D/2)2
Hence we have
PP
sup d
bl m1) - Elo(a, will 21 -m
F-
72
where C* only depends K2, or, only depends Vo.
24

---

Under review as a conference paper at ICLR 2021
This shows that
nr2
P sup JEF
Man vi) log(P((:)) - ((A(2) (0)))))))(((a)) 21 s SC
similar result can be established for the second part since the hypothesis classes there have been studied in Theorem C.IT and C.12
P
sup fEF,
Σ (1
((.,,:))) - P(x.)) - EE[1 - A(x)) log(1 P(x)) 21)
<C*e
4MF
Combining the two parts and noting the following fact:
{sup by + 3) t)
C(sup 1y| + sup |3 2 1
1 ((sup hy| 2 5 (sup |3| 2
conclude that
n1 16M2
sup PEF
LCA E[K (x)] 2t SC
where C only depends on Vo.
Lastly, the following corollary explicitly connects our theoretical developments to the experimental setup:
Corollary C.17. Suppose the NN is designed as the one specified the experiments (Section 5). The training data D = (a1,3:), Wi), i = 1,2, ... ,n} where (2i, Ui) are ii.d. samples ~ Then for any > we have
sup LLAA - E[Ki(] 21 SC fer,Pet PEG
where C' only depends on Vo in Assumption 4.2
Proof. We note that Assumptions 4.2 and 4.4 hold in this case by Theorem 4.3 and the observation
after Assumption So Theorem implies Corollary C.17.
D ALGORITHM DETAILS
We provide additional algorithm details for our framework in Section 3 Algorithm is the descrip- tion of our tuning procedure for Cpp and the average coverage estimation ACp on the validation set D' be defined as
I
\1, A2, Ag. Let the marginal coverage probability
CPp = DD'
[e(((())))))))) AC IED
Σ
Σ P(x:). IED'
D
where ([L(x),U() (z)), P(x)) are prediction results from the deep ensemble. Then, i = 1, 2, are adjusted ensure that CPp coincides roughly with ACD' and CPp attains the target prediction level.
E EXPERIMENTAL DETAILS AND MORE RESULTS
This section illustrates experimental details and more experimental results from proposed model.
25

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Tuning algorithm
Goal: Tune hyperparameters Aı 22; and A3:
Input: Prediction level 1 a, training dataset D. validation dataset D);
Procedure: (1) Initialize X (i 1, 2,)3) so that CP is nontrivial, i.e., not (almost) 0 or 1.
(2) While CPD' is nontrivial: tune 22 and A so that CPP'' ACD' I (e.g., 1%.)
(3) Otherwise tune λ such that CP' is nontrivial. Do step 2 again until we find A2 and X3. fixed from (3).
(4) Tune a such that CDy
where x2 and A3
Output: \1. A2, and Az.
E. EXPERIMENTAL DETAILS
Table gives a detailed description about the datasets we use.
These open-access real-world benchmark regression datasets are widely used for the evaluation of methods in regression tasks
Hemmánezz-Lobato & Adams 2013 Gal Ghahramani
2016 Lakshminarayanan al. 2017
Rosenteld et al.) 2018: Pearce et al. 2018 Zhu et 2019
For synthetic datasets, 2000 data are generated for each synthetic setting and randomly split into 1000 training data and 1000 testing data. For benchmark datasets, we first do the data normalization and then randomly split 80% data for training and 20% for testing. The choice of 80%/20% split, compared to the 90% split in Pearce et al. (2.18), is motivated from the need to increase the test size in order to get meaningful ECE evaluation. The latter is due to that evaluating ECE requires binning, where using a larger number of bins approximates more closely CEE, but also requires larger test size to sustain enough statistical quality for the resulting ECE estimate. This delicate tradeoff motivates us to increase the share of the test set in split. Following PParcee et al. (2018), our hyper-parameter are selected using the validation set from a random split. Then, they are fixed during the evaluation on other random splits.
As specified in Section 2 (Equation (2.4)) and Appendix A.4 (Equation (A.6)), ECE is evaluated based on dividing [0.1] into M sub-intervals. The larger M the more precise in using ECE to approximate CE, the latter being the ideal conditional coverage error estimator. On the other hand, a larger test set size is needed support the use of a larger M without deteriorating the statistical quality of the ECE. This delicate tradeoff motivates us to increase the share of the test set in our split.
For synthetic datasets, the hyperparameters and corresponding results in Figure 2 are:
(a) X 1.7, A2 10-5 As 1500, CP 0.95, JW = -0.40, EC 0.62%
(b) \ 129, 10-5 1.-5.33 1000, CP 0.96, JW = -0.40, ECE, 0.12%.
(c) \ = -3.4, A2 = 10-5,A3 = 1000, CP 0.95, IW = 0.50, ECE; = 0.65%.
For benchmark datasets, the implementation details for baseline algorithms in Table 1 are:
(1) Nearest-neighhors kernel conditional density estimation (NNKCDE). The algorithm is based on Section 2.1 in Dalmasso et al. (200)). We use the same Python code provided by Daammsso et al.) (2020) with the default Gaussian kernel. Two tuning parameters, i.c., the number of nearest neigh- bors k and the bandwidth h of the smoothing kernel, are chosen in a principled way by minimizing the CDE loss on validation data, the same way as in Dalmasso et al. (020)).
(2) Quantile regression forest (QRF). The algorithm is based Meinshausen (006). We use the Random/ForstQuantileeggeess. from the package scikit seikit-garden in Python.
(3) Split conformal learning (SCL). The algorithm based on Algorithm 2 in Lei al. 2018 The regression algorithm inside SCL that we use a neural network with mean square loss. The neural network has the same structure of hidden layers as in Section 5
E.2 ADDITIONAL EXPERIMENTAL. RESULTS
Table 4 gives additional experimental results.
26

---

Under review as a conference paper at ICLR 2021
Datasct
N
Open-access Link
Boston: Boston Housing
506
13
kaggle.
comm///bostonhhousingg
Concrete: Concrete Strength
1030
kaggle.com// hatal//o/o/aashhaaaac/cmmeeeeee
Energy: Energy Efficiency
768
Kin8nm
8192
8
apenml.org/d/189
Plant: Combined Cycle Power Plant
9568
kaggle..om//ooa22//irrrrrssr
Protein: Protein Structure
45730
bettorrkrppssiorr.ccoCCCCAAPPPpp
Wine: Red Wine Quality
1599
Yacht: Yacht Hydrodynamics
308
6
Table 3: Full names and details of benchmarking regression datasets. N is the number of samples
in the dataset and is the dimension of the feature vector.
experiment IW
2-nd experiment
3-rd experiment
Dataset
A
A1
CP
ECE,
A1
CP
IW
ECE,
A1
CPP
IW
ECE;
Boston
1800
3.5
0.87
0.72
1.25%
4,5
0.89
0.85
0.96%
6.0
0.95
1.04
1.38%
Concrete
1000
1.03%
5.0
0.93
1.07
0.24%
Kin8nm
300
2.1
0.85
0.77
1.59%
2.9
0.91
0.89
0.50%
3.6
0.95
1.04
1.32%
Plant
700
0.85
0.63
0.86%
2.4
0.91
0.75
1.15%
3.3
0.95
0.85
0.38%
Protcin
300
1.70
0.71%
6.3
0.91
1.95
2.26
0.41%
Wine
1100
9.0
0.85
1.59
0.98%
15
0.91
2.14
1.28%
19
0.95
2.59
0.42%
Yachi
0,96
Syntheticl
1500
1.0
0.89
0.34
0.73%
1.3
0.93
0.37
0.55%
1.7
0.95
0.40
0.62%
Synthetic2
1000
1.01%
1.4
0.92
0.34
1.27%
0.96
0.12%
Synthetic3
1000
0.87
0.34
0,79%
2.4
0.91
0,42
0.82%
0.95
0.50
0.65%
Table 4: Evaluation metrics of our CaNet on benchmark datasets and synthetic examples with dif- ferent coverage probabilities.
E.3 COMPARISONS WITH TWO-STAGE APPROACH
We compare the performance of CaNet with a two-stage approach to further demonstrate the effec- tiveness of our Ca-Module. The two-stage approach is implemented with two separate steps: (1) given regression dataset, we train neural network generate the prediction interval, (2) after getting the predictor, we train another network to estimate the conditional coverage of the PI from the previous stage using LCa loss.
the reliability diagrams (introduced A.4) and the coverage histograms of CaNet and the two-stage approach on the dataset "Protein". The coverage histograms demonstrate the per- centage of samples in each bin Bn, (equation A.5) for E {1, (1,... M). The average estimated coverage of our model closely matches its coverage probability, while the average estimated cover- age of the two-stage algorithm is substantially lower than its coverage probability. In addition, the ECE, E from CaNet (0.77% (0)7%)) is much lower than the ECE, from the two-stage approach (3.9%).
REFERENCES
Martin Anthony and Peter Bartlett. Neural network learning: Theoretical foundations. Cambridge University Press, 2009.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. The limits of distribution-Fi conditional predictive inference. arXiv preprint arXiv:1903 04684, 2019a.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. Predictive inference with the jackknife+. arXiv preprint 19050099002298 2019b.
Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 10163): 2019.
George EP Box and George Tiao. Bayesian inference in statistical analysis, volume 40. John Wiley & Sons, 2011.
27

---

Under review as a conference paper at ICLR 2021
Coverage Histogram Protein
Coverage Histogram Protein
1.0
1.0
CaNet
Two-Stage Approach
Percentage samples
0.8
0.8
0.6
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Estimated Coverage
Estimated Coverage
Reliability Diagram Protein
Reliability Diagram Protein
Estimatedd Coverage
Entimated Coverage Coverage Probablitt
Coverage Probebility
0.8
0.8
Coverage Probability
0.6
0.6
0.4
0.2
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Estimated Coverage
Estimated Coverage
Figure 3: Coverage histograms (top) and reliability diagrams (bottom) on the dataset "Protein". Left: Our proposed algorithm (ECF, 0.77%, M 3.9%, M 10).
100; Right: The two-stage algorithm (ECF,
John S Bridle. Probabilistic interpretation of feedforward classification network outputs, with rela- tionships to statistical pattern recognition. In Neurocomputing, pp. 227-236. Springer, 1990.
Niccolò Dalmasso, Taylor Pospisil, Ann Lee, Rafael Izbicki, Peter Freeman, and Alex Malz. Conditional density estimation tools in python and with applications to photometric redshifts and likelihood-frze cosmological inference. Astronomy and Computing. 30:100362, 2020.
Vincent Dutordoir, Hugh Salimbeni, James Hensman, and Marc Deisenroth. Gaussian process con- ditional density estimation. In Advances in neural information processing systems, pp. 2385- 2395, 2018.
Stanislav Fort, Huiyi Hu, and Balaji Lakshminarayanan. Deep ensembles: A loss landscape per- spective. arXiv preprint 1rX1v:1112.02757, 2019.
Peter E Freeman, Rafael Izbicki, and Ann B Lec. A unified framework for constructing, tuning and assessing photometric redshift density estimates in selection bias setting, Monthly Notices of the Royal Astronomical Society, 468(4):4556 4565, 2017.
Yarin Gal and Zoubin Ghahramani. Dropout as bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pp. 1050-1059, 2016.
Inés M Galván, José M Valls, Alejandro Cervantes, and Ricardo Aler. Multi-objective evolutionary optimization of prediction intervals for solar energy forecasting with neural networks. Information Sciences, 118:363-382. 2017.
Yonatan Geifman, Guy Uziel, and Ran El- Yaniv. Bias-reduced uncertainty estimation for deep neural classifiers. In International Conference Learning Representations, 2018.
28

---

Under review as a conference paper at ICLR 2021
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1321-1330. JMLR. org, 2017.
Fredrik K Gustafsson, Martin Danelljan, and Thomas B Schon. Evaluating scalable bayesian deep learning methods for robust computer vision. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition Workshops, pp. 318-319, 2020)
José Miguel Hernández-Lobato and Ryan Adams. Probabilistic backpropagation for scalable learn- ing of bayesian neural networks. In International Conference on Machine Learning, pp. 1861- 1869, 2015.
Michael P Holmes, Alexander G Gray, and Charles Lee Isbell Jr. Fast nonparametric conditional density estimation. In Proceedings of the Twenty-Third Conference Uncertainty in Artificial Intelligence, pp. 175-182, 2007.
Rafael Izbicki and Ann B Lee. Nonparametric conditional density estimation in high-dimensional regression setting. Journal of Computational and Graphical Statistics, 25(4):1297-1316, 2016.
Rafael Izbicki, Ann B. Lee, and Peter E. Freeman. Photo-z estimation: An example of nonparamet- ric conditional density estimation under selection bias. Ann. Appl. Stat., 11(2))698-724, 06 2017. doi: 10.1214/16-AAAS001 URL
wtg. 214/16 AOAS1013
Abbas Khosravi, Saeid Nahavandi, Doug Creighton, and Amir F Atiya. Lower upper bound estima- tion method for construction of neural network-based based prediction intervals. IEEE transactions on neural networks, 22(3):337-345 2010.
Abbas Khosravi, Sacid Nahavandi, Doug Creighton, and Amir F Atiya. Comprehensive review of neural network- prediction intervals and new advances. IEEE Transactions on neural nehworks, 22(9):1341 1341-1356.11 2011.
Danijel Kivaranovic, Kory D Johnson, and Hannes Leeb. Adaptive, distribution-free prediction intervals for deep networks. In International Conference on Artificial Intelligence and Statisties, pp. 4346-4356, 2020.
Roger Koenker and Kevin Hallock. Quantile regression. Journal of economic perspectives, 15(4): 143-156, 2001.
Michael R Kosorok. Introduction to empirical processes and semiparametric inference. Springer Science & Business Media, 2007.
Arun Kuchibhotla and Aaditya Ramdas. Nested conformal prediction and the generalized 2019.
jackknife+. arXiv preprint
Meelis Kull, Miquel Perello Nieto, Markus Kängsepp, Telmo Silva Filho, Hao Song, and Peter Flach. Beyond temperature scaling: Obtaining well-calibrated multi-class probabilities with dirichlet calibration. In Advances Neural Information Processing Systems, pp. 12295-12305. 2019.
Ananya Kumar, Percy S Liang, and Tengyu Ma. Verified uncertainty calibration. In Advances in Neural Information Processing Systems, pp. 3787-3798, 2019.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Informaiinn Processing Systems, pp. 6402-6413, 2017.
Stefan Lee, Senthil Purushwalkam, Michael Cogswell, David Crandall, and Dhruv Batra. Why m heads are better than one: Training a diverse ensemble of deep networks. arXiv preprint arXiv: 151 1.063 14, 2015.
Jing Lei and Larry Wasserman. Distribution-fie prediction bands for non non-maraettric regression. Journal of the Royal Statistical Society: Series (Statistical Methodology). 76(1):71-8)) 2014.
29

---

Under review as a conference paper at ICLR 2021
Jing Lei, Alessandro Rinaldo. and Larry Wasserman. A conformal prediction approach explore functional data. Annals of Mathematics and Artificial Intelligence, 74(1-2):29 43, 2015.
Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113 (523):1094-1111, 2018.
David JC MacKay. Bayesian methods for adaptive models. PhD thesis, California Institute of Technology, 1992.
Pascal Massart. Concentration inequalities and model selection, volume 6. Springer, 2007.
Nicolai Meinshausen. Quantile regression forests. Journal of Machine Learning Research, 7(Jun): 983-999, 2006.
Radford M Neal. Bayesian learning for neural networks, volume 118. Springer Science & Business Media, 2012.
Alexandru Niculescu-Mizil and Rich Caruana. Predicting good probabilities with supervised learn- ing. In Proceedings of the 22nd International Conference Machine Learning, pp. 625-632, 2005.
Jeremy Nixon, Mike Dusenberry, Linchuan Zhang, Ghassen Jerfel, and Dustin Tran. Mcasuring calibration in deep learning. arXiv preprint arXiv: 1904000904 2019.
Yaniv Ovadia, Emily Fertig, Jie Ren, Zachary Nado, David Sculley, Sebastian Nowozin, Joshua Dillon, Balaji Lakshminarayanan, and Jasper Snoek. Can you trust your model's uncertainty? evaluating predictive uncertainty under dataset shift. In Advances Neural Information Process- ing Systems, pp. 13991 1-1 14002, 2019.
Utku Ozbulak, Wesley De Neve, and Arnout Van Messem. How the softmax output is misleading for evaluating the strength of adversarial examples. arXiv preprint arXiv:1811.08577 2018.
Tim Pearce, Mohamed Zaki, Alexandra Brintrup. and Andy Neely. High-quality prediction intervals for deep learning: A distribution-fiee ensembled approach. arXiv preprint arXiv:1802.07166 2018.
Tim Pearce, Felix Leibfried, and Alexandra Brintrup. Uncertainty in neural networks: Approxi- mately bayesian ensembling, In International conference on artificial intelligence and statistics, pp. 234-244. PMLR, 2020.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. In Advances in Neural Information Processing Systems, pp.
2019.
Nir Rosenfeld, Yishay Mansour, and Elad Yom-Tov. Diseriminative learning of prediction intervals.
In International Conference on Artificial Intelligence and Statistics, pp. 347-355, 2018.
Murat Sensoy, Lance Kaplan, and Melih Kandemir. Evidential deep learning to quantify classifica- tion uncertainty. In Advances in Neural Information Processing Systems, pp. 3179-3189, 2018
Eduardo D Sontag. VC dimension of neural networks. NATO ASI Series F Computer and Systems Sciences, 168:69-96. 1998.
Natasa Tagasovska and David Lopez-Paz. Frequentist uncertainty estimates for deep learning. arXiv preprint arXiv:1811.0000 2018.
Natasa Tagasovska and David Lopez-Paz. Single-model uncertainties for deep learning. In Advances in Neural Information Processing Systems, pp. 6417-6428, 2019.
Aad W Van der Vaart and Jon A Wellner. Weak Convergence and Empirical Processes with Appli- cations to Statistics. Springer, 1996.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic learning in a random world. Springer Science & Business Media, 2005.
30

---

Under review as a conference paper at ICLR 2021
Vladimir Vovk, Ilia Nouretdinov, Alex Gammerman, et al. On-line predictive linear regression. The Annals of Statistics, 37(3):1566 1590, 2009.
Bin Wang, Jie Lu, Zheng Yan, Huaishao Luo, Tianrui Li, Yu Zheng, and Guangquan Zhang. Deep uncertainty quantification: machine learning approach for weather forecasting. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 2087-2095. 2019.
Haozhe Zhang, Joshua Zimmerman, Dan Nettleton, and Daniel Nordman. Random forest predic- tion intervals. The American Statistician, pp. 1-15, 2019.
Lin Zhu, Jiaxing Lu, and Yihong Chen. HDI-forest: highest density interval regression forest. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 4468 4474. AAAI Press, 2019.
31


Reviews:
[{"review_id": "ZvVzfEkrOL3", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nThe paper proposes a new framework that computes \"high-quality\" prediction intervals (PIs) _and_ an estimate of their conditional coverage. The latter may be regarded as an analogue of [1] for PI estimation. A theoretical justification of the loss is given under some regulatory conditions.\n\nThe problem of conditional coverage estimation is certainly well-motivated. However, there are some potential issues / questions that I would like to see clarified / answered.\n\n---\n## Strengths\n1. The idea of estimating conditional coverage is an interesting one. Many methods with strong finite-sample performance are only capable of offering coverage guarantees that hold marginally. A method that is able to estimate conditional coverage with high accuracy has a potential to be useful as a diagnostic tool.\n\n## Weaknesses / Questions\n1. It isn't clear to me at all how to set $\\lambda_1$ to achieve a desired coverage level. It would appear that the $L_{CP}$ component of the loss merely tracks the proportion of covered / uncovered points, so that a larger value of $\\lambda_1$ is associated with more coverage, and vice versa. What is unclear to me is whether the $\\lambda_1 = \\lambda_1(\\alpha)$ that would achieve a fixed target marginal confidence level $1-\\alpha$ is known or have to be estimated via some sort of a tuning procedure. If the latter, doesn't it make the method prone to overfitting? Also, doesn't it rather invalidate the experimental results, as the comparison methods use a pre-specified target level of $1-\\alpha$?\n2. Is it necessary to estimate the PI and the conditional coverage simultaneously? The form of the total loss in Eq. (3.4) implies a potential tradeoff between obtaining a good PI and a good estimate of conditional coverage, but I do not see why the two objectives need to compete. On a related note, in the PI estimation problem, isn't it more interesting to estimate conditional coverage _conditional_ on a particular output of $L$ and $U$, and therefore, estimate $\\hat P$ _after_ obtaining $L$ and $U$? After all, the target $A$ is already defined conditional on $L$ and $U$.\n\n---\n## Recommendation\nThe problem of estimating conditional coverage is an interesting one. The proposed method is not a convincing solution to the proposed problem.\n\n---\n## Additional Feedback\n1. The version of the split conformal learning (SCL) implemented in experiments is somewhat outdated. [2,3] are rather more current, and produces PIs with adaptive widths, which can lead to narrower intervals in certain situations.\n2. On a related note, in comparing methods that produce PIs with adaptive widths, I am not sure if the average width is interesting as a performance metric. For instance, if I somehow had access to the conditional coverage $A$ and the conditional distribution $Y | X$, I would want to compare to the width of the shortest interval with the conditional coverage. Of course, this information is unknown, but this at least suggests that the average width may be too crude.\n3. Is there a typo in Eq. (3.3)? Also, the abuse of notation later in Theorem 4.5 is slightly confusing.\n4. There is a typo in the line immediately above Assumption 4.2 on p. 5: $L_{CA}$ approximate -> approximate**s**\n5. How difficult is it to tune the hyper-parameters? How sensitive is the method to the hyper-parameter choice?\n\n---\n## References\n1. Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. ICML 2017.\n2. Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. NeurIPS 2019.\n3. Daniel Kivaranovic, Kory D Johnson, and Hannes Leeb. Adaptive, distribution-free prediction intervals for deep networks. AISTATS 2020.\n\n---\n## Update\nI have read the revision and the rebuttal. I have also re-read the initial submission for comparison.\n\nIn the revised version, the authors have added \"(4) Tune \u0015$\\lambda_1$ such that $CP_{\\mathcal{D}'} > 1-\\alpha$ \u000b where $\\lambda_2$ and $\\lambda_3$ are fixed from (3).\" after (3) in Algorithm 4, which substantiates their claim about the marginal coverage guarantee. As my other questions under #1 were all in response to the apparent absence of a valid calibration procedure, with the introduction of this line in the revised version, I have no further complaints about the correctness of the procedure itself. I still strongly recommend including Algorithm 1 in the main part of the paper, as a prediction interval is rather meaningless unless the associated coverage level is also known.\n\nThe biggest reason why I am keeping my score as is that after going through all the reviewing material, some of the recurring questions appear to be pointing at a larger issue with the submission.\n\n1. It is repeatedly emphasized that the proposed method \"outperforms the state-of-the-art algorithms on high-quality PI generation.\" This is great, except that it is hard to see *what* about the method is causing this improvement in performance. Is it the $L_{CA}$ component? Is it some non-obvious differences in architecture or in hyper-parameter tuning? Why should there be such a difference in practical performance for the simultaneous training vs a \"decoupled\" approach, leaving aside the practical concerns such as the computational cost?\n\nNow that I have been thinking about this paper for awhile, I suspect that a great deal of the questions that the other reviewers and I have been asking are really about this need for *some* explanation for the improved performance. In my opinion, the current version does not provide enough evidence to *convince* the readers that the excellent empirical performance reported in Section 5 is an inevitable consequence of their novel method. This makes me cautious.\n\n2. Throughout the review process, I couldn't escape the sense that the authors themselves have not settled on the central message. On this point, I am with R3. There is a lack of clear messaging on whether the focus is on (a) high-quality PI generation or on (b) estimating conditional coverage or on (c) both. About 3/4 of the way into the paper in my initial reading, I received the impression that the paper was definitely about (b). However, I revised my opinion and switched to (a) after going through the experimental section. After reading the first batch of the comments posted by the authors, I thought that the paper must have been about (b) all along. The last comment posted by the authors threw me into doubt yet again, however, as it seemed to indicate (c) as the correct conclusion.\n\nIn my opinion, both these issues need to be addressed before this otherwise interesting paper can be ready for publication.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Xtv6OEuzYDo", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "After author response:\n\nI disagree with the discussion on MSE. For the empirical estimator you mention, we have:\n$$E[(Y - \\hat{P}(X))^2] = E[(Y - A(X))^2] + E[(A(X) - \\hat{P}(X))^2]$$\nImportantly, $E[(Y - A(X))^2]$ is a fixed value regardless of what $\\hat{P}$ you use. So while you can’t compute $E[(A(X) - \\hat{P}(X))^2]$, you can compare whether this is higher or lower for a particular $\\hat{P}$ by just comparing $E[(Y - \\hat{P}(X))^2]$.\n\nBy the way, this is directly analogous to classification. In classification, Y | X is stochastic, it is 1 with some probability A(X) and 0 with probability 1 - A(X). Indeed, we cannot measure $E[(A(X) - \\hat{P}(X))^2]$ directly - instead we estimate $E[(Y - \\hat{P}(X))^2]$, but that’s just off by some fixed value (which does not depend on $\\hat{P}$).\n\nAt a higher level, there isn’t really a distinction between classification and the setting here. Let f(X) be your confidence interval, and introduce a random variable A given by A = 1 if Y \\in f(X) and A = 0 if Y \\not\\in f(X) be a random variable, then we are precisely estimating P(A = 1 | X). This exactly corresponds to classification, where the label A is either 0 or 1, and we are estimating P(A = 1 | X).\n\nAs such, it’s important to compare with standard baselines (e.g. the 2 stage approach). Use the neural network features instead of training the coverage estimation model from scratch in the second stage, and show the MSE and calibration error values.\n\nI still think it’s unclear there is much interaction between the “high quality” confidence interval and coverage estimation. As the author response says, setting $\\lambda_2 = 0$ and turning off the Ca-module, would not affect the confidence intervals produced.\n\n#########################################################################\n\nSummary:\n\nThis paper tackles two problems:\n1. Providing high quality prediction intervals for regression problems. In particular, they want prediction intervals that have a desired marginal coverage (e.g. true output is in prediction interval 95% of the time), and average interval width is small.\n2. Estimating the coverage of a prediction interval (conditional coverage estimation).\n\nFor (2) they propose measuring the calibration of the coverage estimator. They propose training (1) and (2) jointly using a sum of 3 losses. On the theoretical side, (a) they show that the log loss upper bounds the calibration error motivating its use as a surrogate loss, and (b) they show that given enough data objectives (1) and (2) can be trained jointly with low generalization error on the calibration error. They show experimentally that their approach mostly gets smaller interval widths for the same coverage level, than prior work.\n\n#########################################################################\n\nReasons for score:\n\nThe paper has a lot of interesting ideas, but they seem rather disconnected to me. A key missing ingredient is that the paper does not explain why jointly estimating the coverage improves the quality of prediction intervals. Their theory only motivates that they can estimate the conditional coverage. On the experimental side, they don’t have ablations without the coverage estimation (that is, with only losses L_IW and L_CP in their notation) to check whether the coverage estimation loss L_CA helps. I’m unconvinced about the experimental protocol (more details below), the setup and architectures seem different from Pearce, and it’s unclear if results are from a single split which hyperparameters are tuned on. On the plus side, the method seems to have narrower intervals so could be useful for practitioners if some of these concerns are ironed out.\n\nI believe this work could have solid contributions if these issues are cleared up and the paper is made cohesive, and my assessment is based on the current state of the paper as opposed to the research direction. Keep up the good work!\n\n#########################################################################\n\nPros:\n\n- The idea of outputting not only an interval but also a coverage estimate sounds interesting and potentially useful, e.g. it can allow us to identify cases where the intervals do not have the desired coverage. Measuring calibration of the coverage estimator makes sense (it is weaker than a pointwise guarantee, but stronger than a marginal guarantee).\n\n- The (L_IW and L_CP) loss used to train prediction intervals seems sensible. It looks related to Rosenfeld et al, but uses a sigmoid instead of a hinge to penalize predictions that fall out of the prediction interval. Intuitively this makes sense to me for neural nets, since anecdotally my experience is that sigmoid style losses work better. Although if using softmax instead of hinge is being positioned as a major point (I didn’t think it was) there should be a comparison with hinge loss.\n\n- This paper seems to get better results than prior work, which is definitely a positive.\n\n- I skimmed the proof of Theorem 1 and it looks correct, and Theorem 2 sounds likely true.\n\n#########################################################################\n\nCons:\n\n- The main missing ingredient is the connection between predicting coverage and getting tighter intervals. Why does predicting the coverage (the L_CA loss) make the intervals tighter? Taking a step back, does it even make the intervals better? The theory does not address this, and there aren’t any experiments that this L_CA component specifically helps. My judgement (not in the paper) is that the L_CA loss is indeed lower if the prediction intervals have high coverage (if \\hat{k}_i is close to 1 and \\hat{P} is accurate). However, the L_CP term already encourages high coverage, so it’s unclear if L_CA is doing anything. If I only use L_IW and L_CP can I get the same results? Would need to do grid search to choose the right hyperparameters lambda_1 and lambda_3, which would be different after removing L_CA.\n\n- Experimental protocol is unclear. Peirce et al do 20 random splits into 90% train - 10% test, and report means and standard deviations. This paper says the split is 80% train - 20% test. Is there just one split, otherwise what are the standard deviations? The numbers for Peirce et al are quoted directly from their paper as well, so under a different setting. It looks like multiple hyperparameters (lambda1, lambda2, lambda3) are being tuned on the same validation set that the final results are measured on?\n\n- Experiments use different models from prior work and make multiple changes to the losses (sigmoind instead of hinge) and architectures. For example, Peirce et al use one hidden layer and 50 nodes (except for Protein and Song Layer where they seem to use 100). Where are the gains really coming from? Is it just from making the network deeper?\n\n#########################################################################\n\nQuestions and things to improve:\n\nI’ll certainly reconsider my score if at least some of the above are addressed, especially 1. the experimental setup needs to be clarified (hyperparameter tuning, use 20 random splits, report std-devs, 80%-20% split), 2. Need to have ablations without coverage prediction (tune lambda1 and lambda3 in this case), to see if it actually helps. The paper oversells a little in claims of “theoretically justified” since it only justified why the coverage assessment is accurate, but not why coverage assessment helps get better intervals - this needs to be edited.\n\n#########################################################################\n\nAdditional comments on theory:\n\n- Theorem 1: shows log loss is an upper bound for cal error. It shows that the log loss to a suitable power upper bounds the lp calibration error. This looks like a nice and useful result, and I at least haven’t seen this before. I skimmed the proof and it looks correct. The naive way to upper bound say the l2 calibration error is using the MSE, but it does look like the log loss is tighter in many interesting cases. I could see this being positioned as a more important contribution of the paper if there is some argument (or examples motivating) for why the bound is tighter than alternatives (like MSE for l2 calibration error)\n\n- Theorem 2: VC dim argument to show that log loss is approximated correctly by finite samples. I haven’t studied the proof of this theorem. My main questions are 1. An alternative to joint training is you can train the lower bound and upper bound estimator first, and then train the coverage module later on held out data. That should also have an exponential rate, with C* being a function of V_0. The theorem doesn’t seem to explain the advantage of joint training vs the split procedure?, 2. If we just want an exponential tail bound, we could also use a parameter space eps-cover, e.g. assuming the neural network is say L-Lipschitz. What’s the advantage of the VC dimension argument?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "PQf6X6lM-nt", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \n\nIn the submitted paper, the authors study high-quality prediction intervals (PIs). The paper proposes a novel design of loss functions to generate PIs and conditional coverage estimates. The theoretical justification for using the conditional coverage error (in Ca-module) is presented and the numerical experiments with promising results are provided on multiple benchmark datasets.\n\nPros:\n\n- The high-quality and reliable PI becomes more critical than ever as machine learning models have been used in the real-world decision-making process. This paper considers this important topic and provides a simple yet principled solution.\n- The paper is well organized and theoretical results are well explained.\n- Numerical experiment results on multiple synthetic and real datasets justify the practical advantages of the proposed algorithm.\n\nSuggestion:\n\n- Although the Bayesian framework focuses on the parameter uncertainty, as the authors mentioned in Section 6, it can be applied to generate the PIs. (Note that the posterior predictive distribution can be directly derived from the posterior distribution). A comparison study with Bayesian methods will help readers understand the advantages (or disadvantages) of the proposed method.\n\n\nI vote for acceptance. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "FGpTpSvC1f", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n\n \nIn the paper, the author addresses a calibration-based conditional coverage error in order to avoid the difficulty of conditional coverage, which provides a middle ground between marginal (no conditional information) and conditional coverage (high computational cost). The author generates the idea building on prior work and designs a new loss function combining the high-quality criterion and a coverage assessment loss. The theoretical framework about the loss function is laid out clearly, and the performances on benchmark datasets provide accurate results which outperform the other baseline algorithms on high-quality prediction intervals generation.\n\nNot directly estimating conditional coverage probability due to the challenge of approximating conditional distribution, the author develops a metric called calibration-based error to measure the estimation and its empirical counterpart is easy to compute. However, non-differentiable empirical counterpart of calibration-based error metric hinders the algorithm implementation when using gradient-based method, the author replaces it with Kullback-Leibler divergence and theoretically demonstrates this divergence is a tight upper bound of coverage error, which makes the optimization tractable.\n\n\n##########################################################################\n\nReasons for score: \n\n \nOverall, I vote for accepting. The theoretical study is carried out clearly and smoothly. The method proposed, which provides more opportunities for broad application, is creative and well-demonstrated. My major concern is about the clarity of the paper in terms of the order of the presentation, and the possibility of a decoupled method. Hopefully the authors can address my concern in the rebuttal period. \n\n \n##########################################################################\n\nPros: \n\n \n1. This paper considers calibration of the coverage incidence, which is important information for real deployment of any prediction interval method. \n \n2. The proposed loss is clear, intuitive and easy to understand.\n\n3. Nice concentration bound for the calibration part.\n\n\n \n##########################################################################\n\nCons: \n\n \n1. Lemma A.2 (a) is an important argument for constructing the subsequent error metric. I think the statement appears to be too strong in general therefore can not be achieved in practice.\n\n2. The authors should make it crystal clear that they are not proposing a PI with conditional coverage guarantee; instead, just try to provide an estimate of the conditional coverage guarantee given the feature. Somehow I had the impression that the goal was the former, until late in the paper. \n\n3. The methodology in Section 3 is not naturally motivated from the many discussions and definitions about the coverage estimation error starting from Definition 2.1 to the end of Section 2. Their connection is really in the back-end which is not shown until Section 4. It may be better to reshuffle the order of the presentation, or adding some explanation in Section 3 when Loss_CA is introduced. The main gap is that one cannot see how Loss_CA should be defined as in (3.3) after reading all these discussion about CE in Section 2.\n\n4. Is there any advantage to consider the PI problem and the calibration problem in the same network? What is wrong with first estimate the PI, and then estimate the coverage incident given the PI as a separate problem? In this de-coupled framework, Loss_IW and Loss_CO will be used in the PI problem and Loss_CA will be used in the calibration problem, and they do not need to share the same network. More to the point: when a shared total loss is the goal of minimization, it would seem that the PI would evolve to make the task of calibration easier (to have small calibration error); there may be some cost to pay for this joint training, either in terms of IW or coverage. However, it is not clear to me what price we have to pay in the joint problem in (3.4)\n\n 5. Table 1: why 1.13 in the second row is bold face when the IW for QD_Ens has a smaller IW of 1.09?\n\n##########################################################################\n\nQuestions during rebuttal period: \n\nPlease address my comments in cons above plus the followings.\n\nFor the total loss (3.4), since the non-coverage probability is incorporated into the loss, we have to manually or adjust these tune parameters until the marginal coverage probability is satisfied. This does not seem to be trivial. Will this reduce the computation efficiency? Will a constrained optimization instead be faster than this? What is the hyper-parameter $\\lambda_3$ used for?\n\nThe proof on VC-dimension and coverage assessment approximating Kullback-Leibler divergence are well-organized and detailed. However, perhaps supplying the proof on excess risk would be helpful too.\n\n\n####\n\nMinor comments:\n\nI think a useful insight that the author can consider is that the calibration problem can be viewed as a classification problem in which the response is the event that the PI covers the Y value (\\ind{ Y \\in PI}). Then it would be class that the total loss is a PI problem joint with a classification problem. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the problem of estimating high quality prediction intervals for deep regression models. The paper argues that one (relatively under-studied) avenue to improve these intervals is to accurately estimate conditional coverage -- traditional PIs only reason about marginal coverage. The paper argues that in the presence of heteroskedastic errors or model mis-specification, conditional coverage can be dramatically different than marginal coverage. Concrete examples for each of these cases would be useful to establish the claim -- a synthetic experiment later in the paper illustrates the gap using heteroskedastic errors. The paper introduces a "Confidence Assessment" module that estimates the probability that the model's confidence interval is correct. In spirit, this is akin to learning a calibrated probabilistic classifier. Theoretical analysis shows that the CA-module can provably assess the reliability of the confidence intervals while jointly training the confidence interval method -- some reviewers appreciated the rigor in this analysis.

However, the reviewers also pointed out that the main message of the paper is muddled, and the confusion spills over into the experimental execution of the paper. Many of the complaints about baselines and experiment setup can be traced back to this confusion.
There are several claims in the paper:
- Conditional coverage estimation is useful. The synthetic experiments demonstrate this sufficiently.
- The CA-module achieves conditional coverage estimation reliably and efficiently. There are missing baselines (e.g., other approaches implementing a probabilistic classifier) in the experiments to establish this claim. The authors added an experiment to address this, but reviewers are concerned that the baseline classifier is unnecessarily handicapped (e.g., training a new coverage model from scratch instead of using existing learned features). Reviewers also note that there are missing metrics -- the existing metrics can plausibly be gamed by simply outputting the marginal coverage estimate.
- Incorporating CA-module leads to better prediction intervals. Some experiments suggest that this is not the case, and that there is negligible improvement (the lambda_2 = 0 setting that the authors describe). On the other hand, it is heartening to note that adding the CA-module did not adversely affect the quality of the prediction intervals either.

Since a two-stage procedure (estimate intervals, followed by estimating CA-module) is empirically inferior to joint training, reviewers rightly ask for some insight into why estimating conditional coverage jointly would reliably lead to prediction intervals that are more precise on average. The theoretical analysis in the paper applies to the 2-stage procedure too (proving that the 2nd stage CA-module indeed estimates the reliability of the confidence intervals); so there is some missing insight on why joint training could be beneficial.

A clearer message, making weaker claims and experiments that clearly back those claims will make the paper stronger.
For example, (softening claims about CA-module:) The paper introduces one ad-hoc procedure (CA-module) and shows that it is fit for purpose. No claim that it is efficient relative to baselines, but it still needs to justify why CA-module should be preferred compared to any other probabilistic classification approach. (softening claims about better intervals:) joint training works better than stage-wise training (which, by definition, leaves the prediction intervals unaffected). Unclear as to why that should happen in general; two special cases are mis-specification and heteroskedasticity. 

Decision: Reject