Fine-grained Generalisation Analysis of Inductive Matrix Completion

Antoine Ledent, Rodrigo Alves, Yunwen Lei, Marius Kloft

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

7 Citations (Scopus)


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 inductive matrix completion: (1) In the distribution-free setting, we prove sample complexity bounds improving the previously best rate of rd2 to d3/2√r logpdq, where d is the dimension of the side information and r is the rank. (2) We introduce the (smoothed) adjusted trace-norm minimization strategy, an inductive analogue of the weighted trace norm, for which we show guarantees of the order O(dr log (d)) 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 publication35th Conference on Neural Information Processing Systems (NeurIPS 2021)
EditorsMarc'Aurelio Ranzato, Alina Beygelzimer, Yann Dauphin, Percy S. Liang, Jenn Wortman Vaughan
PublisherNeural Information Processing Systems Foundation
Number of pages13
ISBN (Print)9781713845393
Publication statusPublished - 6 Dec 2021
Event35th Conference on Neural Information Processing Systems, NeurIPS 2021 - Virtual
Duration: 6 Dec 202114 Dec 2021 (Conference website) (Conference website) (Conference proceedings) (Conference proceedings)

Publication series

NameAdvances in Neural Information Processing Systems
ISSN (Print)1049-5258
NameNeurIPS Proceedings


Conference35th Conference on Neural Information Processing Systems, NeurIPS 2021
Internet address

Scopus Subject Areas

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing


Dive into the research topics of 'Fine-grained Generalisation Analysis of Inductive Matrix Completion'. Together they form a unique fingerprint.

Cite this