论文标题
沟通受限的假设测试：最佳，鲁棒性和反向数据处理不平等现象
Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities
论文作者
论文摘要
我们研究了在交流约束下的假设检验，其中每个样本在向统计学家展示之前进行量化。没有通信限制，众所周知，简单二进制假设检验的样本复杂性的特征是分布之间的距离。我们表明，在通信约束下，简单的二元假设检验的样本复杂性最多是对对数因素大于不受约束的设置，并且该界限很紧。我们开发一种多项式时算法，该算法可实现上述样品复杂性。我们的框架扩展到可靠的假设检验，其中分布在总变化距离处被损坏。我们的证明依赖于新的反向数据处理不平等和反向马尔可夫的不平等，这可能引起独立的兴趣。对于简单的$ M $ - ARY假设测试，在没有通信约束的情况下，样本复杂性具有对数依赖性$ M $。我们表明，即使对于自适应算法，通信约束也可能导致$ω（m）$样本复杂性，导致指数爆炸。
We study hypothesis testing under communication constraints, where each sample is quantized before being revealed to a statistician. Without communication constraints, it is well known that the sample complexity of simple binary hypothesis testing is characterized by the Hellinger distance between the distributions. We show that the sample complexity of simple binary hypothesis testing under communication constraints is at most a logarithmic factor larger than in the unconstrained setting and this bound is tight. We develop a polynomial-time algorithm that achieves the aforementioned sample complexity. Our framework extends to robust hypothesis testing, where the distributions are corrupted in the total variation distance. Our proofs rely on a new reverse data processing inequality and a reverse Markov inequality, which may be of independent interest. For simple $M$-ary hypothesis testing, the sample complexity in the absence of communication constraints has a logarithmic dependence on $M$. We show that communication constraints can cause an exponential blow-up leading to $Ω(M)$ sample complexity even for adaptive algorithms.
