Document Open Access Logo

From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk

Author Kuikui Liu

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.32.pdf
  • Filesize: 0.79 MB
  • 21 pages

Document Identifiers

Author Details

Kuikui Liu
  • University of Washington, Seattle, WA, USA

Funding

  • Liu, Kuikui: The author is supported by NSF grants CCF-1552097, CCF-1907845.

Acknowledgements

The author would like to thank their advisor Shayan Oveis Gharan for comments on a preliminary draft of this paper. We also thank Nima Anari and Pierre Youssef for informing us that a conjecture posed in a preliminary draft of the paper was already known to be false. We finally thank the anonymous reviewers for delivering valuable feedback on this paper.

Cite As Get BibTex

Kuikui Liu. From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 32:1-32:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.32

Abstract

We show that the existence of a "good" coupling w.r.t. Hamming distance for any local Markov chain on a discrete product space implies rapid mixing of the Glauber dynamics in a blackbox fashion. More specifically, we only require the expected distance between successive iterates under the coupling to be summable, as opposed to being one-step contractive in the worst case. Combined with recent local-to-global arguments [Chen et al., 2021], we establish asymptotically optimal lower bounds on the standard and modified log-Sobolev constants for the Glauber dynamics for sampling from spin systems on bounded-degree graphs when a curvature condition [Ollivier, 2009] is satisfied. To achieve this, we use Stein’s method for Markov chains [Bresler and Nagaraj, 2019; Reinert and Ross, 2019] to show that a "good" coupling for a local Markov chain yields strong bounds on the spectral independence of the distribution in the sense of [Anari et al., 2020].
Our primary application is to sampling proper list-colorings on bounded-degree graphs. In particular, combining the coupling for the flip dynamics given by [Vigoda, 2000; Chen et al., 2019] with our techniques, we show optimal O(nlog n) mixing for the Glauber dynamics for sampling proper list-colorings on any bounded-degree graph with maximum degree Δ whenever the size of the color lists are at least ({11/6 - ε}) Δ, where ε ≈ 10^{-5} is small constant. While O(n²) mixing was already known before, our approach additionally yields Chernoff-type concentration bounds for Hamming Lipschitz functions in this regime, which was not known before. Our approach is markedly different from prior works establishing spectral independence for spin systems using spatial mixing [Anari et al., 2020; Z. {Chen} et al., 2020; Chen et al., 2021; Feng et al., 2021], which crucially is still open in this regime for proper list-colorings.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
Keywords
  • Markov chains
  • Approximate counting
  • Spectral independence

Metrics

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

References

  1. Vedat Levi Alev and Lap Chi Lau. Improved analysis of higher order random walks and applications. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 1198–1211, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3357713.3384317.
  2. Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, and Thuy-Duong Vuong. Fractionally log-concave and sector-stable polynomials: Counting planar matchings and more. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 433–446, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3406325.3451123.
  3. Nima Anari and Michal Derezinski. Isotropy and log-concave polynomials: Accelerated sampling and high-precision counting of matroid bases. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1331-1344, Los Alamitos, CA, USA, November 2020. IEEE Computer Society. Google Scholar
  4. Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant. Log-concave polynomials ii: High-dimensional walks and an fpras for counting bases of a matroid. In Proceedings of the 51st Annual ACM SIGACT Symposium on the Theory Computing, STOC 2019, pages 1-12, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3313276.3316385.
  5. Nima Anari, Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant, and Thuy-Duong Vuong. Log-concave polynomials iv: Approximate exchange, tight mixing times, and near-optimal sampling of forests. In Proceedings of the 53rd Annual ACM SIGACT Symposium on the Theory Computing, STOC 2021, New York, NY, USA, 2021. Association for Computing Machinery. Google Scholar
  6. 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.
  7. Antonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi, Daniel Štefankovič, and Eric Vigoda. On mixing of markov chains: Coupling, spectral independence, and entropy factorization. arXiv preprint arXiv:2103.07459, 2021. Google Scholar
  8. 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, page 287–296, New York, NY, USA, 2003. Association for Computing Machinery. Google Scholar
  9. Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 1 edition, 2016. Google Scholar
  10. Guy Bresler and Dheeraj Nagaraj. Stein’s method for stationary distributions of markov chains and application to ising models. Annals of Applied Probability, 29(5), 2019. Google Scholar
  11. R. Bubley and M. Dyer. Path coupling: A technique for proving rapid mixing in markov chains. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science, FOCS '97, pages 223-, Washington, DC, USA, 1997. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=795663.796353.
  12. R. Bubley and M. E. Dyer. Path coupling, dobrushin uniqueness, and approximate counting. Technical report, University of Leeds, 1997. Google Scholar
  13. Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, and Luke Postle. Improved bounds for randomly sampling colorings via linear programming. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, page 2216–2234, USA, 2019. Society for Industrial and Applied Mathematics. Google Scholar
  14. Z. Chen, K. Liu, and E. 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, 2020. Google Scholar
  15. Zongchen Chen, Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Rapid Mixing for Colorings via Spectral Independence, page 1548–1557. Society for Industrial and Applied Mathematics, USA, 2021. Google Scholar
  16. 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, page 1537–1550, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3406325.3451035.
  17. Zongchen Chen, Kuikui Liu, and Eric Vigoda. Spectral independence via stability and applications to holant-type problems. arXiv preprint arXiv:2106.03366, 2021. Google Scholar
  18. M. Cryan, H. Guo, and G. Mousa. Modified log-sobolev inequalities for strongly log-concave distributions. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1358-1370, 2019. Google Scholar
  19. Persi Diaconis and Laurent Saloff-Coste. Comparison theorems for reversible markov chains. Annals of Applied Probability, 3(3):696-730, 1993. Google Scholar
  20. Persi Diaconis and Laurent Saloff-Coste. Logarithmic sobolev inequalities for finite markov chains. Annals of Applied Probability, 6(3), August 1996. Google Scholar
  21. I. Dinur and T. Kaufman. High dimensional expanders imply agreement expanders. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 974-985, 2017. Google Scholar
  22. R. L. Dobrushin and S. B. Shlosman. Completely Analytical Gibbs Fields, pages 371-403. Birkhäuser Boston, Boston, MA, 1985. Google Scholar
  23. R. L. Dobrushin and S. B. Shlosman. Constructive Criterion for the Uniqueness of Gibbs Field, pages 347-370. Birkhäuser Boston, Boston, MA, 1985. Google Scholar
  24. R. L. Dobrushin and S. B. Shlosman. Completely analytical interactions: Constructive description. Journal of Statistical Physics, 46(5):983-1014, 1987. Google Scholar
  25. Roland Lvovich Dobrushin. Prescribing a system of random variables by conditional distributions. Theory of Probability and its Applications, 15(3):458-486, 1970. Google Scholar
  26. 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
  27. Charilaos Efthymiou, Andreas Galanis, Thomas P. Hayes, Daniel Stefankovic, and Eric Vigoda. Improved Strong Spatial Mixing for Colorings on Trees. In Dimitris Achlioptas and László A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 48:1-48:16, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.48.
  28. Ronen Eldan, James R. Lee, and Joseph Lehec. Transport-entropy inequalities and curvature in discrete-space markov chains. A Journey Through Discrete Mathematics, pages 391-406, 2017. Google Scholar
  29. Tomás Feder and Milena Mihail. Balanced matroids. In STOC, pages 26-38, 1992. Google Scholar
  30. Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang. Rapid Mixing from Spectral Independence beyond the Boolean Domain, page 1558–1577. Society for Industrial and Applied Mathematics, USA, 2021. Google Scholar
  31. Alan Frieze and Eric Vigoda. A survey on the use of markov chains to randomly sample colourings. Combinatorica, January 2007. URL: https://doi.org/10.1093/acprof:oso/9780198571278.003.0004.
  32. David Gamarnik, Dmitriy Katz, and Sidhant Misra. Strong spatial mixing of list coloring of graphs. Random Struct. Algorithms, 46(4):599–613, 2015. URL: https://doi.org/10.1002/rsa.20518.
  33. Sharad Goel. Modified logarithmic sobolev inequalities for some models of random walk. Stochastic Processes and their Applications, 114:51-79, 2004. Google Scholar
  34. Heng Guo and Giorgos Mousa. Local-to-global contraction in simplicial complexes. arXiv preprint arXiv:2012.14317, 2020. Google Scholar
  35. Thomas P. Hayes. A simple condition implying rapid mixing of single-site dynamics on spin systems. FOCS, pages 39-46, 2006. Google Scholar
  36. Thomas P. Hayes and Alistair Sinclair. A general lower bound for mixing of single-site dynamics on graphs. Annals of Applied Probability, 17(3):931-952, 2007. Google Scholar
  37. Thomas P. Hayes and Eric Vigoda. Variable length path coupling. Random Structures and Algorithms, 31:251-272, 2007. Google Scholar
  38. Mark Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Struct. Algorithms, 7(2):157–165, 1995. Google Scholar
  39. Tali Kaufman and David Mass. High dimensional random walks and colorful expansion. In ITCS, pages 4:1-4:27, 2017. Google Scholar
  40. Tali Kaufman and Izhar Oppenheim. High order random walks: Beyond spectral gap. In APPROX/RANDOM, pages 47:1-47:17, 2018. Google Scholar
  41. David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2 edition, 2017. Google Scholar
  42. 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.
  43. M. Mihail and U. Vazirani. On the expansion of 0/1 polytopes. Journal of Combinatorial Theory, 1989. Google Scholar
  44. Yann Ollivier. Ricci curvature of markov chains on metric spaces. Journal of Functional Analysis, 256:810-864, February 2009. Google Scholar
  45. Izhar Oppenheim. Local spectral expansion approach to high dimensional expanders part i: Descent of spectral gaps. Discrete and Computational Geometry, 59(2):293-330, 2018. Google Scholar
  46. Gesine Reinert and Nathan Ross. Approximating stationary distributions of fast mixing glauber dynamics, with applications to exponential random graphs. Annals of Applied Probability, 29, 2019. Google Scholar
  47. Marcus D. Sammer. Aspects of Mass Transportation in Discrete Concentration Inequalities. PhD thesis, Georgia Institute of Technology, April 2005. Google Scholar
  48. Charles Stein. A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, pages 583-602, 1972. Google Scholar
  49. Eric Vigoda. Improved bounds for sampling colorings. Journal of Mathematical Physics, 41, 2000. Google Scholar
  50. Jian-Sheng Wang, Robert H. Swendsen, and Roman Kotecký. Antiferromagnetic potts models. Phys. Rev. Lett., 63:109-112, July 1989. URL: https://doi.org/10.1103/PhysRevLett.63.109.
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