Testing Determinantal Point Processes

Abstract

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 $\epsilon$-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.

References in corpus (14)

• Determinantal Processes and Independence
• Determinantal point process models and statistical inference : Extended version
• Optimal Algorithms for Testing Closeness of Discrete Distributions
• Learning Determinantal Point Processes
• Optimal Testing for Properties of Distributions
• Learning the Parameters of Determinantal Point Process Kernels
• Fast DPP Sampling for Nyström with Application to Kernel Methods
• Expectation-Maximization for Learning Determinantal Point Processes
• Fixed-point algorithms for learning determinantal point processes
• The Kadison-Singer Problem for Strongly Rayleigh Measures and Applications to Asymmetric TSP
• Polynomial Time Algorithms for Dual Volume Sampling
• Diversifying Sparsity Using Variational Determinantal Point Processes
• Learning Determinantal Point Processes in Sublinear Time
• Learning Signed Determinantal Point Processes through the Principal Minor Assignment Problem