Venue: NeurIPS 2022 Conference

Reviews:

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 studies the generalization performance of Markov chain stochastic gradient methods for both minimization problems and minimax optimization problems. The analysis is performed by using the method of algorithmic stability in learning theory. In particular, the paper shows that for ERM problems, MC-SGD can achieve similar stability results as SGD by introducing an on-average stability argument. The paper first studies generalization performance and then obtains bounds for the excess population risk of MC-SGD. For minimax problems, the paper extends existing results on uniform stability by relating on-average argument stability and generalization error. In particular, it obtains generalization and population bounds for MC-SGDA.  
strengths_and_weaknesses: The paper is generally well-written and well-structured. Although I am not very familiar with prior work in this research direction, it seems to me that the paper has good quality and adequate originality for publication. Related work in the literature seems to be sufficiently cited in Subsection 1.1. As mentioned in that subsection, generalization bounds for SGD with i.i.d. sampling scheme has been previously derived using the stability argument for convex and smooth losses. This paper builds upon these works to obtain interesting results for MC-SGMs.  

There are some parts of the paper that can be improved, as I mention here and below. The organization of the paper starting from line 72 can be further expanded to discuss in more detail what are the goals of each section of the paper. The reason for stating Assumption 4 in line 264 is better to be further elaborated, in particular, what "extreme setting" means in that context. 
questions: 1. In line 44, the only justification for using Markov chain SGMs instead of i.i.d. sampling schemes is stated as performing "more efficiently". I think it would be beneficial to further explain the reason for using these Markov chain methods (instead of i.i.d. schemes) in the introduction. 

2. The results of Section 3 hold when the parameter space $\mathcal{W}$ is bounded and has diameter $D$, as assumed in line 260. Is it possible to handle cases when $\mathcal{W}$ is unbounded?

3. The main contributions of the paper stated in line 52 can be made as a separate paragraph or subsection to make it stand out and to be read more easily.

4. Abstract: There are a large amount -->  There is a large amount 
limitations: The authors have adequately addressed the limitations of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies generalization ability and excess risk of a one-sample SGD with averaged iterates where selection of samples happens according to the Markovian process rather than i.i.d. The paper attacks the problem from the algorithmic stability viewpoint, namely the analysis looks at the expected excess risk (in a realizable setting) as a decomposition of the generalization error and optimization error. The generalization error is controlled by stability of such a variant of SGD (as for instance in the well-known analysis of Hardt et al.), while analysis of the optimization error relies on known results. The paper analyzes excess risk for both smooth and non-smooth convex losses under appropriate tuning of step sizes. In both cases, as one would expect, the bound is controlled by the spectral gap. The paper considers extreme cases, of the sampling process, such as i.i.d. and sample on a cycle --- at the very least in the i.i.d. case the bound seems to coincide with known results. For non-convex smooth losses the paper also does a stationary-point convergence analysis in the style of Ghadimi-Lan (presented in appendix).

strengths_and_weaknesses: The stability analysis essentially follows the on Hardt et al. for SGD with a nuance regarding the sampling of SGD indices. While in the analysis of Hardt et al. one assumed a uniform sampling, in the present paper the proof introduces an indicator, which technically can work with any sampling index sampling procedure. Now, it that the key insight is a realization that averaging parameter stability over the training sample takes out the effect of sampling procedure (averaging of aforementioned indicators). As such the resulting stability bound is completely free from the effects of the Markov sampling process, i.e. the same as one would get in the i.i.d. case. Moreover, it seems that this works out not only for Makovian sampling, but *any* sampling. This seems quite surprising, and perhaps could be attributed to the in-expectation nature of the bound. This might seems as, perhaps, even trivial, but when combined with the bound optimization error it provides a rather clean method to obtain excess risk bound with Markovian SGD -- this is definitely a strength of the paper.

Assumptions on the Markov chains considered here seem to be rather limiting and the paper does not discuss relevant cases/examples where do these hold, could be used (for instance, which cases in ML those cover, which cases in RL, are these realistic?). While, technical result is nice, it could be better elucidated with examples. 
questions: Since the Markov chain considered here is aperiodic, it seems that one can consider SGD without replacement as a special case. How does the excess risk rates obtained in this work compare to the known results in this more challenging SGD variant?
limitations: Yes, the paper discussed relevant limitation pertaining to the algorithmic stability analysis.
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 authors proposed a generalization analysis of MC-SGD and MC-SGDA for stability in both smooth and non-smooth problems based on statistical learning theory. The authors could establish the same generalization bound $O(1/\sqrt{n})$ as in the i.i.d sampling scheme.
strengths_and_weaknesses: Pros:

1. The authors propose the first generalization performance of MC-SGD and MC-SGDA with Markov sampling and the rate is the same as the i.i.d sampling scheme.

2. The relation and connection between on-average argument stability and uniform argument stability seem useful.

Cons: 

1. The reason why we should adopt Markov chain sampling is not clearly motivated. Although there is a paper cited [1], the benefits of Monte Carlo sampling are not elaborated or detailed enough, which is hard for researchers outside this community to judge why it is useful.

2. The technical tools used are fairly standard and elementary and the study on the generalization performance of a concrete algorithm seems routine.

[1] On Markov Chain Gradient Descent. 2018
questions: I am not an expert in this area, but I want to hear more about why or/ and when Monte Carlo sampling is better than i.i.d sampling. Maybe Monte Carlo sampling has certain benefits under a few limited scenarios, but the study on concrete properties of such a setup seems not interesting.


limitations: NA
review_title: null

Meta-review: metareview: The paper authors a new generalization analysis of SGD with MC sampling by using algorithmic stability. The reviewers agreed that the technical contribution is novel and interesting. Though initially two reviewers were concerned about the potential applications for SGD with MC sampling, the authors have updated their paper pointing out several applications that fits the type of MC sampling assumed in their proof. 
confidence: Less certain
Decision: Accept