We analyze two communication-efficient algorithms for distributed statistical
optimization on large-scale data sets. The first algorithm is a standard
averaging method that distributes the $N$ data samples evenly to $\nummac$
machines, performs separate minimization on each subset, and then averages the
estimates. We provide a sharp analysis of this average mixture algorithm,
showing that under a reasonable set of conditions, the combined parameter
achieves mean-squared error that decays as $\order(N^{-1}+(N/m)^{-2})$.
Whenever $m \le \sqrt{N}$, this guarantee matches the best possible rate
achievable by a centralized algorithm having access to all $\totalnumobs$
samples. The second algorithm is a novel method, based on an appropriate form
of bootstrap subsampling. Requiring only a single round of communication, it
has mean-squared error that decays as $\order(N^{-1} + (N/m)^{-3})$, and so is
more robust to the amount of parallelization. In addition, we show that a
stochastic gradient-based method attains mean-squared error decaying as
$O(N^{-1} + (N/ m)^{-3/2})$, easing computation at the expense of penalties in
the rate of convergence. We also provide experimental evaluation of our
methods, investigating their performance both on simulated data and on a
large-scale regression problem from the internet search domain. In particular,
we show that our methods can be used to efficiently solve an advertisement
prediction problem from the Chinese SoSo Search Engine, which involves logistic
regression with $N \approx 2.4 \times 10^8$ samples and $d \approx 740,000$
covariates.

分析了两种用于大规模数据集的分布式统计优化的通信有效算法，一种是标准平均法，另一种是基于适当形式的自助子抽样的新算法，实验结果表明两种方法都有效地解决了中文 SoSo 搜索引擎的广告预测问题。