A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization
A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization
复制标题
正则化损失最小化的通用分布式双坐标优化框架
DOI：
--
复制
发表时间：
2016-04
影响因子：
6
通讯作者：
Zhang Tong
中科院分区：
文献类型：
--
作者：
Zheng Shun;Wang Jialei;Xia Fen;Xu Wei;Zhang Tong
在现代大规模机器学习应用中，训练数据通常被分区并存储在多台机器上。通常采用“数据并行”方法，在不跨机器移动数据的情况下将聚合训练损失最小化。在本文中，我们介绍了一种新颖的分布式对偶公式来解决正则化损失最小化问题，它可以直接处理分布式设置中的数据并行性。这个公式使我们能够系统地导出双坐标优化程序，我们将其称为分布式交替双最大化（DADM）。该框架扩展了（Boyd et al., 2011; Ma et al., 2015a; Jaggi et al., 2014; Yang, 2013）中描述的早期研究，并具有严格的理论分析。此外，在新公式的帮助下，我们通过将（Shalev-Shwartz 和Zhang，2014）的加速技术推广到分布式设置，开发了 DADM 的加速版本（Acc-DADM）。我们还为所提出的加速版本提供了理论结果，新结果改进了之前的结果（Yang，2013；Ma et al.，2015a），其运行时间随条件数线性增长。我们的实证研究验证了我们的理论，并表明我们的加速方法显着改进了以前最先进的分布式双坐标优化算法。
In modern large-scale machine learning applications, the training data are often partitioned and stored on multiple machines. It is customary to employ the "data parallelism" approach, where the aggregated training loss is minimized without moving data across machines. In this paper, we introduce a novel distributed dual formulation for regularized loss minimization problems that can directly handle data parallelism in the distributed setting. This formulation allows us to systematically derive dual coordinate optimization procedures, which we refer to as Distributed Alternating Dual Maximization (DADM). The framework extends earlier studies described in (Boyd et al., 2011; Ma et al., 2015a; Jaggi et al., 2014; Yang, 2013) and has rigorous theoretical analyses. Moreover with the help of the new formulation, we develop the accelerated version of DADM (Acc-DADM) by generalizing the acceleration technique from (Shalev-Shwartz and Zhang, 2014) to the distributed setting. We also provide theoretical results for the proposed accelerated version and the new result improves previous ones (Yang, 2013; Ma et al., 2015a) whose runtimes grow linearly on the condition number. Our empirical studies validate our theory and show that our accelerated approach significantly improves the previous state-of-the-art distributed dual coordinate optimization algorithms.
登录
查看更多内容
DOI：
--
发表时间：
2015-07
期刊：
--
影响因子：
--
作者：
Ching-pei Lee;D. Roth
通讯作者：
Ching-pei Lee;D. Roth
DOI：
10.1007/11752578_29
发表时间：
2005-09
期刊：
--
影响因子：
--
作者：
R. Graham;Timothy S. Woodall;Jeffrey M. Squyres
通讯作者：
R. Graham;Timothy S. Woodall;Jeffrey M. Squyres
DOI：
--
发表时间：
2015-02
期刊：
ArXiv
影响因子：
--
作者：
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
影响因子：
2.7
作者：
Shai Shalev-Shwartz;Tong Zhang
通讯作者：
Shai Shalev-Shwartz;Tong Zhang
DOI：
10.1007/b98874
发表时间：
2018-09
期刊：
--
影响因子：
--
作者：
J. Nocedal;Stephen J. Wright
通讯作者：
J. Nocedal;Stephen J. Wright