Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSpectral independence, coupling with the stationary distribution, and the spectral gap of the Glauber dynamics
103
0
0.0
(
0
)
Added by
Vishesh Jain
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present a new lower bound on the spectral gap of the Glauber dynamics for the Gibbs distribution of a spectrally independent $q$-spin system on a graph $G = (V,E)$ with maximum degree $Delta$. Notably, for several interesting examples, our bound covers the entire regime of $Delta$ excluded by arguments based on coupling with the stationary distribution. As concrete applications, by combining our new lower bound with known spectral independence computations and known coupling arguments: (1) We show that for a triangle-free graph $G = (V,E)$ with maximum degree $Delta geq 3$, the Glauber dynamics for the uniform distribution on proper $k$-colorings with $k geq (1.763dots + delta)Delta$ colors has spectral gap $tilde{Omega}_{delta}(|V|^{-1})$. Previously, such a result was known either if the girth of $G$ is at least $5$ [Dyer et.~al, FOCS 2004], or under restrictions on $Delta$ [Chen et.~al, STOC 2021; Hayes-Vigoda, FOCS 2003]. (2) We show that for a regular graph $G = (V,E)$ with degree $Delta geq 3$ and girth at least $6$, and for any $varepsilon, delta > 0$, the partition function of the hardcore model with fugacity $lambda leq (1-delta)lambda_{c}(Delta)$ may be approximated within a $(1+varepsilon)$-multiplicative factor in time $tilde{O}_{delta}(n^{2}varepsilon^{-2})$. Previously, such a result was known if the girth is at least $7$ [Efthymiou et.~al, SICOMP 2019]. (3) We show for the binomial random graph $G(n,d/n)$ with $d = O(1)$, with high probability, an approximately uniformly random matching may be sampled in time $O_{d}(n^{2+o(1)})$. This improves the corresponding running time of $tilde{O}_{d}(n^{3})$ due to [Jerrum-Sinclair, SICOMP 1989; Jerrum, 2003].
rate research
Read More
We prove an optimal $Omega(n^{-1})$ lower bound on the spectral gap of Glauber dynamics for anti-ferromagnetic two-spin systems with $n$ vertices in the tree uniqueness regime. This spectral gap holds for all, including unbounded, maximum degree $Delta$. Consequently, we have the following mixing time bounds for the models satisfying the uniqueness condition with a slack $deltain(0,1)$: $bullet$ $C(delta) n^2log n$ mixing time for the hardcore model with fugacity $lambdale (1-delta)lambda_c(Delta)= (1-delta)frac{(Delta - 1)^{Delta - 1}}{(Delta - 2)^Delta}$; $bullet$ $C(delta) n^2$ mixing time for the Ising model with edge activity $betainleft[frac{Delta-2+delta}{Delta-delta},frac{Delta-delta}{Delta-2+delta}right]$; where the maximum degree $Delta$ may depend on the number of vertices $n$, and $C(delta)$ depends only on $delta$. Our proof is built upon the recently developed connections between the Glauber dynamics for spin systems and the high-dimensional expander walks. In particular, we prove a stronger notion of spectral independence, called the complete spectral independence, and use a novel Markov chain called the field dynamics to connect this stronger spectral independence to the rapid mixing of Glauber dynamics for all degrees.
We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [ALO20]) from the Boolean domain to general discrete domains. This property characterises distributions with limited correlations, and implies that the corresponding Glauber dynamics is rapidly mixing. As a concrete application, we show that Glauber dynamics for sampling proper $q$-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree $Delta$ provided $qge (alpha^*+delta)Delta$ where $alpha^*approx 1.763$ is the unique solution to $alpha^*=exp(1/alpha^*)$ and $delta>0$ is any constant. This is the first efficient algorithm for sampling proper $q$-colourings in this regime with possibly unbounded $Delta$. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [GMP05].
The spectral gap of a Markov chain can be bounded by the spectral gaps of constituent restriction chains and a projection chain, and the strength of such a bound is the content of various decomposition theorems. In this paper, we introduce a new parameter that allows us to improve upon these bounds. We further define a notion of orthogonality between the restriction chains and complementary restriction chains. This leads to a new Complementary Decomposition theorem, which does not require analyzing the projection chain. For $epsilon$-orthogonal chains, this theorem may be iterated $O(1/epsilon)$ times while only giving away a constant multiplicative factor on the overall spectral gap. As an application, we provide a $1/n$-orthogonal decomposition of the nearest neighbor Markov chain over $k$-class biased monotone permutations on [$n$], as long as the number of particles in each class is at least $Clog n$. This allows us to apply the Complementary Decomposition theorem iteratively $n$ times to prove the first polynomial bound on the spectral gap when $k$ is as large as $Theta(n/log n)$. The previous best known bound assumed $k$ was at most a constant.
We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph $G$ on $n$ vertices described by a binary string of length $N$, an integer $kleq log n$, and an error parameter $epsilon > 0$, our algorithm runs in space $tilde{O}(klog (Ncdot w_{mathrm{max}}/w_{mathrm{min}}))$ where $w_{mathrm{max}}$ and $w_{mathrm{min}}$ are the maximum and minimum edge weights in $G$, and produces a weighted graph $H$ with $tilde{O}(n^{1+2/k}/epsilon^2)$ edges that spectrally approximates $G$, in the sense of Spielmen and Teng [ST04], up to an error of $epsilon$. Our algorithm is based on a new bounded-independence analysis of Spielman and Srivastavas effective resistance based edge sampling algorithm [SS08] and uses results from recent work on space-bounded Laplacian solvers [MRSV17]. In particular, we demonstrate an inherent tradeoff (via upper and lower bounds) between the amount of (bounded) independence used in the edge sampling algorithm, denoted by $k$ above, and the resulting sparsity that can be achieved.
Aldous and Fill conjectured that the maximum relaxation time for the random walk on a connected regular graph with $n$ vertices is $(1+o(1)) frac{3n^2}{2pi^2}$. This conjecture can be rephrased in terms of the spectral gap as follows: the spectral gap (algebraic connectivity) of a connected $k$-regular graph on $n$ vertices is at least $(1+o(1))frac{2kpi^2}{3n^2}$, and the bound is attained for at least one value of $k$. Based upon previous work of Brand, Guiduli, and Imrich, we prove this conjecture for cubic graphs. We also investigate the structure of quartic (i.e. 4-regular) graphs with the minimum spectral gap among all connected quartic graphs. We show that they must have a path-like structure built from specific blocks.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
