Tighter generalization bounds for matrix completion via factorization into constrained matrices

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 L₁ and L_∞ constraints into account. Also, we show that our bounds on the Rademacher complexity of the classes are optimal.