Name
Title | ||
|---|---|---|
Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion |
Abstract | ||
|---|---|---|
ABSTRACTWe prove an optimal mixing time bound for the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling in a variety of settings. Our work presents an improved version of the spectral independence approach of Anari et al. (2020) and shows O(nlogn) mixing time on any n-vertex graph of bounded degree when the maximum eigenvalue of an associated influence matrix is bounded. As an application of our results, for the hard-core model on independent sets weighted by a fugacity λ, we establish O(nlogn) mixing time for the Glauber dynamics on any n-vertex graph of constant maximum degree Δ when λc(Δ) where λc(Δ) is the critical point for the uniqueness/non-uniqueness phase transition on the Δ-regular tree. More generally, for any antiferromagnetic 2-spin system we prove O(nlogn) mixing time of the Glauber dynamics on any bounded degree graph in the corresponding tree uniqueness region. Our results apply more broadly; for example, we also obtain O(nlogn) mixing for q-colorings of triangle-free graphs of maximum degree Δ when the number of colors satisfies q > α Δ where α ≈ 1.763, and O(mlogn) mixing for generating random matchings of any graph with bounded degree and m edges. Our approach is based on two steps. First, we show that the approximate tensorization of entropy (i.e., factorizing entropy into single vertices), which is a key step for establishing the modified log-Sobolev inequality in many previous works, can be deduced from entropy factorization into blocks of fixed linear size. Second, we adapt the local-to-global scheme of Alev and Lau (2020) to establish such block factorization of entropy in a more general setting of pure weighted simplicial complexes satisfying local spectral expansion; this also substantially generalizes the result of Cryan et al. (2019). |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1145/3406325.3451035 | ACM Symposium on Theory of Computing |
DocType | Citations | PageRank |
Conference | 1 | 0.36 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zongchen Chen | 1 | 2 | 6.13 |
| Kuikui Liu | 2 | 2 | 2.07 |
| Eric Vigoda | 3 | 747 | 76.55 |