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: The paper aims at deriving new bounds for langevin algorithms in some specific cases, showing that the bound of convergence it attains is better than previously obtained in the literature.
It focuses on obtaining new 1-Wasserstein distance for non-convex losses with L-mixing data variables and polyhedral constraints, showing that the rate of convergence is faster.
strengths_and_weaknesses: The paper is technically well  written and presents a novel bound for Langevin algorithms. The math is advanced and the proof technically difficult. 
Furthermore, the paper is well organized and the derivation is clear.
I checked some of the proofs which were very involved and the resulting paper is impressive theoretically.

The main weaknesses of the paper are to my mind thelimitation to the specific case with L-mixing data variables and polyhedral constraints, which is  Unfortunately not supported by a practical example to show the relevance of the approach proposed by the authors. 
questions: My main question to the authors is can you find a practical case where the bound they obtain begins to be optimal, especially with respect to the rest of the literature ? Which would validate and motivate to my mind the impressive theoretical work you show.
limitations: The limitations are we’ll described by the authors  and are mainly the specificity of the results.
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: Authors study the problem of constrained sampling guarantees for the projected Langevin algorithm in a non-asymptotic sense in Wasserstein 1 metric.
strengths_and_weaknesses: - Strengths:
+The paper is well written and the proofs look correct as far as I can tell.
+ Improves the previously known rates under milder conditions.

- Weakness:
+ Major concern 1: Lack of motivation in the solved problem.
+ Major concern 2: it is not clear how the dimension and other problem parameters interact with the convergence rate. Since the authors are relying on Eberle's reflection coupling, the dimension dependency will be exponential, e.g. exp{LR^2}.
+ Insufficient recent sampling literature review: Unconstrained sampling with Langevin algorithm is a well studied problem, especially under quadratic growth conditions that the current paper is making. Authors cite a few papers from 2017 referring to them as recent, yet there has been a lot of progress since then. 

- Minor concerns:
I listed a few typos that I noticed below.
+ l20 Deep Neural networks
+ l107 missing \nabla 
+l133 the interpolation process is not properly defined, so is the Brownian motion (and its filtration).
+l85 before ever mentioning about f, we are introduced its gradient. 


questions: Q1: What is the dimension dependence of this convergence guarantee?

Q2: What is the motivation for sampling from the Gibbs potential \bar{f}? Is this related to a Bayesian posterior sampling problem or any practical sampling problem? Is it only for obtaining non-convex optimization guarantees?

Q3: What is the benefit of using Eberle's result instead of a functional inequality based approach such as LSI + Holley-Stroock as in Vempala&Wibisono if the dimension dependence is already exponential?
limitations: See the section "Strengths and Weakness".
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: This paper studies the problem of non-asymptotic convergence guarantees in 1-Wasserstein distance for projected Langevin Monte Carlo with (unbounded) polyhedral constraints, non-convex losses and L-mixing data. The convergence rate $O(T^{-1/2}\log T)$, is faster than the previous works on constrained Langevin algorithms in the literature. 
strengths_and_weaknesses: This is a solid theoretical paper and the analysis seems rigorous. This paper obtains the problem of non-asymptotic convergence guarantees in 1-Wasserstein distance for projected Langevin Monte Carlo with (unbounded) polyhedral constraints, non-convex losses and L-mixing data, with the convergence rate $O(T^{-1/2}\log T)$ that is faster than the previous works on constrained Langevin algorithms in the literature. My understanding is that the paper has made the following contributions (1) the convergence rate is faster than the previous works for constrained Langevin algorithms (2) the continuous-time convergence rate in 1-Wasserstein distance extends some existing literature to allow reflected boundary (3) novel discretization error bound where the constraint can be unbounded. 

There are several weaknesses of the paper that makes me question the technical novelty and the significance of the contributions of the paper.

(1) Even though the results are new, similar analysis for non-convex learning for projected Langevin algorithms has already been appeared in [24] for example. The author(s) should do a better job at explaining what are the technical novelties and innovations that allow them to improve the convergence rate and allow the result to work on unbounded constraint set.

(2) In the model, there is a scaling parameter $\beta$, that is known as the inverse temperature. When you are doing sampling, you can simply let $\beta=1$. But when you need to use Langevin algorithms to solve a non-convex optimization problem, you need to have large $\beta$ in order for the Gibbs distribution to concentrate around the global minimizer of the target; see e.g. [30]. The authors at least should comment on the order of dependence of the constants on $\beta$ and whether it is possible to allow $\beta$ to be large to be used for non-convex optimization. Moreover, Theorem 1 is a result that can be used for sampling for non-log-concave target distribution, but can you use the ideas from [30] to obtain results for empirical risk minimization/population risk minimization? It is not clear to me because your result is in 1-Wasserstein and the constraint set is unbounded. In some sense, it is not clear to me your 1-Wasserstein result can lead to any non-convex optimization guarantees on an unbounded domain.

(3)  In Lemma 7, Lemma 8, the error bound has the term $e^{\eta\ell k}$, where $\ell$ is the parameter of the $\ell$-smoothness of the target, $\eta$ is the stepsize and $k$ is the number of iterates. The authors should comment on how tight/good these bounds are. I am a bit worried that these are too loose. For example, to make Langevin algorithm work, you need the continuous time dynamics to be close to the invariant distribution, also known as the Gibbs distribution, which requires $\eta k$ to be large. But if $\eta k$ is large, then the error bounds in Lemma 7 and Lemma 8 are exponentially bound. The discretization error bound in [30] does not have exponential dependence on $\eta k$ and it would certainly be great if the author(s) can improve upon this.
questions: (1) On page 2 and page 3, I suggest the author(s) to define 1-Wasserstein distance and the polyhedral just in case some of the less theoretical readers are not familiar with these concepts.

(2)  The authors should discuss or make some comments about the assumption in Section 2.4. You assumed that $\bar{f}(x)$ is $\mu$-strongly convex outside a ball of radius $R>0$. This can be confusing to some readers who are not familiar with such assumptions because on the surface it gives the readers the impression that you are assuming almost strong-convexity whereas in the abstract you are claiming that you are doing non-convex learning. Please provide some references and comments on whether this is a common assumption, and whether it is equivalent for example to dissipativity condition in the literature.

(3) You mentioned that most of the novel work in the paper focuses on deriving Lemma 3 and you provided Section 3.3 for a proof overview for Lemma 3. But I think what would really be nice is to provide some high-level general discussions in plain English either before Section 3.3. or at the beginning of Section 3.3 about the novelty of your techniques to obtain Lemma 3 as well as the high-level descriptions of the steps needed to achieve Lemma 3.

(4) Journal names etc. should be capitalized in the reference. For example, the journal name in [4] should be capitalized. Also in [6] and [9], langevin should be Langevin.
limitations: Indeed, the author(s) included a section near the end of the paper discussing the limitations of their work.
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 gives W_1 convergence guarantees for the constrained Langevin algorithm with stochastic gradients over a polyhedral constraint set. The assumption on the target function is that it is Lipschitz everywhere and strongly convex outside of a ball; moreover, the stochastic gradients are not i.i.d., but rather are obtained from an L-mixing process (which quantifies the amount of dependence in the noise). Similar problems have been studied before on more general constraint sets, but in the case of a polyhedral constraint set this paper obtains the sharpest bound thus far. The main challenge in this work is the mathematical difficulty associated with studying SDEs reflected at the boundary.
strengths_and_weaknesses: This paper makes a good contribution to a challenging problem. Technically, the analysis is quite similar to that of the prior work [24], which dampens the novelty. However, I believe that this is outweighed by the virtue of analyzing the projected Langevin algorithm, for which quite little is known. I also found the writing to be clear.

Another notable weakness is the lack of theoretical comparisons with other approaches, such as proximal LMC [5]. I understand that the settings considered in prior works may differ from the one considered here, but nevertheless it would be helpful to include a discussion on whether techniques in those other works can be expected to apply to this setting, especially since the other approaches avoid the technicalities involved in the Skorokhod problem.

Specific Comments:
- Line 107, typo in the Lipschitz gradient assumption
- Line 691 in supplement, typo: or -> of
questions: None.
limitations: In the paper, quantitative dependence on problem parameters such as the dimension is not made explicit until the appendix. This is an issue because several parameters are quite large, e.g., there is an exponential dependence on the radius R of the ball without strong convexity, and an exponential dependence on the rank of the matrix specifying the polytope constraints. For the former, this is a standard feature of works which make the “strongly convex outside ball” assumption, but nevertheless such exponential dependence should be discussed clearly in the main text (especially since the abstract claims to handle non-convex functions, but realistically these bounds are quite poor for very non-convex functions). In particular, the contraction factor a is one of the most important parameters and an explicit bound on a should appear in the main text.
review_title: null

Meta-review: metareview: After going through all the reviews, rebuttals, and discussions in detail I am recommending a borderline acceptance for the paper. More precisely, the technical contribution of the paper is significant, even though there have been some concerns raised regarding the motivation/applicability of the setup. However, I do believe that the merits of the paper outweigh its limitations. I recommend the authors to implement all the suggested changes.
confidence: Certain
Decision: Accept