Data/feature distributed stochastic coordinate descent for logistic regression

Dongyeop Kang, Woosang Lim, Kijung Shin, Lee Sael, U. Kang

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

9 Scopus citations

Abstract

How can we scale-up logistic regression, or L1 regularized loss minimization in general, for Terabyte-scale data which do not fit in the memory? How to design the distributed algorithm efficiently? Although there exist two major algorithms for logistic regression, namely Stochastic Gradient Descent (SGD) and Stochastic Coordinate Descent (SCD), they face limitations in distributed environments. Distributed SGD enables data parallelism (i.e., different machines access different part of the input data), but it does not allow feature parallelism (i.e., different machines compute different subsets of the output), and thus the communication cost is high. On the other hand, Distributed SCD allows feature parallelism, but it does not allow data parallelism and thus is not suitable to work in distributed environments. In this paper we propose DF-DSCD (Data/Feature Distributed Stochastic Coordinate Descent), an efficient distributed algorithm for logistic regression, or L1 regularized loss minimization in general. DF-DSCD allows both data and feature parallelism. The benefits of DF-DSCD are (a) full utilization of the capabilities provided by modern distributing computing platforms like MAPREDUCE to analyze web-scale data, and (b) independence of each machine in updating parameters with little communication cost. We prove the convergence of DF-DSCD both theoretically, and also show empirical evidence that it is scalable, handles very high-dimensional data with up to 29 millions of features, and converges 2.2× faster than competitors.

Original languageEnglish (US)
Title of host publicationCIKM 2014 - Proceedings of the 2014 ACM International Conference on Information and Knowledge Management
PublisherAssociation for Computing Machinery
Pages1269-1278
Number of pages10
ISBN (Electronic)9781450325981
DOIs
StatePublished - Nov 3 2014
Externally publishedYes
Event23rd ACM International Conference on Information and Knowledge Management, CIKM 2014 - Shanghai, China
Duration: Nov 3 2014Nov 7 2014

Publication series

NameCIKM 2014 - Proceedings of the 2014 ACM International Conference on Information and Knowledge Management

Other

Other23rd ACM International Conference on Information and Knowledge Management, CIKM 2014
Country/TerritoryChina
CityShanghai
Period11/3/1411/7/14

Bibliographical note

Publisher Copyright:
Copyright 2014 ACM.

Keywords

  • Coordinate descent
  • Distributed computing
  • Hadoop
  • L regularized loss minimization
  • Logistic regression
  • MapReduce

Fingerprint

Dive into the research topics of 'Data/feature distributed stochastic coordinate descent for logistic regression'. Together they form a unique fingerprint.

Cite this