Kuikui Liu

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 $\lambda$, we establish $O(n\log{n})$ mixing time for the Glauber dynamics on any $n$-vertex graph of constant maximum degree $\Delta$ when $\lambda<\lambda_c(\Delta)$ where $\lambda_c(\Delta)$ is the critical point for the uniqueness/non-uniqueness phase transition on the $\Delta$-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 $\Delta$ when the number of colors satisfies $q > \alpha \Delta$ where $\alpha \approx 1.763$, and $O(m\log{n})$ mixing for generating random matchings of any graph with bounded degree and $m$ edges.

This paper formalizes connections between stability of polynomials and convergence rates of Markov Chain Monte Carlo (MCMC) algorithms. We prove that if a (multivariate) partition function is nonzero in a region around a real point $\lambda$ then spectral independence holds at $\lambda$. As a consequence, for Holant-type problems (e.g., spin systems) on bounded-degree graphs, we obtain optimal $O(n\log n)$ mixing time bounds for the single-site update Markov chain known as the Glauber dynamics. Our result significantly improves the running time guarantees obtained via the polynomial interpolation method of Barvinok (2017), refined by Patel and Regts (2017). There are a variety of applications of our results. In this paper, we focus on Holant-type (i.e., edge-coloring) problems, including weighted edge covers and weighted even subgraphs. For the weighted edge cover problem (and several natural generalizations) we obtain an $O(n\log{n})$ sampling algorithm on bounded-degree graphs. The even subgraphs problem corresponds to the high-temperature expansion of the ferromagnetic Ising model. We obtain an $O(n\log{n})$ sampling algorithm for the ferromagnetic Ising model with a nonzero external field on bounded-degree graphs, which improves upon the classical result of Jerrum and Sinclair (1993) for this class of graphs. We obtain further applications to antiferromagnetic two-spin models on line graphs, weighted graph homomorphisms, tensor networks, and more.

We show that the natural Glauber dynamics mixes rapidly and generates a random proper edge-coloring of a graph with maximum degree $\Delta$ whenever the number of colors is at least $q\geq (\frac{10}{3} + \epsilon)\Delta$, where $\epsilon>0$ is arbitrary and the maximum degree satisfies $\Delta \geq C$ for a constant $C = C(\epsilon)$ depending only on $\epsilon$. For edge-colorings, this improves upon prior work \cite{Vig99, CDMPP19} which show rapid mixing when $q\geq (\frac{11}{3}-\epsilon_0 ) \Delta$, where $\epsilon_0 \approx 10^{-5}$ is a small fixed constant. At the heart of our proof, we establish a matrix trickle-down theorem, generalizing Oppenheim's influential result, as a new technique to prove that a high dimensional simplical complex is a local spectral expander.

For general antiferromagnetic 2-spin systems, including the hardcore model and the antiferromagnetic Ising model, there is an $\mathsf{FPTAS}$ for the partition function on graphs of maximum degree $\Delta$ when the infinite regular tree lies in the uniqueness region by Li et al. (2013). Moreover, in the tree non-uniqueness region, Sly (2010) showed that there is no $\mathsf{FPRAS}$ to estimate the partition function unless $\mathsf{NP}=\mathsf{RP}$. The algorithmic results follow from the correlation decay approach due to Weitz (2006) or the polynomial interpolation approach developed by Barvinok (2016). However the running time is only polynomial for constant $\Delta$. For the hardcore model, recent work of Anari et al. (2020) establishes rapid mixing of the simple single-site Markov chain known as the Glauber dynamics in the tree uniqueness region. Our work simplifies their analysis of the Glauber dynamics by considering the total pairwise influence of a fixed vertex $v$ on other vertices, as opposed to the total influence on $v$, thereby extending their work to all 2-spin models and improving the mixing time. More importantly our proof ties together the three disparate algorithmic approaches: we show that contraction of the tree recursions with a suitable potential function, which is the primary technique for establishing efficiency of Weitz's correlation decay approach and Barvinok's polynomial interpolation approach, also establishes rapid mixing of the Glauber dynamics. We emphasize that this connection holds for all 2-spin models (both antiferromagnetic and ferromagnetic), and existing proofs for correlation decay or polynomial interpolation immediately imply rapid mixing of Glauber dynamics. Our proof utilizes that the graph partition function divides that of Weitz's self-avoiding walk trees, leading to new tools for analyzing influence of vertices.

We show that the existence of a "good"' coupling w.r.t. Hamming distance for any local Markov chain on a discrete product space implies rapid mixing of the Glauber dynamics in a blackbox fashion. More specifically, we only require the expected distance between successive iterates under the coupling to be summable, as opposed to being one-step contractive in the worst case. Combined with recent local-to-global arguments \cite{CLV21}, we establish asymptotically optimal lower bounds on the standard and modified log-Sobolev constants for the Glauber dynamics for sampling from spin systems on bounded-degree graphs when a curvature condition \cite{Oll09} is satisfied. To achieve this, we use Stein's method for Markov chains \cite{BN19, RR19} to show that a "good" coupling for a local Markov chain yields strong bounds on the spectral independence of the distribution in the sense of \cite{ALO20}. Our primary application is to sampling proper list-colorings on bounded-degree graphs. In particular, combining the coupling for the flip dynamics given by \cite{Vig00, CDMPP19} with our techniques, we show optimal $O(n\log n)$ mixing for the Glauber dynamics for sampling proper list-colorings on any bounded-degree graph with maximum degree $\Delta$ whenever the size of the color lists are at least $\left(\frac{11}{6} - \epsilon\right)\Delta$, where $\epsilon \approx 10^{-5}$ is small constant. While $O(n^{2})$ mixing was already known before, our approach additionally yields Chernoff-type concentration bounds for Hamming Lipschitz functions in this regime, which was not known before. Our approach is markedly different from prior works establishing spectral independence for spin systems using spatial mixing \cite{ALO20, CLV20, CGSV20, FGYZ20}, which crucially is still open in this regime for proper list-colorings.

We prove tight mixing time bounds for natural random walks on bases of matroids, determinantal distributions, and more generally distributions associated with log-concave polynomials. For a matroid of rank $k$ on a ground set of $n$ elements, or more generally distributions associated with log-concave polynomials of homogeneous degree $k$ on $n$ variables, we show that the down-up random walk, started from an arbitrary point in the support, mixes in time $O(k\log k)$. Our bound has no dependence on $n$ or the starting point, unlike the previous analyses [ALOV19,CGM19], and is tight up to constant factors. The main new ingredient is a property we call approximate exchange, a generalization of well-studied exchange properties for matroids and valuated matroids, which may be of independent interest. In particular, given function $\mu: {[n] \choose k} \to \mathbb{R}_{\geq 0},$ our approximate exchange property implies that a simple local search algorithm gives a $k^{O(k)}$-approximation of $\max_{S} \mu(S)$ when $\mu$ is generated by a log-concave polynomial, and that greedy gives the same approximation ratio when $\mu$ is strongly Rayleigh. As an application, we show how to leverage down-up random walks to approximately sample random forests or random spanning trees in a graph with $n$ edges in time $O(n\log^2 n).$ The best known result for sampling random forest was a FPAUS with high polynomial runtime recently found by \cite{ALOV19, CGM19}. For spanning tree, we improve on the almost-linear time algorithm by [Sch18]. Our analysis works on weighted graphs too, and is the first to achieve nearly-linear running time for these problems.

We say a probability distribution $\mu$ 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 $\mu$ 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 $\mu$. 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}.

We design an FPRAS to count the number of bases of any matroid given by an independent set oracle, and to estimate the partition function of the random cluster model of any matroid in the regime where $0<q<1$. Consequently, we can sample random spanning forests in a graph and (approximately) compute the reliability polynomial of any matroid. We also prove the thirty year old conjecture of Mihail and Vazirani that the bases exchange graph of any matroid has expansion at least 1. One of our key observations is a close connection between pure simplicial complexes and multiaffine homogeneous polynomials. Specifically, if $X$ is a pure simplicial complex with positive weights on its maximal faces, we can associate with $X$ a multiaffine homogeneous polynomial $p_{X}$ such that the eigenvalues of the localized random walks on $X$ correspond to the eigenvalues of the Hessian of derivatives of $p_{X}$.