# Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion

arXiv: https://arxiv.org/abs/2411.12965 · HTML: https://mlsanity.com/paper/2411.12965/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 37 references that are in the map.
- First posted on arXiv 20 Nov 2024.

## Builds on (most cited first, 15 of 15)

- [Recommendations as Treatments: Debiasing Learning and Evaluation](https://mlsanity.com/paper/1602.05352/) (2016)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [Causal Matrix Completion](https://mlsanity.com/paper/2109.15154/) (2021)
- [Provable Inductive Matrix Completion](https://mlsanity.com/paper/1306.0626/) (2013)
- [Missing Not at Random in Matrix Completion: The Effectiveness of Estimating Missingness Probabilities Under a Low Nuclear Norm Assumption](https://mlsanity.com/paper/1910.12774/) (2019)
- [Rates of Convergence of Spectral Methods for Graphon Estimation](https://mlsanity.com/paper/1709.03183/) (2017)
- [Synthetic Interventions](https://mlsanity.com/paper/2006.07691/) (2020)
- [Imputation and low-rank estimation with Missing Not At Random data](https://mlsanity.com/paper/1812.11409/) (2018)
- [High-dimensional principal component analysis with heterogeneous missingness](https://mlsanity.com/paper/1906.12125/) (2019)
- [Matrix completion with data-dependent missingness probabilities](https://mlsanity.com/paper/2106.02290/) (2021)
- [Counterfactual inference in sequential experiments](https://mlsanity.com/paper/2202.06891/) (2022)
- [Optimal Estimation and Completion of Matrices with Biclustering Structures](https://mlsanity.com/paper/1512.00150/) (2015)
- [Doubly robust nearest neighbors in factor models](https://mlsanity.com/paper/2211.14297/) (2022)
- [TenIPS: Inverse Propensity Sampling for Tensor Completion](https://mlsanity.com/paper/2101.00323/) (2021)
- [Nonparametric Matrix Estimation with One-Sided Covariates](https://mlsanity.com/paper/2110.13969/) (2021)

## Built on by (most cited first, 1 of 1)

- [Adaptively-weighted Nearest Neighbors for Matrix Completion](https://mlsanity.com/paper/2505.09612/) (2025)

## Abstract (arXiv)

Nearest neighbor (NN) algorithms have been extensively used for missing data problems in recommender systems and sequential decision-making systems. Prior theoretical analysis has established favorable guarantees for NN when the underlying data is sufficiently smooth and the missingness probabilities are lower bounded. Here we analyze NN with non-smooth non-linear functions with vast amounts of missingness. In particular, we consider matrix completion settings where the entries of the underlying matrix follow a latent non-linear factor model, with the non-linearity belonging to a Holder function class that is less smooth than Lipschitz. Our results establish following favorable properties for a suitable two-sided NN: (1) The mean squared error (MSE) of NN adapts to the smoothness of the non-linearity, (2) under certain regularity conditions, the NN error rate matches the rate obtained by an oracle equipped with the knowledge of both the row and column latent factors, and finally (3) NN's MSE is non-trivial for a wide range of settings even when several matrix entries might be missing deterministically. We support our theoretical findings via extensive numerical simulations and a case study with data from a mobile health study, HeartSteps.