Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisons

Abstract

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.

References in corpus (8)

• BPR: Bayesian Personalized Ranking from Implicit Feedback
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• Latent Collaborative Retrieval
• PASSCoDe: Parallel ASynchronous Stochastic dual Co-ordinate Descent
• Minimax-optimal Inference from Partial Rankings
• Individualized Rank Aggregation using Nuclear Norm Regularization
• Ranking via Robust Binary Classification and Parallel Parameter Estimation in Large-Scale Data

Cited by in corpus (9)

• PASSCoDe: Parallel ASynchronous Stochastic dual Co-ordinate Descent
• SQL-Rank: A Listwise Approach to Collaborative Ranking
• Learning to Hash with Graph Neural Networks for Recommender Systems
• Learning from Comparisons and Choices
• Preference Modeling with Context-Dependent Salient Features
• Dynamic-K Recommendation with Personalized Decision Boundary
• Advances in Collaborative Filtering and Ranking
• Risk Aware Ranking for Top-$k$ Recommendations
• Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations