GMOS Weekly Seminar: Runtimes of Metropolized Sampling Methods for Well-Conditioned Distributions

Metropolis-adjusted Langevin algorithm (MALA) and Metropolized Hamiltonian Monte Carlo (HMC) are two of the most popular sampling methods in practice. In this talk, I will present some upper and lower bounds on the query complexity of MALA and HMC. For MALA and one-step HMC starting from exponential warm starts, the upper and lower bounds match up to logarithmic factors. Our upper bound is the first high-accuracy mixing time result for well-conditioned distributions that achieves linear dependence on the condition number. A key ingredient in our proof is a concentration bound on the gradient norm of strongly convex and smooth function f for x~exp(-f(x)), which may be of independent interest.