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.
