Technical Summary: Two-Sided Nearest Neighbors for Matrix Completion

Problem Statement

The paper addresses the matrix completion problem within the context of latent factor models, specifically focusing on settings where the underlying ground truth matrix $\Theta$ is generated by a non-linear latent function $f$ acting on unknown row and column latent factors. The model is defined as:
$$\theta_{i,j} = f(u_i, v_j)$$
where $u_i \in \mathbb{R}^{d_1}$ and $v_j \in \mathbb{R}^{d_2}$ are latent factors, and $f$ belongs to a Hölder function class with smoothness parameter $\lambda \in (0, 1]$. This setting generalizes standard bilinear models (where $f(u,v) = \langle u, v \rangle$) to non-parametric, potentially non-smooth functions (less smooth than Lipschitz).

A critical challenge addressed is the Missing Not At Random (MNAR) regime. Unlike Missing Completely At Random (MCAR), where missingness is independent of the data, MNAR assumes that the probability of an entry being observed depends on the unobserved latent factors. Furthermore, the authors consider scenarios where entries may be deterministically missing (i.e., missing with probability 0 for specific configurations), a common occurrence in real-world systems like recommendation engines where user preferences dictate visibility.

The objective is to estimate the ground truth $\theta_{i,j}$ for both observed and missing entries without prior knowledge of the latent factors $U$ and $V$ or the function $f$, while achieving minimax optimal rates.

Methodology: Two-Sided Nearest Neighbors (TS-NN)

The authors propose the Two-Sided Nearest Neighbor (TS-NN) algorithm. The core intuition is to approximate the latent distances between rows and columns using observed data, then average outcomes over the resulting neighborhoods.

1. Distance Estimation: Since the latent function $f$ is unknown, the algorithm constructs data-driven proxies for the squared $L_2$ distances between row factors ($d^2_{row}$) and column factors ($d^2_{col}$).

   • The algorithm estimates the distance between row $i$ and $i'$ by averaging the squared differences of their observed entries across common columns, corrected for noise variance ($2\sigma^2$).
   • Similarly, column distances are estimated using common rows.
   • Formally, the estimated row distance is:
     $$\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$$
     (A symmetric formula applies for columns).

2. Neighborhood Construction: Using tuning parameters $\eta_{row}$ and $\eta_{col}$, the algorithm defines neighborhoods:

   • $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. Estimation: The estimate $\hat{\theta}_{i,j}$ is the average of all observed entries $X_{i',j'}$ where $i' \in N_{row}(i)$ and $j' \in N_{col}(j)$.

Key Contributions and Theoretical Results

1. Adaptivity to Smoothness and Minimax Optimality

The primary theoretical finding is that TS-NN adapts to the smoothness $\lambda$ of the latent function $f$.

• MCAR Regime: Under standard MCAR assumptions, the authors prove that with appropriate tuning ($\eta \propto (mn)^{-\frac{\lambda}{2\lambda + d_1 + d_2}}$), the Mean Squared Error (MSE) achieves the non-parametric minimax optimal rate:
  $$\text{MSE} = O\left( (mn)^{-\frac{2\lambda}{2\lambda + d_1 + d_2}} \right)$$
  This rate matches that of an "oracle" algorithm that has access to the true latent factors $U$ and $V$.
• MNAR Regime: The paper establishes that this optimality holds even under MNAR conditions, provided a regularity condition (Assumption 6) is met. This condition essentially requires that the number of observed entries in the intersection of row and column neighborhoods is sufficiently large relative to the product of the neighborhood sizes, even if some entries are deterministically missing.

2. Robustness to Deterministic Missingness

A significant contribution is the demonstration that TS-NN yields non-trivial error rates even when a significant portion of the matrix is deterministically missing (e.g., 50% of entries missing for specific user-item pairs). Theoretical bounds show that as long as the "effective" missingness probability within the neighborhoods remains bounded away from zero, the minimax rate is preserved.

3. Pointwise Guarantees and Asymptotic Normality

• Pointwise Bounds: The paper provides non-asymptotic pointwise error bounds for individual entries $\hat{\theta}_{i,j}$. These bounds exhibit a "curse of dimensionality" with respect to the tuning parameters and matrix dimensions, which vanishes when averaged to the population level (MSE).
• Asymptotic Normality: Under specific conditions on the neighborhood size, the authors prove that the pointwise estimator is asymptotically normal:
  $$\sqrt{|N_{row,col}(i,j)|} (\hat{\theta}_{i,j} - \theta_{i,j}) \xrightarrow{d} \mathcal{N}(0, \sigma^2)$$
  This result enables the construction of valid confidence intervals for counterfactual estimates.

Empirical Results

The authors validate their theoretical findings through:

1. Synthetic Simulations:

   • Experiments compare TS-NN against baselines including Row-NN, Column-NN, Doubly-Robust NN (DR-NN), Universal Singular Value Thresholding (USVT), and SoftImpute.
   • Results: TS-NN consistently achieves the best MSE decay rates, matching the Oracle-TS-NN (which knows latent factors) in MCAR settings. Crucially, TS-NN maintains robust performance in MNAR settings where other methods (like DR-NN) degrade significantly.
   • Smoothness Adaptivity: The empirical decay rates of TS-NN align with theoretical predictions as the smoothness parameter $\lambda$ varies.
   • Confidence Intervals: The constructed confidence intervals achieve near-nominal coverage (95%) for moderate sample sizes, validating the asymptotic normality result.

2. Real-World Case Study (HeartSteps):

   • The method is applied to the HeartSteps mobile health dataset, a micro-randomized trial involving 37 users and decision points over 6 weeks.
   • The dataset exhibits MNAR characteristics (users are unavailable ~20% of the time, and notifications are only sent if available).
   • Results: In a 5-fold cross-validation setting, TS-NN outperforms one-sided NN variants (Row-NN, Col-NN) and baselines like "All-Row-NN" in estimating counterfactual step counts, demonstrating the practical utility of the two-sided approach in handling deterministic missingness.

Significance and Claims

The paper claims to unify two distinct research domains: non-parametric matrix completion and MNAR missing data analysis.

• First-of-its-kind Analysis: The authors state this is the first theoretical analysis of a method that handles unknown row and column latent factors, a non-linear Hölder-continuous function (with $\lambda < 1$), and MNAR missingness simultaneously.
• Oracle Equivalence: The work demonstrates that the lack of knowledge regarding latent factors does not penalize the convergence rate; TS-NN performs as well as an oracle with full knowledge of $U$ and $V$ in the intermediate regime.
• Robustness: The methodology is shown to be robust to deterministic missingness patterns, a feature often ignored in standard matrix completion literature but critical for real-world applications like recommendation systems.

The authors conclude that TS-NN provides a theoretically grounded, adaptive, and robust solution for matrix completion in complex, non-smooth, and non-random missingness environments.