Testing Determinantal Point Processes
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.
Code (0)
등록된 구현이 없습니다.
Tasks
DiversityPoint ProcessesSimilar Papers 제목 키워드 기반
Fast Sampling for Strongly Rayleigh Measures with Application to Determinantal Point Processes
In this note we consider sampling from (non-homogeneous) strongly Rayleigh probability measures. As an important corollary, we obtain a fast mixing Markov Chain sampler for Determinantal Point Processes.
Point ProcessesA New Many-Objective Evolutionary Algorithm Based on Determinantal Point Processes
To handle different types of Many-Objective Optimization Problems (MaOPs), Many-Objective Evolutionary Algorithms (MaOEAs) need to simultaneously maintain convergence and population diversity in the high-dimensional obje…
DiversityEvolutionary AlgorithmsPoint ProcessesDeterminantal thinning of point processes with network learning applications
A new type of dependent thinning for point processes in continuous space is proposed, which leverages the advantages of determinantal point processes defined on finite spaces and, as such, is particularly amenable to sta…
Point ProcessesSchedulingStructured Determinantal Point Processes
We present a novel probabilistic model for distributions over sets of structures -- for example, sets of sequences, trees, or graphs. The critical characteristic of our model is a preference for diversity: sets containin…
DiversityPoint ProcessesPose EstimationCoverage probability in wireless networks with determinantal scheduling
We propose a new class of algorithms for randomly scheduling network transmissions. The idea is to use (discrete) determinantal point processes (subsets) to randomly assign medium access to various {\em repulsive} subset…
Point ProcessesScheduling