To sample from a given target distribution, Markov chain Monte Carlo (MCMC) sampling relies on constructing an ergodic Markov chain with the target distribution as its invariant measure. For any MCMC method, an important question is how to evaluate its efficiency. One approach is to consider the associated empirical measure and how fast it converges to the stationary distribution of the underlying Markov process. Recently, this question has been considered from the perspective of large deviation theory, for different types of MCMC methods, including, e.g., non-reversible Metropolis-Hastings on a finite state space, non-reversible Langevin samplers, the zig-zag sampler, and parallell tempering. This approach, based on large deviations, has proven successful in analysing existing methods and designing new, efficient ones. However, for the Metropolis-Hastings algorithm on more general state spaces, the workhorse of MCMC sampling, the same techniques have not been available for analysing performance, as the underlying Markov chain dynamics violate the conditions used to prove existing large deviation results for empirical measures of a Markov chain. This also extends to methods built on the same idea as Metropolis-Hastings, such as the Metropolis-Adjusted Langevin Method or ABC-MCMC. In this paper, we take the first steps towards such a large-deviations based analysis of Metropolis-Hastings-like methods, by proving a large deviation principle for the the empirical measures of Metropolis-Hastings chains. In addition, we characterize the rate function and its properties in terms of the acceptance- and rejection-part of the Metropolis-Hastings dynamics.
翻译:为了从给定的目标分布中抽样,马尔科夫链蒙特卡罗(MCMC)抽样依赖于构造一个具有目标分布为不变量的遍历性马尔科夫链。对于任何MCMC方法,一个重要的问题是如何评估其效率。一种方法是考虑相关的经验测度及其收敛到基础Markov过程的稳态分布的速度。最近,从大偏差理论的角度出发考虑了不同类型MCMC方法的这个问题,包括有限状态空间上的非可逆Metropolis-Hastings算法、非可逆Langevin抽样器、zig-zag抽样器和平行淬火。这种基于大偏差的方法已被证明可成功分析现有方法并设计出新的高效方法。然而,对于更一般状态空间上的Metropolis-Hastings算法,即MCMC抽样的关键算法,采用同样的技巧分析性能时,由于其基础马尔科夫链动力学违反了用于证明Markov链经验测度的现有大偏差结果的条件,这个问题尚不可解决。这也适用于建立在与Metropolis-Hastings相同思想上的方法,比如Metropolis Adjusted Langevin方法或ABC-MCMC。在本文中,通过证明Metropolis-Hastings链的经验测度的大偏差原理,我们迈出了MCMC抽样中该基础算法大偏差分析方向的第一步。此外,我们通过接受和拒绝的Metropolis-Hastings动力学特征化了率函数及其特性。