Reducing rejection exponentially improves Markov chain Monte Carlo sampling

Abstract

The choice of transition kernel critically influences the performance of the Markov chain Monte Carlo method. Despite the importance of kernel choice, guiding principles for optimal kernels have not been established. Here, we propose a one-parameter rejection control transition kernel that can be applied to various Monte Carlo samplings and demonstrate that the rejection process plays a major role in determining the sampling efficiency. Varying the rejection probability, we examine the autocorrelation time of the order parameter in the two- and three-dimensional ferromagnetic Potts models. Our results reveal that reducing the rejection rate leads to an exponential decrease in autocorrelation time in sequential spin updates and an algebraic reduction in random spin updates. The autocorrelation times of conventional algorithms almost fall on a single curve as a function of the rejection rate. The present transition kernel with an optimal parameter provides one of the most efficient samplers for general cases of discrete variables.

arXiv comment10 pages, 6 figures

References in corpus (16)

• Event-chain Monte Carlo algorithms for hard-sphere systems
• Markov Chain Monte Carlo Method without Detailed Balance
• Generalized event-chain Monte Carlo: Constructing rejection-free global-balance algorithms from infinitesimal steps
• Irreversible Monte Carlo Algorithms for Efficient Sampling
• Asymptotically unbiased estimation of physical observables with neural samplers
• Three-Dimensional 3-State Potts Model Revisited With New Techniques
• Order-N Cluster Monte Carlo Method for Spin Systems with Long-range Interactions
• Boosting Monte Carlo simulations of spin glasses using autoregressive neural networks
• Upper and Lower Critical Decay Exponents of Ising Ferromagnets with Long-range Interaction
• Optimal Monte Carlo Updating
• Canonical local algorithms for spin systems: Heat Bath and Hasting's methods
• Monte Carlo study of very weak first-order transitions in the three-dimensional Ashkin-Teller model
• Efficient Irreversible Monte Carlo samplers
• Geometric Allocation Approaches in Markov Chain Monte Carlo
• Geometric allocation approach to accelerating directed worm algorithm
• Lifted directed-worm algorithm

Cited by in corpus (1)

• Control of probability flow in Markov chain Monte Carlo -- Nonreversibility and lifting