  Hamiltonian Monte Carlo (HMC) has been widely adopted in the statistics
community because of its ability to sample high-dimensional distributions much
more efficiently than other Metropolis-based methods. Despite this, HMC often
performs sub-optimally on distributions with high correlations or marginal
variances on multiple scales because the resulting stiffness forces the
leapfrog integrator in HMC to take an unreasonably small stepsize. We provide
intuition as well as a formal analysis showing how these multiscale
distributions limit the stepsize of leapfrog and we show how the implicit
midpoint method can be used, together with Newton-Krylov iteration, to
circumvent this limitation and achieve major efficiency gains. Furthermore, we
offer practical guidelines for when to choose between implicit midpoint and
leapfrog and what stepsize to use for each method, depending on the
distribution being sampled. Unlike previous modifications to HMC, our method is
generally applicable to highly non-Gaussian distributions exhibiting multiple
scales. We illustrate how our method can provide a dramatic speedup over
leapfrog in the context of the No-U-Turn sampler (NUTS) applied to several
examples.
