Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the generalization of iterative noisy learning algorithms. First of all, the authors provide a new generalization bound based on the Hellinger distance. This bound is basically based on the Hellinger distance between the output of the algorithm when one of the points in the training set is replaced with a fresh sample. They they use this bound to provide a generalization error guarantee for a broad class of noisy iterative algorithm which is defined as W_t = W_{t-1} - eta_t, where eta_t conditioned on the past iterated follows an exponential family distribution which for instance include SGLD. For this broad class, they provide a unified generalization bound that includes SGLD and Noisy Sign-SGD. Finally, the authors provide numerical study of their bound for several benchmarks and show that their bound achieves better estimate of generalization error. 
main_review: - Using the generalization bound in Theorem: In proposition 1, the authors provide a generalization bound based on the distributional stability in terms of Hellinger distance. However, in most of the results in the paper they mainly use the upper bound based on KL divergence (Prop. 2). Is that correct?  

- The dependence of the learning rate on the optimization trajectory: In your bound alpha_t depends on the dataset and trajectory. It basically depends on some sort of Lipschitz constant of the loss function. For instance in SGLD, alpha_t depends on the learning rate and inverse temperatures. Therefore, I think it can limit us to use very small learning rates. Also, how did you make sure that this constraint is satisfied in your numerical studies?

- The comparison with Rodríguez-Gálvez et al.: Your bound is very similar to the generalization bound in Haghifam et al'2020. As you mentioned the bound in Haghifam et al'2020 is stated for LD algorithm. Recently, the bound in Haghifam et al'2020 is extended to SGLD in [1]. The bound in Rodríguez-Gálvez et al has worse dependence on n (1/sqrt(n)), however, they have a decaying factor in their bound to compensate using of the chain rule. It would be nice to numerically compare your bound with the bound in [1]. 

- Applying your framework for analyzing SGD:  What are the roadblocks for applying your bound to analyzing SGD?

- Surrogate loss: I think you should distinguish the loss function that we use to measure the generalization error with the loss function that is used for training. You should use different notations. 


[1] "On random subset generalization error bounds and the stochastic gradient langevin dynamics algorithm", Borja Rodríguez-Gálvez, Germán Bassi, Ragnar Thobaben, Mikael Skoglund

summary_of_the_review: Very interesting and solid contribution!
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper provides generalization guarantees for exponential family sgld which is a more general setup than standard gaussian noise langevin dynamics as it allows for noise settings from any member of the exponential family. The authors point out that the setup they consider is a strict generalization of the standard langevin dynamics, and give another explicit example of sign sgd based generalization. 

The authors use and show gradient discrepancy as opposed to gradient norms as used by Li et al, and gradient incoherence as used by Negrea et al. but the latter have 1/\sqrt{n}. Overall, from useful empirical observations it seems that the bounds proposed by the authors are tighter than these other bounds. 
main_review: There have been several works that generalize from gaussian settings to the more general exponential family, including the ones that are cited by the authors but also for example monotone retargetting and exponential family PCA. As such there are several tools for such an analysis that are pretty well known now. Other than that, the analysis follows closely with that of Li et al, with few minor but important differences. 

I am not sure if the extension to exponential family is a major contribution. It allows for analysis of signSGD. But given several other works of similar nature, I am not sure if the analysis and the major contribution as claimed, including in the title of the paper justifies a publication. 

It seems, however, that proposing gradient discrepancy itself is a useful contribution. Can the authors highlight the difference in the analysis from Li et al explicitly that led to this difference in the bounds ? Why is this sidelined as a side-effect? Does this follow from the new exponential family based analysis proposed here (it does not seem to be so) ? The experiments are also conducted based on this contribution. As such the main message/contribution of the paper and the empirical section seems disconnected. I am happy to be corrected. 
summary_of_the_review: The main contribution of exponential family dynamics seems not very significant. Gradient discrepancy is sidelined as a minor contribution but is focussed on a lot more in the empirical section, which makes the paper seems disconnected.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper under review considers the generalized SDLG algorithms with exponential family noise introduced to the mini-batch gradient descent. The analysis of the error bound is based on the control of the expected stability. Experiments are provided to support the proposed EFLD SGD algorithms.
main_review: Strength.
1. The paper proves the generalization error of ''existing'' noisy stochastic iterative algorithms to have a $\mathcal O(1/n)$ sample dependence. 
2. The exponential family noise is considered in the generalized SGD algorithms. The generalized error bound is based on expected stability, which seems to bring new ideas for general exponential family noise.  A thorough analysis of the error bound of exponential family noise SGD algorithms is provided. 

Weakness.

1. The proposed algorithm does not show state-of-the-art performance.  The ultimate goal of the proposed algorithms is to achieve better performance on real data sets. Without strong support from the empirical study,  it is not convincible to believe why one bothers to study such more complicated cases. 
2. Adding to the above point, the paper only reviews the SGD in the literature, there have been very recent works based on Langevin dynamics, e.g. replica-exchange Langevin dynamic SGD, second-order Hamiltonian Langevin dynamics. Those algorithms achieve state-of-the-art performance. It is questionable to ask if the newly proposed algorithms in this paper could provide better performance if the model architectures are improved. 
summary_of_the_review: The paper seems to provide a new family of SGD algorithms. The potential of the model seems to be broad. The theoretical analysis is recognized and deserves their own interest. However, the current state of the empirical study does not show promising performance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper improves generalization bounds based on the notion of stability. The notion of stability measures the effect of resampling a data point to the output of the algorithm. The paper improves known analyses in two directions: 
- It proposes to use the notion of expected stability rather than uniform stability, which should to be tighter.
- It generalizes the analysis to noises in an exponential family rather than Gaussian noise.

main_review: This paper provides several technical improvements to a recent line of work that I am not familiar with. Thus I can hardly review that relevance  and novelty of these improvements (and I am thus putting a low confidence score). I am concerned by the fact that the article is hard to read in a self-contained way. The authors largely comment the articulation of their work with similar works, but almost never comment the relevance of their work for a wider community. 

Another concern is that the article provides two improvements listed above, but I could not perceive why it was coherent to present them in a common article. This might add some confusion to the paper. 

As a naive question, I would like to ask why expected stability bounds are preferred. It seems that they involve expectations that are hard to compute analytically, at best one can approximate these expectations by sampling. How should these bounds be used in the end? In practice, to choose stopping criteria for algorithms, for instance? Or in theory, to analyze the performance of some algorithms?

I found the generalization from Gaussian noise to exponential families novel and interesting.

In Section 2, I find difficult to determine what are your contributions and what was already known. For instance, Proposition 2 seems well-known right? Why not giving some references rather than proving it? Similarly, to what extent was Proposition 1 known?

Minor comments:
-  Section 2: "D be an unknown distribution OVER Z" (not "of")
- Why do you introduce the notation W_{0:(t-1)} = w_{0:(t-1)}? I am under the impression that this is twice the same object, but I might misunderstand.
- You sometimes use the notation KL(P,Q) and KL(P||Q).
- Conflict of notation between S_0 and S_n (for n=0!).


summary_of_the_review: I am not confident with my review as this paper is quite technical and I am not familiar with this line of work. I would appreciate having more insights about the application of the new techniques and the relevance of exposing them together in this paper.
review_title: null

Meta-review: This paper focuses on generalization bounds for exponential family Langevin dynamics, which extends related recent work for stochastic iterative algorithms such as SGLD in several ways. They derive expected stability bounds for a more general class of noisy stochastic iterative algorithms, leading to an exponential family variation of Langevin dynamics and a noisy version of the sign-SGD algorithm. The contributions are technical and quite positively received by one reviewer, while the others were not convinced to change their opinions during the author response as there were concerns on the limitation of the theoretical contributions and the extent to which these contributions have implications on achieving state of the art performance. While I find it valid that the scope of the paper focuses on generalization bounds and provide improvements over the existing literature, rather than on empirical benchmarks or on optimization-related aspects, the overall borderline impression of the reviewers on the whole suggests that a refined version of the paper that further clarifies the contributions and makes clear its impacts as well as limitations may make for a stronger and more impactful paper.
Decision: Reject