  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.
