Learning Determinantal Point Processes with Moments and Cycles

John Urschel, Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:3511-3520, 2017.

Abstract

Determinantal Point Processes (DPPs) are a family of probabilistic models that have a repulsive behavior, and lend themselves naturally to many tasks in machine learning where returning a diverse set of objects is important. While there are fast algorithms for sampling, marginalization and conditioning, much less is known about learning the parameters of a DPP. Our contribution is twofold: (i) we establish the optimal sample complexity achievable in this problem and show that it is governed by a natural parameter, which we call the cycle sparsity; (ii) we propose a provably fast combinatorial algorithm that implements the method of moments efficiently and achieves optimal sample complexity. Finally, we give experimental results that confirm our theoretical findings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-urschel17a, title = {Learning Determinantal Point Processes with Moments and Cycles}, author = {John Urschel and Victor-Emmanuel Brunel and Ankur Moitra and Philippe Rigollet}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {3511--3520}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/urschel17a/urschel17a.pdf}, url = {https://proceedings.mlr.press/v70/urschel17a.html}, abstract = {Determinantal Point Processes (DPPs) are a family of probabilistic models that have a repulsive behavior, and lend themselves naturally to many tasks in machine learning where returning a diverse set of objects is important. While there are fast algorithms for sampling, marginalization and conditioning, much less is known about learning the parameters of a DPP. Our contribution is twofold: (i) we establish the optimal sample complexity achievable in this problem and show that it is governed by a natural parameter, which we call the cycle sparsity; (ii) we propose a provably fast combinatorial algorithm that implements the method of moments efficiently and achieves optimal sample complexity. Finally, we give experimental results that confirm our theoretical findings.} }
Endnote
%0 Conference Paper %T Learning Determinantal Point Processes with Moments and Cycles %A John Urschel %A Victor-Emmanuel Brunel %A Ankur Moitra %A Philippe Rigollet %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-urschel17a %I PMLR %P 3511--3520 %U https://proceedings.mlr.press/v70/urschel17a.html %V 70 %X Determinantal Point Processes (DPPs) are a family of probabilistic models that have a repulsive behavior, and lend themselves naturally to many tasks in machine learning where returning a diverse set of objects is important. While there are fast algorithms for sampling, marginalization and conditioning, much less is known about learning the parameters of a DPP. Our contribution is twofold: (i) we establish the optimal sample complexity achievable in this problem and show that it is governed by a natural parameter, which we call the cycle sparsity; (ii) we propose a provably fast combinatorial algorithm that implements the method of moments efficiently and achieves optimal sample complexity. Finally, we give experimental results that confirm our theoretical findings.
APA
Urschel, J., Brunel, V., Moitra, A. & Rigollet, P.. (2017). Learning Determinantal Point Processes with Moments and Cycles. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:3511-3520 Available from https://proceedings.mlr.press/v70/urschel17a.html.

Related Material