Adding vs. Averaging in Distributed Primal-Dual Optimization
Adding vs. Averaging in Distributed Primal-Dual Optimization
复制标题
DOI：
--
复制
发表时间：
2015-02
期刊：
影响因子：
--
通讯作者：
Chenxin Ma;Virginia Smith;Martin Jaggi;Michael I. Jordan;Peter Richtárik;Martin Takác
中科院分区：
文献类型：
--
作者：
Chenxin Ma;Virginia Smith;Martin Jaggi;Michael I. Jordan;Peter Richtárik;Martin Takác
用于大规模机器学习的分布式优化方法遭受通信瓶颈。很难减少这个瓶颈，同时仍然有效和准确地聚合来自不同机器的部分工作。在本文中，我们提出了一个新的推广最近的通信有效的原始-对偶框架（可可）的分布式优化。我们的框架，可可COCOA+，允许在每次迭代的局部更新的全局参数的加法组合，而以前的计划与收敛保证只允许保守的平均。我们给出了更强的（原始-对偶）收敛速度保证可可以及我们的新变种，并推广了这两种方法的理论，以涵盖非光滑凸损失函数。我们提供了一个广泛的实验比较，显示了显着提高性能的可可+在几个真实世界的分布式数据集，特别是当扩大机器的数量。
Distributed optimization methods for large-scale machine learning suffer from a communication bottleneck. It is difficult to reduce this bottleneck while still efficiently and accurately aggregating partial work from different machines. In this paper, we present a novel generalization of the recent communication-efficient primal-dual framework (COCOA) for distributed optimization. Our framework, COCOA+, allows for additive combination of local updates to the global parameters at each iteration, whereas previous schemes with convergence guarantees only allow conservative averaging. We give stronger (primal-dual) convergence rate guarantees for both COCOA as well as our new variants, and generalize the theory for both methods to cover non-smooth convex loss functions. We provide an extensive experimental comparison that shows the markedly improved performance of COCOA+ on several real-world distributed datasets, especially when scaling up the number of machines.