License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.26
URN: urn:nbn:de:0030-drops-98154
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9815/
Go to the corresponding LIPIcs Volume Portal

Fischer, Manuela ; Ghaffari, Mohsen

A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics

pdf-format:
LIPIcs-DISC-2018-26.pdf (0.5 MB)

Abstract

Sampling constitutes an important tool in a variety of areas: from machine learning and combinatorial optimization to computational physics and biology. A central class of sampling algorithms is the Markov Chain Monte Carlo method, based on the construction of a Markov chain with the desired sampling distribution as its stationary distribution. Many of the traditional Markov chains, such as the Glauber dynamics, do not scale well with increasing dimension. To address this shortcoming, we propose a simple local update rule based on the Glauber dynamics that leads to efficient parallel and distributed algorithms for sampling from Gibbs distributions.
Concretely, we present a Markov chain that mixes in O(log n) rounds when Dobrushin's condition for the Gibbs distribution is satisfied. This improves over the LubyGlauber algorithm by Feng, Sun, and Yin [PODC'17], which needs O(Delta log n) rounds, and their LocalMetropolis algorithm, which converges in O(log n) rounds but requires a considerably stronger mixing condition. Here, n denotes the number of nodes in the graphical model inducing the Gibbs distribution, and Delta its maximum degree. In particular, our method can sample a uniform proper coloring with alpha Delta colors in O(log n) rounds for any alpha >2, which almost matches the threshold of the sequential Glauber dynamics and improves on the alpha>2 + sqrt{2} threshold of Feng et al.

BibTeX - Entry

@InProceedings{fischer_et_al:LIPIcs:2018:9815,
  author =	{Manuela Fischer and Mohsen Ghaffari},
  title =	{{A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{26:1--26:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9815},
  URN =		{urn:nbn:de:0030-drops-98154},
  doi =		{10.4230/LIPIcs.DISC.2018.26},
  annote =	{Keywords: Distributed Graph Algorithms, Parallel Algorithms, Local Algorithms, Locality, Sampling, Glauber Dynamics, Coloring}
}

Keywords: Distributed Graph Algorithms, Parallel Algorithms, Local Algorithms, Locality, Sampling, Glauber Dynamics, Coloring
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI