Theory Seminar - Statistical Inference Under Local Information Constraints

Title: Statistical Inference Under Local Information Constraints

Abstract: We start by asking the following puzzle. Independent samples from an unknown distribution p on {1, …, k} are distributed across n players, with each player holding one sample. Each player can communicate L bits to a central referee, who wants to simulate a sample from p. When L= log k, one player suffices, since they can send their sample to the referee. How many players are needed to enable simulation if each player can only send L<log k bits? 

The question above will be motivated as a path to solve distributed inference problems under communication constraints. We will consider two prototypical inference questions, distribution learning and identity testing. We will consider and discuss the power of shared/public randomness in distributed inference, and show that for identity testing, schemes without public randomness can be dramatically less efficient than those with. Finally, we show that our framework is general enough to be extended to other distributed settings, in particular to local differential privacy. 

Based on joint works with Clement Canonne, Cody Freitag, and Himanshu Tyagi.