标题： 信息受限下分布式简单二元假设检验的样本复杂度 显示英文标题

标题： The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints

摘要： 本文解决了近期一篇论文（arXiv:2403.16981）中的两个开放问题，涉及在信息约束下分布式简单二元假设检验的样本复杂度。 第一个开放问题询问交互是否可以减少分布式简单二元假设检验的样本复杂度。本文表明，序列交互并无帮助。 第二个问题建议改进现有通信约束下简单二元假设检验的样本复杂度界限。我们为此情景推导出最优紧界，并解决了该问题。 我们的主要技术贡献包括：(i) 一个关于简单二元假设检验中贝叶斯误差的一次性下界，且满足关键的张量化性质；(ii) 对简单二元假设检验无约束情形下的样本复杂度公式的一个简洁证明，该公式最早由 arXiv:2403.16981 提出；(iii) 关于 Hellinger-$\lambda$ 散度的反向数据处理不等式，推广了 arXiv:1812.03031 和 arXiv:2206.02765 中的结果。 显示英文摘要

摘要： This paper resolves two open problems from a recent paper, arXiv:2403.16981, concerning the sample complexity of distributed simple binary hypothesis testing under information constraints. The first open problem asks whether interaction reduces the sample complexity of distributed simple binary hypothesis testing. In this paper, we show that sequential interaction does not help. The second problem suggests tightening existing sample complexity bounds for communication-constrained simple binary hypothesis testing. We derive optimally tight bounds for this setting and resolve this problem. Our main technical contributions are: (i) a one-shot lower bound on the Bayes error in simple binary hypothesis testing that satisfies a crucial tensorisation property; (ii) a streamlined proof of the formula for the sample complexity of simple binary hypothesis testing without constraints, first established in arXiv:2403.16981; and (iii) a reverse data-processing inequality for Hellinger-$\lambda$ divergences, generalising the results from arXiv:1812.03031 and arXiv:2206.02765.