Part of Advances in Neural Information Processing Systems 26 (NIPS 2013)
Yuchen Zhang, John Duchi, Michael I. Jordan, Martin J. Wainwright
We establish minimax risk lower bounds for distributed statistical estimation given a budget $B$ of the total number of bits that may be communicated. Such lower bounds in turn reveal the minimum amount of communication required by any procedure to achieve the classical optimal rate for statistical estimation. We study two classes of protocols in which machines send messages either independently or interactively. The lower bounds are established for a variety of problems, from estimating the mean of a population to estimating parameters in linear regression or binary classification.