SPECTRAL METHOD AND REGULARIZED MLE ARE BOTH OPTIMAL FOR TOP-K RANKING

Area of Science:

• Machine Learning
• Statistics
• Data Science

Background:

• Ranking items from pairwise comparisons is a fundamental problem.
• The Bradley-Terry-Luce model is commonly used for pairwise comparison data.
• Existing methods' performance for top-K ranking is not fully understood.

Purpose of the Study:

• To determine the sample complexity for exact top-K identification using pairwise comparisons.
• To analyze the performance of spectral and maximum likelihood estimation (MLE) methods for top-K ranking.
• To establish theoretical guarantees for these methods under the Bradley-Terry-Luce model.

Main Methods:

• Utilizing the Bradley-Terry-Luce model with latent preference scores.
• Analyzing the spectral method and regularized maximum likelihood estimator (MLE).
• Employing a novel leave-one-out analysis and eigenvector perturbation bounds.

Main Results:

• The spectral method and regularized MLE are minimax optimal for sample complexity in top-K identification.
• Achieved optimal control of entrywise score estimation errors.
• Numerical experiments confirm low entrywise errors for both methods.

Conclusions:

• Both spectral and regularized MLE methods provide theoretically sound and practically effective solutions for top-K ranking.
• The developed leave-one-out analysis is effective for both iterative and non-iterative procedures.
• The study bridges the gap between theoretical bounds and minimax lower limits for spectral methods.