STRADS
Authors:
Open Access
- 18 April 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-16
Abstract
Machine learning (ML) algorithms are commonly applied to big data, using distributed systems that partition the data across machines and allow each machine to read and update all ML model parameters --- a strategy known as data parallelism. An alternative and complimentary strategy, model parallelism, partitions the model parameters for non-shared parallel access and updates, and may periodically repartition the parameters to facilitate communication. Model parallelism is motivated by two challenges that data-parallelism does not usually address: (1) parameters may be dependent, thus naive concurrent updates can introduce errors that slow convergence or even cause algorithm failure; (2) model parameters converge at different rates, thus a small subset of parameters can bottleneck ML algorithm completion. We propose scheduled model parallelism (SchMP), a programming approach that improves ML algorithm convergence speed by efficiently scheduling parameter updates, taking into account parameter dependencies and uneven convergence. To support SchMP at scale, we develop a distributed framework STRADS which optimizes the throughput of SchMP programs, and benchmark four common ML applications written as SchMP programs: LDA topic modeling, matrix factorization, sparse least-squares (Lasso) regression and sparse logistic regression. By improving ML progress per iteration through SchMP programming whilst improving iteration throughput through STRADS we show that SchMP programs running on STRADS outperform non-model-parallel ML implementations: for example, SchMP LDA and SchMP Lasso respectively achieve 10x and 5x faster convergence than recent, well-established baselines.Keywords
Funding Information
- Intel Corporation
- Defense Advanced Research Projects Agency (FA87501220324)
- National Institutes of Health (GWAS R01GM087694)
- National Science Foundation (CNS-1042537, CNS-1042543, IIS-1447676)
This publication has 19 references indexed in Scilit:
- Managed communication and consistency for fast data-parallel iterative analytics2015
- PeacockACM Transactions on Intelligent Systems and Technology, 2015
- Integrated Systems Approach Identifies Genetic Nodes and Networks in Late-Onset Alzheimer’s DiseaseCell, 2013
- Distributed GraphLabProceedings of the VLDB Endowment, 2012
- Scalable inference in latent variable models2012
- Pathwise coordinate optimizationThe Annals of Applied Statistics, 2007
- Finding scientific topicsProceedings of the National Academy of Sciences, 2004
- Penalized Regressions: The Bridge versus the LassoJournal of Computational and Graphical Statistics, 1998
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular GraphsSIAM Journal on Scientific Computing, 1998
- Markov Chains for Exploring Posterior DistributionsThe Annals of Statistics, 1994