Divide-and-Conquer Matrix Factorization

By Lester W. Mackey, Ameet Talwalkar, Michael I. Jordan. 2011

204 citations recorded by the source corpus.

This work introduces Divide-Factor-Combine (DFC), a parallel divide-and-conquer framework for noisy matrix factorization. DFC divides a large-scale matrix factorization task into smaller subproblems, solves each subproblem in parallel using an arbitrary base matrix factorization algorithm, and combines the sub-problem solutions using techniques from randomized matrix approximation. Our experiments with collaborative filtering, video background modeling, and simulated data demonstrate the near-linear to super-linear speed-ups attainable with this approach. Moreover, our analysis shows that DFC enjoys high-probability recovery guarantees comparable to those of its base algorithm.

Subfields: Computational Mathematics, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computational Mechanics

Citations in the corpus

A Neural Autoregressive Approach to Collaborative Filtering (2016, methodology): “There are other MF-based CF methods such as (Rennie & Srebro, 2005; Mackey et al., 2011).”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “Although one-shot or divide-and-conquer communication schemes have been explored in traditional data center settings [29], the behavior of these methods is not well understood in massive and statistical heterogeneous networks.”
Distributed Robust Learning (2014, methodology): “Previous divide-and-conquer distributed learning works [18, 17, 13] commonly merge the k separate estimations by taking their average, i.e. , However, the above average is fragile to outliers [11] with zero breakdown point.”
Stat260/cs294: Randomized Algorithms for Matrices and Data (methodology): “; and Random Projections Today, we will use the concentration results of the last few classes to go back and make statements about approximating the product of two matrices; and we will also describe an important topic we will spend a great deal more time on, i.e., random projections and…”
A Split-and-Conquer Approach for Analysis of Extraordinarily Large Data (2014, methodology): “Mackey, Talwalkar, and Jordan (2011) propose a divide-and-conquer method for matrix factorization, that partitions a large-scale matrix into sub-matrices.”
Local Low-Rank Matrix Approximation (2013, methodology): “In summary, we conclude that (1) LLORMA outperforms SVD and other state-of-the-art methods including the Netflix winner and DFC, (2) LLORMA can achieve high performance with a low-rank and only a few anchor points, and (3) LLORMA works well with either a small or a large train set.”
Supervised Neighborhoods for Distributed Nonparametric Regression (2016, background): “Both machine learning and computer systems researchers are actively exploring techniques to efficiently embed these learning approaches into parallel and distributed computing frameworks, e.g., [1]–[5].”
Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset (2015, methodology): “Furthermore, Sprechman et al.[353] developed an online version of their SPCP via fast trainable encoders.”
TuPAQ: An Efficient Planner for Large-scale Predictive Analytic Queries (2015, background): “[7, 40, 36] Unfortunately, the application of supervised learning techniques to a new input dataset is computationally demanding and technically challenging.”
Revisiting the Nystrom Method for Improved Large-scale Machine Learning (2013, methodology): “by a low-rank matrix [64, 63], the Nyström extension has been used in a large body of subsequent work. For example, applications of the Nyström method to large-scale machine learning problems include [58, 37, 38, 44] and [69, 41, 68], and applications in statistics and signal processing include [53,”
MLbase: A Distributed Machine-learning System (2013, unknown): “These primitives currently include efficient implementations of gradient and stochastic gradient descent, mini-batch extensions of map-reduce that naturally support divide-and-conquer approaches such as [21], and graph-parallel primitives as in GraphLab [20].”