Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow
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.
Code (1)
Tasks
Matrix CompletionSimilar Papers 제목 키워드 기반
Sparse Group Inductive Matrix Completion
We consider the problem of matrix completion with side information (\textit{inductive matrix completion}). In real-world applications many side-channel features are typically non-informative making feature selection an i…
feature selectionLow-Rank Matrix CompletionMatrix CompletionInductive Matrix Completion: No Bad Local Minima and a Fast Algorithm
The inductive matrix completion (IMC) problem is to recover a low rank matrix from few observed entries while incorporating prior knowledge about its row and column subspaces. In this work, we make three contributions to…
Matrix CompletionSample-efficient inductive matrix completion with noise and inexact side-information
Inductive matrix completion (IMC) is a variant of low-rank matrix completion that incorporates row and column side-information. In principle, it can reduce the effective dimension of the recovery problem from the ambient…
Fine-grained Generalization Analysis of Inductive Matrix Completion
In this paper, we bridge the gap between the state-of-the-art theoretical results for matrix completion with the nuclear norm and their equivalent in \textit{inductive matrix completion}: (1) In the distribution-free set…
Matrix CompletionGeneralization Bounds for Inductive Matrix Completion in Low-noise Settings
We study inductive matrix completion (matrix completion with side information) under an i.i.d. subgaussian noise assumption at a low noise regime, with uniform sampling of the entries. We obtain for the first time genera…
Generalization BoundsMatrix Completion