PAC CONFIDENCE SETS FOR DEEP NEURAL NET-
Year: 2020

Abstract:
We propose an algorithm combining calibrated prediction and generalization bounds from learning theory to construct confidence sets for deep neural networks with PAC guarantees—i.e., the confidence set for a given input contains the true label with high probability. We demonstrate how our approach can be used to construct PAC confidence sets on ResNet for ImageNet, a visual object tracking model, and a dynamics model for the half-cheetah reinforcement learning problem. 1

heading: 1 INTRODUCTION
text: A key challenge facing deep neural networks is that they do not produce reliable confidence estimates, which are important for applications such as safe reinforcement learning (Berkenkamp et al., 2017), guided exploration (Malik et al., 2019), and active learning (Gal et al., 2017).
We consider the setting where the test data follows the same distribution as the training data (i.e., we do not consider adversarial examples designed to fool the network (Szegedy et al., 2014)); even in this setting, confidence estimates produced by deep neural networks are notoriously unreliable (Guo et al., 2017). One intuition for this shortcoming is that unlike traditional supervised learning algorithms, deep learning models typically overfit the training data (Zhang et al., 2017). As a consequence, the confidence estimates of deep neural networks are flawed even for test data from the training distribution since, by construction, they overestimate the likelihood of the training data.
A promising approach to addressing this challenge is temperature scaling (Platt, 1999). This approach takes as input a trained neural network fφ̂(y | x)—i.e., whose parameters φ̂ have already been fit to a training dataset Ztrain—which produces unreliable probabilities fφ̂(y | x). Then, this approach rescales these confidence estimates based on a validation dataset to improve their “calibration”. More precisely, this approach fits confidence estimates of the form
fφ̂,τ (y | x) ∝ exp(τ log fφ̂(y | x)),
where τ ∈ R>0 is a temperature scaling parameter that is fit based on the validation dataset. The goal is to choose τ to minimize calibration error, which roughly speaking measures the degree to which the reported error rate differs from the actual error rate.
The key insight is that in the temperature scaling approach, only a single parameter τ is fit to the validation data—thus, unlike fitting the original neural network, the temperature scaling algorithm comes with generalization guarantees based on traditional statistical learning theory.
Despite the improved generalization guarantees, these confidence estimates still do not come with theoretical guarantees. We are interested in producing confidence sets that satisfy statistical guarantees while being as small as possible. Given a test input x ∈ X , a confidence set CT (x) ⊆ Y
1Our code is available at https://github.com/sangdon/PAC-confidence-set.
(parameterized by T ∈ R) should contain the true label y for at least a 1− fraction of cases: P(x,y)∼D[y ∈ CT (x)] ≥ 1− .
Since we are fitting a parameter T to based on Zval, we additionally incur a probability of failure due to the randomness in Zval. In other words, given , δ ∈ R>0, we aim to obtain probably approximately correct (PAC) confidence sets CT (x) ⊆ Y satisfying the guarantee
PZval∼Dn ( P(x,y)∼D(y ∈ CT (x)) ≥ 1− ) ≥ 1− δ.
Indeed, techniques from statistical learning theory (Vapnik, 1999) can be used to do so (Vovk, 2013).
There are a number of reasons why confidence sets can be useful. First, they can be used to inform safety critical decision making. For example, consider a doctor who uses prediction tools to help perform diagnosis. Having a confidence set would both help the doctor estimate the confidence of the prediction (i.e., smaller confidence sets imply higher confidence), but also give a sense of the set of possible diagnoses. Second, having a confidence set can be useful for reasoning about safety since they contain the true outcome with high probability. For instance, robots may use a confidence set over predicted trajectories to determine whether it is safe to act with high probability. As a concrete example, consider a self-driving car that uses a deep neural network to predict the path that a pedestrian might take. We require that the self-driving car avoid the pedestrian with high probability, which it can do by avoiding all possible paths in the predicted confidence set.
Contributions. We propose an algorithm combining calibrated prediction and statistical learning theory to construct PAC confidence sets for deep neural networks (Section 3). We propose instantiations of this framework in the settings of classification, regression, and learning models for reinforcement learning (Section 3.6). Finally, we evaluate our approach on three benchmarks: ResNet (He et al., 2016) for ImageNet (Russakovsky et al., 2015), a model (Held et al., 2016) learned for a visual object tracking benchmark (Wu et al., 2013), and a probabilistic dynamics model (Chua et al., 2018) learned for the half-cheetah environment (Brockman et al., 2016) (Section 4). Examples of ImageNet images with different sized ResNet confidence sets are shown in Table 1. As can be seen, our confidence sets become larger and the images become more challenging to classify. In addition, we show predicted confidence sets for ResNet in Table 2, as well as predicted confidence sets for the visual object tracking model in Table 3.
Related work. There has been work on constructing confidence sets with theoretical guarantees. Oftentimes, these guarantees are asymptotic rather than finite sample (Steinberger & Leeb, 2016; 2018). Alternatively, there has been work focused on predicting confidence sets with a given expected size (Denis & Hebiri, 2017).
More relatedly, there has been recent work on obtaining PAC guarantees. For example, there has been some work specific prediction tasks such as binary classification (Lei, 2014; Wang & Qiao,
2018). There has also been work in the setting of regression (Lei et al., 2018; Barber et al., 2019). However, in this case, the confidence sets are fixed in size—i.e., they do not depend on the input x (Barber et al., 2019). Furthermore, they make stability assumptions about the learning algorithm (though they achieved improved rates by doing so) (Lei et al., 2018; Barber et al., 2019).
The most closely related work is on conformal prediction (Papadopoulos, 2008; Vovk, 2013). Like our approach, this line of work provides a way to construct confidence sets from a given confidence predictor, and provided PAC guarantees for the validity of these confidence sets. Indeed, with some work, our generalization bound Theorem 1 can be shown to be equivalent to Theorem 1 in Vovk (2013). In contrast to their approach, we proposed to use calibrated prediction to construct confidence predictors that can suitably be used with deep neural networks. Furthermore, our approach
makes explicit the connections to temperature scaling and as well as to generalization bounds from statistical learning theory (Vapnik, 1999). In addition, unlike our paper, they do not explicitly provide an efficient algorithm for constructing confidence sets. Finally, we also propose an extension to the case of learning models for reinforcement learning.
Finally, we build on a long line of work on calibrated prediction, which aims to construct “calibrated” probabilities (Murphy, 1972; DeGroot & Fienberg, 1983; Platt, 1999; Zadrozny & Elkan, 2001; 2002; Naeini et al., 2015; Kuleshov & Liang, 2015). Roughly speaking, probabilities are calibrated if events happen at rates equal to the predicted probabilities. This work has recently been applied to obtaining confidence estimates for deep neural networks (Guo et al., 2017; Kuleshov et al., 2018; Pearce et al., 2018), including for learned models for reinforcement learning (Malik et al., 2019). However, these approaches do not come with PAC guarantees.

heading: 2 PAC CONFIDENCE SETS
text: Our goal is to estimate confidence sets that are as small as possible, while simultaneously ensuring that they are probably approximately correct (PAC) (Valiant, 1984). Essentially, a confidence set is correct if it contains the true label. More precisely, let X be the inputs and Y be the labels, and let D be a distribution over Z = X × Y . A confidence set predictor is a function C : X → 2Y such that C(x) ⊆ Y is a set of labels; we denote the set of all confidence set predictors by C. For a given example (x, y) ∼ D, we say C is correct if y ∈ C(x). Then, the error of C is
L(C) = P(x,y)∼D[y 6∈ C(x)]. (1) Finally, consider an algorithm A that takes as input a validation set Zval ⊆ Z consisting of n i.i.d. samples (x, y) ∼ D, and outputs a confidence set predictor Ĉ. Given , δ ∈ R>0, we say that A is probably approximately correct (PAC) if
PZval∼Dn [ L(Ĉ) > where Ĉ = A(Zval) ] < δ. (2)
Our goal is to design an algorithm A that satisfies (2) while constructing confidence sets C(x) that are as “small in size” as possible on average. The size of C(x) depends on the domain. For classification, we consider confidence sets that are arbitrary subsets of labels C(x) ⊆ Y = {1, ..., Y }, and we measure the size by |C(x)| ∈ N—i.e., the number of labels in C(x). For regression, we consider confidence sets that are intervals C(x) = [a, b] ⊆ Y = R, and we measure size by b − a—i.e., the length of the predicted interval. Note that there is an intrinsic tradeoff between satisfying (2) and average size of C(x)—larger confidence sets are more likely to satisfy (2).

heading: 3 PAC ALGORITHM FOR CONFIDENCE SET CONSTRUCTION
text: Our algorithm is formulated in the empirical risk framework. Typically, this framework refers to empirical risk minimization. In our setting, such an algorithm would take as input (i) a parametric family of confidence set predictors C = {Cθ | θ ∈ Θ}, where Θ is the parameter space, and (ii) a training set Zval ⊆ Z of n i.i.d. samples (x, y) ∼ D, and output the confidence set predictor Cθ̂, where θ̂ minimizes the empirical risk:
θ̂ = arg min θ∈Θ
L̂(Cθ;Zval) where L̂(C;Zval) = 1
n ∑ (x,y)∈Zval I[y 6∈ C(x)].
Here, I[φ] ∈ {0, 1} is the indicator function, and the empirical risk L̂ in an estimate of the confidence set error (1) based on the validation set Zval.
However, our algorithm does not minimize the empirical risk. Rather, recall that our goal is to minimize the size of the predicted confidence sets given a PAC constraint on the true risk L(θ̂) based on the given PAC parameters , δ ∈ R>0 and the number of available validation samples n = |Zval|. Thus, the risk shows up as a constraint in the optimization problem, and the objective is instead to minimize the size of the predicted confidence sets:
θ̂ = arg min θ∈Θ
S(θ) subj. to L̂(Cθ;Zval) ≤ α. (3)
At a high level, the value α = α(n, , δ) ∈ R≥0 is chosen to enforce the PAC constraint, and is based on generalization bounds from statistical learning theory (Valiant, 1984). Furthermore, following the temperature scaling approach (Platt, 1999), the parameter space Θ is chosen to be as small as possible (in particular, one dimensional) to enable good generalization. Finally, our choice of size metric S follows straightforwardly based on our choice of parameter space. In the remainder of this section, we describe the choices of (i) parameter space Θ, (ii) size metric S(θ), and (iii) confidence level α(n, , δ) in more detail, as well as how to solve (3) given these choices.

heading: 3.1 CHOICE OF PARAMETER SPACE Θ
text: Probability forecasters. Our construction of the parameteric family of confidence set predictors Cθ assumes given a probability forecaster f : X → PY , wherePY is a space of probability distributions over Y . Given such an f , we use f(y | x) to denote the probability of label y under distribution f(x). Intuitively, f(y | x) should be the probability (or probability density) that y is the true label for a given input x—i.e., f(y | x) ≈ P(X,Y )∼D[Y = y | X = x]. For example, in classification, we can choose PY to be the space of categorical distributions over Y , and f may be a neural network whose last layer is a softmax layer with |Y| outputs. Then, f(y | x) = f(x)y . Alternatively, in regression, we can choose PY to be the space of Gaussian distributions, and f may be a neural network whose last layer outputs the values (µ, σ) ∈ R × R>0 of a Gaussian distribution. Then, f(y | x) = N (x;µ(x), σ(x)2), where (µ(x), σ(x)) = f(x), andN (·;µ, σ2) is the Gaussian density function with mean µ and variance σ2.
Training a probability forecaster. To train a probability forecaster, we use a standard approach to calibrated prediction that combines maximum likelihood estimation with temperature scaling. 2 First, we consider a parametric model family F = {fφ | φ ∈ Φ}, where Φ is the parameter space. Note that Φ can be high-dimensional—e.g., the weights of a neural network model. Given a training set Ztrain ⊆ Z of m i.i.d. samples (x, y) ∼ D, the maximum likelihood estimate (MLE) of φ is
φ̂ = arg min φ∈Φ
`(φ;Ztrain) where `(φ;Ztrain) = − ∑
(x,y)∈Ztrain
log fφ(y | x). (4)
We could now use fφ̂ as the probability forecaster. However, the problem with directly using φ̂ is that
because φ̂ may be high-dimensional, it often overfits the training data Ztrain. Thus, the probabilities are typically overconfident compared to what they should be.
To reduce their confidence, we use the temperature scaling approach to calibrate the predicted probabilities (Platt, 1999; Guo et al., 2017). Intuitively, this approach is to train an MLE estimate using exactly the same approach used to train φ̂, but using a single new parameter τ ∈ R>0. The key idea is that this time, the model family is based on the parameters φ̂ from (4). In other words, the “shape” of the probabilities forecast by fφ̂ are preserved, but their exact values are shifted.
More precisely, consider the model family F ′ = {fφ̂,τ | τ ∈ R>0}, where fφ̂,τ (y | x) ∝ exp ( τ log fφ̂(y | x) ) .
Then, we have the following MLE for τ :
τ̂ = arg min τ∈R>0
`′(τ ;Z ′train) where ` ′(τ ;Z ′train) = − ∑ (x,y)∈Z′train log fφ̂,τ (y | x). (5)
Note that τ̂ is estimated based on a second training set Z ′train. Because we are only fitting a single parameter, this training set can be much smaller than the training set Ztrain used to fit φ̂.
Parametric family of confidence set predictors. Finally, given a probability forecaster f , we consider one dimensional parameter space Θ = R; in an analogy to the temperature scaling technique for calibrated prediction, we denote this parameter by T ∈ Θ. In particular, we assume a confidence probability predictor f is given, and consider
CT (x) = {y ∈ Y | f(y | x) ≥ e−T }. 2A priori, it is not obvious that using temperature scaling can improve our confidence set predictor; we give
a detailed discussion in Appendix A.1.
In other words, CT (x) is the set of y with high probability given x according to f . Considering this scalar parameter space, we denote the minimum of (3) by T̂ .
3.2 CHOICE OF SIZE METRIC S(T )
To choose the size metric S(T ), we note that for our chosen parametric family of confidence set predictors, smaller values correspond to uniformly smaller confidence sets—i.e., T ≤ T ′ ⇒ ∀x, CT (x) ⊆ CT ′(x). Thus, we can simply choose the size metric to be
S(T ) = T. (6) This choice minimizes the size of the confidence sets produced by our algorithm.
3.3 CHOICE OF CONFIDENCE LEVEL α(n, , δ)
Naive approach based on VC generalization bound. A naive approach to choosing α(n, , δ) is to do so based on the VC dimension generalization bound (Vapnik, 1999). It is not hard to show that the problem of estimating T̂ is equivalent to a binary classification problem, and that the VC dimension of Θ for this problem is 1. Thus, the VC dimension bound implies that for all T ∈ Θ,
PZval∼Dn [ L(CT ) ≤ L̂(CT ;Zval) + √ log(2n) + 1− log(δ/4)
n
] ≥ 1− δ. (7)
The details of this equivalence are given in Appendix B.2. Then, suppose we choose α(n, , δ) = − √
log(2n) + 1− log(δ/4) n .
With this choice, for the solution T̂ of (3) with α = α(n, , δ), the constraint in (3) ensures that L̂(CT̂ ;Zval) ≤ α(n, , δ). Together with the VC generalization bound (7), we have
PZval∼Dn [ L(CT̂ ) > ] < δ,
which is exactly desired the PAC constraint on our predicted confidence sets.
Direct generalization bound. In fact, we can get better choices of α by directly bounding generalization error. For instance, in the realizable setting (i.e., we always have L̂(CT̂ ;Zval) = 0), we can get rates of n = Õ(1/ ) instead of n = Õ(1/ 2) (Kearns & Vazirani, 1994); see Appendix A.2 for details. We can achieve these rates by choosing α = 0, but then, the PAC guarantees we obtain may actually be stronger than desired (i.e., for ′ < ). Intuitively, we can directly prove a bound that interpolates between the realizable setting and the VC generalization bound—in particular: Theorem 1. For any ∈ [0, 1], n ∈ N>0, and k ∈ {0, 1, ..., n}, we have
PZval∼Dn [ L(CT̂ ) > ] ≤ k∑ i=0 ( n i ) i(1− )n−i,
where T̂ is the solution to (3) with α = k/n. 3
We give a proof in Appendix B.2. Based on Theorem 1, we can choose
α(n, , δ) = max k∈N∪{0} k/n subj. to k∑ i=0 ( n i ) i(1− )n−i < δ. (8)

heading: 3.4 THEORETICAL GUARANTEES
text: We have the following guarantee, which follows straightforwardly from Theorem 1: Corollary 1. Let T̂ be the solution to (3) for α = α(n, , δ) chosen according to (8). Then, we have
PZval∼Dn [ L(CT̂ ) > ] < δ.
In other words, our algorithm is probably approximately correct. 3The theorem statement relies on additional standard technical conditions; see Appendix B.1.
Algorithm 1 Algorithm for solving (3). procedure ESTIMATECONFIDENCESETPREDICTOR(Ztrain, Z ′train, Zval)
Estimate φ̂, τ̂ using (4) and (5), respectively Compute α(n, , δ) according to (8) by enumerating k ∈ {0, 1, ..., n} Let k∗ = n · α(n, , δ) (note that k ∈ {0, 1, ..., n}) Sort (x, y) ∈ Zval in ascending order of fφ̂,τ̂ (y | x) Let (xk∗+1, yk∗+1) be the (k∗ + 1)st element in the sorted Zval Solve (3) by choosing T̂ = − log fφ̂,τ̂ (yk∗+1 | xk∗+1) Return CT̂ : x 7→ {y ∈ Y | fφ̂,τ̂ (y | x) ≥ e
−T̂ } end procedure

heading: 3.5 PRACTICAL IMPLEMENTATION
text: Our algorithm for estimating a confidence set predictor CT̂ is summarized in Algorithm 1. The algorithm solves the optimization problem (3) using the choices of Θ, S(T ), and α(n, , δ) described in the preceding sections. There are two key implementation details that we describe here.
Computing α(n, , δ). To compute α(n, , δ), we need to solve (8). A straightforward approach is to enumerate all possible choices of k ∈ {0, 1, ..., n}. There are two optimizations. First, the objective is monotone increasing in k, so we can enumerate k in ascending order until the constraint no longer holds. Second, rather than re-compute the left-hand side of the constraint ∑k i=0 ( n i ) i(1 − )n−i,
we can accumulate the sum as we iterate over k. We can also incrementally compute ( n i ) , i, and (1− )n−i. For numerical stability, we perform these computations in log space. Solving (3). To solve (3), note that the constraint in (3) is equivalent to∑
(x,y)∈Zval
E(x, y;T ) ≤ n · α(n, , δ) where E(x, y;T ) = I [ fφ̂,τ̂ (y | x) < e −T ] . (9)
Also, note that k∗ = n · α(n, , δ) is an integer due to the definition of α(n, , δ) in (8). Thus, we can interpret (9) as saying that E(x, y;T ) = 1 for at most k∗ of the points (x, y) ∈ Zval. In addition, note that E(x, y;T ) decreases monotonically as fφ̂,τ̂ (y | x) becomes larger. Thus, we can sort the points (x, y) ∈ Zval in ascending order of fφ̂,τ̂ (y | x), and require that only the first k ∗ points (x, y) in this list satisfyE(x, y;T ) = 1. In particular, letting (xk∗+1, yk∗+1) be the (k∗+1)st point, (9) is equivalent to
fφ̂,τ̂ (yk∗+1 | xk∗+1) ≥ e −T . (10)
In other words, this constraint says that T must satisfy yk∗+1 ∈ CT (xk∗+1). Finally, the solution T̂ to (3) is the smallest T that satisfies (10), which is the T that makes (10) hold with equality—i.e.,
T̂ = − log fφ̂,τ̂ (yk∗+1 | xk∗+1). (11)
We have assumed fφ̂,τ̂ (yk∗+1 | xk∗+1) > fφ̂,τ̂ (yk∗ | xk∗); if not, we decrement k ∗ until this holds.

heading: 3.6 PROBABILITY FORECASTERS FOR SPECIFIC TASKS
text: We briefly discuss the architectures we use for probability forecasters for various tasks. We give details, including how we measure the sizes of predicted confidence sets CT (x), in Appendix C. We consider three tasks: classification, regression, and model-based reinforcement learning. For classification, we use the standard approach of using a soft-max layer to predict label probabilities f(y | x). For regression, we also use a standard approach where the neural network predicts both the mean µ(x) and covariance Σ(x) of a Gaussian distribution N (µ(x),Σ(x)); then, f(y | x) = N (y;µ(x),Σ(x)) is the probability density of y according to this Gaussian distribution. Finally, for model-based reinforcement learning, our goal is to construct confidence sets over trajectories predicted using a learned model of the dynamics. We consider unknown dynamics
g∗(x′ | x, u) mapping a state-action pair (x, u) to a distribution over states x′, and consider a known (and fixed) policy π(u | x) mapping a given state x to a distribution over actions u ∈ U ⊆ RdU . Then, we let f∗(x′ | x) = Eπ(u|x)[g∗(x′ | u)] denote the (unknown) closed-loop dynamics.
Next, we consider a forecaster f(x′ | x) ≈ f∗(x′ | x) of the form f(x′ | x) = N (x′;µ(x),Σ(x)), and our goal is to construct confidence sets for the predictions of f . However, we want to do so for not just for one-step predictions, but for predictions over a time horizon H ∈ N. In particular, given initial state x0 ∈ X , we can sample x∗1:H = (x1, ..., xH) ∼ f∗ by letting x∗0 = x0 and sequentially sampling x∗t+1 ∼ f( · | x∗t ) for each t ∈ {0, 1, ...,H − 1}. Then, our goal is to construct a confidence set that contains x∗1:H ∈ XH with high probability (over both the randomness in an initial state distribution x0 ∼ d0 and the randomness in f∗).
To do so, we construct and use a forecaster f̃(x1:H | x0) based on f . In principle, this task is a special case of multivariate regression, where the inputs are X (i.e., the initial state x0) and the outputs are Y = XH (i.e., a predicted trajectory x1:H ). However, the variance Σ(x) predicted by our probability forecaster is only for a single step, and does not take into account the fact that x is itself uncertain. Thus, we use a simple heuristic where we accumulate variances over time. More precisely, we construct (i) the predicted mean x̄1:H = (x̄1, ..., x̄H) by x̄0 = x0 and x̄t+1 = µ(x̄t) for t ∈ {0, 1, ...,H − 1}, and (ii) the predicted variances Σ̃1:H = (Σ̃1, ..., Σ̃H) by
Σ̃t = Σ(x̄0) + Σ(x̄1) + ...+ Σ(x̄t−1).
We use a probability forecaster f̃(x1:H | x0) = N (x1:H ; x̄1:H , Σ̃1:H) to construct confidence sets.

heading: 4 EXPERIMENTS
text: We describe our experiments on ImageNet (a classification task), a visual object tracking benchmark (a regression task), and the half-cheetah environment (a model-based reinforcement learning task). We give additional results in Appendix D.
ResNet for ImageNet. We use our algorithm to compute confidence sets for ResNet (He et al., 2016) on ImageNet (Russakovsky et al., 2015), for = 0.01, δ = 10−5, and n = 20000 validation images. We show the results in Figure 1. In (a), we compare our approach to an ablation. In particular, C refers to performing an initial temperature scaling step to calibrate the neural network predictor (i.e., using fφ̂ instead of fφ̂,τ̂ ), and (ii)D refers to using Theorem 1 instead of the VC generalization bound. Thus, C + D refers to our approach. As can be seen, using calibrated predictor produces a noticeable reduction in the maximum confidence set size.
We also compared to the ablation C—i.e., using the VC generalization bound. However, we were unable to obtain valid confidence sets for our choice of and δ—i.e., (3) is infeasible. That is, using Theorem 1 outperforms using the VC generalization bound since the VC bound is too loose to satisfy the PAC criterion for our choice of parameters. In addition, in Table 6 in Appendix D, we show results for larger choices of and δ; these results show that our approach substantially outperforms the ablation based on the VC bound even when the VC bound produces valid confidence sets.
In (b), we show the confidence set sizes for images correctly vs. incorrectly labeled by ResNet. As expected, the sizes are substantially larger for incorrectly labeled images. Finally, in (c) and (d), we show how the sizes vary with and δ, respectively. As expected, the dependence on is much more pronounced (note that δ is log-scale).
Visual object tracking. We apply our confidence set prediction algorithm to a 2D visual singleobject tracking task, which is a multivariate regression problem. Specifically, the input space X consists of the previous image, the previous bounding box (in R4), and the current image. The output space Y = R4 is a current bounding box. We use the regression-based tracker from Held et al. (2016), and retrain the regressor neural network to predict the mean and variance of a Gaussian distribution. More precisely, our object tracking model predicts the mean and variance of each bounding box parameter—i.e., (xmin, ymin, xmax, ymax). Given this bounding box forecaster fφ̂, we calibrate and estimate a confidence set predictor as described in Section 3.6.
We use the visual object tracking benchmark from Wu et al. (2013) to train and evaluate our confidence set predictor. This benchmark consists of 99 video sequences labeled with ground truth bounding boxes. We randomly split these sequences to form the training set for calibration, validation set for confidence set estimation, and test set for evaluation. For each sequence, a pair of two adjacent frames constitute a single example. Our training dataset contains 20,882 labeled examples, each consisting of of a pair of consecutive images and ground truth bounding boxes. The validation set for confidence set estimation and test set contain 22,761 and 22,761 labeled examples, respectively. Figure 2 shows the sizes of the predicted confidence sets; the sizes are measured as described in Section 3.6 for regression tasks. As for ResNet, we omit results for the VC bound ablation since n is too small to get a bound. The trends are similar to the ones for ResNet.
Half-cheetah. We use our algorithm to compute confidence sets for a probabilistic neural network dynamics model (Chua et al., 2018) for the half-cheetah environment (Brockman et al., 2016), for = 0.01, δ = 10−5, H = 20 time steps, and n = 5000 validation rollouts. When using temperature scaling to calibrate fφ̂ to obtain fφ̂,τ̂ , we calibrate each dimension of time steps independently (i.e., we fit H parameters, where H is time horizon). We show the results in Figure 3.
In (a), we compare to two ablations. The labels C and D are as for ResNet; in addition, A refers to using the accumulated variance Σ̃t instead of the one-step predicted variances Σt = Σ(x̄t−1). Thus, A+C +D is our approach. As before, we omit results for the ablation using the VC generalization bound since n is so small that the bound does not hold for any k for the given and δ. In (b), we show the same ablations over the entire trajectory until t = 20. As can be seen, using the calibrated predictor produces a large gain; these gains are most noticeable in the tails. Using the accumulated confidence produces a smaller, but still significant, gain. In (c) and (d), we show how the sizes vary with and δ, respectively. The trends are similar those for ResNet.

heading: 5 CONCLUSION
text: We have proposed an algorithm for constructing PAC confidence sets for deep neural networks. Our approach leverages statistical learning theory to obtain theoretical guarantees on the predicted confidence sets. These confidence sets quantify the uncertainty of deep neural networks. For instance, they can be used to inform safety-critical decision-making, and to ensure safety with highprobability in robotics control settings that leverage deep neural networks for perception. Future work includes extending these results to more complex tasks (e.g., structured prediction), and handling covariate shift (e.g., to handle policy updates in reinforcement learning).

heading: ACKNOWLEDGMENTS
text: This work was support in part by NSF CCF-1910769 and by the Air Force Research Laboratory and the Defense Advanced Research Projects Agency under Contract No. FA8750-18-C-0090. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Air Force Research Laboratory (AFRL), the Defense Advanced Research Projects Agency (DARPA), the Department of Defense, or the United States Government.

heading: A DISCUSSION OF ALGORITHM DESIGN CHOICES

heading: A.1 USEFULNESS OF TEMPERATURE SCALING
text: In this section, we discuss why temperature scaling can help improve the predicted confidence sets. A concern is that temperature scaling does not change the ordering of label probabilities. Thus, we may expect that temperature scaling does not affect the predicted confidence sets. However, this fact only holds when considering a single input x—i.e., the ordering of the probabilities p(y | x) for y ∈ Y is not changed by temperature scaling. Indeed, the order of confidences for labels for different inputs can change. For a concrete example, consider two inputs x and x′, and the case Y = {0, 1, 2}. Assume that the label probabilities are
f( · | x) = [1/3 1/3 1/3]>
f( · | x′) = [3/4 1/4 0]> . Now, if we take temperature τ very large, then the labels become roughly
fτ ( · | x) = [1/3 1/3 1/3] >
fτ ( · | x′) = [1/2 1/2 0] > .
As a consequence, there are confidence sets that are achievable when using fτ that are not achievable when using f . In particular, the confidence sets
CT (x) = ∅ CT (x ′) = {0, 1}
can be achieved using fτ (e.g., with e−T = 2/5). However, it is impossible to achieve these confidence sets using f for any choice of T , since if 1 ∈ CT (x′), then it must be the case that CT (x) = {0, 1, 2}. Intuitively, we expect calibrated prediction to improve the ordering of probabilities across different inputs. Our experiments support this intuition, since they show that empirically, using calibrated predictors fτ produces confidence sets of smaller size.

heading: A.2 USEFULNESS OF DIRECT BOUND
text: One key design choice is to use a specialized generalization bound that directly provides PAC guarantees on our confidence sets rather than simply applying the VC dimension bound. The easiest way to determine which bound is better is to examine which one produces a smaller confidence set. In our approach, the size of the confidence set decreases monotonically with the choice of α = α(n, , δ) in (3). Thus, the bound that produces larger α is better. Recall that the VC dimension bound produces
αVC(n, , δ) = − √
log(2n) + 1− log(δ/4) n ,
whereas our direct bound produces (for k = 0)
αdirect(n, , δ) = max k∈N k/n subj. to k∑ i=0 ( n i ) i(1− )n−i < δ.
Directly comparing these two choices of α is difficult, but our experiments show empirically that using the direct bound outperforms using the indirect bound.
A more direct way to compare the two approaches is to instead ask how large n needs to be to achieve α(n, , δ) = 0. For αVC, it is easy to check that we need
n ≥ log(2n) + 1 + log(4/δ) 2 .
Thus, we need n to be at least O(log(1/δ)/ 2) (and possibly greater, to account for the log(2n) term). In contrast, for our direct bound, α = 0 corresponds to the case k = 0. To achieve k = 0, it suffices to have n satisfying (1− )n < δ. Using (1− )n ≤ e−n , it suffices to have n satisfying
n ≥ log(1/δ) .
In other words, n only needs to be O(log(1/δ)/ ). For small (e.g., = 0.01), we need 100× fewer samples to achieve the same size confidence set (i.e., with choice α(n, , δ) = 0). In Figure 4 (right), we compute the exact values of n needed to get α(n, , δ) = 0 as a function of for each bound (fixing δ = 10−5). As expected, our bound requires substantially smaller n.
Finally, in Figure 4 (right), we compare the magnitude of n needed to achieve larger values of α using our direct bound; for simplicity, we actually consider larger values of k (where α = k/n), but the qualitative insights are the same. As can be seen, even for large k, (e.g., k = 50), the number of samples increases, but not substantially.

heading: B THEORETICAL GUARANTEES

heading: B.1 ASSUMPTIONS
text: We make two additional technical assumptions in Theorem 1, both of which are standard. First, we assume that f is measurable; this assumption holds for all models used in practice, including neural networks (e.g., it holds as long as f is continuous).
Second, letting φ : Z → R, where Z = X × Y , be defined by φ((x, y)) = − log f(y | x), we assume that the distribution D̄ induced by φ on R has continuous cumulative distribution function (CDF). More precisely, letting µD be the measure defining D, then D̄ is defined by the measure
µD̄(t) = µD(φ −1(t)),
where φ−1 : R → 2Z is the inverse of φ in the sense that z ∈ φ−1(φ(z)) for all z ∈ Z . Then, we assume that the CDF corresponding to D̄ is continuous. This second assumption is standard in statistical learning theory (Kearns & Vazirani, 1994). Essentially, it says that for any t ∈ R, the probability that t = − log f(y | x) must equal zero. This assumption should hold unless p(x, y) or f(y | x) are degenerate in some way. Furthermore, we can detect this case. In particular, the failure mode corresponds to the case that we see multiple points with the same value − log f(y | x). Thus, choosing T̂ = − log f(y | x) would include all these points, so the realized error rate α is larger than desired for T̂ . In this case, we can simply choose a slightly larger T̂ to avoid this problem.

heading: B.2 PROOF OF THEOREM 1
text: At a high level, our proof proceeds in three steps. First, we show that a confidence set predictor CT can be encoded as a binary classifier MT . Second, we show that a PAC bound for MT implies a PAC bound for CT (where in both cases, the unknown parameter is T ∈ R). Third, we prove PAC bounds on the error of MT̂ ; by the second step, these bounds complete our proof.
Encoding CT as a binary classifier MT . We begin by showing how the problem of learning a PAC confidence set predictor CT reduces to the problem of learning a PAC binary classifier MT . First, we show that for any T ∈ R, the confidence set predictor CT can be encoded as a binary classifier MT . Consider any parameter T ∈ Θ = R. Recall that we use the model f(y | x) to construct the confidence set predictor
CT (x) = {y ∈ Y | f(y | x) ≥ e−T }.
Now, define the map φ : Z → R by φ(x, y) = − log f(y | x), where Z = X × Y , and define the binary classifier MT : R→ {0, 1} by
MT (t) = I[t ≤ T ]. Here, I[s] is the indicator function, which returns one if a statement s is true and zero otherwise. We claim that
CT (x) = {y ∈ Y |MT (φ(x, y)) = 1}. (12) To see this claim, note that
CT (x) = {y ∈ Y | f(y | x) ≥ e−T } = {y ∈ Y | − log f(y | x) ≤ T} = {y ∈ Y | φ(x, y) ≤ T} = {y ∈ Y | I[φ(x, y) ≤ T ] = 1} = {y ∈ Y |MT (φ(x, y)) = 1},
as claimed.
PAC bound for MT implies PAC bound for CT . Next, we show that a PAC bound for MT implies a PAC bound for CT . More precisely, we design a data distribution D̃ and loss ˜̀, and show that (i) the distribution of T̃ (trained to optimizeMT ) is the same as the distribution of T̂ (constructed using our algorithm), and (ii) a PAC bound for MT̃ (where T̃ is trained on data from D̃) implies a PAC bound for CT̃ . We show that as a consequence, a PAC bound on MT̃ implies a PAC bound on CT̂ .
We begin by constructing D̃ and ˜̀. To this end, recall that D is a given distribution over X × Y . We define a data distribution D̃ over X̃ × Ỹ , where X̃ = R and Ỹ = {0, 1}, as follows. The first component of D̃ is the distribution over X̃ induced by φ from D, and the second component is the distribution over Ỹ that places all probability mass on 1. Formally, D̃ exists assuming φ is measurable, so the induced distribution exists; for all our choices of f (i.e., categorical or Gaussian), this property is satisfied. Then,
µD̃((t, a)) = µD(φ −1(t)) · I[a = 1],
where µD̃ is the measure encoding D̃, and µD is the measure encoding D. Furthermore, we define ` : Ỹ × Ỹ → {0, 1} to be the 0-1 loss `(a, a′) = I[a 6= a′]. Finally, let T̂ be chosen using our algorithm—i.e.,
T̂ = arg min T subj. to L(CT ;Z) ≤ α
L(CT ;Z) = 1 |Z| ∑
(x,y)∈Z
I[y 6∈ CT (x)],
for any α ∈ R≥0, and let T̃ be chosen similarly for MT—i.e.,
T̃ = arg min T subj. to L(MT ; Z̃) ≤ α
L(MT ; Z̃) = 1
|Z̃| ∑ (t,a)∈Z̃ `(MT (t), a) = 1 |Z̃| ∑ (t,a)∈Z̃ I[MT (t) 6= a].
Now, we show (i) above. In particular, we claim that T̂ (Z) has the same distribution as T̃ (Z̃), where Z ∼ Dn and Z̃ ∼ D̃n are random datasets. To this end, define Φ : Zn 7→ Z̃n by
Φ((z1, ..., zn)) = ((φ(z1), 1), ..., (φ(zn), 1)).
Note that
L̃(MT ; Φ(Z)) = 1
|Φ(Z)| n∑ i=1 I[MT (φ(xi, yi)) 6= 1]
= 1
|Z| n∑ i=1 I[yi 6∈ CT (xi)]
= L(CT ;Z),
from which it follows that
T̂ (Z) = arg min T subj. to L(CT ;Z) ≤ α = arg min T subj. to L̃(MT ; Φ(Z)) ≤ α = T̃ (Φ(Z)).
By construction of Φ, the random variables Z̃ and Φ(Z) have the same distribution; thus, it follows that the random variables T̃ (Z̃) and T̃ (Φ(Z)) have the same distribution as well. Since T̂ (Z) = T̃ (Φ(Z)), it follows that T̂ (Z) has the same distribution as T̃ (Z̃), as claimed.
Next, we show (ii) above. In particular, we claim that a PAC bound for MT̃ (Z̃)—i.e.,
PZ̃∼D̃n [L̃(MT̃ (Z̃)) ≤ ] ≥ 1− δ,
implies a PAC bound for CT̃ (Z̃)—i.e.,
PZ̃∼D̃n [L(CT̃ (Z̃)) ≤ ] ≥ 1− δ,
where the true losses are
L̃(MT ) = E(t,a)∼D̃[`(MT (t), a)] = P(t,a)∼D̃[MT (t) 6= a] L(CT ) = E(x,y)∼D[I[y 6∈ CT (x)]] = P(x,y)∼D[y 6∈ CT (x)].
Note that it suffices to show that the true loss for CT equals the true loss for MT—i.e.,
L(CT ) = L̃(MT ),
since this equation (together with the PAC bound for MT̃ (Z̃)) implies
PZ̃∼D̃n [L(CT̃ (Z̃)) ≤ ] = PZ̃∼D̃n [L̃(MT̃ (Z̃)) ≤ ] ≥ 1− δ,
as desired. To see the claim, note that
L̃(MT ) = P(t,a)∼D̃[MT (t) 6= a]
= ∫ I[MT (t) 6= a]dµD̃((t, a))
= 1∑ a=0 I[a = 1] · ∫ I[MT (t) 6= a]dµD(φ−1(t))
= ∫ I[MT (t) 6= 1]dµD(φ−1(t))
Now, using the change of variables t 7→ φ(z), we have
L̃(MT ) = ∫ I[MT (φ(z)) 6= 1]dµD(z)
= ∫ I[MT (φ(x, y)) 6= 1] ·D(x, y)dxdy.
Then, using (12), we have
L̃(MT ) = ∫ I[y /∈ CT (x)]D(x, y)dxdy
= P(x,y)∼D[y /∈ CT (x)] = L(CT ),
as claimed.
Finally, combining (i) and (ii), we have
PZ∼Dn [L(CT̂ (Z)) ≤ ] = PZ̃∼D̃n [L(CT̃ (Z̃)) ≤ ] ≥ 1− δ,
where the first equality follows since (i) says that T̂ (Z) (where Z ∼ Dn) has the same distribution as T̃ (Z̃) (where Z̃ ∼ D̃n), and the second inequality follows by (ii). Generalization bound. Finally, we prove the PAC bound
PZ̃∼D̃n [L̃(MT̃ ) ≤ ] ≥ 1− δ0, (13)
for MT̃ , where δ0 = ∑k i=0 ( n i ) i(1 − )n−i; for conciseness, we have dropped the dependence of T̃ on Z̃. By the previous step, this bound implies the theorem statement. To this end, we first simplify the left-hand side of the inequality (13). In particular, let T ∗ be the smallest T for which L̃(MT∗) = ; such a T ∗ exists by our assumption that D̃ has continuous density function.
First, we claim that T < T ∗ implies L̃(MT ) > L̃(MT∗). Assuming T < T ∗, then
L̃(MT ) = P(t,a)∼D̃[MT (t) 6= a] = E(t,a)∼D̃[I[MT (t) 6= a] = E(t,a)∼D̃[I[MT̂ (t) 6= 1]] = E(t,a)∼D̃ [I[I[t ≤ T ] 6= 1]] = E(t,a)∼D̃ [I[t > T ]] > E(t,a)∼D̃ [I[t > T ∗]]
= L̃(MT∗).
Assuming T ≥ T ∗, we can similarly show that L̃(MT̂ ) ≤ L̃(MT∗). It follows that PZ̃∼D̃n [ L̃(MT̃ ) > ] = PZ̃∼D̃n [ L̃(MT̃ ) > L̃(MT∗) ] = PZ̃∼D̃n [ T̃ < T ∗ ] .
As a consequence, (13) is equivalent to PZ̃∼D̃n [ T̃ < T ∗ ] ≤ δ0.
Next, recall that T̃ must satisfy L̃(MT̃ ; Z̃) ≤ α, where
L̃(MT̃ ; Z̃) = 1
n ∑ (t,a)∈Z̃ I[MT̃ (t) 6= a].
Assuming T̂ < T ∗, and using k = n · α, it follows that k ≥ ∑
(t,a)∈Z̃
I[MT̃ (t) 6= a] = ∑
(t,a)∈Z̃
I[MT̃ (t) 6= 1]
= ∑
(t,a)∈Z̃
I[t > T̃ ]
≥ ∑
(t,a)∈Z̃
I[t > T ∗].
As a consequence, we have
PZ̃∼D̃n [ T̃ < T ∗ ] ≤ PZ̃∼D̃n  ∑ (t,a)∈Z̃ I[t > T ∗] ≤ k  =
k∑ i=0 PZ̃∼D̃n  ∑ (t,a)∈Z̃val I[t > T ∗] = i  .
By our definition of T ∗, the event in the final expression says that the sum of n i.i.d. Bernoulli random variables I[t > T ∗] ∼ Bernoulli( ) is at most k. Thus, this event follows a distribution Binomial(n, ), so
PZ̃∼D̃n [ T̃ < T ∗ ] ≤ k∑ i=0 Binomial(i;n, ) = k∑ i=0 ( n i ) i(1− )n−i = δ0,
as claimed. The theorem statement follows.

heading: C DETAILS ON PROBABILITY FORECASTERS FOR SPECIFIC TASKS
text: In this section, we describe architectures for probability forecasters for classification, regression, and model-based reinforcement learning.
Classification. For the case Y = {1, ..., Y }, we choose the probability forecaster f to be a neural network with a softmax output. Then, we can compute a given confidence set
CT (x) = {y ∈ Y | f(y | x) ≥ e−T } by explicitly enumerating y ∈ Y . We measure the size of CT (x) as |CT (x)|. Regression. For the case Y = R, we choose the probability forecaster f to be a neural network that outputs the parameters (µ, σ) ∈ Y × R>0 of a Gaussian distribution. Then, we have
CT (x) =
[ µ− σ √ 2(T − log(σ √ 2π)), µ+ σ √ 2(T − log(σ √ 2π)) ] .
This choice generalizes to Y = Rd by having f output the parameters (µ,Σ) ∈ Y × Sd 0 (where Sd 0 is the set of d dimensional symmetric positive definite matrices) of a d dimensional Gaussian distribution. Note that CT (x) is an ellipsoid CT (x) = µ + ΛSd−1, where Λ ∈ Rd×d and Sd−1 is the unit sphere in Rd; in particular, Λ = D− 12Q, where QDQ> is the eigendecomposition of
(2T − d ln 2π − ln det Σ)−1 · Σ−1. We measure the size of CT (x) as ‖Λ‖F , where ‖ · ‖F is the Frobenius norm. Model-based reinforcement learning. In model-based reinforcement learning, the goal is to predict trajectories based on a model of the dynamics. We consider an MDP with states X ⊆ RdX , actions U ⊆ RdU , an unknown distribution over initial states x0 ∼ d0, and unknown dynamics g∗(x′ | x, u) mapping a state-action pair (x, u) ∈ X ×U to a distribution over states x′ ∈ X . We assume a fixed, known policy π(u | x), mapping a state x ∈ X to a distribution over actions u ∈ U . The (unknown) closed-loop dynamics are f∗(x′ | x) = Eπ(u|x)[g∗(x′ | x, u)]. Given initial state x0 ∈ X and time horizon H ∈ N, we can sample a trajectory x∗1:H = (x∗1, ..., x ∗ H) ∼ f∗ by setting x∗0 = x0 and sequentially sampling x∗t+1 ∼ f∗( · | x∗t ) for t ∈ {0, 1, ...,H−1}. Our goal is to predict a confidence setCT (x0) ⊆ XH that contains x∗1:H ∈ XH with high probability (according to both the randomness in initial states x0 ∼ d0 and in f ). This problem is a multivariate regression problem with inputs X and outputs Y = XH . We assume given a probability forecaster f(x′ | x) = N (x′;µ(x),Σ(x)) trained to predict the distribution over next states—i.e., f(x′ | x) ≈ f∗(x′ | x). Given initial state x0 ∈ X and time horizonH ∈ N, we construct the mean trajectory x̄1:H by setting x̄0 = x0 and letting x̄t+1 = µ(x̄t). To account for the fact that the variances accumulate over time, we sum them together to obtain the predicted variances Σ̃1:H—i.e.,
Σ̃t = Σ(x̄0) + Σ(x̄1) + ...+ Σ(x̄t−1).
Then, we use the probability forecast f̃(x̄1:H , Σ̃1:H) = N (x̄1:H , Σ̃1:H) (where we think of x̄1:H as a vector in RH·dX and Σ̃1:H as a block diagonal matrix in R(H·dX)×(H·dX)) to construct confidence sets.
Finally, we describe how we measure the size of a predicted confidence set CT (x0) ⊆ XH . In particular, note that CT (x0) has the form
CT (x0) = (CT,1(x0), ..., CT,H(x0)),
i.e., CT,t(x0) is the confidence set for the state xt reached after t time steps. Then, we measure the size of the confidence set for each component CT,t(x0) (for t ∈ {1, ...,H}) individually, and take the average. As in the case of regression, CT,t(x0) is an ellipsoid CT,t(x0) = x̄t + ΛtSdX−1; then, the size of CT (x0) is H−1 ∑H t=1 ‖Λt‖F .
An additional detail is that when we calibrate this forecaster, we calibrate each component CT,t(x0) individually—i.e., we use H calibration parameters τ1, ..., τH .

heading: D ADDITIONAL RESULTS

heading: D.1 COMPARISON TO ADDITIONAL BASELINES
text: We compare to two baselines that do not have theoretical guarantees. We assume given a probability forecaster f(y | x). Then, given an input x ∈ X , we construct the confidence set to satisfy∑
y∈C(x)
f(y | x) ≥ 1− . (14)
More precisely, we first rank the labels in decreasing order of f(y | x), to obtain a list (y1, y2, ..., y|Y|). Then, we choose the smallest k such that (14) holds for C(x) = {y1, ..., yk}. Intuitively, if the probabilities f(y | x) are correct (i.e., f(y | x) is the true probability of y given x), then this confidence set should contain the true label y with high probability.
For regression, we cannot explicitly rank labels y ∈ Y ⊆ Rd, but they are monotonically decreasing away from the mean. Then, assuming f(y | x) = N (y;µ(x),Σ(x)) is Gaussian, we take an ellipsoid of shape Σ(x) around µ(x) with minimum radius that captures 1 − of the probability mass of f(y | x). More precisely, we choose
C(x) = CT̂ (x)(x)
T̂ (x) = arg minT∈R T subj. to Pf(y|x)[y ∈ CT (x)] ≥ 1− ,
where CT (x) = {y ∈ Y | f(y | x) ≥ e−T } as before. Note that unlike our algorithm, the threshold T̂ (x) is not a learned parameter, but is computed independently for each new input x. We can solve for T̂ (x) efficiently by changing basis to convert f(y | x) to a standard Gaussian distribution, and then using the error function to compute the cutoff that includes the desired probability mass.
In Figure 5, we compare the confidence sets constructed using this approach with (i) the forecaster fφ̂(y | x) without any calibration, and (ii) the calibrated forecaster fφ̂,τ̂ (y | x). We plot both the confidence set sizes and the empirical error rates. For the latter, recall that a confidence set predictor C is correct if L(C) < , where L(C) the true error rate. However, we cannot measure L(C); instead, we approximate it on a held-out test set Ztest ⊆ X × Y—i.e., L(C) ≈ L̂(C;Ztest), where
L̂(C;Ztest) = 1 |Ztest| ∑
(x,y)∈Ztest
I[y 6∈ C(x)].
Intuitively, L̂(C;Ztest) is the fraction of inputs (x, y) ∈ Ztest such that the predicted confidence set for x does not contain y. We say a confidence set C is empirically valid when L̂(C;Ztest) < . Recall that our algorithm guarantees correctness with probability at least 1− δ, where δ = 10−5. As can be seen, the baseline approaches are not empirically valid in all cases. In one case—namely, the baseline with the calibrated forecaster on ImageNet—the confidence sets are almost empirically valid. However, in this case, the confidence sets are much larger than those based on our approach, despite the fact that the error rate of our confidence sets are empirically valid. Thus, our algorithms outperform the baselines in all cases.

heading: D.2 RESULTS ON ADDITIONAL IMAGENET NEURAL NETWORK ARCHITECTURES
text: We apply our approach to two additional neural network architectures for ImageNet: AlexNet (Krizhevsky, 2014) and GoogLeNet (Szegedy et al., 2015). Our results are shown in Figure 6. As can be seen, calibration reduces the confidence set sizes for AlexNet, but actually increases the confidence set sizes for GoogleNet. Thus, both calibrated and uncalibrated models may need to be considered when constructing confidence set predictors. Also, we find that confidence set sizes are correlated with classification error—the test errors for AlexNet, GoogleNet, and ResNet are 47.83%, 29.41%, and 21.34%, respectively, and their confidence set sizes decrease in the same order.

heading: D.3 RESULTS ON ADDITIONAL CLASSIFICATION DATASETS
text: We apply our approach to three small classification datasets: an Arrhythmia detection dataset (Guvenir et al., 1997), a car evaluation dataset (Bohanec & Rajkovic, 1988), and a medical alarm dataset (Bonafide et al., 2017). The confidence set sizes are shown in Figure 7. We choose larger values of and δ since we cannot obtain confidence sets that satisfy the PAC criterion with smaller and δ when the number of validation examples n is too small. For all three datasets, the empirical confidence set error is smaller than the specified error ; thus, the constructed confidence sets are empirically valid. For these datasets, the confidence set sizes of our approach C +D and our approach without calibration D are similar, most likely due to the small number of class labels.
We additionally ran our approach on a medical dataset where classification decisions are safety critical; thus, correct predicted confidence sets are required. In particular, we use the Children’s Hospital of Philadelphia (CHOP) alarm dataset (Bonafide et al., 2017). This dataset consists of vital signs from 100 patients around one year of age. One of the vital signs is the oxygen level of the blood, and a medical device generates an alarm if the oxygen level is below a specified level. The labels indicate whether the generated alarm is true (y = 1) or false (y = 0). We use n = 1000, = 0.02, and δ = 10−5. The empirical confidence set error of our approach is L̂(C;Ztest) = 0.0159.
The key question is how many false alarms can be reliably detected using machine learning to help reduce alarm fatigue. We consider an approach where we use the predicted confidence sets to detect false alarms. In particular, we first train a probability forecaster f : X → PY , where Y = {0, 1}, to predict the probability that an alarm is true, and then construct a calibrated confidence set predictor f̃ : X → 2Y based on this forecaster. We consider an alarm to be false if the predicted confidence set is f̃(x) = {0}—i.e., according to our confidence set predictor, the alarm is definitely false. Then, our PAC guarantee says that the alarm is actually false with probability at least 1 − . In summary, we suppress an alarm if f̃(x) = {0}. Using our approach, 176/630 (i.e., 27.94%) of false alarms are suppressed, while only 13/187 (i.e., 6.95%) true alarms are suppressed (see Figure 7 (d)).

heading: D.4 RESULTS ON ADDITIONAL REGRESSION DATASETS
text: We ran our algorithm on two small regression baselines—the Auto MPG dataset (Quinlan, 1993) and the student grade dataset (Cortez & Silva, 2008). We show results in Figure 8. The parameters we use are = 0.1 and δ = 0.05; as with the smaller classification datasets, we use larger choices of and δ since we cannot construct valid confidence sets for smaller choices. For the Auto MPG dataset, the empirical confidence set error of our final model C + D is L̂(C;Ztest) = 0.0597, so these are empirically valid. For the student grade dataset, the error is L̂(C;Ztest) = 0.1250, which is slightly larger than desired; this failure is likely due to the fact that the failure probability δ = 0.05 is somewhat large.

heading: D.5 ADDITIONAL RESULTS ON IMAGENET, HALF-CHEETAH, AND OBJECT TRACKING
text: Table 4 & 5 show examples of ResNet confidence set sizes for ImageNet images. Table 6 shows results for varying , δ on ResNet. Tables 7 & 8 show results for varying , δ on the Half-Cheetah. Table 9 shows visualizations of the confidence sets predicted for our object tracking benchmark.

Review summaries:
This paper propose to estimate the confidence sets for deep neural networks with PAC guarantees by combining calibrated prediction and generalization bounds from learning theory. Reliable confidence set estimation can be very useful for applications in safe-critical domains, and a paper advancing knowledge in this area is certainly welcome. The paper is clearly presented and well motivated. In addition to give a direct generalization bound that trades off between realizable setting and the VC bound, it also proposes an algorithm for predict the confidence set in practice. Experimental results in image classification and reinforcement learning illustrate the effectiveness of the proposed algorithm. One thing that may need further clarify is that the derived bound and algorithm is general in that it can be applied to any estimator f_\theta using 4 and 5. What kind of structural characteristic of neutral nets that are explicitly exploited in the algorithm in particular? Will this consideration further tighten the bound? Small typo: under Equation 5, Z^\prime_{train} is oftentimes the Z_{val}.