Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
This provides theoretical limits for widely used sampling methods in statistics and machine learning, addressing an open question and confirming the necessity of dimension scaling, which is incremental but clarifies fundamental performance constraints.
The paper establishes lower bounds on mixing times for Metropolis-adjusted Langevin algorithm (MALA) and Hamiltonian Monte Carlo (HMC) applied to well-conditioned distributions, showing a nearly-tight bound of Ω̃(κd) for MALA and polynomial dimension dependence for HMC, matching prior algorithmic results up to logarithmic factors.
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Ω(κd)$ on the mixing time of MALA from an exponentially warm start, matching a line of algorithmic results up to logarithmic factors and answering an open question of Chewi et. al. We also show that a polynomial dependence on dimension is necessary for the relaxation time of HMC under any number of leapfrog steps, and bound the gains achievable by changing the step count. Our HMC analysis draws upon a novel connection between leapfrog integration and Chebyshev polynomials, which may be of independent interest.