Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling
This provides a theoretical foundation for efficient sampling in high-dimensional statistics and machine learning, with incremental improvements in mixing time bounds.
The paper tackles the problem of sampling from log-concave distributions using the Metropolis-adjusted Langevin algorithm (MALA), establishing an optimal minimax mixing time of $ ilde O(\kappa\sqrt{d})$ iterations, which improves upon previous dependencies on condition number $\kappa$ or dimension $d$, and includes a matching lower bound.
We study the mixing time of the Metropolis-adjusted Langevin algorithm (MALA) for sampling from a log-smooth and strongly log-concave distribution. We establish its optimal minimax mixing time under a warm start. Our main contribution is two-fold. First, for a $d$-dimensional log-concave density with condition number $κ$, we show that MALA with a warm start mixes in $\tilde O(κ\sqrt{d})$ iterations up to logarithmic factors. This improves upon the previous work on the dependency of either the condition number $κ$ 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 prove a spectral gap based mixing time lower bound for reversible MCMC algorithms on general state spaces. We apply this lower bound result to construct a hard distribution for which MALA requires at least $\tilde Ω(κ\sqrt{d})$ steps to mix. The lower bound for MALA matches our upper bound in terms of condition number and dimension. Finally, numerical experiments are included to validate our theoretical results.