Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction
Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction
复制标题
DOI：
10.1109/tit.2020.3028440
复制
发表时间：
2018-12
影响因子：
2.5
通讯作者：
Jayadev Acharya;C. Canonne;Himanshu Tyagi
中科院分区：
文献类型：
--
作者：
Jayadev Acharya;C. Canonne;Himanshu Tyagi
多名球员每人都会获得一个独立的样本，他们只能向中央裁判提供有限的信息。每个玩家都可以使用通道族 $\mathcal {W}$ 中的一个通道向裁判描述其观察到的样本，该通道可以被实例化以捕获通信和隐私约束设置等。裁判使用玩家的消息来解决生成样本的未知分布的推理问题。我们得出了在这种信息受限的环境中学习和测试离散分布的样本复杂性的下限。我们的界限的基础是当施加信息约束时观察到的样本分布之间的卡方距离收缩的特征。这种收缩是通过给定通道的卡方波动和解耦卡方波动（我们引入的两个量）在局部邻域中捕获的。前者捕获输入上两个产品分布的通道输出分布之间的平均距离，后者捕获输入上的产品分布和产品分布混合的通道输出分布之间的平均距离。我们对于公共和私有币协议的界限都很严格。有趣的是，当仅限于私有币协议时，测试的样本复杂性按顺序会更高。
Multiple players are each given one independent sample, about which they can only provide limited information to a central referee. Each player is allowed to describe its observed sample to the referee using a channel from a family of channels $\mathcal {W}$ , which can be instantiated to capture, among others, both the communication- and privacy-constrained settings. The referee uses the players’ messages to solve an inference problem on the unknown distribution that generated the samples. We derive lower bounds for the sample complexity of learning and testing discrete distributions in this information-constrained setting. Underlying our bounds is a characterization of the contraction in chi-square distance between the observed distributions of the samples when information constraints are placed. This contraction is captured in a local neighborhood in terms of chi-square and decoupled chi-square fluctuations of a given channel, two quantities we introduce. The former captures the average distance between distributions of channel output for two product distributions on the input, and the latter for a product distribution and a mixture of product distribution on the input. Our bounds are tight for both public- and private-coin protocols. Interestingly, the sample complexity of testing is order-wise higher when restricted to private-coin protocols.