Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This interesting paper studies the connection between generalization abilities of of SGLD and the covariance structure of its noise term. It first proves that with constraint to guarantee low empirical risk and commonly used data-dependent priors, the optimal noise covariance of SGLD in terms of the bound is similar to the empirical gradient covariance. The paper further proves that if the generalization bound is jointly optimized with respect to both prior and posterior, the optimal noise covariance is the square root of the expected gradient covariance. These facts can be used to further support the belief of the superiority of SGD noise over isotropic noise.
main_review: This paper studies the connection between generalization abilities of of SGLD and the covariance structure of its noise term. It proves that with constraint to guarantee low empirical risk and commonly used data-dependent priors, the optimal noise covariance of SGLD in terms of the bound is similar to the empirical gradient covariance. The paper further proves that if the generalization bound is jointly optimized with respect to both prior and posterior, the optimal noise covariance is the square root of the expected gradient covariance. Overall, the concern of optimization methods with generalization abilties from the viewpoint of noise covariance structure is novel, interesting and important. It is important because these facts can be used to further support the belief of the superiority of SGD noise over isotropic noise, an important theme towards the understanding of implicit regularization of SGD.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: From usual isentropic noise to data-dependent priors, the authors extend the existing information-theoretic analysis of SGLD. Additionally, they identify the optimal choice of prior distribution covariance. Last but not least, the paper includes empirical observations to validate its technical findings.
main_review: I must admit that I am not an expert in this field. Nevertheless, the paper is very well-written, the literature review is extensive, and the technical contributions appear to be solid. Bellow you can find my comments.

- Is there a regularity condition (such as having a full-rank matrix) for the covariance matrix \Sigma_{S, W}^{sd}? 

- How do you compare the value of \tilde \sigma_{i}^{S, W} and \sigma_{i}^{S, W}? Which one is larger, and can we conclude that the condition number of \Sigma_t^\star is larger than the condition number of \Sigma_{S, W}^{sd}?

- Does \Sigma_t^\star converge to a certain matrix as t tends to infinity?
limitations_and_societal_impact:
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of understanding the generalization of the SGLD algorithms using information-theoretic techniques. This line of work initiates by [27],[24], and [13]. The goal in this paper is to "modify" the SGLD algorithms such that it has a good generalization properties and good performance on the training set. Basically, the modification that the authors considered is to make the covariance of the Gaussian noise in the SGLD update to depend on the trajectory. Note that in the usual setting the noise is isotropic. Then, authors claim that controlling the trace of the SGLD ensures we have good performance on training set and good generalization. Then the authors provide a generalization bound which uses reverse KL between posterior and the prior distribution. I think this bound is not true as stated in my review. Since this bound has been used in the paper, I think the authors should comment on the validity of the theorem.
main_review: - The presentation of the paper is not good.

- Why the assumption 1 is a valid assumption? There is no discussion in the paper.

- I think Theorem 2 in the paper is NOT CORRECT. I will provide a counterexample here. Assume that we have a finite hypothesis class $H= \{ h_1,...,h_M \} $. Assume the learner is an "ERM" so after receiving a training set it outputs a single hypothesis that minimizes the empirical error. Assume we have a consistent way to break the ties. For instance we choose the hypothesis with smallest index. Therefore the posterior distribution is $Q^{S}= \delta_{h_{i^\star}}$ where $h_{i^\star}$ is the ERM classifier. Assume based on your generalization bound in Theorem 2, we choose the uniform prior over the set of hypothesis, i.e., $P(h_i)=\frac{1}{M}$. Based on this theorem $KL(P||Q)=\frac{1}{M}\log \frac{1}{M}$. Therefore we obtain   $EGE<\sqrt{\frac{1}{2}\frac{1}{M}\log \frac{1}{M}}$. It implies that when $M\to \infty$, the generalization bound becomes smaller!!!  From the first part of "Understanding machine learning: From theory to algorithms" we know the expected generalization error is upper and lower bounded by $\log(M)$. Therefore this example depicts that this bound can't be true. I also checked the proof and the proof also has error in Lines 584 and 585.  

The main reason is that similar to PAC-Bayesian bounds we can't have upper bound with "revers KL" between the posterior and prior.


As this bound is used all over the paper, I appreciate if the authors comment on how this theorem affects the paper's conclusion. Also if there is a misunderstanding by me, please let me know.
limitations_and_societal_impact: I have some concern on the validity of one of the main results in the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper study the interplay between generalization bound and the covariance of perturbed gradient descent. The authors invoke a recent (information-theoretic) bound for stochastic optimization methods. Then, they optimize the upper bound with respect to trace constraint on the covariance of noise in each step and experimentally show that this optimization may be effective for training neural networks. 
main_review: I could not follow the statement of theorems and theoretical results. Definitely, the paper requires refinement of notations and also writing. 

I can not understand the notations in Propostion1. In equation 4, what is exactly the risk for a joint distribution $Q_T^{S,V_T}$? The input of the risk has to be a parameter, not the joint distribution of a stochastic process. 

I am not sure whether I understood the statement of Proposition 1 and Theorem 1. Suppose that $T=0$, then the starting distribution is the same so the right side of equations 4 and 6 is zero. But the left side is $R_D(W_0) -R_S(W_0)$ which is not necessarily less than zero. Intuitively, if the algorithm is deterministic, still the generalization error is not zero. Should not use an absolute value for the left side of the generalization error? 

The optimality is not defined well. The target objective is optimizing the divergence of test error from the training error under a trace constraint for the covariance of the noise, which is meaningless. The optimal algorithm requires to achieve the lowest level of the test error. Indeed, authors require to minimize $$ E [R_D(W_T)] $$  which I am not sure whether is possible. 

One of the claims in the introduction is that the optimal covariance matrices found in this paper match the covariance of stochastic gradient descent. I saw in experiments there is one result indicating anti-isotropy of the noise of stochastic gradients which is a known fact in the literature. Is there any other result that shows the optimal covariance matrices extracted by the proposed algorithm is similar to the covariance structure of stochastic gradients during training? 


**Post Rebuttal**


I thank the authors for their detailed responses that helped me to understand the results better. Now, I understand Lemma 2 and the role of the trace constraint in optimization. After a more careful study, I decided to increase my score. This paper is rather difficult to follow due to the use of complicated notations and I highly recommend the authors to improve the writing. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies optimization of the information theoretical generalization bounds of Stochastic Gradient Langevin Dynamics (SGLD) with respect to the noise covariance. Here are the main findings:
* When updating rule is fixed and only optimizing noise covariance under the constraint that the trace of the covariance is fixed, the noise covariance of SGLD is similar to the empirical gradient covariance
* When both updating rule and the noise covariance are jointly minimized, the noise covariance of SGLD is the square root of the expected gradient covariance. 
The two results can potentially be used to improve information theoretical generalization bounds obtained in the literature. The theoretical results are validated by some numerical experiments. 

main_review: SGLD is a popular stochastic optimization algorithm used in practical training of neural networks. Its generalization property is an important issue and is worth to study. The present work aims (and manages) to improve information theoretical generalization bounds obtained in the literature (e.g. Refs [24,13]) by optimizing the noise covariance. However, I do have some concerns on the results.
* My major concern is about the usefulness of the information theoretical generalization bounds. From my perspective, the generalization bound in Theorem 2 seems very brutal. The reason is that I would expect the generalization error to decrease or at least not increase with respect to the training time $T$, while the right hand side of Eqn (7) increases linearly in $T$ as it involves the relative entropy between two measures on the whole path space of trajectories. If the upper bound is brutal, then I do not see the point of optimizing the right hand side since it is not likely to improve the actual generalization error.
* Speaking about the information theoretical bound, I would think of a lower bound (rather than upper bound) for the generalization error involving information quantities, such as relative entropy or mutual information. This is because it is the lower bound that reflects the fundamental information limit of a learning algorithm (SGLD in this case). 
* In Figure 2, I do not see why the generalization error could increase along the epoch. Is the figure showing the information theoretical upper bound or the actual generalization error? If it is the former, please specify this in the figure. 
* The improvement of SREGC-SGLD over IS-SGLD seems not convincing in Figure 2.c since all the curves are nearly aligned with each other.

limitations_and_societal_impact: Yes
review_title: null

Meta-review: The paper studies the connection between the generalization ability of SGLD and the covariance structure of its noise term. The reviewers initially had a lot of concerns about the lack of clarity of the paper and some details in the derivation of the proofs. Most of these concerns were addressed by the authors in the rebuttal and some reviewers raised their scores as a result. Overall, the contribution made in the paper is seen as interesting and worthy of acceptance. However, many reviewers, and myself included, think that the writing in some sections of the paper and the clarity are poor. I strongly advise the authors to follow the suggestions made by the reviewers to improve the manuscript for the camera-ready version.
Decision: Accept (Poster)