Distributed Matrix Completion
Authors:
- Christina TeflioudiCTChristina Teflioudi
- Faraz MakariFMFaraz Makari
- Rainer GemullaRGRainer Gemulla
- 1 December 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15504786,p. 655-664
Abstract
We discuss parallel and distributed algorithms for large-scale matrix completion on problems with millions of rows, millions of columns, and billions of revealed entries. We focus on in-memory algorithms that run on a small cluster of commodity nodes, even very large problems can be handled effectively in such a setup. Our DALS, ASGD, and DSGD++ algorithms are novel variants of the popular alternating least squares and stochastic gradient descent algorithms, they exploit thread-level parallelism, in-memory processing, and asynchronous communication. We provide some guidance on the asymptotic performance of each algorithm and investigate the performance of both our algorithms and previously proposed Map Reduce algorithms in large-scale experiments. We found that DSGD++ outperforms competing methods in terms of overall runtime, memory consumption, and scalability. Using DSGD++, we can factor a matrix with 10B entries on 16 compute nodes in around 40 minutes.Keywords
This publication has 10 references indexed in Scilit:
- Large-scale matrix factorization with distributed stochastic gradient descent2011
- An architecture for parallel topic modelsProceedings of the VLDB Endowment, 2010
- Ricardo2010
- Distributed nonnegative matrix factorization for web-scale dyadic data analysis on mapreduce2010
- Matrix Factorization Techniques for Recommender SystemsComputer, 2009
- Exact Matrix Completion via Convex OptimizationFoundations of Computational Mathematics, 2009
- Collaborative Filtering for Implicit Feedback Datasets2008
- Google news personalization2007
- A Limited Memory Algorithm for Bound Constrained OptimizationSIAM Journal on Scientific Computing, 1995
- Distributed asynchronous deterministic and stochastic gradient optimization algorithmsIEEE Transactions on Automatic Control, 1986