# Poisson Midpoint Method for Log Concave Sampling: Beyond the Strong Error Lower Bounds

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 33 references that are in the map.
- First posted on arXiv 9 Jun 2025.

## Builds on (most cited first, 20 of 20)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [Convergence of Langevin MCMC in KL-divergence](https://mlsanity.com/paper/1705.09048/) (2017)
- [The Randomized Midpoint Method for Log-Concave Sampling](https://mlsanity.com/paper/1909.05503/) (2019)
- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [On sampling from a log-concave density using kinetic Langevin diffusions](https://mlsanity.com/paper/1807.09382/) (2018)
- [On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness](https://mlsanity.com/paper/2005.13097/) (2020)
- [Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence](https://mlsanity.com/paper/2007.11612/) (2020)
- [Improved Bounds for Discretization of Langevin Diffusions: Near-Optimal Rates without Convexity](https://mlsanity.com/paper/1907.11331/) (2019)
- [Improved Discretization Analysis for Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2302.08049/) (2023)
- [Faster Differentially Private Samplers via R'enyi Divergence Analysis of Discretized Langevin MCMC](https://mlsanity.com/paper/2010.14658/) (2020)
- [On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method](https://mlsanity.com/paper/2011.03176/) (2020)
- [Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited](https://mlsanity.com/paper/2306.08494/) (2023)
- [Shifted Composition III: Local Error Framework for KL Divergence](https://mlsanity.com/paper/2412.17997/) (2024)
- [The Poisson Midpoint Method for Langevin Dynamics: Provably Efficient Discretization for Diffusion Models](https://mlsanity.com/paper/2405.17068/) (2024)

## Abstract (arXiv)

We study the problem of sampling from strongly log-concave distributions over ℝd using the Poisson midpoint discretization (a variant of the randomized midpoint method) for overdamped/underdamped Langevin dynamics. We prove its convergence in the 2-Wasserstein distance (W2), achieving a cubic speedup in dependence on the target accuracy (ε) over the Euler-Maruyama discretization, surpassing existing bounds for randomized midpoint methods. Notably, in the case of underdamped Langevin dynamics, we demonstrate the complexity of W2 convergence is much smaller than the complexity lower bounds for convergence in L2 strong error established in the literature.