caa a22 4500 555285502 20190715031130.0 cr unu---uuuuu 190206s2018 xx s 100 0 eng 10.3929/ethz-b-000315332 doi 10.4230/LIPIcs.DISC.2018.26 doi (ETHRESEARCH)oai:www.research-collection.ethz.ch:20.500.11850/315332 Fischer Manuela A simple parallel and distributed sampling technique: Local glauber dynamics [Elektronische Daten] [Manuela Fischer, Mohsen Ghaffari, Ulrich Schmid (Editor), Josef Widder (Editor)] Leibniz int. proc. inform. Dagstuhl Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018 Open access ethresearch 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. 32nd International Symposium on Distributed Computing (DISC 2018) in New Orleans, LA, USA (October 15-19, 2018) Creative Commons Attribution 3.0 Unported http://creativecommons.org/licenses/by/3.0 ethresearch Distributed Graph Algorithms ethresearch Parallel Algorithms ethresearch Local Algorithms ethresearch Locality ethresearch Sampling ethresearch Glauber Dynamics ethresearch Coloring ethresearch Ghaffari Mohsen joint author Schmid Ulrich Editor edt Widder Josef Editor edt 32nd International Symposium on Distributed Computing (DISC 2018) Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik pp. 26:1-26:11 978-3-95977-092-7 http://hdl.handle.net/20.500.11850/315332 text/html WWW-Backlink auf das Repository (Open access) 1 Conference Paper ethresearch ETHRESEARCH 856 40 http://hdl.handle.net/20.500.11850/315332 text/html WWW-Backlink auf das Repository (Open access) ETHRESEARCH 100 1- Fischer Manuela ETHRESEARCH 700 1- Ghaffari Mohsen joint author ETHRESEARCH 700 1- Schmid Ulrich Editor edt ETHRESEARCH 700 1- Widder Josef Editor edt ETHRESEARCH 773 0- 32nd International Symposium on Distributed Computing (DISC 2018) Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik pp. 26:1-26:11 978-3-95977-092-7 BK010053 XK010053 XK010000 ETHRESEARCH ETHRESEARCH ETHRESEARCH Conference Paper Open access