Document Open Access Logo

Rapid Mixing of Global Markov Chains via Spectral Independence: The Unbounded Degree Case

Authors Antonio Blanca, Xusheng Zhang

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2023.53.pdf
  • Filesize: 0.81 MB
  • 19 pages

Document Identifiers

Author Details

Antonio Blanca
  • Pennsylvania State University, University Park, PA, USA
Xusheng Zhang
  • Pennsylvania State University, University Park, PA, USA

Funding

The research is supported in part by NSF grant CCF-2143762.

Acknowledgements

The authors thank the anonymous referees for their constructive comments during the manuscript review process.

Cite As Get BibTex

Antonio Blanca and Xusheng Zhang. Rapid Mixing of Global Markov Chains via Spectral Independence: The Unbounded Degree Case. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 53:1-53:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.53

Abstract

We consider spin systems on general n-vertex graphs of unbounded degree and explore the effects of spectral independence on the rate of convergence to equilibrium of global Markov chains. Spectral independence is a novel way of quantifying the decay of correlations in spin system models, which has significantly advanced the study of Markov chains for spin systems. We prove that whenever spectral independence holds, the popular Swendsen-Wang dynamics for the q-state ferromagnetic Potts model on graphs of maximum degree Δ, where Δ is allowed to grow with n, converges in O((Δ log n)^c) steps where c > 0 is a constant independent of Δ and n. We also show a similar mixing time bound for the block dynamics of general spin systems, again assuming that spectral independence holds. Finally, for monotone spin systems such as the Ising model and the hardcore model on bipartite graphs, we show that spectral independence implies that the mixing time of the systematic scan dynamics is O(Δ^c log n) for a constant c > 0 independent of Δ and n. Systematic scan dynamics are widely popular but are notoriously difficult to analyze. This result implies optimal O(log n) mixing time bounds for any systematic scan dynamics of the ferromagnetic Ising model on general graphs up to the tree uniqueness threshold. Our main technical contribution is an improved factorization of the entropy functional: this is the common starting point for all our proofs. Specifically, we establish the so-called k-partite factorization of entropy with a constant that depends polynomially on the maximum degree of the graph.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
  • Mathematics of computing → Gibbs sampling
Keywords
  • Markov chains
  • Spectral Independence
  • Potts model
  • Mixing Time

Metrics

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

Related Versions

References

  1. Dimitris Achlioptas and Assaf Naor. The two possible values of the chromatic number of a random graph. Annals of Mathematics, 162(3):1335-1351, 2005. Google Scholar
  2. Kenneth S. Alexander. On weak mixing in lattice models. Probab. Theory Relat. Fields, 110(441-471), 1998. Google Scholar
  3. Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong. Entropic independence: Optimal mixing of down-up random walks. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 1418-1430, New York, NY, USA, 2022. Association for Computing Machinery. URL: https://doi.org/10.1145/3519935.3520048.
  4. Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. Spectral independence in high-dimensional expanders and applications to the hardcore model. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1319-1330, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00125.
  5. Vincent Beffara and Hugo Duminil-Copin. The self-dual point of the two-dimensional random-cluster model is critical for q ≥ 1. Probab. Theory Relat. Fields, 153(511-542), 2012. Google Scholar
  6. Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Stefankovic, and Eric Vigoda. On mixing of Markov chains: coupling, spectral independence, and entropy factorization. Electronic Journal of Probability, 27:1-42, 2022. URL: https://doi.org/10.1214/22-EJP867.
  7. Antonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair, and Eric Vigoda. Entropy decay in the Swendsen–Wang dynamics on ℤ^d. The Annals of Applied Probability, 32(2):1018-1057, 2022. URL: https://doi.org/10.1214/21-AAP1702.
  8. Antonio Blanca, Pietro Caputo, Alistair Sinclair, and Eric Vigoda. Spatial mixing and nonlocal markov chains. Random Structures & Algorithms, 55(3):584-614, 2019. URL: https://doi.org/10.1002/rsa.20844.
  9. Antonio Blanca, Zongchen Chen, Daniel Stefankovic, and Eric Vigoda. The Swendsen–Wang dynamics on trees. Random Structures & Algorithms, 2023. Google Scholar
  10. Antonio Blanca, Zongchen Chen, and Eric Vigoda. Swendsen-wang dynamics for general graphs in the tree uniqueness region. Random Structures & Algorithms, 56(2):373-400, 2020. Google Scholar
  11. Antonio Blanca and Alistair Sinclair. Dynamics for the mean-field random-cluster model. In Proceedings of APPROX/RANDOM, 2015. Google Scholar
  12. Antonio Blanca and Xusheng Zhang. Rapid mixing of global markov chains via spectral independence: the unbounded degree case. arXiv preprint arXiv:2307.00683, 2023. Google Scholar
  13. Sergey Bobkov and Prasad Tetali. Modified log-sobolev inequalities, mixing and hypercontractivity. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC '03, pages 287-296, New York, NY, USA, 2003. Association for Computing Machinery. URL: https://doi.org/10.1145/780542.780586.
  14. Magnus Bordewich, Catherine Greenhill, and Viresh Patel. Mixing of the glauber dynamics for the ferromagnetic potts model. Random Structures & Algorithms., 48(1):21-52, January 2016. URL: http://dro.dur.ac.uk/15252/.
  15. Christian Borgs, Jennifer T. Chayes, and Prasad Tetali. Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point. Probab. Theory Relat. Fields, 152(3-4):509-557, 2012. URL: https://doi.org/10.1007/s00440-010-0329-0.
  16. Pietro Caputo, Georg Menz, and Prasad Tetali. Approximate tensorization of entropy at high temperature, 2014. URL: https://doi.org/10.48550/arXiv.1405.0608.
  17. Pietro Caputo and Daniel Parisi. Block factorization of the relative entropy via spatial mixing. Communications in Mathematical Physics, 388(2):793-818, October 2021. URL: https://doi.org/10.1007/s00220-021-04237-1.
  18. Filippo Cesi. Quasi-factorization of the entropy and logarithmic Sobolev inequalities for Gibbs random fields. Probability Theory and Related Fields, 120:569-584, 2001. Google Scholar
  19. Xiaoyu Chen, Weiming Feng, Yitong Yin, and Xinyuan Zhang. Optimal mixing for two-state anti-ferromagnetic spin systems. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 588-599. IEEE, 2022. Google Scholar
  20. Xiaoyu Chen, Weiming Feng, Yitong Yin, and Xinyuan Zhang. Rapid mixing of glauber dynamics via spectral independence for all degrees. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 137-148, 2022. URL: https://doi.org/10.1109/FOCS52979.2021.00022.
  21. Xiaoyu Chen, Jingcheng Liu, and Yitong Yin. Uniqueness and rapid mixing in the bipartite hardcore model, 2023. URL: https://arxiv.org/abs/2305.00186.
  22. Zongchen Chen, Andreas Galanis, Daniel Stefankovic, and Eric Vigoda. Rapid mixing for colorings via spectral independence. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1548-1557, 2021. Google Scholar
  23. Zongchen Chen, Kuikui Liu, Nitya Mani, and Ankur Moitra. Strong spatial mixing for colorings on trees and its algorithmic applications, 2023. URL: https://arxiv.org/abs/2304.01954.
  24. Zongchen Chen, Kuikui Liu, and Eric Vigoda. Rapid mixing of Glauber dynamics up to uniqueness via contraction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1307-1318. IEEE Computer Society, 2020. Google Scholar
  25. Zongchen Chen, Kuikui Liu, and Eric Vigoda. Optimal mixing of glauber dynamics: Entropy factorization via high-dimensional expansion. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, pages 1537-1550, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3406325.3451035.
  26. Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Štefankovič, and Eric Vigoda. Metastability of the Potts ferromagnet on random regular graphs. Communications in Mathematical Physics, 2023. URL: https://doi.org/10.1007/s00220-023-04644-6.
  27. P. Diaconis and L. Saloff-Coste. Logarithmic Sobolev inequalities for finite Markov chains. The Annals of Applied Probability, 6(3):695-750, 1996. URL: https://doi.org/10.1214/aoap/1034968224.
  28. Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. Dobrushin conditions and systematic scan. In Josep Díaz, Klaus Jansen, José D. P. Rolim, and Uri Zwick, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 327-338, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. Google Scholar
  29. Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. Systematic scan for sampling colorings. The Annals of Applied Probability, 16(1):185-230, 2006. Google Scholar
  30. Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. Matrix norms and rapid mixing for spin systems. The Annals of Applied Probability, 19(1):71-107, 2009. Google Scholar
  31. Martin Dyer, Alistair Sinclair, Eric Vigoda, and Dror Weitz. Mixing in time and space for lattice spin systems: A combinatorial view. Random Structures & Algorithms, 24(4):461-479, 2004. URL: https://doi.org/10.1002/rsa.20004.
  32. Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang. Rapid mixing from spectral independence beyond the boolean domain. ACM Trans. Algorithms, 18(3), October 2022. URL: https://doi.org/10.1145/3531008.
  33. James Allen Fill. Eigenvalue Bounds on Convergence to Stationarity for Nonreversible Markov Chains, with an Application to the Exclusion Process. The Annals of Applied Probability, 1(1):62-87, 1991. URL: https://doi.org/10.1214/aoap/1177005981.
  34. James Allen Fill and Jonas Kahn. Comparison inequalities and fastest-mixing Markov chains. The Annals of Applied Probability, 23(5):1778-1816, 2013. URL: https://doi.org/10.1214/12-AAP886.
  35. Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Swendsen-Wang algorithm on the mean-field Potts model. In Proceedings of APPROX/RANDOM, 2015. Google Scholar
  36. Reza Gheissari and Eyal Lubetzky. Mixing times of critical two-dimensional Potts models. Comm. Pure Appl. Math, 71(5):994-1046, 2018. Google Scholar
  37. Reza Gheissari, Eyal Lubetzky, and Yuval Peres. Exponentially slow mixing in the mean-field Swendsen-Wang dynamics. Annales de l'Institut Henri Poincare (B), 2019. Extended abstract appeared in Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 1981-1988. Google Scholar
  38. Vivek K. Gore and Mark R. Jerrum. The Swendsen-Wang process does not always mix rapidly. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC '97, pages 674-681, New York, NY, USA, 1997. Association for Computing Machinery. URL: https://doi.org/10.1145/258533.258662.
  39. Heng Guo and Mark Jerrum. Random cluster dynamics for the Ising model is rapidly mixing. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pages 1818-1827, 2017. Google Scholar
  40. Heng Guo, Kaan Kara, and Ce Zhang. Layerwise systematic scan: Deep Boltzmann machines and beyond. In International Conference on Artificial Intelligence and Statistics, pages 178-187. PMLR, 2018. Google Scholar
  41. Thomas P. Hayes. A simple condition implying rapid mixing of single-site dynamics on spin systems. In The 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 39-46, 2006. URL: https://doi.org/10.1109/FOCS.2006.6.
  42. Thomas P. Hayes and Alistair Sinclair. A general lower bound for mixing of single-site dynamics on graphs. The Annals of Applied Probability, 17(3), June 2007. URL: https://doi.org/10.1214/105051607000000104.
  43. Mark Huber. A bounding chain for Swendsen-Wang. Random Structures & Algorithms, 22(1):43-59, 2003. Google Scholar
  44. Vishesh Jain, Huy Tuan Pham, and Thuy-Duong Vuong. Spectral independence, coupling, and the spectral gap of the glauber dynamics. Information Processing Letters, 177:106268, 2022. Google Scholar
  45. F. Martinelli, E. Olivieri, and R. H. Schonmann. For 2-D lattice spin systems weak mixing implies strong mixing. Communications in Mathematical Physics, 165(1):33-47, 1994. URL: https://doi.org/cmp/1104271032.
  46. Fabio Martinelli. Lectures on Glauber dynamics for discrete spin models. Lectures on probability theory and statistics (Saint-Flour, 1997), 1717:93-191, 1999. Google Scholar
  47. Katalin Marton. Logarithmic sobolev inequalities in discrete product spaces. Combinatorics, Probability and Computing, 28(6):919-935, 2019. URL: https://doi.org/10.1017/S0963548319000099.
  48. Ravi Montenegro and Prasad Tetali. Mathematical aspects of mixing times in markov chains. Foundations and Trends® in Theoretical Computer Science, 1(3):237-354, 2006. URL: https://doi.org/10.1561/0400000003.
  49. Yuval Peres and Peter Winkler. Can extra updates delay mixing? Communications in Mathematical Physics, 323(3):1007-1016, 2013. Google Scholar
  50. Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, Eric Vigoda, and Linji Yang. Improved mixing condition on the grid for counting and sampling independent sets. Probab. Theory Relat. Fields, 2013. URL: https://doi.org/10.1007/s00440-012-0421-8.
  51. BARRY SIMON. The Statistical Mechanics of Lattice Gases, Volume I. Princeton University Press, 1993. URL: http://www.jstor.org/stable/j.ctt7ztwsn.
  52. Alistair Sinclair, Piyush Srivastava, Daniel Stefankovic, and Yitong Yin. Spatial mixing and the connective constant: Optimal bounds. Probab. Theory Relat. Fields, 168:153-197, 2017. URL: https://doi.org/10.1007/s00440-016-0708-2.
  53. Robert H. Swendsen and Jian-Sheng Wang. Nonuniversal critical dynamics in Monte Carlo simulations. Phys. Rev. Lett., 58:86-88, 1987. URL: https://doi.org/10.1103/PhysRevLett.58.86.
  54. Mario Ullrich. Rapid mixing of swendsenendashwang dynamics in two dimensions. Dissertationes Mathematicae, 502:1-64, 2014. URL: https://doi.org/10.4064/dm502-0-1.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact