# Generalization Bounds for Inductive Matrix Completion in Low-noise Settings

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 59 references that are in the map.
- First posted on arXiv 16 Dec 2022.

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

- [Embarrassingly Shallow Autoencoders for Sparse Data](https://mlsanity.com/paper/1905.03375/) (2019)
- [Inductive Matrix Completion Based on Graph Neural Networks](https://mlsanity.com/paper/1904.12058/) (2019)
- [Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization](https://mlsanity.com/paper/1902.07698/) (2019)
- [Provable Inductive Matrix Completion](https://mlsanity.com/paper/1306.0626/) (2013)
- [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (2013)
- [Towards Open-World Recommendation: An Inductive Model-based Collaborative Filtering Approach](https://mlsanity.com/paper/2007.04833/) (2020)
- [Matrix Completion via Max-Norm Constrained Optimization](https://mlsanity.com/paper/1303.0341/) (2013)
- [Low-rank Characteristic Tensor Density Estimation Part I: Foundations](https://mlsanity.com/paper/2008.12315/) (2020)
- [Learning Mixtures of Smooth Product Distributions: Identifiability and Algorithm](https://mlsanity.com/paper/1904.01156/) (2019)
- [Inductive Matrix Completion Using Graph Autoencoder](https://mlsanity.com/paper/2108.11124/) (2021)
- [Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow](https://mlsanity.com/paper/1803.01233/) (2018)
- [Low-rank Characteristic Tensor Density Estimation Part II: Compression and Latent Density Estimation](https://mlsanity.com/paper/2106.10591/) (2021)
- [Beyond Smoothness: Incorporating Low-Rank Analysis into Nonparametric Density Estimation](https://mlsanity.com/paper/2204.00930/) (2022)
- [Nonparametric Estimation of Multi-View Latent Variable Models](https://mlsanity.com/paper/1311.3287/) (2013)
- [Matrix Completion with Model-free Weighting](https://mlsanity.com/paper/2106.05850/) (2021)
- [Orthogonal Inductive Matrix Completion](https://mlsanity.com/paper/2004.01653/) (2020)
- [Improving Nonparametric Density Estimation with Tensor Decompositions](https://mlsanity.com/paper/2010.02425/) (2020)
- [Online Matrix Completion with Side Information](https://mlsanity.com/paper/1906.07255/) (2019)
- [Generalization error bounds for kernel matrix completion and extrapolation](https://mlsanity.com/paper/1906.08770/) (2019)

## Built on by (most cited first, 2 of 2)

- [Generalization Bounds for Semi-supervised Matrix Completion with Distributional Side Information](https://mlsanity.com/paper/2511.13049/) (2025)
- [Sample-efficient inductive matrix completion with noise and inexact side-information](https://mlsanity.com/paper/2605.17189/) (2026)

## Abstract (arXiv)

We study inductive matrix completion (matrix completion with side information) under an i.i.d. subgaussian noise assumption at a low noise regime, with uniform sampling of the entries. We obtain for the first time generalization bounds with the following three properties: (1) they scale like the standard deviation of the noise and in particular approach zero in the exact recovery case; (2) even in the presence of noise, they converge to zero when the sample size approaches infinity; and (3) for a fixed dimension of the side information, they only have a logarithmic dependence on the size of the matrix. Differently from many works in approximate recovery, we present results both for bounded Lipschitz losses and for the absolute loss, with the latter relying on Talagrand-type inequalities. The proofs create a bridge between two approaches to the theoretical analysis of matrix completion, since they consist in a combination of techniques from both the exact recovery literature and the approximate recovery literature.