We study the tradeoff between the statistical error and communication cost of
distributed statistical estimation problems in high dimensions. In the
distributed sparse Gaussian mean estimation problem, each of the $m$ machines
receives $n$ data points from a $d$-dimensional Gaussian distribution with
unknown mean $\theta$ which is promised to be $k$-sparse. The machines
communicate by message passing and aim to estimate the mean $\theta$. We
provide a tight (up to logarithmic factors) tradeoff between the estimation
error and the number of bits communicated between the machines. This directly
leads to a lower bound for the distributed \textit{sparse linear regression}
problem: to achieve the statistical minimax error, the total communication is
at least $\Omega(\min\{n,d\}m)$, where $n$ is the number of observations that
each machine receives and $d$ is the ambient dimension. These lower results
improve upon [Sha14,SD'14] by allowing multi-round iterative communication
model. We also give the first optimal simultaneous protocol in the dense case
for mean estimation.
As our main technique, we prove a \textit{distributed data processing
inequality}, as a generalization of usual data processing inequalities, which
might be of independent interest and useful for other problems.

本文研究了高维分布统计估计问题的统计误差和通信成本之间的权衡，并提供了分布式稀疏高斯均值估计问题的紧密的权衡分析结果，这直接导致了分布式稀疏线性回归问题的下界，并给出了在稠密情况下均值估计的第一个最优同时协议。