# Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond

arXiv: https://arxiv.org/abs/1906.07868 · HTML: https://mlsanity.com/paper/1906.07868/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2019.

## Built on by (most cited first, 30 of 33)

- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [Convex Analysis of the Mean Field Langevin Dynamics](https://mlsanity.com/paper/2201.10469/) (2022)
- [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025)
- [The Mirror Langevin Algorithm Converges with Vanishing Bias](https://mlsanity.com/paper/2109.12077/) (2021)
- [Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequality](https://mlsanity.com/paper/2303.03589/) (2023)
- [Improved Discretization Analysis for Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2302.08049/) (2023)
- [Sqrt(d) Dimension Dependence of Langevin Monte Carlo](https://mlsanity.com/paper/2109.03839/) (2021)
- [Self-Consistency of the Fokker-Planck Equation](https://mlsanity.com/paper/2206.00860/) (2022)
- [On Convergence of Federated Averaging Langevin Dynamics](https://mlsanity.com/paper/2112.05120/) (2021)
- [Fisher information lower bounds for sampling](https://mlsanity.com/paper/2210.02482/) (2022)
- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [Interacting Contour Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2202.09867/) (2022)
- [Constrained Exploration via Reflected Replica Exchange Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2405.07839/) (2024)
- [Heavy-tailed Sampling via Transformed Unadjusted Langevin Algorithm](https://mlsanity.com/paper/2201.08349/) (2022)
- [A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers](https://mlsanity.com/paper/2405.16736/) (2024)
- [The Poisson Midpoint Method for Langevin Dynamics: Provably Efficient Discretization for Diffusion Models](https://mlsanity.com/paper/2405.17068/) (2024)
- [Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models](https://mlsanity.com/paper/2412.07435/) (2024)
- [Score-based Diffusion Models for Bayesian Image Reconstruction](https://mlsanity.com/paper/2305.16482/) (2023)
- [Mean-Square Analysis of Discretized Ito Diffusions for Heavy-tailed Sampling](https://mlsanity.com/paper/2303.00570/) (2023)
- [Langevin Quasi-Monte Carlo](https://mlsanity.com/paper/2309.12664/) (2023)
- [Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias](https://mlsanity.com/paper/2408.13115/) (2024)
- [Generative Modelling of L'evy Area for High Order SDE Simulation](https://mlsanity.com/paper/2308.02452/) (2023)
- [Single-seed generation of Brownian paths and integrals for adaptive and high order SDE solvers](https://mlsanity.com/paper/2405.06464/) (2024)
- [Mirror Mean-Field Langevin Dynamics](https://mlsanity.com/paper/2505.02621/) (2025)
- [Anchored Langevin Algorithms](https://mlsanity.com/paper/2509.19455/) (2025)
- [A Dynamical System View of Langevin-Based Non-Convex Sampling](https://mlsanity.com/paper/2210.13867/) (2022)
- [Mean-field underdamped Langevin dynamics and its spacetime discretization](https://mlsanity.com/paper/2312.16360/) (2023)
- [Higher Order Generalization Error for First Order Discretization of Langevin Diffusion](https://mlsanity.com/paper/2102.06229/) (2021)
- [When Langevin Monte Carlo Meets Randomization: New Sampling Algorithms with Non-asymptotic Error Bounds beyond Log-Concavity and Gradient Lipschitzness](https://mlsanity.com/paper/2509.25630/) (2025)
- [Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD](https://mlsanity.com/paper/2604.10373/) (2026)

## Abstract (arXiv)

Sampling with Markov chain Monte Carlo methods often amounts to discretizing some continuous-time dynamics with numerical integration. In this paper, we establish the convergence rate of sampling algorithms obtained by discretizing smooth Ito diffusions exhibiting fast Wasserstein-2 contraction, based on local deviation properties of the integration scheme. In particular, we study a sampling algorithm constructed by discretizing the overdamped Langevin diffusion with the method of stochastic Runge-Kutta. For strongly convex potentials that are smooth up to a certain order, its iterates converge to the target distribution in 2-Wasserstein distance in tildeO(dε-2/3) iterations. This improves upon the best-known rate for strongly log-concave sampling based on the overdamped Langevin equation using only the gradient oracle without adjustment. In addition, we extend our analysis of stochastic Runge-Kutta methods to uniformly dissipative diffusions with possibly non-convex potentials and show they achieve better rates compared to the Euler-Maruyama scheme in terms of the dependence on tolerance ε. Numerical studies show that these algorithms lead to better stability and lower asymptotic errors.