Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies the PAC generalization bound and relaxes the uniform bounds assumptions in literature by the on-average bounded loss and on-average bounded gradient norm assumption. Under this relaxed assumption, the paper derives new generalization bound related with the loss-gradient norm. The paper verified its effect empirically.

strengths_and_weaknesses: Strengths:

The paper relaxed an unrealistic assumption in previous PAC generalization bound. The relaxation is natural and interesting, providing a fine-grained view to improve existing results. The average gradient norm has been studied to reflect the generalization of the algorithm [1], and this PAC bound gives more theoretical evidence on the importance of the average gradient norm.

[1] Understanding generalization error of SGD in nonconvex optimization

It uses clean mathematical language and explains the caveats clearly. Overall the presentation is very good.

Weakness:

The assumptions on the data are strong (x Gaussian or mixture Gaussian, y label balance) in Section 3's entropy bound. It is not clear how critical these assumptions are in terms of deriving a meaningful bound.

 In the generalization bound, it considers the complexity term and ignores the KL term and empirical loss term. Only optimizing the complexity term may lead to some undesired behavior: "one may achieve a fast rate bound by forcing the gradient-norm to vanish rapidly, practical experience shows that vanishing gradients prevent the deep net from fitting the model". This hides the influence of the empirical loss and the KL divergence part.   It would be great if they can be jointly studied, i.e., trade-off the noise variance and lambda.

Though non vacuous, the paper does not demonstrate the power of such generalization bound. It will be much more interesting if we can see how the generalization bound / numerically computed generalization gap changes according to the model architecture, data distribution, or label balance.

questions: The paper should be clearer about the assumption on the data, i.e., how to understand these assumptions and derived bound therein when the real data do not satisfy these assumptions.
limitations: See the later two parts of the weakness.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors present a new PAC-Bayesian generalization bound in connections with the gradient norm of loss function with respect to the input space. The authors start from the bound presented in Alquier 2016, and compared to the assumption where loss is uniformly bounded, the authors try to give the complexity term a new bound with a more general assumption, i.e. on-average bounded loss and gradient norm. With such assumptions, this new bounds regarding both linear and non-linear models are proved via the Herbst theorem and Log-Sobolev inequalities. Finally, the authors show some empirical study to show the effectiveness of their frame, which can provide tighter generalization bound compared to conventional techniques.

strengths_and_weaknesses: &nbsp;
### **Strengths**

1. This paper is clear and well written. 
2. This paper provides a new generalization bound with a more relaxing assumption. In my opinion, theoretical insights of the generalization bound are valuable for enriching our understanding towards the neural networks. It is encouraged to contribute to this topic. The authors prove it under the assumptions to the on-average bounded loss and gradient norm, which, to my understanding, makes it closer to our practical situations, although the assumption here has not been significantly improved compared to that in Alquier 2016 (i.e. from uniformly bounded loss assumption to on-average bounded loss assumption). 
3. It is interesting to see the theoretical connections between the generalization and the gradient norm of loss w.r.t the input space. This may also provide theoretical insights about the model robustness.
4. This paper provides rigorous mathematical proof.

&nbsp;
### **Weaknesses**

1. I think it can be much more better if the authors show the experiments results regarding the connections between the generalization bound, gradient norm and testing performance.
2. From formula 22 and Lemma 3.1 to Lemma 3.3, it seems that the authors exchange the expectation and integral operation. I am somehow worried about whether such exchange is eligible.
2. Formula 8, $Ent[e^{\alpha F]}$ -> $Ent[e^{\alpha F}]$.
3. Formula 23, it seems that the authors are missing the explanation of $d$, which may be $W \in R^{k \times d}$.
questions: I hope the authors can address my concerns in their rebuttal..
limitations: In my opinion, this paper do not involve related issues for its current version.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper extends PAC-Bayes generalization literature by proving new generalization bounds. These bounds require (and depend on) the expected loss (and loss gradient norm) to be bounded, where the expectation is taken over the data distribution. In general, these assumptions on the bound on the loss and gradient have to be valid uniformly over the weight space, or when integrated over the prior on the weights (if computing such a quantity is possible). The bounds were derived for a data distribution that is a mixture of Gaussians. The authors also include an empirical section, measuring how the complexity terms appearing in the bounds change with a parameter lambda that appears in the bounds, as well as the depth of the network.
strengths_and_weaknesses: Overall, it’s a pretty good and interesting paper, and I believe the advancements in PAC-Bayes theory are worth a publication and novel. I like that the authors did not only stick to theory, but also evaluated their bound empirically. However, there are a few issues 
 - with the experiments (i hope the authors will answer my questions, and confirm the correctness of their evaluation of the bounds), 
 - some presentation issues in the theory part that need to be addressed with care to improve clarity, 
 - and also missing references and comparison to prior work, which is the one of the biggest issues for me. 

I am leaning towards accepting the paper with the hope that the issues listed above will be addressed by the authors. 

questions: Related work issues: the literature on information-theoretic approaches to generalization contains several papers that depend on gradient norms, an average deviations from the norms. The paper under submission is obviously related, and thus I believe a deeper comparison is needed. The authors should check a fairly large body of work, such as Negrea et al ‘19, Haghifam et al ‘20, Mou et al. ‘18, Pensia et al. ‘18.

Empirical evaluation / Section 4: 
Section 4 contains a paragraph on verifying assumptions, but there is no mention of the assumption that the data is sampled from a mixture of Gaussians. This is the key assumption used to derive the main result.
There is no plot directly comparing average gradient versus max gradient, which is the key distinction. 
Fig 1 shows how the expected loss and loss gradient vary with sigma (prior variance). It looks like these quantities are reported at a fixed w (the one learned by SGD?). If so, the relevant quantity is the one where w is also random, and sampled from the posterior, and the expectation should be taken over w.
Given the issue with Figure 1, I would also like the authors to explicitly confirm that Table 1 reports average error of randomized classifiers.

When discussing subgaussianity in Sec 2.1, and assumptions for Herbst theorem in Section 2.2,  the same letter sigma is being used, despite sigma referring to two different quantities (if i understand correctly). I found it a bit confusing at first, and wondered for some time whether 2.2 uses subgaussianity  in any way.

Theorem 2.2 gives a bound on the log moment generating function that essentially looks like a bound for subgaussian random variables, but also has an extra term E[F]. For a subgaussian loss, what would sigma in Eq (5) look like?

It seems like Theorem 2.3 could have been stated for a single draw from a gaussian, given it’s use in the proof of Lemma 3.3.


The proofs for existing results (that are not derived by the authors) are included in the main text, but the proofs for new results are all in the appendix. I think the authors should at least include the outlines in the main text, and, if needed, shorten the other proofs.

Other comments and minor issues:
Notation in theorem 3.4 is unclear: does one need a bound on the loss gradient norm to hold uniformly over y? Or t (so w, and x, i suppose)?
Theorem 3.5 what is the gradient w.r.t.? 
Line 15 “they do not tend to overfit” is not really accurate, depends on the exact definition of overfitting, what loss overfitting is being measured w.r.t., etc. The same holds for ~line 271.
Lines 100, 253 typos
What do the authors mean by “avoid integrating” in line 166?
- line 333 typo, lower case log.
limitations: The authors discuss how their work can be extended. However, there is no explicit discussion of limitations. I think the major one if the assumption on the data distribution (mixture of gaussians). This should be mentioned explicitly in the abstract, as well as discussed under limitations. I personally do not see any societal impact of this work beyond standard impact of theory and better understanding of deep learning, thus for me personally it is not an issue that the authors skipped it.

I believe citations to datasets and architectures used are missing.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper presented a novel PAC-Bayesian generalization error bound that depends on the gradient norm of the loss function. The idea is to use Herbst argument and control the entropy using the appropriate assumption about data and loss functions and their gradient norm. The obtained bound assumes the average of the loss function and its gradient norm. Numerical experiments suggest that the obtained bound can capture the structure of the deep neural networks.
strengths_and_weaknesses: # Strengths
- The motivation of the research is practical and easy to understand.
- As far as I know, using Herbst argument for deriving the generalization error bound seems novel and the assumption of the obtained bound (on average bounded and Lipschitz property of the loss function) is also novel and meaningful.
- The obtained bound naturally includes the multi-class classification, which is practically important. 
- The numerical experiments especially Figure 2, can successfully capture the importance of the depth of neural networks in generalization ability.

# Weaknesses
- I think some assumptions are difficult to verify or strong in practice. I list them below.
- To analyze the entropy, the authors assumed that input data $x$ follows the Gaussian distribution (line 139), which is a very strong assumption in practice.
- The assumption in Lemma 3.3, ``the loss per label is balanced'', for any parameter $w$ is very strong and difficult to understand intuitively.

questions: - Questions related to Weaknesses.
- The assumption in line 139, input data $x$ follows the Gaussian distribution, is very strong. On the other hand, if we relax such an assumption not the input space but the feature or latent space, then it would be moderate and easier to verify. Is such relaxation possible?

- In lines 233 to 237, the assumption in Lemma 3.3 is evaluated by the numerical experiments. Authors claimed that ``The maximum standard deviation across the labels is 0.022, while the mean value is 4.605. Hence, it is evident that this assumption holds in practice", but I cannot how this conclusion is derived. I would like to know more detail about this point.
limitations: The limitations (assumptions) are written clearly. Since this paper proposed a theoretical analysis, it seems there exists no social negative impact.
review_title: null

Meta-review: metareview: This paper presents a generalization bound that strengthens influential earlier bounds in a clear and meaningful way.  They provide support experiments.  The paper is well written.

confidence: Certain
Decision: Accept