技術要約：行列補完のための二方向最近傍法（Two-Sided Nearest Neighbors）

問題設定

本論文は、潜在因子モデルの文脈における行列補完問題を取り扱う。具体的には、基礎となる真の行列 $\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]$ を持つヘルダー関数クラスに属する。この設定は、標準的な双線形モデル（$f(u,v) = \langle u, v \rangle$）を、非パラメトリックで、潜在的に（リプシッツ連続よりも）滑らかさが低い（$\lambda < 1$）関数へと一般化したものである。

解決すべき重要な課題は、MNAR（Missing Not At Random：非ランダム欠測）レジームである。欠測がデータとは独立しているMCAR（Missing Completely At Random：完全ランダム欠測）とは異なり、MNARでは、あるエントリーが観測される確率が、観測されない潜在因子に依存すると仮定する。さらに、著者らは、エントリが決定論的に欠測している（特定の構成において欠測確率が0である）シナリオも検討している。これは、ユーザーの好みが可視性を左右するレコメンデーションエンジンなどの実世界のシステムにおいて一般的に見られる現象である。

目的は、潜在因子 $U, V$ や関数 $f$ の事前知識なしに、真の $\theta_{i,j}$ を推定し、ミニマックス最適レートを達成することである。

手法：二方向最近傍法（TS-NN）

著者らは、**二方向最近傍法（Two-Sided Nearest Neighbor: TS-NN）**を提案している。その核心となる直感は、観測されたデータを用いて行と列の潜在的な距離を近似し、その結果得られる近傍におけるアウトカムを平均化することである。

1. 距離推定: 潜在関数 $f$ は未知であるため、アルゴリズムは、行因子の平方 $L_2$ 距離（$d^2_{row}$）と列因子の平方 $L_2$ 距離（$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$ にアクセスできる「オラクル」アルゴリズムのレートと一致する。
• MNARレジーム: 規則性条件（Assumption 6）が満たされる限り、この最適性がMNAR条件下でも保持されることを本論文は確立している。この条件は、行と列の近傍の交差部分における観測エントリーの数が、近傍サイズの積に対して十分に大きいことを要求するものであり、たとえ一部のエントリが決定論的に欠測していても成立する。

2. 決定論的欠測への堅牢性

TS-NNが、行列の大部分が決定論的に欠測している（例：特定のユーザー・アイテムのペアに対して50%のエントリが欠測している）場合でも、非自明な誤差率をもたらすことを示すことは、重要な貢献である。理論的境界は、近傍内での「実効的な」欠測確率がゼロから離れてさえいれば、ミニマックスレートが維持されることを示している。

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. 合成シミュレーション:

   • 実験では、Row-NN、Column-NN、Doubly-Robust NN (DR-NN)、Universal Singular Value Thresholding (USVT)、SoftImpute などのベースラインと比較して TS-NN を評価している。
   • 結果: TS-NN は一貫して最高の MSE 減衰レートを達成し、MCAR 設定では、真の潜在因子を知っている Oracle-TS-NN と一致する。極めて重要な点として、TS-NN は、DR-NN のような他の手法が著しく低下する MNAR 設定においても、堅牢な性能を維持している。
   • 滑らかさへの適応性: TS-NN の経験的な減衰レートは、滑らかさパラメータ $\lambda$ が変化するにつれて、理論的な予測と一致している。
   • 信頼区間: 構築された信頼区間は、中程度のサンプルサイズにおいて、ほぼ公称カバレッジ（95%）を達成しており、漸近正規性の結果を裏付けている。

2. 実世界でのケーススタディ (HeartSteps):

   • 本手法は、37人のユーザーと6週間にわたる意思決定ポイントを含むマイクロランダム化試験である HeartSteps モバイルヘルスデータセットに適用されている。
   • このデータセットは MNAR の特性を有している（ユーザーは約20%の時間、利用不可であり、通知は利用可能な場合にのみ送信される）。
   • 結果: 5分割交差検証の設定において、TS-NN は、反事実的な歩数数を推定する際、片方向 NN 変種（Row-NN, Col-NN）や "All-Row-NN" のようなベースラインよりも優れた性能を示し、決定論的欠測を扱う上での二方向アプローチの実用的な有用性を実証した。

意義と主張

本論文は、非パラメトリック行列補完と MNAR 欠測データ分析という 2 つの異なる研究領域を統合することを主張している。

• 初の解析: 著者らは、未知の行および列の潜在因子、非線形なヘルダー連続関数（$\lambda < 1$）、および MNAR 欠測を同時に扱う手法の理論的解析としては、これが初であると述べている。
• オラクル等価性: 潜在因子の知識の欠如が収束レートにペナルティを与えないことを示しており、中間的なレジームにおいて TS-NN は $U$ および $V$ に関する完全な知識を持つオラクルと同等の性能を発揮する。
• 堅牢性: 本手法は決定論的な欠測パターンに対して堅牢であることが示されており、これは標準的な行列補完の文献ではしばしば無視されるが、レコメンデーションシステムのような実世界のアプリケーションにおいて極めて重要である。

著者らは、TS-NN が、複雑で非平滑かつ非ランダムな欠測環境における行列補完のための、理論的に裏付けられた、適応的かつ堅牢なソリューションを提供すると結論付けている。