  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.
