Communication-Constrained Inference and the Role of Shared Randomness
Communication-Constrained Inference and the Role of Shared Randomness
复制标题
通信约束推理和共享随机性的作用
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Himanshu Tyagi
中科院分区：
文献类型：
--
作者：
Jayadev Acharya;C. Canonne;Himanshu Tyagi
中心服务器需要根据分布在多个用户上的样本执行统计推断，每个用户可以向中心发送有限长度的消息。我们研究了这种分布式推理环境下的分布学习和身份检验问题，并考察了共享随机性作为一种资源的作用。我们提出了一种通用的模拟和推断策略，该策略仅使用私有货币通信协议，并且对于分布学习来说是样本最优的。事实证明，这种通用策略即使对于私有货币协议之间的分发测试也是样本最优的。有趣的是，我们提出了一种公共货币协议，它在分布测试中优于模拟和推断，实际上是样本最优的。我们的公共币协议的基础是一个随机哈希，当应用于样本时，它将最小限度地缩小其分布与均匀分布的卡方距离。
A central server needs to perform statistical inference based on samples that are distributed over multiple users who can each send a message of limited length to the center. We study problems of distribution learning and identity testing in this distributed inference setting and examine the role of shared randomness as a resource. We propose a general purpose simulate-and-infer strategy that uses only private-coin communication protocols and is sample-optimal for distribution learning. This general strategy turns out to be sample-optimal even for distribution testing among private-coin protocols. Interestingly, we propose a public-coin protocol that outperforms simulate-and-infer for distribution testing and is, in fact, sample-optimal. Underlying our public-coin protocol is a random hash that when applied to the samples minimally contracts the chi-squared distance of their distribution from the uniform distribution.
登录
查看更多内容
DOI：
--
发表时间：
2018
期刊：
and Automata
影响因子：
--
作者：
Diakonikolas, Ilias;Gouleakis, Themis;Peebles, John;Price, Eric
通讯作者：
Price, Eric
DOI：
--
发表时间：
2017
期刊：
--
影响因子：
--
作者：
Ilias Diakonikolas;Elena Grigorescu;Jerry Li;Abhiram Natarajan;Krzysztof Onak;Ludwig Schmidt
通讯作者：
Ilias Diakonikolas;Elena Grigorescu;Jerry Li;Abhiram Natarajan;Krzysztof Onak;Ludwig Schmidt
影响因子：
0.7
作者：
Watson, Thomas
通讯作者：
Watson, Thomas
影响因子：
2.5
作者：
Jayadev Acharya;C. Canonne;Himanshu Tyagi
通讯作者：
Jayadev Acharya;C. Canonne;Himanshu Tyagi