Group-Based Alternating Direction Method of Multipliers for Distributed Linear Classification
Authors:
- 1 June 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Cybernetics
- Vol. 47 (11) , 3568-3582
Abstract
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.Keywords
Funding Information
- National Science Foundation of China (61432008, 61305068, 61321491)
- Collaborative Innovation Center of Novel Software Technology and Industrialization
- full Marsden
- New Zealand
This publication has 26 references indexed in Scilit:
- Semi-Supervised Nonnegative Matrix Factorization via Constraint PropagationIEEE Transactions on Cybernetics, 2015
- Distributed Object Detection With Linear SVMsIEEE Transactions on Cybernetics, 2014
- Fast Alternating Direction Optimization MethodsSIAM Journal on Imaging Sciences, 2014
- Online Selective Kernel-Based Temporal Difference LearningIEEE Transactions on Neural Networks and Learning Systems, 2013
- On the $O(1/n)$ Convergence Rate of the Douglas–Rachford Alternating Direction MethodSIAM Journal on Numerical Analysis, 2012
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of MultipliersFoundations and Trends in Machine Learning, 2011
- Validation analysis of mirror descent stochastic approximation methodMathematical Programming, 2011
- Pegasos: primal estimated sub-gradient solver for SVMMathematical Programming, 2010
- A dual coordinate descent method for large-scale linear SVM2008
- On the Convergence of Augmented Lagrangian Methods for Constrained Global OptimizationSIAM Journal on Optimization, 2008