An Empirical Study of the Discreteness Prior in Low-Rank Matrix Completion

Rodrigo Alves, Antoine Ledent, Renato Assunção, Marius Kloft
NeurIPS 2020 Workshop on Pre-registration in Machine Learning, PMLR 148:111-125, 2021.

Abstract

A reasonable assumption in recommender systems is that the rows (users) and columns (items) of the rating matrix can be split into groups (communities) with the following property: each entry of the matrix is the sum of components corresponding to community behavior and a purely low-rank component corresponding to individual behavior. We investigate (1) whether such a structure is present in real-world datasets, (2) whether the knowledge of the existence of such structure alone can improve performance, without explicit information about the community memberships. To these ends, we formulate a joint optimization problem over all (completed matrix, set of communities) pairs based on a nuclear-norm regularizer which jointly encourages both low-rank solutions and the recovery of relevant communities. Since our optimization problem is non-convex and of combinatorial complexity, we propose a heuristic algorithm to solve it. Our algorithm alternatingly refines the user and item communities through a clustering step jointly supervised by nuclear-norm regularization. The algorithm is guaranteed to converge. We performed synthetic and real data experiments to confirm our hypothesis and evaluate the efficacy of our method at recovering the relevant communities. The results shows that our method is capable of retrieving such an underlying (community behaviour + continuous low-rank) structure with high accuracy if it is present.

Cite this Paper

BibTeX
@InProceedings{pmlr-v148-alves21a, title = {An Empirical Study of the Discreteness Prior in Low-Rank Matrix Completion}, author = {Alves, Rodrigo and Ledent, Antoine and Assun{\c{c}}{\~a}o, Renato and Kloft, Marius}, booktitle = {NeurIPS 2020 Workshop on Pre-registration in Machine Learning}, pages = {111--125}, year = {2021}, editor = {Bertinetto, Luca and Henriques, João F. and Albanie, Samuel and Paganini, Michela and Varol, Gül}, volume = {148}, series = {Proceedings of Machine Learning Research}, month = {11 Dec}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v148/alves21a/alves21a.pdf}, url = {https://proceedings.mlr.press/v148/alves21a.html}, abstract = {A reasonable assumption in recommender systems is that the rows (users) and columns (items) of the rating matrix can be split into groups (communities) with the following property: each entry of the matrix is the sum of components corresponding to community behavior and a purely low-rank component corresponding to individual behavior. We investigate (1) whether such a structure is present in real-world datasets, (2) whether the knowledge of the existence of such structure alone can improve performance, without explicit information about the community memberships. To these ends, we formulate a joint optimization problem over all (completed matrix, set of communities) pairs based on a nuclear-norm regularizer which jointly encourages both low-rank solutions and the recovery of relevant communities. Since our optimization problem is non-convex and of combinatorial complexity, we propose a heuristic algorithm to solve it. Our algorithm alternatingly refines the user and item communities through a clustering step jointly supervised by nuclear-norm regularization. The algorithm is guaranteed to converge. We performed synthetic and real data experiments to confirm our hypothesis and evaluate the efficacy of our method at recovering the relevant communities. The results shows that our method is capable of retrieving such an underlying (community behaviour + continuous low-rank) structure with high accuracy if it is present. } }
Endnote
%0 Conference Paper %T An Empirical Study of the Discreteness Prior in Low-Rank Matrix Completion %A Rodrigo Alves %A Antoine Ledent %A Renato Assunção %A Marius Kloft %B NeurIPS 2020 Workshop on Pre-registration in Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Luca Bertinetto %E João F. Henriques %E Samuel Albanie %E Michela Paganini %E Gül Varol %F pmlr-v148-alves21a %I PMLR %P 111--125 %U https://proceedings.mlr.press/v148/alves21a.html %V 148 %X A reasonable assumption in recommender systems is that the rows (users) and columns (items) of the rating matrix can be split into groups (communities) with the following property: each entry of the matrix is the sum of components corresponding to community behavior and a purely low-rank component corresponding to individual behavior. We investigate (1) whether such a structure is present in real-world datasets, (2) whether the knowledge of the existence of such structure alone can improve performance, without explicit information about the community memberships. To these ends, we formulate a joint optimization problem over all (completed matrix, set of communities) pairs based on a nuclear-norm regularizer which jointly encourages both low-rank solutions and the recovery of relevant communities. Since our optimization problem is non-convex and of combinatorial complexity, we propose a heuristic algorithm to solve it. Our algorithm alternatingly refines the user and item communities through a clustering step jointly supervised by nuclear-norm regularization. The algorithm is guaranteed to converge. We performed synthetic and real data experiments to confirm our hypothesis and evaluate the efficacy of our method at recovering the relevant communities. The results shows that our method is capable of retrieving such an underlying (community behaviour + continuous low-rank) structure with high accuracy if it is present.
APA
Alves, R., Ledent, A., Assunção, R. & Kloft, M.. (2021). An Empirical Study of the Discreteness Prior in Low-Rank Matrix Completion. NeurIPS 2020 Workshop on Pre-registration in Machine Learning, in Proceedings of Machine Learning Research 148:111-125 Available from https://proceedings.mlr.press/v148/alves21a.html.

Related Material