Logo image
Back
Hybrid-DCA: A double asynchronous approach for stochastic dual coordinate ascent
Journal article   Open access   Peer reviewed

Hybrid-DCA: A double asynchronous approach for stochastic dual coordinate ascent

Soumitra Pal, Tingyang Xu, Tianbao Yang, Sanguthevar Rajasekaran and Jinbo Bi
Journal of parallel and distributed computing, Vol.143, pp.47-66
09/2020
DOI: 10.1016/j.jpdc.2020.04.002
PMCID: PMC7375401
PMID: 32699464
url
https://doi.org/10.1016/j.jpdc.2020.04.002View
Published (Version of record) Open Access

Abstract

In prior works, stochastic dual coordinate ascent (SDCA) has been parallelized in a multi-core environment where the cores communicate through shared memory, or in a multi-processor distributed memory environment where the processors communicate through message passing. In this paper, we propose a hybrid SDCA framework for multi-core clusters, the most common high performance computing environment that consists of multiple nodes each having multiple cores and its own shared memory. We distribute data across nodes where each node solves a local problem in an asynchronous parallel fashion on its cores, and then the local updates are aggregated via an asynchronous across-node update scheme. The proposed double asynchronous method converges to a global solution for L-Lipschitz continuous loss functions, and at a linear convergence rate if a smooth convex loss function is used. Extensive empirical comparison has shown that our algorithm scales better than the best known shared-memory methods and runs faster than previous distributed-memory methods. Big datasets, such as one of 280 GB from the LIBSVM repository, cannot be accommodated on a single node and hence cannot be solved by a parallel algorithm. For such a dataset, our hybrid algorithm takes less than 30 s to achieve a duality gap of 10−5 on 16 nodes each using 12 cores, which is significantly faster than the best known distributed algorithms, such as CoCoA+, that take more than 160 s on 16 nodes. •A novel and practical framework for solving optimization problems in machine learning using modern high performance computing platforms.•Double asynchronous updates both at the inter-core level within a node and at the inter-node level enable better utilization of modern multicore clusters.•Global solution has provable theoretical convergence.•Experimental results show more than 10x improvements on big datasets.
 Distributed computing Dual coordinate descent Optimization

Details

Metrics

13 Record Views
3 Times Cited - Web of Science
Logo image