Seminar Details
2023-04-25 (14h) : Ranking from pairwise comparisons: a near-linear time minimax optimal algorithm for learning BTL weights
At Euler building (room A.002)
Organized by Mathematical Engineering
Speaker :
Hendrickx, Julien
Abstract :
We consider the problem of ranking and learning the qualities w1,…,wn of a collection of items by performing noisy comparisons among them. We assume that there is a fixed “comparison graph”, and every neighboring pair of items is compared k times.
We focus more specifically on the popular Bradley-Terry-Luce model, where comparisons are i.i.d. events, and the probability for item i to win the comparison against j is wi/(wi+wj).
We propose a near-linear time algorithm allowing us to recover the weights with an accuracy that outperforms all existing algorithms, and show that this accuracy is actually within a constant factor of information-theoretic lower bounds, that we also develop. This accuracy is related to the average resistance of the comparison graph.
Our algorithm is based on a weighted least square, with weights determined from empirical outcomes of the comparisons.
We further discuss the extension to other models of comparisons, and comparisons involving multiple items.