DFacTo: Distributed Factorization of Tensors

Abstract

We present a technique for significantly speeding up Alternating Least Squares (ALS) and Gradient Descent (GD), two widely used algorithms for tensor factorization. By exploiting properties of the Khatri-Rao product, we show how to efficiently address a computationally challenging sub-step of both algorithms. Our algorithm, DFacTo, only requires two sparse matrix-vector products and is easy to parallelize. DFacTo is not only scalable but also on average 4 to 10 times faster than competing algorithms on a variety of datasets. For instance, DFacTo only takes 480 seconds on 4 machines to perform one iteration of the ALS algorithm and 1,143 seconds to perform one iteration of the GD algorithm on a 6.5 million x 2.5 million x 1.5 million dimensional tensor with 1.2 billion non-zero entries.

Under review for NIPS 2014

References in corpus (2)

• Emergence of scaling in random networks
• All-at-once Optimization for Coupled Matrix and Tensor Factorizations

Cited by in corpus (19)

• Tensor Decomposition for Signal Processing and Machine Learning
• Low-Rank Tensor Networks for Dimensionality Reduction and Large-Scale Optimization Problems: Perspectives and Challenges PART 1
• Tensor Networks for Dimensionality Reduction and Large-Scale Optimizations. Part 2 Applications and Future Perspectives
• A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization
• Federated Tensor Factorization for Computational Phenotyping
• A Unified Optimization Approach for Sparse Tensor Operations on GPUs
• Fast and Guaranteed Tensor Decomposition via Sketching
• Tensor Completion Algorithms in Big Data Analytics
• SPARTan: Scalable PARAFAC2 for Large & Sparse Data
• Efficient Nonnegative Tensor Factorization via Saturating Coordinate Descent
• Computing Eigenvalues of Large Scale Hankel Tensors
• Convex Factorization Machine for Regression
• Load-Balanced Sparse MTTKRP on GPUs
• The landscape of software for tensor computations
• Distributed Flexible Nonlinear Tensor Factorization
• Streaming Probabilistic Deep Tensor Factorization
• User-Guided Clustering in Heterogeneous Information Networks via Motif-Based Comprehensive Transcription
• Nonparametric Sparse Tensor Factorization with Hierarchical Gamma Processes
• Communication Efficient Generalized Tensor Factorization for Decentralized Healthcare Networks