Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm

MaRDI QIDQ6356818arXivFDO

Authors Sinho Chewi, Chen Lu, Kwangjun Ahn, Xiang Cheng, Thibaut Le Gouic, Philippe Rigollet

Publication date 23 December 2020

Published in arXiv

arXiv classification

cs.LGmath.STstat.TH

Abstract: 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 $widetildeTheta(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.

Cited in

(1)

• Exact simulation of diffusions and improved algorithms for log-concave sampling

This page was built for publication: Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6356818)