Source-linked AI summary
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
Nima Anari, Kuikui Liu, Shayan Oveis Gharan
TL;DR
The paper addresses efficient sampling and mixing for the hardcore model, where exact partition-function computation is #P-hard and prior approaches can be quasi-polynomial. It connects spectral independence to local spectral expansion and proves polynomial-time Glauber-dynamics mixing up to the uniqueness threshold, while identifying a limitation in the resulting dependence on δ.
Problem
Exact computation of the hardcore partition function is #P-hard, while Weitz’s algorithm is not polynomial-time on graphs with unbounded maximum degree and Glauber-dynamics mixing up to the uniqueness threshold remained unresolved.
Method
The paper proves that spectral independence yields local spectral expansion, then combines this framework with Glauber-dynamics spectral-gap results and tree-recursion potential methods for controlling correlations.
Results
Polynomial-time mixing holds for hardcore-model Glauber dynamics on maximum-degree-∆ graphs with λ=(1−δ)λc(∆), with running time O(n^C(δ)) and C(δ)≤exp(O(1/δ)).
Takeaways & Limitations
The framework gives fast Glauber-dynamics sampling from the hardcore distribution whenever λ<λc(∆), including the uniqueness-threshold regime.
Takeaways & Limitations
The resulting dependence on δ is significantly worse than Weitz’s: C(δ)≤exp(O(1/δ)) rather than O(1/δ), and local-to-global bounds cannot generally improve beyond n^O(1/δ).
Abstract
from arXiv · showhide
We say a probability distribution $μ$ is spectrally independent if an associated correlation matrix has a bounded largest eigenvalue for the distribution and all of its conditional distributions. We prove that if $μ$ is spectrally independent, then the corresponding high dimensional simplicial complex is a local spectral expander. Using a line of recent works on mixing time of high dimensional walks on simplicial complexes \cite{KM17,DK17,KO18,AL19}, this implies that the corresponding Glauber dynamics mixes rapidly and generates (approximate) samples from $μ$. As an application, we show that natural Glauber dynamics mixes rapidly (in polynomial time) to generate a random independent set from the hardcore model up to the uniqueness threshold. This improves the quasi-polynomial running time of Weitz's deterministic correlation decay algorithm \cite{Wei06} for estimating the hardcore partition function, also answering a long-standing open problem of mixing time of Glauber dynamics \cite{LV97,LV99,DG00,Vig01,EHSVY16}.
1 Introduction
The paper connects spectral independence of distributions to local spectral expansion of associated simplicial complexes, yielding rapid Glauber-dynamics mixing. Applied to the hardcore model, this gives polynomial-time mixing up to the uniqueness threshold and an FPRAS for the partition function.
- Definitions: Spectral independence bounds the largest eigenvalue of a pairwise influence matrix for a distribution and all its conditional distributions.The parameter sequence (η0, …, ηn−2) records these bounds across successive conditionings.
- Glauber dynamics: Theorem 1.3 shows that spectral independence gives the natural Glauber dynamics a positive spectral gap and therefore rapid mixing.The construction uses connections between Markov-chain analysis and high-dimensional expanders.
- High-dimensional expanders: Theorem 1.5 converts (η0, …, ηn−2)-spectral independence into local spectral expansion of the associated weighted simplicial complex.The resulting expansion improves toward lower-dimensional faces when the ηi are O(1).
- Hardcore application: The result yields an FPRAS for estimating the hardcore partition function at λ = (1−δ)λc(∆) on graphs of maximum degree at most ∆.This addresses the conjectured polynomial-time mixing of natural Glauber dynamics up to the uniqueness threshold.
2 Preliminaries
The preliminaries define the paper’s probabilistic, Markov-chain, tree-recursion, and correlation-decay frameworks. They connect spatial mixing for the hardcore model to uniqueness and Weitz’s self-avoiding-walk-tree reduction.
- Markov chains: A reversible Markov chain has a stationary distribution characterized by detailed balance, and its mixing behavior is governed by the second-largest eigenvalue in absolute value.The largest eigenvalue is 1; λ*(P) denotes the maximum of the absolute values of the remaining extreme eigenvalues.
- Tree recurrences: The hardcore tree recurrence expresses a root’s marginal through child marginals and yields a polynomial-time dynamic program for computing the partition function on trees.For regular trees without boundary conditions, the recurrence reduces to a univariate map with a unique fixed point.
- Correlation decay: Weak and strong spatial mixing quantify how boundary assignments affect a vertex, with strong mixing weighting differences by their distances from that vertex.The definitions use a decay rate α and constant C; the relevant assignment differences are captured by S(τ,σ).
3 The Eigenvalues of the Pairwise Influence Matrix
This section characterizes the spectrum of the simplicial-complex walk associated with a distribution through its pairwise influence matrix. The proof removes structural eigenvalues induced by the complex’s multipartite organization and relates the remaining spectrum to Ψµ.
- Spectral characterization: The spectrum of P∅ is characterized by relating it to the spectrum of (1/(n−1))Ψµ through an intermediate matrix M∅.The proof’s central strategy is to construct M∅ from P∅ after accounting for eigenvalues forced by the n-partite structure.
- Trivial eigenvalues: P∅ has trivial eigenvalues 1 and −1/(n−1), while M∅ replaces these structural eigenvalues with n additional zero eigenvalues.The eigenvalue −1/(n−1) has multiplicity at least n−1, and the eigenvalue 1 has multiplicity at least 1.
- Influence matrix: The spectrum of M∅ is the multiset union of the spectrum of (1/(n−1))Ψµ and n additional copies of 0.This follows by expressing the relevant block matrix as a rescaled influence matrix after the structural modes are removed.
- Eigenvector structure: The vectors 1_i form orthogonal eigenvectors for the structural modes, while the vectors π_i provide corresponding left eigenvectors.These vectors are supported on the two assignments associated with each element i.
- Multipartite structure: The multipartite structure explains the structural modes: indicator vectors of the parts generate eigenvectors, generalizing the −1 eigenvalue of weighted bipartite random walks.For a d-dimensional d-partite weighted complex, the part indicators are eigenvectors with the corresponding structural eigenvalue.
4 Influence Decoupling in Weitz’s Self-Avoiding Walk Tree
The analysis converts influence bounds on general graphs into tree bounds using Weitz’s self-avoiding walk tree, then decouples multiple copies of each vertex via R-pseudoinfluence. Under the uniqueness condition, exponentially decaying tree influences yield an exp(O(1/δ)) bound and establish the target theorem.
- Reduction and decoupling: Weitz’s self-avoiding walk tree converts influence analysis on general graphs into a corresponding tree problem, but repeated vertex copies require decoupling.The construction represents the graph around a root by a tree, while R-pseudoinfluence handles the many copies of one original vertex.
- Reduction and decoupling: R-pseudoinfluence measures a vertex’s effect on the root under boundary marginal assignments on the remaining vertices at the same level.The definition allows partial assignments on the rest of the relevant tree level and maximizes the resulting root influence.
- Reduction and decoupling: A generic decoupling lemma applies to any two-state spin system and separates the influence of repeated copies into single-copy contributions.The proof uses an intermediate pseudoinfluence quantity and an induction over an ancestor-free set of vertices.
- Tree bounds: For the hardcore model below the uniqueness threshold, the total R-pseudoinfluence on trees is bounded by exp(O(1/δ)).The proof combines a decay bound beyond level ℓ0 = Θ(1/δ) with a trivial bound for shallower levels.
- Tree bounds: The resulting decoupling and tree bound together complete the proof of Theorem 1.13.The argument sets λ = (1 −δ)λc(∆), applies the self-avoiding walk tree at an arbitrary root, and invokes the R-pseudoinfluence bound.
5 Bounding the R-Pseudoinfluence Decay: The Potential Method
The potential method proves decay of R-pseudoinfluence by transforming the tree recurrence into a recurrence for a concave potential. Strong spatial mixing controls boundary errors, allowing the resulting decay estimate to hold beyond depth Θ(1/δ).
- Potential method: The potential method uses a continuously differentiable, strictly increasing, concave function to analyze message decay in the tree recurrence.Its derivative is positive and decreasing, and the chosen potential is independent of λ and ∆.
- Controlling boundary effects: Strong spatial mixing controls the additional boundary-error factor needed to apply the potential decay argument.The analysis explicitly controls η as a function of the level using a strong spatial mixing result.
- Controlling boundary effects: For λ up-to-∆unique with gap δ, the decay analysis begins after ℓ0 = Θ(1/δ), when the required error condition becomes valid.The proof verifies that the potential-method hypothesis holds at this depth and then combines the relevant propositions and lemmas.
- Potential method: The transformed ϕ-pseudoinfluence recurrence enables a decay analysis through the potential’s derivative and the tree update map.The recurrence for K is induced by the recurrence for R, and the proof relates the two pseudoinfluences using the Mean Value Theorem.
- Decay comparison: The proof relates true decay to ideal decay while controlling coordinate-wise errors through monotonicity and concavity.The comparison introduces a multiplicative error factor and bounds it using the range between Rmax(ℓ) and Rmin(ℓ).
6 Conclusion and Open Problems
The paper obtains polynomial-time Glauber mixing for the hardcore model below the uniqueness threshold, while identifying a substantial dependence on the distance to the threshold and a limitation of current local-to-global methods.
- Main conclusion: For λ = (1 −δ)λc(∆), Glauber dynamics mixes in O(n^C(δ)) steps on graphs of maximum degree at most ∆.The exponent satisfies C(δ) ≤ exp(O(1/δ)).
- Main conclusion: The exponent’s dependence on δ is significantly worse than the O(1/δ) dependence reported for Weitz’s correlation-decay algorithm.The paper contrasts C(δ) ≤ exp(O(1/δ)) for Glauber dynamics with C(δ) ≤ O(1/δ) for the correlation-decay algorithm.
- Limitations and open problems: On infinite ∆-regular trees, the maximum eigenvalue of the influence matrix cannot generally be bounded asymptotically better than O(1/δ).The paper establishes this through a Θ(1/δ) total pairwise influence on a vertex.
- Limitations and open problems: This lower bound limits the mixing-time guarantee obtainable by bounding spectral independence and applying the cited local-to-global theorem to n^O(1/δ).The paper notes that stronger n^O(C(δ) n log n) behavior suggested by prior results is not captured by the current framework.
A Precise Strong Spatial Mixing: Proof of Proposition 5.4
This appendix proves the strong spatial mixing estimate used in the potential-method analysis. The estimate supplies the boundary-insensitivity control needed for decay beyond the threshold depth.
- Proof strategy: The appendix’s goal is to prove Proposition 5.4 using a previously established strong spatial mixing result.The cited result assumes λ is up-to-∆unique with rate δ and applies to rooted trees at every level.
- Proof strategy: The proof transfers the cited spatial-mixing estimate into the form required by Proposition 5.4 through nearly identical inequalities.After establishing these inequalities, the argument derives the proposition’s stated bound.
B The Pairwise Influence Matrix on Infinite Regular Trees
For two-state spin systems on the infinite Δ-regular tree, the pairwise influence matrix can be analyzed through tree structure and recurrences. In the uniqueness regime, its largest eigenvalue scales as Θ(1/δ), with the proof combining multiplicative path factorization, explicit neighbor influences, and parity-based bounds.
- Setup: The section studies pairwise influence matrices for general two-state spin systems on the infinite Δ-regular tree in the uniqueness regime.The hardcore model is recovered when β = 0 and γ = 1; β = γ gives the Ising model.
- Main result: λmax(Ψµ) = Θ(1/δ) when the parameters lie in the uniqueness regime, where δ measures the distance from the uniqueness boundary.This is the section’s main result for the infinite regular tree.
- Proof strategy: On the regular tree, the proof combines the path-factorization lemma with an explicit calculation of neighboring influences.These two lemmas reduce the theorem to controlling influence as a function of distance from a fixed root.
- Proof strategy: Pairwise influences factor along paths: if w lies between u and v, then Ψµ(u, v) = Ψµ(u, w) · Ψµ(w, v).The factorization follows from conditional independence of u and v given the spin at w.
- Spectral bounds: In the antiferromagnetic case, influence from the root is negative at odd distance and positive at even distance.The sign pattern follows from the neighboring-influence calculation and the sign of the derivative at the fixed point.
- Spectral bounds: The eigenvalue bounds use a root-centered distance calculation and the principal submatrix on vertices at even distance from the root.Even-distance vertices have positive pairwise influences, while symmetry gives equal row sums for the full matrix.