Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper aims at developing a better understanding of generalization error for increasingly prevalent non-convex learning problems. For many such problems, the existing generalization bounds in the statistical learning theory literature are not very informative. To address these issues, the paper explores algorithm-specific generalization bounds,  especially focusing on various types of noisy gradient methods.

The paper employs a framework that combines uniform stability and PAC-Bayesian theory to obtain generalization bound for the noisy gradient methods. For gradient Langevin dynamic (GLD) and stochastic gradient Langevin dynamics (SGLD), using this Bayes-Stability framework, the paper obtains a generalization bound on the expected generalization error that scales with the expected empirical squared gradient norm. As argued in the paper, this provides an improvement over the existing bounds in the literature. Furthermore, this bound enables the treatment of the setting with noisy labels. For this setting the expected empirical squared gradient norm along the optimization path is higher, leading to worse generalization bound. 

The paper then extends their results to the setting where an $\ell_2$ regularization is added to the non-convex objective. By using a new Log-Sobolev inequality for the parameter distribution at time t, the paper obtains new generalization bounds for continuous Langevin dynamic (CLD). These bounds subsequently provide bounds for GLD as well.

The paper demonstrates the utility of their generalization bound via empirical evaluation on MNIST and CIFAR dataset. The obtained generalization bounds are informative as they appear to capture the trend in the generalization error. 

Overall, the paper is very well written with a clear comparison with the existing generalization bounds. The results in the paper are interesting and novel. That said, the discussion in the introduction and abstract appears a bit misleading as it gives the impression that this is the first paper that combines the ideas from stability and PAC-Bayesian theory to obtain generalization bounds. This is not the case, e.g. see [1].

As noted by the authors, some of the bounds obtained in this paper share similarities with one of the bounds in Mou et al.  as all these bounds contain the expected empirical squared gradient norm. The bound in Mou et al. holds with high probability and decays as $O(1/\sqrt{n})$, whereas the bounds in this paper are on expected generalization error and decay as $O(1/n)$. Could authors comment on extending their results to hold with high probability and how it would affect their bounds?

[1] Rivasplata et al., PAC-Bayes bounds for stable algorithms with instance-dependent priors.


----------------------- Post author response -------------

Thank you for addressing my comments. I have decided to keep my original score unchanged.
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: In this paper, the authors provide new generalization analysis of (stochastic) gradient langevin dynamics in a nonconvex learning setting. The results are largely based on and improves the analysis in Mou et al. (2018). In more details,  Theorem 11 improves the corresponding generalization bound in Mou et al. (2018) by replacing the uniform Lipschitz constant by the expected empirical gradient norm, which can be smaller than the Lipschitz constant. The authors also argue this can distinguish normal data from randomly labelled data with experiments. The authors further studied the setting with an l_2 regularizer and derived improved result applicable to the case with infinite number of iterations, in which case the results in Mou et al. (2018) can diverge. These results are derived by a new bayes-stability method.

A drawback is that the results are only applicable to gradient methods in Section 4, i.e., using all examples in the gradient calculation. It would be interesting to see how the generalization bound would be for the stochastic counterparts.

The authors assume \lambda>1/2 in deriving (8). In practice, the regularization parameter should be set to be small enough to achieve a small test error. Therefore, eq (8) may not be quite interesting.

----------------------
After rebuttal:

I have read the authors' response. I would like to keep my original score.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper studies the generalization error bounds of stochastic gradient Langevin dynamics. The convexity of the loss function is not assumed. The author proposed "Bayes-stability" to derive generalization bound while taking the randomness of the algorithm into account. The generalization bound proposed in this paper applies to some existing problem setups. Also, the authors proposed the generalization bound of the continuous Langevin dynamics.

This is an interesting paper. Overall, the readability is high. The Bayes-stability is a significant contribution of this paper, and the theoretical analysis of the SGLD with non-Gaussian noise distribution will have a practical impact. 

Some comments below:
- What is the function f of f(w,0)=0 above the equation (5)? Besides, the role of zero data point, i.e., f(w,0)=0, was not very clear. 
- In the numerical results (b) and (c) of Figure 1, the scale in the y-axis was very different. What made the generalization bound so loose? 
- In this paper, the developed theory was a general-purpose methodology. For deep neural networks, however, is there a meaningful insight obtained from the method developed in this paper?

review_title: Official Blind Review #2

Meta-review: The authors provide bounds on the expected generalization error for noisy gradient methods (such as SGLD). They do so using the information theoretic framework initiated by Russo and Zou, where the expected generalization error is controlled by the mutual information between the weights and the training data. The work builds on the approach pioneered by Pensia, Jog, and Loh, who proposed to bound the mutual information for noisy gradient methods in a step wise fashion.

The main innovation of this work is that they do not implicitly condition on the minibatch sequence when bounding the mutual information. Instead, this uncertainty manifests as a mixture of gaussians. Essentially they avoid the looseness implied by an application of Jensen's inequality that they have shown was unnecessary.

I think this is an interesting contribution and worth publishing. It contributes to a rapidly progressing literature on generalization bounds for SGLD that are becoming increasingly tight.

I have one strong request that I will make of the authors, and I'll be quite disappointed if it is not executed faithfully.

1. The stepsize constraint and its violation in the experimental work is currently buried in the appendix. This fact must be brought into the main paper and made transparent to readers, otherwise it will pervert empirical comparisons and mask progress.

2. In fact, I would like the authors to re-run their experiments in a way that guarantees that the bounds are applicable. One approach is outline by the authors: the Lipschitz constant can be replaced by a max_i bound on the running squared gradient norms, and then gradient clipping can be used to guarantee that the step-size constraint is met.  The authors might compare step sizes, allowing them to use less severe gradient clipping. The point of this exercise is to verify that the learning dynamics don't change when the bound conditions are met. If they change, it may upset the empirical phenomena they are trying to study. If this change does upset the empirical findings, then the authors should present both, and clearly explain that the bound is not strictly speaking known to be valid in one of the cases. It will be a good open problem.





Decision: Accept (Poster)