Timezone: »

 
Poster
Minimax Rate for Learning From Pairwise Comparisons in the BTL Model
Julien Hendrickx · Alex Olshevsky · Venkatesh Saligrama

Tue Jul 14 07:00 AM -- 07:45 AM & Tue Jul 14 06:00 PM -- 06:45 PM (PDT) @
in Poster Session 1 »

We consider the problem of learning the qualities w1, ... , wn of a collection of items by performing noisy comparisons among them. We assume there is a fixed ``comparison graph'' and every neighboring pair of items is compared k times. We will study the popular Bradley-Terry-Luce model, where the probability that item i wins a comparison against j equals wi/(wi + wj). We are interested in how the expected error in estimating the vector w = (w1, ... , w_n) behaves in the regime when the number of comparisons k is large.

Our contribution is the determination of the minimax rate up to a constant factor. We show that this rate is achieved by a simple algorithm based on weighted least squares, with weights determined from the empirical outcomes of the comparisons. This algorithm can be implemented in nearly linear time in the total number of comparisons.

Keywords: Ranking and Preference Learning · Supervised Learning

Author Information

Julien Hendrickx (University of Catholique de Louvain)
Alex Olshevsky (Boston University)
Venkatesh Saligrama (Boston University)

More from the Same Authors