Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper presents novel and tighter information-theoretic upper bounds for the generalization error of machine learning models, such as neural networks, trained with SGD. Following the same construction of the auxiliary weight process in Neu (2021), the upper bounds proposed in this paper improve upon Neu (2021) in two ways. One improvement is mainly due to removing an unnecessary term in the bound of Neu (2021), which the author refers to as “local gradient sensitivity”, by invoking the HWI inequality (Raginsky & Sason, 2018). Additionally, the improvement also benefits from replacing a sample-level mutual information term in Neu (2021) with an individual sample mutual information term, exploiting a recent result of Bu et al. (2020). The bounds obtained here decompose into two terms, one measuring the impact of training trajectories (“the trajectory term”) and the other measuring the impact of the flatness of the found solution (“the flatness term”).

The authors also apply these bounds to analyze the generalization behavior of linear and two-layer ReLU networks. Experimental studies based on these bounds provide some insights into the SGD training of neural networks. Some simple regularization schemes, including dynamical gradient clipping and Gaussian model perturbation, are proposed, which are shown to perform comparably to the current state of the art.

main_review: Two comments:
1.	The introduction of Wasserstein distance in the main body of the paper seems to be redundant, as what is really used in the proof is the eq (3) in the appendix, which is only related to squared error between X and Y. A more concise way to present the result could be put eq (3) in the main body of the paper and discuss its connection to Wasserstein distance and HWI inequality in the appendix.
2.	In evaluating the bounds in Figures 2 and 3, how to compute the sub-Gaussian parameter R? If I understand correctly, the loss function for MLP and AlexNet should be cross-entropy, which is not bounded. Moreover, can you prove that they are subgaussian?

Minor comments:
1.	The organization of section 3 can be improved. Currently, the statement of the main theorem, discussion, sketch of proof, and comparison are stuck together.
2.	Plots in Figure 3 have two different y-axes, which is hard for me to compare the true generalization gap and the bound. Can you somehow calibrate these plots?

summary_of_the_review: This is a great paper that refines the information-theoretical analysis of the generalization behavior of SGD using the HWI inequality and the ISMI bound.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper derives an improved stability-based generalization bound for SGD upon Neu et. al.’s work. In particular, they drop a term called local gradient sensitivity, leading to significantly tighter bound in practical models. Based on this generalization bound, they study both linear model and two layer ReLU neural networks. During their analysis, they obtain several interesting observations, which is consistent to the previous ones. Finally, based on their bound, they propose a new training scheme, named Gaussian model perturbation, having good performance on popular datasets.
main_review: This paper is solid and well-structured. It has a very clear introduction part, making readers easy to follow their idea. On the other hand, compared to Neu et. al., the bound derived in this paper is much tighter (see figure 1), and the technique to derive this is very interesting. However, there do exist some small issues, which is listed as below:
1. The main concern comes from the novelty. The author also admitted that their bounds are not new compared with the previous result. On the other hand, their application for linear model, and two layer ReLU network is not convincing enough. For example, they author claims that the bound might be independent with the model complexity in the generalization bound due to the fact that the deactivated neurons do not contribute to the bound. However, it is not clear that how many neurons are activated from this bound, which means that this bound itself is not useful. On the other hand, the authors argue that their bound decays with the increase of the model size. This is not fair since they only run the simulation for different widths and filters (Figure 3a, b). It would be great if they can provide experiments for the depth.
2. Some arguments are provided without any explanation. For example, in page 5, the last second paragraph of Theorem 2, the author mentioned that “This justifies the construction of the auxiliary weight process”. It is a little confused for me that based on the previous description, without the auxiliary weight process the bound will include an additional $log(n)$ factor, which is not a big problem to me. Another example, in the Experimental Study section, author said that “replace the labels of ε fraction of the training and testing instances with random labels”. Is the label in testing instances also replaced by the random labels?  Moreover, in the Dynamic Gradient Clipping section, author said that “i.e., the model is expected to have entered the “memorization” regime”. It is quite confusing for me that why the gradient norm is large than the gradient norm K steps earlier can lead to this argument.
summary_of_the_review: This paper is good and well-structured. However, its novelty is not very strong and there exists some confusing arguments.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposed a new generalization bound which is based on the recent construction by Neu (2021). The authors made further assumptions on the randomness of the batch sequence, and improved the results by Neu by achieving tighter bounds by tuning the trajectory term. It is verified empirically, and the flatness term gives a regularization technique for better classification on VGG16 on MNIST.

main_review: This paper is based on (Neu 2021). The authors clearly presented the technical increment, and the empirical improvements. A strength in this paper is that the proposed generalization bound yields a simple practical regularization technique, which can improve classification with VGG16. This is some novel bits as compared to (Neu 2021), which is mostly theoretical.

Despite a few weakness (see below, for the authors to work on a revision), I tend to vote for acceptance, subject to the authors' rebuttal and the reviewers' discussion.

First, this paper largely requires the settings of a very recent work. However, the significance of (Neu, 2021) is not clearly written. Why this
recently published results are such a foundational work to build upon? It is meaningful to compare against another, more well-known, bound. For example, in the figure 1, there can be a third bound, comparing with the sum of the trajectory term and the flatness term.

"let $\xi$ govern the randomness in the sequence": this paragraph explain a main assumption of the results, and is informal. There are two factors: the way that the samples are split, and the way the batches are ordered. It not clear on what is random and what is fixed.

The discussion after theorem 1. There is an inconsistency here. Do $\Psi(W_t)$ in Lemma 3 and $\Phi(W_t)$ here refer to the same thing?
The bounds in Lemma 3 and Theorem 1 should be explained in more detail. As the meaning of those two terms, and which one is the trajectory/flatness term.

Overall, the writing can be better polished to explain the background and provide intuitions.

**Minor comments:**

Introduction: "Neu (2021) presents an information- theoretic analysis" extra space before theoretic

P2
"The bounds we obtain decompose into two terms"
-> "The bounds we obtained can be decomposed into two terms"

Theorem 4: the equation is too wide

Table 1: add some margin between the table and the surrounding text 

P3: is the KL divergence or cross entropy sub-Gaussian?

Lemma 3: add a remark to compare against lemma 1 and lemma 2

Statements in conclusion. This is not so meaningful without sufficient motivation and discussion.


summary_of_the_review: Pro:
- Novel increments over a recent work on generalization bound
- New regularization based on the flatness term

Con:
- A few glitches in writing
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: summary_of_the_paper: The paper presents a new bound on the generalization error of models trained with stochastic gradient descent. The new bound builds on the work of Neu, but is tighter. Based on the insights obtained from the bounds, the authors propose two approaches to improve generalization. On the one hand, they show that gradient clipping helps preventing overfitting. On the other hand, the authors propose a regularization term that adds Gaussian noise to the network weights (Gaussian model perturbation) and show that this type of regularization performs on par with or even better than other contemporary regularization schemes. Aside from these technical contributions, the authors provide ample insight into the mathematical terms they derive and discuss several phenomena observed during learning. In the outlook, the authors discuss how their bound can be further improved by utilizing the strong data processing inequality.
main_review: The paper is exceptionally well written. The contribution is important not only from a theoretical, but also from a practical perspective, and the insights and hypotheses derived have the potential to bring the field a significant step forward. The authors also cover and connect with the related literature, at least as far as I can tell from my limited knowledge of this field. The explanations after Lemma 5 and Theorem 2 are particularly nice, and so is the discussion of Dynamic Gradient Clipping.

I do have some questions that I would appreciate to have addressed during the discussion period, but these are mostly out of my own curiosity:

- First, from Th. 3 and 4 it becomes clear that the generalization error increases with the number of epochs. This is also seen in Fig. 1. I assume that this is natural for the first few epochs, as initially the model performs equally badly on the training data and on the population. Is this the correct interpretation? However, what is the intuition behind a monotonic increase of the generalization error over epochs? Especially in the linear model, the term |W_t-1|^2 will eventually settle to a constant (if we can assume that training is successful). Does this mean that essentially the bound becomes more and more loose as T increases? Figure 8 suggests so.
- In Figure 7, it seems that the trajectory term and flatness term have different orders of magnitude. This somehow works against your explanation that the two terms behave in opposite ways when it comes to batch size and learning rate. The picture is rather clear when you consider the orders of magnitude.
- Does the second term in (1) really measure flatness? Suppose that w_1 is a very deep local minima, such that \gamma evaluated at s is large for many samples s (e.g., if s is a large enough sample). In this case, we may assume that the flatness term is small, since both \gamma values (at S and S') cancel, despite the fact that w_1 is not flat. What am I missing?
- In Th. 3 and 4, is it still possible to dissect the bound into the product of a Hessian and a gradient dispersion term? If so, please mention that in the text.
- In respect to Figure 4, why is gradient dispersion small at later epochs? I would assume that at a minimum of w, the gradient direction fluctuates more strongly with different samples than it does during initial training (where a strong gradient signal is available). Is this related to the flatness of the minimum, where the gradient magnitude is small for almost all Z? Does, in this sense, also the trajectory term contain some information about flatness?
- In your regularization scheme, why do you not propose regularizing with the magnitude (or some other norm) of L_s(w+\Delta)-L_s(w)?
- How did you obtain the standard deviations (?) in Table 1? How many independent instances did you train?
Furthermore, I have a few editorial comments:
- In some instances, the text could do with a revision (e.g., p1: "in fact broadly apply broadly", p2: "is presented, which the bound is revised", p2: "We also provide an application of our bounds is in analyzing", etc.).
- The distinction between sample-level and instance-level mutual information was not clear to me in the introduction, even though I am familiar with both types of bounds. Have these terms become common?
- The usage of the batch gradient function g is not consistent; e.g., in the definition of \psi, g is evaluated at a single sample Z (if I understood it correctly) and thus coincides with \nabla_w l(w,Z); however, in the definition of V(w) the nabla version is used instead of g.
- The HWI of the HWI inequality could be spelled out completely at least once. I am not familiar with this inequality, and I think it would be good to have a name to it.
- Fig. 2 is too small to read.
- In Fig. 3, I suggest to use the same axes for both the gap and the bound. Even though the results may not look as impressive, it would be good to show a fair comparison.


I nevertheless have a few
summary_of_the_review: An excellent paper of high theoretical and practical relevance. Very well written, with many interesting insights.
review_title: null

Meta-review: This paper offers a refinement of the information-theoretic characterization of the generalization of models obtained via SGD. This is assessed on some basic neural architectures and inspires the use of new regularizers. Overall, even though the perspective of this paper is not novel, the presented results appear to be clearer and tighter than prior instances of the same ideas. This was appreciated by most reviewers. The few clarity and organization concerns that were raised by the reviewers were adequately addressed by the authors. Overall, the paper deserves to be shared with the community.
Decision: Accept (Poster)