Spectral MLE: Top-$K$ Rank Aggregation from Pairwise Comparisons

Abstract

This paper explores the preference-based top-$K$ rank aggregation problem. Suppose that a collection of items is repeatedly compared in pairs, and one wishes to recover a consistent ordering that emphasizes the top-$K$ ranked items, based on partially revealed preferences. We focus on the Bradley-Terry-Luce (BTL) model that postulates a set of latent preference scores underlying all items, where the odds of paired comparisons depend only on the relative scores of the items involved. We characterize the minimax limits on identifiability of top-$K$ ranked items, in the presence of random and non-adaptive sampling. Our results highlight a separation measure that quantifies the gap of preference scores between the $K^{\text{th}}$ and $(K+1{)}^{\text{th}}$ ranked items. The minimum sample complexity required for reliable top-$K$ ranking scales inversely with the separation measure irrespective of other preference distribution metrics. To approach this minimax limit, we propose a nearly linear-time ranking scheme, called \emph{Spectral MLE}, that returns the indices of the top-$K$ items in accordance to a careful score estimate. In a nutshell, Spectral MLE starts with an initial score estimate with minimal squared loss (obtained via a spectral method), and then successively refines each component with the assistance of coordinate-wise MLEs. Encouragingly, Spectral MLE allows perfect top-$K$ item identification under minimal sample complexity. The practical applicability of Spectral MLE is further corroborated by numerical experiments.

accepted to International Conference on Machine Learning (ICML), 2015

References in corpus (8)

• Rényi Divergence and Kullback-Leibler Divergence
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• Noisy Sorting Without Resampling
• Active Ranking using Pairwise Comparisons
• When is it Better to Compare than to Score?
• Rank Centrality: Ranking from Pair-wise Comparisons
• Individualized Rank Aggregation using Nuclear Norm Regularization
• Analysis of Crowdsourced Sampling Strategies for HodgeRank with Sparse Random Graphs

Cited by in corpus (16)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
• Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking
• Principal component analysis for big data
• Worst-case vs Average-case Design for Estimation from Fixed Pairwise Comparisons
• Active Ranking from Pairwise Comparisons and when Parametric Assumptions Don't Help
• Matrix Completion with Hierarchical Graph Side Information
• Computational and Statistical Tradeoffs in Learning to Rank
• PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Bounds
• Breaking the $1/\sqrt{n}$ Barrier: Faster Rates for Permutation-based Models in Polynomial Time
• On the Minimax Misclassification Ratio of Hypergraph Community Detection
• A Nearly Instance Optimal Algorithm for Top-k Ranking under the Multinomial Logit Model
• Simultaneous Preference and Metric Learning from Paired Comparisons
• Ranking Recovery from Limited Comparisons using Low-Rank Matrix Completion
• Secretary Ranking with Minimal Inversions
• Dynamic change-point detection using similarity networks