Distributed Signal Detection under Communication Constraints

Jayadev Acharya, Clément L Canonne, Himanshu Tyagi
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:41-63, 2020.

Abstract

Independent draws from a $d$-dimensional spherical Gaussian distribution are distributed across users, each holding one sample. A central server seeks to distinguish between the two hypotheses: the distribution has zero mean, or the mean has $\ell_2$-norm at least $\varepsilon$, a pre-specified threshold. However, the users can each transmit at most $\ell$ bits to the server. This is the problem of detecting whether an observed signal is simply white noise in a distributed setting. We study this distributed testing problem with and without the availability of a common randomness shared by the users. We design schemes with and without such shared randomness which achieve sample complexities. We then obtain lower bounds for protocols with public randomness, tight when $\ell=O(1)$. We finally conclude with several conjectures and open problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-acharya20b, title = {Distributed Signal Detection under Communication Constraints}, author = {Acharya, Jayadev and Canonne, Cl{\'e}ment L and Tyagi, Himanshu}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {41--63}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/acharya20b/acharya20b.pdf}, url = {https://proceedings.mlr.press/v125/acharya20b.html}, abstract = { Independent draws from a $d$-dimensional spherical Gaussian distribution are distributed across users, each holding one sample. A central server seeks to distinguish between the two hypotheses: the distribution has zero mean, or the mean has $\ell_2$-norm at least $\varepsilon$, a pre-specified threshold. However, the users can each transmit at most $\ell$ bits to the server. This is the problem of detecting whether an observed signal is simply white noise in a distributed setting. We study this distributed testing problem with and without the availability of a common randomness shared by the users. We design schemes with and without such shared randomness which achieve sample complexities. We then obtain lower bounds for protocols with public randomness, tight when $\ell=O(1)$. We finally conclude with several conjectures and open problems.} }
Endnote
%0 Conference Paper %T Distributed Signal Detection under Communication Constraints %A Jayadev Acharya %A Clément L Canonne %A Himanshu Tyagi %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-acharya20b %I PMLR %P 41--63 %U https://proceedings.mlr.press/v125/acharya20b.html %V 125 %X Independent draws from a $d$-dimensional spherical Gaussian distribution are distributed across users, each holding one sample. A central server seeks to distinguish between the two hypotheses: the distribution has zero mean, or the mean has $\ell_2$-norm at least $\varepsilon$, a pre-specified threshold. However, the users can each transmit at most $\ell$ bits to the server. This is the problem of detecting whether an observed signal is simply white noise in a distributed setting. We study this distributed testing problem with and without the availability of a common randomness shared by the users. We design schemes with and without such shared randomness which achieve sample complexities. We then obtain lower bounds for protocols with public randomness, tight when $\ell=O(1)$. We finally conclude with several conjectures and open problems.
APA
Acharya, J., Canonne, C.L. & Tyagi, H.. (2020). Distributed Signal Detection under Communication Constraints. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:41-63 Available from https://proceedings.mlr.press/v125/acharya20b.html.

Related Material