Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm
This work provides a tighter theoretical understanding of MALA's performance for practitioners and researchers working with high-dimensional sampling problems, offering a more accurate complexity estimate.
This paper investigates the mixing time of the Metropolis-Adjusted Langevin Algorithm (MALA) for log-smooth and strongly log-concave distributions. It establishes that the mixing time is \u03f4(d^1/2) under a warm start, improving upon the previously known non-asymptotic bound of O(d) and refining the conventional wisdom of O(d^1/3).
Conventional wisdom in the sampling literature, backed by a popular diffusion scaling limit, suggests that the mixing time of the Metropolis-Adjusted Langevin Algorithm (MALA) scales as $O(d^{1/3})$, where $d$ is the dimension. However, the diffusion scaling limit requires stringent assumptions on the target distribution and is asymptotic in nature. In contrast, the best known non-asymptotic mixing time bound for MALA on the class of log-smooth and strongly log-concave distributions is $O(d)$. In this work, we establish that the mixing time of MALA on this class of target distributions is $\widetildeΘ(d^{1/2})$ under a warm start. Our upper bound proof introduces a new technique based on a projection characterization of the Metropolis adjustment which reduces the study of MALA to the well-studied discretization analysis of the Langevin SDE and bypasses direct computation of the acceptance probability.