Venue: ICLR 2020 Conference

Reviews:

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

final_score: rating: 6: Weak Accept
review_content: The paper proposes an algorithm combining calibrated prediction and generalization to construct confidence sets for deep neural networks with PAC guarantees. 
The main novelty is that existing approaches do not come with PAC guarantees
Following (Platt et al., 1999) and (Guo et al., 2017), the calibration of the learned model is controlled by its temperature. In particular, the proposed approach exploits another (small) training dataset to learn a temperature that gives the best calibration. 
An efficient algorithm for constructing confidence sets that are "small in size" is also proposed. 
The framework is introduced for the classification, regression and reinforcement learning tasks.

I vote for acceptance for the following reasons:
- The paper is well-written, the motivation and comparison to related work is also clear.
- The paper is very solid theoretically and experimentally. A theoretical analysis is provided, and practical implementations are proposed to deal with scalability issues. VC generalization bounds are studied in detail.

Concerning experiments that are not about Reinforcement learning, the paper proposes different strategies to learn a ResNet architecture for ImageNet. One might argue that the different results might be only valid for the chosen architecture and dataset. 
Although the study for that architecture and (large scale) dataset is exhaustive, it might be interesting to study if the reported results are also valid on (smaller?) datasets and other architectures.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: Summary: This paper presents an approach for generating confidence set predictions from deep networks. That is, the smallest set of predictions where the true answer is included in that set. Theory is used to derive an algorithm with PAC-style bounds on the population risk. 


Overall Assessment: I like the core idea of this paper---developing region-based prediction algorithms with theoretical backing by taking advantage of a small calibration dataset and simple models of uncertainty. However, there are significant clarity and evaluation issues that must be addressed before the paper is ready for publication.  In current form, I rate the paper between Weak reject and strong reject overall. 

Strengths: 
+ Nice general direction.
+ New algorithm for confidence set prediction with theoretical guarantees. 
+ Experiments show favourable performance vs a few ablations.

Weaknesses & Questions:  
1. It is unclear to me why the temperature scaling component is needed. It does not actually change the ordering of the probabilities assigned to each class, so from what I can tell all it does is change the optimal T, but not the final performance.
2. The paper presents a bound on the population risk, but the experiments do not include a comparison of the expected worst-case error rates with the empirical error rates achieved on the test set. This should be corroborated. 
3. The  description for the Model-based reinforcement learning subsection is impossible to follow due to ambiguity and lack of detail overall.
3.1. Some specific confusions about this section: Paper overloads f to be both a deterministic transition function, and also a distribution over possible states. It also switches between using x_{t+1} / x_t and x^\prime / x to mean the same thing. The notation used to describe the multi-step setting also seems to use "t" for two different things: the current time-step, and some arbitrary time-step in the past.
3.2. It is unclear what metric is being used to evaluate the state transition models---L2 distance between what? Given that the predictions are not point estimates, I would expect something that takes uncertainties into account.
5. For both sets of experiments (classification and RL), there are no alternative methods used as points of reference. There are a multitude of other approaches incorporating uncertainty into predictions, as mentioned in Section 1. A trivial baseline is to heuristically generates confidence sets by trusting the probabilities produced by the model and building a set out of the classes corresponding the top 1-\epsilon probability mass should be essential. This could be improved by applying difference calibration approaches to make the probabilities more trustworthy. Model ensembles provide another easy baseline. Such simple baselines are a minimum expectation, before even getting to state of the art alternatives.
6. There seem to be no vanilla regression experiment, only the harder-to-interpret RL experiment. EG: Since we already have a vision context: If you are doing facial age estimation , or interest point tracking, could one make a PAC prediction about the true age region/interest point location?
7. Overall the paper introduction misses some explanation on the motivating scenarios where such confidence set predictions are useful. One can perhaps imagine this for vision, but some help connecting the dots to how it could be useful in regression and RL would help. 
8. It is claimed that Theorem 1 provides a "better" bound than the one based on the VC dimension. What is meant by better?

Minor comments:
* There are a couple of small mistakes in the proof of theorem 1. The \tilde{X} and \tilde{Y} in the definition of \tilde{Z}_{val} are in the wrong place. The "sum of k i.i.d. random variables" should be "sum of n i.i.d. random variables".
* In general, the proof is quite hard to follow. At times it was quite unclear how you get from one step to the next, because it relies on something shown several steps early, which is not referenced.
* Notation, in general, is a bit of an issue in this paper. See comments above, but also: switching between \theta and T for the parameter used in the confidence set predictor, some confusion between T and \hat{T}.
* It is unclear how the neural network used in model-based RL predicts a PSD covariance matrix.
* \hat{T} is not defined when it is first referenced (Section 3.3).
* Algorithm 1 appears several pages before it is referenced.

-------------- POST REBUTTAL ------------
I modify my score to 6: Weak accept.
review_title: Official Blind Review #2

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