Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper tackles an important concern when it comes to PAC-Bayes bounds, i.e., the fact that such bounds apply to the risk of a stochastic predictor rather than a deterministic one. The authors propose bounds on a "single draw" of a predictor according to the PAC-Bayesian predictor. 

However, I would like the author to discuss to which extent the derivation of this "single draw'' bound differs from the result of Hellstrõm & Durisi (2020) they refer to. Indeed, the latter is a "slow rate" $O(1/\sqrt{n)}$ bound, while the proposed result is a "fast rate" $O(1/n)$ one. However, such bounds for randomized predictors already exist in the PAC-Bayes literature for randomized predictors. As a matter of fact, the PAC-Bayes theorem of Seeger (2002), involving the KL divergence between two Bernoulli distributions, is tighter than both the slow rate result of Eq. (1) and the fast rate result of Eq. (2); the Seeger's bound achieving fast rate when the empirical loss is zero (see Letarte et al., 2019 (Thm 3), for an explicit connection between Eq (2) and Seeger's bound). 

In other words, I wonder if the proposed "fast rate" bound is a particular case of a general analysis obtainable from a slight generalization of Hellstrõm & Durisi (2020).

The experiments show promising results but would benefit by being extended. Figure 1 shows the bound values according to the training epoch up to 30 epochs. The training and test loss are still decreasing at this point. In order to have the complete picture, it would be important to compare the results for fully trained models. Moreover, I would like to see the bounds values in the overfitting regime, when the training error is close to zero, as the experiments are performed in Dziugate & Roy (2017). Note that the proposed fast rate bounds only converge in this setting.

Finally, a nice addition would be to comment on the possibly to learn a predictor by directly minimizing a single draw bound, as it is frequently done in the PAC-Bayes works (e.g., Dziugate & Roy (2017). 

### Minor comments:
- I do not understand the subscript $i + S_i n$ of $\tilde Z$ (middle of page 3)
- It is strange that the authors cite an unpublished paper (Guedj and Pujol 2019) for the canonical PAC-Bayes bound stated in the early PAC-Bayes works of McAllester.

### References:
Letarte et al., Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks. NeurIPS 2019
Seeger, PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification. JMLR 2002

review_title: Interesting result, but would benefit from a more detailed theoretical and empirical study.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper derives bounds on the test loss under the random-subset setting, which are expressed with conditional information measures, and have fast rates with respect to the sample size n. The derived bounds are compared with the practical performance of deep neural networks (DNNs) trained on the MNIST and Fashion-MNIST data sets.

Although the derived bounds can be somewhat loose practically as it can be larger than those of slow-rates, the paper provides a steady theoretical progress on the evaluation of loss bounds using conditional information measures.

Although the experiments with NNs and practical data sets are interesting, they are a little unsatisfactory for demonstrating the significance of the derived fast-rate bounds.

p.5, main theorem: It would be nicer to explain what novel important proof techniques are required, if any, to derive the fast-rate bounds in Section 3.

p.6, computation of \mu_2: Since NNs have hierarchical structures, computing the average of their weights does not seem so good. I wonder if computed \mu_2 are close to zero and if there is any other possible ways to compute \mu_2.

p.7, experiments on MNISTs: Although the experiments demonstrate that the fast-rate bound can in fact be tighter than the slow-rate bound in practical cases, I wonder if some experiments should be designed with changing the sample size n in order to compare fast and slow rate bounds. 
As the training and test errors reported in Fig. 1 are close to each other, isn’t it better to produce any overfitting situation, even for synthetic data?

review_title: Steady theoretical progress while a little unsatisfactory validation

final_score: rating: 7: Good paper, accept
review_content: This paper extends results of prior work by Steinke and Zakynthinou, by providing generalization bounds in the PAC-Bayesian and single-draw settings that depend on the conditional mutual information. The emphasis in this work is on obtaining fast rates ($1/n$ vs. $1/\sqrt{n}$). The authors also conduct empirical experiments showing how the fast rate bounds they propose can be useful for obtaining non-vacuous generalization bounds in the context of over-parameterized neural networks.

I think Theorem 1 and its corollaries are a nice contribution. The paper is very well written and clear. The authors do an excellent job in explaining the relevant related work, and how their results expand upon the results of earlier work. 

It might be useful if the authors could indicate or explain whether their bounds suggest or motivate improved learning algorithms. For example, how should one choose a prior distribution Q over the hypothesis based on knowledge of the full training examples?


review_title: Review

Meta-review: The paper extends results from the recent work of Steinke and Zakynthinou (SZ) for the test loss of randomized learning algorithms. They provide bounds in the single draw as well as PAC-Bayes setting. The main result is about fast rates the proof of which follows with minor modifications from the corresponding result in SZ. It is unclear to me the contribution over existing work is sufficient to merit acceptance.
Decision: Reject