Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited

We thank the reviewer for the valuable feedback. Please find out our response below.

1. A major part of this paper’s contribution is removing the (square root of) $mnh$ for the error bounds of RLMC and RKLMC, yet I’m not clear on how important this is. The removal of this term, claimed by the authors, is an important step toward extending these results to potentials that are not strongly convex. Similarly, in the comments for the result for RKLMC, the authors claimed that not requiring the algorithm to be initialized at the minimizer of the potential is important for extending the method to non-convex potentials.

Let us provide some additional explanations related to these claims. First, let us explain the importance of removing the time horizon $T = nh$ from the upper bound on the discretization error. For most non-convex potentials, the associated Langevin process is not geometrically ergodic, but it can still be ergodic with a polynomial mixing rate. This implies that the time horizon necessary to achieve $\epsilon$-accuracy for the continuous-time process depends polynomially on $1/\epsilon$ (as opposed to the logarithmic dependence in the geometrically ergodic setting). Hence, removing from the discretization error a factor that is polynomial in $T$ would lead to an improvement of the upper bound on the overall sampling error that scales polynomially in $1/\epsilon$.

Likewise, the insistence on the initial point being at the minimizer is tailored to the (strong) convexity assumption, ensuring the computationally efficient determination of such a minimizer. Clearly, this is not the case when dealing with a non-convex potential function.

Therefore, eliminating the term $T = nh$ and removing the requirement for the initialization to be at the minimizer constitute crucial steps in generalizing the results to the non-convex case.

2. However, as the authors pointed out in the discussion, strong convexity seems to be an essential assumption for these results. Therefore, I’m a bit unclear on the significance of this paper’s contribution... Please see the weakness part. In particular, how would the extension to non-convex or non-strongly convex potentials depend on the authors’ proposed methods?

One of the prevalent approaches to relaxing strong convexity is to replace it with some isoperimetric inequalities like LSI (Vempala and Wibisono, 2019) or Poincaré inequality (Chewi et al. 2020). These conditions keep the contractivity of the Langevin diffusion without directly assuming strong convexity. To analyze non-strongly convex methods (Dalalyan et al. 2022) and (Karagulyan et al. 2020) have proposed a quadratic penalization which renders the potential strongly convex.

In both cases, having explicit non-asymptotic and most importantly reproducible theoretical guarantees is quintessential to both directions. Thus, we believe that our methods will be relevant also in future work.

We thank the reviewer for their valuable feedback. Please find our point-by-point response below.

1. While the paper presents some intriguing results, most of them primarily offers incremental advancements in the field. It applies the Randomized Midpoint technique to lessen discretization errors, which in turn marginally enhances the rate of convergence. However, the mathematical methods employed are not particularly interesting or surprising.

We firmly believe that our results and techniques are valuable. Although the proof technique appears straightforward, it is nontrivial, demanding additional efforts and meticulous handling of intermediate terms (refer to the detailed explanation of display (14) in the submission). Notably, our coherent treatment of the randomized midpoint method yields enhanced convergence guarantees for RLMC and RKLMC, and provides explicit dependence on the initialization and small constants. Furthermore, our technique eliminates the requirement for the algorithm to be initialized at the minimizer of the potential and removes the dependence of the upper bound on the time horizon $T = nh$. We believe that these improvements are crucial for envisioning to extend previously existing results to the case of non-convex potentials. Indeed, for a non-convex potential, it is not realistic to assume that the algorithm is initialized at a minimizer of the potential function. In addition, if the non-convex potential is such that the resulting Langevin process is not geometrically ergodic, then the time horizon necessary to achieve $\epsilon$-accuracy for the continuous-time process depends polynomially on $1/\epsilon$. Hence, removing from the discretization error a factor that is polynomial in $T$ would lead to an improvement of the upper bound on the overall sampling error that scales polynomially in $1/\epsilon$.

Furthermore, we demonstrated that our proof technique, applied to the analysis of the KLMC algorithm, leads to an enhanced upper bound on the sampling error compared to the results available in the literature. It is worth noting that many prominent researchers have worked on this problem, and our innovative approach, involving a smart application of the discrete integration by parts argument, improves upon their results.

2. The empirical evidence looks weak to justify the criticality of the Randomized Midpoint in standard LMC.

We note that the target density considered in the empirical studies satisfies a stricter set of assumptions. However, in this work, we aim to analyze the theoretical convergence in the worst-case scenario. In this context, the extent to which the randomized midpoint method outperforms its vanilla version depends on the properties of the target density.

3. Can you provide any empirical evidence that the current algorithm improves in real world?

We note that the primary focus of this submission is to present a thorough and refined theoretical analysis of midpoint randomization applied to (kinetic) Langevin Monte Carlo. While we acknowledge that demonstrating a more concrete and tangible real-world application could enhance the practical significance of our findings, delving into the applied aspects of midpoint randomization presents challenges. Factors such as the measurement of Wasserstein distance, estimation of smoothness and strong convexity parameters, etc., may require extensive efforts. Consequently, we regard this avenue as a direction for future research.

We thank the reviewer for the positive and encouraging feedback.

1. It would be nice if some simulations in higher dimensions p could be included in Section 5.

We thank the reviewer for raising this question. Calculating the Wasserstein-2 distance in a high dimensional setting poses significant challenges. Furthermore, increasing the dimensionality may implicitly alter the strong convexity and smoothness parameters. This is the rationale behind our focus on low dimensions.

2. Potential typos:

We thank the reviewer for pointing out the typos, and we corrected them in the revision of the paper.

We thank the reviewer for their valuable feedback. Please find our response below.

1. Some of the results are potentially still not optimal as the authors also suggest.

While our bound offers the best-known dependence on the condition number for Kinetic Langevin Monte Carlo, it's essential to note that the optimal dependence remains an open question.

2. It would also be nice to see how the improved bounds can be applied to some more concrete problems even for theoretical results... Do you an example application of the improved analysis do get better results for a specific problem?

The primary focus of our work is to present a thorough and refined theoretical analysis of midpoint randomization applied to Langevin Monte Carlo. While we acknowledge that demonstrating a more concrete and tangible real-world application could enhance the practical significance of our findings, delving into the applied aspects of midpoint randomization presents challenges. Factors such as the calculation of Wasserstein distance in high dimension, measurement of the distributions of the samples and the true underlying distribution, estimation of smoothness and strong convexity parameters, etc., may require extensive efforts. Consequently, we regard this avenue as a direction for future research.

3. Potential typos:

We thank the reviewer for pointing out the typos, and we corrected them in the revision of the paper.