Lower Bounds on Metropolized Sampling Methods for Well-Conditioned
Distributions
Lower Bounds on Metropolized Sampling Methods for Well-Conditioned
Distributions
We give lower bounds on the performance of two of the most popular sampling methods in practice, the Metropolis-adjusted Langevin algorithm (MALA) and multi-step Hamiltonian Monte Carlo (HMC) with a leapfrog integrator, when applied to well-conditioned distributions. Our main result is a nearly-tight lower bound of $\widetilde{\Omega}(\kappa d)$ on the …