PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction

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.


INTRODUCTION
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 Z train -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 C T (x) ⊆ Y Published as a conference paper at ICLR 2020 |C(x)| = 1 5 ≤ |C(x)| ≤ 10 50 ≤ |C(x)| ≤ 100 |C(x)| ≥ 200 airship zebra Table 1: ImageNet images with varying ResNet confidence set sizes. The confidence set sizes are on the top. The true label is on the left-hand side. Incorrectly labeled images are boxed in red.
(parameterized by T ∈ R) should contain the true label y for at least a 1 − fraction of cases: Since we are fitting a parameter T to based on Z val , we additionally incur a probability of failure due to the randomness in Z val . In other words, given , δ ∈ R >0 , we aim to obtain probably approximately correct (PAC) confidence sets C T (x) ⊆ Y satisfying the guarantee P Zval∼D n P (x,y)∼D (y ∈ C T (x)) ≥ 1 − ≥ 1 − δ.
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, 1 ≤ |C(x)| < 5 5 ≤ |C(x)| < 10 10 ≤ |C(x)| < 20 king penguin Chihuahua, toy terrier, Italian greyhound, Boston bull, miniature pinscher banded gecko, common iguana, American chameleon, whiptail, agama, frilled lizard, alligator lizard, green lizard, African chameleon, Komodo dragon barber chair, hand blower, medicine chest, paper towel, plunger, shower curtain, soap dispenser, toilet seat, tub, washbasin, washer, toilet tissue Table 2: Confidence sets of ImageNet images with varying ResNet confidence set sizes. The predicted confidence set is shown to the right of the corresponding input image. The true label is shown in red, and the predicted label is shown with a hat. See Table 5 in Appendix D for more examples.  (Wu et al., 2013), including the ground truth bounding box (white), the bounding box predicted by the original neural network (Held et al., 2016) (red), and the bounding box produced using our confidence set predictor (green). We have overapproximated the predicted ellipsoid confidence set with a box. Our bounding box contains the ground truth bounding box with high probability. See Table 9 in Appendix D for more examples. 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.

PAC CONFIDENCE SETS
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 → 2 Y 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 (1) Finally, consider an algorithm A that takes as input a validation set Z val ⊆ Z consisting of n i.i.d. samples (x, y) ∼ D, and outputs a confidence set predictorĈ. Given , δ ∈ R >0 , we say that A is probably approximately correct (PAC) if 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).

PAC ALGORITHM FOR CONFIDENCE SET CONSTRUCTION
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 Z val ⊆ Z of n i.i.d. samples (x, y) ∼ D, and output the confidence set predictor Cθ, whereθ minimizes the empirical risk: Here, I[φ] ∈ {0, 1} is the indicator function, and the empirical riskL in an estimate of the confidence set error (1) based on the validation set Z val .
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 = |Z val |. 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: 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.

CHOICE OF PARAMETER SPACE Θ
Probability forecasters. Our construction of the parameteric family of confidence set predictors C θ assumes given a probability forecaster f : X → P Y , where P Y 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 For example, in classification, we can choose P Y 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 P Y 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, , and N (·; µ, σ 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 Note that Φ can be high-dimensional-e.g., the weights of a neural network model. Given a training set 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 Z train . 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 Then, we have the following MLE for τ : 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 Z train 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 In other words, C T (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) byT .

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, C T (x) ⊆ C T (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.

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 estimatingT 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 ∈ Θ, The details of this equivalence are given in Appendix B.2. Then, suppose we choose With this choice, for the solutionT of (3) with α = α(n, , δ), the constraint in (3) ensures that L(CT ; Z val ) ≤ α(n, , δ). Together with the VC generalization bound (7), we have P Zval∼D n 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 haveL(CT ; Z val ) = 0), we can get rates of n =Õ(1/ ) instead of n =Õ(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 We give a proof in Appendix B.2. Based on Theorem 1, we can choose

THEORETICAL GUARANTEES
We have the following guarantee, which follows straightforwardly from Theorem 1: Corollary 1. LetT be the solution to (3) for α = α(n, , δ) chosen according to (8). Then, we have In other words, our algorithm is probably approximately correct.

PRACTICAL IMPLEMENTATION
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 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
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) ∈ Z val .
In addition, note that E(x, y; T ) decreases monotonically as fφ ,τ (y | x) becomes larger. Thus, we can sort the points (x, y) ∈ Z val in ascending order of fφ ,τ (y | x), and require that only the first k * points (x, y) in this list satisfy E(x, y; T ) = 1. In particular, letting (x k * +1 , y k * +1 ) be the (k * +1)st point, (9) is equivalent to In other words, this constraint says that T must satisfy y k * +1 ∈ C T (x k * +1 ). Finally, the solutionT to (3) is the smallest T that satisfies (10), which is the T that makes (10) hold with equality-i.e., We have assumed if not, we decrement k * until this holds.

PROBABILITY FORECASTERS FOR SPECIFIC TASKS
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 C T (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 ⊆ R d U . Then , 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 x 0 ∈ X , we can sample x * 1: Then, our goal is to construct a confidence set that contains x * 1:H ∈ X H with high probability (over both the randomness in an initial state distribution x 0 ∼ d 0 and the randomness in f * ).
To do so, we construct and use a forecasterf (x 1:H | x 0 ) based on f . In principle, this task is a special case of multivariate regression, where the inputs are X (i.e., the initial state x 0 ) and the outputs are Y = X H (i.e., a predicted trajectory x 1: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 meanx 1: We use a probability forecasterf (x 1:H | x 0 ) = N (x 1:H ;x 1:H ,Σ 1:H ) to construct confidence sets.

EXPERIMENTS
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. 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 R 4 ), and the current image. The output space Y = R 4 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., (x min , y min , x max , y max ). 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.

CONCLUSION
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).  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 Now, if we take temperature τ very large, then the labels become roughly 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 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 ∈ C T (x ), then it must be the case that C T (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.

A.2 USEFULNESS OF DIRECT BOUND
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) 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. 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.

B THEORETICAL GUARANTEES B.1 ASSUMPTIONS
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 distributionD induced by φ on R has continuous cumulative distribution function (CDF). More precisely, letting µ D be the measure defining D, thenD is defined by the measure where φ −1 : R → 2 Z is the inverse of φ in the sense that z ∈ φ −1 (φ(z)) for all z ∈ Z. Then, we assume that the CDF corresponding toD 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, choosingT = − log f (y | x) would include all these points, so the realized error rate α is larger than desired forT . In this case, we can simply choose a slightly largerT to avoid this problem.

B.2 PROOF OF THEOREM 1
At a high level, our proof proceeds in three steps. First, we show that a confidence set predictor C T can be encoded as a binary classifier M T . Second, we show that a PAC bound for M T implies a PAC bound for C T (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 C T as a binary classifier M T . We begin by showing how the problem of learning a PAC confidence set predictor C T reduces to the problem of learning a PAC binary classifier M T . First, we show that for any T ∈ R, the confidence set predictor C T can be encoded as a binary classifier M T . Consider any parameter T ∈ Θ = R. Recall that we use the model f (y | x) to construct the confidence set predictor Here, I[s] is the indicator function, which returns one if a statement s is true and zero otherwise. We claim that To see this claim, note that as claimed.
PAC bound for M T implies PAC bound for C T . Next, we show that a PAC bound for M T implies a PAC bound for C T . More precisely, we design a data distributionD and loss˜ , and show that (i) the distribution ofT (trained to optimize M T ) is the same as the distribution ofT (constructed using our algorithm), and (ii) a PAC bound for MT (whereT is trained on data fromD) 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 constructingD and˜ . To this end, recall that D is a given distribution over X × Y.
We define a data distributionD overX ×Ỹ, whereX = R andỸ = {0, 1}, as follows. The first component ofD is the distribution overX induced by φ from D, and the second component is the distribution overỸ 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, where µD is the measure encodingD, and µ D is the measure encoding D. Now, we show (i) above. In particular, we claim thatT (Z) has the same distribution asT (Z), where Z ∼ D n andZ ∼D n are random datasets. To this end, define Φ : Z n →Z n by Φ ((z 1 , ..., z n )) = ((φ(z 1 ), 1), ..., (φ(z n ), 1)).

Note thatL
from which it follows that By construction of Φ, the random variablesZ and Φ(Z) have the same distribution; thus, it follows that the random variablesT (Z) andT (Φ(Z)) have the same distribution as well. SinceT (Z) = T (Φ(Z)), it follows thatT (Z) has the same distribution asT (Z), as claimed.
Next, we show (ii) above. In particular, we claim that a PAC bound for MT (Z) -i.e., implies a PAC bound for CT (Z) -i.e., where the true losses arẽ Note that it suffices to show that the true loss for C T equals the true loss for M T -i.e., since this equation (together with the PAC bound for MT (Z) ) implies Now, using the change of variables t → φ(z), we havẽ Then, using (12), we haveL as claimed.
Finally, combining (i) and (ii), we have where the first equality follows since (i) says thatT (Z) (where Z ∼ D n ) has the same distribution asT (Z) (whereZ ∼D n ), and the second inequality follows by (ii).
Generalization bound. Finally, we prove the PAC bound for MT , where δ 0 = k i=0 n i i (1 − ) n−i ; for conciseness, we have dropped the dependence ofT onZ. 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(M T * ) = ; such a T * exists by our assumption thatD has continuous density function.
First, we claim that T < T * impliesL(M T ) >L(M T * ). Assuming T < T * , theñ Assuming T ≥ T * , we can similarly show thatL(MT ) ≤L(M T * ). It follows that As a consequence, (13) is equivalent to Next, recall thatT must satisfyL(MT ;Z) ≤ α, wherẽ AssumingT < T * , and using k = n · α, it follows that k ≥ As a consequence, we have 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 as claimed. The theorem statement follows.

C DETAILS ON PROBABILITY FORECASTERS FOR SPECIFIC TASKS
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 by explicitly enumerating y ∈ Y. We measure the size of C T (x) as |C T (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

This choice generalizes to
We measure the size of C T (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 ⊆ R d X , actions U ⊆ R d U , an unknown distribution over initial states x 0 ∼ d 0 , 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 x 0 ∈ X and time horizon H ∈ N, we can sample a trajectory x * 1:H = (x * 1 , ..., x * H ) ∼ f * by setting x * 0 = x 0 and sequentially sampling x * t+1 ∼ f * ( · | x * t ) for t ∈ {0, 1, ..., H−1}. Our goal is to predict a confidence set C T (x 0 ) ⊆ X H that contains x * 1:H ∈ X H with high probability (according to both the randomness in initial states x 0 ∼ d 0 and in f ). This problem is a multivariate regression problem with inputs X and outputs Y = X H .
To account for the fact that the variances accumulate over time, we sum them together to obtain the predicted variancesΣ 1:H -i.e., Then, we use the probability forecastf (x 1:H ,Σ 1:H ) = N (x 1:H ,Σ 1:H ) (where we think ofx 1:H as a vector in R H·d X andΣ 1:H as a block diagonal matrix in R (H·d X )×(H·d X ) ) to construct confidence sets.
Finally, we describe how we measure the size of a predicted confidence set C T (x 0 ) ⊆ X H . In particular, note that C T (x 0 ) has the form i.e., C T,t (x 0 ) is the confidence set for the state x t reached after t time steps. Then, we measure the size of the confidence set for each component C T,t (x 0 ) (for t ∈ {1, ..., H}) individually, and take the average. As in the case of regression, C T,t (x 0 ) is an ellipsoid C T,t (x 0 ) =x t + Λ t S d X −1 ; then, the size of C T (x 0 ) is H −1 H t=1 Λ t F . An additional detail is that when we calibrate this forecaster, we calibrate each component C T,t (x 0 ) individually-i.e., we use H calibration parameters τ 1 , ..., τ H .

D.1 COMPARISON TO ADDITIONAL BASELINES
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 More precisely, we first rank the labels in decreasing order of f (y | x), to obtain a list (y 1 , y 2 , ..., y |Y| ). Then, we choose the smallest k such that (14) holds for C(x) = {y 1 , ..., y k }. 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 ⊆ R d , 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 Conf. set size Figure 6: Confidence set sizes for two neural network architectures trained on ImageNet; for both, we use n = 20, 000, = 0.01 and δ = 10 −5 . Left: AlexNet (Krizhevsky, 2014); here, the empirical confidence set error of our approach C + D is 0.0066. Right: GoogLeNet (Szegedy et al., 2015); here, the empirical confidence set error of our approach is 0.0061.
where C T (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 forT (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 Z test ⊆ X × Y-i.e., L(C) ≈L(C; Z test ), wherê Intuitively,L(C; Z test ) is the fraction of inputs (x, y) ∈ Z test such that the predicted confidence set for x does not contain y. We say a confidence set C is empirically valid whenL(C; Z test ) < . 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.

D.2 RESULTS ON ADDITIONAL IMAGENET NEURAL NETWORK ARCHITECTURES
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.

D.3 RESULTS ON ADDITIONAL CLASSIFICATION DATASETS
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 isL(C; Z test ) = 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 → P Y , where Y = {0, 1}, to predict the probability that an alarm is true, and then construct a calibrated confidence set predictor f : X → 2 Y based on this forecaster. We consider an alarm to be false if the predicted confidence set isf (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 iff (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)).

D.4 RESULTS ON ADDITIONAL REGRESSION DATASETS
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 isL(C; Z test ) = 0.0597, so these are empirically valid. For the student grade dataset, the error isL(C; Z test ) = 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.   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.
barber chair, hand blower, medicine chest, paper towel, plunger, shower curtain, soap dispenser, toilet seat, tub, washbasin, washer, toilet tissue vulture, great grey owl, bittern tiger cat, lynx, leopard, snow leopard, jaguar, tiger, cheetah amphibian, cassette player, fire engine, minibus, minivan, passenger car, pole, police van, puck, racer, radio, school bus, screwdriver, streetcar, trolleybus junco, water ouzel, water snake, drake, red-breasted merganser, goose, crayfish, little blue heron, European gallinule, ruddy turnstone, red-backed sandpiper, redshank, dowitcher, oystercatcher, albatross, otter indigo bunting, bee eater, hummingbird, jacamar   Table 5: Confidence sets of ImageNet images with varying ResNet confidence set sizes. The predicted confidence set is shown to the right of the corresponding input image. The true label is shown in red, and the predicted label is shown with a hat. Conf. set size Table 6: Confidence set sizes for ResNet trained on ImageNet, for varying , δ and for n = 20, 000. The plots are as in Figure 1  Conf. set size (log-scale) Table 7: Confidence set sizes for a neural network dynamics model trained on the half-cheetah environment, for varying , δ and for n = 5000. The plots are as in Figure 3 Figure 3 (b). , and the bounding box produced using our confidence set predictor (green). We have overapproximated the predicted ellipsoid confidence set with a box. Our bounding box contains the ground truth bounding box with high probability.