论文标题
测试确定点过程
Testing Determinantal Point Processes
论文作者
论文摘要
确定点过程（DPP）是流行的多样性概率模型。在本文中，我们从新的角度研究了DPP：分布的属性测试。给定对未知分配$ q $访问地面套件的示例访问，我们旨在区分$ q $是DPP分配，还是$ \ ell_1 $ distance中的所有DPP发行版的$ε$ -FAR。在这项工作中，我们提出了第一种用于测试DPP的算法。此外，我们在DPP测试的样品复杂性上建立了匹配的下限。该下限还扩展到显示了测试更通用的对数 - 模块化分布类别的问题的新硬度结果。
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.
