Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: In the context of sum-decomposable, smooth, and strongly convex potential functions the authors propose algorithms to improve the upper bound on the approximation error for estimating a Underdamped Langevin Diffusion (ULD) process and on the sampling error of the strongly-log-concave sampling problem. The continuous time ULD process has the strongly-log-concave distribution as its invariant distribution so approximating this process and sampling from this distribution are closely related. In the full gradient setting, the authors present a novel algorithm, ALUM which has optimal iteration complexity in $d$, $N$ and $\epsilon$ for the ULD approximation problem. Here, $N$ is the number of terms in the sum-decomposable function, $d$ is the input dimension and $\epsilon$ is the accuracy parameter. In comparison to the RMM algorithm (Lee et al), the dependence on $d$, $N$ and $\epsilon$ in the iteration complexity are matched, but the number of gradient evaluations are reduced by a factor of 2.
Next the stochastic gradient oracle setting is considered: here the authors propose algorithms (SVRG-ALUM and SAGA-ALUM) and analyze the corresponding sampling/discretization error. Finally an improvement in the lower bound for the gradient complexity of the ULD approximation problem to $\Omega(N + d^{1/3}N^{2/3}/\epsilon^{2/3})$ is presented. This shows that the gradient complexity of the presented Variance reduction modifications of ALUM match the lower bound in $d$, $N$ and $n$ in the sum-decomposable setting with a stochastic gradient oracle.
main_review: Overall the authors do a good job in conveying the content of the paper. The body of the paper abstracts the lower level details of the paper fairly effectively, and the relationship of the presented algorithms with the rest of the literature is comprehensive (case in point: section 4.1).

However, I should point out that I find the main contribution of the paper in the gradient oracle setting questionable. In each iteration, the algorithm saves a single gradient computation, but this is at the cost of worse dependence on $\kappa$ which can often be $10^2$ or larger in practice. Thus, overall the results seem to suggest that the gradient complexity may even be worse when the error parameter $\epsilon$ is moderately large.

- Space permitting, I would recommend moving the first paragraph from appendix A.1 into the preliminaries section of the paper. I think it sets up a nice general introduction to the setting and the relation between the sampling and ULD approximation problems.

- It should be made more clear that the gradient complexity upper bounds proved in the paper are not optimal in all parameters. The dependence on the condition number $\kappa$ can be improved (as with the RMM algorithm of Lee et al).

- In Section 7, the authors mention that the dependence on the condition number $O(\kappa^2)$ can be reduced to $O(\kappa^{3/2})$. It would help to be more explicit about the approach here and what are the challenges in improving the guarantee.

- The intuition in Section 4.1, lines 118-123 can be made more clear. Namely, it would be more clear to write the bias accumulated over $T/h$ steps as $O(Th^2)$ (instead of $O(h^2)$). Further, it is mentioned that the variance term is $O(h^{3})$, so I fail to see how the bias is of smaller order than the induced standard deviation. It would also help to point out how the calculation for the variance is carried out.

- According to the first two plots in the experiments section, the ALUM algorithm appears to have the same curve as the RMM algorithm but shifted by what appears to be a constant factor for all ranges of the error parameter. Seeing that the dependence on $\kappa$ ($\gg 1$ here) is presumably worse for ALUM compared to RMM in the proved results, does this plot seem to indicate that the analysis of with respect to $\kappa$ can be improved for ALUM? If the precision level $\epsilon$ is increased further, would the plots eventually diverge?

- An important point to address in the paper is the case when Assumption 2 is relaxed so that only the total potential function $f$ is L-Smooth and the uniform smoothness assumption on the $f_i$'s is dropped. Is there any intuition about whether ALUM / SVRG-ALUM continue to achieve a similar iteration complexity under the gradient and stochastic gradient oracles?

- This is an important point to address at least in the special case when $f$ takes the form of an empirical risk under L2 loss: the smoothness of each $f_i$ corresponds to $\| x_i \|_2^2$ where $x_i$ is the $i^{\text{th}}$ input point. The current smoothness assumption implies that all the $x_i$'s lie in an L2 ball of radius $\sqrt{L}$. Without the uniform smoothness assumption, but assuming that $f$ is $L$ smooth relaxes the condition on the points lying strictly in an L2 ball and imposes an eigenvalue constraint on the covariance matrix which is of more practical significance. Do the guarantees carry over here?

limitations_and_societal_impact: Yes, I believe the authors have.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers methods for approximating underdamped Langevin diffusion processes with sum-decomposable strongly convex potential. The main contribution in the paper is the proposal of the Accelerated ULD-MCMC algorithm and its variance-reduced variants. This is followed by a detailed analysis of convergence for each of the algorithms, and the derivation of an information-based lower bound for gradient complexity in the task of estimating ULD that matches the upper bound (in dimensionality, component number, and target accuracy). The authors conclude with a discussion of the optimality (or lack thereof) of ALUM with respect to all the variables. Comprehensive experiments are presented to compare the performance of various algorithms on estimation ULD processes, showing that ALUM and its variants achieve better performance than previous algorithms.
main_review: ** Update: The additional discussion and context provided in the rebuttal addressed my concerns and I have adjusted the score accordingly. **

The paper is interesting and well-written overall with good contribution to the algorithms for ULD processes. The authors offer a clear context about ULD and existing algorithms such as LPM and RMM (mostly in appendix, some of which I believe might better fit in the intro if space allows). I find it interesting and a bit surprising that dropping the $-\psi_2(at)\nabla f(X_0)$ term in RMM does not hinder the accuracy by much. The authors also offer a very comprehensive and detailed discussion on the experiments on both synthesized and real-world data.

However, my main concern is that I’m not fully convinced that the newly proposed algorithm and its performance improvement are significant enough. The difference between ALUM and RMM might seem subtle: I did not completely get the motivation behind ALUM or its intuition (e.g., why the extra gradient term can be drop - such intuition could potentially be of value in other problems); the factor-two reduction in gradient evaluation could also use more justification regarding why it is significant (e.g., is there some applications that can critically benefit from the factor-two reduction?). For the experiment results, while I agree that the proposed algorithms outperform the existing ones (e.g., Fig 1), I would again suggest that the authors argue its significance by, e.g., relating the improvement to some application.

Comparison of ALUM with RMM and NAG is also interesting, but I would hope to see deeper insights, e.g., whether there may be underlying intuition for why ALUM might be desirable in its current form. I would expect this theme to re-appear in later discussion if the authors believe there may be more interesting insights.

I did not go over all the proofs. Overall, the theoretical analysis is sound and I believe all the claims are correct. As a minor point I believe some of the proofs in the appendices could use more polishing with explanations around the equations (for easier reading).

To sum up, I believe the paper can be stronger if the authors could demonstrate better the significance of the improvement and/or offer some motivation or intuition behind the ALUM and RMM distinction.

### Other comments:

Should probably mention $I$ is identity matrix with dimension inferred from context (since $I_n$ is also used in some discussion for other things).

Given the tiny error bars (e.g., in Fig 1), I would expect the curves to be smoother/straighter. Is there certain artifact that contributes to the curviness or maybe I missed something in my thinking?

Apart from the main assumptions in Section 3 (Assumptions 1-3), there seem to be a number of sporadic assumptions in the theorems/lemmas, e.g. bounded 2-Wasserstein distance of initialization (Section 5, L156, and I did not fully get how Appendix A.6 addresses this), and assumption on step size $h$ in Theorem 3 (L185). I would hope that a quick comment can be added to address how strong/realistic these assumptions are.

The paper could benefit from proof-reading for typos and minor English style/grammar errors.

Some typos spotted:

L74: studies -> studied

L132: comes -> come, is -> are

L184: delete “and”

L521: Eqn (20), don’t think $\gamma=\bar{\gamma}$ is needed

L609: Eqn (35) seems incomplete (I think a summation is missing)
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the underdamped Langevin diffusion for strongly-convex potential consists of finite sum of smooth components. The authors propose ALUM, which achieves optimal asymptotic complexity in the full gradient setting, and only requires one gradient at each iteration compared to RMM. For the stochastic gradient setting, VR-ALUM methods are proposed which improve over the previous methods in gradient complexity. The authors also accompany with a lower bound showing that the proposed methods are optimal in related parameters for the approximation problem. 

main_review: Overall, I believe this work is a nice complement to existing underdamped Langevin MCMC literature. The presentation is good with clear upper and lower bounds and fair experiments. My comments are summarized as below:

1. The paper studies two problems: sampling in $W_2$ distance and approximation in Euclidean distance. It is known that in the full gradient setting, the algorithm matches RMM, which achieves optimal asymptotic complexity for sampling problem, and in the stochastic setting, the proposed algorithm achieves optimal complexity for the approximation problem. Since sampling problem is considered an important target in MCMC, it would be great if the authors can further comment on the optimality of the proposed algorithm for sampling problem in the stochastic setting beyond the paragraph around line 252: is the gap conjectured to be only logarithmic? What are the lower bounds that one can achieve so far? 

2. Given that there are two different problems (sampling vs. approximation) and two different settings (full gradient vs stochastic gradient), the authors are encouraged to be explicit on the optimality w.r.t. which problem in the introduction and be careful with overclaim in e.g. line 57. Furthermore, the rate $\Theta(N+d^{1/3}N^{2/3}/\epsilon^{2/3})$ for approximation never appears in the introduction, which to me is one of the core contributions of this paper.

3. The theoretical analysis relies on the assumption that the initialization is not too far away from the target distribution. How does this assumption compare to that in other algorithms? Is this the exact same assumption used in other algorithms? Appendix A.6 also appears to be too brief to make the initialization condition clear.


** Update on the reply:

Thanks for the detailed reply. I'm satisfied with the responses to the comments and remain my score.


limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper proposes a randomized algorithm for approximating a trajectory of underdamped Langevin dynamics, similar to the RMM method cited in the paper. It further uses variance reduction method to improve the error over sum-decomposable problems. An information theoretic lower bound is established, which the proposed method matches.
main_review: This paper is interesting and technically sound. Even tough the lower bounds are only in terms of approximating a specific trajectory---instead of for sampling a posterior distribution---they are still useful for numerical methods with Monte Carlo strategies. I quickly skimmed through the proofs, which seem to make sense. 

More specific comments below:

In remark 1, the authors stated that the function can be rescaled for arbitrary L. It is worthwhile to point out how does the step size h scale with L as well.

The notation of equations (2) and (3) causes some confusion: I first thought that the authors are analyzing an algorithm with a shriking step size. It turns out that the step size is a constant. I would suggest chaning t to something else (perhaps \eta). 

In variance reduction, m has been double used as both the epoch length and the strong convexity. For brevity, the authors can also choose a suitable (if not optimal) epoch length and define it in the algorithm.

It seems that the improvement of N dependence provided by the current method is due to the variance reduction method. It seems to also work on the RMM method. Is that the take away from the experiments? Also it is mentioned that the error for ALUM, LPM, and RMM with full gradient, stochastic gradient, SVRG, and SAGA are compared. I can't seem to find the curve for LPM with stochastic gradient.

The overall structure of the paper is clear. However, the literary quality of the paper can be improved. The authors should also be aware of grammatical errors. For example, in the abstract, "consists of finite summation" should be changed to "consisting of finite summation".
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies sampling from strongly convex potential in the form of finite summation of N smooth components. The authors show that using ALUM to simulate ULD needs $O(N+d^{1/3}N^2/3/\epsilon^{2/3})$ gradient evaluations.
main_review: This paper proposes a new algorithm ALUM and combines it with SVRG and SAGA. The algorithms and theorems are clearly written. The claims are supported by theoretical analysis and experimental results.

However, this paper does not discuss some of the important works studying the same problem, e.g. [1,2].  The significance of this work is unclear given previous works [1,2]. [1] shows it is possible to achieve better $\kappa$ and $N$ dependence than ALUM using much simpler algorithms based on similar ideas. The only advantage of ALUM over [1] is that ALUM can improve eps dependence from $1/\epsilon$ to $1/\epsilon^{2/3}$, but [2] shows that with a simple MH step, it’s possible to achieve $\log 1/\epsilon$ and much better $\kappa$ and $N$ dependence at the same time. For this reason, it’s unclear why improving $1/\epsilon$ to $1/\epsilon^{2/3}$ is important. 

Moreover, the algorithm ALUM seems very tailored to sampling from potential in the form of finite summation. It’s based on the idea of RMM, a previous sampler, but its performance on sampling general log-concave distributions is worse than that of RMM. As a result, the contribution of ALUM to understanding broader sampling problems is limited as well. 

[1] Chatterji, Niladri, et al. "On the theory of variance reduction for stochastic gradient Monte Carlo." International Conference on Machine Learning. PMLR, 2018.

[2] Lee, Yin Tat, et al. "Structured Logconcave Sampling with a Restricted Gaussian Oracle." arXiv preprint arXiv:2010.03106 (2020).


limitations_and_societal_impact: Some limitations are discussed in sec 7.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes a new way of discretizing the underdamped Langevin dynamics, by modifying the Randomized midpoint method, proposed by Shen and Lee 2019, which reduces the number of gradient queries by a constant factor. In the case when the log potential of the target distribution is a sum of many terms, the paper produces a variance-reduced variant of their discretization method, which they show achieves the optimal query complexity for approximating the underdamped Langevin dynamics.
main_review: My main criticism for the paper is that the problems investigated are not well motivated. The setting is overly specific to be interesting to a practitioner, so the main contribution of the paper is a technical one. However, although the analysis is impressive, there does not seem to be genuinely new proof ideas introduced, so it seems unlikely that the paper will generate much interest among theoreticians. The lower bound that the paper proves is also not the most interesting one: it proves a lower bound for the point-wise approximation error; however, in sampling it is much more natural to consider distributional approximation error.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper makes new contributions to the literature on sampling from a strongly log-concave smooth measure. This is done by approximating the Underdamped Langevin Diffusion (ULD), and so, a fortiori, the paper also contributes to this approximation problem.

The main result is a new algorithm to approximate the ULD, which is well suited to a stochastic setting, where the gradient of the potential is replaced by certain estimators. 
In the full gradient (i.e. without using an estimator for the gradient) setting the new algorithm matches the asymptotic performance of previous works while cutting the number of Gradient queries by about half.
In the stochastic setting, if the potential can be represented as a sum of $N$ smooth functions, then the authors also show how to modify their algorithm to accommodate estimators to the gradient and reduce the overall query and iteration complexity.

The results of the stochastic setting are also complemented by a lower bound which essentially show that the dependence on the parameters $N$, and $d$, the dimension are essentially optimal.

main_review: ======POST REBUTTAL======
The authors addressed my concerns and I have raised my score accordingly.

The new algorithm, which the authors dub ALUM (with stochastic variant VR-ALUM), is based on the RMM method for discretizing the ULD, introduced by Shen and Lee in 2019.
The RMM method makes two gradient queries per iteration, and the gradient cleverly identified a way to remove one query so that the overall bias does not increase too much.
However, this does come at the cost of worsening the dependence on the condition number, which, I believe, was the main motivation in introducing the RMM algorithm.

The stochastic gradient analog introduced by the authors is a nice addition to the literature and, to my knowledge, outperforms previous algorithms. It is based on thoroughly analyzing variance reduction techniques to stochastic gradients coupled with the discretization scheme of the ULD. The supplied lower bounds further strengthen this.

While the authors supply a clear motivation and an explanation of their analysis, I tried to go over the proofs. I found them extremely technical, even when compared to previous works. This is the reason why my current score is not higher, and I am hoping that the authors can comment on that and explain the main technical difficulties and their own contributions in this sense so that I can raise my score.

Other than that, the paper has many typos and English grammar mistakes. I would ask the authors to go over the entire paper and fix such issues carefully. Such a thing could greatly improve the readability of the paper. (I want to emphasize that my score is not based on that point).

Other comments (I do not mention here typos):
Table 1: Actually, the dependency on $d$ is not shown below ($d$ is not even properly defined by this point)
Line 36: I agree that the question is natural, but perhaps there is some room for discussion about the notion of optimality here.
Optimality can be taken with respect to the number of iterations, the total number of queries, and total operations.
Also, which parameters are taken into account (this discussion appears later in the paper, but some small mention could be appropriate here.
Line 63: I could not understand which divergences are discussed. Total variation vs. something else?
Line 95: I'm not sure what the $h$ in the subscript $X_h$ stands for.
Line 126: I'm not sure what the comparison to Nesterov's momentum algorithm is supposed to demonstrate. Yes, the algorithms are similar because both of them add a momentum term to accelerate the vanilla gradient method. This similarity was already observed before (for example [CCBG2018]).
Line 211: I would suggest reconsidering the use of $U$ for a potential function and $\mathcal{F}$ for a function class. An uncareful reader can think that $\mathcal{F}$ stands for a sigma-algebra and $U$ is an open set.
Line 239: Can the authors say something about the requirement that n is a multiple of N. At first glance, it looks very artificial.
Line 727: I could not find a Lemma 7 in the paper of Dalalyan and Riou-Durand, in any of its versions.
Line 371: On the same topic, there are only two authors to this paper, no et al.

[CCBG2018] Cheng, X., Chatterji, N. S., Bartlett, P. L., & Jordan, M. I. (2018, July). Underdamped Langevin MCMC: A non-asymptotic analysis. In Conference on learning theory (pp. 300-323). PMLR.
limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: This paper proposes a randomized algorithm for approximating a trajectory of underdamped Langevin dynamics. It also uses variance reduction to improve the error over decomposable problems. It also establishes an information-theoretic lower bound. There have been extensive discussions between the authors and the reviewers, and I have gone through them carefully. I agree with the majority of the reviewers that the paper has made interesting technical contributions to the field. I am happy to recommend acceptance. 


Decision: Accept (Poster)