For general spin systems, we prove that a contractive coupling for an arbitrary local Markov chain implies optimal bounds on the mixing time and the modified logSobolev constant for a large class of Markov chains including the Glauber dynamics, arbitrary heatbath block dynamics, and the SwendsenWang dynamics. This reveals a novel connection between probabilistic techniques for bounding the convergence to stationarity and analytic tools for analyzing the decay of relative entropy. As a corollary of our general results, we obtain O(n log n) mixing time and Ω(1/n) modified logSobolev constant of the Glauber dynamics for sampling random qcolorings of an nvertex graph with constant maximum degree Δ when q > (11/6–∊0)Δ for some fixed ∊0 > 0. We also obtain O(log n) mixing time and Ω(1) modified logSobolev constant of the SwendsenWang dynamics for the ferromagnetic Ising model on an nvertex graph of constant maximum degree when the parameters of the system lie in the tree uniqueness region. At the heart of our results are new techniques for establishing spectral independence of the spin system and block factorization of the relative entropy. On one hand we prove that a contractive coupling of any local Markov chain implies spectral independence of the Gibbs distribution. On the other hand we show that spectral independence implies factorization of entropy for arbitrary blocks, establishing optimal bounds on the modified logSobolev constant of the corresponding block dynamics.
more »
« less
Entropic independence: optimal mixing of downup random walks
We introduce a notion called entropic independence that is an entropic analog of spectral notions of highdimensional 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 exponentialsized state spaces.
In our main technical result, we show a general way of deriving entropy contraction, a.k.a. modified logSobolev inequalities, for downup random walks from spectral notions. We show that spectral independence of a distribution under arbitrary external fields automatically implies entropic independence. We furthermore extend our theory to the case where spectral independence does not hold under arbitrary external fields. To do this, we introduce a framework for obtaining tight mixing time bounds for Markov chains based on what we call restricted modified logSobolev inequalities, which guarantee entropy contraction not for all distributions, but for those in a sufficiently large neighborhood of the stationary distribution. 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 (1) tight modified logSobolev inequalities and mixing times for multistep downup walks on fractionally logconcave distributions, (2) 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$, and (3) nearlylinear time $\widetilde O_{\delta}(n)$ samplers for the hardcore and Ising models on $n$node graphs that have $\delta$relative gap to the treeuniqueness threshold. In the last application, our bound on the running time does not depend on the maximum degree $\Delta$ of the graph, and is therefore optimal even for highdegree graphs, and in fact, is sublinear in the size of the graph for highdegree graphs.
more »
« less
 Award ID(s):
 2045354
 NSFPAR ID:
 10393962
 Date Published:
 Journal Name:
 Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
 Page Range / eLocation ID:
 1418 to 1430
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Spectral independence is a recentlydeveloped framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n log n) sampling algorithms on boundeddegree graphs for a large class of problems throughout the socalled uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Isingmodel configurations. Our main contribution is to relax the boundeddegree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using L_pnorms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, Yin; FOCS’13). The nonlinearity of L_pnorms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the L_panalysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to boundeddegree graphs. As a main application of our techniques, we consider the random graph G(n, d/n), where the previously known algorithms run in time n^O(log d) or applied only to large d. We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant d, throughout the uniqueness regime.more » « less

Spectral independence is a recentlydeveloped framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n log n) sampling algorithms on boundeddegree graphs for a large class of problems throughout the socalled uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Isingmodel configurations. Our main contribution is to relax the boundeddegree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using L^pnorms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, Yin; FOCS'13). The nonlinearity of L^pnorms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the L^panalysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to boundeddegree graphs. As a main application of our techniques, we consider the random graph G(n,d/n), where the previously known algorithms run in time n^O(log d) or applied only to large d. We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant d, throughout the uniqueness regime.more » « less

Two recent and seeminglyunrelated techniques for proving mixing bounds for Markov chains are: (i) the framework of Spectral Independence, introduced by Anari, Liu and Oveis Gharan, and its numerous extensions, which have given rise to several breakthroughs in the analysis of mixing times of discrete Markov chains and (ii) the Stochastic Localization technique which has proven useful in establishing mixing and expansion bounds for both logconcave measures and for measures on the discrete hypercube. In this paper, we introduce a framework which connects ideas from both techniques. Our framework unifies, simplifies and extends those two techniques. In its center is the concept of a localization scheme which, to every probability measure, assigns a martingale of probability measures which localize in space as time evolves. As it turns out, to every such scheme corresponds a Markov chain, and many chains of interest appear naturally in this framework. This viewpoint provides tools for deriving mixing bounds for the dynamics through the analysis of the corresponding localization process. Generalizations of concepts of Spectral Independence and Entropic Independence naturally arise from our definitions, and in particular we recover the main theorems in the spectral and entropic independence frameworks via simple martingale arguments (completely bypassing the need to use the theory of highdimensional expanders). We demonstrate the strength of our proposed machinery by giving short and (arguably) simpler proofs to many mixing bounds in the recent literature, including giving the first O(nlogn) bound for the mixing time of Glauber dynamics on the hardcoremodel (of arbitrary degree) in the treeuniqueness regime.more » « less

Wootters, Mary ; Sanita, Laura (Ed.)The SwendsenWang algorithm is a sophisticated, widelyused Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising and Potts models. This chain has proved difficult to analyze, due in part to the global nature of its updates. We present optimal bounds on the convergence rate of the SwendsenWang algorithm for the complete dary tree. Our bounds extend to the nonuniqueness region and apply to all boundary conditions. We show that the spatial mixing conditions known as Variance Mixing and Entropy Mixing, introduced in the study of local Markov chains by Martinelli et al. (2003), imply Ω(1) spectral gap and O(log n) mixing time, respectively, for the SwendsenWang dynamics on the dary tree. We also show that these bounds are asymptotically optimal. As a consequence, we establish Θ(log n) mixing for the SwendsenWang dynamics for all boundary conditions throughout the tree uniqueness region; in fact, our bounds hold beyond the uniqueness threshold for the Ising model, and for the qstate Potts model when q is small with respect to d. Our proofs feature a novel spectral view of the Variance Mixing condition inspired by several recent rapid mixing results on highdimensional expanders and utilize recent work on block factorization of entropy under spatial mixing conditions.more » « less