Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo
This provides a theoretical foundation for the efficiency of a widely used sampling method in high-dimensional statistics and machine learning, with applications such as Bayesian logistic regression, though it is incremental as it confirms a long-standing conjecture under specific conditions.
The paper proves that second-order Hamiltonian Monte Carlo (HMC) with leapfrog integration runs in d^{1/4} gradient evaluations for sampling from strongly log-concave distributions under a weak third-order regularity condition, improving upon previous bounds of d^{1/2} and showing better performance in simulations.
Hamiltonian Monte Carlo (HMC) is a widely deployed method to sample from high-dimensional distributions in Statistics and Machine learning. HMC is known to run very efficiently in practice and its popular second-order "leapfrog" implementation has long been conjectured to run in $d^{1/4}$ gradient evaluations. Here we show that this conjecture is true when sampling from strongly log-concave target distributions that satisfy a weak third-order regularity property associated with the input data. Our regularity condition is weaker than the Lipschitz Hessian property and allows us to show faster convergence bounds for a much larger class of distributions than would be possible with the usual Lipschitz Hessian constant alone. Important distributions that satisfy our regularity condition include posterior distributions used in Bayesian logistic regression for which the data satisfies an "incoherence" property. Our result compares favorably with the best available bounds for the class of strongly log-concave distributions, which grow like $d^{{1}/{2}}$ gradient evaluations with the dimension. Moreover, our simulations on synthetic data suggest that, when our regularity condition is satisfied, leapfrog HMC performs better than its competitors -- both in terms of accuracy and in terms of the number of gradient evaluations it requires.