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.

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

通过分布式数据处理不等式推导统计估计问题的通信下界

Communication Lower Bounds for Statistical Estimation Problems via a  Distributed Data Processing Inequality

We present DUAL-LOCO, a communication-efficient algorithm for distributed
statistical estimation. DUAL-LOCO assumes that the data is distributed
according to the features rather than the samples. It requires only a single
round of communication where low-dimensional random projections are used to
approximate the dependences between features available to different workers. We
show that DUAL-LOCO has bounded approximation error which only depends weakly
on the number of workers. We compare DUAL-LOCO against a state-of-the-art
distributed optimization method on a variety of real world datasets and show
that it obtains better speedups while retaining good accuracy.

DUAL-LOCO 是一种通信高效的分布式统计估计算法，通过低维随机投影来近似不同工作者之间可用特征之间的依赖关系，具有有界的近似误差，并在各种真实世界数据集上与最先进的分布式优化方法进行比较，同时保持较好的准确性。