aiqbench analysis
This research presents a theoretically grounded nearest neighbor procedure optimized for matrix completion tasks involving non-smooth, non-linear latent factors and high rates of missing data. By adapting mean squared error to the underlying function smoothness, the method achieves oracle-like performance even when data is deterministically missing, offering robust improvements for recommender systems and sequential decision-making models.
Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion
arXiv:2411.12965v3 Announce Type: replace-cross Abstract: 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.
Abstract: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.
Machine Learning (stat.ML); Machine Learning (cs.LG); Statistics Theory (math.ST); Methodology (stat.ME)
arXiv:2411.12965 [stat.ML]
(or arXiv:2411.12965v3 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2411.12965 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 287 words
Related coverage
From Vector Search to Agentic RAG: Building an Enterprise Research Analyst with hipVS
AMD · Jul 15, 2026
Optimizing ATOM and vLLM-ATOM for High-Interactivity Inference
AMD · Sep 1, 2026
NEAREST BY Join: Scaling Vector Search in Databricks Runtime
Databricks · Oct 5, 2026
Productionizing TurboQuant on AMD GPUs for KV-Cache-Bound LLM Inference
AMD · Jun 11, 2026