技术摘要：用于矩阵补全的双侧最近邻算法

问题陈述

本文在潜在因子模型的背景下探讨了矩阵补全问题，特别关注底层真实矩阵 $\Theta$ 是由作用于未知行和列潜在因子的非线性潜在函数 $f$ 生成的场景。该模型定义为：
$$\theta_{i,j} = f(u_i, v_j)$$
其中 $u_i \in \mathbb{R}^{d_1}$ 和 $v_j \in \mathbb{R}^{d_2}$ 是潜在因子，且 $f$ 属于具有光滑度参数 $\lambda \in (0, 1]$ 的 Hölder 函数类。这一设定将标准的双线性模型（其中 $f(u,v) = \langle u, v \rangle$）推广到了非参数化、可能非光滑（光滑度低于 Lipschitz）的函数。

本文解决的一个关键挑战是 非随机缺失 (MNAR) 机制。与缺失机制独立于数据的 完全随机缺失 (MCAR) 不同，MNAR 假设条目是否被观测到取决于未观测到的潜在因子。此外，作者还考虑了条目可能确定性缺失（即对于特定配置，缺失概率为 0）的情景，这在推荐引擎等现实世界系统中非常常见，其中用户偏好决定了可见性。

目标是在没有先验知识获知潜在因子 $U$、$V$ 或函数 $f$ 的情况下，估计真实值 $\theta_{i,j}$（包括已观测和缺失的条目），并达到极小极大最优速率（minimax optimal rates）。

方法论：双侧最近邻 (TS-NN)

作者提出了 双侧最近邻 (Two-Sided Nearest Neighbor, TS-NN) 算法。其核心直觉是通过观测数据来近似行和列之间的潜在距离，然后在由此产生的邻域内对结果进行平均。

1. 距离估计： 由于潜在函数 $f$ 是未知的，该算法构建了行距离（$d^2_{row}$）和列距离（$d^2_{col}$）的数据驱动代理。

   • 算法通过计算行 $i$ 与 $i'$ 在共同列上的观测条目平方差的平均值，并针对噪声方差（$2\sigma^2$）进行修正，来估计行之间的距离。
   • 类似地，列距离通过共同行进行估计。
   • 形式上，估计的行距离为：
     $$\hat{d}^2_{row}(i, i') = \frac{\sum_{j} (X_{i,j} - X_{i',j})^2 A_{i,j}A_{i',j}}{\sum_{j} A_{i,j}A_{i',j}} - 2\sigma^2$$
     （列距离也适用对称公式）。

2. 邻域构建： 使用调节参数 $\eta_{row}$ 和 $\eta_{col}$，算法定义了邻域：

   • $N_{row}(i) = \{i' : \hat{d}^2_{row}(i, i') \leq \eta^2_{row}\}$
   • $N_{col}(j) = \{j' : \hat{d}^2_{col}(j, j') \leq \eta^2_{col}\}$

3. 估计： 估计值 $\hat{\theta}_{i,j}$ 是所有满足 $i' \in N_{row}(i)$ 且 $j' \in N_{col}(j)$ 的观测条目 $X_{i',j'}$ 的平均值。

核心贡献与理论结果

1. 对光滑度的适应性与极小极大最优性

主要的理论发现是 TS-NN 能够适应 潜在函数 $f$ 的光滑度 $\lambda$。

• MCAR 机制： 在标准的 MCAR 假设下，作者证明了通过适当的调节（$\eta \propto (mn)^{-\frac{\lambda}{2\lambda + d_1 + d_2}}$），均方误差 (MSE) 能够达到非参数极小极大最优速率：
  $$\text{MSE} = O\left( (mn)^{-\frac{2\lambda}{2\lambda + d_1 + d_2}} \right)$$
  该速率与一个能够获取真实潜在因子 $U$ 和 $V$ 的“预知” (Oracle) 算法相匹配。
• MNAR 机制： 本文确立了即使在 MNAR 条件下，只要满足正则性条件（假设 6），这种最优性依然成立。该条件本质上要求行和列邻域交集中的观测条目数量相对于邻域大小的乘积而言足够大，即使存在某些确定性缺失的情况。

2. 对确定性缺失的鲁棒性

一个重要的贡献是证明了即使在大量条目确定性缺失（例如，特定的用户-物品对缺失 50% 的条目）的情况下，TS-NN 仍能产生非平凡的误差率。理论界限表明，只要“有效”缺失概率在邻域内保持远离零，极小极大速率就能得到保持。

3. 点估计保证与渐近正态性

• 点估计界限： 本文提供了单个条目 $\hat{\theta}_{i,j}$ 的非渐近点估计误差界限。这些界限相对于调节参数和矩阵维度表现出“维度诅咒”，但在聚合到总体水平（MSE）时，这种影响会消失。
• 渐近正态性： 在特定的邻域大小条件下，作者证明了点估计量具有渐近正态性：
  $$\sqrt{|N_{row,col}(i,j)|} (\hat{\theta}_{i,j} - \theta_{i,j}) \xrightarrow{d} \mathcal{N}(0, \sigma^2)$$
  这一结果使得构建有效的反事实估计置信区间成为可能。

实证结果

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

1. 合成模拟：

   • 实验将 TS-NN 与包括单侧 Row-NN、Column-NN、双重稳健 NN (DR-NN)、通用奇异值阈值法 (USVT) 和 SoftImpute 在内的基准方法进行了对比。
   • 结果： TS-NN 始终实现最佳的 MSE 衰减速率，在 MCAR 设置下与已知潜在因子的 Oracle-TS-NN 相匹配。至关重要的是，在其他方法（如 DR-NN）性能显著下降的 MNAR 设置中，TS-NN 保持了稳健的表现。
   • 光滑度适应性： TS-NN 的经验衰减速率随光滑度参数 $\lambda$ 的变化而与理论预测保持一致。
   • 置信区间： 构建的置信区间在样本量适中时达到了接近名义的覆盖率 (95%)，验证了渐近正态性的结果。

2. 真实案例研究 (HeartSteps)：

   • 该方法应用于 HeartSteps 移动健康数据集，这是一个涉及 37 名用户并在 6 周内进行决策点的微随机试验。
   • 该数据集具有 MNAR 特征（用户约 20% 的时间处于不可用状态，且仅在用户可用时才会发送通知）。
   • 结果： 在 5 折交叉验证设置中，TS-NN 在估计反事实步数方面优于单侧 NN 变体（Row-NN, Col-NN）以及像 "All-Row-NN" 这样的基准方法，展示了双侧方法在处理确定性缺失方面的实际效用。

意义与主张

本文声称统一了两个不同的研究领域：非参数矩阵补全与 MNAR 缺失数据分析。

• 首创性分析： 作者指出，这是第一个同时处理未知行和列潜在因子、非线性 Hölder 连续函数（$\lambda < 1$）以及 MNAR 缺失情况的理论分析。
• 预知等价性 (Oracle Equivalence)： 该工作证明了对潜在因子的缺乏知识并不会惩罚收敛速率；在中间阶段，TS-NN 的表现与拥有完整 $U$ 和 $V$ 知识的 Oracle 算法一样出色。
• 鲁棒性： 研究表明，该方法对确定性缺失模式具有鲁棒性，而这一特征在标准矩阵补全文献中经常被忽略，但在推荐系统等现实应用中至关重要。

作者总结道，TS-NN 为复杂、非光滑且非随机缺失环境下的矩阵补全提供了一个具有理论依据、具备适应性且稳健的解决方案。