Communication-Constrained Inference and the Role of Shared Randomness

Jayadev Acharya, Clement Canonne, Himanshu Tyagi
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:30-39, 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 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-acharya19a, title = {Communication-Constrained Inference and the Role of Shared Randomness}, author = {Acharya, Jayadev and Canonne, Clement and Tyagi, Himanshu}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {30--39}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/acharya19a/acharya19a.pdf}, url = {https://proceedings.mlr.press/v97/acharya19a.html}, 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 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.} }
Endnote
%0 Conference Paper %T Communication-Constrained Inference and the Role of Shared Randomness %A Jayadev Acharya %A Clement Canonne %A Himanshu Tyagi %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-acharya19a %I PMLR %P 30--39 %U https://proceedings.mlr.press/v97/acharya19a.html %V 97 %X 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.
APA
Acharya, J., Canonne, C. & Tyagi, H.. (2019). Communication-Constrained Inference and the Role of Shared Randomness. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:30-39 Available from https://proceedings.mlr.press/v97/acharya19a.html.

Related Material