Testing Determinantal Point Processes

NeurIPS

Cite Paper

Authors

Khashayar Gatmiry
Maryam Aliakbarpour
Stefanie Jegelka

Published on

08/09/2020

Categories

NeurIPS

Determinantal point processes (DPPs) are popular probabilistic models of diversity. In this paper, we investigate DPPs from a new perspective: property testing of distributions. Given sample access to an unknown distribution q over the subsets of a ground set, we aim to distinguish whether q is a DPP distribution, or ϵ-far from all DPP distributions in ℓ1-distance. In this work, we propose the first algorithm for testing DPPs. Furthermore, we establish a matching lower bound on the sample complexity of DPP testing. This lower bound also extends to showing a new hardness result for the problem of testing the more general class of log-submodular distributions.

This paper has been published as a spotlight at the 2020 Neural Information Processing Systems (NeurIPS) conference.

Please cite our work using the BibTeX below.

@misc{gatmiry2020testing,
      title={Testing Determinantal Point Processes}, 
      author={Khashayar Gatmiry and Maryam Aliakbarpour and Stefanie Jegelka},
      year={2020},
      eprint={2008.03650},
      archivePrefix={arXiv},
      primaryClass={cs.LG}
}