Generalization Bounds for Semi-supervised Matrix Completion with Distributional Side Information

AI summary

Overview

• Research area: Machine learning theory — generalization bounds for matrix completion, specifically a semi-supervised setting with side information, motivated by recommender systems.
• Technical level: Advanced (a theory paper built on matrix perturbation theory and classic matrix-completion generalization bounds, though the framing is explained in accessible terms).
• Scope: The paper proposes a semi-supervised matrix completion paradigm in which a low-rank sampling distribution and a low-rank ground truth matrix share a common subspace, proves generalization bounds that split additively into a subspace-estimation term and a matrix-completion term, and validates this with synthetic and real recommender-system experiments.

What This Paper Is About

The paper studies matrix completion when only a small number of entries come with labels (explicit ratings) but a much larger number of entries are observed without labels (implicit feedback, such as clicks or purchases). The central assumption is that the unknown sampling distribution over observed entries is itself low-rank and shares a common subspace with the ground truth matrix of ratings. The goal is to prove that accurate prediction is possible with very few labeled samples, provided enough unlabeled samples are available, and to show the two sources of error combine additively rather than compounding.

Key Contributions

1. A new semi-supervised learning paradigm for matrix completion. The sampling distribution P ∈ [0,1]^(m×n) over entries is assumed to share a low-rank subspace with the ground truth matrix G_ground, and the learner is given a large number M of unlabeled interactions plus a much smaller number N of labeled interactions. The paper states this is the first attempt to formalize a relationship between implicit feedback (the sampling distribution over ratings) and explicit feedback (the matrix of latent rankings).

2. Generalization bounds whose two error terms disentangle. Under incoherence, uniform marginals and bounded sampling probability assumptions, the authors prove bounds scaling as Õ(√(nd/M)) + Õ(√(dr/N)) — and, in the simplified square-case form, Õ(√([m+n]r/M) + √(dr/N)) — where d is the rank of P and r is the rank of the ground truth matrix. The bound holds simultaneously over all bounded-nuclear-norm predictors, with probability greater than 1−δ.

3. A concrete algorithm, DAMC (Distributionally Aware Matrix Completion). Unlabeled data is used to estimate the subspaces via a truncated SVD of the empirical observation matrix; the resulting side-information matrices X and Y then feed a classic Inductive Matrix Completion empirical risk minimization with a nuclear-norm constraint.

4. Synthetic and real-data validation. Synthetic experiments confirm the additive splitting of errors; experiments on Douban, ML-100K and Yelp (with most explicit ratings removed) show the method outperforming baselines that rely only on explicit ratings.

Main Findings

• Additive error decomposition: The generalization bound is a sum of four explicit terms — 2ℬ log(6/δ)/√N, plus 16ℓ𝒫²√(κ₁κ₂) log(2de) √(dr/N), plus 75𝒫ℓκκ₁ log(12[m+n]/δ) √([m+n]r/M), plus 25𝒫ℓκ* log(12[m+n]/δ) √([m+n]Γr/MN). Treating κ₁, κ₂, κ*, 𝒫*, ℓ and ℬ as constants, the error scales as Õ(√([m+n]r/M) + √(dr/N)): the first term is the subspace-estimation error from unlabeled data, the second the ground truth estimation error assuming perfect side information.

• Dramatically lower labeled-sample requirement: Recovery needs M = Õ([m+n]r) unlabeled samples and N = Õ(dr) labeled samples. By contrast, applying state-of-the-art i.i.d. matrix completion results with uniform marginals and no side information (cf. Foygel et al. 2011) would give Õ(√([m+n]r/N)) and require as many as Õ([m+n]r) labeled samples. The bound remains meaningful even when the average number of labeled samples per row or column is vanishingly small, as long as there are Õ(r) unlabeled samples in each row or column.

• Required condition on unlabeled data: Theorem 1 requires M ≥ 470 log(4[m+n]/δ) κ²𝒫²[m+n].

• Fallback without the bounded-probability assumption: If only Assumptions 1–6 hold, Γ can be replaced by the cruder estimate Γ = κ₁[m+n] derived from the uniform-marginals assumption, at the cost of requiring N ≥ (m+n)/2 labeled samples — a fixed threshold rather than a term in the error bound.

• The shared-subspace assumption is not as strong as it looks: The true rank r of G_ground can be much smaller than the subspace dimension d, since the core matrix may be low-rank. The assumptions reduce to: P is well approximated by a rank-d matrix whose row and column spaces include those of the ground truth, and the ground truth's row and column spaces are possibly strict subspaces of P's.

• Assumption 7 is the most restrictive: It caps the maximum entry of the sampling distribution at Γ/(mn). The paper notes Assumption 4 implies Assumption 7 with at least the coarse bound Γ ≤ κ₁[m+n], and gives a clustered "checkerboard" example where Γ = k/2 + 1/2 = [d+1]/2 so that the extra term is benign.

• Synthetic confirmation of Claim 1: With G, P ∈ ℝ^(200×200) and d = r = 4, over M ∈ {10000, 20000, …, 100000} and N ∈ {50, 100, 150, …, 1000}, averaged over 30 independent runs, the true generalization error correlates strongly with the disentangled estimate GAP(M, 1000) + GAP(100000, N). The range was chosen because N = 100, M = 100000 yields perfect recovery up to a high decimal point. The paper reports a strong correlation, implying the two error forms combine additively without strong interactive effects.

• Real-data confirmation of Claim 2 (RMSE, lower is better): On ML-100K, DAMC achieves 0.9068 at label fraction 0.0, versus userKNN 1.0123, IGMC 0.9281 and Soft Impute 0.9179; at fraction 0.5 DAMC reaches 0.9364 versus 1.0380/0.9824/0.9616. On Douban, DAMC achieves 0.7178 at 0.0 versus 0.7946 (userKNN), 0.7437 (IGMC) and 0.7383 (Soft Impute). On Yelp, DAMC achieves 1.0320 at 0.0 versus 1.0955 (userKNN), 1.0707 (IGMC) and 1.3888 (Soft Impute); the Yelp DAMC row in the provided content stops at the 0.7 column with value 1.0750, so the final two entries are not shown.

• Robustness to removing explicit ratings: Across the label fractions reported (0.0, 0.05, 0.1, 0.3, 0.5, 0.7, 0.9, 0.95), DAMC degrades more gracefully than Soft Impute, whose errors grow sharply at high fractions (for example, Soft Impute on Douban reaches 3.1966 at 0.95 and on Yelp reaches 3.4140).

• Relation to existing literature: The paper positions itself against the approximate-recovery branch of matrix completion (Foygel et al. 2011; Shamir and Shalev-Shwartz 2011, 2014; Ledent and Alves 2024), Inductive Matrix Completion (Xu et al. 2013; Chiang et al. 2018; Ledent et al. 2021b), Matrix-Normal/MNAR-style work (Ma and Chen 2019), and general semi-supervised learning. It argues all prior matrix completion theory assumes every observed entry is labeled.

Methodology in Plain English

The authors set up matrix completion as an i.i.d. regression problem where each sample is a (row, column) pair drawn from a categorical distribution P, plus a noisy label. They then add the semi-supervised twist: M unlabeled pairs drawn from P, and N labeled pairs drawn from the same P with noisy estimates of the true entries.

To make the problem tractable they impose a chain of assumptions: the loss is bounded and Lipschitz; P is low-rank with rank d and the ground truth lies in the same row and column spaces; those spaces are incoherent; the marginals of P are approximately uniform; P is well-conditioned (its smallest singular value is not too small relative to its norm); the side-information matrices are well-conditioned; and no single entry has too large a sampling probability.

The algorithm is straightforward in structure. First, build the empirical matrix of observed unlabeled entries, take a rank-d truncated SVD, and use the resulting factors as estimated side-information matrices X and Y (rescaled by √(m/d) and √(n/d)). Second, solve a standard Inductive Matrix Completion problem on the labeled data with a nuclear-norm constraint on the core matrix. In practice the nuclear-norm constraint is replaced by a Lagrangian with squared Frobenius penalties on the two factors, solvable with gradient methods in PyTorch.

Proving the bound means separately controlling the error introduced by estimating the subspaces from unlabeled data (drawing on matrix perturbation theory) and the error of matrix completion given the estimated subspaces (drawing on classic generalization bounds), then showing the two combine additively. The synthetic experiment tests this directly by defining a "disentangled estimate" — the gap at (M, 1000) plus the gap at (100000, N) — and correlating it against the measured generalization gap. The real-data experiment covers ML-100K, Douban and Yelp, comparing against userKNN, IGMC and Soft Impute while progressively removing explicit ratings.

Why This Matters

• For research: It is presented as the first theoretical framework that does not assume every observed sample is labeled, and the first to formalize a shared-subspace relationship between the sampling distribution (implicit feedback) and the ground truth (explicit feedback). It gives a statistically justified reason why implicit feedback should help explicit rating prediction, and it shows the two error sources can be analyzed separately rather than as one entangled quantity.

• Real-world applications (as named or implied in the paper):

  • Recommender systems, where implicit interactions (views, purchases, clicks) vastly outnumber explicit 1-to-5 star ratings.
  • Drug discovery and drug interaction prediction, where feature vectors describe molecular or chemical properties.
  • Chemical and thermal engineering, cited as an established matrix completion application area.
  • User/item clustering regimes, e.g. settings akin to stochastic block models where group memberships are unknown but structure exists.

• Industry relevance: The practical claim is that a service can get good rating predictions with far fewer explicit ratings if it collects enough implicit signals — the bound needs only Õ(dr) labeled interactions versus Õ([m+n]r) for side-information-free methods. The authors also note the conclusions align with what recent applied recommender-systems work implicitly assumes.

Future Directions

• Relaxing the bounded sampling probability assumption (Assumption 7). The paper itself calls this its most restrictive assumption; removing it, or the N ≥ (m+n)/2 fallback condition, is the clearest open problem.
• Better comparison with the MNAR literature. The paper explains that MNAR results (Ma and Chen 2019) target a uniform Frobenius error with inverse propensity weighting, impose nuclear-norm constraints on Γ rather than a genuine low-rank condition, and require a lower bound on the sampling probability that its own results avoid. Reconciling the two regimes is left open.
• Extending the semi-supervised machinery beyond regression. The paper notes that success in semi-supervised learning has mostly come from classification (contrastive learning and related methods), which do not apply cleanly to discrete input spaces like matrix completion.
• Tightness and lower bounds. The paper reports upper bounds only; whether these rates are optimal, and whether the additivity of the two error terms is fundamental or an artifact of the analysis, is not addressed.

Target Audience

Researchers in statistical learning theory and matrix completion who are interested in semi-supervised and side-information settings. It is also relevant to recommender-systems practitioners who want a theoretical justification for combining implicit and explicit feedback, and to readers already familiar with inductive matrix completion, nuclear-norm regularization, and matrix perturbation results. The paper assumes comfort with excess-risk bounds, incoherence conditions and SVD-based estimators, so it is best suited to an advanced audience.

Authors’ abstract

We study a matrix completion problem where both the ground truth $R$ matrix and the unknown sampling distribution $P$ over observed entries are low-rank matrices, and \textit{share a common subspace}. We assume that a large amount $M$ of \textit{unlabeled} data drawn from the sampling distribution $P$ is available, together with a small amount $N$ of labeled data drawn from the same distribution and noisy estimates of the corresponding ground truth entries. This setting is inspired by recommender systems scenarios where the unlabeled data corresponds to `implicit feedback' (consisting in interactions such as purchase, click, etc. ) and the labeled data corresponds to the `explicit feedback', consisting of interactions where the user has given an explicit rating to the item. Leveraging powerful results from the theory of low-rank subspace recovery, together with classic generalization bounds for matrix completion models, we show error bounds consisting of a sum of two error terms scaling as $\widetilde{O}\left(\sqrt{\frac{nd}{M}}\right)$ and $\widetilde{O}\left(\sqrt{\frac{dr}{N}}\right)$ respectively, where $d$ is the rank of $P$ and $r$ is the rank of $M$. In synthetic experiments, we confirm that the true generalization error naturally splits into independent error terms corresponding to the estimations of $P$ and and the ground truth matrix $\ground$ respectively. In real-life experiments on Douban and MovieLens with most explicit ratings removed, we demonstrate that the method can outperform baselines relying only on the explicit ratings, demonstrating that our assumptions provide a valid toy theoretical setting to study the interaction between explicit and implicit feedbacks in recommender systems.