Venue: NeurIPS 2022 Conference

Reviews:

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 connection between Langevin sampling and optimization has been extensively studied. A line of research in literature tries to adapt the known optimization techniques to get new sampling algorithms. This paper follows the same direction. The authors studies two algorithms SVRG-LD and SARAH-LD which are respectively based on the variance-reduced stochastic optimization algorithms SVRG and SARAH. Under the smoothness and LSI conditions the convergence of both algorithms is established in the KL divergence through a descent-like inequality. Under additional conditions, they apply these algorithms for the problem of non-convex optimization.
strengths_and_weaknesses: Strengths
* The paper is very well written. It explains the problem and the setting very clearly. One of the best written papers I have reviewed this year.
* The proposed methods work in the relaxed LSI regime instead of strong convexity. 


Weaknesses
* In the literature review the paper _"On the Theory of Variance Reduction for SG-MC " _ by Chetterji et al. is missing. This paper studies a similar problem. In particular, they propose an adaptation of the SAGA algorithm to the LMC problem. After a brief overview of the results, I saw that the their iteration complexity of Chatterji et al. is smaller than the one proposed in this paper. A discussion on this paper is required. 

questions: * How does your work compare to the above mentioned paper?
* In the statement of the theorems 1 and 2, the introduction of the constant $\Lambda$  seems to be redundant as $\Lambda = 1 + 2\Xi$.


limitations: * The assumption 6 is restrictive as one might have multiple global minima.
* The discussion on the limitations of the work seem to be absent in the paper.
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: In this paper, the authors proved the convergence rate of the Stochastic Variance Reduced Gradient Langevin Dynamics and the Stochastic Recursive Gradient Langevin Dynamics. The proof is based on Log-Sobolev inequality and a relaxed assumption of smoothness and the result shows an improvement from the previous analysis.

strengths_and_weaknesses: This paper provides a non-asymptotic analysis of the convergence of SVRG-LD and SARAH-LD to the Gibbs distribution in terms of KL-divergence. The analysis is based on the relaxed assumptions of smoothness and LSI which are weaker conditions than those used in prior works for these algorithms. Overall, the proven convergence rate of SVRG is better than in previous work. 


However, I feel the result seems to be an incremental improvement of the work by Li and Erdogdu (2020) and Vempala and Wibisono (2019).

questions: 1. Wondering if the authors could comment on the scale of the learning rate. I feel in order to have Theorem 1 and Corollary 1.1. to hold, the required learning rate could be quite small.

2. While setting the batch size to be $\sqrt(n)$ leads to an improved gradient complexity, such batch size is very large and rarely used in practice. What would the gradient complexity look like if using a much smaller batch size?

limitations: In order to have the theorems hold, the choice of a few hyper-parameters, such as learning rate and batch size seem, seem to be far away from what has been used in practice.
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 presents improved convergence rates of SGLD with variance reduction. Also, it presents an application to non-convex optimization -- namely an upper bound on the gradient complexity necessary to reach a certain complexity, in SVRG-LD and SARAH-LD methods. The results are novel -- they take the same assumptions of Vempala et al. (2019), who also used the KL divergence as a criterion, but derive a better gradient complexity. Other works have used other assumptions or criteria. Crucially, however, this paper assumes that the batch size and inner loop length is set to \sqrt{n}.  
strengths_and_weaknesses: This is theoretically a very strong paper. The main weakness is that its implications are a bit restrictive, as SVRG-LD and SARAH-LD aren't used so much in practice, as far as I know. (In fact, variance reduction is not used much in practice; instead, it has been shown recently that the stochasticity in SGD is vital for generalization and escaping minima/saddle-points.)

Strengths:
The analysis is very detailed and technically involved. I did not read the Appendix, but could follow the exposition in the main paper. The literature review is very good and contains most relevant prior work. Table 1 is very helpful to the reader. (A few more words about the comparison with Vempala et al. (2019) could be added to the caption though.) The texts are clear and easy to read, and the authors are transparent about their assumptions. 

Weaknesses: 
1. The discussion of variance reduction methods is lacking in nuance: Lately it has been demonstrated the _stochasticity_, i.e. the variance, actually makes SGD so good by improving generalization. See e.g. https://arxiv.org/abs/2006.15081?context=stat or https://arxiv.org/pdf/2202.02831.pdf . Also, the variance is useful to escape saddle points and local minima: https://opt-ml.org/papers/2021/paper24.pdf and https://arxiv.org/abs/1902.04811. As far as I know, people don't really use variance reduction in practice, for precisely this reason. This is not a fundamental criticism of the paper: It is still important to study variance reduction, but there should be a discussion of the role of stochasticity and the usefulness of the studied methods in the Introduction. Also, the restriction of the results to variance-reduced method of course reduces the significance of the result.
2. There should be a better discussion of the assumption that "the batch size and the inner loop length are set to \sqrt{n}". While the other assumptions are fairly standard, this assumption is highly unusual. Also, it doesn't appear in Table 1 (why?). There should be a better discussion of this assumption, if this appears in other papers, too, and why it is necessary. 
3. Some plots or experiments demonstrating these experiments would be nice. (The proofs are very complicated and it would make the results more plausible if there were a few experiments, demonstrating them.)

Bottom line: If the authors provide a few experiments, I am fine with accepting this paper.


questions: 1. I didn't understand what the "inner loop length" is. This concept needs some clarification in my opinion. 
2. Doesn't one have to assume, in Assumption 2, that \rho is asymptotically continuous wrt. \nu.
3. The paragraph on top of page 9, before "Analysis under the weak Morse condition", is very confusing. Why is the second term with n^{1/2} almost all the time dominant? Why does the analysis of Mattingly et al. (2002) support this? Why use "likely" if the work of Raginsky et al. (2017) implies it? (Not a big deal, but maybe this paragraph can be improved.)
limitations: No limitations and no negative societal impact.
review_title: null

Meta-review: metareview: This paper proposes an improved convergence rate for stochastic gradient Langevin dynamics with variance reduction under smoothness and Log-Sobolev inequality assumptions, which improves a long line of prior works. After author response and reviewer discussion, the paper receives unanimous support from the reviewers. Thus, I recommend acceptance. 
confidence: Certain
Decision: Accept