Poisson Midpoint Method for Log Concave Sampling: Beyond the Strong Error Lower Bounds
This provides improved sampling algorithms for high-dimensional statistical inference, though it is incremental as it builds on existing randomized midpoint methods.
The paper tackles sampling from strongly log-concave distributions using the Poisson midpoint method for Langevin dynamics, achieving a cubic speedup in accuracy dependence over Euler-Maruyama discretization and demonstrating complexity below strong error lower bounds for underdamped dynamics.
We study the problem of sampling from strongly log-concave distributions over $\mathbb{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.