mlsanityData to 14 Oct 2026

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

arXiv 2506.07614 ↗First posted 9 Jun 2025math.PR cs.LG math.STcited by 0

Not on the map. Why?

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.

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

20 of 33 references.

References · 20

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2017A Tutorial on Thompson Samplingcited by 433
  3. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 227
  4. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 208
  5. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 197
  6. 2017Underdamped Langevin MCMC: A non-asymptotic analysiscited by 133
  7. 2018Analysis of Langevin Monte Carlo via convex optimizationcited by 127
  8. 2017Convergence of Langevin MCMC in KL-divergencecited by 88
  9. 2019The Randomized Midpoint Method for Log-Concave Samplingcited by 78
  10. 2022Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlocited by 63
  11. 2018On sampling from a log-concave density using kinetic Langevin diffusionscited by 62
  12. 2020On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothnesscited by 55
8 more
  1. 2020Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergencecited by 42
  2. 2019Improved Bounds for Discretization of Langevin Diffusions: Near-Optimal Rates without Convexitycited by 39
  3. 2023Improved Discretization Analysis for Underdamped Langevin Monte Carlocited by 28
  4. 2020Faster Differentially Private Samplers via R'enyi Divergence Analysis of Discretized Langevin MCMCcited by 27
  5. 2020On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Methodcited by 23
  6. 2023Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisitedcited by 10
  7. 2024Shifted Composition III: Local Error Framework for KL Divergencecited by 7
  8. 2024The Poisson Midpoint Method for Langevin Dynamics: Provably Efficient Discretization for Diffusion Modelscited by 6

Built on by

Not cited yet.