A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics

Authors Manuela Fischer, Mohsen Ghaffari



PDF
Thumbnail PDF

File

LIPIcs.DISC.2018.26.pdf
  • Filesize: 478 kB
  • 11 pages

Document Identifiers

Author Details

Manuela Fischer
  • ETH Zurich, Switzerland
Mohsen Ghaffari
  • ETH Zurich, Switzerland

Cite AsGet BibTex

Manuela Fischer and Mohsen Ghaffari. A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 26:1-26:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.DISC.2018.26

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Distributed Graph Algorithms
  • Parallel Algorithms
  • Local Algorithms
  • Locality
  • Sampling
  • Glauber Dynamics
  • Coloring

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Christophe Andrieu, Nando De Freitas, Arnaud Doucet, and Michael I. Jordan. An Introduction to MCMC for Machine Learning. Machine Learning, 50(1-2):5-43, 2003. Google Scholar
  2. Russ Bubley and Martin Dyer. Path Coupling: A Technique for Proving Rapid Mixing in Markov Chains. In the Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 223-231, 1997. Google Scholar
  3. Sitan Chen and Ankur Moitra. Linear Programming Bounds for Randomly Sampling Colorings. arXiv preprint arXiv:1804.03156, 2018. Google Scholar
  4. Michelle Delcourt, Guillem Perarnau, and Luke Postle. Rapid Mixing of Glauber Dynamics for Colorings Below Vigoda’s 11/6 Threshold. arXiv preprint arXiv:1804.04025, 2018. Google Scholar
  5. Roland L. Dobruschin. The Description of a Random Field by Means of Conditional Probabilities and Conditions of its Regularity. Theory of Probability &Its Applications, 13(2):197-224, 1968. Google Scholar
  6. Weiming Feng, Thomas P. Hayes, and Yitong Yin. Distributed Symmetry Breaking in Sampling (Optimal Distributed Randomly Coloring with Fewer Colors). arXiv preprint arXiv:1802.06953, 2018. Google Scholar
  7. Weiming Feng, Yuxin Sun, and Yitong Yin. What Can Be Sampled Locally? In Proceedings of the International Symposium on Principles of Distributed Computing (PODC), pages 121-130, 2017. Google Scholar
  8. Alan Frieze and Eric Vigoda. A Survey on the Use of Markov Chains to Randomly Sample Colourings. Oxford Lecture Series in Mathematics and its Applications, 34:53, 2007. Google Scholar
  9. Joseph Gonzalez, Yucheng Low, Arthur Gretton, and Carlos Guestrin. Parallel Gibbs Sampling: From Colored Fields to Thin Junction Trees. In the Proceedings of the International Conference on Artificial Intelligence and Statistics, pages 324-332, 2011. Google Scholar
  10. Heng Guo, Mark Jerrum, and Jingcheng Liu. Uniform Sampling Through the Lovász Local Lemma. Proceedings of the Symposium on Theory of Computing (STOC), pages 342-355, 2017. Google Scholar
  11. J. M. Hammersley and P. Clifford. Markov Fields on Finite Graphs and Lattices. Unpublished, available at http://www.statslab.cam.ac.uk/~grg/books/hammfest/hamm-cliff.pdf, 1971.
  12. Mark Jerrum. A Very Simple Algorithm for Estimating the Number of k-Colorings of a Low-Degree Graph. Random Structures &Algorithms, 7(2):157-165, 1995. Google Scholar
  13. Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random Generation of Combinatorial Structures from a Uniform Distribution. Theoretical Computer Science, 43:169-188, 1986. Google Scholar
  14. Nathan Linial. Distributive Graph Algorithms - Global Solutions From Local Data. In the Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 331-335. IEEE, 1987. Google Scholar
  15. Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics, 21(6):1087-1092, 1953. Google Scholar
  16. Surendra Nahar, Sartaj Sahni, and Eugene Shragowitz. Simulated Annealing and Combinatorial Optimization. In Proceedings of the Design Automation Conference, pages 293-299. IEEE Press, 1986. Google Scholar
  17. Moni Naor and Larry Stockmeyer. What Can Be Computed Locally? SIAM Journal on Computing, 24(6):1259-1277, 1995. Google Scholar
  18. David Newman, Padhraic Smyth, Max Welling, and Arthur U. Asuncion. Distributed Inference for Latent Dirichlet Allocation. In Advances in Neural Information Processing Systems, pages 1081-1088, 2008. Google Scholar
  19. Jesús Salas and Alan D. Sokal. Absence of Phase Transition for Antiferromagnetic Potts Models via the Dobrushin Uniqueness Theorem. Journal of Statistical Physics, 86(3-4):551-579, 1997. Google Scholar
  20. Eric Vigoda. Improved Bounds for Sampling Colorings. Journal of Mathematical Physics, 41(3):1555-1569, 2000. Google Scholar
  21. Feng Yan, Ningyi Xu, and Yuan Qi. Parallel Inference for Latent Dirichlet Allocation on Graphics Processing Units. In Advances in Neural Information Processing Systems, pages 2134-2142, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail