Document Open Access Logo

Domain Sparsification of Discrete Distributions Using Entropic Independence

Authors Nima Anari, Michał Dereziński, Thuy-Duong Vuong, Elizabeth Yang

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.5.pdf
  • Filesize: 0.74 MB
  • 23 pages

Document Identifiers

Author Details

Nima Anari
  • Stanford University, CA, USA
Michał Dereziński
  • University of Michigan, Ann Arbor, MI, USA
Thuy-Duong Vuong
  • Stanford University, CA, USA
Elizabeth Yang
  • UC Berkeley, CA, USA

Funding

Nima Anari and Thuy-Duong Vuong are supported by NSF CAREER award CCF-2045354, a Sloan Research Fellowship, and a Google Faculty Research Award. Elizabeth Yang is supported by the NSF Graduate Research Fellowship under Grant No. DGE 1752814.

Cite AsGet BibTex

Nima Anari, Michał Dereziński, Thuy-Duong Vuong, and Elizabeth Yang. Domain Sparsification of Discrete Distributions Using Entropic Independence. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.5

Abstract

We present a framework for speeding up the time it takes to sample from discrete distributions μ defined over subsets of size k of a ground set of n elements, in the regime where k is much smaller than n. We show that if one has access to estimates of marginals P_{S∼ μ} {i ∈ S}, then the task of sampling from μ can be reduced to sampling from related distributions ν supported on size k subsets of a ground set of only n^{1-α}⋅ poly(k) elements. Here, 1/α ∈ [1, k] is the parameter of entropic independence for μ. Further, our algorithm only requires sparsified distributions ν that are obtained by applying a sparse (mostly 0) external field to μ, an operation that for many distributions μ of interest, retains algorithmic tractability of sampling from ν. This phenomenon, which we dub domain sparsification, allows us to pay a one-time cost of estimating the marginals of μ, and in return reduce the amortized cost needed to produce many samples from the distribution μ, as is often needed in upstream tasks such as counting and inference. For a wide range of distributions where α = Ω(1), our result reduces the domain size, and as a corollary, the cost-per-sample, by a poly(n) factor. Examples include monomers in a monomer-dimer system, non-symmetric determinantal point processes, and partition-constrained Strongly Rayleigh measures. Our work significantly extends the reach of prior work of Anari and Dereziński who obtained domain sparsification for distributions with a log-concave generating polynomial (corresponding to α = 1). As a corollary of our new analysis techniques, we also obtain a less stringent requirement on the accuracy of marginal estimates even for the case of log-concave polynomials; roughly speaking, we show that constant-factor approximation is enough for domain sparsification, improving over O(1/k) relative error established in prior work.

Subject Classification

ACM Subject Classification
  • Theory of computation → Random walks and Markov chains
  • Theory of computation → Sketching and sampling
Keywords
  • Domain Sparsification
  • Markov Chains
  • Sampling
  • Entropic Independence

Metrics

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

Related Versions

References

  1. Dorna Abdolazimi, Kuikui Liu, and Shayan Oveis Gharan. A matrix trickle-down theorem on simplicial complexes and applications to sampling colorings. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.03845.
  2. 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, pages 1198-1211, 2020. Google Scholar
  3. Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, and Thuy-Duong Vuong. Fractionally log-concave and sector-stable polynomials: Counting planar matchings and more. arXiv preprint, 2021. URL: http://arxiv.org/abs/2102.02708.
  4. Nima Anari and Michał Dereziński. Isotropy and log-concave polynomials: Accelerated sampling and high-precision counting of matroid bases. In Proceedings of the 61st Annual Symposium on Foundations of Computer Science, 2020. Google Scholar
  5. Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong. Entropic independence i: Modified log-sobolev inequalities for fractionally log-concave distributions and high-temperature ising models. arXiv (to appear), 2021. Google Scholar
  6. Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. Spectral independence in high-dimensional expanders and applications to the hardcore model. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society, November 2020. Google Scholar
  7. 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 Theory of Computing. ACM, June 2019. Google Scholar
  8. 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. arXiv preprint, 2020. URL: http://arxiv.org/abs/2004.07220.
  9. Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant. Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 35-46. IEEE, 2018. Google Scholar
  10. Nima Anari and Thuy-Duong Vuong. Simple and near-optimal MAP inference for nonsymmetric dpps. CoRR, abs/2102.05347, 2021. URL: http://arxiv.org/abs/2102.05347.
  11. Bardenet, Rémi, Lavancier, Frédéric, Mary, Xavier, and Vasseur, Aurélien. On a few statistical applications of determinantal point processes. ESAIM: Procs, 60:180-202, 2017. URL: https://doi.org/10.1051/proc/201760180.
  12. 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, 2021. URL: http://arxiv.org/abs/2103.07459.
  13. Sergey G Bobkov and Prasad Tetali. Modified logarithmic sobolev inequalities in discrete settings. Journal of Theoretical Probability, 19(2):289-336, 2006. Google Scholar
  14. Julius Borcea, Petter Brändén, and Thomas Liggett. Negative dependence and the geometry of polynomials. Journal of the American Mathematical Society, 22(2):521-567, 2009. Google Scholar
  15. Petter Brändén and June Huh. Lorentzian polynomials. arXiv preprint, 2019. URL: http://arxiv.org/abs/1902.03719.
  16. Daniele Calandriello, Michał Dereziński, and Michal Valko. Sampling from a k-dpp without looking at all items. In Advances in Neural Information Processing Systems, volume 33, 2020. Google Scholar
  17. L Elisa Celis, Amit Deshpande, Tarun Kathuria, Damian Straszak, and Nisheeth K Vishnoi. On the complexity of constrained determinantal point processes. arXiv preprint, 2016. URL: http://arxiv.org/abs/1608.00554.
  18. Xiaoyu Chen, Weiming Feng, Yitong Yin, and Xinyuan Zhang. Rapid mixing of glauber dynamics via spectral independence for all degrees. arXiv preprint, 2021. URL: http://arxiv.org/abs/2105.15005.
  19. Zongchen Chen, Andreas Galanis, Daniel Štefankovič, 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. SIAM, 2021. Google Scholar
  20. Zongchen Chen, Kuikui Liu, and Eric Vigoda. Rapid mixing of glauber dynamics up to uniqueness via contraction. arXiv preprint, 2020. URL: http://arxiv.org/abs/2004.09083.
  21. Mary Cryan, Heng Guo, and Giorgos 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. IEEE, 2019. Google Scholar
  22. Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós. A sparse johnson: Lindenstrauss transform. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 341-350, 2010. Google Scholar
  23. Michał Dereziński. Fast determinantal point processes via distortion-free intermediate sampling. In Proceedings of the 32nd Conference on Learning Theory, 2019. Google Scholar
  24. Michał Dereziński, Burak Bartan, Mert Pilanci, and Michael W Mahoney. Debiasing distributed second order optimization with surrogate sketching and scaled regularization. In Advances in Neural Information Processing Systems, volume 33, 2020. Google Scholar
  25. Michał Dereziński, Daniele Calandriello, and Michal Valko. Exact sampling of determinantal point processes with sublinear time preprocessing. In Advances in Neural Information Processing Systems 32, pages 11542-11554, 2019. Google Scholar
  26. Michał Dereziński, Kenneth L. Clarkson, Michael W. Mahoney, and Manfred K. Warmuth. Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1050-1069, Phoenix, USA, 2019. Google Scholar
  27. Michał Dereziński, Rajiv Khanna, and Michael W Mahoney. Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nyström method. In Advances in Neural Information Processing Systems, volume 33, pages 4953-4964, 2020. Google Scholar
  28. Michał Dereziński and Michael W Mahoney. Determinantal point processes in randomized numerical linear algebra. Notices of the American Mathematical Society, 68(1):34-45, 2021. Google Scholar
  29. Michał Dereziński and Manfred K. Warmuth. Unbiased estimates for linear regression via volume sampling. In Advances in Neural Information Processing Systems 30, pages 3087-3096, Long Beach, CA, USA, 2017. Google Scholar
  30. Michał Dereziński, Manfred K. Warmuth, and Daniel Hsu. Leveraged volume sampling for linear regression. In Advances in Neural Information Processing Systems 31, pages 2510-2519, 2018. Google Scholar
  31. Michał Dereziński, Manfred K Warmuth, and Daniel Hsu. Unbiased estimators for random design regression. arXiv preprint, 2019. URL: http://arxiv.org/abs/1907.03411.
  32. Amit Deshpande and Luis Rademacher. Efficient volume sampling for row/column subset selection. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 329-338, Las Vegas, USA, October 2010. Google Scholar
  33. Amit Deshpande, Luis Rademacher, Santosh Vempala, and Grant Wang. Matrix approximation and projective clustering via volume sampling. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, pages 1117-1126, Miami, FL, USA, January 2006. Google Scholar
  34. David Eppstein and Vijay V Vazirani. Nc algorithms for computing a perfect matching, the number of perfect matchings, and a maximum flow in one-crossing-minor-free graphs. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures, pages 23-30, 2019. Google Scholar
  35. Weiming Feng, Heng Guo, Yitong Yin, and Chihao Zhang. Rapid mixing from spectral independence beyond the boolean domain. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1558-1577. SIAM, 2021. Google Scholar
  36. Anna Galluccio and Martin Loebl. On the theory of pfaffian orientations. i. perfect matchings and permanents. the electronic journal of combinatorics, pages R6-R6, 1999. Google Scholar
  37. Mike Gartrell, Victor-Emmanuel Brunel, Elvis Dohmatob, and Syrine Krichene. Learning nonsymmetric determinantal point processes. arXiv preprint, 2019. URL: http://arxiv.org/abs/1905.12962.
  38. Mike Gartrell, Insu Han, Elvis Dohmatob, Jennifer Gillenwater, and Victor-Emmanuel Brunel. Scalable learning and MAP inference for nonsymmetric determinantal point processes. CoRR, abs/2006.09862, 2020. URL: http://arxiv.org/abs/2006.09862.
  39. Heng Guo and Giorgos Mousa. Local-to-global contraction in simplicial complexes. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.14317.
  40. Venkatesan Guruswami and Ali K. Sinop. Optimal column-based low-rank matrix reconstruction. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1207-1214, Kyoto, Japan, January 2012. Google Scholar
  41. Leonid Gurvits. On multivariate newton-like inequalities. In Advances in combinatorial mathematics, pages 61-78. Springer, 2009. Google Scholar
  42. A Guénoche. Random spanning tree. Journal of Algorithms, 4(3):214-220, 1983. URL: https://doi.org/10.1016/0196-6774(83)90022-6.
  43. J. Ben Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág. Determinantal processes and independence. Probability surveys, 3:206-229, 2006. Google Scholar
  44. Vishesh Jain, Huy Tuan Pham, and Thuy Duong Vuong. Spectral independence, coupling with the stationary distribution, and the spectral gap of the glauber dynamics. arXiv preprint, 2021. URL: http://arxiv.org/abs/2105.01201.
  45. Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM (JACM), 51(4):671-697, 2004. Google Scholar
  46. 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
  47. Pieter Kasteleyn. Graph theory and crystal physics. Graph theory and theoretical physics, pages 43-110, 1967. Google Scholar
  48. Alex Kulesza and Ben Taskar. k-DPPs: Fixed-Size Determinantal Point Processes. In Proceedings of the 28th International Conference on Machine Learning, pages 1193-1200, June 2011. Google Scholar
  49. Alex Kulesza and Ben Taskar. Determinantal Point Processes for Machine Learning. Now Publishers Inc., Hanover, MA, USA, 2012. Google Scholar
  50. David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017. Google Scholar
  51. Kuikui Liu. From coupling to spectral independence and blackbox comparison with the down-up walk. arXiv preprint, 2021. URL: http://arxiv.org/abs/2103.11609.
  52. Odile Macchi. The coincidence approach to stochastic point processes. Advances in Applied Probability, 7(1):83-122, 1975. URL: http://www.jstor.org/stable/1425855.
  53. Mojmir Mutny, Michał Dereziński, and Andreas Krause. Convergence analysis of block coordinate algorithms with determinantal sampling. In International Conference on Artificial Intelligence and Statistics, pages 3110-3120, 2020. Google Scholar
  54. Aleksandar Nikolov, Mohit Singh, and Uthaipon Tao Tantipongpipat. Proportional volume sampling and approximation algorithms for a-optimal design. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1369-1386, 2019. Google Scholar
  55. Daniel A Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM Journal on Computing, 40(4):981-1025, 2011. Google Scholar
  56. Kazuhiro Suzuki, Dongvu Tonien, Kaoru Kurosawa, and Koji Toyota. Birthday paradox for multi-collisions. In Min Surp Rhee and Byoungcheon Lee, editors, Information Security and Cryptology - ICISC 2006, pages 29-40, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact