Fixing the convergence problems in parallel asynchronous dual coordinate descent

Huan Zhang, Cho Jui Hsieh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Solving L2-regularized empirical risk minimization (e.g., linear SVMs and logistic regression) using multiple cores has become an important research topic. Among all the existing algorithms, Parallel ASynchronous Stochastic dual Co-Ordinate DEscent (PASSCoDe) demonstrates superior performance compared with other methods. Although PASSCoDe is fast when it converges, the algorithm has been observed to diverge on several cases especially when a relatively large number of threads are used. This is mainly due to the delayed parameter access problem -The parameters used for the current update may be delayed and are not the latest ones. In theory, the algorithm converges only when the delay is small enough, but in practice the delay depends on the underlying parallel computing environment and cannot be guaranteed. In this work, we propose a simple and computational efficient way to fix the convergence problem of PASSCoDe. Instead of allowing all worker threads to conduct asynchronous updates wildly, we add periodic check points to the procedure, where all workers need to stop and refine the current solution at each check point. The resulting 'semi-Asynchronous' algorithm is guaranteed to converge for any problem even when PASSCoDe diverges, and for the cases where PASSCoDe converges they have almost identical speed.

Original languageEnglish (US)
Title of host publicationProceedings - 16th IEEE International Conference on Data Mining, ICDM 2016
EditorsFrancesco Bonchi, Xindong Wu, Ricardo Baeza-Yates, Josep Domingo-Ferrer, Zhi-Hua Zhou
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages619-628
Number of pages10
ISBN (Electronic)9781509054725
DOIs
StatePublished - Jan 31 2017
Externally publishedYes
Event16th IEEE International Conference on Data Mining, ICDM 2016 - Barcelona, Catalonia, Spain
Duration: Dec 12 2016Dec 15 2016

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786

Other

Other16th IEEE International Conference on Data Mining, ICDM 2016
Country/TerritorySpain
CityBarcelona, Catalonia
Period12/12/1612/15/16

Keywords

  • Asynchronous algorithm
  • Coordinate descent

ASJC Scopus subject areas

  • General Engineering

Fingerprint

Dive into the research topics of 'Fixing the convergence problems in parallel asynchronous dual coordinate descent'. Together they form a unique fingerprint.

Cite this