Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: Traditional generalization analysis assume that a given algorithm converges to a fixed point. This paper studies the generalization of algorithms when the weights converge in distribution. In particular, the authors propose statistical algorithmic stability (SAS), through which they give upper bounds for the generalization bound. Then this paper gives a sufficient condition for an algorithm that satisfies the SAS.
Finally, this paper provides numerical results to find the SAS coefficient.
strengths_and_weaknesses: Strengths:
- This paper is well organized and easy to follow.
- The idea of analyzing the generalization of algorithms that converge in distribution is interesting.
- Provides the code.


Weaknesses:
- The significance of SAS is not clearly stated when comparing with traditional algorithm stability.  By taking the expectation over the randomness of an algorithm, traditional algorithm stability can also analyzes the generalization when an algorithm does not converge to a fixed point. See the Questions part for details. 


Minor issue:
- The references in the PDF cannot be retrieved. Maybe because the hyperref package is missing.


questions: - My main concern lies on the difference between the traditional algorithm stability and SAS in this paper. 
The Definition 1 in this paper is based on a deterministic algorithm. However,  [1] gives a uniform stability definition with exception over the randomness of a random algorithm. That is to say, traditional algorithm stability can also handles the situations when learning algorithms that do not converge to a fixed point. I think it would be better if the authors could give more discussions on the comparison between the uniform stability in [1] and SAS. 

- The generalization bound in Theorem 1 seems to be dominated by $\beta$. It would be more convincing if the authors could include numerical results on the order of $\beta$ when varying the sample size (on clean dataset rather than corrupted dataset)
 



[1] Hardt, Moritz, Ben Recht, and Yoram Singer. "Train faster, generalize better: Stability of stochastic gradient descent." International conference on machine learning. PMLR, 2016.
limitations: It seems that there is no potential negative societal impact of this work.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The standard notion o stability assumes learning algorithms to be convergent to a fixed point w.r.t. the weights. But, in practice, the weights of deep neural networks optimized with stochastic gradient descent do not satisfy such a condition and they often oscillate indefinitely. Motivated by this fact, the authors propose a notion of statistical algorithmic stability (SAS) that extends classical algorithmic stability to algorithms in which the weights only converge in distribution. The authors also show particular conditions under which such stability condition is satisfied and they discuss the learning algorithms from a dynamical systems perspective. Finally, they confirm their theoretical findings by computational experiments.
strengths_and_weaknesses: The problem addressed by the authors is for sure an interesting question. On the other hand, I think that the results could be presented in a clearer way, adding some examples and more discussion would make the paper for sure more readable by the community. For instance, adding specific examples of SAS algorithms would be very useful. Also the presentations of the theoretical results could be better addressed and the reader could be better guided in the meaning of the paper. For instance, giving a sketch of the proof of Thm.1 would be very meaningful. Otherwise, the paper remains quite abstract.

questions: In my opinion, the relation between the standard notion of stability and the SAS stability is not well investigated in the paper. Which is the relation between them? What about the generalization property of the two? 
limitations: I do not see any negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper lays the theoretical groundwork for studying the behavior (generalization, dynamics) of stochastic learning algorithms: here, the appropriate notion is not deterministic convergence to a fixed-point, but rather various notions of stochastic convergence. Specifically, the paper posits (Assumption 1) that the dynamics of the hypothesis (input-output function) are ergodic. Thus, functionals of the hypothesis may converge over the SGD trajectory, while the parameters themselves may not converge. The paper also discusses relations to existing notions of stability and convergence, and provides a toy analysis for when SGD learning is "stochastically stable."

strengths_and_weaknesses: Strengths:
The paper is very well-motivated and well-written: it correctly points out limitations of prior (deterministic) approaches to analyzing learning dynamics, and it clearly outlines a formalism for studying stochastic dynamics of SGD. The mathematical exposition is clear. 

Weaknesses:
Assumption 1 is very strong, and is not tested with proper experiments. For example: Assumption 1 (and the definition of SAS) involves a supremum over all inputs z, and all test functions \ell. However, the experiments in Figure 1 only measure several observables, and make no effort to take the supremum over z.
This limitation should be discussed in the paper: do the authors claim that Assumption 1 is realistic, or is it merely meant to be theoretically-suggestive, while being too strong to hold in practice?

I am also curious whether Assumption 1 is consistent with the "Disagreement Property" in the literature (introduced by [1][https://arxiv.org/abs/2009.08092] and followed-up by [2][https://arxiv.org/abs/2106.13799]).
The Disagreement Property in [2] shows that two models trained with different seeds, on the same train dataset, *do not* converge to the same hypothesis function. Rather, the two hypotheses "disagree" in their predictions, at a rate roughly equal to the test error.
This property seems at-odds with the convergence that's claimed in the present paper, and I'd be curious to hear the author's thoughts on this.

questions: See above.
limitations: NA
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper, entitled "On the generalization of learning algorithms that do not converge", extends the notion of algorithmic stability to algorithms that do not converge in the traditional sense of reaching a fixed point in weight space. Because it is increasingly becoming clear that many commonly used algorithms often do not converge, this covers a broad range of algorithms. By using ergodic theory, the authors define statistical algorithmic stability and develop bounds for their metric. These bounds identify that algorithms "that exhibit faster convergence to the stationary measure on the loss space generalize better." Finally, the authors validate their theory on VGG-16 and ResNet-18 models.
strengths_and_weaknesses: STRENGTHS:

1. This paper is very well written. It was easy to read and get the main points from. 

2. This paper effectively motivates the problem by identifying a gap in the current theory developed for studying algorithmic stability and illustrating why many commonly used algorithms fall into this gap. TA large body of literature was cited and it was clear where overlap between this paper's contributions and other work in the field was. 

3. The authors' new definition of statistical algorithmic stability is general, intuitive, and theoretically backed. This last point, being grounded in theory, makes it especially appealing as an extension for algorithmic stability.  I believe that it will be prove useful for studying algorithmic stability, and will open up new discussion in the field.  Additionally, the authors should be applauded for their treatment of dynamical systems and ergodic theory, which was clear and well laid out.

4. The result that "that exhibit faster convergence to the stationary measure on the loss space generalize better" is very interesting. If anything, I think the authors should emphasize this point more throughout the paper, as I imagine it will be of interest to the community. 

WEAKNESSES:

1. The discussion surrounding the use of the auto-correlation and the non-Markovian nature of samples from the loss space felt cramped. I understand page that there are page constraints, but it felt a little difficult to connect the experimental results with the theory that had been laid out earlier. Additionally, I would emphasize the last (punchline) sentence of Sec. 4 (lines 324-326) more. 

2. The generalization gap for the 50% noise being nearly the same (if not lower) than the generalization gap of the 0% noise confuses me (Figure 2). Is this because the ResNet is performing "at chance"? Adding a sentence or two to clarify this would be helpful for interpreting this result. 

3. There are two points in Sec. 5 where I believe the conclusions from the results are overstated. First, Figure 3 (right) shows the lower bounds of $\beta$. Therefore, the claim "illustrating that cases with worse generalization error have larger $\beta$" (lines 344-345), is not quite right because it has not been shown how tight the lower bound is. However, I do think it is interesting and telling that the lower bound increases with worse generalization. Making this point more accurately does not, in my mind, diminish the finding. And second, "the magnitude of the test loss autocorrelation correlates with with the generalization gap" (lines 353-354). Looking at Figure 2 (center), it appears that the generalization gap between 10%, 17%, and 25% noise, at the end of the 1000 epochs, is pretty minimal. However, there is a very clear difference in the magnitude of the test loss autocorrelation between 10% and 17%/25% (Figure 2 (right)). Similarly, there is a large difference in magnitude between 0% and 50%, whereas there is not a major difference between the generalization gap of those two. I think the authors would do better to report the results as is. The theory they develop is very convincing (at least to me), and improvements on the bounds and ways to compute $\lambda$ will lead to stronger numerical results. For now, it is sufficient (again, to me) to just show the current state of numerical results, even if they aren't 100% convincing. 

3. The abstract mentions the work "provides clues to overfitting" (line 12), but overfitting is not explicitly mentioned. I would either discuss this in Sec. 6 or remove from the abstract.

MINOR POINTS:

1. Figure 3 (left) should have lines instead of dots to reduce the thickness of the curves. 

2. That Figure 2 and Figure 3 are tested on different models should be made more clear in the text (not just the figure captions). 

3. It should be noted after Eq. 7 that a smaller value of $\beta$ implies better generalization. This is of course obvious from the equation, but "stability coefficient" may make readers think bigger is more stable. 

4. "two notions of risk defined..." (lines 250-252) is an interesting point and should be made a little more clear. What precisely is "the space of learning algorithms"? Why does Eq. 8 lie in the space?

5. There are a few typos:

i. Lines 94 and 99 have mis-formatted citations. 

ii. Line 355 should say Eq. 12 or (12).

iii. Should it say "Figure 3 (left)" on line 345?

6. There are a few places where things should be defined before they are used:

i. $m$ being the batch size in line 133. 

ii. $|| \cdot ||_{TV}$ in Eq. 10. 

iii. The # symbol in line 274.

7. The literature was in general very well cited, but I think adding some references when discussing dynamical systems theory and ergodic theory in ML would be helpful. Eg: Saxe et al. 2013; Li et al. 2018; Dietrich et al. 2020; Dogra and Redman, 2020. 

OVERALL:

I believe this paper is strong and fills an important need in the field. Given that generalization is a major problem in machine learning, and that current approaches based in algorithmic stability have limitations (namely, they require that the algorithmic converge in weight space, which many commonly used algorithms do not do). Additionally, I believe that the ergodic theory, and dynamical systems theoretic more generally, perspective the authors take is a very fruitful direction for the general field of ML to move in. 

For all these reasons, I am giving the paper a 7. That being said, I do believe the points I discuss above in the weakness section (which I believe can be addressed in a straightforward manner) need to be addressed for this score to remain this high. 
questions: I have no additional questions for the authors.
limitations: The authors should make a little more clear what possible limitations the use of the auto-correlation and the non-Markovian nature of samples from the loss space introduces into their numerical experiments.
review_title: null

Meta-review: metareview: The authors new notation for the statistical algorithmic stability. It will be useful for studying algorithmic stability, and will open up new discussion in the field. Overall, the review team provide positive feedback and I would recommend accepting this work.

confidence: Less certain
Decision: Accept