Communication-efficient algorithms for statistical optimization
Communication-efficient algorithms for statistical optimization
复制标题
DOI：
10.5555/2567709.2567769
复制
发表时间：
2012-12
期刊：
影响因子：
--
通讯作者：
Yuchen Zhang;John C. Duchi;M. Wainwright
中科院分区：
文献类型：
--
作者：
Yuchen Zhang;John C. Duchi;M. Wainwright
我们研究了两种通信效率高的算法，用于大规模数据的分布式统计优化。第一种算法是平均方法，将N个数据样本均匀分布到m台机器上，对每个子集执行单独的最小化，然后对估计值进行平均。我们提供了一个尖锐的分析，这种平均混合算法，表明在一组合理的条件下，组合参数实现的均方误差衰减为O（N-1 +（N/m）-2）。当m ≤ N时，该保证与通过访问所有N个样本的集中式算法可实现的最佳可能速率相匹配。第二种算法是一种新的方法，基于适当形式的引导。它只需要一轮通信，具有衰减为O（N-1 +（N/m）-3）的均方误差，因此对并行化的数量更具鲁棒性。
We study two communication-efficient algorithms for distributed statistical optimization on large-scale data. The first algorithm is an averaging method that distributes the N data samples evenly to m 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 O(N-1 + (N/m)-2). Whenever m ≤ √N, this guarantee matches the best possible rate achievable by a centralized algorithm with access to all N samples. The second algorithm is a novel method, based on an appropriate form of bootstrap. Requiring only a single round of communication, it has mean-squared error that decays as O(N-1 + (N/m)-3), and so is more robust to the amount of parallelization.