CommunicationConstrained Inference and the Role of Shared Randomness
[edit]
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:3039, 2019.
Abstract
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 simulateandinfer strategy that uses only privatecoin communication protocols and is sampleoptimal for distribution learning. This general strategy turns out to be sampleoptimal even for distribution testing among privatecoin protocols. Interestingly, we propose a publiccoin protocol that outperforms simulateandinfer for distribution testing and is, in fact, sampleoptimal. Underlying our publiccoin protocol is a random hash that when applied to the samples minimally contracts the chisquared distance of their distribution from the uniform distribution.
Related Material


