Technical Summary: Sample Efficient Inductive Matrix Completion with Noise and Inexact Side Information

1. Problem Formulation

The paper addresses Inductive Matrix Completion (IMC), a variant of low-rank matrix completion where prior information about the row and column spaces of the target matrix is available. The goal is to recover a ground-truth low-rank matrix $L^\star \in \mathbb{R}^{n_1 \times n_2}$ of rank $r$ from a subset of noisy observations.

The observation model is given by:
$$M = P_\Omega(L^\star + E)$$
where $P_\Omega$ is the projection onto a set of observed entries $\Omega$ (sampled independently with probability $p$), and $E$ is an additive noise matrix.

In IMC, the user is provided with side information matrices $X \in \mathbb{R}^{n_1 \times a_1}$ and $Y \in \mathbb{R}^{n_2 \times a_2}$, which encode prior knowledge about the column and row spaces of $L^\star$.

• Exact Side Information: The true column and row spaces are subspaces of the columns of $X$ and $Y$, respectively. This allows $L^\star$ to be parameterized as $L^\star = X Z^\star Y^\top$, where $Z^\star \in \mathbb{R}^{a_1 \times a_2}$ is a lower-dimensional core matrix.
• Inexact Side Information: The side information subspaces are only approximately aligned with the true spaces, characterized by a deviation parameter $\delta$ (measured via principal angles).

The Gap: Prior work established that IMC with exact side information in noiseless settings achieves significantly reduced sample complexity (scaling with the feature dimensions $a_1, a_2$ rather than ambient dimensions $n_1, n_2$). However, in noisy settings, existing methods either fail to provide sharp error guarantees or require sample complexity matching the ambient dimension, negating the benefits of side information. Furthermore, most theoretical guarantees assume exact side information, which is often unrealistic.

2. Methodology

The authors propose a Projected Gradient Descent (PGD) algorithm with Spectral Initialization to solve the nonconvex IMC problem.

Algorithm Overview

1. Parameterization: Instead of estimating $L^\star$ directly, the algorithm estimates factors $A \in \mathbb{R}^{a_1 \times r}$ and $B \in \mathbb{R}^{a_2 \times r}$ such that $Z \approx AB^\top$. The reconstruction is $\hat{L} = XAB^\top Y^\top$.
2. Objective Function: The algorithm minimizes a nonconvex loss function:
   $$f(A, B) = \frac{1}{2p} \| P_\Omega(XAB^\top Y^\top - M) \|_F^2 + \frac{1}{16} \| A^\top A - B^\top B \|_F^2$$
   The second term acts as a balancing regularizer to keep the singular values of $A$ and $B$ close.
3. Initialization: A spectral initialization is performed using the top-$r$ SVD of $\frac{1}{p} X^\top P_\Omega(M) Y$ to provide a starting point close to the ground truth.
4. Optimization: The algorithm performs gradient descent steps followed by a projection onto a constraint set that enforces incoherence (bounded $\ell_{2,\infty}$ norms).
   • Note: The authors observe empirically that this projection step is often inactive in practice but is crucial for the theoretical proof.

Handling Inexact Side Information

For the inexact setting, the authors propose an Interpolation Scheme. They introduce a penalized objective that interpolates between standard matrix completion (ignoring side information) and IMC (enforcing side information alignment):
$$\tilde{f}(\tilde{A}, \tilde{B}) = \frac{1}{2p} \| P_\Omega(\tilde{A}\tilde{B}^\top - M) \|_F^2 + \frac{1}{16} \| \tilde{A}^\top \tilde{A} - \tilde{B}^\top \tilde{B} \|_F^2 + \lambda \| \tilde{A}\tilde{B}^\top - XX^\top \tilde{A}\tilde{B}^\top YY^\top \|_F^2$$
Here, $\lambda$ controls the strength of the side-information penalty. Small $\lambda$ prioritizes data fit (robust to misspecification), while large $\lambda$ enforces the inductive structure (efficient for low sample sizes).

3. Key Contributions and Theoretical Results

A. Exact Side Information with Noise

The paper establishes that noisy IMC can achieve reduced sample complexity governed by the effective problem size ($a_1, a_2$) rather than the ambient dimension ($n_1, n_2$).

• Sample Complexity: The algorithm succeeds with $n_1 n_2 p \gtrsim a \cdot \text{poly}(r, \log n)$, where $a = \max(a_1, a_2)$. This matches the reduced complexity of noiseless IMC.
• Estimation Error: The estimation error scales as:
  $$\| \hat{L} - L^\star \|_F \lesssim \text{noise level} \times \sqrt{\frac{a}{p}}$$
  This unifies the reduced sample complexity of noiseless IMC with the sharp error guarantees of noisy matrix completion.
• Technical Core: The proof relies on establishing a Regularity Condition for the IMC loss function at this reduced sample complexity. This condition ensures that the loss landscape possesses favorable local geometry (strong convexity-like properties) near the ground truth, enabling linear convergence.

B. Inexact Side Information

The authors extend the analysis to cases where side information is imperfect ($\delta > 0$).

• Sample Complexity: The reduced sample complexity requirement ($n_1 n_2 p \gtrsim a \cdot \text{poly}(r, \log n)$) remains sufficient even with inexact side information.
• Error Bounds: The estimation error degrades gracefully with the inexactness $\delta$. Specifically, the error includes an additional term proportional to $\delta$, which is shown to be order-optimal.
• Interpolation: The proposed penalized formulation allows the method to hedge against misspecification. Empirical results suggest that selecting an intermediate $\lambda$ (via cross-validation) can outperform both pure IMC and standard matrix completion in regimes where sample size is limited but side information is noisy.

4. Experimental Validation

The authors validate their theory through:

1. Synthetic Simulations:
   • Exact SI: IMC achieves exact recovery and lower estimation error than standard matrix completion at significantly lower sampling probabilities ($p$).
   • Inexact SI: IMC outperforms standard MC at low sample sizes but its error plateaus as $p$ increases (limited by $\delta$), whereas standard MC continues to improve.
   • Interpolation: The interpolation scheme successfully balances these trade-offs, achieving lower error than either extreme when $\lambda$ is tuned.
2. Real-World Data (MovieLens 100K):
   • Using user demographics and movie genres as side information, IMC significantly outperforms non-inductive matrix completion when the training set is small (e.g., $m=5000$).
   • As the sample size grows, non-inductive methods eventually catch up, consistent with the theoretical prediction that IMC's advantage is most pronounced in low-sample regimes.

5. Significance and Claims

The paper claims to close a significant gap in the theoretical understanding of Inductive Matrix Completion:

1. Unification: It unifies the reduced sample complexity guarantees of noiseless IMC with the sharp error guarantees of noisy matrix completion, demonstrating that side information remains beneficial even in the presence of noise.
2. Robustness: It provides the first theoretical guarantees for IMC with inexact side information, showing that the sample efficiency is preserved and the error is controlled by the level of misspecification.
3. Algorithmic Efficiency: By using a nonconvex projected gradient descent approach, the paper offers a computationally efficient method that avoids the high computational cost of convex relaxations (like nuclear norm minimization) while maintaining statistical optimality.

The authors note that while the projection step is theoretically necessary for their proofs, it is empirically redundant in their experiments, leaving the question of whether comparable guarantees can be proven for unprojected gradient descent as an open direction. They also highlight entrywise guarantees and partial side information as future research directions.