On sampling symmetric Gibbs distributions on sparse random (hyper)graphs with contiguity
Charilaos Efthymiou
In this talk, we present efficient algorithms for
approximate sampling from symmetric Gibbs distributions on the sparse
random (hyper)graph. The examples we consider include (but are not
restricted to) some important distributions on spin systems and
spin-glasses.
We consider the $q$ state antiferromagnetic Potts model for $q\geq
2$, including the random colourings. We also consider the uniform
distributions over the Not-All-Equal solutions of random $k$-CNF
formulas. Finally, we present an algorithm for sampling from the
{\em spin-glass} distribution called the $k$-spin model. To our
knowledge this is the first, rigorously analysed, efficient algorithm
for spin-glasses which operates in a non trivial range of the
parameters of the distribution.
We rely on the approach that was introduced in [Efthymiou: SODA 2012].
For a symmetric Gibbs distribution $\mu$ on a random (hyper)graph
whose parameters are within an appropriate range, our sampling
algorithm has the following properties: with probability $1-o(1)$
over the instances of the input (hyper)graph, it generates a
configuration which is distributed within total variation distance
$n^{-\Omega(1)}$ from $\mu$. The time complexity is $O(n^{2}\log n)$,
where $n$ is the size of the input (hyper)graph.
It is evident that the algorithm requires a range of the parameters
of the Gibbs distributions that coincides with those of the
tree-uniqueness region, parameterized w.r.t. the expected degree $d$.
To be more precise, this is true for distributions such that the
uniqueness region is well-known. For cases like e.g., the
anti-ferromagnetic Potts the algorithm works for the range of
parameters which corresponds to what is conjectured to be the tree
uniqueness.
For many of the distributions we consider here, we are far from
establishing what is believed to be their tree uniqueness region.
This imposes certain limitations to our purposes. That is, for a
given set of the parameters of the Gibbs distribution we cannot use
that the corresponding tree recursions converge to the desired fixed
point. To this end, we build a novel approach which utilises the
notion of {\em contiguity} between Gibbs distributions and the
so-called {\em teacher-student model}, with the later distribution
also known in various contexts as the {\em planted model}. With
this approach we bring together tools and notions from sampling
algorithms and statistical inference algorithms.