Markov Chain Importance Sampling – a highly efficient estimator for MCMC

Markov chain (MC) algorithms are ubiquitous in machine learning and statistics and many other disciplines. Typically, these algorithms can be formulated as acceptance rejection methods. In this work we present a novel estimator applicable to these methods, dubbed Markov chain importance sampling (MCIS), which efficiently makes use of rejected proposals. For the unadjusted Langevin algorithm, it provides a novel way of correcting the discretization error. Our estimator satisfies a central limit theorem and improves on error per CPU cycle, often to a large extent. As a by-product it enables estimating the normalizing constant, an important quantity in Bayesian machine learning and statistics.

马尔可夫链（Markov Chain, MC）算法在机器学习、统计学及诸多其他学科中均无处不在。此类算法通常可被表述为接受-拒绝方法。本文提出一种适用于该类方法的新型估计器，命名为马尔可夫链重要性采样（Markov Chain Importance Sampling, MCIS），其可高效利用被拒绝的采样提议。针对未调整朗之万算法（unadjusted Langevin Algorithm），该方法提供了一种修正离散化误差的全新途径。我们提出的估计器满足中心极限定理（central limit theorem），且能在多数场景下大幅优化单位CPU周期的误差表现。此外，作为附带成果，该方法还可用于估算归一化常数——这是贝叶斯机器学习与统计学中的一项关键量化指标。