技术摘要：含噪声与不精确侧信息的样本高效归纳式矩阵补全

1. 问题表述

本文探讨了归纳式矩阵补全（IMC），这是低秩矩阵补全的一种变体，其中目标矩阵的行空间和列空间具有先验信息。其目标是从部分含噪声观测中恢复一个秩为 $r$ 的真实低秩矩阵 $L^\star \in \mathbb{R}^{n_1 \times n_2}$。

观测模型由下式给出：
$$M = P_\Omega(L^\star + E)$$
其中 $P_\Omega$ 是投影到观测条目集合 $\Omega$ 上的算子（以概率 $p$ 独立采样），$E$ 是加性噪声矩阵。

在 IMC 中，用户获得侧信息矩阵 $X \in \mathbb{R}^{n_1 \times a_1}$ 和 $Y \in \mathbb{R}^{n_2 \times a_2}$，它们编码了关于 $L^\star$ 列空间和行空间的先验知识。

• 精确侧信息：真实的列空间和行空间分别是 $X$ 和 $Y$ 列向量的子空间。这使得 $L^\star$ 可参数化为 $L^\star = X Z^\star Y^\top$，其中 $Z^\star \in \mathbb{R}^{a_1 \times a_2}$ 是一个低维核心矩阵。
• 不精确侧信息：侧信息子空间仅与真实空间近似对齐，其特征由偏差参数 $\delta$ 描述（通过主角度测量）。

差距： prior 工作表明，在无噪声设置下，具有精确侧信息的 IMC 能显著降低样本复杂度（其规模取决于特征维度 $a_1, a_2$ 而非环境维度 $n_1, n_2$）。然而，在含噪声设置中，现有方法要么无法提供精确的误差保证，要么需要与环境维度相匹配的样本复杂度，从而抵消了侧信息的优势。此外，大多数理论保证假设侧信息是精确的，这往往不符合实际。

2. 方法论

作者提出了一种带有谱初始化的**投影梯度下降（PGD）**算法，以解决非凸 IMC 问题。

算法概述

1. 参数化：算法不直接估计 $L^\star$，而是估计因子 $A \in \mathbb{R}^{a_1 \times r}$ 和 $B \in \mathbb{R}^{a_2 \times r}$，使得 $Z \approx AB^\top$。重构结果为 $\hat{L} = XAB^\top Y^\top$。
2. 目标函数：算法最小化一个非凸损失函数：
   $$f(A, B) = \frac{1}{2p} \| P_\Omega(XAB^\top Y^\top - M) \|_F^2 + \frac{1}{16} \| A^\top A - B^\top B \|_F^2$$
   第二项作为平衡正则化项，用于保持 $A$ 和 $B$ 的奇异值接近。
3. 初始化：使用 $\frac{1}{p} X^\top P_\Omega(M) Y$ 的前 $r$ 个奇异值分解（SVD）进行谱初始化，以提供一个接近真实值的起点。
4. 优化：算法执行梯度下降步骤，随后投影到一个强制非相干性（有界 $\ell_{2,\infty}$ 范数）的约束集上。
   • 注：作者通过经验观察到，该投影步骤在实践中通常不活跃，但对于理论证明至关重要。

处理不精确侧信息

针对不精确设置，作者提出了一种插值方案。他们引入一个惩罚目标函数，在标准矩阵补全（忽略侧信息）和 IMC（强制侧信息对齐）之间进行插值：
$$\tilde{f}(\tilde{A}, \tilde{B}) = \frac{1}{2p} \| P_\Omega(\tilde{A}\tilde{B}^\top - M) \|_F^2 + \frac{1}{16} \| \tilde{A}^\top \tilde{A} - \tilde{B}^\top \tilde{B} \|_F^2 + \lambda \| \tilde{A}\tilde{B}^\top - XX^\top \tilde{A}\tilde{B}^\top YY^\top \|_F^2$$
其中，$\lambda$ 控制侧信息惩罚的强度。较小的 $\lambda$ 优先考虑数据拟合（对误设具有鲁棒性），而较大的 $\lambda$ 则强制归纳结构（在样本量较少时更高效）。

3. 主要贡献与理论结果

A. 含噪声的精确侧信息

本文证明，含噪声的 IMC 可以实现降低的样本复杂度，该复杂度由有效问题规模（$a_1, a_2$）而非环境维度（$n_1, n_2$）决定。

• 样本复杂度：算法在 $n_1 n_2 p \gtrsim a \cdot \text{poly}(r, \log n)$ 条件下成功，其中 $a = \max(a_1, a_2)$。这与无噪声 IMC 的降低复杂度相匹配。
• 估计误差：估计误差的规模如下：
  $$\| \hat{L} - L^\star \|_F \lesssim \text{噪声水平} \times \sqrt{\frac{a}{p}}$$
  这统一了无噪声 IMC 的降低样本复杂度与含噪声矩阵补全的精确误差保证。
• 技术核心：证明依赖于在降低的样本复杂度下为 IMC 损失函数建立正则性条件。该条件确保损失景观在真实值附近具有有利的局部几何结构（类似强凸性），从而实现线性收敛。

B. 不精确侧信息

作者将分析扩展到侧信息不完美（$\delta > 0$）的情况。

• 样本复杂度：即使侧信息不精确，降低的样本复杂度要求（$n_1 n_2 p \gtrsim a \cdot \text{poly}(r, \log n)$）仍然充分。
• 误差界：估计误差随不精确度 $\delta$ 优雅地退化。具体而言，误差包含一个与 $\delta$ 成正比的额外项，且被证明是阶最优的。
• 插值：提出的惩罚公式允许该方法对冲误设风险。经验结果表明，在样本量有限但侧信息含噪声的区间内，通过交叉验证选择中间值的 $\lambda$ 可以优于纯 IMC 和标准矩阵补全。

4. 实验验证

作者通过以下方式验证了其理论：

1. 合成模拟：
   • 精确侧信息：在显著较低的采样概率（$p$）下，IMC 实现了精确恢复，且估计误差低于标准矩阵补全。
   • 不精确侧信息：在低样本量下，IMC 优于标准 MC，但随着 $p$ 增加，其误差趋于平稳（受 $\delta$ 限制），而标准 MC 继续改善。
   • 插值：插值方案成功平衡了这些权衡，当 $\lambda$ 经过调整时，其误差低于任一极端情况。
2. 真实世界数据（MovieLens 100K）：
   • 利用用户人口统计信息和电影类型作为侧信息，当训练集较小时（例如 $m=5000$），IMC 显著优于非归纳式矩阵补全。
   • 随着样本量增加，非归纳式方法最终赶上，这与理论预测一致，即 IMC 的优势在低样本区间最为显著。

5. 意义与主张

本文声称填补了归纳式矩阵补全理论理解中的一个重大空白：

1. 统一性：它统一了无噪声 IMC 的降低样本复杂度保证与含噪声矩阵补全的精确误差保证，证明了即使在存在噪声的情况下，侧信息仍然有益。
2. 鲁棒性：它首次为具有不精确侧信息的 IMC 提供了理论保证，表明样本效率得以保留，且误差由误设水平控制。
3. 算法效率：通过使用非凸投影梯度下降方法，本文提供了一种计算高效的方法，避免了凸松弛（如核范数最小化）的高计算成本，同时保持了统计最优性。

作者指出，虽然投影步骤对于他们的证明在理论上是必要的，但在他们的实验中经验上是冗余的，这留下了是否可以为未投影的梯度下降证明可比保证的问题，作为一个开放的研究方向。他们还强调了逐元素保证和部分侧信息作为未来的研究方向。