We propose an algorithm combining calibrated prediction and generalization bounds from learning theory to construct confidence sets for deep neural networks with PAC guarantees-i.e., the confidence set for a given input contains the true label with high probability. We demonstrate how our approach can be used to construct PAC confidence sets on ResNet for ImageNet, and on a dynamics model the half-cheetah reinforcement learning problem.
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.