Fine-grained generalization analysis of inductive matrix completion

Antoine Ledent, Rodrigo Alves, Yunwen Lei, Marius Kloft

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Downloads (Pure)


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 O(rd2) to Õ(d3/2√r), where d is the dimension of the side information and r 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 Õ(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.
Original languageEnglish
Title of host publicationAdvances in Neural Information Processing Systems 34 (NeurIPS 2021)
EditorsM. Ranzato, A. Beygelzimer, P.S. Liang, J.W. Vaughan, Y. Dauphin
ISBN (Print)9781713845393
Publication statusPublished - 1 Dec 2021
EventThirty-fifth Conference on Neural Information Processing Systems - Virtual
Duration: 6 Dec 202114 Dec 2021

Publication series

NameAdvances in neural information processing systems
ISSN (Print)1049-5258


ConferenceThirty-fifth Conference on Neural Information Processing Systems
Abbreviated titleNeurIPS 2021


Dive into the research topics of 'Fine-grained generalization analysis of inductive matrix completion'. Together they form a unique fingerprint.

Cite this