Robust Noisy Inductive Matrix Completion with Local Linear Convergence

We study noisy inductive matrix completion (IMC) in the presence of heavy-tailed and possibly asymmetric noise, where the goal is to recover a rank-$r$ matrix of ambient dimension $d$ given $n$ features as side prior information. So far, there has been a lack of theoretical understanding of the statistical estimation error in noisy IMC, let alone theory under heavy-tailed noise. We first develop an efficient two-stage nonconvex algorithm, called RGDIMC, via robust gradient descent with spectral initialization and feature-aware matrix factorization, based on an adaptive Huber loss to accommodate heavy-tailed noise. We prove that RGDIMC converges locally at a linear rate with sample complexity depending only linearly on $n$ (up to $\log n$) and logarithmically on $d$, and achieves the minimax-optimal statistical error rate $O_p(\sigma\sqrt{dr/p})$ under merely a bounded second-moment condition on the noise, where $r$ is the rank of the unknown core matrix. The theoretical results are strongly supported by extensive experiments.