mlsanityData to 7 Oct 2026

Generalization Bounds for Inductive Matrix Completion in Low-noise Settings

arXiv 2212.08339 ↗First posted 16 Dec 2022cs.LG stat.MLcited by 2

Not on the map. Why?

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.

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

Builds on

19 of 59 references.

References · 19

  1. 2019Embarrassingly Shallow Autoencoders for Sparse Datacited by 93
  2. 2019Inductive Matrix Completion Based on Graph Neural Networkscited by 85
  3. 2019Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimizationcited by 58
  4. 2013Provable Inductive Matrix Completioncited by 31
  5. 2013Incoherence-Optimal Matrix Completioncited by 27
  6. 2020Towards Open-World Recommendation: An Inductive Model-based Collaborative Filtering Approachcited by 20
  7. 2013Matrix Completion via Max-Norm Constrained Optimizationcited by 18
  8. 2020Low-rank Characteristic Tensor Density Estimation Part I: Foundationscited by 15
  9. 2019Learning Mixtures of Smooth Product Distributions: Identifiability and Algorithmcited by 14
  10. 2021Inductive Matrix Completion Using Graph Autoencodercited by 9
  11. 2018Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flowcited by 8
  12. 2021Low-rank Characteristic Tensor Density Estimation Part II: Compression and Latent Density Estimationcited by 8
7 more
  1. 2022Beyond Smoothness: Incorporating Low-Rank Analysis into Nonparametric Density Estimationcited by 8
  2. 2013Nonparametric Estimation of Multi-View Latent Variable Modelscited by 7
  3. 2021Matrix Completion with Model-free Weightingcited by 6
  4. 2020Orthogonal Inductive Matrix Completioncited by 5
  5. 2020Improving Nonparametric Density Estimation with Tensor Decompositionscited by 4
  6. 2019Online Matrix Completion with Side Informationcited by 3
  7. 2019Generalization error bounds for kernel matrix completion and extrapolationcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025Generalization Bounds for Semi-supervised Matrix Completion with Distributional Side Informationcited by 0
  2. 2026Sample-efficient inductive matrix completion with noise and inexact side-informationcited by 0