Tighter Generalization Bounds for Matrix Completion Via Factorization Into Constrained Matrices

Ken-ichiro MORIDOMI  Kohei HATANO  Eiji TAKIMOTO  

IEICE TRANSACTIONS on Information and Systems   Vol.E101-D   No.8   pp.1997-2004
Publication Date: 2018/08/01
Publicized: 2018/05/18
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2017EDP7339
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
matrix completion,  non-negative matrix factorization,  collaborative filtering,  Rademacher complexity,  generalization error bound,  

Full Text: PDF(394.1KB)>>
Buy this Article

We prove generalization error bounds of classes of low-rank matrices with some norm constraints for collaborative filtering tasks. Our bounds are tighter, compared to known bounds using rank or the related quantity only, by taking the additional L1 and L constraints into account. Also, we show that our bounds on the Rademacher complexity of the classes are optimal.