Distributed matrix completion and robust factorization

zbMATH Open1337.68225arXiv1107.0789MaRDI QIDQ5502138FDOQ5502138

Authors: Lester Mackey, Ameet Talwalkar, Michael Jordan 

Publication date: 17 August 2015

Abstract: If learning methods are to scale to the massive sizes of modern datasets, 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.

Full work available at URL: https://arxiv.org/abs/1107.0789

Recommendations

• Parallel stochastic gradient algorithms for large-scale matrix completion
• Distributed Bayesian matrix factorization with limited communication
• Matrix completion and low-rank SVD via fast alternating least squares
• Spectral regularization algorithms for learning large incomplete matrices
• Online learning for matrix factorization and sparse coding

zbMATH Keywords

matrix factorizationmatrix completionrandomized algorithmsdistributed algorithmscollaborative filteringparallel algorithmsdivide-and-conquervideo surveillancerobust matrix factorization

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Factorization of matrices (15A23) Randomized algorithms (68W20) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Cited In (19)

• Distributed Bayesian matrix factorization with limited communication
• Decentralized Gradient-Quantization Based Matrix Factorization for Fast Privacy-Preserving Point-of-Interest Recommendation
• Distributed Orthogonal Factorization: Givens and Householder Algorithms
• Title not available (Why is that?)
• Parallelizing spectrally regularized kernel algorithms
• A distributed Frank-Wolfe framework for learning low-rank matrices with the trace norm
• Communication-efficient distributed \(M\)-estimation with missing data
• Communication-efficient distributed statistical inference
• Meta Clustering for Collaborative Learning
• Title not available (Why is that?)
• A MOM-based ensemble method for robustness, subsampling and hyperparameter tuning
• Distributed Robust Subspace Recovery
• CEDAR: Communication Efficient Distributed Analysis for Regressions
• LIBMF: a library for parallel matrix factorization in shared-memory systems
• Robust PCA by manifold optimization
• Title not available (Why is that?)
• Partitioned Approach for High-dimensional Confidence Intervals with Large Split Sizes
• A distributed and integrated method of moments for high-dimensional correlated data analysis
• Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset

Uses Software

• Jellyfish
• HOGWILD

This page was built for publication: Distributed matrix completion and robust factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5502138)