Group-Based Alternating Direction Method of Multipliers for Distributed Linear Classification
Group-Based Alternating Direction Method of Multipliers for Distributed Linear Classification
复制标题
用于分布式线性分类的基于群的乘法器交替方向方法
DOI：
10.1109/tcyb.2016.2570808
复制
发表时间：
2017-11
影响因子：
11.8
通讯作者：
Wang Ruili
中科院分区：
文献类型：
--
作者：
Wang Huihui;Gao Yang;Shi Yinghuan;Wang Ruili
乘法器交替方向法（ADMM）算法在分布式机器学习任务中得到了广泛的应用。然而，它有几个限制，例如，相对较低的收敛速度和昂贵的时间成本。为此，本文提出了一种新的分布式线性分类方法，即基于分组的ADMM （GADMM）。为了加快收敛速度和提高全局一致性，GADMM首先采用组层将所有从节点划分为若干组。然后，在组层收集所有本地变量（来自从节点）以生成不同的组变量。最后，通过加权平均的方法，协调组变量更新全局变量（从主节点），直到得到全局问题的解。通过理论分析，我们发现：1)GADMM的数学收敛速度为$O({1}/{k})$，其中${k}$为外迭代次数；2)与不采用分组方法的分布式ADMM框架相比，采用分组方法的GADMM可以提高收敛速度。此外，我们系统地评估了四个公开可用的LIBSVM数据集上的GADMM。对于分布式分类，与disADMM和乘法器- admm交替方向随机对偶坐标上升法相比，GADMM能够减少外部迭代次数，从而具有更快的收敛速度和更好的全局一致性。特别是，实验进行了统计显著性检验，结果验证了在webspam和epsilon等大规模数据集上，与disADMM相比，GADMM可以显著节省高达30%的总时间成本（精度损失小于0.6%）。
The alternating direction method of multipliers (ADMM) algorithm has been widely employed for distributed machine learning tasks. However, it suffers from several limitations, e.g., a relative low convergence speed, and an expensive time cost. To this end, in this paper, a novel method, namely the group-based ADMM (GADMM), is proposed for distributed linear classification. In particular, to accelerate the convergence speed and improve global consensus, a group layer is first utilized in GADMM to divide all the slave nodes into several groups. Then, all the local variables (from the slave nodes) are gathered in the group layer to generate different group variables. Finally, by using a weighted average method, the group variables are coordinated to update the global variable (from the master node) until the solution of the global problem is reached. According to the theoretical analysis, we found that: 1) GADMM can mathematically converge at the rate $O({1}/{k})$ , where ${k}$ is the number of outer iterations and 2) by using the grouping methods, GADMM can improve the convergence speed compared with the distributed ADMM framework without grouping methods. Moreover, we systematically evaluate GADMM on four publicly available LIBSVM datasets. Compared with disADMM and stochastic dual coordinate ascent with alternating direction method of multipliers-ADMM, for distributed classification, GADMM is able to reduce the number of outer iterations, which leads to faster convergence speed and better global consensus. In particular, the statistical significance test has been experimentally conducted and the results validate that GADMM can significantly save up to 30% of the total time cost (with less than 0.6% accuracy loss) compared with disADMM on large-scale datasets, e.g., webspam and epsilon.
登录
查看更多内容
DOI：
--
发表时间：
2015-07
期刊：
--
影响因子：
--
作者：
Ching-pei Lee;D. Roth
通讯作者：
Ching-pei Lee;D. Roth
DOI：
--
发表时间：
2014-06
期刊：
--
影响因子：
--
作者：
Taiji Suzuki
通讯作者：
Taiji Suzuki
DOI：
10.5555/1756006.1953017
发表时间：
2009-12
期刊：
J. Mach. Learn. Res.
影响因子：
--
作者：
Lin Xiao
通讯作者：
Lin Xiao
DOI：
--
发表时间：
2015-06
期刊：
ArXiv
影响因子：
--
作者：
Yossi Arjevani;Ohad Shamir
通讯作者：
Yossi Arjevani;Ohad Shamir
DOI：
--
发表时间：
2004-12
期刊：
--
影响因子：
--
作者：
H. Graf;E. Cosatto;L. Bottou;Igor Durdanovic;V. Vapnik
通讯作者：
H. Graf;E. Cosatto;L. Bottou;Igor Durdanovic;V. Vapnik