Probability and Statistics Seminar: Optimal Ranking Recovery from Pairwise Comparisons

Friday, February 26 at 3:00pm to 4:00pm

This is a past event.
Virtual Event

Anderson Ye Zhang
Wharton School of the University of Pennsylvania

Abstract: Ranking from pairwise comparisons is a central problem in a wide range of learning and social contexts. Researchers in various disciplines have made significant methodological and theoretical contributions to it. However, many fundamental statistical properties remain unclear especially for the recovery of ranking structure. This talk presents two recent projects towards optimal ranking recovery, under the Bradley-Terry-Luce (BTL) model.
In the first project, we study the problem of top-k ranking. That is, to optimally identify the set of top-k players. We derive the minimax rate and show that it can be achieved by MLE. On the other hand, we show another popular algorithm, the spectral method, is in general suboptimal.
In the second project, we study the problem of full ranking among all players. The minimax rate exhibits a transition between an exponential rate and a polynomial rate depending on the magnitude of the signal-to-noise ratio of the problem. To the best of our knowledge, this phenomenon is unique to full ranking and has not been seen in any other statistical estimation problem. A divide-and-conquer ranking algorithm is proposed to achieve the minimax rate.

Dial-In Information

Please see your email to join via zoom

Event Type

Lecture / Talk / Workshop

Add this to your calendar

Recent Activity