提出双向近邻法，实现非光滑矩阵补全的自适应最优性能
Two-Sided Nearest Neighbors: An adaptive and minimax optimal procedure for matrix completion
- 采用双向近邻策略处理非线性、高缺失场景下的矩阵补全
- 误差率逼近已知因子的最优理想情况，且随平滑度自适应调整
- 适用于复杂缺失模式，适合医疗健康等高缺失数据场景
近邻算法广泛应用于推荐系统和序列决策中的缺失数据问题。以往理论分析表明，当数据足够平滑且缺失概率有下界时，近邻方法具有优良保证。本文研究在非平滑非线性函数及大量缺失情况下的近邻方法。具体考虑矩阵补全场景，其中底层矩阵遵循潜在非线性因子模型，非线性属于比Lipschitz更弱的\'Holder函数类。结果表明：（1）合适的双向近邻方法其均方误差（MSE）可自适应非线性平滑度；（2）在特定正则条件下，其误差率匹配已知行、列因子的最优预言机；（3）即使部分矩阵条目被确定性缺失，其MSE仍保持非平凡。通过大量数值模拟及来自移动健康研究HeartSteps的数据案例验证了理论发现。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。