论文标题
分布式高维相关测试的沟通复杂性
Communication Complexity of Distributed High Dimensional Correlation Testing
论文作者
论文摘要
两方观察到$ d $维矢量和标量的独立副本。他们试图测试他们的数据是否相关，也就是说，他们试图测试其观察值之间相关向量$ρ$的规范$ \ |ρ\ | _2 $超过$τ$还是$ 0 $。为此，它们进行交流并声明测试的输出。我们表明，对于解决上面的分布式相关测试问题，大致订购$ d/τ^2 $ coomenterion就足够且必要。此外，我们建立了大约$ d^2/τ^2 $位的下限，用于分布式相关估计所需的通信，从而在分布式相关测试所需的通信中，估算估算方法和测试方法次优。对于具有单向通信的一维情况，我们的界限即使在恒定状态下也很紧，并且提供了对两种类型误差概率的准确依赖性。
Two parties observe independent copies of a $d$-dimensional vector and a scalar. They seek to test if their data is correlated or not, namely they seek to test if the norm $\|ρ\|_2$ of the correlation vector $ρ$ between their observations exceeds $τ$ or is it $0$. To that end, they communicate interactively and declare the output of the test. We show that roughly order $d/τ^2$ bits of communication are sufficient and necessary for resolving the distributed correlation testing problem above. Furthermore, we establish a lower bound of roughly $d^2/τ^2$ bits for communication needed for distributed correlation estimation, rendering the estimate-and-test approach suboptimal in communication required for distributed correlation testing. For the one-dimensional case with one-way communication, our bounds are tight even in the constant and provide a precise dependence of communication complexity on the probabilities of error of two types.
