# The Randomized Midpoint Method for Log-Concave Sampling

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

## Key facts

- Cited by 78 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2019.

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

- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Parallel Sampling of Diffusion Models](https://mlsanity.com/paper/2305.16317/) (2023)
- [Variational inference via Wasserstein gradient flows](https://mlsanity.com/paper/2205.15902/) (2022)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Fast Solvers for Discrete Diffusion Models: Theory and Applications of High-Order Algorithms](https://mlsanity.com/paper/2502.00234/) (2025)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [ScoreGrad: Multivariate Probabilistic Time Series Forecasting with Continuous Energy-based Generative Models](https://mlsanity.com/paper/2106.10121/) (2021)
- [Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity](https://mlsanity.com/paper/2405.15986/) (2024)
- [Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequality](https://mlsanity.com/paper/2303.03589/) (2023)
- [Accelerated Diffusion Models via Speculative Sampling](https://mlsanity.com/paper/2501.05370/) (2025)
- [Improved dimension dependence of a proximal algorithm for sampling](https://mlsanity.com/paper/2302.10081/) (2023)
- [Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel](https://mlsanity.com/paper/2406.00924/) (2024)
- [Beyond Log-Concavity and Score Regularity: Improved Convergence Bounds for Score-Based Generative Models in W2-distance](https://mlsanity.com/paper/2501.02298/) (2025)
- [Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space](https://mlsanity.com/paper/2202.01908/) (2022)
- [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)
- [A Proximal Algorithm for Sampling from Non-smooth Potentials](https://mlsanity.com/paper/2110.04597/) (2021)
- [A Proximal Algorithm for Sampling](https://mlsanity.com/paper/2202.13975/) (2022)
- [Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling](https://mlsanity.com/paper/2210.08448/) (2022)
- [A Convergence Theory for SVGD in the Population Limit under Talagrand's Inequality T1](https://mlsanity.com/paper/2106.03076/) (2021)
- [Sampling via Gradient Flows in the Space of Probability Measures](https://mlsanity.com/paper/2310.03597/) (2023)
- [Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions](https://mlsanity.com/paper/2106.05480/) (2021)
- [Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion](https://mlsanity.com/paper/2402.17886/) (2024)
- [The query complexity of sampling from strongly log-concave distributions in one dimension](https://mlsanity.com/paper/2105.14163/) (2021)
- [Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition](https://mlsanity.com/paper/2206.00508/) (2022)
- [When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?](https://mlsanity.com/paper/2304.04724/) (2023)
- [On Convergence of Federated Averaging Langevin Dynamics](https://mlsanity.com/paper/2112.05120/) (2021)
- [Chain of Log-Concave Markov Chains](https://mlsanity.com/paper/2305.19473/) (2023)
- [Error bounds for particle gradient descent, and extensions of the log-Sobolev and Talagrand inequalities](https://mlsanity.com/paper/2403.02004/) (2024)
- [When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint](https://mlsanity.com/paper/2110.01827/) (2021)

## Abstract (arXiv)

Sampling from log-concave distributions is a well researched problem that has many applications in statistics and machine learning. We study the distributions of the form p*proptoexp(-f(x)), where f:ℝdrightarrowℝ has an L-Lipschitz gradient and is m-strongly convex. In our paper, we propose a Markov chain Monte Carlo (MCMC) algorithm based on the underdamped Langevin diffusion (ULD). It can achieve ε· D error (in 2-Wasserstein distance) in tildeOleft(kappa7/6/ε1/3+kappa/ε2/3right) steps, where Doversetdef=√fracdm is the effective diameter of the problem and kappaoversetdef=fracLm is the condition number. Our algorithm performs significantly faster than the previously best known algorithm for solving this problem, which requires tildeOleft(kappa1.5/εright) steps. Moreover, our algorithm can be easily parallelized to require only O(kappalogfrac1ε) parallel steps. To solve the sampling problem, we propose a new framework to discretize stochastic differential equations. We apply this framework to discretize and simulate ULD, which converges to the target distribution p*. The framework can be used to solve not only the log-concave sampling problem, but any problem that involves simulating (stochastic) differential equations.