An asymptotic Peskun ordering and its application to lifted samplers

Abstract

A Peskun ordering between two samplers, implying a dominance of one over the other, is known among the Markov chain Monte Carlo community for being a remarkably strong result. It is however also known for being a result that is notably difficult to establish. Indeed, one has to prove that the probability to reach a state $\mathbf{y}$ from a state $\mathbf{x}$, using a sampler, is greater than or equal to the probability using the other sampler, and this must hold for all pairs $(\mathbf{x},\mathbf{y})$ such that $\mathbf{x}\ne \mathbf{y}$. We provide in this paper a weaker version that does not require an inequality between the probabilities for all these states: essentially, the dominance holds asymptotically, as a varying parameter grows without bound, as long as the states for which the probabilities are greater than or equal to belong to a mass-concentrating set. The weak ordering turns out to be useful to compare lifted samplers for partially-ordered discrete state-spaces with their Metropolis--Hastings counterparts. An analysis in great generality yields a qualitative conclusion: they asymptotically perform better in certain situations (and we are able to identify them), but not necessarily in others (and the reasons why are made clear). A quantitative study in a specific context of graphical-model simulation is also conducted.

References in corpus (11)

• General state space Markov chains and MCMC algorithms
• Non-reversible Metropolis-Hastings
• Non-Reversible Parallel Tempering: a Scalable Highly Parallel MCMC Scheme
• A New Bayesian Approach to Robustness Against Outliers in Linear Regression
• Eigenvalue analysis of an irreversible random walk with skew detailed balance conditions
• Efficient Irreversible Monte Carlo samplers
• Irreversible simulated tempering
• An automatic robust Bayesian approach to principal component regression
• Accelerated Sampling on Discrete Spaces with Non-Reversible Markov Processes
• An asymptotic Peskun ordering and its application to lifted samplers
• Non-reversible Markov chain Monte Carlo for sampling of districting maps

Cited by in corpus (4)

• Informed reversible jump algorithms
• An asymptotic Peskun ordering and its application to lifted samplers
• Robust heavy-tailed versions of generalized linear models with applications in actuarial science
• Theoretical guarantees for lifted samplers