论文标题
大都会调整后的兰格文算法的最佳维度依赖性
Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm
论文作者
论文摘要
取样文献中的传统智慧在流行的扩散缩放限制的支持下表明，大都会调整后的Langevin算法（MALA）的混合时间为$ O（d^{1/3}）$，其中$ d $是尺寸。但是，扩散缩放极限需要对目标分布进行严格的假设，并且本质上是渐近的。相比之下，在日志平滑和强烈的对数符号分布的类别上，最著名的非质子混合时间是$ O（d）$。在这项工作中，我们确定MALA在此类目标分布上的混合时间为$ \widetildeθ（d^{1/2}）$在温暖的开始下。我们的上限证明基于大都市调整的投影表征引入了一项新技术，该技术将MALA的研究降低到对Langevin SDE的经过良好研究的离散化分析，并绕过对接受概率的直接计算。
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.
