Spectral Independence and Local-to-Global Techniques for Optimal Mixing of Markov Chains
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915497605332992 |
|---|---|
| author | Chen, Zongchen Stefankovic, Daniel Vigoda, Eric |
| author_facet | Chen, Zongchen Stefankovic, Daniel Vigoda, Eric |
| contents | This monograph is an exposition on an exciting new technique known as spectral independence, which has been instrumental in analyzing the convergence rate of Markov Chain Monte Carlo (MCMC) algorithms. For a high-dimensional distribution defined on labelings of the vertices of an n-vertex graph, the spectral independence condition, introduced by Anari, Liu, and Oveis Gharan (2020), is a bound on the maximum eigenvalue of the nxn influence matrix whose entries capture the influence between pairs of vertices (closely related to the covariance between the variables). In the first part of the monograph, we present results showing that spectral independence (and related techniques) imply fast mixing of simple Markov chains such as the Gibbs sampler. These proofs utilize local-to-global theorems which we will detail in this work.
We focus on two applications: the hard-core model on independent sets of a graph (which is a binary graphical model) and random bases of a matroid. We demonstrate several methods for establishing spectral independence, including the correlation decay approach introduced by Weitz (2006) and the analytic approach introduced by Barvinok (2015) using zero-freeness of the associated complex-valued partition function. As a consequence of the techniques presented in this monograph we obtain fast mixing of the Gibbs sampler on general graphs in the so-called tree-uniqueness region, polynomial-time mixing on general graphs at the critical point for the uniqueness threshold, and polynomial-time mixing on random regular graphs beyond the uniqueness threshold. We also utilize the local-to-global framework of spectral independence and the Trickle-Down theorem of Oppenheim (2018) to prove fast mixing of the bases-exchange walk for generating a random basis of an arbitrary matroid, which was established by Anari, Liu, Oveis Gharan and Vinzant (2019). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_13826 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Spectral Independence and Local-to-Global Techniques for Optimal Mixing of Markov Chains Chen, Zongchen Stefankovic, Daniel Vigoda, Eric Discrete Mathematics Probability This monograph is an exposition on an exciting new technique known as spectral independence, which has been instrumental in analyzing the convergence rate of Markov Chain Monte Carlo (MCMC) algorithms. For a high-dimensional distribution defined on labelings of the vertices of an n-vertex graph, the spectral independence condition, introduced by Anari, Liu, and Oveis Gharan (2020), is a bound on the maximum eigenvalue of the nxn influence matrix whose entries capture the influence between pairs of vertices (closely related to the covariance between the variables). In the first part of the monograph, we present results showing that spectral independence (and related techniques) imply fast mixing of simple Markov chains such as the Gibbs sampler. These proofs utilize local-to-global theorems which we will detail in this work. We focus on two applications: the hard-core model on independent sets of a graph (which is a binary graphical model) and random bases of a matroid. We demonstrate several methods for establishing spectral independence, including the correlation decay approach introduced by Weitz (2006) and the analytic approach introduced by Barvinok (2015) using zero-freeness of the associated complex-valued partition function. As a consequence of the techniques presented in this monograph we obtain fast mixing of the Gibbs sampler on general graphs in the so-called tree-uniqueness region, polynomial-time mixing on general graphs at the critical point for the uniqueness threshold, and polynomial-time mixing on random regular graphs beyond the uniqueness threshold. We also utilize the local-to-global framework of spectral independence and the Trickle-Down theorem of Oppenheim (2018) to prove fast mixing of the bases-exchange walk for generating a random basis of an arbitrary matroid, which was established by Anari, Liu, Oveis Gharan and Vinzant (2019). |
| title | Spectral Independence and Local-to-Global Techniques for Optimal Mixing of Markov Chains |
| topic | Discrete Mathematics Probability |
| url | https://arxiv.org/abs/2307.13826 |