# Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisons

arXiv: https://arxiv.org/abs/1507.04457 · HTML: https://mlsanity.com/paper/1507.04457/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2015.

## Built on by (most cited first, 11 of 11)

- [LoRe: Personalizing LLMs via Low-Rank Reward Modeling](https://mlsanity.com/paper/2504.14439/) (2025)
- [Binary Classification with Confidence Difference](https://mlsanity.com/paper/2310.05632/) (2023)
- [Semi-verified PAC Learning from the Crowd](https://mlsanity.com/paper/2106.07080/) (2021)
- [Learning Human-Compatible Representations for Case-Based Decision Support](https://mlsanity.com/paper/2303.04809/) (2023)
- [Ranking with Confidence for Large Scale Comparison Data](https://mlsanity.com/paper/2202.01670/) (2022)
- [Leveraging Sparsity for Sample-Efficient Preference Learning: A Theoretical Perspective](https://mlsanity.com/paper/2501.18282/) (2025)
- [Safe Collaborative Filtering](https://mlsanity.com/paper/2306.05292/) (2023)
- [Recommendations with Sparse Comparison Data: Provably Fast Convergence for Nonconvex Matrix Factorization](https://mlsanity.com/paper/2502.20033/) (2025)
- [Fusion Subspace Clustering for Incomplete Data](https://mlsanity.com/paper/2205.10872/) (2022)
- [A Perturbation Bound on the Subspace Estimator from Canonical Projections](https://mlsanity.com/paper/2206.14278/) (2022)
- [Population-Level Generative Modeling for Ranking Data](https://mlsanity.com/paper/2608.08422/) (2026)

## Abstract (arXiv)

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(rlog2 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.