Abstract
We propose a Markov chain Monte Carlo (MCMC) algorithm based on third-order Langevin dynamics for sampling from distributions with smooth, log-concave 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(d^{1/4} / \varepsilon^{1/2}) steps. This result requires only Lipschitz conditions on the gradient. For general strongly convex potentials with \alpha-th order smoothness, we prove that the mixing time scales as O(d^{1/4} / \varepsilon^{1/2} + d^{1/2} / \varepsilon^{1 / (\alpha - 1)}). Joint work with Yi-An Ma, Martin J. Wainwright, Peter L. Bartlett, and Michael I. Jordan.