Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm

Conventional wisdom in the sampling literature, backed by a popular diffusion\nscaling limit, suggests that the mixing time of the Metropolis-Adjusted\nLangevin Algorithm (MALA) scales as $O(d^{1/3})$, where $d$ is the dimension.\nHowever, the diffusion scaling limit requires stringent assumptions on the\ntarget distribution and is asymptotic in nature. In contrast, the best known\nnon-asymptotic mixing time bound for MALA on the class of log-smooth and\nstrongly log-concave distributions is $O(d)$. In this work, we establish that\nthe mixing time of MALA on this class of target distributions is\n$\\widetilde\\Theta(d^{1/2})$ under a warm start. Our upper bound proof\nintroduces a new technique based on a projection characterization of the\nMetropolis adjustment which reduces the study of MALA to the well-studied\ndiscretization analysis of the Langevin SDE and bypasses direct computation of\nthe acceptance probability.\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC