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

We study the problem of sampling from strongly log-concave distributions over R 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 (W 2 ), 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 W 2 convergence is much smaller than the complexity lower bounds for convergence in L 2 strong error established in the literature. However, sampling algorithm guarantees consider 'weak errors' which are distances between Law(U T (ω)) and Law(A(f, ω, ω)). In particular, the Wasserstein-2 distance is the infimum of L 2 errors when U T is driven by B t (ω) and A(•) queries B ′ t (ω) over all couplings of distinct Brown-