Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary:  The authors study the generalization properties of stochastic gradient Langevin dynamics (SGLD),  using
results about Gaussian channels from info theory. 

The paper derives a generalization bound that involves the variance of the mini batch gradients in various steps. The variance terms are multiplied by a decaying factor (Thm 1) when one is interested in generalization bound for the last iterate, and the factor is (not surprisingly) absent when the function under consideration depends on all the iterates (Thm 2). The results are established by building on the recent results relating generalization bounds for sub-Gaussian loss functions in terms of the mutual information between the parameter iterates and samples used at various iterations (Bu et al. 2020 result), and upper bounding the mutual information in terms of the variance of gradient of the loss function, and the SGLD step size eta, and temperature beta (Lemma 5). The results scale as 1/n with sample size n---which is better than some of the previous results that try to remove the Lip constant dependence. 

The authors present some numerical experiments that demonstrate that their generalization bounds correlate well with generalization gaps observed with small versions of MNIST and CIFAR 10 datasets (5k training examples): (a) with the amount of corrupted labels---increasing corruption increases the generalization error, (b) the width of the network---increasing width decreases the generalization. Their bounds (Table 1) correlate with generalization bounds better compared with Negrea et al. 2019 results, when one considers various settings across learning rate, width, and depth hyper-parameters.

The paper is very well written and fairly easy to follow---a feature missing in several submissions in recent times. It summarizes some useful results in a reader-friendly way.
main_review: 
I have four major concerns with the current version of the work:

1. The authors say that prior works often characterize the generalization bounds in terms of the Lipschitz constants, and argue that '''such bounds can be potentially loose since the Lipschitz constants may be large and fails to explain some empirical observations (e.g., a network trained using true labels generalizes better than a network trained using corrupted labels as shown in Figure 1)'''--- I find this argument incomplete, especially because prior work by Foster et al. https://arxiv.org/pdf/1706.08498.pdf  (that this work does not cite) try to study phenomenon identical to Figure 1 and they show that Lipschitz based bounds can explain this phenomenon to a certain degree; the constants are large when there are fake labels. In fact, one of the key pieces of numerical evidence for the usefulness of the results in this draft is the same as the evidence in this earlier work---the generalization bounds ``correlate" with the generalization gaps observed in datasets with correct and fake labels. I would like to see a discussion to this end.


2. The authors state '''In contrast, we do not need any assumptions on the learning rate.''' This aspect while on the face seems true, it is unclear to me how the variance bounds in Thm 1 and 2 evolve over time for arbitrary step sizes. Do we not need some condition on eta for the variances to remain stable over time? For large eta, I can see that the q will degenerate to 1, and that we have a factor of sqrt(eta) in Thm 1, but the variance terms will begin to blow up as we increase eta. This leads to a slightly more important question: Some discussion is warranted on what condition on eta and beta is sufficient to ensure that the bounds in Thm 1 and Thm 2 are not vacuous, or increasing with time.

3. While it is heartening to see the bounds having some nice correlations, none of the experiments (I checked the appendix) involved a large sample dataset (the usual 50k for MNIST and CIFAR 10)---is there a reason for that? Also, the authors should add details about the variance of gradients were estimated?

4. The authors discuss related work earlier in the work, but ignore it completely after stating their bounds more formally---a revisit to the key results from prior works and putting their bounds in Thm 1 and Thm 2 would allow me to better appreciate their results in context. Also, see the minor question below.

Minor question (optional)

1. Are there settings under which Lemma 5 is tight? For instance, does the bound in Thm 1 provide a strict improvement over Lemma 3 https://arxiv.org/pdf/1901.04609.pdf for large T?
limitations_and_societal_impact: The authors have not included a discussion on this.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper presents some new results on bounding the generalization error of the SGLD algorithm using the properties of Gaussian channels. For SGLD without sample replacement, strong data processing inequality for Gaussian channel is used to show a time-wise contraction of the upper bound. For the general SGLD with sample replacement, a result that relates the mutual information of Gaussian channel to the input variance is used to obtain a more general upper bound.
Experiments are also performed to show some interesting correlations between the obtained upper bounds and the true generalization error.
main_review: While the results presented in the paper look to be new and the experimental results look interesting, there are some aspects that could be improved.
1. The term "DP SGD" is mentioned several times in the paper without an explicit statement. It looks to be referring to SGD without sample replacement, but it would be better if this can be explicitly stated.
2. For Theorem 1, obtaining a time-decaying (contraction) is good, but there is no further discussion on this factor, e.g. how does the final bound scale as T increases. Even some qualitative discussion on this factor would be useful to assess its significance. 
3. For Theorem 2, it is claimed that the final bound scales in n as O(1/n). However, the actual dependence of the bound on n may not be that simple, because here n = m*b, which means that as n increases, both m and b would increase. It is thus not clear whether the O(1/n) can be maintained as n increases. Also, at least some qualitative discussion on the dependence on n and T would be helpful.
4. For the experimental results, many details are missing. For example, how are the variance terms in the bound (Theorem 2) evaluated?
How are the bounds scaled to match the empirical generalization error? 
How is the correlation between the bound the empirical generalization defined?
It can also be seen that the empirical generalization error in all cases saturates as T increases. Is this predicted by the bound? This is another reason why more discussions on the bounds themselves should be provided. 
limitations_and_societal_impact: The major limitations are the lack of discussions on the obtained bounds and missing details of the experimental results. But I think the paper can be easily improved by addressing these limitations.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper derives upper bounds on the generalization error of SGLD and DP-SGD using an information theoretic analysis. Compared to past work on this problem the authors derive upper bounds that depend on the sum of variance of the gradients along the path, converge at a rate of 1/n, and discount the effect of samples seen early in the training run. 
main_review: As mentioned by the authors, previous papers have used information theoretic tools to obtain generalization bounds that have one or more of the following properties: a) upper bounds that depend on the sum of variance of the gradients along the path or on the expected norm of the gradients, b) converge at a rate of 1/n, and c) discount the effect of samples seen early in the training run; but none of the previous bounds have satisfy all of the properties simultaneously. The authors derive such a bound, and the main technical driving force for their analysis seems to be the use of strong data processing inequalities. While I appreciate this advance, it does seem like a narrow, technical step forward to me in light of the past work on this area, including the paper of Xu and Raginsky, who also previously suggested using strong data processing inequalities to get tighter bounds. Other comments and questions about the paper are listed below:

1. The abstract suggest that SGLD is a widely used optimizer, but the authors do not provide any citations to support this claim. The authors should back up this claim with citations in the text. 
2. Do the bounds of Li et al. (2019) discussed in ln 94 also depend on the sum of the variance of the gradients or on the expected norms of the gradients?
3. Ln. 219 says that DP-SGD is a special instance of SGLD algorithm. I am not sure why this is the case, since the gradients are clipped in the DP-SGD algorithm (see Algorithm 1, Abadi et al. (2016)). How does the theory handle this clipping? Relatedly, do Theorems 1 and 2, and Corollary 1 apply to the DP-SGD algorithm? The authors should clarify this.
4. In ln. 246, if I understand correctly, the sharpness studied Jiang et al. 2019 refers to the robustness of the network's output when the weights are perturbed slightly. Why does the variance of the gradient relate to the sharpness studied there?
5. Do the authors expect a sharper version of Theorem 2 to hold if the average iterate is returned instead of an arbitrary function of the weights.
6. Regarding the experiments, in Table 1, I am not quite sure why the authors only compare their generalization bounds to that of Negrea et al. The authors say that the previous papers Mou et al., Pensia et al. ,... did not perform a empirical study, but Table 1 only compares the correlation between the actual generalization performance of a network and the theoretical bound. I believe the authors should add these comparisons to their empirical study. 



============== Post author rebuttal =============
Thank you for carefully answering my questions. I have raised my score as a result.
limitations_and_societal_impact: I do not think there is any potential negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper gives a generalization bound for the stochastic gradient Langevin dynamics (SGLD) algorithm using tools from information theory (notably, the SDPI for Gaussian channels and the HWI inequality). The bound is subsequently used to analyze generalization of differentially private SGD (DP-SGD). Supporting experiments on the CIFAR-10 dataset show that the bound is more favorably correlated with the generalization error than prior work by Negrea et al. (2019).

main_review: *** Post-rebuttal ***

I am increasing my score to 6 based on the authors' response.

***

Generalization bounds for SGLD have recently attracted a lot of attention in the NeurIPS community and the contribution is timely. 

Originality:

-- The analysis primarily builds on the works of Xu and Raginsky (2017), and Pensia et al. (2018) that bound the expected generalization error in terms of the mutual information (MI) between the input training data and the output hypothesis under a sub-Gaussian loss. Since the date generating distribution is unknown, estimating the mutual information is intractable. This issue is addressed by upper-bounding the MI. The bounds thus obtained (for DP-SGD) are expressed as a sum of errors associated with each training iteration and features the variance of the gradients (from upper bounding the MI + chain rule of MI) and a time-decaying factor (by way of Gaussian SDPI) that weighs the contributions from early iterations of SGLD. The intuition for the time-decaying factor is natural as it factors in the cumulative effect of noise. 

-- In terms of originality, application of the SDPI and HWI inequality for Gaussians appear novel.  


Issues:

-- It appears that there is a version of this work (arXiv:2102.02976v1, dated Feb 5th, 2021) with a different title ``"Learning While Dissipating Information: Understanding the Generalization Capability of SGLD."  I will recommend that the authors cite this work. Also a question: Theorem 1 in the arXiv version apparently gives a bound for SGLD (sampling with replacement) that features the time-decay factor. I believe the corresponding bound in the present submission is Theorem 2, which does NOT feature the time-decay factor. If the latter is a correction of sorts for the one in the arXiv version, then this should be stated clearly with citation. 

-- I can understand that the DP-SGD is a special case of SGLD, but the motivation for selecting this specific algorithm is not very clear. Ideally, the general version of the algorithm (SGLD, Theorem 2) should be stated before stating a special case (DP-SGD, Theorem 1). However, the order is reversed here. I believe this was done to accentuate the role of the time-decay factor. In any case, the organization and overall presentation of the paper can be significantly improved.


Suggestion (minor):

-- The isotropic noise structure of SGLD is integral to the proof here and I am inclined to believe that the technique cannot be applied to SGD. Nonetheless, a discussion on if and how any of the proposed techniques can be used to analyze SGD might benefit the potential reader. 
limitations_and_societal_impact: The authors claim that that is no direct negative societal impact of their work and I agree.
review_title: null

Meta-review: The paper provides new generalization guarantees for SGLD, which incorporate the gradient variance, giving a more adaptive flavor. The paper also considers differentially private stochastic optimization as an application of their results. 

We had quite a bit of discussion on this paper and we thank the authors for providing the reviewers with additional details, which helped to clear up some confusion. After deliberation, we agreed that the paper should be accepted. 

Please do carefully go over the reviews and discussion and incorporate any suggestions into the final manuscript.
Decision: Accept (Poster)