Distributed Statistical Estimation of High-Dimensional Distributions and Parameters under Communication Constraints

Modern data sets are often distributed across multiple machines and processors, and bandwidth and energy limitations in networks and within multiprocessor systems often impose significant bottlenecks on the performance of algorithms. Motivated by this trend, we consider the problem of estimating high-dimensional distributions and parameters in a distributed network, where each node in the network observes an independent sample from the underlying distribution and can communicate it to a central processor by writing at most k bits on a public blackboard. We obtain matching upper and lower bounds for the minimax risk of estimating the underlying distribution or parameter under various common statistical models. Our results show that the impact of the communication constraint can be qualitatively different depending on the tail behavior of the score function associated with each model. The key ingredient in our proof is a geometric characterization of Fisher information from quantized samples.

Joint work with Leighton Barnes, Yanjun Han, and Tsachy Weissman.