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

arXiv: https://arxiv.org/abs/2511.13049 · HTML: https://mlsanity.com/paper/2511.13049/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 52 references that are in the map.
- First posted on arXiv 17 Nov 2025.

## Builds on (most cited first, 20 of 20)

- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Learning from positive and unlabeled data: a survey](https://mlsanity.com/paper/1811.04820/) (2018)
- [Spectral Methods for Data Science: A Statistical Perspective](https://mlsanity.com/paper/2012.08496/) (2020)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [Inductive Matrix Completion Based on Graph Neural Networks](https://mlsanity.com/paper/1904.12058/) (2019)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Missing Not at Random in Matrix Completion: The Effectiveness of Estimating Missingness Probabilities Under a Low Nuclear Norm Assumption](https://mlsanity.com/paper/1910.12774/) (2019)
- [Generalization Analysis for Contrastive Representation Learning](https://mlsanity.com/paper/2302.12383/) (2023)
- [Machine Learning in Thermodynamics: Prediction of Activity Coefficients by Matrix Completion](https://mlsanity.com/paper/2001.10675/) (2020)
- [Low-rank Characteristic Tensor Density Estimation Part I: Foundations](https://mlsanity.com/paper/2008.12315/) (2020)
- [Beyond Smoothness: Incorporating Low-Rank Analysis into Nonparametric Density Estimation](https://mlsanity.com/paper/2204.00930/) (2022)
- [Orthogonal Inductive Matrix Completion](https://mlsanity.com/paper/2004.01653/) (2020)
- [Generalization Analysis for Supervised Contrastive Representation Learning under Non-IID Settings](https://mlsanity.com/paper/2505.04937/) (2025)
- [LEARNER: A Transfer Learning Method for Low-Rank Matrix Estimation](https://mlsanity.com/paper/2412.20605/) (2024)
- [Generalization Bounds for Inductive Matrix Completion in Low-noise Settings](https://mlsanity.com/paper/2212.08339/) (2022)
- [Optimal Transfer Learning for Missing Not-at-Random Matrix Completion](https://mlsanity.com/paper/2503.00174/) (2025)
- [Community Detection and Matrix Completion with Social and Item Similarity Graphs](https://mlsanity.com/paper/1912.04099/) (2019)
- [Conv4Rec: A 1-by-1 Convolutional AutoEncoder for User Profiling through Joint Analysis of Implicit and Explicit Feedbacks](https://mlsanity.com/paper/2509.07499/) (2025)

## Abstract (arXiv)

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 textitshare a common subspace. We assume that a large amount M of textitunlabeled 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 widetildeOleft(√fracndMright) and widetildeOleft(√fracdrNright) 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.