
Rapid Mixing SwendsenWang Sampler for Stochastic Partitioned Attractive Models
The Gibbs sampler is a particularly popular Markov chain used for learning and inference problems in Graphical Models (GMs). These tasks are computationally intractable in general, and the Gibbs sampler often suffers from slow mixing. In this paper, we study the SwendsenWang dynamics which is a more sophisticated Markov chain designed to overcome bottlenecks that impede the Gibbs sampler. We prove O( n) mixing time for attractive binary pairwise GMs (i.e., ferromagnetic Ising models) on stochastic partitioned graphs having n vertices, under some mild conditions, including low temperature regions where the Gibbs sampler provably mixes exponentially slow. Our experiments also confirm that the SwendsenWang sampler significantly outperforms the Gibbs sampler when they are used for learning parameters of attractive GMs.
04/06/2017 ∙ by Sejun Park, et al. ∙ 0 ∙ shareread it

Structure Learning of Hcolorings
We study the structure learning problem for graph homomorphisms, commonly referred to as Hcolorings, including the weighted case which corresponds to spin systems with hard constraints. The learning problem is as follows: for a fixed (and known) constraint graph H with q colors and an unknown graph G=(V,E) with n vertices, given uniformly random Hcolorings of G, how many samples are required to learn the edges of the unknown graph G? We give a characterization of H for which the problem is identifiable for every G, i.e., we can learn G with an infinite number of samples. We focus particular attention on the case of proper vertex qcolorings of graphs of maximum degree d where intriguing connections to statistical physics phase transitions appear. We prove that when q>d the problem is identifiable and we can learn G in poly(d,q)× O(n^2n) time. In contrast for softconstraint systems, such as the Ising model, the best possible running time is exponential in d. When q≤ d we prove that the problem is not identifiable, and we cannot hope to learn G. When q<d√(d) + Θ(1) we prove that even learning an equivalent graph (any graph with the same set of Hcolorings) is computationally hardsample complexity is exponential in n in the worstcase. For the qcolorings problem, the threshold for efficient learning seems to be connected to the uniqueness/nonuniqueness phase transition at q=d. We explore this connection for general Hcolorings and prove that under a wellknown condition in statistical physics, known as Dobrushin uniqueness condition, we can learn G in poly(d,q)× O(n^2n) time.
08/17/2017 ∙ by Antonio Blanca, et al. ∙ 0 ∙ shareread it

On Counting Perfect Matchings in General Graphs
Counting perfect matchings has played a central role in the theory of counting problems. The permanent, corresponding to bipartite graphs, was shown to be #Pcomplete to compute exactly by Valiant (1979), and a fully polynomial randomized approximation scheme (FPRAS) was presented by Jerrum, Sinclair, and Vigoda (2004) using a Markov chain Monte Carlo (MCMC) approach. However, it has remained an open question whether there exists an FPRAS for counting perfect matchings in general graphs. In fact, it was unresolved whether the same Markov chain defined by JSV is rapidly mixing in general. In this paper, we show that it is not. We prove torpid mixing for any weighting scheme on hole patterns in the JSV chain. As a first step toward overcoming this obstacle, we introduce a new algorithm for counting matchings based on the GallaiEdmonds decomposition of a graph, and give an FPRAS for counting matchings in graphs that are sufficiently close to bipartite. In particular, we obtain a fixedparameter tractable algorithm for counting matchings in general graphs, parameterized by the greatest "order" of a factorcritical subgraph.
12/20/2017 ∙ by Daniel Stefankovic, et al. ∙ 0 ∙ shareread it

Sampling in Uniqueness from the Potts and RandomCluster Models on Random Regular Graphs
We consider the problem of sampling from the Potts model on random regular graphs. It is conjectured that sampling is possible when the temperature of the model is in the uniqueness regime of the regular tree, but positive algorithmic results have been for the most part elusive. In this paper, for all integers q≥ 3 and Δ≥ 3, we develop algorithms that produce samples within error o(1) from the qstate Potts model on random Δregular graphs, whenever the temperature is in uniqueness, for both the ferromagnetic and antiferromagnetic cases. The algorithm for the antiferromagnetic Potts model is based on iteratively adding the edges of the graph and resampling a bichromatic class that contains the endpoints of the newly added edge. Key to the algorithm is how to perform the resampling step efficiently since bichromatic classes may induce linearsized components. To this end, we exploit the tree uniqueness to show that the average growth of bichromatic components is typically small, which allows us to use correlation decay algorithms for the resampling step. While the precise uniqueness threshold on the tree is not known for general values of q and Δ in the antiferromagnetic case, our algorithm works throughout uniqueness regardless of its value. In the case of the ferromagnetic Potts model, we simplify the algorithm significantly by utilising the randomcluster representation of the model. In particular, we show that a percolationtype algorithm succeeds in sampling from the randomcluster model with parameters p,q on random Δregular graphs for all values of q≥ 1 and p<p_c(q,Δ), where p_c(q,Δ) corresponds to a uniqueness threshold for the model on the Δregular tree. When restricted to integer values of q, this yields a simplified algorithm for the ferromagnetic Potts model on random Δregular graphs.
04/22/2018 ∙ by Antonio Blanca, et al. ∙ 0 ∙ shareread it

SwendsenWang Dynamics for General Graphs in the Tree Uniqueness Region
The SwendsenWang dynamics is a popular algorithm for sampling from the Gibbs distribution for the ferromagnetic Ising model on a graph G=(V,E). The dynamics is a "global" Markov chain which is conjectured to converge to equilibrium in O(V^1/4) steps for any graph G at any (inverse) temperature β. It was recently proved by Guo and Jerrum (2017) that the SwendsenWang dynamics has polynomial mixing time on any graph at all temperatures, yet there are few results providing o(V) upper bounds on its convergence time. We prove fast convergence of the SwendsenWang dynamics on general graphs in the tree uniqueness region of the ferromagnetic Ising model. In particular, when β < β_c(d) where β_c(d) denotes the uniqueness/nonuniqueness threshold on infinite dregular trees, we prove that the relaxation time (i.e., the inverse spectral gap) of the SwendsenWang dynamics is Θ(1) on any graph of maximum degree d ≥ 3. Our proof utilizes a version of the SwendsenWang dynamics which only updates isolated vertices. We establish that this variant of the SwendsenWang dynamics has mixing time O(V) and relaxation time Θ(1) on any graph of maximum degree d for all β < β_c(d). We believe that this Markov chain may be of independent interest, as it is a monotone SwendsenWang type chain. As part of our proofs, we provide modest extensions of the technology of Mossel and Sly (2013) for analyzing mixing times and of the censoring result of Peres and Winkler (2013). Both of these results are for the Glauber dynamics, and we extend them here to general monotone Markov chains. This class of dynamics includes for example the heatbath block dynamics, for which we obtain new tight mixing time bounds.
06/12/2018 ∙ by Antonio Blanca, et al. ∙ 0 ∙ shareread it

Markov chains for the hardcore model via polymer models
Jenssen, Keevash and Perkins give an FPTAS and an efficient sampling algorithm for the highfugacity hardcore model on boundeddegree bipartite expander graphs. Their method is based on using the cluster expansion to obtain a zerofree region for a socalled polymer model partition function in the complex plane, and then approximating the polymer partition function using the Taylor series truncation method of Barvinok. We circumvent the zerofree analysis and the generalisation to complex fugacities, showing that the polymer partition function can be approximated using Glauber dynamics on polymers. The proof that polymer Glauber dynamics mixes rapidly is easy and is based on using the sizes of the disagreeing polymers as a distance function. We then use Markov chain comparison to show that the hardcore partition function can be approximated using spin Glauber dynamics restricted to even and odd dominant portions of the state space. Our techniques also apply to the Ferromagnetic Potts model.
01/20/2019 ∙ by Zongchen Chen, et al. ∙ 0 ∙ shareread it

Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the model M and a sampling oracle for the distribution μ_M̂ of an unknown model M̂, can we efficiently determine if the two models M and M̂ are the same? We consider identity testing for both softconstraint and hardconstraint systems. In particular, we prove hardness results in two prototypical cases, the Ising model and proper colorings, and explore whether identity testing is any easier than structure learning. For the ferromagnetic (attractive) Ising model, Daskalasis et al. (2018) presented a polynomial time algorithm for identity testing. We prove hardness results in the antiferromagnetic (repulsive) setting in the same regime of parameters where structure learning is known to require a superpolynomial number of samples. In particular, for nvertex graphs of maximum degree d, we prove that if β d = ω(n) (where β is the inverse temperature parameter), then there is no polynomial running time identity testing algorithm unless RP=NP. We also establish computational lower bounds for a broader set of parameters under the (randomized) exponential time hypothesis. Our proofs utilize insights into the design of gadgets using random graphs in recent works concerning the hardness of approximate counting by Sly (2010). In the hardconstraint setting, we present hardness results for identity testing for proper colorings. Our results are based on the presumed hardness of #BIS, the problem of (approximately) counting independent sets in bipartite graphs. In particular, we prove that identity testing is hard in the same range of parameters where structure learning is known to be hard.
01/22/2019 ∙ by Ivona Bezakova, et al. ∙ 0 ∙ shareread it
Eric Vigoda
is this you? claim profile