Tighter Generalization Bounds for Matrix Completion Via Factorization Into Constrained Matrices
Ken-ichiro MORIDOMI, Kohei Hatano, Eiji Takimoto · IEICE Transactions on Information and Systems · 2018
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.