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

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.

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