The Department of Mathematical Sciences will host Dr. Yuansi Chen from the Department of Statistical Sciences at Duke University, for its math seminar series. Dr. Chen will present, “Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-concave Sampling.” This free seminar will take place on Friday, February 25, at 11 a.m. in BSB 132. A virtual option is also available: https://tinyurl.com/9nrnveur.
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