  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.
