Generalization Bounds for Inductive Matrix Completion in Low-noise Settings
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Generalization BoundsMatrix CompletionSimilar Papers 제목 키워드 기반
Noisy Inductive Matrix Completion Under Sparse Factor Models
Inductive Matrix Completion (IMC) is an important class of matrix completion problems that allows direct inclusion of available features to enhance estimation capabilities. These models have found applications in persona…
Dictionary LearningMatrix CompletionRecommendation SystemsFine-grained Generalization Analysis of Inductive Matrix Completion
In this paper, we bridge the gap between the state-of-the-art theoretical results for matrix completion with the nuclear norm and their equivalent in \textit{inductive matrix completion}: (1) In the distribution-free set…
Matrix CompletionOnline Matrix Completion with Side Information
We give an online algorithm and prove novel mistake and regret bounds for online binary matrix completion with side information. The mistake bounds we prove are of the form $\tilde{O}(D/\gamma^2)$. The term $1/\gamma^2$ …
Matrix CompletionProvable Inductive Matrix Completion
Consider a movie recommendation system where apart from the ratings information, side information such as user's age or movie's genre is also available. Unlike standard matrix completion, in this setting one should be ab…
Matrix CompletionMissing LabelsMovie RecommendationOpen Problem: Separating Geometric and Algorithmic Compression via Cayley-Table Completion
Modern statistical learning theory and deep learning characterize generalization primarily in terms of continuous capacity control (e.g., norm-based regularization, margin maximization, low-rank bias). While highly succe…