Timezone: »

 
Poster
Communication-Constrained Inference and the Role of Shared Randomness
Jayadev Acharya · Clément Canonne · Himanshu Tyagi

Thu Jun 13 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #169
in Posters Thu »

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 \textit{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.

Keywords: Information Theory and Estimation · Statistical Learning Theory

Author Information

Jayadev Acharya (Cornell University)
Clément Canonne (Stanford University)
Himanshu Tyagi (IISC)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors