In this paper we consider the collaborative ranking setting: a pool of users each provides a small number of pairwise preferences between $d$ possible items; from these we need to predict preferences of the users for items they have not yet seen. We do so by 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 (b) we develop a large-scale non-convex implementation, which we call AltSVM, that 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 in other measures of ranking performance.

本文针对协作排名问题展开研究，通过基于凸优化的算法和AltSVM这种大规模非凸实现方式，实现从用户提供的两两偏好比较结果中预测他们对未曾见过物品的偏好，该算法展现出了在多个协作过滤数据集中NDCG和排名性能的许多中等规模基线的表现优势。

基于成对比较的大规模协作排名偏好数据填充