Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo

Understand

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.