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

MAKE IMPACT

Ledent, Antoine , Soo Mun Chong , Hieu, Nong Minh · YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2511.13049

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.

Type

preprint

Landing Page

https://doi.org/10.48550/arxiv.2511.13049

OA Status

green

OpenAlex ID

https://openalex.org/W7106014889

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W7106014889

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2511.13049

Digital Object Identifier

Title

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

Work title

Type

preprint

OpenAlex work type

Publication year

2025

Year of publication

Publication date

2025-11-17

Full publication date if available

Authors

Ledent, Antoine, Soo Mun Chong, Hieu, Nong Minh

List of authors in order

Landing page

https://doi.org/10.48550/arxiv.2511.13049

Publisher landing page

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://doi.org/10.48550/arxiv.2511.13049

Direct OA link when available

Concepts

MovieLens, Generalization, Matrix completion, Rank (graph theory), Matrix (chemical analysis), Subspace topology, Scaling, Computer science, Recommender system, Algorithm, Distribution (mathematics), Sampling (signal processing), Synthetic data, Ground truth, Mathematics, Low-rank approximation, Upper and lower bounds, Sparse matrix, Matrix decomposition, Data Matrix, Mathematical optimization, Applied mathematics, Collaborative filtering, Discrete mathematics, Orthogonality, Probability distribution

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Full payload