  We consider the problem of sampling from a strongly log-concave density in
$\mathbb{R}^d$, and prove a non-asymptotic upper bound on the mixing time of
the Metropolis-adjusted Langevin algorithm (MALA). The method draws samples by
simulating a Markov chain obtained from the discretization of an appropriate
Langevin diffusion, combined with an accept-reject step. Relative to known
guarantees for the unadjusted Langevin algorithm (ULA), our bounds show that
the use of an accept-reject step in MALA leads to an exponentially improved
dependence on the error-tolerance. Concretely, in order to obtain samples with
TV error at most $\delta$ for a density with condition number $\kappa$, we show
that MALA requires $\mathcal{O} \big(\kappa d \log(1/\delta) \big)$ steps, as
compared to the $\mathcal{O} \big(\kappa^2 d/\delta^2 \big)$ steps established
in past work on ULA. We also demonstrate the gains of MALA over ULA for weakly
log-concave densities. Furthermore, we derive mixing time bounds for the
Metropolized random walk (MRW) and obtain $\mathcal{O}(\kappa)$ mixing time
slower than MALA. We provide numerical examples that support our theoretical
findings, and demonstrate the benefits of Metropolis-Hastings adjustment for
Langevin-type sampling algorithms.
