New Algorithm Improves Sample Efficiency in Inductive Matrix Completion with Noisy Data

A new paper posted to arXiv addresses a longstanding gap in the theory of inductive matrix completion (IMC), a technique that uses row and column side-information to reduce the effective dimensionality of matrix recovery problems. While IMC has long promised sample complexity governed by the side-information feature dimension rather than the full matrix size, existing guarantees broke down in noisy settings, requiring sample sizes comparable to ordinary matrix completion. The authors analyze a nonconvex projected gradient descent algorithm with spectral initialization and prove it achieves linear convergence and stable recovery at the reduced sample complexity even under noise. A key technical contribution is establishing a local regularity condition for the IMC loss function that holds at this smaller sample size despite a mismatch between observation patterns and side-information subspaces. The paper further extends results to inexact side-information, showing that estimation error degrades gracefully and optimally with the degree of subspace misspecification. To balance sample efficiency against robustness to imperfect side-information, the authors also propose a penalized interpolation between IMC and standard matrix completion. Experiments on the MovieLens dataset and simulations support the theoretical results and demonstrate practical benefits in low-sample regimes.