High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
This provides an accelerated sampling method for machine learning and statistics, though it is incremental as it builds on higher-order dynamics.
The paper tackles the problem of sampling from log-concave and smooth distributions by proposing a third-order Langevin dynamics MCMC algorithm, achieving a mixing time of O(d^{1/4}/ε^{1/2}) for generalized linear models and O(d^{1/4}/ε^{1/2} + d^{1/2}/ε^{1/(α-1)}) for general strongly convex potentials.
We propose a Markov chain Monte Carlo (MCMC) algorithm based on third-order Langevin dynamics for sampling from distributions with log-concave and smooth densities. The higher-order dynamics allow for more flexible discretization schemes, and we develop a specific method that combines splitting with more accurate integration. For a broad class of $d$-dimensional distributions arising from generalized linear models, we prove that the resulting third-order algorithm produces samples from a distribution that is at most $\varepsilon > 0$ in Wasserstein distance from the target distribution in $O\left(\frac{d^{1/4}}{ \varepsilon^{1/2}} \right)$ steps. This result requires only Lipschitz conditions on the gradient. For general strongly convex potentials with $α$-th order smoothness, we prove that the mixing time scales as $O \left(\frac{d^{1/4}}{\varepsilon^{1/2}} + \frac{d^{1/2}}{\varepsilon^{1/(α- 1)}} \right)$.