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

2025/11/17 by Antoine Ledent, Ledent, Antoine, Mun Chong Soo +2
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.2511.13049

openalex publication_date 2025/11/17 · openalex created_date 2025/11/19 · openalex updated_date 2026/07/28

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 share a common subspace. We assume that a large amount M of 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 \widetildeO(√((nd)/(M))) and \widetildeO(√((dr)/(N))) 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.

Citations

• Conv4Rec: A 1-by-1 Convolutional AutoEncoder for User Profiling through Joint Analysis of Implicit and Explicit Feedbacks
• Generalization Analysis for Supervised Contrastive Representation Learning under Non-IID Settings
• Optimal Transfer Learning for Missing Not-at-Random Matrix Completion
• LEARNER: A Transfer Learning Method for Low-Rank Matrix Estimation
• Generalization Analysis for Contrastive Representation Learning
• Beyond Smoothness: Incorporating Low-Rank Analysis into Nonparametric\n Density Estimation
• Community Detection and Matrix Completion with Social and Item Similarity Graphs
• Missing Not at Random in Matrix Completion: The Effectiveness of Estimating Missingness Probabilities Under a Low Nuclear Norm Assumption
• Inductive Matrix Completion Based on Graph Neural Networks
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Character-level Convolutional Networks for Text Classification
• Norm-Based Capacity Control in Neural Networks
• Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares
• Exact Recovery in the Stochastic Block Model
• Learning with the Weighted Trace-norm under Arbitrary Sampling Distributions
• Matrix Factorization Techniques for Recommender Systems
• Matrix Completion With Noise
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Exact Matrix Completion via Convex Optimization

Related

• Sequential Matrix Completion
• On the Fundamental Limits of Matrix Completion: Leveraging Hierarchical Similarity Graphs
• Partial Matrix Completion
• Multiple Testing of Linear Forms for Noisy Matrix Completion
• Provable Inductive Matrix Completion