Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

12-2021

Abstract

In this paper, we bridge the gap between the state-of-the-art theoretical results for matrix completion with the nuclear norm and their equivalent in \textit{inductive matrix completion}: (1) In the distribution-free setting, we prove bounds improving the previously best scaling of \widetilde{O}(rd2) to \widetilde{O}(d3/2√r), where d is the dimension of the side information and rr is the rank. (2) We introduce the (smoothed) \textit{adjusted trace-norm minimization} strategy, an inductive analogue of the weighted trace norm, for which we show guarantees of the order \widetilde{O}(dr) under arbitrary sampling. In the inductive case, a similar rate was previously achieved only under uniform sampling and for exact recovery. Both our results align with the state of the art in the particular case of standard (non-inductive) matrix completion, where they are known to be tight up to log terms. Experiments further confirm that our strategy outperforms standard inductive matrix completion on various synthetic datasets and real problems, justifying its place as an important tool in the arsenal of methods for matrix completion using side information.

Keywords

Matrix Completion, Recommender Systems, Distribution-sensitive Learning, Statistical Learning Theory, Nuclear Norm

Discipline

Databases and Information Systems | Graphics and Human Computer Interfaces

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the 35th Conference on Neural Information Processing System (NeurIPS 2021), Virtual Conference, December 6-12

Volume

34

First Page

25540

Last Page

25552

ISBN

9781713845393

City or Country

Virtual Conference

Additional URL

https://proceedings.neurips.cc/paper/2021/hash/d6428eecbe0f7dff83fc607c5044b2b9-Abstract.html

Download

Share

COinS