Learning Determinantal Point Processes with Moments and Cycles
John Urschel, Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet
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.
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.}
}