Testing Determinantal Point Processes

2020/08/09 by Gatmiry, Khashayar, Aliakbarpour, Maryam, Jegelka, Stefanie
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2008.03650

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 ε-far from all DPP distributions in ℓ₁-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.

Related

• Efficient Sampling for k-Determinantal Point Processes
• Rates of estimation for determinantal point processes
• Learning Determinantal Point Processes with Moments and Cycles
• Markov Determinantal Point Processes
• Asymptotic Equivalence of Fixed-size and Varying-size Determinantal Point Processes