Sample efficient inductive matrix completion with noise and inexact side information

Yuepeng Yang, Cong Ma · 2026

Read Sample efficient inductive matrix completion with noise and inexact side information by Yuepeng Yang, Cong Ma (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-17189.txt.

Introduction

Yang and Ma close a gap in noisy inductive matrix completion, where side information about rows and columns should shrink the problem but prior guarantees did not deliver in noise. They analyze projected gradient descent with spectral start and prove linear convergence and stable recovery at sample sizes set by side-information dimension, not matrix size. The analysis extends to imperfect side information, and a penalized blend balances efficiency against robustness.

Catalog record

CREATORYuepeng Yang, Cong Ma
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE132648
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.17189

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sample efficient inductive matrix completion with noise and inexact side information Yuepeng Yang, Cong Ma Abstract Low-rank matrix completion is a widely studied problem with many variants. Inductive matrix completion (IMC) incorporates row and column side information to significantly narrow the search space. Prior work falls into two regimes: methods that exploit this structure to achieve reduced sample complexity but only in noiseless settings, and methods that handle noise but require sample complexity matching the ambient matrix dimension—forfeiting the sample efficiency that side information should provide. In this paper, we close this gap by studying noisy IMC with a nonconvex projected gradient descent algorithm with spectral initialization. Our main technical contribution is establishing a regularity condition for the IMC loss function that holds at the reduced sample complexity determined by the effective problem size—scaling with the side information dimension a a rather than the ambient dimension n n . This directly yields linear convergence and an estimation error that both depend only on the effective problem size rather than the ambient matrix dimension. We further extend our analysis to the inexact side information setting, demonstrating that the reduced sample complexity is maintained and the estimation error is order-optimal with respect to the inexactness of the side information. Extensive simulations and real-world experiments on the MovieLens dataset validate our theoretical findings. 1 Introduction Low-rank matrix completion is a fundamental problem in high-dimensional statistics and machine learning. We consider a rank- r ground-truth matrix \bm{L}^{\star}\in\mathbb{R}^{n_{1}\times n_{2}} corrupted by an additive noise matrix \bm{E}\in\mathbb{R}^{n_{1}\times n_{2}} , where each entry in [n_{1}]\times[n_{2}] is observed independently with probability p . Let \Omega denote the set of observed entries. Given the observed matrix \bm{M}=\mathcal{P}_{\Omega}(\bm{L}^{\star}+\bm{E}), (1) the goal is to estimate \bm{L}^{\star} . This problem is now well understood in several canonical regimes. Let n denote the larger of n_{1} and n_{2} . Prior work shows that with \widetilde{O}(nr) observed entries, one can achieve exact recovery in the noiseless setting when \bm{E}=\bm{0} [ 3 , 26 ] and near-optimal estimation error in the noisy setting [ 5 , 9 ] . In the vanilla matrix completion problem, the only constraint on \bm{L}^{\star} is that it is low rank. In some settings, prior information on the column space and row space of \bm{L}^{\star} is available. Consider the case where we are given two orthonormal matrices \bm{X}\in\mathbb{R}^{n_{1}\times a_{1}} and \bm{Y}\in\mathbb{R}^{n_{2}\times a_{2}} which are called side information matrices. As suggested by their names, the matrix \bm{X} contains information for the column space of \bm{L}^{\star} and \bm{Y} contains information for the row space of \bm{L}^{\star} . In the case with exact side information, we can rewrite \bm{L}^{\star} as \bm{X}\bm{Z}^{\star}\bm{Y}^{\top} for some rank- r matrix \bm{Z}^{\star}\in\mathbb{R}^{a_{1}\times a_{2}} and the observed matrix as \bm{M}=\mathcal{P}_{\Omega}(\bm{X}\bm{Z}^{\star}\bm{Y}^{\top}+\bm{E}). (2) The goal now is to recover the matrix \bm{L}^{\star}=\bm{X}\bm{Z}^{\star}\bm{Y}^{\top} and this problem is sometimes called inductive matrix completion (IMC) or subspace-constrained matrix completion. Since the unknown matrix is now parameterized by the smaller core matrix \bm{Z}^{\star}\in\mathbb{R}^{a_{1}\times a_{2}} , one expects the effective problem size to be governed by the feature dimensions a_{1},a_{2} rather than the ambient dimensions n_{1},n_{2} . For comparison, we refer to ( 1 ) as the non-inductive matrix completion problem. Such side information is available in practice in various problems. IMC and other models using side information have applications in many problems where known structure or covariates can be exploited. It is used in multi-label learning [ 30 , 14 ] , prediction for gene-disease associations [ 23 , 6 , 21 , 20 ] , recommendation systems [ 28 , 16 ] , link prediction [ 34 ] , semi-supervised clustering [ 11 , 33 , 24 ] , etc. In IMC, the restriction of the column and row spaces of \bm{L}^{\star} means that the search space in the estimation is narrowed. As a consequence, one would hope that this extra side information allows smaller sample complexity or better estimation error. Equivalently, one expects both the sample complexity and the estimation error to be governed by the effective problem size induced by the side information, rather than by the ambient matrix dimension. Several works have explored this topic. On the one hand, [ 7 , 30 ] consider the noiseless setting when \bm{E}=\bm{0} with nuclear norm minimization. They obtain exact recovery with significantly fewer samples required than non-inductive matrix completion, with the sample complexity governed by the lower-dimensional side-information structure. On the other hand, [ 4 ] studies the noisy setting with \bm{E}\neq\bm{0} and proves a sharp estimation error guarantee, but with a sample complexity requirement at the same scale as ordinary matrix completion. Prior theory leaves a clear gap: noiseless IMC enjoys reduced sample complexity, while noisy IMC retains sharp error guarantees only at the larger sample size required in the non-inductive problem. It is therefore natural to ask whether these two types of results can be unified. This leads to the following central question: Can one estimate \bm{L}^{\star} in the presence of noise \bm{E} using a sample size below that required for ordinary matrix completion? In Theorem 1 , we resolve this question affirmatively. We show that one can retain the reduced inductive sample complexity from [ 7 , 30 ] while simultaneously matching the noisy estimation guarantee of [ 4 ] . The main technical ingredient is a regularity condition for the IMC loss function that holds at the scale of this effective problem size. In addition to the sub-optimal sample complexity in the noisy setting, a major limitation of some prior works [ 7 , 30 ] on IMC is that they require the side information to be exact, meaning that the provided side-information subspaces exactly contain the true row and column spaces. This can be restrictive in practice. This raises a second question: Can one still estimate \bm{L}^{\star} with reduced sample complexity when the side information is inexact? In Theorem 2 , we give a positive answer. We propose a way to quantify the level of inexactness of the side information via principal angles between the true and observed side-information subspaces, and show that it is possible to estimate \bm{X}\bm{Z}^{\star}\bm{Y}^{\top} with the same sample complexity requirement as in Theorem 1 . Moreover, we show that the estimation error is order-optimal with respect to the level of inexactness. 1.1 Our Contributions We summarize our main contributions as follows. Exact side information: reduced sample complexity with noisy guarantees. In Theorem 1 , we show that projected gradient descent with spectral initialization succeeds with sample complexity 1 1 1 Here we denote a=\max(a_{1},a_{2}) and n=\max(n_{1},n_{2}) for simplicity. n_{1}n_{2}p\gtrsim a\,\mathrm{poly}(r,\log n). Moreover, after linear convergence, the estimation error obeys \|\widehat{\bm{L}}-\bm{L}^{\star}\|_{\mathrm{F}}\lesssim\text{noise level}\times\sqrt{\frac{a}{p}}, up to logarithmic and conditioning factors. In comparison, in standard matrix completion without side information, one typically requires n_{1}n_{2}p\gtrsim n\,\mathrm{poly}(r,\log n) and obtains noisy estimation error of order \|\widehat{\bm{L}}-\bm{L}^{\star}\|_{\mathrm{F}}\lesssim\text{noise level}\times\sqrt{n/p} [ 5 , 9 ] . Thus Theorem 1 replaces the ambient dimension n by the effective dimension a in both the sample complexity and the noisy estimation error. This unifies the reduced-sample guarantees of noiseless IMC [ 30 , 7 ] with the sharp noisy estimation guarantees known for larger sample sizes [ 4 ] . The key technical step is to overcome the hurdle of the mismatch between the side

Read the complete text