On Sampling Diluted Spin-Glasses Using Glauber Dynamics

Abstract

{\em Spin-glasses} are natural Gibbs distributions that have been studied in theoretical computer science for many decades. Recently, they have been gaining renewed attention from the community as they emerge naturally in {\em neural computation} and {\em learning}, {\em network inference}, {\em optimisation} and many other areas. Here we consider the {\em 2-spin model} at inverse temperature $\beta$ when the underlying graph is an instance of $G(n, d/n)$, i.e., the random graph on $n$ vertices such that each edge appears independently with probability $d/n$, where the expected degree $d=\Theta(1)$. We study the problem of efficiently sampling from the aforementioned distribution using the well-known Markov chain called {\em Glauber dynamics}. For a certain range of $\beta$, that depends only on the expected degree $d$ of the graph, and for typical instances of the 2-spin model on $G(n, d/n)$, we show that the corresponding (single-site) Glauber dynamics exhibits mixing time $O\left(n^{2+\frac{3}{\log^2 d}}\right)$. The range of $\beta$ for which we obtain our rapid mixing result corresponds to the expected influence being smaller than $1/d$. We establish our results by utilising the well-known {\em path-coupling} technique. In the standard setting of Glauber dynamics on $G(n, d/n)$ one has to deal with the so-called effect of high degree vertices. % in the path-coupling analysis. Here, with the spin-glasses, rather than considering vertex-degrees, it is more natural to use a different measure on the vertices of the graph, that we call {\em aggregate influence}. We build on the block-construction approach proposed by [Dyer, Flaxman, Frieze and Vigoda: 2006] to circumvent the problem with the high degrees in the path-coupling analysis. Specifically, to obtain our results, we first establish rapid mixing for an appropriately defined block-dynamics. We design this dynamics such that vertices of large aggregate influence are placed deep inside their blocks. Then, we obtain rapid mixing for the (single-site) Glauber dynamics by utilising a comparison argument.