PAC Confidence Predictions for Deep Neural Network Classifiers
Authors: Sangdon Park
Shuo Li
Insup Lee
Osbert Bastani
Venue: ICLR 2021 Poster (2021)
Keywords: classification
calibration
probably approximated correct guarantee
fast DNN inference
safe planning

Abstract: A key challenge for deploying deep neural networks (DNNs) in safety critical settings is the need to provide rigorous ways to quantify their uncertainty. In this paper, we propose a novel algorithm for constructing predicted classification confidences for DNNs that comes with provable correctness guarantees. Our approach uses Clopper-Pearson confidence intervals for the Binomial distribution in conjunction with the histogram binning approach to calibrated prediction. In addition, we demonstrate how our predicted confidences can be used to enable downstream guarantees in two settings: (i) fast DNN inference, where we demonstrate how to compose a fast but inaccurate DNN with an accurate but slow DNN in a rigorous way to improve performance without sacrificing accuracy, and (ii) safe planning, where we guarantee safety when using a DNN to predict whether a given action is safe based on visual observations. In our experiments, we demonstrate that our approach can be used to provide guarantees for state-of-the-art DNNs.

Published as a conference paper at ICLR 2021
PAC CONFIDENCE PREDICTIONS FOR DEEP NEURAL NETWORK CLASSIFIERS
Sangdon Park, Shuo Li, Insup Lee & Osbert Bastani
PRECISE Center
University of Pennsylvania
(sangdonp, lishuol, lee, obastani @seas upenn.
ABSTRACT
A key challenge for deploying deep neural networks (DNNs) in safety critical settings is the need to provide rigorous ways to quantify their uncertainty. In this paper, we propose a novel algorithm for constructing predicted classification confidences for DNNs that comes with provable correctness guarantees, Our ap- proach uses Clopper- Pearssn confidence intervals for the Binomial distribution conjunction with the histogram binning approach to calibrated prediction. In addi- tion, we demonstrate how our predicted confidences can be used to enable down- stream guarantees in two settings: (i) fast DNN inference, where demonstrate how to compose a fast but inaccurate DNN with an accurate but slow DNN in a rigorous way improve performance without sacrificing accuracy, and (ii) safe planning, where we guarantee safety when using a DNN to predict whether given action is safe based on visual observations. In our experiments, demonstrate that our approach can be used to provide guarantees for state-of-the-art DNNs.
INTRODUCTION
Due to the recent success of machine learning, there has been increasing interest in using predic- tive models such as deep neural networks (DNNs) in criitclciitical settings, such as robotics (e.g., obstacle detection (Ren al. 2015) and forecasting (Kitani et al., 2012)) and healthcare (e.g.. diag- nosis (Gulshan et al. 2016 Esteva et al. 2017) and patient care management (Liao et al. 2020
One of the key challenges is the need to provide guarantees on the safety or performance of DNNs used in these settings. The potential for failure is inevitable when using DNNs, since they will in- evitably make some mistakes in their predictions. Instead, our goal is to design tools for quantifying the uncertainty of these models; then, the overall system can estimate and account for the risk inher- ent in using the predictions made by these models. For instance, a medical decision decision-making making system doctor when its prediction is uncertain whether its diagnosis is correct, or
may want to fall back a robot may want to stop moving and ask a human for help if it is uncertain to act safely. Uncertainty e.g., for doctor decide whether trust.
estimates can also be useful for human decision-makes their intuition over the predicted diagnosis.
While many DNNs provide confidences in their predictions, especially in the classification setting, these are often overconfident. This phenomenon is most likely because DNNs are designed to overfit the training data (e.g., to avoid local minima (Satran & Shamir 2018)). which results in the predicted probabilities on the training data being very close to one for the correct prediction. Recent work has demonstrated how calibrate the confidences to significantly reduce overconfidence (Guo al., 2017). Intuitively, these techniques rescale the confidences on held-out calibration set. Because they are only fitting a small number of parameters, they do not overfit the data as was the case in the original DNN training. However, these techniques do not provide thcoretical guarantees on their correctness, which can be necessary in safcty-critical settings to guarantee correctness.
We propose a novel algorithm for calibrated prediction in the classification setting that provides theoretical guarantees on the predicted confidences. We focus on on-distribution guarantees- i.e., where the test distribution is the same the training distribution. In this setting, can build on ideas from statistical learning theory to provide probably approximately correctness (PAC) guar- antees (Valiant 1984). Our approach is based calibrated prediction technique called histogram

---

Published as a conference paper at ICLR 2021
binning Zadrozny & Elkan 2001), which rescales the confidences by binning them and then rescal- ing each bin independently. We use Clopper-Pearne Pearson bounds on the tails of the binomial distribution to obtain PAC upper/llwer bounds on the predicted confidences.
Next, we study how it enables theoretical guarantees in two applications. First, we consider the problem of speeding up DNN inference by composing a fast but inaccurate model with slow but accurate model-i.e. by using the accurate model for inference only if the confidence of the inaccu- rate one underconfident (Téerapittayanon et al. 2016). We use our algorithm to obtain guarantees on accuracy of the composed model. Second, for safe planning, we consider using a DNN to predict whether or not a given action (e.g. move forward) is safe (e.g., do not run into obstacles) given an observation (e.g., a camera image). The robot only continues to act if the predicted confidence is above some threshold. We use our algorithm to ensure safety with high probability. Finally, we evaluate the efficacy of our approach in the context of these applications.
Related work. Calibrated prediction (Murphy 1972 DeGroot Fienberg 1983 Platt 1999) has recently gained attention a way to improve DNN confidences (Guo et al. 2017). Histogram binning non-parametric approach that sorts the data into finitely many bins and rescales the confidences per bin (Zadrozny & Elkan 2001] 2002 Naeini et al. 2013). However, traditional ap- proaches do not provide theoretical guarantees on the predicted confidences. There has been work on predicting confidence sets (i.e.. predict set of labels instead of single label) with theoreti- cal guarantees (Park et al., 2020a). but this approach does not provide the confidence of the most likely prediction, as is often desired. There has also been work providing guarantees the overall calibration error (Kumar et al. 2019), but this approach does not provide per-prediction guarantees.
There has been work speeding up DNN inference (Hinton al., 2015). One approach is to allow intermediate layers to be dynamically skipped (Teerapittayanon et al. 2016 Figurnov et al., 2017] Wang et al. 2018). which can be thought of as composing multiple models that share a backbone. Unlike our approach, they do not provide guarantees on the accuracy of the composed model.
There has also been work on safe Searningbbased control (Akametalu et al. 2014 Fisac al. 2019 Bastani, 2019 L & Bastani 2020 Wabersich & Zeilinger 2018]] Alshickh et al. 2018); however, these approaches are not applicable to perception- braeed control. The most closely related work is Dean et al. (2019), which handles perception, but they are restricted to known linear dynamics.
2 PAC CONFIDENCE PREDICTION
In this section, we begin by formalizing the PAC confidence coverage prediction problem; then, we describe our algorithm for solving this problem based on histogram binning.
Calibrated prediction. Let x E X be an example and y y be one of finite label set, and let D be distribution over X' x y: A confidence predictor is a model f : X - Py, where Py is the space of probability distributions over labels. In particular, f(z) is the predicted confidence that the true label for is y. We let ÿ : X' + y be the corresponding label predictor-iee. i(x) = arg max.ey f(x), and let X' + R20 be corresponding top-label confidence predictor- i.e., p(z) m f(x)g- While traditional DNN classifiers are confidence predictors, naively trained DNN is not reliable-i.e predicted confidence does not match to the true confidence; recent work has studied heuristies for improving reliability (Guo et al., (017]) In contrast, our goal is to construct a confidence predictor that comes with theoretical guarantees.
We first introduce the definition of calibration (DeGroot & Fienberg 1983 Zadrozny & Elkan 2002 Park et al., 2020b)-i.e what we mean for predicted confidence to be "correct". In many cases, the main quantity of interest is the confidence of the top prediction. Thus, we focus on ensuring that the tabllabel predicted confidence p(x) is calibrated (Guo et al. (201)): our approach can easily be extended to providing guarantees on all confidences predicted using f. Then, we say a confidence predictor f is well-calibrated with respect to distribution D if
P (a [y = ((x) p(z) = t] =
(vt E [0,
That is, among all examples x such that the label prediction (x) has predicted confidence t = -(xx), ((r) is the correct label for exactly / fraction of these examples. Using change of variables (Park)
2

---

Published as a conference paper at ICLR 2021
al. 2020b). f being well-calibrated is equivalent to p(x) =x((x) P (=',///~>> 'o' ((x') ((2') p(x)]
(Va X)).
(1)
Then, the goal of well-calibration is to make P equal to ej. Note that f appears on both sides of the equation p(x) = c) in p-which is what makes it challenging to satisfy. Indeed, in general, it is unlikely that (I) holds exactly for all Instead, based on the idea of histogram binning (Zadrozny & Elkan 200T), we consider a variant where we partition the data into fixed number of bins and then construct confidence coverages separately for each bin. In particular, consider K bins Bi...., BK S [0, 1], where B1 = [0, by] and B = (bk-1, 1, by] for k > 1. Here, K and 0 < bj S ..... < bx-1 & by = 1 are hyperparameters. Given f. let n : X + {I...., K} to denote the index of the bin that contains p(x² i.e. p(x) BRy(s)-
Definition 1 We say ff well-calibrated for distribution D and bins BI...., if
(()) = c)(x) P( (2'' (
- 5(2') 0(z') E Bxy(s))
(Vx X),
(2)
where we refer to (z(x) as the true confidence. Intuitively, this definition "coarsens" the calibration problem across the bins i.e. rather than sorting the inputs x into continuum of "bins" p(x) = t
for each E [o. 1] as in ( we sort them into a finite number of bins f(x)) E Bx: intuitively, we
have of Cf if the bin sizes are close to zero. It may not be obvious what downstream guarantees
can be obtained based on this definition; we provide examples Sections 3
Problem formulation. We formalize the problem of PAC calibration. We focus on the setting where the training and test distributions are identical-e.g. we cannot handle adversarial examples or changes in covariate distribution (e.g., common in reinforcement learning). Importantly, while we assume a pre-trained confidence predictor f is given, we make no assumptions about f-e.g., it can be uncalibrated heuristically calibrated. If f performs poorly, then the predicted confidences will be close to 1/D express confidence in the predictions. Thus, it fine if f is poorly calibrated; the important property that the confidence predictor f have similar true confidences.
The challenge in formalizing PAC calibration is that quantifying over all x in 2 One approach is to provide guarantees in expectation over x (Kumar et al., 2019); however, this approach does not provide guarantees for individual predictions.
Instead, our goal is to find a set of predicted confidences that includes the true confidence with high probability. Of course, could simply predict the interval [0, 1], which always contains the true confidence; thus, simultancously want to make the size of the interval small. To this end, we consider a confidence coverage predictor Ô X > 23, where c²(x) E C(x) with high probability.
In particular, Õ(z) outputs an interval Jc, a C IR, where & S 7, instead of set. We only consider a single interval (rather than disjoint intervals) since one suffices to localize the true confidence cj.
We are interested in providing theoretical guarantees for an algorithm used to construct confidence coverage predictor Ö given held-out calibration set Z C X x y In addition, we assume the algorithm is given pretrained confidence predictor f. Thus, consider Ć as depending Z and f. which we denote by Ö(: (.z. Z). Then, we want Ö to satisfy the following guarantee:
Definition Given E Ryo and n E N, Ô is probably approximately correct (PAC) if for any D,
P2-D=
A c((x) E Óz; Z) LEE
2 21-
(3)
Note that oj depends on D. Here, "approximately correct" technically refers to the mean of Č(z; f, 2), which is an estimate of cy(x); the interval captures the bound e on the error of this es- timate; see Appendix A for details. Furthermore, the conjunction over all x E X may seem strong. We can obtain such guarantee due to our binning strategy: the property cy(x) E Ö( f. 2) only depends the bin (x)(())+ the conjunction is really only over bins k {1....K} K).
3

---

Published as a conference paper at ICLR 2021
Algorithm. We propose confidence coverage predictor that satisfies the PAC property. The prob- lem of estimating the confidence interval (xx of the binned true confidence cz(x) is closely related to the binomial proportion confidence interval estimation; consider Bernoulli random variable b ~ B == Bernoulli()) for any E [0, 1], where b = 1 denotes a success and = 0 denotes a failure, and 0 is unknown. Given sequence of observations bi.. (b1,...,0u b,) ~ B", the goal is to construct an interval (b1..) C R that includes with high probability iee,
P B 0 @bb)m)) 1 a,
(4)
where a E -gso is given confidence level. In particular, the Clopper-Peanee Pearson interval
@cr(binia) = inf 0
Pe S
a sup {0 Pa
1s 1 9) 2 ]]
2
guarantees 4 CClppper & Pearson 1934 Brown et al., 2001). where s = =E b, is the number of observed successes, n is the number observations, and a Binomial random variable S ~ Binomial (n, 0). Intuitively, the interval is constructed such that the number of observed success falls in the region with high-pros probabprobbbblity for any 0 in the interval. The following expression is equivalent due to the relationship between the Binomial and Beta distributions (Hartley & Fitch 1951 Brown
et al. 2001 ie.. Po 2 s] = Io(s, n s + 1), where Ig is the CDF of Beta 8, n S 1):
2 quantile of Beta(s, - (1 21- quantile of Beta(s 1, 6)
écp(bimni ar)
Now, for each of the K bins, we apply θcp with confidence level
K -
8 K
C(x; 2,,) f, = Ôcp W
where Wx == (1((()) =) (x, v) E S.t.
(.s.,,y(x)) (x(()) k3
Here, Wi is the set of observations of successes failures corresponding to the subset of labeled examples (x, y) E Z such that p(x) falls in the bin Bg, where a success is defined to be a correct prediction (1x) y- We note that for efficiency, the confidence interval for each of the K bins can be precomputed. Our construction of Ć satisfies the following: see Appendix B for a proof:
Theorem Our confidence coverage predictor Ò is PAC for any 8 E R and n E N.
Note that Clopper-Pearson intervals are exact, ensuring the size of Ô for each bin is small in practice. Finally, an important special case is when there is a single bin B [0, 1] -ee...
f. = (w:(WW
where
W = (1((<x))) = 3/) (x',3') E Z'}.
Note that Co does not depend x, so we drop it-iee, So(fzz',1 @cr :8) -ee Co com- putes the Clopper-Pearson interval over Z', which is a subset of the original set 2.
3 APPLICATION TO FAST DNN INFERENCE
A key application predicted confidences is to perform model composition to improve the running time of DNNs without sacrificing accuracy. The idea is to fast but inaccurate model when it is confident in its prediction, and switch to an accurate but slow model otherwise (Bolukbasi et al.) 2017]; we refer to the combination as the composed model. To further improve performance, have the two models share a backbone-i.e, the fast model shares the first few layers of the slow model (Terrapitayanon et al. (016). We refer the decision of whether to skip the slow model as the exit condition; then, our goal is to construct confidence thresholds for exit conditions in way that provides theoretical guarantees on the overall accuracy.
can
Problem setup. The early-stopping approach for fast DNN inference can be formalized as a se- quence of branching classifiers organized in cascading way-i.e.
iee.
(x) if Am= (px(x) xx) (Bm 2 7m) (Am E {1, M - 1)) (z) otherwise,
(x; 71 =
4

---

Published as a conference paper at ICLR 2021
f((2)
ft
f
fo
I
(x
fa(a)
fa(x)
Figure 1: A composed model in a cascading way for M 4.
where M is the number of branches, fm the confidence predictor, and im and pm are the asso- ciated label and top-label confidence predictor, respectively. For conciseness, we denote the exit m-1 condition of the mth branch by d,m (i.e., (x) == 1 (A (ft(1:) < 74) A (fm(2)) 2 7m))) with
thresholds M...... 7/m E [0. 1]. The fm share backbone and are trained in the standard way; see Appendix F.44 for details. Figure [ illlustrates the composed model for M = 4; the gray area rep- resents the shared backbone. We refer an overall model composed in this way as cascading classifier.
Desired error bound. Given & R>o, our goal to choose 7::M-1 = (n..... 715-1) so the error difference of the cascading classifier Jc and the slow classifier ÿas is at most ( i.e.
(5) To obtain the desired error bound, an example x exits at the mth branch if fm likely to classify x correctly, allowing for most & fraction of errors total. Intuitively, if the confidence of ÿm on is sufficienlly high, then im (2) = with high probability. In this case, ÿM either correctly classifies or misclassifies the same example; if the example misclassified, it contributes decrease per: otherwise, we have (x) = (x)(x) with high probability, which contributes to maintain pem-
Per = P( (x.y)>> [+) * y] I2 (z.g)) [DM (z) + yl S.
Fast inference. To minimize running time, prefer allow higher error rates the lower branches-i.er we want to choose Y'm as small as possible at lower branches m.
Algorithm. Our algorithm takes prediction branches f. (for m E fl..... M)), the desired relative error Ş E 00, 1]. a confidence level 5 [0, 1). and a calibration set S X D, and outputs 71:M-1 so that (5) holds with probability at least 1 5. It iteratively chooses the thresholds from "n to 7M-11 at each step, it chooses Ym as small as possible subject to Per S E. Note that 7m implicitly
appears in Per in the constraint due to the dependence of (x:) on Ym- The challenge is enforcing the constraint since we cannot evaluate it. To this end,
6m = IP (a.N)~D [0m (x) * y (m(x)) + (M (x) A dnn (x)= =
é = IP (a.))D (ŪM(x)) # y (m((x) & (M)( (x(x)= =1]
then it is possible to show that Per Σ M-1 em - e'm (see proof of Theorem in Appendix C Then, we can compute bounds on and e'm using the following:
P [im (x:) = y im (x: * (M) A dm (x) 1] Ia Cm)] == Co (fm: 7m, 3(M 1)
6
P PDrr (x) = y (m F (M(( A dm (x) = 1| Ic cy = Co
(fM, Zm:
8
3(M 1)
8
PP (i)(x)) + (M(()) A dm dm))))
Lm = Ocp
Wmi
3(M - 1)
where
(z) A dmn (z) = = W. (1(0m (x) # UM (x) d. (x) 1) (x. y) E Z}. Thus, we have em 5 em and e'm 2 InI.n in which case it suffices to sequentially solve
Z,, = {xxx y) E Z 1m (x) + (x)
7m = arg min ? subj. to r
Σ -nn-dn-s
(6)
Here, Cm. P. Cm. and r., are implicitly a function of y. which we can optimize using line search. We have the following guarantee; Appendix for a proof:
5

---

Published as a conference paper at ICLR 2021
Theorem 2 We have Per I E with probability at least 1 over Z D
Moreover, the proposed greedy algorithm (6) is actually optimal in reducing inference speed when M = 2. Intuitively, we are always better off in terms of inference time by classifying more examples using a faster model. In particular, we have the following theorem: see Appendix Dfor a proof:
Theorem If M = 2, `í minimizes (6). and the classifiers Um are faster for smaller m, then the resulting &c is the fastest cascading classifier among cascading classifiers that satisfy Per S &.
4 APPLICATION TO SAFE PLANNING
Robots acting in open world environments must rely on deep learning for tasks such as object recognition-e;; detect objects in a camera image; providing guarantees on these predictions is critical for safe planning. Safety requires not just that the robot is safe while taking the action, but that can safely come to a stop afterwards- e.g., that a robot can safely come to a stop be- fore running into wall. We consider binary classification DNN trained to predict probability f(x)) [0, 1] of whether the robot is unsafe in this sense If f(x) 2 Y for some threshold E [0. 1], then the robot comes to a stop (e.g,, to ask a human for help). the label [f((x) 2 7) correctly predicts safety, then this policy ensures safety as long as the robot starts from safe state (Li & Bastani 2020). We apply our approach to choose y to ensure safety with high probability.
Problem setup. Given a performant but potentially unsafe policy á (e.g., DNN policy trained to navigate to the goal), our goal is to override î as needed to ensure safety. We assume that क is trained in simulator, and our goal is to ensure that A is safe according our model of the environment, which is already a challenging problem when स is deep neural network over perceptual inputs. In particular, we do not address the sim-to-real problem.
Let E be the states, Xate S X be the safe states (i.e., our goal is to ensure the robot stays in X,utee, O be the observations, dynamics, and X - O be the observation function. state x: is recoverable (denoted x E Nesc) the robot can use à in state x and then safely come to stop using backup policy To (e.g., braking).
21 be the actions, 9 X' U X' be the (deterministic)
Then, the shield policy uses ग if x E Xree and my otherwise [Bastani 2019). This policy guarantees safety as long as an initial state is recoverable-i.e,, æi Xr The challenge is determining whether E Xwe. When we observe H, we can use model-based simulation to perform this check. However, in many settings, we only have access observations e.g. camera images or LIDAR scans so this approach does not apply. Instead, we propose train a DNN to predict recoverability -ie.
1 1 -unreeoovrrale") f(o) 27
0(o) =
where
0= -=(x),
0 ("recoverable")
otherwise
with the goal that ((o) y (x) = 1(x & X resulting the following the shield policy Tahield
(()
if (o) 00
ग. (Thhieaa)) =
(T))) otherwise.
Safety guarantee. Our main goal is to choose so that Tshield ensures safety with high probability i.e., given R5 and any distribution D over initial states Xo Xree, we have
Punsafe = PP Pe-Droad [S & Xastel S E.
(Fo, (Fo. ......) is rollout from To D generated using π--.e. F++1 g( x (h((( ()) We assume the rollout terminates either once the robot reaches its goal, or once switches To and comes to stop; in particular, the robot never switches from Tn back to f.
where ((zo, T))
Success rate. To maximize the success rate (i.e., the rate at which the robot achieves its goal), we need minimize how often Whhield switches mo. which corresponds to maximizing 7-
I Since | = 2, can be represented as a map f + J0, 1]; the second component is simply 1 f(x). We can handle infinitely long rollouts, but in practice rollouts will be finite (but possibly arbitrarily long). and D Drase is an induced distribution over rollouts ((ro; T.tiela).

---

Published as a conference paper at ICLR 2021
ECE 7295
EC2 1.0%%
ECE 0.00%
[0 10.00%, 3.70%)
estimates
entimated
estimated
Hea rasl
Hoal rall
redo
canfdence
confilence
corfisence
(a) Naïve softmax
(b) Temperature scaling
(c) Proposed
Figure 2: Calibration comparison; default parameters of C are K = 20, 20, 000, and ó = 10"
Algorithm. Our algorithm takes the confidence predictor f. desired bound R>0 the unsafety probability, confidence level 6 E [0. 1]. calibration set W S x rollouts Ç ~ Dz. and calibra- tion set 7 C O of samples from distribution 1) described helow; see Appendix F.5 for details on sampling < and constructing W. Z, and D. We want to maximize y subject to Punsafe S E, where Punsafe is implicitly function of y. However, cannot evaluate Punsafe. we need an upper bound.
To this end, consider a rollout that the first unsafe state is encountered on step / (i.e., It g Xate but 3, Xat for all L), which call unsafe rollout, and denote the event that the unsafe rollout is encountered by E;; we exploit the unsafe rollouts to bound Punsafe- In particular, let = Pç-D, [Ee], and let p Ei=o Pt. be the probability that a rollout is unsafe. Then, consider new distribution over O with a probability density function (D( == Ei=o PD. (o E2) Pt/p. where draw an observation D by sampling the observation of the first unsafe state from a rollout sample (and rejecting if the entire rollout is safe). Then, we can show the following (see a proof of Theorem in Appendix E
PD+ is the original probability density function of D in particular,
Punsafe
P Po)D((()) = 0] Punsafee-
(8)
We use our confidence coverage predictor Co to compute bounds on Punsale i.e.,
f. f.Z 6
IP D (0(0) 1] E l.. Co
where
Z' ((0,1) O 2}
|r, Ocr
W
where
W' = (1(5 & Xsate) 15 W}.
Here, Z' is labeled version of Z, where "1" denotes "un-recoverable"" n = W/. and n' == |Z]. where 2 n'. Then, we have Punsafe F. (1 cc.. so it suffices to solve the following problem:
max 7 subj. 7'E(0.1]
F F. c) <
Here, is implicitly function of r': thus, We have the following safety guarantee, see Appendix for a proof:
line search to solve this optimization problem.
Theorem We have Punnade S & with probability at least 1 - over W ~ D and Z ~ D
5 EXPERIMENTS
We demonstrate that how our proposed approach can be used to obtain provable guarantees in our two applications: fast DNN inference and safe planning. Additional results are in Appendix G
5.1 CALIBRATION
We illustrate the calibration properties of our approach using reliability diagrams, which show the empirical accuracy of each bin function of the predicted confidence (Guo et al. 2017). Ideally, the accuracy should equal the predicted confidence, so the ideal curve is the line y σ. To draw our predicted confidence intervals in these plots, need to rescale them; see Appendix
F3
Setup. We use the ImageNet dataset (Russakovsky et al. 2013) and ResNet101 (He et al. 2016) for evaluation. We split the ImageNet validation into 20, 000 calibration and 10, 000 test images.
7

---

Published as a conference paper at ICLR 2021
520
drdind
pndeed eemo
J0n petrest
21 (sace
Ex-errp theothis)
M6
Hit. Desdiio
ogores found
250
234
[-0.01
[-0.55
(a) Comparison to baselines.
(b) Varying desired rate Ç.
method
lpp-1 emor
CPU (js)
GPU
MACSs
network
214.31
2,95
10
<") "--softmax (haseline)
22.34
104.24
1,78
6.60
10P
)-temperature scaling (haseline)
22.22
109.57
1.81
6.83
102
histogram binning (baselinc)
24.54
70.72
1.19
1.62
10
rigorous (ours)
23.26
85.58
1.34
5.33
10"
(c) Running time comparison.
Figure 3: Fast DNN inference results; default parameters are n2 = 20, 000, 5 = 0.02, and 6 = 10-3
Baselines. We consider three baselines: (i) naïve softmax of f. (ii) temperature scaling (Guo et al. 2017]. and (iii) histogram binning (Zadrozny & Elkan 200T); see Appendix F.2 for details. For histogram binning and our approach, use K 20 bins of the same size.
Metric. We use expected calibration error (ECE) and reliability diagrams (see Appendix F33
Results. Results are shown in Figure 2 The ECE of the naïve softmax baseline is 4.79% (Figure 2al, temperature scaling enhances this to 1.66% (Figure 2b), and of histogram binning is 0.99%
(Figure 2cp. Our approach predicts an interval that include the empirical accuracy in all bins (solid red lines in Figure 2c); furthermore, the upper/lower bounds of the ECE over values our bins is [0.0%, 3. 76%),, which includes zero ECE. See Appendix G.1 for additional results.
5.2 FAST DNN INFERENCE
Setup. We use the same ImageNet setup along with ResNet101 as the calibration task. For the cascading classifier, we use the original 1e1 as the slow network, and add single exit branch (i.e., .M = 2) at a quarter of the way from the input layer. We train the newly added branch using the standard procedure for training ResNet101.
Baselines. We compare to naïve softmax and to calibrated prediction via temperature scaling, both using a threshold 71 = 1 - <', where is the sum of and the validation error of the slow model; intuitively, this threshold is the brated. We also compare to histogram binning- -ie.. our approach but using the means of each bin instead of the upper/lower bounds. See Appendix F2 for details.
would use if the predicted probabilities are perfectly cali-
Metrics. First, we measure test set top-1 classification error (i.e. 1 accuracy), which we want to guarantee this lower than desired error (i.e., the error of the slow model and desired relative error (). To measure inference time, we consider the average number of autiiplication-accumbbbll erations (MACs) used inference per example. Note that the MACs are averaged over all examples in the test set since the combined model may use different numbers of MACs for different examples.
op-
Results. The comparison results with the baselines are shown Figure 3a The original neural network model is denoted by "slow network", our approach (6) by "rigorous" and our baseline by "(1-E')- soootma"""" "(1 - >-temp.". and "hist. bin.". For each method, we plot the classification error and time MACs. The desired error upper bound plotted classification error to be lower than this line. As can be seen, our method is guaranteed to achieve the desired error, while improving the inference time by 32% compared to the slow model. On the other hand, the histogram baseline improves the inference time but fails to satisfy the desired error. Asymptotically, histogram binning is guaranteed to be perfectly calibrated, but it makes mistakes due to finite sample errors. The other baselines do not improve inference time. Next, Figure (3b shows the classification error as we vary the desired relative eиror ş: our approach always achieves the desired error the test set, and often very close (which maximizes speed). However, the
dotted line; the goal is for the
8

---

Published as a conference paper at ICLR 2021
deaked sundy
Ins) (asscire) figross Couss
satwty
2-0.0 2-0.5 2-411 8-6as 2-0.33
(a) Comparison to baselines.
(b) Varying desired safety rate g.
Figure 4: Safe planning results; default parameters are: nt 20, 000, &
baselines often violate the desired error bound. Finally, the MACs metric is only an approximation of the actual inference time. To complement MACs, we also measure CPU and GPU time using the PyTorch profiler. In Figure 3c we show the inference times for each method, where trends are as before; approach improves running time by 54%, while only reducing classification error by 1%. The histogram baseline is faster than our approach, but does not satisfy the error guarantee. These results include the time needed to compute the intervals, which is negligible.
5.3
SAFE PLANNING
Setup. We evaluate on Habitat (Savva et al. 2019). an indoor robot simulator that provides agents with observations h(x)) that RGB camera images. The safety constraint is to avoid colliding with obstacles such as furniture in the environment. We use the learned policy î available with the environment. Then, we train recoverability predictor, trained using 500 rollouts with horizon of 100. We calibrate this model on an additional n rollouts.
Baselines. We compare three baselines: (i) histogram binning-i.e, our approach but using the means of each bin rather than upper/lower bounds, (ii) a naïve approach of choosing y 0.5, and (ii) a naive but adaptive approach of choosing ? = e, called "ç-naive".
Metrics. We measure both the safety rate and the success rate; in particular, a rollout is successful the robot reaches its goal state, and a rollout is safe if does not reach any unsafe states.
Results. We show results in Figure 4a The desire safety rate & is shown by the dotted line-i.e., we expect the safety rate be above this line. As can be seen, our approach achieves the desired safety rate. While it sacrifices success rate, this is because the underlying learned policy म is frequently unsafe; in particular,
only safe in about 30% rollouts. The naive approach fails to satisfy the safety constraint. The Ç-naïve approach tends to be optimistic, and also fails when (4b). The histogram baseline performs similarly to our approach. The main benefit of our approach providing the absolute guarantee safety, which the histogram baseline does not provide. Thus, in this case, our approach can provide this guarantee while achieving similar performance. Figure 4b shows the safety rate vary the desired safety rate ç. Both approach and the baseline satisfy the desired safety guarantee, whereas the naive approaches do not always do so.
0.03 (Figure
6 CONCLUSION
We have proposed novel algorithm for calibrated prediction that provides PAC guarantees, and demonstrated how our approach can be applied fast DNN inference and safe planning. There are many directions for future work-e.g, leveraging these techniques in more application domains and extending our approach to settings with distribution shift (see Appendix F. for a discussion).
ACKNOWLEDGMENTS
This work supported in part by AFRL/DARPA FA8750-18 18-C-0090, ARO 1NF-1N200--0000 DARPA FA8750-19-2-000 and NSF CCF 1910769. Any opinions, findings and conclusions or recommendations expressed in this material those of the authors and do not necessarily reflect the views of the Air Force Research Laboratory (AFRL), the Ammy Research Office (ARO), the Defense Advanced Research Projects Agency (DARPA), the Department of Defense, the United States Govermment.

---

Published as a conference paper at ICLR 2021
REFERENCES
A. K. Akametalu, J. F. Fisac, J. H. Gillula, S. Kaynama, M. N. Zeilinger, and C. J. Tomlin. Reachability-based safe learning with gaussian processes. In 53rd IEEE Conference on Deci- sion and Control, pp. 1424-1431, 2014.
Mohammed Alshiekh, R. Bloem, R. Ehlers, Bettina Könighofer, S. Niekum, and U. Topcu. Safe reinforcement learning via shielding. ArXiv, abs/1708.0861. 2018.
Osbert Bastani. Safe planning via model predictive shielding. 2019.
Tolga Bolukbasi, Joseph Wang, Ofer Dekel, and Venkatesh Saligrama. Adaptive neural networks for efficient inference. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 527-536. JMLR. org, 2017.
Lawrence D Brown, T Tony Cai, and Anirban DasGupta. Interval estimation for a binomial propor- tion. Statistical science, pp. 101-117, 2001.
Maxime Cauchois, Suyash Gupta, Alnur Ali, and John C. Duchi. Robust validation: Confident predictions even when distributions shift, 2020.
Charles J Clopper and Egon Pearson. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404-413, 1934.
Sarah Dean, Nikolai Matni, Benjamin Recht, and Vickie Ye. Robust guarantees for perception-based control, 2019.
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.
Andre Esteva, Brett Kuprel, Roberto A Novoa, Justin Ko, Susan M Swetter, Helen M Blau, and Sebastian Thrun. Dermatologist-level classification of skin cancer with deep neural networks. nature, 542(7639):115-111 2017.
Michael Figurnov, Maxwell Collins, Yukun Zhu, Li Zhang, Jonathan Huang. Dmitry Vetrov, and Ruslan Salakhutdinov. Spatially adaptive computation time for residual networks. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 1039-1048, 2017.
Fisac, A. K. Akametalu, M. N. Zeilinger, S. Kaynama, Gillula, and C. J. Tomlin. A general safety framework for learningbbased control in uncertain robotic systems. IEEE Transactions Automatic Control, 64(7):2737-2752, 2019.
Arthur Gretton, Karsten M Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola. 2012.
A kernel two-sample test. The Journal of Machine Learning Research,
Varun Gulshan, Lily Peng, Mare Coram, Martin C Stumpe, Derek Wu, Arunachalam Narayanaswamy, Subhashini Venugopalan, Kasumi Widner, Tom Madams, Jorge Cuadros, et al. Development and validation of deep learning algorithm for detection of diabetic retinopathy in retinal fundus photographs. Jama, 3 316(22):2402-244 2016.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. arXiv preprint arXiv: 170.00499, 2017.
HO Hartley and ER Fitch. A chart for the incomplete ceta-function and the cumulative binomial distribution. Biometrika, 38(344):433-426, 1951.
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, pp. 770-778, 2016.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. arXiv preprint 1503.0/503.0233 2015.
Kris M Kitani, Brian D Ziebart, James Andrew Bagnell, and Martial Hebert. Activity forecasting. In European Conference Computer Vision, pp. 201-214. Springer, 2012.
10

---

Published as a conference paper at ICLR 2021
Ananya Kumar, Percy S Liang, and Tengyu Ma. Verified uncertainty calibration. In Advances in Neural Information Processing Systems, pp. 3792-3803, 2019.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predic- tive uncertainty estimation using deep ensembles. In Advances in neural information processing systems. pp. 6402-6413, 2017.
Li and O. Bastani. Robust model predictive shielding for safe reinforcement learning with stochas- tic dynamics. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pp- 7166-7172, 2020.
Shuo Li and Osbert Bastani. Robust model predictive shielding for safe reinforcement learning with stochastic dynamics. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 7166-7172. IEFE, 2020.
Peng Liao, Kristjan Greenewald, Predrag Klasnja, and Susan Murphy. Personalized heartsteps: A reinforcement learning algorithm for optimizing physical activity. Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies, 4(1):1-22, 2020.
Allan H Murphy. Scalar and vector partitions of the probability score: Part i. two-state situation. Journal of Applied Meteorology, 11(2):273-222, 1972.
Mahdi Pakdaman Nacini, Gregory Cooper, and Milos Hauskrecht. Obtaining well calibrated prob- abilities using bayesian binning. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
Sangdon Park, Osbert Bastani, Nikolai Matni, and Insup Lee. Pac confidence sets for deep neural networks via calibrated prediction. In International Conference on Learning Representations, 2020a. URL http:httss/::peeeeee
net/ Fo
Sangdon Park, Osbert Bastani, James Weimer, and Insup Lee. Calibrated prediction with covariate shift via unsupervised domain adaptation. In The 23rd International Conference on Artificial Intelligence and Statisties, 2020b.
John Platt. Probabilistic outputs for support vector machines and comparisons to regularized likeli- hood methods. Advances in large margin classifiers, 1999.
Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: Towards real-time object detection with region proposal networks. In Advances in neural information processing systems, pp. 91-99, 2015.
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 recognition challenge. International journal of computer vision, 115(3))11122) 2015.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International Conference on Machine Learning, pp. 4433-4441, PMLR, 2018
Manolis Savva, Abhishek Kadian, Oleksandr Maksymets, Yili Zhao, Erik Wijmans, Bhavana Jain, Julian Straub, Jia Liu, Vladlen Koltun, Jitendra Malik, Devi Parikh, and Dhruv Batra. Habitat: A Platform for Embodied AI Research. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), 2019.
Surat Teerapittayanon, Bradley McDanel, and Sosiang-Tsung Kung. Branchynet: Fast inference via early exiting from deep neural networks. In 2016 23rd International Conference on Pattern Recognition (ICPR), pp. 2464-2469 IEEE, 2016.
Ryan Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal predic- tion under covariate shift. Advances in Neural Information Processing Systems, 32:2530-2540, 2019.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27(11): 134-1111134443 1142, 1984.

---

Published as a conference paper at ICLR 2021
Kim Wabersich and Melanie Zeilinger. Linear model predictive safety certification for learning- based control. 03 2018. doi: 10.1 11.////C...1..8119......
Xin Wang, Fisher Yu, Zi-Yi Dou, Trevor Darrell, and Joseph E Gonzalez. Skipnet: Learning dy- namic routing in convolutional networks. In Proceedings of the European Conference Com- puter Vision (ECCV), pp. 409-424, 2018.
Bianca Zadrozny and Charles Elkan. Obtaining calibrated probability estimates from decision trees and naive bayesian classifiers. In Proceedings of the Eighteenth International Conference on Machine Learning. Citeseer, 2001.
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. 694 699, ACM, 2002.
12

---

Published as a conference paper at ICLR 2021
A CONNECTION TO PAC LEARNING THEORY
We explain the connection to PAC learning theory. First, note that we can represent C as confidence interval around the empirical estimate of cf(x))ie,, εy(x) = (ar 1 ((2)))/1ss)
where S₂ {(d', p(x') Bey(x)) Then, we can write
((x) = 10)(z)) - Sx - c te]
In this case,
is equivalent to
PM~D"
sc((x) - Sxy(o) S S ((((2) + (xy(()) 21- 5,
(10)
LEE
for some E1, ........... EK, In this bound, "approximately" refers the fact that the empirical estimate (z) is within of the true value cz(x). and "probably" refers to the fact that this error bound holds with high probability over the training data D" By abuse of terminology, we refer to the confidence interval predictor Ć as PAC rather than just (z(r).
Alternatively, we also have the following connection to PAC learning theory:
Definition 3 Given e, E R>o and E N, Ô is probably approximately correct (PAC) if, for any distribution D, we have
P PEwD (cg(x) Ölz: f.): 2 1 1--c - 8.
P PZ-Da
(11)
The following theorem shows that the proposed confidence coverage predictor satisfies the PAC guarantee in Definition
13

---

Published as a conference paper at ICLR 2021
Theorem 5 Our confidence coverage predictor Ö satisfies Definition 3 for all e, E Ryo. and n E N.
We exploit the independence of each bin for the proof. Let (xz(m) cz(x), which is the parameter of the Binomial distribution of the ki (z)tt bin, the following holds:
Proof.
cj(x) e Ölz e 2 21-6
P 2~D"
K
c7(x) E 0(: f. A V p(x) E Be 21-E k=
P
P
2~D
K
Σ
(cglz) E f(z;f 2, p(x) Ba] 21 -
P
P
D
P
Σ
IP
(c((x) E Ö(; 1,0,0 ((x) BE
IP (ī(x) B&] 2 1 1
Z=D
2nD
anD
K Σ
Wxx: xx)
P
P
Og E Ôcr
p(x) E Bs
P
1p(x) By] N 1-6
ZnDn
anD
K
)
P Dn
Σ
1
0x Ocp
Whi -
P [p(x) E B&l 21-6 anD
P
Ok Ocp
WWs K
IP [p(x) B1 znD
Z-D"
^
A 1 Ox E θer k=1
K
Wki K 1
-1
K
1
0g θcr
- ] WKii
P
[p(x) E B&] 2 1-
A
K
On Oce
(Was: x
]
K
D
aND
k=1
(WA: 5
)
IP Dr
A 1
ON Ocr
P
Σ
K
P
[pxx)
E B-]21-
K A
I
On
E
Ôcp
WRi K )]
-11
Dn
k=1
(x) }
IP Z~Dr
A
1
ON
Ôer
WKii
L=l
K
8
]
K
Ox E Ocp (Wis:
8
P 2n
121
A
O2 E Ôcp
WAi
K
2~D
PP
K
K
WKi K )
P ZnD
A 1 ON E Ôcr
-
=
A=1
A On ÔcP Wes )
K
Z~
k=1
6,
where the last inequality holds by the union bound.
14

---

Published as a conference paper at ICLR 2021
B PROOF OF THEOREM 1
We prove this by exploiting the independence of each bin. Recall that C(x) = (()=))=((()))-0)) c. (x()) +
&... and the interval obtained by applying the Clopper-Pearson interval with confidence level 4 at each bin. Then, the following holds due the Clopper-Pearson interval for all A E {1, K}: K
p [[ - 2j
ch
S
K
where Cf cf(x) and Gg == 2 for x such that xz(()) k. and en max(sx)) By applying the union bound, the following also holds:
K P
f. jj >
Sd,
Considering the fact that X' is partitioned into K spaces due to the binning and the equivalence form I0 of the PAC criterion in Definition 3 the claimed statement holds.
C PROOF OF THEOREM 2
We drop probabilities over (2, D. First, we decompose the error of cascading classifier P (x) # y] as follows:
(1)()) # y] P [0(()) * n (Dc(x) (M()) (0(x)) + Br((=)]
PP (Dc(x) * A (x(x) = (x) (ic(T)) # y de (x) + (M((1)) P (i(()) # y (c(x) (N)( + PP (x) # y (c(x) # (M(2))
where the last equality holds since the events of fc = DAs (x) and of (c + UM (x) are disjoint. Similarly, for the error of slow classifier P [uM (x) * y). we have:
P (z) + y| = [+)(()) * y A (c(2) = PM (z)) + IP [MM(x) # y dc(x) + (ms(z)).
Thus, the error difference can be represented as follows:
IP (x) + v] IP [is (x) y] PP [ # A (o(x) # (as(x) - P 19M + y $c(x) # (x)())). (12)
To complete the proof, need upper bound 12 by Define the following events:
Dm = A (f((x) <<) A (m(x)) 7m (Vm E (1...., M 1})
1=1
DM A (fi(x) 7c)
Ec = (x) # (x)
Em = 0m (I) # (M(
(Vm E (1,..., M 1})
Fc = (z(x) #
Fm = (m) $y
(Am E fl,... M 1})
G = UM (2) + V,
15

---

Published as a conference paper at ICLR 2021
where D1, D2...... Dar form a partition of sample space. Then, we have: PP ())()) # y (c(x)) + (M)( IP Fc Ec]
M
=P Fc Ec A
V Dm m=1
M
P
V (FC RC Dm)
L
Σ P [ Dml
Σ P [F Em A Dml
m=1
M
Σ m=1
P [F Fm A Dml P FF A Din)s
Similarly, we have:
M
P (f) + y (c(x) # (M(x)]
Σ
[
Em A Dm) P [Em A Dm)
m=1
Thus, 12
can be rewritten follows:
[+(()) * yl IP (x) # y]
M
Σ m=1
(IP [I'm
Em A Dml P Em A Dm] IP [G Em A Dml - PP [Em A Dml)
M
(cm
emm))
m=1
(cm
émm
S. where the last equality holds since eœ c = O, and the last inequality holds due to (6 probability least 1 6, thus proves the claim.
with
D PROOF OF THEOREM 3
Suppose there is 71 which is different to 7 and produces a faster cascading classifier than the cascading classifier with 7 Since 7 is the optimal solution of (6). 7í > 75. This further implies that the less number of examples exits at the first branch of the cascading classifier with 7 but these examples classified by the upper, slower branch. This means that the overall inference speed of the cascading classifier with 7 slower then that with 7 which leads to a contradiction.
PROOF OF THROREM
denote state is "recoverable" (i.e., y²(x) 0) and u to denote state x "un-recoverrabe" (i.e. y (x) 1). Now, note that a rollout (( Thhiela) == (To. 2 21,...) unsafe if (i) some step have (*x)) u (i.e. H, is not recoverable), yet (((z) r. where = h((x)) (i.e., y predicts vs is recoverable), and furthermore (ii) for every step S - 1. (zx) ((,)) i.e.
For clarity,
(r)))) =r) (1"(x)) = uAD(O)) =r) )
Punsate Pg- D Dresiit
(13)
16

---

Published as a conference paper at ICLR 2021
Condition (i) is captured by the second parenthetical inside the probability;; intuitively, it says that ((or) is a false negative. Condition (ii) is captured by the first parenthtiica inside the probability; intuitively, it says that ((;;) is true negative for any S t - 1. Next, let the event E, be
t-1 E = (x)) = 22 (x1) u.
then the following holds:
oo
(v(t)==ralln = (uno))=
Pen renidd
y0 (2,) = = (x)) (())))))''()))) = =w) ^ \ ((a)) = ((or) (r =r) =
1==
o(o,) =r) ] Es BEASSOD) ((or) =
2-1
P'g
Es A A ((o:) = =ra
1==0
==0
V
< Pe
Recall that p upper-bound as follows:
1== PE-D, [bj] and po(o)= = Eizo E.) PE-D. then we can
00 V 1==0
Ee A ((or) =+)
Punsafe S Pg Drsisl
PE Desss
[Ee ((o)) =r]
P PE Dr - (ū(0r) =r Fe]] P eh D [E
PE- Drenss [0(0)= =r Eel P' [Ei]
Σ1 f 1(8(0)= =r) .D (0 ( IPEDDran [Er] do
/ 10(() = Σ
PD (ol Ex) Pe-D.
saia [Eg] do
1=
$ 10((0) = r) Σ
PD, (0 E PgpDD [Eg] do
t=
1(((0) = (o)
= P. P POD( = r),
where we use the fact that F, are disjoint by construction for the first equality, and we use o without time index for the third equality since it clearly represents the last observation if it is conditioned on E. Moreover, the last inequality holds due to the following: (i) PD (o E,) PD. (o E, since E, implies that the backup policy of Tahield isn't activated up to the step t, so Tshield = A. and (ii) IP iPg-D.and [E]] < Pe-D. [Er], since mabield less likely reach unsafe states by its design than #. Thus, the constraint in 99) implies Punsate S & with probability at least - 5, so the claim follows.
17

---

Published as a conference paper at ICLR 2021
F ADDITIONAL DISCUSSION
F.1 LIMITATION ON-DISTRIBUTION SETTING
Our PAC guarantees (i.e.. Theorems I & (5) transfer to the test distribution if it is identical to the validation distribution. We believe that providing theoretical guarantees for out-of-distribution data is important direction; however, wards this goal. In particular, to the best of our knowledge, we do not know of any existing work that provides theoretical guarantees on calibrated probabilities even for the in-distribution case. One possible direction is to use our approach in conjunction with covariate shift detectors-e,, (Gretonnn a 2012). Alternatively, may be possible directly incorporate ideas from recent work on cali- brated prediction with covariate shift (Park et al. 2020b) or uncertainty set prediction with covariate shift (Cauchois et al. 2020 Tibshirani et al. 2019). particular, we can use importance weighting ((z)/p((z) where p(æ) is the training distribution and q(x)) is the test distribution, to reweight our training examples, enabling us to transfer our guarantees from the training set to the test distribution. The key challenge is when these weights unknown. In this case, can estimate them given set of unlabeled examples from the test distribution (Park et al. 2020b), but we then need to account for the error in estimates.
believe that our work is important stepping stone to-
F.2 BASELINES
The following includes brief descriptions on baselines that used in experiments.
Histogram binning. This algorithm calibrates the top-label confidence prediction of f by sorting the calibration examples (Ir, y) into bins B; based on their predicted top-label confidence-i.e. (x, y) is associated with B; if f(xx) E B;. Then, for each bin, it computes the empirical confidence P: = [5: Ee.,))ss ((((z)= = y). where S; is the set of labeled examples that are associated with bin B B.e. the empirical counterpart of the true confidence in (2). Finally, during the test-time, it returns a predicted confidence i; for all future test examples p(x) E B,.
(1 (1- (1- )-softmaxx In fast DNN inference, a threshold can heuristically chosen based on the desired relative error & and the validation error of the slow model. In particular, when a cascading classifier consists of two branches-i.e M the threshold of the first branch is chosen by the sum & and the validation error of the slow model. We call this
71 = 1 < where approach (1 E >ssoftmax.
(1 - 5 ) -tmpeerature scaling. A more advanced approach to first calibrate each branch to get better confidence. We consider using temperature scaling to do so so-i.e, first calibrate each branch using the temperature scaling, and then the branch threshold by ? 1 when M 2. We call this approach (1 )-temperature scaling.
F.3 CALIBRATION: INDUCED INTERVALS FOR ECE AND RELIABILITY DIAGRAM
ECE. The expected calibration error (ECE), which is way to measure calibration performance, defined as follows:
S S
ECE
p(z)
Σ 1(0(x) = y)
|S
[S
(w.y)s
(a.))SS
where J is the total number of bins for ECE, S C X x y is the evaluation set, and SJ is the set of labeled examples associated to the jth bin-i.e., (x, E S, if p(x) B,.
confidence coverage predictor Õ(x) outputs an interval instead of a point estimate f(x) of the confidence. To evaluate the confidence coverage predictor, we remap intervals using the ECE formulation. In particular, we equivalently represents ((x) by mean confidence (x( and dif- ferences from the mean-i.e. Ö(x) (()))<()) (ē)(x)) e,, (y(x) + En] (see Appendix A for description this equivalent representation). Then, sort each labeled example into
18

---

Published as a conference paper at ICLR 2021
bins using ()(x) to form Sy. Le., ECEinduced
Next, consider an interval instead of p(x) to compute ECE
ECE, ECE],
where
SS
ECE
inf By PCaat
Pj
Σ [(ū(z) y)
|||
|Sy]
|Sg |S|
ECE
sup By ECoat
Pj |S (z,
(((x)) = v)
and
j=1
Confy = Conff. Confy)
=
min c(x), max a(x) (w.y)ES,
(x.w))S
Reliability diagram. This evaluation technique pictorial summary of the ECE, where the x- axis represents the mean confidence [5y ((sw)ss p(x) for each bin, and the y-axis represents the
mean accuracy [S,] (z,))ss (()(x) y) for each bin. If an interval from confidence coverage predictor is given, then the mean confidence is replaced by Conf,, resulting in visualizing an interval instead of point.
F.4 FAST DNN INFERENCE: CASCADING CLASSIFIER TRAINING
We describe a way to train a cascading classifier with M branches. Basically, we consider to inde- pendently train M different neural networks with shared backbone. In particular, we first train the Mth branch using training set by minimizing a cross-entropy loss. Then, we train the (M 1)th branch, which consists of two parts: backbone part from the Mth branch, and the head of the (M 1 1)th branch. Here, the backbone part is already trained in the previous stage, so we do not update the backbone part and only train the head of this branch using the same training set by mini- mizing the same gross-entrope loss (with the same optimization hyperparameters). This step is done repeatedly down to the first branch.
F.5 SAFR PLANNING: DATA COLLECTION FROM A SIMULATOR
We collect required data from simulator, where given policy á is already learned over the simu- lator. We describe how we form the necessary data from rollouts sampled from the simulator.
First, to sample rollout Ç. use á from random initial state Zo D; denote the sequence of states visited as a rollout (#0, #) = (æa, ......). ). We denote the induced distribution over rollouts by 5 Dz- Note that the contains unsafe states since î is potentially unsafe. However, when constructing our recoverability classifier, we only use the sequence of safe states, followed by a single unsafe state. In particular, let W be a given rollout, we consider the observation in the first unsafe state in that rollout (if one exists); we denote the distribution over such observations by D. Finally, we take to be a set of sampled observations o ~ D.
of i.i.d. sampled rollouts Ç Da- Next, for
G ADDITIONAL EXPERIMENTS
G.1 CALIBRATION
19

---

Published as a conference paper at ICLR 2021
ECE 4.79%
ECE 1.66%
estimated
estimated
ideal
Ideal
ratio
ratio
example ratio
eX3 example ratio
0.6
0.6
accuracy
0.6
2.6
0.8
0.0
0.0
confidence
confidence
(a) Naive softmax
(b) Temperature scaling
ECE = 0.99%
ECE 0.99%
[0.00%, 3.76%]
estimated
estimated
ideal
Ideal
0.0
ratio
0.8
0.3
ratio
3.8
example ratio
mxpm ratio
accuracy
0.6
accuracy
0.6
0.2
0.2
0.0
confidence
confidence
(c) Histogram binning
(d) Proposed
Figure 5: Calibration comparison in reliability diagrams and ECES. The size of validation set for calibration is 20, 000. The blue histogram represents the example ratio for the corresponding bin. The diagonal line labeled "idcal" is the best reliability diagram, which produces the zero ECE. The estimated reliability diagram is represented "estimated" in dotted red.
(a) The naïve softmax output from neural network is unreliable in ECE. (b, c) The temperature scaling and histogram binning are fairly good calibration approaches. which decreases ECE. (d) The proposed approach generates "induced" intervals (see Appendix FF3) on top of the histogram binning approach, where each interval contains the ideal diagonal line with high probability. Moreover, the proposed one also produces induced ECE interval, where it contains the zero ECE with high probability.
20

---

Published as a conference paper at ICLR 2021
ECE = 4.79%
ECE 1.72%
estimated
estimated
ideal
ideal
0.8
ratio
ratio
9.8
example ratio
example ratio
0.6
accuracy
2.6
6.2
0.9
0.
0.0
confidence
confidence
(a) Naive softmax
(b) Temperature scaling
ECE 2.14%
ECE 2.14% [0.00%, 12.09%)
1.0
estimated
estimated
ideal
ideal
0.8
ratio
0.0
0.8
exampi ratio
example ratio
accuracy
accuracy
0.2
02
022
0.0
0.6
confidence
confidence
(c) Histogram binning
(d) Proposed
Figure 6: Calibration comparison via reliability diagrams and ECE. The size of validation set for calibration is 000. See the caption of F interpretation. For the induced intervals, the length of the interval is larger than that with = 20, 000 due to the estimation error.
1.00
softmax
temp.
conditional accuracy
0.95
hist. bin.
ours
0.90
0.85
0.75
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
confidence threshold
Figure 7: Accuracy-confidence plot. This plot is useful for choosing proper confidence threshold that achieves a desired conditional accuracy (Lakshminarayanan et al., (017)) the a- axis is the confidence threshold and the y-axis is the empirical value of the conditional curacy P (x))
p(()) 2 t]. Since our approach outputs an interval [c(z), we plot [}(x)) c(x) 2 t and [z) y π(अ) 2 t] for the upper and lower bound of the green area, respectively.
21

---

Published as a conference paper at ICLR 2021
G.2
FAST DNN INFERENCE
estimated trade-off
estimated trade-off
rigorous (ours)
rigorous (ours)
hist. bin, (baseline)
hist. bin, (baseline)
()-sottmax (baselino)
El)ssottma (baseline)
1%0
25
te-temp. (baseline)
1%
f'-ttep.. (baseline)
desired
desired
23
23
3.0
1.2
1.1
0.4
1.2
3.1
MACS
X30
MACS
X308
(a) 5, 000
(b) n 10, 000
esti mated trade-off
esti matie trade-off
rigorous (ours)
rigorous (ours)
hist. bin. (baseline)
26-
hist. bin. (baseline)
(1 so)sootaaxx (baseline)
(1 sofmmax (baseline)
(90)
(1 C'-temp. (baseline)
(%)
(1 E'-temp. (baseline)
desired error
desired error
24-
24-
X30
X30*
(c) nl 15, 000
(d) 12 20, 000
Figure 8: Ablation study on various n for g 0.02, = 10-2, and M shown number of samples with the same & and 5. The "estimated trade-off" represents the error and MACs trade-off depending on threshold 71. The markers show the trade-off by the baselines. The "desired error" is user-specified error bound, where the error of each method need to be below of this line. The proposed approach reduces the inference speed as the number of sample increases, while satisfying the desired error bound. The baselines are either fails to satisfy the desired error bound or overly conservative to satisfy the bound.
Each plot uses the
22

---

Published as a conference paper at ICLR 2021
estimated trade-off
estimated trade-off
rigerous (ours)
rigerous (ours)
hist. bin. (baseline)
hist. bin. (baseline)
(1 soffmmaa (baseline)
(1 so)sooxaax (baseline)
(40)
25
(1 E'-ttmp. (baseline)
(%)
25
(1 E'l-temp. (baseline)
desired
3.0
1.2
1.1
1.2
0.1
1.2
1.1
MACS
X30
MACS
X30
(a) 0.01
(b) { 0.02
est mated trade-off
estimatted trade-off
rigerous (ours)
rigerous (ours)
20
[baseline]
26-
(baseline)
(1 El)sootmax (baseline)
(1 11--2 E')-sotmaax (baseline)
(1 E1-temp. (baseline)
(1 E'lttemp. (baseline)
desired emro
desired emror
M.CC
MACS
(c) f = 0.03
(d) E = 0.04
Figure 9: Ablation study on various & for = 20, 000, 5 10-2, and M 2. Each plot uses the shown desired relative error & with the same and 8. The "estimated trade-off" represents the error and MACs trade-off depending on threshold 71- The markers show the trade-off by the shown baselines. The "desired error" is user-specified error bound, where the error of each method need to be below of this line. The proposed approach allows more error as at most specified by the desired error, reduce the inference speed. Other baselines either overly increase the error or conservatively maintain overly low error.
23

---

Published as a conference paper at ICLR 2021
esti trade-oft
estimaated trade-off
rigorous (ours)
rigorous (ours)
hist. bin. (baseline)
hist. bin, (baseline)
(o)ssottmax (baseline)
(')-sottmax (baseline)
error 25
('Htemp. (baseline)
(%)
23
d'Htemp. (baseline)
desired
desired
23-
23-
0.4
399
1.
1.1
1.4
0.4
0.9
1.7
1.1
MACS
MACS
(a)
(b)
estimated trade-off off
estimated trade-off
rigerous (ours)
rigerous (ours)
26
26
(baseline)
(1 E')sootmax (baseline)
(1 s')sootaax (baseline)
(1 t1-tomp. (baseline)
(1 E1-ttmm. (baseline)
desired error
desired error
MACS
MACs
(c) 5 = 10-3
(d) 8 = 10-4
Figure 10: Ablation study on various for n = 20, 000, { = 0.02, and M = 2. Each plot uses the shown misconfidence level 8 with the same and ç. The "estimated trade-off" represents the еттог and MACs trade-off depending on threshold 71. The markers show the trade-off by the shown baselines. The "desired error" is user-specified error bound, where the of each method need to be below of this line. The proposed approach produces larger error gap toward the desired error as we enforce stronger confidence level from ó 10 to 8 10 Note that other baselines do not depend on d as designed.
24

---

Published as a conference paper at ICLR 2021
G.3
SAFE PLANNING
nalve Ibaselinel
naive (baselinel
Enaiie (baseline)
Enaiie (baselin)
(%)
(baselire]
linring
succets rato 1%
(%)
(baselire)
tinning
succeds rate (60)
ngorous
rigerous
safety
success
safety
success
(a) n 20, 000
(b) n2 15, 000
thaseline)
(haseline)
Enaive (baseline)
Enaive (baseline)
(baselire)
binring
SucCesS rate (%)
(963
(basel lnee
binning
SucCESS rate (%)
rigorous
Safety
success
safety
success
(c) n = 10, 000
(d) n = 5, 000
Figure 11: Ablation study on various for and 10-2, Each plot uses shown sample size with the same & and 6. The "naive", "f-naiie", and "histogram binning" represent baseline results on the safety rate and success rate. The proposed approach is labeled "rigorous". ". The desired safety rate is a user-specified rate, where the safety rate of each method need to be above of this line. The safety rate of the proposed approach is above the desired safety rate, and it tends to be closer to the desired safety rate increases.
25

---

Published as a conference paper at ICLR 2021
desied (baseline)
desired safety (baseline)
E-naive (baseline)
E-naive (baceline)
tinning
sucress rate 0%
binning
Success rate (S0
Ibaseline
(baseling
safeey
safety
success
safety
success
(a) { 0.2
(b) { 0.15
desined safety rate Enaive (baseline)
desired safety rate (baseline)
Enaive (baseline)
Nistogram ainiing
success (%)
histogram binning
SucCCss (%)
(baseline)
(baseline)
(oun)
(oun)
safecy
safecy
safety
safety
(c) = 0.1
(d) E 0.05
Figure 12: Ablation study on various for n 20, 000 and 5 10 2, Each plot uses the shown desired unsafe rate with the same and The "naive", "Ç-naive", and "histogram binning" represent baseline results on the safety rate and success rate. The proposed approach is labeled "rigorous". The desired safety rate is a user-specified rate, where the safety rate of each method need be above this line. The safety rate the proposed approach is closely above the desired safety rate to satisfy the safety constraint. However, the naive can violate the safety constraint, and n-nvve can overly optimistic. The histogram binning and g-naive look empirically fine, but they can in theory violate desired safety rate (e.g.. Figure 4b)
26

---

Published as a conference paper at ICLR 2021
desied safety rale
desired safety rate
(baseline)
Enaive (baseline)
Enaive (baseline)
rale (96)
(baseline]
Nittgram ainiing
succoss (50
histogram binning
(baseline)
SUCCIOS (50
rigoroux (ours)
rigeroux (oum)
safety
safety
success
safety
success
(a) 5 = 10
(b) = 10
desired
desired safety
(baseline)
(baseline)
E-niie (baseline)
E-aive (baseline)
Ibaseline)
tinning
success rate (%)
safely 0%)
(baseling
binning
Success (S))
safegy
safety
Success
safety
success
(c) Ā = 10
(d) 8 = 10
Figure 13: Ablation study on various for n 20, 000 and { = 0.1. Each plot uses the shown misconfidence level & with the same n and Ç. The "naive"" "ç-naive". and "histogram binning" represent baseline results on the safety rate and success rate. The proposed approach is labeled "rigorous". The desired safety rate is user-specified rate, where the safety rate of each method need to be above this line. The proposed approach produces more conservative safety rates- i.e., larger gap between the estimated safety rate and desired safety rate-as we enforce stronger confidence level-iee, from = 10-1 to = 10-4 Note that other baselines do not depend on as designed.
27


Reviews:
[{"review_id": "km1PF3H6C0T", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper proposes a method for obtaining probably-approximately correct (PAC) predictions given a pre-trained classifier. The PAC intervals are connected to calibration, and take the form of confidence intervals given the bin a prediction falls in. They demonstrate and explore two use cases: applying this technique to get faster inference in deep neural networks, and using the PAC predictor to do safe planning. Experiments in both of these cases show improvements in speed-accuracy or safety-accuracy tradeoffs, as compared to baselines.\n\nI’m recommending acceptance since the idea seems useful and well-argued both conceptually and experimentally. However, the paper needs some work in terms of clarification of the key ideas – with this clarification I can raise my score.\n\nStrong points: \n-\tThe proposed method provides a provable guarantee on the reliability of a pre-trained methods prediction, which is a very nice property to have in the reliability/safety problem.\n-\t This approach is a simple but good idea, seems grounded in a good motivation and the explored use cases are informative and interesting. \n-\tExperimentally, the method shows improvements over a naïve baselines, and demonstrate that it can obey a given error or safety threshold in practice, an important property\n\nWeak points + Clarifications:\n-\tI am confused about the application of this method to safe planning. In particular, it seems to me like the proposed intervals only hold their PAC guarantee when the test-time distribution matches the training distribution. However, this will not be the case in the safe planning setting as I understand it, since the observed trajectories are drawn from a different policy than the one which will be implemented in the world\n-\tWith respect to these test set questions, it would be nice to see a little discussion in the paper of how these guarantees transfer from training set to the test distribution\n-\tI would like to see more explanation of the proofs in the appendix, right now they are a little too compact for me\n-\tExperimental baselines raise some questions for me. First, I need more explanation on the histogram binning baseline beyond the one sentence given. Second, the authors state this baseline “does not satisfy the desired error” – but I’m not sure why we would expect it to, since that baseline was not tuned to any sort of error level. Finally, I would like to see naïve threshold baselines in the safe planning setting for more cautious values than 0.5 – since that is more aligned with the goals of safety.\n-\tIn your PAC definition, we could just always output [0, 1] to satisfy it. Therefore, when framing the goals of your method, you should be a little more clear about exactly what you want from a PAC prediction.\n-\tA number of notation errors throughout which are important to fix for clarity and neatness, and a decent amount of lack of precision in language throughout which is important to fix for clarity. See Other Feedback\n-\tLine below Eq 5 confuses me: you say you exit at m if \\hat{y}_m correctly classified an example also correctly classified at \\hat{y}_M. But how can you know this without doing inference to the last layer?\n-\tIs there a reason why the greedy approach to Fast DNN inference you take is desirable? Be more clear about why you chose this and if it is optimal somehow or not\n\nOther feedback:\n-\t- Some precision in language could be improved throughout – for instance “by using the accurate model only if the confidence of the accurate one is underconfident” on p2 doesn’t really make sense\n-\t-p2: “a naively trained DNN is not reliable” what does reliable mean here?\n-\t-above eq 2, should this be \\kappa_x ?\n-\t-Defn 1: should this be a nearness constraint rather than equality? We have multiple examples x in a bin each with their own p-hat, and so not all of them can be equal to c(x)\n-\t-Is there a reason why these intervals should be defined as continuous rather than possibly a disjoint set?\n-\t-should make it clearer from the start that this is defined for post-hoc classifiers, you’re not learning these intervals directly\n-\tEq 4 – the bold theta-hat here is different from the one defined in the line above\n-\tNeed more explanation on “The following expression is equivalent due to the relationship between the Binomial and Beta distributions” p. 4\n-\tIn the definition of C-hat, you’re overloading x on the right side of the given sign. Can you use x’ or something?\n-\tIn the “important case” below Thm 1, can you clarify – this is the mean right?\n-\tProblem formulation in Fast DNN Inference: should the \\hat{y}_i be \\hat{y}_m? I feel like i is not scoped here\n-\tYou define d_m below the problem formulation but it isn’t in the formulation itself.\n-\tTop of p5, you train the network in the “standard way” – this is not clear. Do the gradients at the lower levels flow back through the earlier layers? Or are they stopped and the only gradients are from the final prediction task at the last layer? Either could make sense to me\n-\tShould define more carefully what the “composed classifier” refers to\n-\tClarify how rollouts work – will you observe unsafe states? Sometimes in safe planning you assume you don’t actually observe the unsafe states in training but it looks like you need that\n-\tBottom of p6: what is Z’? Not sure what Z is – is it ordered pairs? Why is the second element always 1?\n-\tP13: why is this an upper bound? It’s hard to parse but it looks equal to the expression in 10 at first glance – it’s the appendix so please explain further. You can also note that the E_t are disjoint by definition\n-\tAlso please add comments about the appendix figures? I have no idea what they are\n \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "_W0xIiVPqa", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This is a paper that focusses on the timely and important problem of uncertainty quantification for the predictions of deep neural network classifiers. The authors propose constructing calibrated outputs that have provable correctness guarantees, using PAC-style arguments. \n\nThe authors also demonstrate how this framework can be utilized for computationally efficient predictions by combining a smaller, faster albeit less accurate model with a larger, more accurate model, utilizing the latter only when the former is less confident. For this to work, one needs good guarantees on the DNN's estimates of its confidence -- and creating such guarantees forms the crux of the paper.\n\nPros:\n+ Paper is well written\n+ Important and timely problem, motivating arguments are well constructed\n+ Paper appears to be mathematically sound though I did not check all the proofs in the appendix.\n\nCons\n+ One of the crucial assumptions is that the data during test time will be from in-distribution. While I understand it is hard and maybe impossible to provide any guarantees for out-of-distribution data,  it is important to realize that one of the most common ways in which DNNs can fail when deployed in safety critical systems is when faced with predicting from an out-of-distribution data. So it is unclear how  practically applicable the proposed method is. \n\n+ If somehow, one is always guaranteed to work within in-distribution data, then the authors should compare other methods that improve calibration (but don't have guarantees) with the proposed method, both in terms of calibration and computational efficiency in the fast-model/slow-model approach.\n\n+ Also I do not see any calibration performance in the experimental results. While I understand the proposed method is using histogram binning and is not a new calibration method per se, these results should be included. That is,show how  accuracy correlates with the softmax predictions (on the test set) using proposed technique.\n\n+ Since the proposed method provides stronger UQ than other methods, I would also like to see accuracy-vs-coverage curves for benchmark datasets, and compare this to such curves for the baseline (where one thresholds on the winning softmax scores).\n\nOverall, this is a very worthwhile line of work, and I feel the paper has merit, but given that some important results are missing, as it stands, does not meet the bar for acceptance. \n\n== Post rebuttal update ==\n\nSee my response to author's rebuttal below. In light of new experimental results, I feel this now meets the bar of acceptance at ICLR, and hence  updating my score to 6.", "extra_scores": {}, "extra_text": {}}, {"review_id": "GQK1pFFLkDN", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "In this work, the authors provide a method for a posteriori calibration of DNN uncertainty with emphasis on constructing a classifier that has PAC uncertainty guarantees. The authors define a ‘calibrated’ probability prediction to be one such that given (for example) an image labeled as a cat, that the probability assigned to the class label ‘cat’ by the predictor is equivalent to the probability that the classifier correctly predicts images from the class ‘cat.’ The authors seek to create a ‘provably’ correct classifier under iid data assumptions. \n\nAccounting for and re-calibrating the poor uncertainty of neural networks is a central problem for deep learning especially when operating in safety-critical domains and so the work is certainly attempting to attack a worthwhile problem.\n\nOne concern I have about the theory laid out by the authors is that they place no conditions on \\hat{f}. That is, one could have a classifier which has arbitrarily bad uncertainty calibration. Take for example a predictor \\hat{f} which assigns \\hat{p}(x) = 0.9 to every input ‘x’ regardless of its ultimate accuracy on the class, then given a new input with unknown label, it is not clear to me exactly how the framework would use the intervals to improve the uncertainty of this classifier, especially given that the class of this new point is unknown. I would appreciate if the authors could help me understand this case as I think it is indicative of a misunderstanding on my part. \n\nAnother concern is the fact that getting well calibrated Clopper-Pearson intervals with good statistical guarantees takes a non-trivial number of samples and it appears this would scale with the number of classes. Thus, for a task like ImageNet, the authors inference model would require the set Z to be quite large (quoted at 20000). It seems that considering this overhead would greatly slow the average inference time. Is this overhead considered in figure 2a? I think this is a OK trade-off to make when in safety-critical scenarios, but then the authors give “fast inference” as one of their primary applications, it seems like a bit more discussion of this may be warranted. \n\nThe authors use the word “provably” correct in a couple places (page 2 and 3) where the correct term they should use is “probably” or PAC. Saying that a statistical guarantee is “provably” correct is an over claim and in my view this should be corrected.\n\nMy last concern is not so much with what the authors have presented, just in the fact that the limitation is not clearly stated. When using statistical guarantees such as those given under the PAC framework, the iid assumption is almost always necessary. Yet, it can be limiting in both the case of planning and image classification, especially when we are considering safety-critical applications. In such applications, one often considers worst-case scenarios and in these cases the iid assumption usually does not hold. Thus, the PAC guarantees in this paper would seemingly be invalidated. For example, adversarial examples may be out of the support of the data distribution, but are still valid inputs. In the presence of adversarial examples the uncertainty guarantees presented here are rendered void. Similarly, there is often concept drift in RL and control problems. Ultimately, I don’t think this is only a minor mark against the work, and one that can be overlooked given that such cases are at least clearly stated as limitations of the approach.\n\n\nPost-Rebuttal Comment: \n\nI would like to thank the authors for thoughtfully answering my concerns and questions. I think the small modifications made in response to my comments have made the paper much easier to understand and I think the work is well presented and positioned. Ultimately, I have increased my score to Accept on the basis that I no longer have any major criticism of the work. I do hope the authors can make a more prominent note about appendix F1 in the main text as I think it is an interesting and important thing to highlight for those who may be skeptical. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a method for constructing PAC confidence scores for pre-trained deep learning classifiers. The reviewers were all positive about the paper.

Pros:
- Has provable guarantees on the reliability of the prediction. Such guarantees are quite desirable in practice.
- The problem of neural network uncertainty is important and timely problem, especially in safety-critical applications.
- The method is simple and well-motivated.
- Strong empirical performance.
- Interesting applications to fast DNN inference and safe planning.

Cons:
- Lack of generalization guarantees-- the guarantees in the paper only hold on the training set; but in practice, performance in test is what's important.
- Only a handful of baselines tested against, most of which (if not all) were naive.
Decision: Accept (Poster)