Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper derives time-independent generalization bounds for (discrete- and continuous- time) SGLD under dissipativity and smoothness assumptions. The main novelty of the new bounds appears to be the fact that they decay to zero as the sample size increases. The authors claim that the theoretical approach is different to prior related works on SGLD as it relies on the framework of uniform stability.
main_review: Before everything, let me say that I am not quite familiar with this line of work on analyzing SGLD in non-convex settings. Thus, even though I have not found a technical issue in the proof sketch in the main body, I cannot guarantee correctness of the all the proofs. 

In general, the paper is well written with only a few typos. Main results and accompanying assumptions are clearly stated. Also, comparison to related literature is thorough and seems satisfactory, although at certain places it is mostly targeting the expert reader rather than the general Neurips audience.

I understand from the presentation that the results are novel and the technique differs from previous most closely related works. In particular, it is claimed that the authors are the first to bring the contraction property of Langevin dynamics in Wasserstein distance from the optimization/sampling literature to generalization analysis. 

However, I am not convinced about the consequences of the new bounds. What do we learn from them about SGLD behavior (that is perhaps surprising or new)? Are there any implications ---even at a high-level--- about SGD schemes used in practice of non-convex optimization? Does it say something about how to choose the learning parameter? Or under what conditions on loss and data is generalization good?

I would like to see more such discussion and insights on the bounds that would also benefit the broader Neurips crowd. 

Other questions:
1. Why are *time-independent* bounds desirable? Wouldn't it be better that they depend on time so that they are informative about the algorithm's evolution over time. This seems to not be explained in the paper.

2. Lines 84-85: How do your assumptions on the learning rate relate to practical choices?

3. Equation end of page 4: Why is the weight-decay in the form of \ell_2, rather than \ell_2^2 norm? Also, is the weight decay needed here for the analysis?
limitations_and_societal_impact: I would like to see more discussion on the consequences of the new bounds in the practice of non-convex optimization. See above.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proves generalization bounds for SGLD under dissipativity and smoothness assumptions. A nice feature of these bounds is that they are "time-independent" and uniformly hold across all iterations. 
main_review: *Main Comments*
- The paper requires a more detailed comparison with previous work and a better interpretation/justification for the bounds (see below). 
- Although the "time-independent" bounds are elegant, and the analysis is novel, I do not understand the utility of these bounds even in theoretically understanding the fundamental dependencies on the dimension, batch-size or the step-size in the discrete setting. In these terms, the paper needs to be better motivated for the machine learning audience. 

*Details*
- In Theorem 3.1, the constants $C_1, C_2, C_3$ depend exponentially on the $M, L, \beta, \lambda$. Is there a lower bound that justifies this bad dependence? 
- In this theorem, please explain the effect of the regularization - how does it help the generalization (does the bound capture the difference between the regularized case, and when $\lambda = 0$)? SImilarly, what is the effect of the batch-size $k$ (do we expect better generalization bounds for smaller batch-sizes)? What is the intuition behind the $\eta \geq C_1 \frac{k}{n}$ condition needed in the theorem?
- It would be helpful to compare Theorem 3.1 to the bounds obtained in the previous work, for example, [22]
- Similarly, for Theorem 4.1, please compare the obtained bounds to the previous work. And are there corresponding lower bounds to explain the dependence on $n$, and the exponential dependence on the constants? It is unclear to me which dependencies are fundamental vs those that are limitations of the analysis technique. 
- Comparing the bounds in Theorems 3.1 and 4.1, with the Lipschitz assumption, the bounds for the discrete case are better in $n$, but suffer a dimension dependence. For Thm 4.1, the discrete case bounds have worse dependence on $n$ which makes sense, but they do not have a dimension dependence. What is the reasoning behind this?
-  



limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proves generalization bounds for stochastic gradient Langevin dynamics (SGLD) for nonconvex functions. Previous bounds for SGLD in similar settings typically goes to infinity as time or the number of steps increases. This work gives bounds that are independent of time, and also decreases to 0 as the sample size $n$ grows.

Similar to previous bounds, the authors prove that SGLD is uniformly stable, which is known to imply good generalization. The proofs of stability proceed by starting with the continuous version of the algorithm, and then apply discretization techniques to get guarantees for the discrete-time SGLD. This discretization leads to a slower rate: the bounds are $O(1/n)$ vs $O(\sqrt{d/n})$ for Lipschitz loss functions plus weight decay, and $O(1/n^{1/3})$ vs $O(1/n^{1/6})$ for the full dissipative case without the Lipschitz-ness assumption.

For Lipschitz loss functions, it is sufficient to control the 1-Wasserstein distance ($W_1$) between the distributions induced by two neighbouring datasets. The nontrivial step is Lemma 3.4, which shows that conditioning that the differing data point, $n$, is not in the minibatch, some proxy for $W_1$, $W_g$, actually gets contracted due to the regularization term. Then, as long as the minibatch size is relatively small, the overall distance also gets shrinked. This leads to the time-independent bound on stability.

The proof becomes more challenging without the Lipschitz-ness assumption, since controlling $W_1$ alone does not guarantee stability. The authors show that controlling $W_2$ instead would work, though the contraction proof becomes more involved.
main_review: I found the paper very well-written, as it includes sufficient motivation and background for the problem, and the main paper contains an appropriate amount of technical details to allow the readers to understand the general proof strategy.

I have two questions:
- Theorem 3.1: The precondition requires the minibatch size, $k$, to be relatively small to the dataset size $n$. In particular, the theorem does not seem to hold for the full gradient setting $k = n$, whereas the result of Li et al. [16] (only) holds for this setting. Some discussion about this distinction could be helpful.
- Line 298: Is $\mathbb{E}\|A(S)\|^2 \le s^2$ an additional assumption for Theorem 4.1 to hold (instead of something that can be proven)? If so, it should also appear in the theorem statement.

The analyses follow a similar roadmap to those of previous stability bounds, though a few new tools (like considering both $W_1$, $W_2$ and their proxies under different settings) are needed to establish the required contraction phenomena and time-independent bounds. My only reservation is that the applicability of the results to actual ML settings, since they either require $d \ll n$ (which is not true for overparametrized models) or the dissipativity condition which is too strong to hold for real-world loss functions. That said, the current paper already contains interesting new results to a problem of much recent attention, so I recommend accept.

===Added After Author Response===

I have read the authors' response, and would like to thank the authors for answering the questions. My overall evaluation of the paper stays positive.
limitations_and_societal_impact: Adequately addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors investigate the stability of stochastic gradient Langevin dynamics (SGLD) with varying data sets. They prove a time-independent stability bound for SGLD in non-convex settings. And their analysis can also be used to analyze other variants of SGLD.

More specifically, the reviewer summarizes their contribution as follows: In this paper, they bound the generalization error to show the stability of SGLD. As claimed by the authors, unlike existing bounds for SGLD in non-convex setting, their bound is time-independent and decays to zero as data size increases.

main_review: Quality, significance: Overall, the reviewer thinks this is a good paper.  They give a time-independent bound for generalization error in non-convex setting. There haven't been any results like this before. (This is claimed by the author, in fact, the reviewer is not familiar with the reference in this area.) The reviewer thinks this is an interesting and reasonable improvement. 

Clarity: On the whole, the review thinks the organization of this paper is clear. But there are still some misleading parts, the review will mention them in "Limitations". 

Originality:  The review thinks this paper is novel enough to be published. The reviewer has done some research in Langevin dynamics before. So the reviewer thinks that the idea in this paper is not very surprising and creative. But it's good that the author can combine different results together to bound the generalization error. 
limitations_and_societal_impact: There are several limitations and concerns that the reviewer wants to mention:
1. The authors mention they require the learning rate to be sufficiently large relative to n. This is counter-intuitive. The reviewer thinks if \eta is small enough, then the whole system will converge to an SDE. And it's often easier to study the stability of SDE. Can the authors give more comments on this?
2. In Theorem 3.1 and 4.1, the authors give an equal requirement for time step $\eta$ in the discretization case. This seems too strict. Is it possible to give a looser requirement for $\eta$? 
3. The authors need a weight term in their result, is this purely technical? 
4. The reviewer quickly went through the proof of Proposition 4.2 (Appendix E.1). The reviewer is curious about how the authors get the second inequality in (18).  It seems the authors use the contraction property of Langevin dynamics (Lemma 3.4). But the assumptions of Lemma 3.4 are no longer true in Section 4. The reviewer might miss something.
5. Although the authors give an improved result, the paper lacks applications. Is it possible to give some applications?

There are some structural problems and typos that the reviewer wants to mention:
1. The authors put the definition of $\bar{F}_S$ at the beginning of Section 3. This is weird since this definition is also used in Section 4. 
2. In Section 4, $m$ is abused. It is used for both dissipative constant and iteration steps.
3. There are a lot of parameters in this paper. The authors might recall the origin of some parameters when they use them. One example is $\lambda$ in Theorem 3.1 and 4.1. 
4. When the authors mention continuous-time algorithm or discrete-time algorithm, the authors can also cite the equations. Then it will be more clear to readers.
review_title: null

Meta-review: The paper has been received with mixed impressions. I mostly agree with the bottom-line of the reviews: the paper does introduce novel results and techniques to the line of work on generalization of SGLD, and there should be sufficient interest at NeurIPS for such a contribution; yet on the other hand, it is unclear how significant are the actual bounds derived, and the paper does not provide ample discussion/comparison around this.

As some of the reviews alluded to, the significance of the dimension-dependant bounds is questionable (under the assumptions the paper makes, $\sqrt{d/n}$-type bounds can be obtained, independently of the algorithm, from generic uniform-convergence arguments; the authors response to this point is unconvincing).  While the dimension-independent bounds (Theorem 4.1) seem more compelling, for truly appreciating them I would have liked to see a more nuanced discussion of their relation to existing bounds, as well as a more careful analysis of their precise dependence on the problem parameters.

All considered, my decision is to accept the paper - but I urge the authors to carefully address the primary concerns raised in the discussion for the final version and carefully clarify their contribution and its relation to existing generalization bounds.

Decision: Accept (Poster)