High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm

Recent years have seen substantial progress in the theoreti cal analysis of algorithms for large-scale statistical inference. For both the optimization alg orithms of frequentist inference and the sampling algorithms that underpin Bayesian inference,nonasymptotic rates of convergence have been obtained and, increasingly, those rates include d imension dependence [see, e.g., 8, 11, 9, 7, 5, 12, 18, 4 ]. In particular, for the gradient-based algorithms that ha ve become the state-of-the-art in many large-scale applications, the di mension dependence is generally linear or sublinear, providing strong theoretical support for the deployment of these algorithms in large-scale problems. Although progress has been made in both optimization and sam pling, the latter has lagged the former, arguably because of the inherent stochasticity of the sampling paradigm. Indeed, much of the recent progress in both paradigms has involved ta king a continuous-time point of view, whereby algorithms are obtained as discretizations o f underlying continuous dynamical systems, and this line of attack is more challenging for samp ling methods. For optimization algorithms the continuous dynamics can be represented as ordinary differential equations (ODEs) [ 3, 27, 29, 24 ], whereas the underlying dynamics are characterized as sto chastic differential equations (SDEs) in the case of sampling algorithms [ 23, 8, 11 ]. The non-smooth nature of the Brownian motion underlying these SDEs raises fundame ntal challenges in carrying out the discretization that is needed to transfer the continuou s-time results to discrete time.