Efficient Irreversible Monte Carlo samplers

Abstract

We present here two irreversible Markov chain Monte Carlo algorithms for general discrete state systems, one of the algorithms is based on the random-scan Gibbs sampler for discrete states and the other on its improved version, the Metropolized-Gibbs sampler. The algorithms we present incorporate the lifting framework with skewed detailed balance condition and construct irreversible Markov chains that satisfy the balance condition. We have applied our algorithms to 1D 4-state Potts model. The integrated autocorrelation times for magnetisation and energy density indicate a reduction of the dynamical scaling exponent from $z\approx 1$ to $z\approx 1/2$. In addition, we have generalized an irreversible Metropolis-Hastings algorithm with skewed detailed balance, initially introduced by Turitsyn et al. (2011) for the mean field Ising model, to be now readily applicable to classical spin systems in general; application to 1D 4-state Potts model indicate a square root reduction of the mixing time at high temperatures.

arXiv commentThe document consists of 45 pages and 32 figures

References in corpus (27)

• Simulated Tempering: A New Monte Carlo Scheme
• Multicanonical Ensemble: A New Approach to Simulate First-order Phase Transitions
• Parallel Tempering Algorithm for Conformational Studies of Biological Molecules
• A Biased Monte Carlo Scheme for Zeolite Structure Solution
• Strict Detailed Balance is Unnecessary in Monte Carlo Simulation
• 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
• General non-existence theorem for phase transitions in one-dimensional systems with short range interactions, and physical examples of such transitions
• Irreversible Monte Carlo Algorithms for Efficient Sampling
• Non-Reversible Parallel Tempering: a Scalable Highly Parallel MCMC Scheme
• Violation of detailed balance accelerates relaxation
• Event-chain Monte Carlo for classical continuous spin models
• Generalized Geometric Cluster Algorithm for Fluid Simulation
• Optimal Monte Carlo Updating
• Event-chain algorithm for the Heisenberg model: Evidence for $z\simeq 1$ dynamic scaling
• Dynamics of the One-Dimensional Ising Model without Detailed Balance Condition
• Acceleration of convergence to equilibrium in Markov chains by breaking detailed balance
• On generalized cluster algorithms for frustrated spin models
• Eigenvalue analysis of an irreversible random walk with skew detailed balance conditions
• Sampling from a polytope and hard-disk Monte Carlo
• Mathematical understanding of detailed balance condition violation and its application to Langevin dynamics
• Geometric Allocation Approaches in Markov Chain Monte Carlo
• Optimization of Markov process violates detailed balance condition
• Irreversible simulated tempering
• Stochastic gradient method with accelerated stochastic dynamics
• Replica-Permutation Method with the Suwa-Todo Algorithm beyond the Replica-Exchange Method

Cited by in corpus (12)

• Enhanced sampling methods for molecular dynamics simulations
• Large deviations for the Skew-Detailed-Balance Lifted-Markov processes to sample the equilibrium distribution of the Curie-Weiss model
• Control of probability flow in Markov chain Monte Carlo -- Nonreversibility and lifting
• An asymptotic Peskun ordering and its application to lifted samplers
• Path integral Monte Carlo in a discrete variable representation with Gibbs sampling: dipolar planar rotor chain
• Pair Approximating the Action For Molecular Rotations in Path Integral Monte Carlo
• Path Integral Monte Carlo in the Angular Momentum Basis for a Chain of Planar Rotors
• Reducing rejection exponentially improves Markov chain Monte Carlo sampling
• Simulated tempering with irreversible Gibbs sampling techniques
• Comparison of the clock, stochastic cutoff, and Tomita Monte Carlo methods in simulating the dipolar triangular lattice at criticality
• Theoretical guarantees for lifted samplers
• Accelerating Multicanonical Sampling with Irreversibility