Cited By
View all- Guo HLiao CLu PZhang CChan T(2019)Zeros of holant problemsProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310572(2262-2278)Online publication date: 6-Jan-2019
Canonical paths for MCMC: from art to science
Pages 514 - 527
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 [18], 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 b ≤ 7 and b-edge-cover with b ≤ 2. They are natural generalizations of matchings and edge covers for graphs. No polynomial time approximation was previously known for these problems.
References
[1]
Milton Abramowitz, Irene A Stegun, et al. Handbook of math. functions. US Gov't. Printing Off., Washington, DC, 1965.
[2]
Ivona Bezáková and William Rummler. Sampling edge covers in 3-regular graphs. In Mathematical Foundations of Computer Science 2009, pages 137--148. Springer, 2009.
[3]
R. Bubley and M. Dyer. Path coupling: A technique for proving rapid mixing in Markov chains. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pages 223--231. IEEE, 1997.
[4]
Mary Cryan, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, and Russell Martin. Rapidly mixing markov chains for sampling contingency tables with a constant number of rows. SIAM Journal on Computing, 36(1):247--278, 2006.
[5]
Persi Diaconis and Daniel Stroock. Geometric bounds for eigenvalues of markov chains. The Annals of Applied Probability, pages 36--61, 1991.
[6]
Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM), 38(1):1--17, 1991.
[7]
Martin Dyer and Catherine Greenhill. On Markov chains for independent sets. Journal of Algorithms, 35(1):17--49, 2000.
[8]
Martin Dyer, Mark Jerrum, and Eric Vigoda. Rapidly mixing Markov chains for dismantleable constraint graphs. In Randomization and Approximation Techniques in Computer Science, pages 68--77. Springer, 2002.
[9]
Leslie Ann Goldberg and Mark Jerrum. A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid. In Proceedings of the 39th International Colloquium Conference on Automata, Languages and Programming, pages 521--532, 2011.
[10]
Mark Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structures & Algorithms, 7(2):157--166, 1995.
[11]
Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM journal on computing, 18(6):1149--1178, 1989.
[12]
Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM Journal on computing, 22(5):1087--1116, 1993.
[13]
Mark Jerrum and Alistair Sinclair. The Markov chain Monte Carlo method: an approach to approximate counting and integration. Approximation algorithms for NP-hard problems, pages 482--520, 1996.
[14]
Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM, 51:671--697, July 2004.
[15]
Mark Jerrum, Leslie Valiant, and Vijay Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169--188, July 1986.
[16]
Chengyu Lin, Jingcheng Liu, and Pinyan Lu. A simple FPTAS for counting edge covers. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 341--348, 2014.
[17]
Jingcheng Liu, Pinyan Lu, and Chihao Zhang. FPTAS for counting weighted edge covers. In Proceedings of the 22nd Annual European Symposium on Algorithms, pages 654--665, 2014.
[18]
Colin McQuillan. Approximating holant problems by winding. arXiv preprint arXiv:1301.2880, 2013.
[19]
Ben Morris and Alistair Sinclair. Random walks on truncated cubes and sampling 0-1 knapsack solutions. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science, pages 230--240. IEEE, 2002.
[20]
Alistair Sinclair. Improved bounds for mixing rates of markov chains and multicommodity flow. Combinatorics, probability and Computing, 1(04):351--370, 1992.
[21]
Eric Vigoda. Improved bounds for sampling coloring. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, pages 51--59. IEEE, 1999.
- Canonical paths for MCMC: from art to science
Recommendations
Accelerating MCMC algorithms
Markov chain Monte Carlo algorithms are used to simulate from complex statistical distributions by way of a local exploration of these distributions. This local feature avoids heavy requests on understanding the nature of the target, but it also ...
Markov chain Monte Carlo algorithms are used to simulate from complex statistical distributions by way of a local exploration of these distributions. This local feature avoids heavy requests on understanding the nature of target, but it also potentially ...
Localization for MCMC: sampling high-dimensional posterior distributions with local structure
AbstractWe investigate how ideas from covariance localization in numerical weather prediction can be used in Markov chain Monte Carlo (MCMC) sampling of high-dimensional posterior distributions arising in Bayesian inverse problems. To localize ...
Highlights- We explain how to use localization for the numerical solution of Bayesian inverse problems by Markov chain Monte Carlo (MCMC).
The Metropolized Partial Importance Sampling MCMC Mixes Slowly on Minimum Reversal Rearrangement Paths
Markov chain Monte Carlo has been the standard technique for inferring the posterior distribution of genome rearrangement scenarios under a Bayesian approach. We present here a negative result on the rate of convergence of the generally used Markov ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- SIAM Activity Group on Discrete Mathematics
- SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 10 January 2016
Check for updates
Qualifiers
- Research-article
Conference
SODA '16
Sponsor:
Acceptance Rates
Overall Acceptance Rate 411 of 1,322 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 128Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
Cited By
View all- Guo HLiao CLu PZhang CChan T(2019)Zeros of holant problemsProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310572(2262-2278)Online publication date: 6-Jan-2019
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in