Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

The 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.

Pros:
+ Paper is well written
+ Important and timely problem, motivating arguments are well constructed
+ Paper appears to be mathematically sound though I did not check all the proofs in the appendix.

Cons
+ 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. 

+ 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.

+ 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.

+ 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).

Overall, 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. 

== Post rebuttal update ==

See 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.
review_title: Method to provide prediction guarantees of DNNs, but some crucial experimental results are missing.

final_score: rating: 7: Good paper, accept
review_content: 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. 

Accounting 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.

One 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. 

Another 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. 

The 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.

My 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.


Post-Rebuttal Comment: 

I 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. 
review_title: Certainly interesting, but perhaps needs to address limitations more clearly

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

I’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.

Strong points: 
-	The 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.
-	 This approach is a simple but good idea, seems grounded in a good motivation and the explored use cases are informative and interesting. 
-	Experimentally, 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

Weak points + Clarifications:
-	I 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
-	With 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
-	I would like to see more explanation of the proofs in the appendix, right now they are a little too compact for me
-	Experimental 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.
-	In 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.
-	A 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
-	Line 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?
-	Is 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

Other feedback:
-	- 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
-	-p2: “a naively trained DNN is not reliable” what does reliable mean here?
-	-above eq 2, should this be \kappa_x ?
-	-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)
-	-Is there a reason why these intervals should be defined as continuous rather than possibly a disjoint set?
-	-should make it clearer from the start that this is defined for post-hoc classifiers, you’re not learning these intervals directly
-	Eq 4 – the bold theta-hat here is different from the one defined in the line above
-	Need more explanation on “The following expression is equivalent due to the relationship between the Binomial and Beta distributions” p. 4
-	In the definition of C-hat, you’re overloading x on the right side of the given sign. Can you use x’ or something?
-	In the “important case” below Thm 1, can you clarify – this is the mean right?
-	Problem formulation in Fast DNN Inference: should the \hat{y}_i be \hat{y}_m? I feel like i is not scoped here
-	You define d_m below the problem formulation but it isn’t in the formulation itself.
-	Top 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
-	Should define more carefully what the “composed classifier” refers to
-	Clarify 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
-	Bottom of p6: what is Z’? Not sure what Z is – is it ordered pairs? Why is the second element always 1?
-	P13: 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
-	Also please add comments about the appendix figures? I have no idea what they are
 

review_title: Good idea, good motivation/use cases, needs some clarification + cleaning up

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)