Parallel Asynchronous Stochastic Dual Coordinate Descent Algorithms for High Efficiency and Stable Convergence
Journal
Proceedings - 29th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2021
Pages
44-53
Date Issued
2021
Author(s)
Abstract
Parallel asynchronous stochastic dual coordinate descent algorithm (PASSCoDe) is an efficient method to train linear models in multi-core shared-memory systems. PASSCoDe enjoys a good speedup when the number of threads is less than 8 on sparse datasets, i.e., the percentage of nonzero elements in the training data is relatively small. However, due to the memory conflict and delayed parameter access problem in parallel execution, it often diverges or does not converge to the best accuracy as a serial dual coordinate descent algorithm does. In this paper, we propose two algorithms - Adaptive Hybrid algorithm and Lazy-Sync algorithm, to overcome the convergence issues in parallel execution. Both algorithms use the current accuracy to guide the execution and strike a balance between accuracy and efficiency. Experimental results indicate that both algorithms converge to the same high accuracy as a sequential program does on all datasets tested except on an extremely small one. On the other hand, PASSCoDe sometimes converges to a less accurate value or does not converge at all on some datasets. Our methods also outperform PASSCoDe-Fix, an improved version of PASSCoDe, in stable convergence, execution speed, and scalability. For example, the Adaptive Hybrid algorithm runs up to 2.8 times faster than PASSCoDe-Fix, and the Lazy-Sync algorithm runs 11 times faster than PASSCoDe-Fix on dataset covtype with 10 threads. ? 2021 IEEE.
Subjects
Efficiency; Software testing; Stochastic systems; Convergence issues; Coordinate descent; Hybrid algorithms; Number of threads; Parallel executions; Sequential programs; Shared memory system; Stable convergence; Stochastic models
SDGs
Type
conference paper