Canonical Paths for MCMC: from Art to Science

DOI10.1137/1.9781611974331.CH38zbMATH Open1411.68193arXiv1510.04099OpenAlexW2949326365MaRDI QIDQ4575615FDOQ4575615

Lingxiao Huang, Chihao Zhang, Pinyan Lu

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: Markov Chain Monte Carlo (MCMC) method is a widely used algorithm design scheme with many applications. To make efficient use of this method, the key step is to prove that the Markov chain is rapid mixing. Canonical paths is one of the two main tools to prove rapid mixing. However, there are much fewer success examples comparing to coupling, the other main tool. The main reason is that there is no systematic approach or general recipe to design canonical paths. Building up on a previous exploration by McQuillan, we develop a general theory to design canonical paths for MCMC: We reduce the task of designing canonical paths to solving a set of linear equations, which can be automatically done even by a machine. Making use of this general approach, we obtain fully polynomial-time randomized approximation schemes (FPRAS) for counting the number of $b$-matching with $bleq7$ and $b$-edge-cover with $bleq2$. They are natural generalizations of matchings and edge covers for graphs. No polynomial time approximation was previously known for these problems.

Full work available at URL: https://arxiv.org/abs/1510.04099

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Randomized algorithms (68W20) Approximation algorithms (68W25)

Cited In (10)

• Zeros and approximations of holant polynomials on the complex plane
• Title not available (Why is that?)
• On the Complexity of Holant Problems
• Some applications of Wagner's weighted subgraph counting polynomial
• Spectral independence via stability and applications to Holant-type problems
• Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
• Multicanonical MCMC for sampling rare events: an illustrative review
• Beyond windability: approximability of the four-vertex model
• Approximability of the complementarily symmetric Holant problems on cubic graphs
• Counting vertices of integral polytopes defined by facets

Recommendations

• Advanced MCMC methods for sampling on diffusion pathspace 👍 👎
• MCMC from Scratch 👍 👎
• Multicanonical MCMC for sampling rare events: an illustrative review 👍 👎
• A pathological MCMC algorithm and its use as a benchmark for convergence assessment technique chains 👍 👎
• MCMC perspectives on simulated likelihood estimation 👍 👎
• Practical Use of MCMC Methods: Lessons from a Case Study 👍 👎

This page was built for publication: Canonical Paths for MCMC: from Art to Science

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575615)