Information-theoretic lower bounds for distributed statistical estimation with communication constraints
Yuchen Zhang, John C. Duchi, Michael I. Jordan, Martin J. Wainwright · arXiv (Cornell University) · 2013
We establish lower bounds on minimax risks for distributed statistical estimation under a communication budget. Such lower bounds reveal the minimum amount of communication required by any procedure to achieve the centralized minimax-optimal rates for statistical estimation. We study two classes of protocols: one in which machines send messages independently, and a second allowing for interactive communication. We establish lower bounds for several problems, including various types of location models, as well as for parameter estimation in regression models.