Efthymiou, Charilaos
On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs
Abstract
In this paper, we present a novel, polynomial time, algorithm for approximate sampling from symmetric Gibbs distributions on the sparse random graph and hypergraph. The examples of symmetric distributions we consider here include some important distributions on spinsystems and spinglasses. These are: the qstate antiferromagnetic Potts model for q ≥ 2, including the (hyper)graph Ising model and random colourings. The uniform distribution over the NotAllEqual solutions of a random kSAT formula. Finally, we consider sampling from the spinglass distribution called the kspin model, i.e., this is the "diluted" version of the wellknown SherringtonKirkpatrick model. Spinglasses give rise to very intricate distributions which are also studied in mathematics, in neural computation, computational biology and many other areas. To our knowledge, this is the first rigorously analysed efficient sampling algorithm for spinglasses which operates in a non trivial range of the parameters of the distribution.
We present, what we believe to be, an elegant sampling algorithm. Our algorithm is unique in its approach and does not belong to any of the wellknown families of sampling algorithms. We derive it by investigating the power and the limits of the approach that was introduced in [Efthymiou: SODA 2012] and combine it, in a novel way, with powerful notions from the Cavity method.
Specifically, for a symmetric Gibbs distribution μ on the random (hyper)graph whose parameters are within an appropriate range, our sampling algorithm has the following properties: with probability 1o(1) over the instances of the input (hyper)graph, it generates a configuration which is distributed within total variation distance n^{Ω(1)} from μ. The time complexity is O((nlog n)²), where n is the size of the input (hyper)graph.
We make a notable progress regarding impressive predictions of physicists relating phasetransitions of Gibbs distributions with the efficiency of the corresponding sampling algorithms. For most (if not all) the cases we consider here, our algorithm outperforms by far any other sampling algorithms in terms of the permitted range of the parameters of the Gibbs distributions.
The use of notions and ideas from the Cavity method provides a new insight to the sampling problem. Our results imply that there is a lot of potential for further exploiting the Cavity method for algorithmic design.
BibTeX  Entry
@InProceedings{efthymiou:LIPIcs.ICALP.2022.57,
author = {Efthymiou, Charilaos},
title = {{On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {57:157:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16398},
URN = {urn:nbn:de:0030drops163982},
doi = {10.4230/LIPIcs.ICALP.2022.57},
annote = {Keywords: spinsystem, spinglass, sparse random (hyper)graph, approximate sampling, efficient algorithm}
}
28.06.2022
Keywords: 

spinsystem, spinglass, sparse random (hyper)graph, approximate sampling, efficient algorithm 
Seminar: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Issue date: 

2022 
Date of publication: 

28.06.2022 