PAC Confidence Sets for Deep Neural Networks via Calibrated Prediction
Authors: Sangdon Park
Osbert Bastani
Nikolai Matni
Insup Lee
Venue:  (2020)
Keywords: PAC
confidence sets
classification
regression
reinforcement learning

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.

Published as a conference paper at ICLR 2020
PAC CONFIDENCE SETS FOR DEEP NEURAL NET- WORKS VIA CALIBRATED PREDICTION
Sangdon Park
Osbert Bastani
University of Pennsylvania
University of Pennsylvania
sangdonpéci s. upenn edu
obastani @seas upenn edd
Nikolai Matni
Insup Lee
University of Pennsylvania mmatni@seas upenn. edu
University of Pennsylvania leefcis, upenn. edu
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 dynamics model for the half-cheetah reinforcement learning prob- lem.
INTRODUCTION
A key challenge facing deep neural networks is that they do not produce reliable confidence esti- mates, 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. (017).
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 al.) (2044): even in this setting, confidence estimates produced by deep neural networks are notoriously unreliable (Guo al. 2017 One intuition for this shortcoming is that unlike traditional supervised learning al- gorithms, deep learning models typically overfit the training data (Zhang et al. 2017). As a con- sequence, 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 temperature scaling (Plat[ 1999p. This ap- proach takes as input a trained neural network fz(y x)-iee. whose parameters Φ have already been fit to a training dataset Zurin- produces unreliable probabilities fz(y x).. Then, this approach rescales these confidence estimates based on a validation dataset to improve their "calibra- tion". More precisely, this approach fits confidence estimates of the form
(y x) x exp(T log fg(2) x)),
where 7 E Rso 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 7 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 guar- antees while being small as possible. Given test input E X,, confidence set Cr(x) y
Our code is available at /ttt:pa///gtttbbbcom//eee/ http://hww....oooooooo////ccaaaa -enneeeeooiiieeeeeeeeee

---

Published as a conference paper at ICLR 2020
[C(x)]
S (x) S 10
50 <
[C(x) - 100
((() N 200
Skadalenetie
zebra
Table I: ImageNet images with varying ResNet confidence set sizes. The confidence set sizes are on the top. The true label is the left-hand side. Incorrectly labeled images are boxed in red.
(parameterized by T E I)) should contain the true label y for at least a 1 fraction of cases:
F(a.y)~Dly E Cr(x)] 2 1-c.
Since we are fitting parameter to based on Zval= we additionally incur a probability of fail- due to the randomness in Zval- In other words, given e, Rso, aim obtain probably approximately correct (PAC) confidence sets Cr(x) C y satisfying the guarantee
BairD (Pe.)))n(( e Cr(z)) 2 1 1-c) 2 2
Indeed, techniques from statistical learning theory (Vapnik 1999) can be used to do so (Vovk 2013).
There are number of reasons why confidence sets can be useful. First, they can be used inform safety critical decision making. For example, consider a doctor who uses prediction tools to help perform diagnosis. Having confidence set would both help the doctor estimate the confidence of the prediction (i.e., smaller confidence sets imply higher confidence), but also give 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 confidence set over predicted trajectories to determine whether is safe to act with high probability. As concrete example, consider self-driving car that path that a pedestrian might take. We require that the self-driving car avoid the pedestrian with high probability, which can do by avoiding all possible paths in the predicted confidence set.
deep neural network to predict the
Contributions. We propose an algorithm combining calibrated prediction and statistical learning theory construct PAC confidence sets for deep neural networks (Section B We propose instantia- tions of this framework in the settings of classification, regression, and learning models for reinforce- ment 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 vi- sual object tracking benchmark (Wu al. (013)) and a probabilistic dynamics model (Chua 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 As can 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
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 given ex- pected 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
2

---

Published as a conference paper at ICLR 2020
(a(x)
S [C(x) 10
10 |C(x)) 20
banded gocko, chameleun, whipeail. againa. frilled lizun),
Chilushin, tay tenier, Iaalin greyhoumd, Roston hull. mimature pinscher
king penguin
alligatoe
green licard. African chameleon, Komodo dragon
English springer, Welsh springer spaniel collie, beser.
allar, analog clock, bell cose, castle, church, cinema, dome, munustery, paliace, vanill; wall clock
shopping Busket
Leanberg
barber chair. blower, medicine chest, rowel, planger, curtain, scop dispenser, toilct tub. washahusin, washer, roilet tissue
face powder,
chambered
humper; Intion, packet, shopping basket
nounlla
Table 2: Confidence sets of ImageNet images with varying ResNet confidence set sizes. The pre- dicted 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 hat. See Table 5 in Appendix D for more examples.
including the ground truth bounding box (white), the bounding box predicted by the original neural network (Held 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 in Appendix D more examples.
Table 3: Visualization of confidence for the tracking dataset (Wu al. 2013
2018). There has also been work the setting 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 (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 al. 2019).
The most closely related work on conformal prediction (Papadopoulos) 2008 Vovk 2013). Like our approach, this line of work provides way to construct confidence sets from given confidence predictor, and provided PAC guarantees for the validity of these confidence sets. Indeed, with some work, our generalization bound Theorem I can be shown to be equivalent Theorem 1 in Vovk (2013). In contrast to their approach, we proposed to use calibrated prediction to construct confi- dence predictors that can suitably be used with deep neural networks. Furthermore, approach
3

---

Published as a conference paper at ICLR 2020
makes explicit the connections to temperature scaling and well to generalization bounds from statistical learning theory (Vapnik] 1999). In addition, unlike our paper, they do not explicitly pro- vide efficient algorithm for constructing confidence sets. Finally, we also propose extension to the case of learning models for reinforcement learning.
Finally, we build long line of work calibrated prediction, which aims to construct "cali- brated" probabilities (Murphy) DeGroot & Fienberg 1983 Platt 1999. Zadrozny & Elkan 2001 2002] Naeini al. [2015] Kuleshov & Liang] 2015). Roughly speaking, probabilities are cal- ibrated if events happen at rates equal to the predicted probabilities. This work has recently been applied 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 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' x V. A confidence set predictor is function C' : X' + 2 such that (z) S y a set of labels; we denote the set of all confidence set predictors by For a given example (z, v) ~ D, we say C' is correct if y E C(z). Then, the eπror of C' is
I(C) P ((.,))>Dy @ C(x)).
Finally, consider an algorithm A that takes as input a validation set Zval S Z consisting of n i.d. samples (xx y) ~ D, and outputs a confidence set predictor Ò. Given c, 5 E Ry0, we say that A is probably approximately correct (PAC) if
P [LC] > e where Ć = A(Zval) <
Our goal is to design an algorithm A that satisfies ( 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 classifi- cation, we consider confidence sets that are arbitrary subsets of labels C(x) S y = (1,.., Y }. and we measure the size by [C(x)] E N i.e., the number of labels in C(x). For regression, we consider confidence sets that are intervals C(x) (a. bj S
E. and we measure size by b a -...e. the length of the predicted interval. Note that there is an intrinsic tradeoff between satisfying 22) and average size of C(xr)-lrger 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 training set Zval S Z of n i.i.d. samples (x, 3) ~ D, and output the confidence set predictor C where 0 minimizes the empirical risk: where L(C; n
{Ca
θ), where θ is the parameter space, and (ii)
i arg min L(Co; Zva) dee
Σ 1ly $ C(z)).
(x.))
Here, I[Ø] E {0, 13 the indicator function, and the empirical risk L. in an estimate of the confidence set error based on the validation set Z
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 PAC constraint on the true risk I.(0) based on the given PAC parameters ê E Rş0 and the number of available validation samples n = Zvall 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(0) subj. to i(C; 7ra) S 8E0
(3)
4

---

Published as a conference paper at ICLR 2020
At high level, the value = a(n, c, E Ryo 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 θ 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 our choice of parameter space. In the remainder of this section, we describe the choices of (i) parameter space O. (ii) size metric S(O), and (iii) confidence level (nn, e, 6) in more detail, as well as how solve given these choices.
3.1 CHOICE OF PARAMETER SPACE +
Probability forecasters. Our construction of the parameteric family of confidence set predictors Co assumes given a probability forecaster f X + Py. where Py is a space of probability distributions over V. Given such an f. use fly x) denote the probability of label y under distribution f(x). Intuitively, f z) should be the probability (or probability density) that y is the true label for given input x-i.e. f(y 2)) se P(x,Y)=D!
y X x]. For example, in classification, can choose Py to be the space of categorical distributions over V. and ff may be a neural network whose last layer is softmax layer with [Y] outputs. Then, f(y x)) f(z)y. Alternatively, in regression, we can choose Py to be the space of Gaussian distributions, and I may be neural network whose last layer outputs the values (H, E R x Ry0 of Gaussian distribution. Then, where (n(z), (()) f(x), and Nod o²) is the Gaussian density
f(y r) = [<;; (()) (z)²), function with mean ii and variance o².
Training a probability forecaster. To train probability forecaster, we use a standard approach to calibrated prediction that combines maximum likelihood estimation with temperature scaling. First, we consider a parametric model family F = {fo Φ E }). where & is the parameter space. Note that & can be diah-nmmnniionll-- e.g., the weights of neural network model. Given a training set Z C 2 of m i.i.d. samples (x, ~ D, the maximum likelihood estimate (MLE) of Φ is
arg min ((d; Zuain)
where
l(d;; Zumin) =
log Jols x).
(4)
oE#
(m.3)) Zuiá
We could now use f3 as the probability forecaster. However, the problem with directly using & is that because è may be high-dimensional, it often overfits the training data Zerain Thus, the probabilities are typically overconfident compared what they should be.
To reduce their confidence, we use the lemperature scaling approach to calibrate the predicted probabilities (Platt 1999 Guo al. 2017). Intuitively, this approach to train an MLE estimate using exactly the same approach used to train e. but using single new parameter 7 E RR>0- The key idea that this time, the model family is based on the parameters & from 44). In other words, the "shape" of the probabilities forecast by fg are preserved, but their exact values are shifted.
More precisely, consider the model family F' VSrr I E 1R where
(u x exp (r log fa(y x))
Then, we have the following MLE for T:
arg min E' (T; ?
where
('(T; ((Triiiinn
Σ (z.))
log S fū. 2))
(5)
=CR
Note that f is estimated based on a second training set Zrainn Because we are only fitting a single parameter, this training set can be much smaller than the training Zuzin used to fit é.
Parametric family of confidence set predictors. Finally, given a probability forecaster f. we con- sider one dimensional parameter space θ IR; in an analogy the temperature scaling technique for calibrated prediction, we denote this parameter by 7' E e. In particular, we assume a confidence probability predictor f is given, and consider
Cr(x) = tu E y f(y x) 2 TT..
2 A priori, it is not obvious that using temperature scaling can improve our confidence set predictor; we give detailed discussion in Appendix A.
5

---

Published as a conference paper at ICLR 2020
In other words, (2) is the set of with high probability given x according f. Considering this scalar parameter space, we denote the minimum of (3) by 7.
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 uniformly smaller confidence sets-i.e.,
T = Vx. Cr(x) - Cr)
Thus, 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 ann,,, 6,
Naive approach based on VC generalization bound. naive approach to choosing a(n, G, 5) is to do so based on the VC dimension generalization bound (Vapnik) (999). 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 E O
L(Cr) S L(Cri Zvai) + (og(2m) + log()/4)
D" D
21-8
The details of this equivalence are given in Appendix B.2 ann, c, c log(2n) + - log(6/4)
Then, suppose we choose
With this choice, for the solution I of (3) with a = a(n, e, 6), the constraint ensures that [CG; Zvai) S a((n,,,8) Together with the VC generalization bound (7), we have
P Pn [L(Cp) > c] <
which is exactly desired the PAC constraint
predicted confidence sets.
Direct generalization bound. In fact, we can get better choices of a by directly bounding general- ization error. For instance, in the realizable setting (i.c., we always have [(C. Zva)) = 0), we can rates of = ((1/e) instead of n Ô(1/c) (Karns & Vazirani 1994); see Appendix A.2 for details. We can achieve these rates by choosing a 0, but then, PAC guarantees we obtain may actually be stronger than desired (i.e., for e' < e). Intuitively, we can directly prove bound that interpolates between the realizable setting and the VC generalization bound-ing particular:
Theorem 1. For any E [0, 11. E Noo. and A: E {0, 1,.., n2 we have
P P [L(C+) > c)
e'(1 - -))
where i is the solution to
with k/
We give proof in Appendix B.2 Based on Theorem I we can choose
max k/n subj. Σ ! el -c)n=i<> <
a(n,c,0)
KENL(U)
3.4 THEORETICAL GUARANTEES
We have the following guarantee, which follows straightforwardly from Theorem 1 Corollary 1. Let T be the solution for = a(n, e, 5) chosen according to 8 Then, we have
P.wan Dm [L(Cp) > <.
In other words, our algorithm is probably approximately correct.
Thhe theorem statement relies additional standard technical conditions; see Appendix B.1

---

Published as a conference paper at ICLR 2020
Algorithm 1 Algorithm for solving
procedure ESSTRAATCCONIDDDNSSEEEEEEEDCCC Zuain Zirain Zvai)
Estimate è, using 4 and ( respectively
Compute (n,,, e, 6) according to (8) by enumerating & (0.,,...,
Let k = T1 a(n,, e, d) (note that E ( (O.1,..,,,)
Sort (z,y) E Zval in ascending order of (3
Let (z +1++1) be the (k* + 1)st element in the sorted Zval
Solve (3) by choosing T = log Ja. (yR- x(++1)
Return C : x + {y E y fa 2) 2 2c-
end procedure
3.5 PRACTICAL IMPLEMENTATION
Our algorithm for estimating confidence set predictor Cp is summarized in Algorithm 1 The algorithm solves the optimization problem (3) using the choices O S(T), and a(n, c, 6) described in the preceding sections. There are two key implementation details that we describe here.
a(n, e, 8). To compute (n, o) we need to solve 8 A straightforward approach is to enumerate all possible choices of k E {0, 1,..,,,,, nt. There are two optimizations. First, the objective ascending order until the constraint no longer
Computing
monotone increasing in so we can enumerate
holds. Second, rather than re-compute the left-hand side of the constraint Ei (1))'(1-0 - -)"-
we can accumulate the sum as we iterate over k. We can also incrementally compute (?). 6", and
(1 e)n- For numerical stability, we perform these computations in log space.
Solving (3.. To solve
3 note that the constraint 3 is equivalent to
E( S n a(n,e,,) where E(s, y: T) = [T (w) <o-).
(9)
Also, note that k* adn, e, 5) is an integer due to the definition of (n,, e, in 8 Thus, can interpret (9) as saying that E(x, y; T) = 1 for at most h" of the points (x, y) E Zvai-
In addition, note that E(x, y; T) decreases monotonically as fa.=() x)) becomes larger. Thus, we can sort the points (x, Zval ascending order of fa.+ (v z)), and require that only the first points (I. in this list satisfy F(x, y; T) = 1. In particular, letting (ox=+1 (1-+1) 1) be the (I* + 1)st
point, (9) is equivalent
fa. (y xx*+1) T-.
(10)
In other words, this constraint says that 7 must satisfy yk*+1 E Cr( Finally, the solution f to 3 is the smallest 7" that satisfies (00). which is the I that makes (10) hold with equality- i...
f log fo.+ (yk++1 21)+1).
(11)
We have assumed J3, (Mie+ (x4+1)) > S6,+ (vk- xy ); if not, we decrement ks until this holds.
3.6 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 Cr(x), in Appendix C We consider three tasks: classification, regression, and model-based reinforcement learning. For classification, we use the standard approach of using soft-max layer to predict label probabilities also a standard approach where the neural network predicts both
fly | x²). For regression, the mean (u(x) and covariance E(x) of a Gaussian distribution ((((x), I(x)): then, f(y x)) = (y; p(z), E(x)) is the probability density of according to this Gaussian distribution.
Finally, for model-based reinforcement learning, our goal is to construct confidence sets over trajectories predicted using learned model of the dynamics. We consider unknown dynamics
7

---

Published as a conference paper at ICLR 2020
1000
1000
Conf. set size
Conf. set size
600
000
200
200
cornect
incomect
(a)
(b)
1000
1000
800
Conf. set size
Conf. size
600
600
200
200
(c)
(d)
Figure 1: Results on ResNet for ImageNet with n 20000. Default parameters are = 0.01 and 8 10-5 5 We plot the median and min/max confidence set sizes. (a) Ablation study; C is "calibrated predictor" (i.e., use fa.+ instead of fa), and D is "direct bound" (i.e., use Theorem instead of the VC generalization bound). (b) Restricted to correctly vs. incorrectly labeled images. (c) Varying c. (d) Varying
g0(x" | Ix. u) mapping state-action pair (x, u) distribution states x', and consider known (and fixed) policy Tr x) mapping a given state x to a distribution over actions u E U S Rd Then, we let f (x' 2) Ba(()=) [g" (x' u]] denote the (unknown) closed-loop dynamics.
Next, we consider forecaster f(x' xx) v f"(x') a:) of the form f(x' x)) = -N(''s ((x); M(x)), and our goal 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 time horizon H E N. In particular, given initial state 2y E X, we can sample z = (I',..., FH f by letting z = zo and sequentially sampling #++1 f(- x;)) for each t 10, H 1}. Then, goal is construct confidence that contains oi.H E X with high probability (over both the randomness in initial state distribution
do and the randomness in f*).
To do so, we construct and use a forecaster f(I (n) based on f. In principle, this task is special of multivariate regression, where the inputs X' (i.e., the initial state 2o) and the outputs are y = x (i.e., a predicted trajectory æ1.H). However, the variance E(x) predicted by our probability forecaster only for single step, and does not take into account the fact that is itself uncertain. Thus, we use a simple heuristic where we accumulate variances over time. More precisely, we construct (i) the predicted mean Z1:H = (Z.,..,, FHH by io = In and T++1 = ((x)) E [0, 1, 1}, and (ii) the predicted variances E1.1 = (Si,.., En) by
Σ = E(To) + (a) +... + [(T--1).
We use probability forecaster f(x1.H xo) Nx TI.H Er:H) to construct confidence sets.
EXPERIMENTS
We describe experiments ImageNet (a classification task), 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
8

---

Published as a conference paper at ICLR 2020
400
400
35.0
25.-
Conf. set size
300
-010
300
250
25.0
250
set
Conf. set
200
-00
200
150
130
150
100
100
100-
50
50-
50-
0
C+0
0.91
9.02
0.03
0.04
0.05
10
10"
2
(a)
(b)
(c)
Figure 2: Confidence set sizes for an object tracking benchmark (Wu et al. 2013); we use n 5, 000, 0.01, and 5 10-5, (a) Ablation study similar Figure In (b) and (c), we show how the confidence set sizes produced using our algorithm vary with respect to and 6, respectively.
ResNet for ImageNet. We use algorithm to compute confidence sets for ResNet (He et al. 2016) on ImageNet (Russakovsky et al. 2.15), for = 0.01, = 10 and n = 20000 validation images. approach to an ablation. In particular,
We show the results in Figure [ In (a), we compare C' refers to performing an initial temperature scaling step to calibrate the neural network predictor (i.e., using f instead of fa ), and (ii) D refers using Theorem iintted of the VC generalization bound, Thus, C + D refers our approach. As can be seen, using calibrated predictor produces noticeable reduction in the maximum confidence set size.
We also compared the ablation C-i.e., using the VC generalization bound. However, were unable to obtain valid confidence sets for our choice of e and i-i.e., (3) is infeasible. That is, using Theorem outperfomm 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 d in Appendix [ 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 8, respectively. 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 single- object tracking task, which is multivariate regression problem. Specifically, the input space X consists of the previous image, the previous bounding box (in R+), and the current image. The output space y = IR is current bounding box. We use the regression-basee based tracker from Held et al. (2)1)) 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. (æmin: Jmin Tmax: Fmax). Given this bounding box forecaster fg. we calibrate and estimate a confidence set predictor as described in Section 3.6
We the visual object tracking benchmark from Wu et al. (2013) to train and evaluate con- fidence 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, valida- tion set for confidence set estimation, and test set for evaluation. For each sequence, pair of two adjacent frames constitute single example. Our training dataset contains 20,882 labeled examples, each consisting of of 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, respec- tively. 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 is too small to get 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 al., 2016), for c= 0.01, 5 = 10 H 20 time steps, and n = 5000 validation rollouts. When using temperature scaling to calibrate fa to obtain fā.+, calibrate each dimension of time steps independently (i.e., fit H parameters, where H is time horizon). We show the results in Figure

---

Published as a conference paper at ICLR 2020
100
1024
Conf. set size (log-scale)
C+D
10t:
1P
A+D
10
10
A+C+D (ours)
109
Cont. set size
10"
100
10*
10*
101
141
10a
C:D
A:D
A:C.ID
10-
Time
(a)
(b)
1044
103
Cont. set size [log-Scale)
Conf. set size (log-scale)
1012
10t
20*
10*
20f
10a
30²
10
10
10
6
(c)
(d)
Figure 3: Results the dynamics model for the half-cheetah with 5000. Default parameters are e 0.01 and = 10 (a) Ablation study; is "accumulated variance" (i.e., for each E use En instead of Σn ((),-))), and and are as for ResNet. We plot the median and min/max confidence set sizes (see Section 3.6 averaged across ablations, but with per time step size. We plot the average size of the confidence set for the predicted state 2t step i, as function of t {I, 20). (c) Varying e, and (d) varying d.
{1...., 20). (b) Same
In (a), we compare to two ablations. The labels C and D are as for ResNet; in addition, refers to using the accumulated variance Σ, instead of the one-step predicted variances E, E(ā,-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 for the given and In (b), we show the same ablations over the entire trajectory until 20. As can be seen, using the calibrated predictor produces a large gain; these gains are most noticeable the tails. Using the accumulated confidence produces 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 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 in- stance, they can be used to inform safety-criticll decision-naking, and to ensure safety with high- probability in roboties control settings that leverage deep neural networks for perception. Future work includes extending these results to more complex tasks (c.g., structured prediction), and han- dling covariate shift (c.g., handle policy updates reinforcement learning).
ACKNOWLEDGMENTS
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. BA8750-18-C-000 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.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshirani. Predictive inference with the jackknife+. arXiv preprint arXiv: 140i::9905.000 02928, 2019.
Felix Berkenkamp, Mattco Turchetta, Angela Schoellig, and Andreas Krause. Safe model-based reinforcement learning with stability guarantees. In Advances in neural information processing systems, pp. 908 918, 2017.
Marko Bohanec and Vladislav Rajkovic. Knowledge acquisition and explanation for multi-attribute decision making. In 8th Intl Workshop on Expert Systems and their Applications, 1988.
Christopher Bonatide, Russell Localio, John H Holmes, Vinay M Nadkarni, Shannon Stemler, Matthew MacMurchy, Miriam Zander, Kathryn E Roberts, Richard Lin, and Ron Keren. Video analysis of factors associated with response time physiologic monitor alarms childrens hospital. JAMA pediatrics, 171(6)5524-533) 2017.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv:1606.01540 2016.
Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learn- ing in handful of trials using probabilistic dynamics models. In Advances in Neural Information Processing Systems, pp. 4754-4765, 2018.
Paulo Cortez and Alice Maria Goncalves Silva. Using data mining to predict secondary school student performance. 2008.
Morris H DeGroot and Stephen E Fienberg. The comparison and evaluation of forecasters. Journal of the Royal Statistical Society: Series D (The Statistician), 32(1-2):12-22, 1983.
Christophe Denis and Mohamed Hebiri. Confidence sets with expected sizes for multiclass classifi- cation. The Journal of Machine Learning Research, 18(1):5571-3598, 2017.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In Proceedings of the 34th International Conference Machine Learning- Learning-Volume Volume 70, pp. 1183-
1192. JMLR. org, 2017.
Chuan Guo, Gcoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. arXiv preprint arXiv: / 170.04459, 2017.
H Altay Guvenir, Burak Acar, Gulsen Demiroz, and Ayhan Cekin. A supervised machine learning algorithm for arrhythmia analysis. In Computers in Cardiology 1997, pp. 433-436. IEEE, 1997.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
David Held, Sebastian Thrun, and Silvio Savarese. Learning to track at 100 fps with deep regression networks. In European Conference Computer Vision, pp. 749-765. Springer, 2016.
Michael Kearns and Umesh Virkumar Vazirani. An introduction to computational learning theory. MIT press, 1994.
Alex Krizhevsky, One weird trick for parallelizing convolutional neural networks. arXiv preprint 1rXiv:1404.5997, 2014.
Volodymyr Kuleshov and Percy S Liang. Calibrated structured prediction. Advances in Neural Information Processing Systems, pp. 3474-3482, 2015.
Volodymyr Kuleshov, Nathan Fenner, and Stefano Ermon. Accurate uncertainties for deep learning using calibrated regression. arXiv preprint arXiv:1807.002633 2018.
Jing Lei. Classification with confidence. Biometrika, 101(4):755-76, 2014.

---

Published as a conference paper at ICLR 2020
Jing Lei, Max GSell, Alessandro Rinaldo, Ryan Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113 1733:1094-1111,201 2018.
Ali Malik, Volodymyr Kuleshov, Jiaming Song, Danny Nemer, Harlan Seymour, and Stefano Er- mon. Calibrated moddel-based deep reinforcement learning. In International Conference on Ma- chine Learning, pp. 2:14-4322 2019.
Allan H Murphy, Scalar and vector partitions of the probability score: Part i. two-state situation. Journal of Applied Meteorology, 11(2):73-282, 1972.
Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht. Obtaining well calibrated prob- abilities using bayesian binning. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
Harris Papadopoulos. Inductive conformal prediction: Theory and application to neural networks. In Tools in artificial intelligence. IntechOpen, 2008.
T Pearce, M Zaki, A Brintrup, and A Neely. High-quality prediction intervals for deep learning: A distribution-free, ensembled approach. In 35th International Conference on Machine Learning, ICMI. 2018, volume 9, pp. 6473-6488 2018.
John Platt. Probabilistic outputs for support vector machines and comparisons regularized likeli- hood methods. Advances in large margin classifiers, 1999.
J Ross Quinlan. Combining instance-based and model-based learning. In Proceedings of the Tenth International Conference on International Conference on Machine Learning, pp. 236-243. Mor- gan Kaufmann Publishers Inc., 1993.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma. Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recogmition challenge. International journal of computer vision, 115(3):211-22) 2015.
Lukas Steinberger and Hannes Leeb. Leave-one-out prediction intervals in linear regression models with many variables. arXiv preprint arXiv: 16Xivv1602..55811, 2016.
Lukas Steinberger and Hannes Leeb. Conditional predictive inference for high-dimensional stable algorithms. arXiv preprint 100.vv8809901112 2018
Christian Szegedy. Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations (ICLR), 2014.
Christian Szegedy, Wei Liu, Yangging Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Du- mitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1-9, 2015.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27 (7(1 1984.
Vladimir N Vapnik. An overview of statistical learning theory. IEEE transactions on neural net- works, 10(5):988-995 -998899999990 1999.
Vladimir Vovk. Conditional validity of inductive conformal predictors. Machine learning, 92(2-3): 349-376, 2013.
Wenbo Wang and Xingye Qiao. Learning confidence sets using support vector machines. In Ad- vances in Neural Information Processing Systems, pp. 4929-4938. 2018.
Yi Wu, Jongwoo Lim, and Ming- Yang. Online object tracking: benchmark. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2013.
Bianca Zadrozny and Charles Elkan. Obtaining calibrated probability estimates from decision trees and naive bayesian classifiers. In In Proceedings of the Eighteenth International Conference on Machine Learning. Citeseer, 2001.
12

---

Published as a conference paper at ICLR 2020
Bianca Zadrozny and Charles Elkan. Transforming classifier scores into accurate multiclass proba- bility estimates. In Proceedings of the eighth ACM SIGKDD international conference on Knowl- edge discovery and data mining, pp. 699. ACM, 2002.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In /CLR, 2017.
13

---

Published as a conference paper at ICLR 2020
A DISCUSSION OF ALGORITHM DESIGN CHOICES
A.1 USEFULNESS OF TEMPERATURE SCALING
In this section, discuss why temperature scaling 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 single input x x-i.e. the ordering of the probabilities ply x) for y y is changed by temperature scaling, Indeed, the order of confidences for labels for different inputs can change. For a concrete example, consider two inputs and x', and the case = (0, Assume that the label probabilities are
1( = [1/3 1/3 1/3]
S( 1(11=)) (3/4 1/4 0]
Now, if we take temperature very large, then the labels become roughly
[1/3 1/3 1/3] f+ 22) 12)
1.12=) D/2 1/2 o]_
As consequence, there confidence that are achievable when using fo that not achievable when using f. In particular, the confidence sets
Cr(z) Ø Cr(x') = (0,
can be achieved using fr (e.g., with e- 2/5). However, it is impossible to achieve these confidence sets using for any choice of T, since if 1 Cr(x'), then it must be the that (r)) = {0, 1.2]. Intuitively, we expect calibrated prediction to improve the ordering of probabili- ties 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 use specialized generalization bound that directly provides PAC guar- antees on our confidence sets rather than simply applying the VC dimension bound. The casiest way determine which bound better is to examine which one produces smaller confidence set. In our approach, the size of the confidence set decreases monotonically with the choice of a a(n, e, 5) in 3). Thus, the bound that produces larger a is better. Recall that the VC dimension bound produces
log(2n)
log (5/4)
ave(n, e, 8) = -
n
whereas our direct bound produces (for l = 0)
(direcan,, e, 6) = max k/n subj. to Σ 1=0
11 {(r)
-1 <8.
KER
Directly comparing these two choices of a 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 needs to be to achieve a(n, e, = For ovc, it is easy to check that we need
log(2n) + log(4/6)
22
Thus, we need n to be at least O(log(L/8)/e) (and possibly greater, to account for the log(2n) term). In contrast, for direct bound, = 0 corresponds to the case A O. To achieve k = 0, suffices to have n satisfying (1 - cc"" 5. Using (1 c) " S e-me, suffices to have n satisfying
log(1/8)
14

---

Published as a conference paper at ICLR 2020
200055
VC direct
000
k
k
4002
k
k
25005
4003
5000
2008
0.52
5.22
3009
00.00
0.815
0.81
6.15
3.00
8.42
0,09
3.00
0.5%
0.00
6.00
0645
3058
Figure 4: Sample complexity of different bounds; fix 8 = 10-5. Left: Sample complexity of VC bound and direct bound when = 0. Right: Sample complexity of direct bound for varying
In other words, n only needs to be ((log(1/0)/e) For small e (c.g., E 0.01), we need 100x fewer samples to achieve the same size confidence set (i.e., with choice a, c, 5) 0). In Figure 4 (right), we compute the exact values n needed to get a(n, c, c. = 0 as a function of c for each bound requires substantially smaller
bound (fixing 10-5). As expected,
Finally, in Figure 4 (right), we compare the magnitude of n needed to achieve larger values of a using direct bound; for simplicity, actually consider larger values of (where a 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 [ both of which are standard. First, we assume that 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 Φ 2 + R. where Z X x V, be defined by (((x,)) y)) log x). assume that the distribution D induced by á on has continuous cumulative distribution function (CDF). More precisely, letting μu be the measure defining D, then D is defined by the measure (t) = (n
that (-1(((=)) for all Z. Then, we assume that the CDF corresponding to is continuous. This second assumption is standard in statistical learning theory (Kearns & Vazirani 1994). Essentially, it says that for any R. the probability that f - log [ x) must equal zero. This assumption should hold unless p(z, y) or fly x) are degenerate 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 x). Thus, choosing f log fy x) would include all these points, so the realized error rate is larger than desired for 7' In this case, can simply choose slightly larger T' to avoid this problem.
where Φ-1 IR 22 the inverse of in the
B.2 PROOF OF THEOREM 1
At a high level, our proof proceeds in three steps. First, we show that a confidence set predictor Cr can be encoded as binary classifier Mr. Second, show that PAC bound for Mr implies PAC bound for Cr (where in both cases, the unknown parameter is T E R). Third, we prove PAC bounds on the error of My; by the second step, these bounds complete our proof.
Encoding Cr as binary classifier My. We begin by showing how the problem of learning a PAC confidence set predictor Or reduces to the problem of learning PAC binary classifier Mr. First, we show that for any 7 E RR the confidence set predictor Cr can be encoded as binary classifier MT. Consider any parameter E = confidence set predictor
R. Recall that we use the model f(y x) to construct the
Cr {u f(y | x) TT).
15

---

Published as a conference paper at ICLR 2020
Now, define the map ø 2 R by d(r,y) log f(y x) where 2 = X' x V, and define the binary classifier Mr : + {0,1} by
Mr(t) = 1lt - T..
Here, [s}] is the indicator function, which returns one a statement 8 is true and zero otherwise. We claim that
Cr(2) = tu Mr(((z,))) 1}.
(12)
To see this claim, note that
Cr(x)
(y E (VE))I((()))(+)
{y E /1) ST}
( ST)
{y E/ []((z,)) =1]
(1 E y Mr(0(2,9)) = =1}
as claimed.
PAC bound for My implies PAC bound for Cr. Next, we show that PAC bound for Mr implies PAC bound for Cr. More precisely, we design a data distribution D and loss é, and show that (i) the distribution T' (trained to optimize Mr) is the same as the distribution of T' (constructed using algorithm), and (ii) PAC bound for Mr (where T is trained data from D) implies PAC bound for Cj. We show that as a consequence, PAC bound on Mi implies PAC bound on C.--
We begin by constructing D and É. To this end, recall that D is a given distribution over X' x V. We define data distribution D over X' x V, where X = IR and 5 {0, 1}. as follows. The first component of Í) is the distribution over X' 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 f (i.e., categorical or Gaussian), this property is satisfied. Then,
(D((L,a) =D( I[a 1],
where PD is the measure encoding D, and μu is the measure encoding D. Furthermore, we define e: y' x {0, 1] be the 0-1 loss ala,a') I[a # a'). Finally, let T be chosen using our algorithm-ies i..,
i arg min T subj. to I(Cr; Z) Sa
[(C;; 7) = Z
Σ
Thy & Cr(x)).
(æ.))Z
for any a E Rgo. and let 7 he chosen similarly for My-iie.
i arg min T subj. to L(Mr; 2) S
L(MT; 2)
1
Σ ((MT(t), a) (t.a)E2
Σ I[Mr(t) # a].
(L,))
Now, show (i) above. In particular, we claim that T(Z) has the same distribution T T(2), where Z D and 7 ~ Dr are random datasets. To this end, define & nn + 2n by
(((2),-.;,n)))) 2n)) ((1(21),
())
Note that
1
i(M;; 2(Z))
[Mr(((()) + #1]
| 2)
"
Σ
My Cr(x))
77
L(Cr;; Z):
16

---

Published as a conference paper at ICLR 2020
from which it follows that
T(Z) arg min T subj. to 2) aa arg min T subj. [(Mr; (Z)) S
By construction of Φ the random variables Z and Φ Z) have the same distribution; thus, it follows that the random variables T(Z) and (Z)( have the same distribution well. Since T() (Z), it follows that FZ) has the same distribution as T()), as claimed.
Next, we show (ii) above. In particular, we claim that PAC bound for M
P (M(2)(2) < 2 1-
implies PAC bound for C222) -ie.
PVNDn ( sd
where the true losses are
I(Mr) = E L(CT) = (B [l & Cx = I (2.g)~ $ Cr(x)]
(t), = ((.a)) (Mr(t) +
Note that it suffices to show that the true loss for Or equals the true loss for My-icc
I(Cr) = L(My),
since this equation (logether with the PAC bound for (2) implies
Pn-Dn ((CT()) = Pz- (( 2el2-0
as desired. To see the claim, note that
((MT) = P P(..a--(MT (MT(1) + a]
= 1[Mr(1) # a)dpp((((a))
Σ Ila = 1] [[Mr(t)) + aldup(o=' (())
o=0
/ (tMr(t) # 1)duD(o (t))
Now, using the change of variables t + d(z), we have
i(Mr)= = / ([M(((==) # (]dun(=)
/ (Mr(C(5, v)) 1] D(x, drddy
Then, using 12 we have
i(Mr) / [Tl & Cr()))
= P(aN) & Cr(x) I(Cr),
as claimed.
Finally, combining (i) and (ii), we have
P2~D=IL(C = ==P2d=(([(Cr))) s
17

---

Published as a conference paper at ICLR 2020
where the first equality follows since (i) says that TZ) (where Z D has the same distribution T(2) (where Z ~ D)), and the second inequality follows by (ii).
Generalization bound. Finally, we prove the PAC bound
P2- (L(M)) s 1-21-10 50.
(13)
for Mr. where 60 = E (1) e)" for conciseness, we have dropped the dependence of Ie on Z. By the previous step, this bound implies the theorem statement. To this end, first simplify the left-hand side of the inequality (33). In particular, let I"r be the smallest T for which L(Mr-) = e; such a 7 exists by our assumption that D has continuous density function.
First, we claim that T < T implies L(MT) L(Mr-). Assuming T < T", then
i(Mr)
P(t.aa [T # a]
B((,aa [MM((1) (((r(() # a]
b((a))-)4((MM((() # 1]]
Bl(aaD [4[[[t - 7] + II]
EleayDD [I[t > T]]
BleaayD [T] > T*]
i(Mr-))
Assuming 7 T can similarly show that I(M²) i(Mr-)) ). It follows that
PMNDa [(MM)) { = =P
[L(M)) > L(Mr.))
T [<T
= =P2DDa
As a consequence,
13 is equivalent to
P2DDa
T < T S 80.
Next, recall that 7 must satisfy L(M;;
p; 2) S a, where
1 L(M;; n (1,a)E2
Σ (t) a).
Assuming f < T and using hs follows that
k M Σ ( = Σ
[[M #1)
(r.a)²
(t.a)EZ
Σ T[ 7)
(taje2
2 Σ
T| T*
(taje2
As consequence, we have
P Pr-D
[ <P<T0]
S SPa-
Σ
TT k
(t,a)E
P Pr
Σ
T<>T
1=0
(t,a)eZaa
18

---

Published as a conference paper at ICLR 2020
By definition of T", the event in the final expression says that the sum of ii.. Bernoulli random variables Il > T ~ Bernoulli(e) is at most k. Thus, this event follows a distribution Binomial(n, c), so
k
* Σ 1=0
(z)
Pz-D=
T < T -
Binomial (1 n, =
e -c)= 60.
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 neural network with a softmax output. Then, we can compute given confidence set
Cx (v E D fly x) 2 )
by explicitly enumerating y E V. We measure the size of Cr(x) (Cr(
Regression. For the case y = R, we choose the probability forecaster to be a neural network that outputs the parameters (H, 0) E y' R>o of Gaussian distribution. Then, we have
Cr(z)= μ - ov / 2(T log(oo/2))) a 2(T
//2 log(o (2V2/TT)
This choice generalizes to y = Rd by having f output the parameters (1, Σ) E y x S (where 8 is the set of d dimensional symmetric positive definite matrices) of d dimensional Gaussian distribution. Note that Cr (x) is an ellipsoid Cr = + A5 where A Rdxd and 5 is the unit sphere in R. in particular, A D Q. where QDQT is the eigendecomposition of (2T In 2nr In del Σ)-1 -
We measure the size of (r as ||||, where || is the Frobenius norm.
Model-based reinforcement learning. In model-based reinforcement learning, the goal to predict trajectories based on model of the dynamics. We consider an MDP with states X' C Rdx actions C Rg an unknown distribution over initial states zig ~ dg. and unknown dynamics g (a' x, u) mapping state-action pair (z, u) E X' x 2 to distribution over states x' E X. We assume fixed, known policy π x), mapping a state x E X' to a distribution over actions u U. The (unknown) closed-loop dynamics f=' x))
Ex(u))] [g" (x' Ir, u)].
Given initial state Zo E X' and time horizon H E N, we can sample a trajectory o (af...., xHH) f* by setting z Zo and sequentially sampling if+1 f(( 23) for E {0, 1,.., H-13. Our goal is predict a confidence set Cr(xo) S X that contains si.H E H with high probability (according to both the randomness in initial states zo ~ do and in f). This problem is multivariate regression problem with inputs and outputs y x
((z), E(x)) trained to predict the distribution over next i.t f(x' x) z ft z). Given initial state zo X and time horizon H E N, we construct the mean trajectory ZI:H by setting 2o = To and letting ēt+1 = p(æ,), To account for the fact that the variances accumulate over time, we sum them together obtain the predicted variances E1.4 ie..
We assume given probability forecaster f(ø' x)
Σ = E(To) + E(Tr) + +... I(Tx-1).
Then, we use the probability forecast f 1H E1.H) = N( EIS) (where we think 1 as a vector in I2 fr-xx and Σ1-H as block diagonal matrix in IR (x) (H--x)) to construct confidence sets.
Finally, we describe how we measure the size of a predicted confidence set Cr (2o) S H In particular, note that (zo) has the form
(x (2), Cr.
19

---

Published as a conference paper at ICLR 2020
E 0.01
0.0175
Cont. set error
Conf. set size
0.0150
600
0.0125
0.0100
0.0075
0.0050
200
0.0025
OLES
naive
(a)
(b)
0.01
Conf: set size (log-scale)
10a4
0.8
10a
10
Cont. Set
0.6
10t
10F
0.2
10
10
naive
naive
naive
ouTs
call)
(no
(c)
(d)
Figure 5: Comparison to baselines that do not have theoretical guarantees. (a) and (b), we show results for ImageNet, and in (c) and (d), we show results for the half-cheetah. In (a) and (c), show the empirical error in confidence set sizes; the dotted line denotes e 0.01, our target confidence set error. In (b) and (d), we show the sizes of the constructed confidence sets.
i... (r.a(Fo) is the confidence set for the state 2e reached after time steps. Then, we measure the size of the confidence set for each component Cr.e(Tu) (for t E {1...., H}) individually, and take the average. As the case of regression, (z,( is an ellipsoid Cr,e(ro) = Hg + A,5 -1, then, the size of Cr(zo) is H E ||A]]
additional detail that when we calibrate this forecaster, we calibrate each component (T,) individually-i.e, we use H calibration parameters T1: TH-
D ADDITIONAL RESULTS
D.1 COMPARISON TO ADDITIONAL BASELINES
We compare two baselines that do not have theoretical guarantees. We assume given probability forecaster f(y r). Then, given an input E X, we construct the confidence set to satisfy
Σ flula)216.
(14)
(EC(#)
More precisely, we first rank the labels in decreasing order of f x:), obtain a list (y1. 3/,..., }/ Then, we choose the smallest such that (14) holds for C(x) {y1.... Bk.. Intuitively, if the probabilities fly x)) are correct (i.e., fly x) is the true probability of y given r), then this confidence set should contain the true label y with high probability.
For regression, we cannot explicitly rank labels y E J C Rd but they are monotonically decreasing away from the mean. Then, assuming [ x) = Nis ((x), E(x)) is Gaussian, we take an ellipsoid of shape Exx)) around μ(x) with minimum radius that captures e of the probability mass of fly x). More precisely, choose
C(x) Ci(e) (z)
f(x) mignene T subj. to Fo Cr(x)) 2
20

---

Published as a conference paper at ICLR 2020
1000
Cont. Set size
600
Cont. set
600
200
200
Figure 6: Confidence set sizes for two neural network architectures trained on ImageNet; for both, we use n 20, 000, c 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 0.0061.
where Cr(z) = {y e fly 2) 2 e- as before. Note that unlike our algorithm, the threshold ((x) is not learned parameter, but computed independently for each new input x. We can solve for (1x) efficiently by changing basis to convert fly x)) to a standard Gaussian distribution, and then using the error function 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 fa(u x) without any calibration, and (ii) the calibrated forecaster fa.+ (y/ x:). We plot both the confidence set sizes and the empirical error rates. For the latter, recall that confidence 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 Zrest S X x V-iie.. I(C) N L(C; Zuea), where
predictor
(C; 7ress)
Σ
My & C(x)).
[Zeeal
Intuitively, ÍC; Zua) is the fraction of inputs (I, y) E Zus such that the predicted confidence set for x does not contain y. We say confidence set C is empirically valid when i.(C: 7 < Recall that our algorithm guarantees correctness with probability at least - 8, where
10-5,
As can be seen, the baseline approaches are not empirically valid in all cases. In one pase-namely the baseline with the calibrated forecaster on ImageNet-thhe 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 al. 2015 Our results 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. 47.83% 29.41% %, and 21. 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 (Gu- venir 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 Figure We choose larger values of and since we cannot obtain confidence sets that satisfy the PAC criterion with smaller and 8 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 E; thus, the constructed confidence sets empirically valid. For these datasets, the confidence set sizes our approach C + D and our approach without calibration D are similar, most likely due the small number of class labels.
21

---

Published as a conference paper at ICLR 2020
2,00
1.75
3.5
1.50
1.25
2.5
Cont. set
1.00
2.0
0.75
1.5
1.0
0.25
0.5
0.00
0.0
(a) Arrhythmia
(b) Car
2.00
suppressed alarm ratio (%)
0:25
Cont. Set 5128
1.50
1.25
0.20
1.00
0.15
0.75
0:10
0.50
0.25
0.05
C+D
Tase alarm
actionable alarm
(c) CHOP Alarm
(d) Suppressed alarms
Figure 7: Confidence set sizes for three additional classification benchmarks: (a) the arrhythmia detection dataset (Guvenir et al. 1997;; here, n1 = 90, confidence set error of our approach C + D is 0.0435, (b) the car evaluation dataset (Bohanec & Rajkovic 1988); here, n = 345, E = 0.05, 8 = 10-5, and the empirical confidence set error of our approach C D is 0.0172, and (c) the CHOP alarm dataset (Bonatide et al., (2017); here, n 1000, <= 0.02, 5 = 10-6, and the empirical confidence set error of our approach C+ F++Di is 0.0159. (d) The fractions of actionable and false alarms with a confidence set {0} (i.e., only contains false alarm).
0.1, = 0.05, and the empirical
We additionally our approach on medical dataset where classification decisions 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 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(; Zuai) 0.0159.
The key question 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 calibrated confidence set predictor f: X + 2 based on this forecaster. We consider an alarm to be false if the predicted confidence set is f(x) (..-i... 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 - e. In summary, we suppress an alarm f(x) = {0}. Using our approach, 176/ /630 (i.c., 27.94%) of false alarms suppressed, while only 13/ 187 (i.c., 6.95%) true alarms are suppressed (see Figure (d))
D.4 RESULTS ON ADDITIONAL REGRESSION DATASETS
We ran our algorithm on two small regression baselines-th the Auto MPG dataset QQiinann 1993) and the student grade dataset (Cortez Silva 2008). We show results in Figure 3 The parameters we use are e = 0.1 and = 0.05; as with the smaller classification datasets, we use larger choices of e and 5 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 f.(C:, Zua) = 0.0597, so these are empirically valid. For the student grade dataset, the error is (C: Zus)) 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.
22

---

Published as a conference paper at ICLR 2020
50
Conf. set size
40
Conf, set
30
20
C+D
C-D
Figure 8: Confidence set sizes for two benchmarks focused on regression; for both, we use 0.1 and ő = 0.05. Left: the Auto MPG dataset (Quinlan 1993); here, n = 70, and the empirical confidence set error of our approach + D 1250. Right: The student grade dataset (Cortez & Silva 2008); here, 100, and the empirical confidence set error of our approach is 0.0597.
D.5 ADDITIONAL RESULTS ON IMAGENET, HALE-CHEETAH, AND OBJECT TRACKING
Table show examples of ResNet confidence sizes for ImageNet images. Table shows results for varying c on ResNet. Tables 7 & g show results for varying c, on the Half- Cheetahhe Table shows visualizations of the confidence sets predicted for our object tracking benchmark.
23

---

Published as a conference paper at ICLR 2020
[C(x)
10
50 -
[C(x)
S 100
(C())
200
Bell
ditssip
SkodaRonmster
7ebra
banana
carouse!
starfish
8g
GIVE WAY
OFFICE
Street sign
ROAD
GOOD
McLELLAN AN
8900
Rackas
Economy
MOTEL
Table 4: 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.
24

---

Published as a conference paper at ICLR 2020
S (x) < 5
5 5 [C(x) < 10
10 S [C(x) < 20
banded gecko, commitin iguana, American chameleon, whiptall, agaata.. frilled licurd,
Chituniun, Iaalin greyhoumd, Roston hull, miniature pinscher)
king penguin
alligator lizard, licand. chameloon,
Komoodo dragon
alkar clock, bell cose, castle, church, cinema, munastery, palace, vaull; wall clock
springer, springer spaniel
Shopping Busket
collie, baser, Saint Beriian,, Leasberg
barber chair. hand blower, chest, piger rowel, planger, shower curtain, scup diapenser, roiler seat, washshssin, washer, tissue
powder,
chambered naunalas
hamper,
lotion, packet, shopping basket
beach wagon, cab, wheel. comeerible. guille. limousine, minivan, mabile home. paesenger pickap. recreational velucle, sports cannon, castle, cluff dweiling, megalish, momestrry; obellsk, prison, stone wall, triumphal vault, slp, cliff, proasontory. valley smphihian, cassette player, line engine, minibus, minivan, passenger pole, police van, puck, racer, radio, school screwchiver. strveticar,
kill. hald eagle, vulture. great grey owl. bittrn
Eiger cat, lyns, leopard, snow leopard, jaguar, figer, cheerah
Madagaicar cat.
indra
rush machine, deskrop computer, entertain, center, home thester, Toudlppakker,
ballpoinn, Fountain pen
sureen, television
tolleyyius
juncu,
water stake, drake, red-hreasted mergatterr
whiptail, agama, frilled lianl, alligatoc lixard, licand, dragton African crocodile, American alligator
cnay fish, lirtl blue
Thes impula, gooalle
European gallinule, rukly turnstone red-hhucked sandpiper, redshank, dowitcher, oysterentcher her, albatross,
accondion, nconetic guitar, banjo, bassoon, cornet, drametick, elactric guitar, French horn, microphone,, oboe, Sux, stage; torch. mromoose,
barber cliair, barbershop. electric san, hand blower, iron. rocking chair, table lamp, tneycte,
indigo bunting, bee coter. hummingbard. jicammar
Table 5: Confidence sets of ImageNet images with varying ResNet contidence set sizes. The pre- dicted confidence set is shown to the right of the corresponding input image. The true label is shown red, and the predicted label shown with a hat.
25

---

Published as a conference paper at ICLR 2020
8 10-1
10-3
10-5
1000
1000
1000
800
800
800
Cont. set
Cont set
0.05
600
800
set
800
400
400
400
200
200
200
1000
800
Cont. set size
Cont. set size
0.04
Conf.
200
6
C-D
D
C40
CLD
1000
1.000
1000
800
800
800
Cont: set size
Cont. set size
0.03
600
800
Cont. set
800
=
400
400
400
200
200
200
Cont. set
Cont. set sibe
0.02
Conf..
200
200
C-D
C+D
0
C+D
1000
1.000
1000
800
800
800
Cont: set S28
Cont. Set size
0.01
600
800
set
600
400
4:00
400
200
200
Table 6: Confidence set sizes for ResNet trained on ImageNet, for varying c, and for n = 20, 000.
The plots are Figure (a).
26

---

Published as a conference paper at ICLR 2020
6 = 10
= 10
10
Conf. set size (log (lggscall))
10M4
1024
1034
1031
10st
10
10a0
10za
flag
1010
0.05
10ar
10a3
10
1om
Cont. Set sete
107
1017
10
109
Conf.
C-0
A+D
A-C+D
C-0
A+D
A+C+D
C+0
A+D
A+C-D
Conf. set size (log scale)
1034
Cont: set 520 (o0-scale)
1024
1024
10z1
1021
10
1014
(lg
= 0.04
10
Conf.
18a
10
10a
18a
10"
C-D
A-D
A-C+D
C.0
AID
A-C1D
C4D
A+D
A+C-D
Cont. set size (log scale]
1034
Cont. set size (og-scale))
1014
Conf. set (log
0.03
10
10
10
102t
10:2
1042
10a
109
10*
104
100
10a
10
100
10a
109
A-D
A+C+D
Cont. set size (log scalel
1.04
Cont. dog-scale!
1024
104
1691
1041
1641
1.04
1034
(lg
10
0.02
10t
10
10
10a2
1022
1012
10p
10a
109
104
10a.
104
Conf.
10a
10a
203
10a
100
Conf. set size [lagsccale]
1034
Cont. set site soseelle
1024
1044
1ea1
1024
1641
1om
1073
Conf. sire (lag
10
0.01
10a5
1035
1015
10zt
1032
1014
10a
109
C-D
A-D
A+C+D
C-D
A+D
ArC1D
C+D
A+D
ArC+D
Table 7: Confidence set sizes for neural network dynamics model trained the half-cheetah environment, for varying d and for n 5000. The plots are as in Figure 3
(a).
27

---

Published as a conference paper at ICLR 2020
5 10
=10
-1033
-006
10
10a
102t
Conf. set size (l0g scale)
10
C+D
Cont. set size (log-scale)
10T
C+D
Cont size (log scale)
1074
C+D
20
(ours)
0.05
10
1.
1074
10.2
101
1012
196
10f
104
1.6
100
307
10
Time
Time step
Time step
10
10ah
102F
Cont. set size (log scale)
10
C+D
Cont: sete (log-scale)
100
C+D
Canf: set size Jlg scale)
1014
C+D
A+D
A+D
A+D
A+C+D (ours)
A+C+D (ours)
A+C+D (aurs)
0.04
2014
104s
1014
10
101
1017
10a
1.9
139
109
30a
10
Time step
Time
10
Cant. Set size (log scale)
10M
C+D
Conf. set (log-scale)
1pm
C+D
Conf.. set size (log scale)
2024
C+D
A+D
A+D
A+D
30
A+C+D (ours)
10
A+C+D (ours)
10
A+C+D (ours)
0.03
20
2013
10k
40a2
1.6
109
30*
136
105
307
step
step
step
20.4
Cont. set size flog scale)
Cont. Set size (log-scale)
Conf. (lag scale)
30M4
C+D
182
C+D
1014
C+D
A+D
A+D
A+D
10
A+C+ D (ours)
1,19
A+CC C+D (ours)
10P
A+C+D (ours)
0.02
2014
1ou
2012
1.2
10a
30*
30r
30
Time step
Time step
Time Ttmp
10/4
109
Conf. set size (log (log-scale)
1014
Cont. size (log-scale)
(log-scale)
C+D
A+D
A+D
A+D
10/e
A+C+ D (ours)
1.79
A+ C (ours)
300
At C+D (ours)
0.01
2014
1p1s
2019
3.7
10r
10
15
10
20
Time step
Time step
Time step
Table 8: Confidence set sizes for a neural network dynamics model trained on the half-cheetah environment, for varying 5 and for 5000. The plots are as in Figure 3 (b).
28

---

Published as a conference paper at ICLR 2020
Table 9: Visualization of confidence sets for the tracking dataset (w 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 with box. Our bounding box contains the ground truth bounding box with high probability.
29


Reviews:
[{"review_id": "rkgiuG8pYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an algorithm combining calibrated prediction and generalization to construct confidence sets for deep neural networks with PAC guarantees. \nThe main novelty is that existing approaches do not come with PAC guarantees\nFollowing (Platt et al., 1999) and (Guo et al., 2017), the calibration of the learned model is controlled by its temperature. In particular, the proposed approach exploits another (small) training dataset to learn a temperature that gives the best calibration. \nAn efficient algorithm for constructing confidence sets that are \"small in size\" is also proposed. \nThe framework is introduced for the classification, regression and reinforcement learning tasks.\n\nI vote for acceptance for the following reasons:\n- The paper is well-written, the motivation and comparison to related work is also clear.\n- The paper is very solid theoretically and experimentally. A theoretical analysis is provided, and practical implementations are proposed to deal with scalability issues. VC generalization bounds are studied in detail.\n\nConcerning experiments that are not about Reinforcement learning, the paper proposes different strategies to learn a ResNet architecture for ImageNet. One might argue that the different results might be only valid for the chosen architecture and dataset. \nAlthough the study for that architecture and (large scale) dataset is exhaustive, it might be interesting to study if the reported results are also valid on (smaller?) datasets and other architectures.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "r1lOV7t2KS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper presents an approach for generating confidence set predictions from deep networks. That is, the smallest set of predictions where the true answer is included in that set. Theory is used to derive an algorithm with PAC-style bounds on the population risk. \n\n\nOverall Assessment: I like the core idea of this paper---developing region-based prediction algorithms with theoretical backing by taking advantage of a small calibration dataset and simple models of uncertainty. However, there are significant clarity and evaluation issues that must be addressed before the paper is ready for publication.  In current form, I rate the paper between Weak reject and strong reject overall. \n\nStrengths: \n+ Nice general direction.\n+ New algorithm for confidence set prediction with theoretical guarantees. \n+ Experiments show favourable performance vs a few ablations.\n\nWeaknesses & Questions:  \n1. It is unclear to me why the temperature scaling component is needed. It does not actually change the ordering of the probabilities assigned to each class, so from what I can tell all it does is change the optimal T, but not the final performance.\n2. The paper presents a bound on the population risk, but the experiments do not include a comparison of the expected worst-case error rates with the empirical error rates achieved on the test set. This should be corroborated. \n3. The  description for the Model-based reinforcement learning subsection is impossible to follow due to ambiguity and lack of detail overall.\n3.1. Some specific confusions about this section: Paper overloads f to be both a deterministic transition function, and also a distribution over possible states. It also switches between using x_{t+1} / x_t and x^\\prime / x to mean the same thing. The notation used to describe the multi-step setting also seems to use \"t\" for two different things: the current time-step, and some arbitrary time-step in the past.\n3.2. It is unclear what metric is being used to evaluate the state transition models---L2 distance between what? Given that the predictions are not point estimates, I would expect something that takes uncertainties into account.\n5. For both sets of experiments (classification and RL), there are no alternative methods used as points of reference. There are a multitude of other approaches incorporating uncertainty into predictions, as mentioned in Section 1. A trivial baseline is to heuristically generates confidence sets by trusting the probabilities produced by the model and building a set out of the classes corresponding the top 1-\\epsilon probability mass should be essential. This could be improved by applying difference calibration approaches to make the probabilities more trustworthy. Model ensembles provide another easy baseline. Such simple baselines are a minimum expectation, before even getting to state of the art alternatives.\n6. There seem to be no vanilla regression experiment, only the harder-to-interpret RL experiment. EG: Since we already have a vision context: If you are doing facial age estimation , or interest point tracking, could one make a PAC prediction about the true age region/interest point location?\n7. Overall the paper introduction misses some explanation on the motivating scenarios where such confidence set predictions are useful. One can perhaps imagine this for vision, but some help connecting the dots to how it could be useful in regression and RL would help. \n8. It is claimed that Theorem 1 provides a \"better\" bound than the one based on the VC dimension. What is meant by better?\n\nMinor comments:\n* There are a couple of small mistakes in the proof of theorem 1. The \\tilde{X} and \\tilde{Y} in the definition of \\tilde{Z}_{val} are in the wrong place. The \"sum of k i.i.d. random variables\" should be \"sum of n i.i.d. random variables\".\n* In general, the proof is quite hard to follow. At times it was quite unclear how you get from one step to the next, because it relies on something shown several steps early, which is not referenced.\n* Notation, in general, is a bit of an issue in this paper. See comments above, but also: switching between \\theta and T for the parameter used in the confidence set predictor, some confusion between T and \\hat{T}.\n* It is unclear how the neural network used in model-based RL predicts a PSD covariance matrix.\n* \\hat{T} is not defined when it is first referenced (Section 3.3).\n* Algorithm 1 appears several pages before it is referenced.\n\n-------------- POST REBUTTAL ------------\nI modify my score to 6: Weak accept.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJgsF1xecr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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}.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper describes a method for bounding the confidence around predictions made by deep networks. Reviewers agree that this result is of technical interest to the community, and with the added reorganization and revisions described by the authors, they and the AC agree the paper should be accepted. 
Decision: Accept (Poster)