A splitting Hamiltonian Monte Carlo method for efficient sampling

We propose a splitting Hamiltonian Monte Carlo (SHMC) algorithm, which can be numerically and computationally efficient when combined with the random mini-batch strategy. By splitting the "effective potential energy" $U\propto -\beta^{-1}\log \rho$ into two parts $U = U_1 + U_2$, one makes a proposal using the "easy-to-sample" part $U_1$, followed by probabilistically accepting that proposal by a Metropolis rejection step using $U_2$. The splitting allows efficient sampling from systems with singular potentials (or distributions with degenerate points) and/or with multiple potential barriers. In our SHMC algorithm, the proposal using $U_1$ is generated by the Hamiltonian dynamics, which can be potentially more efficient than the overdamped Langevin dynamics. We also use random batch strategies to reduce the computational cost to $\mathcal{O}(1)$ per time step in generating the proposals for problems arising from many-body systems and Bayesian inference, and prove that the errors of the Hamiltonian induced by the random batch approximation is $\mathcal{O}(\sqrt{\Delta t})$ in the strong and $\mathcal{O}(\Delta t)$ in the weak sense, where $\Delta t$ is the time step. Numerical experiments are conducted to verify the theoretical results and the computational efficiency of the proposed algorithms in practice.