Forward Event-Chain Monte Carlo: Fast Sampling by Randomness Control in Irreversible Markov Chains

Abstract

Irreversible and rejection-free Monte Carlo methods, recently developed in physics under the name event-chain and known in statistics as piecewise deterministic Monte Carlo (PDMC), have proven to produce clear acceleration over standard Monte Carlo methods, thanks to the reduction of their random-walk behavior. However, while applying such schemes to standard statistical models, one generally needs to introduce an additional randomization for sake of correctness. We propose here a new class of event-chain Monte Carlo methods that reduces this extra-randomization to a bare minimum. We compare the efficiency of this new methodology to standard PDMC and Monte Carlo methods. Accelerations up to several magnitudes and reduced dimensional scalings are exhibited. Supplementary materials for this article are available online.

Keywords:

• High-dimensional sampling
• Markov chain Monte Carlo method
• Piecewise deterministic Markov process

Acknowledgments

M. M. is very grateful for the support from the Data Science Initiative and M. M and A. D. thank the Chaire BayeScale “P. Laffitte” for its support. We are grateful to the cluster computing facilities at École Polytechnique (mésocentre PHYMATH) and the Mésocentre Clermont Auvergne University for providing computing resources.

Supplementary Materials

Appendix A: Formal derivation of new Markov kernels QComplementary details to the presentation in Section 3. (pdf)

Appendix B: Choices of $K^{x,/\mathrm{}\mathrm{}/}$ Expression for Metropolis–Hastings choice for $K^{x,/\mathrm{}\mathrm{}/}$. (pdf)Appendices C1–C4: Implementation details

Presentation and pseudocodes of the extended PDMP MCMC process relying on a fixed-time refreshement. Additional technical details on event-time computations. Presentation and pseudocode of distribution factorization for PDMC implementation. (pdf)

Appendices D1–D5: Addition to the numerical experimentsFurther numerical results on comparison to a Hastings–Metropolis scheme for the anisotropic Gaussian distribution, choices of $K^{x,/\mathrm{}\mathrm{}/},K^{x,y_{/\mathrm{}\mathrm{}/},\perp }$, T, p, and θ, ESS for mixture of Gaussian distributions. (pdf)

Notes

¹ In the case where ${\mu }_Y$ is the uniform distribution on ${\mathbb{S}}^{d-1}$, ${\tilde{T}}^{x,\perp }(y_{/\mathrm{}\mathrm{}/},·)$ defined in (A.10) is the uniform distribution on the d – 1-sphere of $\text{span}{(\nabla U(x))}^{\perp }$ with radius ${(1-y_{/\mathrm{}\mathrm{}/}^2)}^{1/2}$, for all $x\in {\mathbb{R}}^d$ and $y_{/\mathrm{}\mathrm{}/}\in \left[-1,1\right]$. In the case where ${\mu }_Y$ is the $(d-1)$-dimensional standard Gaussian distribution, ${\tilde{T}}^{x,\perp }(y_{/\mathrm{}\mathrm{}/},·)$ is the $(d-1)$-dimensional standard Gaussian, for all $x\in {\mathbb{R}}^d$ and $y_{/\mathrm{}\mathrm{}/}\in \mathbb{R}$.