Timezone: »

 
Poster
Fine-grained Generalization Analysis of Inductive Matrix Completion
Antoine Ledent · Rodrigo Alves · Yunwen Lei · Marius Kloft

Tue Dec 07 04:30 PM -- 06:00 PM (PST) @ Virtual
in Poster Session 2 »
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(rd^2)$ to $\widetilde{O}(d^{3/2}\sqrt{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 $\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: Theory

Author Information

Antoine Ledent (TU Kaiserslautern)

I obtained a PhD in stochastic analysis at the University of Luxembourg, and am now working in statistical learning theory as a postdoc.

Rodrigo Alves (TU Kaiserslautern)
Yunwen Lei (University of Birmingham)

I am currently a Lecturer at School of Computer Science, University of Birmingham. Previously, I was a Humboldt Research Fellow at University of Kaiserslautern, a Research Assistant Professor at Southern University of Science and Technology, and a Postdoctoral Research Fellow at City University of Hong Kong. I obtained my PhD degree in Computer Science at Wuhan University in 2014.

Marius Kloft (TU Kaiserslautern)

More from the Same Authors