NOMAD
Authors:
Open Access
- 1 July 2014
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 7 (11) , 975-986
Abstract
We develop an efficient parallel distributed algorithm for matrix completion, named NOMAD (Non-locking, stOchastic Multi-machine algorithm for Asynchronous and Decentralized matrix completion). NOMAD is a decentralized algorithm with non-blocking communication between processors. One of the key features of NOMAD is that the ownership of a variable is asynchronously transferred between processors in a decentralized fashion. As a consequence it is a lock-free parallel algorithm. In spite of being asynchronous, the variable updates of NOMAD are serializable, that is, there is an equivalent update ordering in a serial implementation. NOMAD outperforms synchronous algorithms which require explicit bulk synchronization after every iteration: our extensive empirical evaluation shows that not only does our algorithm perform well in distributed setting on commodity hardware, but also outperforms state-of-the-art algorithms on a HPC cluster both in multi-core and distributed memory settings.Keywords
This publication has 19 references indexed in Scilit:
- Parallel stochastic gradient algorithms for large-scale matrix completionMathematical Programming Computation, 2013
- Distributed GraphLabProceedings of the VLDB Endowment, 2012
- An architecture for parallel topic modelsProceedings of the VLDB Endowment, 2010
- Large-Scale Parallel Collaborative Filtering for the Netflix Prize2008
- MapReduceCommunications of the ACM, 2008
- Lessons from the Netflix prize challengeACM SIGKDD Explorations Newsletter, 2007
- Optimizing a conjugate gradient solver with non-blocking collective operationsParallel Computing, 2007
- On asynchronous iterationsJournal of Computational and Applied Mathematics, 2000
- Chaotic relaxationLinear Algebra and its Applications, 1969
- A Stochastic Approximation MethodThe Annals of Mathematical Statistics, 1951