Collaboratively Learning Preferences from Ordinal Data
This work addresses preference prediction for applications like recommendation systems, but it is incremental as it builds on existing convex relaxation methods.
The paper tackles the problem of predicting user preferences from ordinal data, such as in recommendation systems, by learning a low-rank multinomial logit model using convex relaxation of nuclear norm minimization. It shows that this approach is minimax optimal, with proven upper bounds on error and matching lower bounds for collaborative ranking and bundled choice modeling.
In applications such as recommendation systems and revenue management, it is important to predict preferences on items that have not been seen by a user or predict outcomes of comparisons among those that have never been compared. A popular discrete choice model of multinomial logit model captures the structure of the hidden preferences with a low-rank matrix. In order to predict the preferences, we want to learn the underlying model from noisy observations of the low-rank matrix, collected as revealed preferences in various forms of ordinal data. A natural approach to learn such a model is to solve a convex relaxation of nuclear norm minimization. We present the convex relaxation approach in two contexts of interest: collaborative ranking and bundled choice modeling. In both cases, we show that the convex relaxation is minimax optimal. We prove an upper bound on the resulting error with finite samples, and provide a matching information-theoretic lower bound.