acceptodds
Under review as a conference paper at ICLR 2027

Accelerating Langevin Monte Carlo via Randomization

Abstract

As a fundamental algorithmic task, sampling from a high-dimensional probability distribution finds wide-ranging applications in scientific computing, computational statistics and machine learning. In particular, Langevin Monte Carlo (LMC) sampling algorithms are among the most widely used ones and have received increasing attention in recent years. By injecting additional randomness for every iteration, this paper aims to propose two novel higher-order LMC algorithms, including a Taylor scheme involved with the Hessian of the potential and a Hessian-free Runge–Kutta type variant. Under gradient Lipschitz and Hessian Lipschitz conditions, both algorithms are shown to enjoy non-asymptotic -error bounds of order beyond log-concavity, which guarantees a mixing time complexity . This improves the dimension-dependence of mixing time complexity for the existing high-order LMC algorithms. Moreover, the error analysis of the newly proposed algorithms do not require any Lipschitz condition on the 3rd-order derivative of the potential, which is, however, necessary in obtaining the desired convergence order of existing high-order LMC methods. Some numerical experiments are reported to support the effectiveness of new sampling algorithms.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Langevin Monte Carlo, Randomization, Wasserstein Convergence, log-Sobolev inequality

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_8ZcyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes two randomized higher-order Langevin algorithms—a Hessian-based Taylor scheme and a Hessian-free Runge–Kutta variant—that improve dimension-dependent mixing guarantees beyond log-concavity without requiring Lipschitz third derivatives.

Critical strengths

The paper proposes a randomized correction that potentially improves the dimension dependence of higher-order Langevin sampling while removing the Lipschitz assumption on the third derivative. Its gradient-only variant avoids explicit Hessian calculations, making the approach potentially useful in practice.

Critical weaknesses

The bound in line 782 appears to omit a sqrt{d} factor because J_i has root-mean-square magnitude O(sqrt{d h^3}). This makes Gronwall step dimension dependent. This also affects gradient-only analysis. Although the error seems fixable, this requires a major rewriting which becomes inappropriate for the intended scope of author rebuttal. Therefore I suggest the authors to fix the problem and resubmit so that it can be reevaluated carefully again in a future venue.

In addition, the experiments provide limited evidence of a practical advantage: the dimension-scaling test covers only d=8–16, and the paper does not establish a clear advantage at matched computational cost over alternatives.

Questions for authors

N.A.

1 comment
AuthorsOpenReview ↗

Response to Reviewer 8Zcy

We are grateful to the reviewer for the constructive comments. We appreciate these valuable suggestions, which will substantially improve the presentation of the paper.

About Critical Weaknesses

“The bound in line 782 ...”

Response: We sincerely thank the reviewer for pointing out this issue and apologize for it. As identified by the reviewer, our previous proof, relied on a direct iterative argument, indeed suffering from the dimension-dependent accumulation. To address this issue, we have substantially revised our proof strategy. Specifically, instead of directly iterating the one-step error estimates, we now adopt a local-to-global approach, as established in [Yang and Wang, ICML, 2025] to establish the finite-time error bounds. More precisely, one can easily bound the one-step local truncation errors as follows: ∣E[X(t,x,t+h)−Y(t,x,t+h)]∣=O(dh5/2),∥∣X(t,x,t+h)−Y(t,x,t+h)∥∣L2(Ω;Rd)=O(dh2),|E[X(t,x,t+h)-Y(t,x,t+h)]| = O (d h^{5/2}),\quad \||X(t,x,t+h) - Y(t,x,t+h)\||_{L^2(\Omega;\mathbb R^{d})}= O (d h^{2}), where X(t,x,t+h)X(t,x,t+h) and Y(t,x,t+h)Y(t,x,t+h) denote one-step true and numerical solution starting from initial data xx at tt, respectively. By applying Theorem 3.3 of [Yang and Wang, ICML, 2025] with p1=5/2p_1=5/2 and p2=2p_2=2, we obtain a finite-time mean-square error bound (E[∥X(tn)−Yn∥2])1/2≤C(T)(d2+E[∥X0∥4])1/2h3/2,∀0≤n≤N,(E [ \| X( t_n ) - Y_n \|^2 ])^{1/2} \leq C(T)( d^2+ E[ \| X_0 \|^4 ] )^{1/2} h^{3/2},\quad \forall 0 \le n \le N, where T=NhT= Nh. Following the idea of [Yang and Wang, ICML, 2025], we exploit the exponential ergodicity of the Langevin diffusion and the uniform-in-time moment bounds of both the exact and numerical solutions, to transfer finite-time error bound to uniform-in-time one in W2\mathcal{W}_2-distance. In this way we obtain the desired uniform-in-time non-asymptotic error bound.

This revised approach avoids the problematic dimension dependence in the Grönwall argument and also addresses the corresponding issue in the gradient-only analysis. The detailed arguments can be found in Appendix B of the revised manuscript.

[Yang and Wang, ICML, 2025] B. Yang and X. Wang. Non-asymptotic error bounds in W2-distance with sqrt (d) dimension dependence and first order convergence for Langevin Monte Carlo beyond log-concavity, ICML, 2025.

“In addition, ...”

Response: Thank you for this comment. We have supplemented the original tests with an experiment at d∈(142,144,146,148,150)d\in(142,144,146,148,150), showing approximately linear empirical dimension dependence over this range. Our convergence experiments also show that RT-LMC and RRK-LMC achieve smaller errors and higher convergence rates than the classical LMC and RLMC at the same step sizes.

Reviewer_CMupOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2(+1)
Presentation
2
Soundness
2
Read review
Paper summary

This paper started from the standard Euler-Maruyama discretization of the overdamped Langevin dynamics. By writing the remainder as an integral and approximating the integral with the expectation, the paper proposed Randomized Taylor LMC and a Runge-Kutta variant called the Runge-Kutta LMC.

Critical strengths
  1. The new method is mathematically well-grounded.
Critical weaknesses
  1. The algorithm is very similar in spirit to the randomized midpoint discretization [1]. [1] discusses the underdamped Langevin dynamics, and the analysis of the overdamped version can be found in [2]. In a more general sense, the discussion with prior methods is restricted to the introduction. The sections of methodology and theoretical results have no comparison with existing methods. Specifically, it is unclear how Proposition 3.3 compares with prior works. The comparison can also be better presented in a table.
  2. The interpretation of Proposition 3.3 is lacking. It is unclear how C(T)C(T) increases with TT, which is crucial for the choice of the step size hh.
  3. The question of how the Brownian motion terms Ξn\Xi_n and WnW_n are calculated can be discussed in greater detail. They should be sampled as correlated Gaussian's, not calculated by integral. See, e.g., ξ(1)\xi^{(1)} and ξ(2)\xi^{(2)} in [3].

I am looking forward to the authors providing a detailed comparison with prior works, especially with the randomized midpoint. My current rating represents my concerns about originality and completeness, and I would be happy to raise my rating if the rebuttal is satisfactory.

[1] Shen and Lee. The randomized midpoint method for log-concave sampling. 2019.

[2] Altschuler and Chewi. Shifted Composition III: Local Error Framework for KL Divergence. 2024.

[3] Altschuler et al. Shifted Composition IV: Toward Ballistic Acceleration for Log-Concave Sampling. 2025.

Questions for authors
  1. Can the paper be analyzed under the framework of [1]?

[1] Altschuler and Chewi. Shifted Composition III: Local Error Framework for KL Divergence. 2024.

3 comments
AuthorsOpenReview ↗

Response to Reviewer CMup

We thank the reviewer for this review. All comments/suggestions will be carefully taken into account when revising the manuscript.

About Critical Weaknesses

Response to Comment 1: Thanks for your comments! Different from existing randomized midpoint methods based on the following unbiased approximation of Euler type: ∫tntn+1f(X(r))dr=Eτ[f(X(tn+τn+1h))]≈hf(X(tnτ)),tnτ:=tn+τn+1h\int_{t_{n}}^{t_{n+1}}f(X(r))dr=E_{\tau}[f(X(t_{n}+\tau_{n+1}h))]\approx h f ( X (t_n^\tau) ),\quad t_{n}^{\tau}:=t_{n}+\tau_{n+1}h where h:=tn+1−tnh := t_{n+1} - t_{n} and τn+1∼U(0,1)\tau_{n+1} \sim U (0, 1). We first perform the Taylor expansion to the integrand ff and keep the remainder involving the Brownian increment W(s)−W(tn)W(s) - W (t_{n}): Rn+1:=∫tntn+1[f(X(s))−f(X(tn))−2f′(X(tn))(W(s)−W(tn))]ds.R_{n+1}:=\int_{t_{n}}^{t_{n+1}}[f(X(s))-f(X(t_{n}))-\sqrt{2} f'(X(t_{n}))(W(s)-W(t_{n}))]ds. This way, the new integrand for Rn+1R_{n+1} enjoys order 11 mean-square Holder continuity, improving the order 1/21/2 for f(X(s))f(X(s)) in the overdamped case. Then using external randomness we randomize $ R_{n+1}$ to obtain a martingale, which is essentially used to promote the global convergence rate to order 1.51.5, with an additional order 12\frac12 improvement over order 11 mean-square Holder continuity of the new integrand.

Although the randomization idea is not new, such an approach of randomization is, to the best of our knowledge, new in the sampling area and brings several benefits:

  • Comparison with Euler-type algorithms. For existing works on the overdamped LMC, gradient Lipschitz and Hessian Lipschitz conditions ensure an error bound O(dh)O(d h) in a non-log-concavity setting. Instead, our randomized methods give an error bound O(dh1.5)O(d h^{1.5}) under the same smoothness conditions.
  • Comparison with higher-order algorithms. To derive the convergence order 1.51.5 for existing Taylor or Runge-Kutta higher-order schemes, additional smoothness of the 3rd derivative is required, leading to the dimension dependence d32d^{\frac32} or even worse. Instead, our randomized methods improves the state-of-the-art convergence order O(d32h32)O(d^{\frac32} h^{\frac32}) to O(dh1.5)O(d h^{1.5}), just under gradient Lipschitz and Hessian Lipschitz conditions.
  • Comparison with other randomized methods. Existing randomized methods are based on Euler-type schemes, while we propose randomized Taylor/Runge-Kutta methods here, which achieve a better convergence rate under an additional Hessian Lipschitz condition. For the underdamped case, the integrands only involves with the position, which enjoys order 11 mean-square Holder continuity (in contrast to order 12\tfrac12 for the velocity). Therefore, the randomized midpoint (Euler) for ULD gives order 1.51.5. Applying our approach of randomization to the underdamped case would promote to order 2.52.5, which is an ongoing project.

In the revision, we will make related comments and compare theoretical results with existing methods, listed in a table (see Table 1).

Response to Comment 2: Thanks. In the revision, we give an interpretation of Proposition 3.3 (Proposition 3.6 now in the revision) and also provide a detailed constant C(T)C(T), which exponentially depends on TT. The exponential ergodicity of Langevin dynamics and the uniform-in-time moment bounds, however, would transfer finite-time error estimates to uniform-in-time ones.

Response to Comment 3: Thanks! In the revision, we add (in Appendix D) some details on how to sample from the three involved correlated Gaussians ξ1:=Wk(tn+1)−Wk(tn+δh),ξ2:=Wk(tn+δh)−Wk(tn),ξ3:=∫tntn+1∫tntdWk(s)dt\xi_1 := W_k(t_{n+1})-W_k(t_n+\delta h), \xi_2 := W_k(t_n+\delta h)-W_k(t_n), \xi_3 : = \int_{t_n}^{t_{n+1}}\int_{t_n}^{t} \mathrm{d}W_k(s)dt for δ∈(0,1)\delta \in (0, 1), with a covariance matrix Σh\Sigma_h given. In short, given ζ1,ζ2,ζ3∼i.i.d.N(0,1),\zeta_1,\zeta_2,\zeta_3\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,1), ξ1,ξ2,ξ3\xi_1, \xi_2, \xi_3 can be generated explicitly as follows: ξ1=(1−δ)hζ1,ξ2=δhζ2,ξ3=(1−δ)h2ζ1+h(1−δ2)ζ2+h3/21−3δ+3δ212ζ3.\xi_1=\sqrt{(1-\delta)h}\zeta_1,\quad \xi_2=\sqrt{\delta h}\zeta_2,\quad \xi_3=\tfrac{(1-\delta)h}{2}\zeta_1+h\left(1-\tfrac{\delta}{2}\right)\zeta_2+h^{3/2}\sqrt{\tfrac{1-3\delta+3\delta^2}{12}}\zeta_3. As different components are mutually independent, the random vectors can be sampled easily.

Comments: I am looking ...

Response: Thanks. We have tried out best to revise the manuscript and hope you would find it satisfactory. Please let us know if you have any concerns or questions.

About Questions For Authors

Response: Many thanks for this interesting question. We have checked the shifted composition framework of [1], which we think also works for the proposed scheme. But it is not a focus of this paper and we leave it for future study.

Many thanks for the rebuttal.

The table is very informative, which is the main reason why I increased my rating. However, the formatting of the paper needs improvement. For example, "Paper A/B/C" looks weird.

I was also expecting a comparison of the methods because randomization is not a new idea. Only through a comparison between the proposed methods and the randomized midpoint method from the methodological perspective can this work be correctly positioned in the literature and the novelty of the proposed method be established.

AuthorsOpenReview ↗

Many thanks for increasing the rating

Thanks a lot for your quick response and for increasing the rating. Following your suggestions, we do not use "Paper A/B/C" and use, e.g., "CB18" to mention the reference "Cheng & Bartlett (2018)". We updated the revised manuscript (already submitted). As commented by reviewer vUEC: "The authors propose some interesting additions to the recent literature on Langevin diffusion-based algorithms". Roughly speaking, we combine the existing randomization idea with the Taylor expansion to construct higher-order randomized schemes. Compared with the existing randomized midpoint scheme, our schemes achieve a better convergence rate w.r.t the stepsize, under an additional Hessian Lipschitz condition. Sincerely hope you can re-evaluate our contributions. Thanks a million! Please let us know if you have any further concerns.

Reviewer_vUECOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper investigates the problem of sampling from a smooth density defined on the dd-dimensional Euclidean space. The authors propose some interesting additions to the recent literature on Langevin diffusion-based algorithms. More precisely, they propose two new discretization schemes that take advantage of the second-order smoothness of the log-density and involve an external randomization in the spirit of Shen and Lee (NeurIPS 2019). The main results obtained in the paper are valid under the following conditions:

  1. The log-density is Gradient-Lipschitz
  2. The Hessian of the log-density is Lipschitz as well
  3. The log-density satisfies the dissipativity condition
  4. The target density satisfies the log-Sobolev inequality

Under these assumptions, and assuming that all the constants involved in these assumptions are dimension-free, the paper shows that the Wasserstein-2 error of the proposed sampling schemes is bounded by Cdh3/2+Cde−λnhC d h^{3/2} + C \sqrt{d}e^{-\lambda n h}, where hh is the step-size and nn is the number of iterations.

The paper also contains some numerical experiments illustrating the behaviour of the introduced sampling schemes.

Critical strengths
  1. The paper introduces some new variants of the randomized mid-point LMC algorithm that are suitable in the case where the potential has a Hessian and the Hessian is Lipschitz continuous.
  2. The upper bounds obtained for the errors demonstrate an improved dependence on the dimension and the step-size.
Critical weaknesses

I don't see any critical weakness that would justify the rejection of the paper. But I provide below some limitations that somewhat justify the assessment that I gave.

  1. There might be useful to provide a discussion on the assumption that all the involved constants are dimension-free. Some examples might be useful.
  2. In the discussion of the second paragraph of page 2, I suggest to add the recent result by Pedrotti and Whalley https://arxiv.org/abs/2608.02430
  3. When discussing available upper bounds under second-order regularity, it might be useful to mention the result obtained for the KLMC2 scheme by Ruou-Durand and Dalallyan https://arxiv.org/pdf/1807.09382
Questions for authors

Can you provide a family of distributions that naturally appear in ML or Statistics, or another scientific field where the problem of sampling is relevant, and for which all the assumptions are satisfied with dimension-free constants?

Related to the previous question, my suggestion would be to consider the example of a potential that is strongly convex outside a ball of radius RR. It would be interesting to see how the constants depend on RR.

1 comment
AuthorsOpenReview ↗

Response to Reviewer vUEC

Thank you for the review. All your comments/suggestions will be carefully taken into account when revising the manuscript.

About Critical Weaknesses

Response: Thank you for your comments. Below, we respond to each point in turn.

  1. Thank you for your comment. We have provided an example of sampling problems to illustrate this assumption. Please see our response to the question below for details.
  2. Thank you for this suggestion. We have added the recent result by Pedrotti and Whalley (arxiv:2608.02430), together with a brief discussion of its result in the revised manuscript.
  3. We sincerely thank the reviewer for bringing this relevant work to our attention. Following the reviewer's suggestion, we have added a discussion of the KLMC2 result by Dalalyan and Riou-Durand (2018) in the Introduction, immediately after the discussion of the Hessian Lipschitz. This addition provides a more comprehensive overview of existing convergence results under second-order regularity assumptions.

About Questions For Authors

Response: Many thanks for your helpful questions. We have identified a concrete family of non-log-concave target distributions arising from the Bayesian binary classification model studied in Section 5.3 of Wang et al. (2026):

[Wang, Wang and Zhu. 2026], Sampling Non-Log-Concave Densities via Hessian-Free High-Resolution Dynamics (https://arxiv.org/abs/2601.02725).

We show that this family satisfies all our assumptions, including dissipativity, Lipschitz continuity of the gradient and Hessian, and the log-Sobolev inequality, with constants independent of the dimension.

In the revised manuscript, we have introduced this example and provided a detailed verification of all the required assumptions in Appendix C. Unfortunately, this example does not satisfy the strong convexity outside a ball of radius RR, which might make the constant exponentially depend on RR. Due to limited time, we would leave the interesting question for future work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.