  We propose a new framework of variance-reduced Hamiltonian Monte Carlo (HMC)
methods for sampling from an $L$-smooth and $m$-strongly log-concave
distribution, based on a unified formulation of biased and unbiased variance
reduction methods. We study the convergence properties for HMC with gradient
estimators which satisfy the Mean-Squared-Error-Bias (MSEB) property. We show
that the unbiased gradient estimators, including SAGA and SVRG, based HMC
methods achieve highest gradient efficiency with small batch size under high
precision regime, and require $\tilde{O}(N + \kappa^2 d^{\frac{1}{2}}
\varepsilon^{-1} + N^{\frac{2}{3}} \kappa^{\frac{4}{3}} d^{\frac{1}{3}}
\varepsilon^{-\frac{2}{3}} )$ gradient complexity to achieve
$\epsilon$-accuracy in 2-Wasserstein distance. Moreover, our HMC methods with
biased gradient estimators, such as SARAH and SARGE, require
$\tilde{O}(N+\sqrt{N} \kappa^2 d^{\frac{1}{2}} \varepsilon^{-1})$ gradient
complexity, which has the same dependency on condition number $\kappa$ and
dimension $d$ as full gradient method, but improves the dependency of sample
size $N$ for a factor of $N^\frac{1}{2}$. Experimental results on both
synthetic and real-world benchmark data show that our new framework
significantly outperforms the full gradient and stochastic gradient HMC
approaches. The earliest version of this paper was submitted to ICML 2020 with
three weak accept but was not finally accepted.
