Document Open Access Logo

On the Complexity of Constrained Determinantal Point Processes

Authors L. Elisa Celis, Amit Deshpande, Tarun Kathuria, Damian Straszak, Nisheeth K. Vishnoi

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.36.pdf
  • Filesize: 0.56 MB
  • 22 pages

Document Identifiers

Author Details

L. Elisa Celis
Amit Deshpande
Tarun Kathuria
Damian Straszak
Nisheeth K. Vishnoi

Cite As Get BibTex

L. Elisa Celis, Amit Deshpande, Tarun Kathuria, Damian Straszak, and Nisheeth K. Vishnoi. On the Complexity of Constrained Determinantal Point Processes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.36

Abstract

Determinantal Point Processes (DPPs) are probabilistic models that arise in quantum physics and random matrix theory and have recently found numerous applications in theoretical computer science and machine learning. DPPs define probability distributions over subsets of a given ground set, they exhibit interesting properties such as negative correlation, and, unlike other models of negative correlation such as Markov random fields, have efficient algorithms for sampling. When applied to kernel methods in machine learning, DPPs favor subsets of the given data with more diverse features. However, many real-world applications require efficient algorithms to sample from DPPs with additional constraints on the sampled subset, e.g., partition or matroid constraints that are important from the viewpoint of ensuring priors, resource or fairness constraints on the sampled subset. Whether one can efficiently sample from DPPs in such constrained settings is an important problem that was first raised in a survey of DPPs for machine learning by Kulesza and Taskar and studied in some recent works.

The main contribution of this paper is the first  resolution of the complexity of sampling from DPPs with constraints. On the one hand, we give exact efficient algorithms for sampling from constrained DPPs when the description of the constraints is  in unary; this includes special cases of practical importance such as a small number of partition, knapsack or budget constraints. On the other hand, we prove that when the constraints are specified in binary, this problem is #P-hard via a reduction from the problem of computing mixed discriminants; implying that it may be unlikely that there is an FPRAS. Technically, our algorithmic result benefits from viewing the constrained sampling  problem via the lens of polynomials and we obtain our complexity results by providing an equivalence between computing mixed discriminants and sampling from partition constrained DPPs. As a consequence, we obtain a few  corollaries of independent interest: 1) An  algorithm to count, sample (and, hence, optimize) over the base polytope of regular matroids when there are additional (succinct) budget constraints and, 
2) An algorithm to evaluate and compute mixed characteristic polynomials, that played a central role in the resolution of the Kadison-Singer problem, for certain special cases.

Subject Classification

Keywords
  • determinantal point processes
  • constraints
  • matroids
  • sampling and counting
  • polynomials
  • mixed discriminant

Metrics

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

References

  1. N. Anari, S. O. Gharan, and A. Rezaei. Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes. In COLT, pages 103-115, 2016. Google Scholar
  2. N. Anari, S. O. Gharan, A. Saberi, and N. Srivastava. Approximating the largest root and applications to interlacing families. CoRR, abs/1704.03892, 2017. URL: http://arxiv.org/abs/1704.03892.
  3. R. B. Bapat. Mixed discriminants of positive semidefinite matrices. Lin. Algebra &Applications, 126, 1989. Google Scholar
  4. A. Barvinok. Computing mixed discriminants, mixed volumes, and permanents. Discrete & Computational Geometry, 18, 1997. Google Scholar
  5. D. Bertsimas and S. Vempala. Solving convex programs by random walks. J. ACM, July 2004. Google Scholar
  6. A. Z. Broder and E. W. Mayr. Counting minimum weight spanning trees. J. of Algorithms, 24(1), 1997. Google Scholar
  7. L. E. Celis, A. Deshpande, T. Kathuria, and N. K. Vishnoi. How to be fair and diverse? Fairness, Accountability, and Transparency in Machine Learning, 2016. Google Scholar
  8. C. Chekuri, J. Vondrak, and R. Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In FOCS, 2010. Google Scholar
  9. A. Deshpande, T. Kathuria, D. Straszak, and N. K. Vishnoi. Combinatorial Determinantal Point Processes. ArXiv e-prints, 2016. URL: http://arxiv.org/abs/1608.00554.
  10. A. Deshpande and L. Rademacher. Efficient Volume Sampling for Row/Column Subset Selection. In FOCS, Oct 2010. Google Scholar
  11. M. E. Dyer, A. M. Frieze, and R. Kannan. A random polynomial time algorithm for approximating the volume of convex bodies. J. ACM, 38(1):1-17, 1991. Google Scholar
  12. D. Eppstein. Representing all minimum spanning trees with applications to counting and generation. UC Irvine, 1995. Google Scholar
  13. S. Friedland and D. Levy. A polynomial-time approximation algorithm for the number of k-matchings in bipartite graphs. ArXiv, 2006. URL: http://arxiv.org/abs/0607135.
  14. M. Gartrell, U. Paquet, and N. Koenigstein. Bayesian low-rank determinantal point processes. In Proceedings of the 10th ACM Conference on Recommender Systems, Boston, MA, USA, September 15-19, 2016, pages 349-356, 2016. Google Scholar
  15. L. Gurvits. On the complexity of mixed discriminants and related problems. In MFCS, 2005. Google Scholar
  16. L. Gurvits and A. Samorodnitsky. A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary. Discrete &Computational Geometry, 27(4), 2002. Google Scholar
  17. B. Hajek. Cooling schedules for optimal annealing. Mathematics of operations research, 13(2), 1988. Google Scholar
  18. N. Harvey. An introduction to the Kadison-Singer problem and the paving conjecture, 2013. Google Scholar
  19. N. Harvey and N. Olver. Pipage rounding, pessimistic estimators and matrix concentration. In SODA'14, pages 926-945, 2014. Google Scholar
  20. J. B. Hough, M. Krishnapur, Y. Peres, and B. Virág. Determinantal Processes and Independence. ArXiv Mathematics e-prints, March 2005. URL: http://arxiv.org/abs/math/0503110.
  21. M. Jerrum, A. Sinclair, and E. Vigoda. A Polynomial-time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries. J. ACM, 51(4), July 2004. Google Scholar
  22. M. R. Jerrum, L. G. Valiant, and V. V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169-188, 1986. Google Scholar
  23. A. Krause, A. Singh, and C. Guestrin. Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies. J. Mach. Learn. Res., 9, June 2008. Google Scholar
  24. A. Kulesza and B. Taskar. Determinantal point processes for machine learning. ArXiv, July 2012. URL: http://arxiv.org/abs/1207.6083.
  25. C. Li, S. Jegelka, and S. Sra. Markov chain sampling in discrete probabilistic models with constraints. In NIPS, 2016. Google Scholar
  26. H. Lin and J. Bilmes. A Class of Submodular Functions for Document Summarization. In Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, HLT'11, 2011. Google Scholar
  27. A. W. Marcus, D. A. Spielman, and N. Srivastava. Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem. Ann. Math. (2), 182(1):327-350, 2015. Google Scholar
  28. M. Mezard and A. Montanari. Information, physics, and computation. Oxford University Press, 2009. Google Scholar
  29. R. Pemantle. Uniform random spanning trees. arXiv preprint math/0404099, 2004. Google Scholar
  30. A. Prasad, S. Jegelka, and D. Batra. Submodular meets structured: Finding diverse subsets in exponentially-large structured item sets. In Advances in Neural Information Processing Systems, December 8-13 2014, Montreal, Quebec, Canada, pages 2645-2653, 2014. Google Scholar
  31. P. Rebeschini and A. Karbasi. Fast mixing for discrete point processes. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, pages 1480-1500, 2015. Google Scholar
  32. Damian Straszak and Nisheeth K. Vishnoi. Real stable polynomials and matroids: Optimization and counting. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing. ACM, 2017. Google Scholar
  33. M. J. Wainwright, M. I. Jordan, et al. Graphical models, exponential families, and variational inference. Foundations and Trendsregistered in Machine Learning, 1(1-2):1-305, 2008. Google Scholar
  34. K. Wei, R. K. Iyer, and J. A. Bilmes. Submodularity in data subset selection and active learning. In Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, pages 1954-1963, 2015. Google Scholar
  35. Y. Yue and T. Joachims. Predicting Diverse Subsets Using Structural SVMs. In ICML, 2008. Google Scholar
  36. C. X. Zhai, W. W. Cohen, and J. Lafferty. Beyond Independent Relevance: Methods and Evaluation Metrics for Subtopic Retrieval. In SIGIR, 2003. Google Scholar
  37. T. Zhou, Z. Kuscsik, J. Liu, M. Medo, J. R. Wakeling, and Y. Zhang. Solving the apparent diversity-accuracy dilemma of recommender systems. PNAS, 107(10), 2010. 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 About DROPS Imprint Privacy Contact