PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion

Zongchen Chen, Kuikui Liu, Eric Vigoda

arXiv:2011.02075v4cs.DMcs.DSmath-phmath.PR

TL;DR

The paper addresses how to obtain optimal mixing for local Glauber dynamics in regimes where rapid mixing was known but optimal bounds were not. It combines spectral independence with entropy factorization and local-to-global arguments, proving O(n log n) mixing across tree-uniqueness and related settings. The results cover general spin systems, colorings, and matchings, subject to stated degree, marginal, and expansion conditions.

  • Problem

    Rapid mixing of Glauber dynamics was difficult to establish at optimal O(n log n) rates throughout tree-uniqueness regions.

  • Method

    The paper combines spectral independence with entropy contraction, block-to-single-site factorization, and local-to-global arguments based on high-dimensional expansion.

  • Results

    The paper proves O(n log n) mixing for bounded-degree antiferromagnetic 2-spin systems in the up-to-Δ uniqueness region, hard-core models below λc(Δ), Ising models in the stated β range, and q-colorings with q ≥ (α*+δ)Δ; matchings mix in O(m log n).

  • Takeaways & Limitations

    The framework gives optimal mixing and modified log-Sobolev bounds across multiple spin-system regimes and extends to random matchings and general simplicial-complex walks.

  • Takeaways & Limitations

    The general bound has constants whose dependence can be substantial; for hard-core systems, C(Δ,δ) scales roughly as Δ^O(Δ^2/δ), and local entropy-contraction arguments include stated size-range conditions.

Abstract

from arXiv · show

We prove an optimal mixing time bound on 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(n\log{n})$ 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(n\log{n})$ 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(n\log{n})$ 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(n\log{n})$ mixing for $q$-colorings of triangle-free graphs of maximum degree $Δ$ when the number of colors satisfies $q > αΔ$ where $α\approx 1.763$, and $O(m\log{n})$ mixing for generating random matchings of any graph with bounded degree and $m$ edges.

1. Introduction.

The paper develops an entropy-based spectral-independence framework that proves optimal O(n log n) Glauber-dynamics mixing in broad spin-system regimes, including tree-uniqueness settings. It applies this framework to hard-core models, Ising models, colorings, and matchings, while also deriving asymptotically optimal log-Sobolev bounds.

  • Setting: The Glauber dynamics updates one uniformly chosen vertex from its conditional marginal, and O(n log n) is optimal for bounded-degree instances.The mixing-time lower bound is Ω(n log n) for a family of bounded-degree graphs.
  • Main framework: If influence eigenvalues are bounded and marginal probabilities are lower bounded, the paper proves O(n log n) mixing for general spin systems.The proof establishes constant-rate relative-entropy contraction, equivalently a modified log-Sobolev inequality of order 1/n.
  • Applications: O(n log n) mixing holds for antiferromagnetic 2-spin systems throughout the up-to-Δ uniqueness region, including the hard-core model when λ ≤ (1−δ)λc(Δ).For both results, the graph has maximum degree at most Δ and the constants depend on Δ and δ.
  • Applications: For the Ising model, O(n log n) mixing holds for β ∈ [Δ^-2+δ, Δ^-2+δ] as stated in the theorem excerpt, for every external field λ > 0.The paper also states that C = Δ^O(1/δ) suffices for sufficiently large n, yielding polynomial mixing even for unbounded degree.
  • Applications: O(n log n) mixing holds for q-colorings of triangle-free graphs when q ≥ (α*+δ)Δ, with α* ≈ 1.763, and O(m log n) mixing holds for matchings on bounded-degree graphs.The matching result applies to graphs with n vertices and m edges, improving the previously cited O(n^2m log n) bound.
  • Further consequences: The techniques also yield asymptotically optimal standard and modified log-Sobolev constants across the stated bounded-degree regimes.These consequences extend to some problems previously handled using path coupling or canonical paths.

2. Proof Outline.

The proof combines entropy factorization with spectral independence through a reduction from large-block factorization to approximate tensorization, then derives the main mixing framework for bounded-degree spin systems.

  • Proof strategy: The proof outline develops approximate tensorization, block factorization, spectral independence, and their connection to global entropy contraction.The paper introduces entropy factorization and then uses weighted simplicial complexes to connect block factorization with contraction.
  • Approximate tensorization: Approximate tensorization is implied by uniform block factorization on blocks of size ℓ = ⌈θn⌉ for suitable θ depending on marginal bounds and maximum degree.This reduction is formalized for b-marginally bounded Gibbs distributions on graphs of maximum degree at most ∆.
  • Spectral expansion: Local spectral expansion of marginally bounded pure weighted simplicial complexes yields global entropy contraction through a local-to-global argument.Lemma 2.8 establishes this implication for all orders 0 ≤ r < s ≤ n.
  • Entropy contraction: Uniform block factorization is equivalent to global entropy contraction for the corresponding weighted simplicial complex.For block size ℓ, the associated contraction rate satisfies Cκ = ℓ/n.
  • Main framework: Combining the reduction with spectral independence gives approximate tensorization with a constant independent of n for bounded-degree, totally connected Gibbs distributions.The resulting theorem applies when the distribution is both b-marginally bounded and η-spectrally independent.
  • Applications: The framework recovers optimal mixing consequences through the entropy-based analysis and supplies spectral independence for several spin-system families.The paper states that the main results follow by establishing marginal boundedness and spectral independence for each model, including monomer-dimer systems.

3. Preliminaries.

The preliminaries define entropy, conditional distributions, functional inequalities, and the relationship between approximate tensorization and Glauber-dynamics guarantees.

  • Basic definitions: The paper defines expectations, variance, covariance, entropy, and KL divergence for distributions on finite spaces.KL divergence is identified with the entropy of the relative density f = ν/µ.
  • Conditional distributions: Conditional expectations and entropies are taken under Gibbs distributions restricted to a vertex subset with a fixed boundary condition.The notation treats these conditional quantities as functions of the boundary condition.
  • Entropy decomposition: The entropy decomposition separates total entropy into conditional entropy and the entropy of the conditional expectation.For a subset S, Ent(f) = µ[Ent_S(f)] + Ent[µ_S(f)].
  • Consequences: For a distribution satisfying approximate tensorization with constant C1, the Glauber dynamics satisfies Poincaré and modified log-Sobolev inequalities with constants scaling as 1/(C1n).The same framework also gives mixing-time, concentration, and standard log-Sobolev consequences.
  • Block factorization: Uniform block factorization generalizes single-vertex factorization to fixed-size vertex subsets and corresponds to heat-bath block dynamics.The single-site case is recovered when the block size is one.

4. Approximate Tensorization via Uniform Block Factorization.

The paper reduces approximate tensorization to entropy factorization on linear-size random blocks by exploiting the small connected components induced by random vertex subsets.

  • Reduction: A block factorization assumption on ℓ = ⌈θn⌉ vertices implies approximate tensorization with a controlled constant for bounded-degree, marginally bounded Gibbs distributions.The proof uses θ ≤ b^2/(4e∆) and establishes the resulting constant as Θ(C).
  • Random-subset structure: A random linear-size vertex subset induces many small connected components, enabling entropy factorization over components.Each component has constant expected size and size O(log n) with high probability.
  • Component factorization: Conditional Gibbs distributions factor across connected components of the induced subgraph, allowing the analysis to reduce to small connected subgraphs.Product-measure entropy factorization is applied componentwise under the boundary condition.
  • Local bounds: The approximate tensorization constant on a subset is bounded using spectral gap, log-Sobolev, conductance, and marginal-boundedness estimates.These estimates provide a crude exponential bound for conditional distributions on small subsets.
  • Shattering estimate: For a uniformly random subset, the probability that a given vertex lies in a large connected component is controlled by counting connected induced subgraphs in bounded-degree graphs.The counting bound is at most (e∆)^(k−1) for connected induced subgraphs of size k containing a fixed vertex.
  • Conclusion: Combining the component-size estimate and local tensorization bounds establishes the desired approximate tensorization result.The proof concludes the reduction by summing the resulting bounds over component sizes.

5. Global Entropy Contraction via Local Spectral Expansion.

This section proves global entropy contraction from local spectral expansion of weighted simplicial complexes via a local-to-global scheme.

  • Proof structure: The argument first develops preliminaries for simplicial complexes, then establishes a general local-to-global scheme for entropy contraction.It finally reduces local entropy contraction to local spectral expansion.

5.1. Preliminaries for Simplicial Complexes.

This section introduces weighted simplicial complexes, their global and local walks, and the entropy-contraction consequences used for Glauber dynamics. It identifies Glauber dynamics and block dynamics as down-up walks on complexes.

  • Weighted simplicial complexes encode distributions over configurations, with faces representing partial assignments and maximal faces representing full configurations.
  • Global up and down operators add or remove elements according to the complex weights and induce up-down and down-up walks.
  • Glauber dynamics is the order-(n, n −1) down-up walk, while heat-bath block dynamics updating ℓ vertices is the order-(n, n −ℓ) down-up walk.
  • Local walks are defined on links of faces, and global walks can be analyzed by decomposing them into these local walks.
  • Global entropy contraction with rate κ implies Poincaré and modified log-Sobolev inequalities, relative-entropy decay, mixing bounds, and concentration inequalities.

5.2. Local-to-Global Entropy Contraction.

The section establishes a local-to-global theorem: local entropy contraction across links yields global entropy contraction across larger walks. This extends the local-to-global paradigm from variance to entropy.

  • The local contraction definition considers only local functions induced by global functions, which suffices for the target order-(n, k) down-up walks.
  • Local-to-global entropy contraction converts contraction on links into contraction for global walks on the full simplicial complex.
  • Theorem 5.4 provides global entropy-contraction rates obtained from the sequence of local rates α0, …, αn−2.
  • For homogeneous strongly log-concave distributions, all local contraction parameters satisfy αk = 1, recovering the corresponding earlier entropy-contraction result.

5.3. Local Entropy Contraction via Local Spectral Expansion.

This section derives local entropy contraction from local spectral expansion under marginal boundedness. The resulting theorem supplies the local ingredient needed to invoke the local-to-global entropy theorem.

  • Local spectral expansion plus marginal boundedness implies local entropy contraction for every link of the weighted simplicial complex.
  • Theorem 5.6 applies the local result to links, and together with Theorem 5.4 yields the entropy-contraction lemma used for mixing.
  • A second, cruder bound provides weak control when the first bound becomes vacuous, although it is not needed for the main mixing results.
  • The first contraction bound has the form αk = 1 −Θ(ζk), linking local entropy contraction directly to the local spectral-expansion parameter.
  • The proof combines a spectral-gap inequality on local walks, balance of induced local functions, and an entropy–variance comparison for bounded functions.

6. Spectral Independence for the Monomer-Dimer Model.

This section proves spectral-independence bounds for the monomer-dimer model by reducing edge influences on graphs to influences on self-avoiding-walk trees. Tree bounds then yield the graph-level result.

  • The monomer-dimer model assigns weight λ^|M| to each matching M and can also be viewed as a hard-core model on the line graph.
  • Spectral independence is defined through pairwise edge influences under feasible boundary conditions and a uniform bound on the maximum eigenvalue of the influence matrix.
  • Theorem 6.1 establishes spectral independence for monomer-dimer models on graphs of maximum degree at most Δ under arbitrary feasible boundary conditions.
  • The proof reduces total influence of an edge in a graph to total influence of the corresponding edge in a self-avoiding-walk tree, then bounds influence on bounded-degree trees.
  • The graph-to-tree reduction follows from matching-polynomial identities relating influences in G to influences in TSAW(G, r).

7. Proofs of Main Results.

The proofs reduce optimal mixing to marginal boundedness and spectral independence, then apply the paper’s entropy-contraction theorem across antiferromagnetic 2-spin systems and several applications.

  • Main proof: Up-to-∆ uniqueness with gap δ is defined through the unique fixed point of a tree recursion and a derivative gap condition.The parameters satisfy 0 ≤ β ≤ γ, βγ < 1, and λ > 0.
  • Main proof: The main proof invokes spectral independence and marginal boundedness, after which Theorem 1.12 yields the optimal mixing bound.For antiferromagnetic 2-spin systems, uniqueness gives spectral independence, while local neighborhood bounds provide marginal boundedness.
  • Applications: The antiferromagnetic 2-spin theorem gives mixing time Cn log(n/ε), with C depending on ∆, δ, β, γ, and λ.The proof obtains this by combining O(1/δ) spectral independence with marginal boundedness.
  • Applications: For the hard-core model, the proof combines Theorem 1.1 below the uniqueness threshold with Dobrushin bounds at sufficiently small fugacity.The resulting bound is C′n log(n/ε).
  • Applications: For antiferromagnetic and ferromagnetic Ising models, the proofs split parameter regimes between Theorem 1.12 and Dobrushin uniqueness.The antiferromagnetic case gives ∆O(1/δ)n log(n/ε) for λ ≥ 1/500, while the ferromagnetic case gives that bound for λ ≤ 500.
  • Applications: The same framework gives O(n log(n/ε)) mixing for random colorings and applies to monomer-dimer sampling through equivalence with the hard-core model on the line graph.For monomer-dimer models, spectral independence and marginal boundedness imply the theorem’s mixing bound.

8. Open Problems.

The open problems concern improving the dependence of the mixing bounds on maximum degree and spectral independence, especially for the hard-core and monomer-dimer models.

  • Dependence on parameters: The hard-core mixing bound currently scales as ∆O(∆2/δ) × O(n log n), motivating the question of whether poly(∆, 1/δ)n log n is possible.The open problem asks for better dependence in the approximate tensorization and mixing-time constants.
  • Monomer-dimer spectral independence: For the monomer-dimer model, the total influence bound is tight, but the maximum-eigenvalue bound obtained through the influence-matrix ∞-norm is not tight.The authors identify improved spectral-independence bounds for monomer-dimer models as an open direction.

A. Factorization and Contraction of Variance.

The variance appendix develops analogs of entropy factorization and contraction because variance is closely connected to spectral-gap bounds for Markov chains.

  • Variance analogs: Approximate tensorization and uniform block factorization of entropy have corresponding variance notions used to study spectral gaps.The appendix states that its main technical contributions also extend to the variance setting.

A.1. Spin Systems.

For spin systems, variance factorization parallels entropy factorization and translates into spectral-gap guarantees for Glauber and block dynamics.

  • Variance factorization: Variance has analogous decomposition and tensorization properties to entropy for spin-system distributions.These include the decomposition result Fact 3.4 and the product-measure tensorization lemma.
  • Block dynamics: Uniform block factorization of variance corresponds to a spectral-gap bound for block dynamics that updates a random vertex subset.The block size is represented by the factorization parameter ℓ.
  • Spectral gap: Approximate tensorization of variance is equivalent to a Poincaré inequality and therefore to a lower bound on the Glauber dynamics spectral gap.The equivalence is stated through Fact A.3.
  • Variance factorization: The paper’s entropy reduction from uniform block factorization to approximate tensorization also holds for variance.This is stated as the variance analogue of Lemma 2.3.
  • Variance factorization: If uniform block factorization has constant C and the distribution is marginally bounded, approximate tensorization has constant C1 = O(C).The hidden constant depends only on the marginal-bound parameter b.
  • Spectral independence: For spectrally independent distributions, the optimal uniform block factorization constant is O(1), yielding an optimal Ω(1/n) spectral-gap bound.This combines the block-factorization result with the variance reduction lemma.

A.2. Simplicial Complexes.

This section relates variance contraction to spectral gaps and local spectral expansion in weighted simplicial complexes. It develops local-to-global variance contraction and compares resulting bounds in special cases.

  • Variance contraction is equivalent to the Poincaré inequality, and global variance contraction is equivalent to spectral gaps of corresponding down-up walks.
  • Local variance contraction is defined through conditions on functions associated with faces of the simplicial complex, using all local functions.
  • Local variance contraction is equivalent to local spectral expansion, with ζ_k = (1−α_k)/(1+α_k).
  • The local-to-global theorem converts local variance contraction into global variance contraction and spectral-gap bounds for down-up and up-down walks.
  • For strongly log-concave distributions and ζ_k = 1/(k+2), the two displayed bounds coincide in the respective special cases.
  • The resulting bound (A.2) is never better than (A.1), because local variance-contraction rates must satisfy the trickling-down consistency condition.
Loading 2011.02075v4…