Testing Determinantal Point Processes
This addresses a theoretical gap in distribution testing for machine learning models of diversity, with incremental contributions to property testing and hardness results for log-submodular distributions.
The paper tackles the problem of property testing for determinantal point processes (DPPs), proposing the first algorithm to distinguish whether an unknown distribution is a DPP or far from all DPPs, and establishes a matching lower bound on sample complexity.
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 $\ell_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.