8

Parallel Discrete Sampling via Continuous Walks

 1 month ago
source link: https://dl.acm.org/doi/abs/10.1145/3564246.3585207
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

ABSTRACT

We develop a framework for sampling from discrete distributions µ on the hypercube {± 1}n by sampling from continuous distributions supported on ℝn obtained by convolution with spherical Gaussians. We show that for well-studied families of discrete distributions µ, the result of the convolution is well-conditioned log-concave, whenever the Gaussian’s variance is above an O(1) threshold. We plug off-the-shelf continuous sampling methods into our framework to obtain novel discrete sampling algorithms. Additionally, we introduce and study a crucial notion of smoothness for discrete distributions that we call transport stability, which we use to control the propagation of error in our framework. We expect transport stability to be of independent interest, as we connect it to constructions of optimally mixing local random walks and concentration inequalities. As our main application, we resolve open questions raised by Anari, Hu, Saberi, and Schild on the parallel sampling of distributions which admit parallel counting. We show that determinantal point processes can be sampled via RNC algorithms, that is in time log(n)O(1) using nO(1) processors. For a wider class of distributions, we show our framework yields Quasi-RNC sampling, i.e., log(n)O(1) time using nO(logn) processors. This wider class includes non-symmetric determinantal point processes and random Eulerian tours in digraphs, the latter nearly resolving another open question raised by prior work.

References

  1. David J. Aldous. 1990. The random walk construction of uniform spanning trees and uniform labelled treeSsI. AM J. Discrete Math., 3, 4, 450-465. https://d oi. org/10.1137/0403039.
  2. Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, and Thuy-Duong Vuong. © 2021. Fractionally log-concave and sector-stable polynomials: counting planar matchings and more. ISnTOC '21-Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. ACM, New York, 433-446. https://doi.org/10.1145/3406325.3451123.
  3. Nima Anari, Callum Burgess, Kevin Tian, and Thuy-Duong Vuong. 2022. Quadratic speedups in parallel sampling from determinantal distributions. ( 2022 ). arXiv:2203.11190 [cs.DS].
  4. Nima Anari, Nathan Hu, Amin Saberi, and Aaron Schild. 2021. Sampling arborescences in parallel. I1n2th Innovations in Theoretical Computer Science Conference. LIPIcs. Leibniz Int. Proc. Inform. Vol. 185. Schloss Dagstuhl. LeibnizZent. Inform., Wadern, Art. No. 83, 18h.ttps://doi.org/10.4230/LIPIcs.ITCS. 202 1.83.
  5. Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong. © 2022. Entropic independence: optimal mixing of down-up random walks. InSTOC '22-Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. ACM, New York, 1418-1430.https://doi.o rg/10.1145/3519935.3520048.
  6. B. Awerbuch, A. Israeli, and Y. Shiloach. 1984. Finding euler circuits in logarithmic parallel time. InProceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC '84). Association for Computing Machinery, New York, NY, USA, 249-257.isbn: 0897911334. https://doi.org/10.1145/800057.808688.
  7. Julius Borcea, Peter Brändén, and Thomas M. Ligget. 2009. Negative dependence and the geometry of polynomialJs. Amer. Math. Soc., 22, 2, 521-567. https://doi.org/10.1090/S0894-0347-08-00618-8.
  8. André Bouchet. 1995. Coverings and delta-coverings. IInnteger programming and combinatorial optimization (Copenhagen, 1995 ). Lecture Notes in Comput. Sci. Vol. 920. Springer, Berlin, 228-243 https://doi.org/10.1007/3-540-59408-6_54.
  9. Peter Brändén. 2007. Polynomials with the half-plane property and matroid theory. Adv. Math., 216, 1, 302-320. https://doi.org/10.1016/j.aim. 2007. 05.011.
  10. Graham R. Brightwell and Peter Winkler. 2005. Counting eulerian circuits is #p-complete. In Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, ALENEX /ANALCO 2005, Vancouver, BC, Canada, 22 January 2005. Camil Demetrescu, Robert Sedgewick, and Roberto Tamassia, (Eds.) SIAM, 259-262.
  11. A. Broder. 1989. Generating random spanning trees. PIrnoceedings of the 30th Annual Symposium on Foundations of Computer Science (SFCS '89). IEEE Computer Society, USA, 442-447.isbn: 0818619821. https://doi.org/10.1109 /SFCS. 1989. 63516.
  12. Elisa Celis, Vijay Keswani, Damian Straszak, Amit Deshpande, Tarun Kathuria, and Nisheeth Vishnoi. 2018. Fair and diverse DPP-based data summarization. In Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research). Jennifer Dy and Andreas Krause, (Eds.) Vol. 80. PMLR, (Oct. 2018 ), 716-725.
  13. S. Chaiken and D. J. Kleitman. 1978. Matrix tree theoremJs.. Combinatorial hTeory Ser. A, 24, 3, 377-381. https://doi.org/10.1016/ 0097-3165 ( 78 ) 90067-5.
  14. Yuansi Chen and Ronen Eldan. © 2022. Localization schemes: a framework for proving mixing bounds for Markov chains2. 0I2n2 IEEE 63rd Annual Symposium on Foundations of Computer Science-FOCS 2022. IEEE Computer Soc., Los Alamitos, CA, 110-122.https://doi.org/10.1109/FOCS54457. 2022. 0001 8.
  15. L. Csanky. 1976. Fast parallel matrix inversion algorithSmIsA. M J. Comput., 5, 4, 618-623. https://doi.org/10.1137/0205040.
  16. Michael W. Dereziński Michałand Mahoney. 2021. Determinantal point processes in randomized numerical linear algebrNao. tices Amer. Math. Soc., 68, 1, 34-45. https://doi.org/10.1090/noti220.2 Martin Dyer, Alan Frieze, and Ravi Kannan. 1991. A random polynomial-time algorithm for approximating the volume of convex bodiJe. sA. ssoc. Comput. Mach., 38, 1, 1-17. https://doi.org/10.1145/102782.102783.
  17. Martin Dyer, Alan Frieze, and Ravi Kannan. 1991. A random polynomial-time algorithm for approximating the volume of convex bodies. J. Assoc. Comput. Mach., 38, 1, 1–17. https://doi.org/10.1145/102782.102783.
  18. Martin Dyer, Leslie Ann Goldberg, and Mark Jerrum. 2004. Counting and sampling H-colourings. Inform. and Comput., 189, 1, 1–16. https://doi.org/10.1016/j.ic.2003.09.001.
  19. Ahmed El Alaoui and Andrea Montanari. 2022. An information-theoretic view of stochastic localizatio nIE. EE Trans. Inform. Theory, 68, 11, 7423-7426. https: //doi.org/10.1109/TIT. 2022. 3180298.
  20. Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. ©2022. Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization. In2022 IEEE 63rd Annual Symposium on Foundations of Computer Science-FOCS 2022. IEEE Computer Soc., Los Alamitos, CA, 323-334.https://d oi. org/10.1109/FOCS54457. 2022. 00038.
  21. Ronen Eldan. 2013. Thin shell implies spectral gap up to polylog via a stochastic localization schemeG.eom. Funct. Anal., 23, 2, 532-569. https://doi.org/10.1007 /s00039-013-0214-y.
  22. Ronen Eldan, James R. Lee, and Joseph Lehec. 2017. Transport-entropy inequalities and curvature in discrete-space Markov chainsA. Ijnourney through discrete mathematics. Springer, Cham, 391-406.https://doi.org/10.1007/978-3-3 19-44479-6_16.
  23. Ronen Eldan and Omer Shamir. 2022. Log concavity and concentration of Lipschitz functions on the Boolean hypercubJ. eF.unct. Anal., 282, 8, Paper No. 109392, 22. https://doi.org/10.1016/j.jfa.2022.109392
  24. Weiming Feng, Thomas P. Hayes, and Yitong Yin. 2021. Distributed metrop- olis sampler with optimal parallelism. InProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). [Society for Industrial and Applied Mathematics (SIAM)], Philadelphia, PA, 2121-2140 https://doi.org/10.1137/1.9781611976465.127.
  25. Mike Gartrell, Victor-Emmanuel Brunel, Elvis Dohmatob, and Syrine Krichene. 2019. Learning nonsymmetric determinantal point processes. AIdnvances in Neural Information Processing Systems. H. Wallach, H. Larochelle, A. Beygelz- imer, F. d' Alché-Buc, E. Fox, and R. Garnet, (Eds.) Vol. 32. Curran Associates, Inc.
  26. Qi Ge and Daniel Štefankovič. 2012. The complexity of counting Eulerian tours in 4-regular graphsA.lgorithmica, 63, 3, 588-601. https://doi.org/10.1007/s0045 3-010-9463-4.
  27. Jonathan Hermon and Justin Salez. 2023. Modified log-Sobolev inequalities for strong-Rayleigh measuresA. nn. Appl. Probab., 33, 2, 1301-1314. https://doi.org /10.1214/ 22-aap1847.
  28. Mark Jerrum, Alistair Sinclair, and Eric Vigoda. 2004. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM, 51, 4, 671-697. https://doi.org/10.1145/1008731.1008738.
  29. Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. 1986. Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci., 43, 2-3, 169-188. https://doi.org/10.1016/ 0304-3975 ( 86 ) 90174-X.
  30. P. W. Kasteleyn. 1963. Dimer statistics and phase transitioJn. sM.athematical Phys., 4, 287-293. https://doi.org/10.1063/1.1703953.
  31. Alex Kulesza and Ben Taskar. 2012. Determinantal point processes for machine learning. Foundations and Trends® in Machine Learning, 5, 2-3, 123-286. https: //doi.org/10.1561/2200000044.
  32. Hongyang Liu and Yitong Yin. ©2022. Simple parallel algorithms for single-site dynamics. InSTOC '22-Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. ACM, New York, 1431-1444.https://doi.o rg/10.1145/3519935.3519999.
  33. Robin Pemantle and Yuval Peres. 2014. Concentration of Lipschitz functionals of determinantal and other strong Rayleigh measuCreosm. bin. Probab. Comput., 23, 1, 140-160. https://doi.org/10.1017/S0963548313000345.
  34. Ruoqi Shen and Yin Tat Lee. 2019. The randomized midpoint method for logconcave sampling. InAdvances in Neural Information Processing Systems. H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnet, (Eds.) Vol. 32. Curran Associates, Inc.
  35. H. N. V. Temperley and Michael E. Fisher. 1961. Dimer problem in statistical mechanics-an exact resultP. hilos. Mag. (8), 6, 1061-1063. https://doi.org/10.10 80/14786436108243366.
  36. Shang-Hua Teng. 1995. Independent sets versus perfect matchings. Theoret. Comput. Sci., 145, 1-2, 381-390. https://doi.org/10.1016/ 0304-3975 ( 94 ) 00289-U.
  37. W. T. Tute and C. A. B. Smith. 1941. On Unicursal Paths in a Network of Degree 4. Amer. Math. Monthly, 48, 4, 233-237. https://doi.org/10.2307/2302716.
  38. T. van Aardenne-Ehrenfest and N. G. de Bruijn. 1951. Circuits and trees in oriented linear graphSsi. mon Stevin, 28, 203-217.

Recommendations

Comments

0 Comments

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Sign in

  • Published in

    cover image ACM Conferences
    STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
    June 2023
    1926 pages
    ISBN:9781450399135
    DOI:10.1145/3564246
    • General Chair:
    • Program Chair:

    Copyright © 2023 ACM

    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    • Published: 2 June 2023

    Permissions

    Request permissions about this article.

    Request Permissions

    Check for updates

    Qualifiers

    • research-article

    Acceptance Rates

    Overall Acceptance Rate1,469of4,586submissions,32%

    Upcoming Conference

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Share this Publication link

https://dl.acm.org/doi/abs/10.1145/3564246.3585207

Share on Social Media

Share on

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK