Testing Determinantal Point Processes
Khashayar Gatmiry, Maryam Aliakbarpour, Stefanie Jegelka
Spotlight presentation: Orals & Spotlights Track 25: Probabilistic Models/Statistics
on Thu, Dec 10th, 2020 @ 16:30 – 16:40 GMT
on Thu, Dec 10th, 2020 @ 16:30 – 16:40 GMT
Poster Session 6 (more posters)
on Thu, Dec 10th, 2020 @ 17:00 – 19:00 GMT
GatherTown: Theory ( Town D2 - Spot C3 )
on Thu, Dec 10th, 2020 @ 17:00 – 19:00 GMT
GatherTown: Theory ( Town D2 - Spot C3 )
Join GatherTown
Only iff poster is crowded, join Zoom . Authors have to start the Zoom call from their Profile page / Presentation History.
Only iff poster is crowded, join Zoom . Authors have to start the Zoom call from their Profile page / Presentation History.
Toggle Abstract Paper (in Proceedings / .pdf)
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.