In this paper we consider the collaborative ranking setting: a pool of users each provides a set of pairwise preferences over a small subset of the set of d possible items; from these we need to predict each user’s preferences for items s/he has not yet seen. We do so via fitting a rank r score matrix to the pairwise data, and provide two main contributions: (a) We show that an algorithm based on convex optimization provides good generalization guarantees once each user provides as few as O(r log^2 d) pairwise comparisons — essentially matching the sample complexity required in the related matrix completion setting (which uses actual numerical as opposed to pairwise information), and also matching a lower bound we establish here. (b) We develop a large-scale non-convex implementation, which we call AltSVM, which trains a factored form of the matrix via alternating minimization (which we show reduces to alternating SVM problems), and scales and parallelizes very well to large problem settings. It also outperforms common baselines on many moderately large popular collaborative filtering datasets in both NDCG and other measures of ranking performance.
Dohyung Park is a Ph.D student of Electrical and Computer Engineering at UT Austin, working with Prof. Sujay Sanghavi and Prof. Constantine Caramanis. Prior to UT Austin, he was an R&D staff member at Samsung Advanced Institute of Technology (SAIT) from 2008 to 2011. He obtained a B.S. and a M.S. from KAIST in 2005 and 2008, respectively.