Distributed Matrix Completion and Robust Factorization

If learning methods are to scale to the massive sizes of modern data sets, it is essential for the field of machine learning to embrace parallel and distributed computing. Inspired by the recent development of matrix factorization methods with rich theory but poor computational complexity and by the relative ease of mapping matrices onto distributed architectures, we introduce a scalable divide-and-conquer framework for noisy matrix factorization. We present a thorough theoretical analysis of this framework in which we characterize the statistical errors introduced by the "divide" step and control their magnitude in the "conquer" step, so that the overall algorithm enjoys high-probability estimation guarantees comparable to those of its base algorithm. We also present experiments in collaborative filtering and video background modeling that demonstrate the near-linear to superlinear speed-ups attainable with this approach. [abs] [ pdf ][ bib ] &copy JMLR 2015. ( edit, beta )

Authors

• Lester Mackey Microsoft Research
• Ameet Talwalkar Carnegie Mellon University
• Michael I. Jordan UC Berkeley

Keywords

No keywords are indexed for this paper.