Partial matrix completion

Conference item

The matrix completion problem involves reconstructing a low-rank matrix by using a given set of revealed (and potentially noisy) entries. Although existing methods address the completion of the entire matrix, the accuracy of the completed entries can vary significantly across the matrix, due to differences in the sampling distribution. For instance, users may rate movies primarily from their country or favorite genres, leading to inaccurate predictions for the majority of completed entries.We propose a novel formulation of the problem as Partial Matrix Completion, where the objective is to complete a substantial subset of the entries with high confidence. Our algorithm efficiently handles the unknown and arbitrarily complex nature of the sampling distribution, ensuring high accuracy for all completed entries and sufficient coverage across the matrix. Additionally, we introduce an online version of the problem and present a low-regret efficient algorithm based on iterative gradient updates. Finally, we conduct a preliminary empirical evaluation of our methods.

Authors: Hazan, E; Kalai, AT; Kanade, V; Mohri, C; Sun, YJ

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Curran Associates
• Host title: Advances in Neural Information Processing Systems 36 (NeurIPS 2023)
• Volume: 36
• Pages: 30134-30145
• Publication date: 2023-12-15
• Acceptance date: 2023-09-21
• Event title: 37th Annual Conference on Neural Information Processing Systems (NeurIPS 2023)
• Event location: New Orleans, Louisiana, USA
• Event website: https://neurips.cc/Conferences/2023
• Event start date: 2023-12-10
• Event end date: 2023-12-16
• DOI: 10.52202/075280-1311
• EISBN: 9781713899921
• Language: English