Collaborative Filtering with the Trace Norm: Learning, Bounding, and Transducing

Ohad Shamir, Shai Shalev-Shwartz
Proceedings of the 24th Annual Conference on Learning Theory, PMLR 19:661-678, 2011.

Abstract

Trace-norm regularization is a widely-used and successful approach for collaborative filtering and matrix completion. However, its theoretical understanding is surprisingly weak, and despite previous attempts, there are no distribution-free, non-trivial learning guarantees currently known. In this paper, we bridge this gap by providing such guarantees, under mild assumptions which correspond to collaborative filtering as performed in practice. In fact, we claim that previous difficulties partially stemmed from a mismatch betweenthe standard learning-theoretic modeling of collaborative filtering, and its practical application. Our results also shed some light on the issue of collaborative filtering with bounded models, which enforce predictions to lie within a certain range. In particular, we provide experimental and theoretical evidence that such models lead to a modest yet significant improvement.

Cite this Paper

BibTeX
@InProceedings{pmlr-v19-shamir11a, title = {Collaborative Filtering with the Trace Norm: Learning, Bounding, and Transducing}, author = {Shamir, Ohad and Shalev-Shwartz, Shai}, booktitle = {Proceedings of the 24th Annual Conference on Learning Theory}, pages = {661--678}, year = {2011}, editor = {Kakade, Sham M. and von Luxburg, Ulrike}, volume = {19}, series = {Proceedings of Machine Learning Research}, address = {Budapest, Hungary}, month = {09--11 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v19/shamir11a/shamir11a.pdf}, url = {https://proceedings.mlr.press/v19/shamir11a.html}, abstract = {Trace-norm regularization is a widely-used and successful approach for collaborative filtering and matrix completion. However, its theoretical understanding is surprisingly weak, and despite previous attempts, there are no distribution-free, non-trivial learning guarantees currently known. In this paper, we bridge this gap by providing such guarantees, under mild assumptions which correspond to collaborative filtering as performed in practice. In fact, we claim that previous difficulties partially stemmed from a mismatch betweenthe standard learning-theoretic modeling of collaborative filtering, and its practical application. Our results also shed some light on the issue of collaborative filtering with bounded models, which enforce predictions to lie within a certain range. In particular, we provide experimental and theoretical evidence that such models lead to a modest yet significant improvement.} }
Endnote
%0 Conference Paper %T Collaborative Filtering with the Trace Norm: Learning, Bounding, and Transducing %A Ohad Shamir %A Shai Shalev-Shwartz %B Proceedings of the 24th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2011 %E Sham M. Kakade %E Ulrike von Luxburg %F pmlr-v19-shamir11a %I PMLR %P 661--678 %U https://proceedings.mlr.press/v19/shamir11a.html %V 19 %X Trace-norm regularization is a widely-used and successful approach for collaborative filtering and matrix completion. However, its theoretical understanding is surprisingly weak, and despite previous attempts, there are no distribution-free, non-trivial learning guarantees currently known. In this paper, we bridge this gap by providing such guarantees, under mild assumptions which correspond to collaborative filtering as performed in practice. In fact, we claim that previous difficulties partially stemmed from a mismatch betweenthe standard learning-theoretic modeling of collaborative filtering, and its practical application. Our results also shed some light on the issue of collaborative filtering with bounded models, which enforce predictions to lie within a certain range. In particular, we provide experimental and theoretical evidence that such models lead to a modest yet significant improvement.
RIS
TY - CPAPER TI - Collaborative Filtering with the Trace Norm: Learning, Bounding, and Transducing AU - Ohad Shamir AU - Shai Shalev-Shwartz BT - Proceedings of the 24th Annual Conference on Learning Theory DA - 2011/12/21 ED - Sham M. Kakade ED - Ulrike von Luxburg ID - pmlr-v19-shamir11a PB - PMLR DP - Proceedings of Machine Learning Research VL - 19 SP - 661 EP - 678 L1 - http://proceedings.mlr.press/v19/shamir11a/shamir11a.pdf UR - https://proceedings.mlr.press/v19/shamir11a.html AB - Trace-norm regularization is a widely-used and successful approach for collaborative filtering and matrix completion. However, its theoretical understanding is surprisingly weak, and despite previous attempts, there are no distribution-free, non-trivial learning guarantees currently known. In this paper, we bridge this gap by providing such guarantees, under mild assumptions which correspond to collaborative filtering as performed in practice. In fact, we claim that previous difficulties partially stemmed from a mismatch betweenthe standard learning-theoretic modeling of collaborative filtering, and its practical application. Our results also shed some light on the issue of collaborative filtering with bounded models, which enforce predictions to lie within a certain range. In particular, we provide experimental and theoretical evidence that such models lead to a modest yet significant improvement. ER -
APA
Shamir, O. & Shalev-Shwartz, S.. (2011). Collaborative Filtering with the Trace Norm: Learning, Bounding, and Transducing. Proceedings of the 24th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 19:661-678 Available from https://proceedings.mlr.press/v19/shamir11a.html.

Related Material