Abstract
We study the problem of using the Metropolis-adjusted Langevin algorithm (MALA) to sample from a log-smooth and strongly log-concave distribution in dimension $d$ with condition number $\kappa$. We establish its optimal minimax mixing time under a warm start. First, we demonstrate that MALA with a warm start mixes in $O(d^{1/2} \kappa)$ iterations up to logarithmic factors; this improves upon the previous work on the dependency of either the condition number $\kappa$ or the dimension $d$. Our proof relies on comparing the leapfrog integrator with the continuous Hamiltonian dynamics, where we establish a new concentration bound for the acceptance rate. Second, we provide an explicit mixing time lower bound for reversible MCMC algorithms on general state spaces. We use this result to show that MALA requires at least $\Omega(d^{1/2} \kappa)$ steps in the worst case, matching our upper bound in terms of both the condition number and the dimension. This is joint work with Keru Wu and Scott Schmidler.