REVIEW 7 cited by
Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Models
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Models
read the original abstract
We introduce a notion called entropic independence that is an entropic analog of spectral notions of high-dimensional expansion. Informally, entropic independence of a background distribution $\mu$ on $k$-sized subsets of a ground set of elements says that for any (possibly randomly chosen) set $S$, the relative entropy of a single element of $S$ drawn uniformly at random carries at most $O(1/k)$ fraction of the relative entropy of $S$. Entropic independence is the analog of the notion of spectral independence, if one replaces variance by entropy. We use entropic independence to derive tight mixing time bounds, overcoming the lossy nature of spectral analysis of Markov chains on exponential-sized state spaces. In our main technical result, we show a general way of deriving entropy contraction, a.k.a. modified log-Sobolev inequalities, for down-up random walks from spectral notions. We show that spectral independence of a distribution under arbitrary external fields automatically implies entropic independence. To derive our results, we relate entropic independence to properties of polynomials: $\mu$ is entropically independent exactly when a transformed version of the generating polynomial of $\mu$ is upper bounded by its linear tangent; this property is implied by concavity of the said transformation, which was shown by prior work to be locally equivalent to spectral independence. We apply our results to obtain tight modified log-Sobolev inequalities and mixing times for multi-step down-up walks on fractionally log-concave distributions. As our flagship application, we establish the tight mixing time of $O(n\log n)$ for Glauber dynamics on Ising models whose interaction matrix has eigenspectrum lying within an interval of length smaller than $1$, improving upon the prior quadratic dependence on $n$.
Forward citations
Cited by 7 Pith papers
-
A Near-Optimal Parallel Algorithm for Finding Matroid Bases
Parallel algorithm for matroid basis computation with O(n^{1/3} log^{1/3} n) round complexity, nearly matching the KUW lower bound.
-
G{\aa}rding's Theorem for Posynomials
Homogeneous posynomials zero-free on right half-planes have concave degree-normalized roots, so sector stability of aperture απ implies sharp α-fractional log-concavity.
-
Glauber dynamics for random field Ising models on bounded degree graphs and MLSI
Glauber dynamics for RFIM on bounded-degree graphs mixes in polynomial time w.h.p. under anti-concentrated random fields, with MLSI and weak Poincaré inequalities also established.
-
Entropic independence via sparse localization
Sparse localization deduces entropic independence from sparse ℓ2-independence with explicit loss, yielding approximate entropy conservation for uniform independent sets of fixed size in bounded-degree graphs.
-
Edge-Tilting Field Dynamics: Rapid Mixing at the Uniqueness Threshold and Optimal Mixing for Swendsen-Wang Dynamics
Proves polynomial mixing of Glauber dynamics at the antiferromagnetic two-spin uniqueness threshold and optimal logarithmic mixing for Swendsen-Wang dynamics on bounded-degree graphs, resolving a conjecture.
-
G{\aa}rding's Theorem for Posynomials
A homogeneous posynomial that is zero-free on a product of right half-planes has a concave degree-normalized root, giving a sharp link between sector stability and fractional log-concavity.
-
Lower bound on the mixing time of $p$-spin glasses
Proves an exponential lower bound on the mixing time of Glauber dynamics for the p-spin glass at inverse temperatures above C ln(p)/p for large p, via energy landscape analysis with Gaussian decompositions and a bottl...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.