论文标题
低噪声设置中归纳矩阵完成的概括范围
Generalization Bounds for Inductive Matrix Completion in Low-noise Settings
论文作者
论文摘要
我们研究了I.I.D.下的归纳矩阵完成（矩阵完成）。在低噪声状态下的Subgaussian噪声假设，条目均匀采样。我们首次获得了以下三个属性的概括界限：（1）它们像噪声的标准偏差一样缩放，特别是在精确恢复情况下零尺寸； （2）即使在存在噪声的情况下，当样本量接近无穷大时，它们也会收敛到零； （3）对于侧面信息的固定尺寸，它们仅对矩阵的大小具有对数依赖性。与近似恢复中的许多作品不同，我们提出了有限的Lipschitz损失和绝对损失的结果，后者依赖于Talagrand型不平等。这些证明在两种方法之间创造了矩阵完成理论分析的方法，因为它们包括来自精确恢复文献和近似恢复文献的技术组合。
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.
