Optimality guarantees for distributed statistical estimation
  Large data sets often require performing distributed statistical estimation,
with a full data set split across multiple machines and limited communication
between machines. To study such scenarios, we define and study some refinements
of the classical minimax risk that apply to distributed settings, comparing to
the performance of estimators with access to the entire data. Lower bounds on
these quantities provide a precise characterization of the minimum amount of
communication required to achieve the centralized minimax risk. We study two
classes of distributed protocols: one in which machines send messages
independently over channels without feedback, and a second allowing for
interactive communication, in which a central server broadcasts the messages
from a given machine to all other machines. We establish lower bounds for a
variety of problems, including location estimation in several families and
parameter estimation in different types of regression models. Our results
include a novel class of quantitative data-processing inequalities used to
characterize the effects of limited communication.
