TY - JOUR

T1 - On the utility of Metropolis-Hastings with asymmetric acceptance ratio

AU - Andrieu, Christophe

AU - Doucet, Arnaud

AU - Yıldırım, Sinan

AU - Chopin, Nicolas

PY - 2018/3/26

Y1 - 2018/3/26

N2 - The Metropolis-Hastings algorithm allows one to sample asymptotically from any probability distribution $\pi$. There has been recently much work devoted to the development of variants of the MH update which can handle scenarios where such an evaluation is impossible, and yet are guaranteed to sample from $\pi$ asymptotically. The most popular approach to have emerged is arguably the pseudo-marginal MH algorithm which substitutes an unbiased estimate of an unnormalised version of $\pi$ for $\pi$. Alternative pseudo-marginal algorithms relying instead on unbiased estimates of the MH acceptance ratio have also been proposed. These algorithms can have better properties than standard PM algorithms. Convergence properties of both classes of algorithms are known to depend on the variability of the estimators involved and reduced variability is guaranteed to decrease the asymptotic variance of ergodic averages and will shorten the burn-in period, or convergence to equilibrium, in most scenarios of interest. A simple approach to reduce variability, amenable to parallel computations, consists of averaging independent estimators. However, while averaging estimators of $\pi$ in a pseudo-marginal algorithm retains the guarantee of sampling from $\pi$ asymptotically, naive averaging of acceptance ratio estimates breaks detailed balance, leading to incorrect results. We propose an original methodology which allows for a correct implementation of this idea. We establish theoretical properties which parallel those available for standard PM algorithms and discussed above. We demonstrate the interest of the approach on various inference problems. In particular we show that convergence to equilibrium can be significantly shortened, therefore offering the possibility to reduce a user's waiting time in a generic fashion when a parallel computing architecture is available.

AB - The Metropolis-Hastings algorithm allows one to sample asymptotically from any probability distribution $\pi$. There has been recently much work devoted to the development of variants of the MH update which can handle scenarios where such an evaluation is impossible, and yet are guaranteed to sample from $\pi$ asymptotically. The most popular approach to have emerged is arguably the pseudo-marginal MH algorithm which substitutes an unbiased estimate of an unnormalised version of $\pi$ for $\pi$. Alternative pseudo-marginal algorithms relying instead on unbiased estimates of the MH acceptance ratio have also been proposed. These algorithms can have better properties than standard PM algorithms. Convergence properties of both classes of algorithms are known to depend on the variability of the estimators involved and reduced variability is guaranteed to decrease the asymptotic variance of ergodic averages and will shorten the burn-in period, or convergence to equilibrium, in most scenarios of interest. A simple approach to reduce variability, amenable to parallel computations, consists of averaging independent estimators. However, while averaging estimators of $\pi$ in a pseudo-marginal algorithm retains the guarantee of sampling from $\pi$ asymptotically, naive averaging of acceptance ratio estimates breaks detailed balance, leading to incorrect results. We propose an original methodology which allows for a correct implementation of this idea. We establish theoretical properties which parallel those available for standard PM algorithms and discussed above. We demonstrate the interest of the approach on various inference problems. In particular we show that convergence to equilibrium can be significantly shortened, therefore offering the possibility to reduce a user's waiting time in a generic fashion when a parallel computing architecture is available.

KW - stat.CO

M3 - Article (Academic Journal)

JO - arXiv

JF - arXiv

ER -