Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow

Abstract

We revisit the inductive matrix completion problem that aims to recover a rank-$r$ matrix with ambient dimension $d$ given $n$ features as the side prior information. The goal is to make use of the known $n$ features to reduce sample and computational complexities. We present and analyze a new gradient-based non-convex optimization algorithm that converges to the true underlying matrix at a linear rate with sample complexity only linearly depending on $n$ and logarithmically depending on $d$. To the best of our knowledge, all previous algorithms either have a quadratic dependency on the number of features in sample complexity or a sub-linear computational convergence rate. In addition, we provide experiments on both synthetic and real world data to demonstrate the effectiveness of our proposed algorithm.

arXiv comment35 pages, 3 figures and 2 tables

References in corpus (14)

• Global Optimality of Local Search for Low Rank Matrix Recovery
• How to Escape Saddle Points Efficiently
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• A New Approach to Collaborative Filtering: Operator Estimation with Spectral Regularization
• Incoherence-Optimal Matrix Completion
• Matrix Completion has No Spurious Local Minimum
• Provable Inductive Matrix Completion
• The Noisy Power Method: A Meta Algorithm with Applications
• Fast matrix completion without the condition number
• An Improved Gap-Dependency Analysis of the Noisy Power Method
• On the Power of Truncated SVD for General High-rank Matrix Estimation Problems
• Matrix Completion from $O(n)$ Samples in Linear Time
• Matrix Completion and Related Problems via Strong Duality

Cited by in corpus (3)

• Scalable Probabilistic Matrix Factorization with Graph-Based Priors
• Nonlinear Inductive Matrix Completion based on One-layer Neural Networks
• Generating Artificial Core Users for Interpretable Condensed Data