Graph Resistance and Learning from Pairwise Comparisons

By Julien M. Hendrickx, Alexander Olshevsky, Venkatesh Saligrama. 2019

12 citations recorded by the source corpus.

We consider the problem of learning the qualities of a collection of items by performing noisy comparisons among them. Following the standard paradigm, we assume there is a fixed "comparison graph" and every neighboring pair of items in this graph is compared $k$ times according to the Bradley-Terry-Luce model (where the probability than an item wins a comparison is proportional the item quality). We are interested in how the relative error in quality estimation scales with the comparison graph in the regime where $k$ is large. We prove that, after a known transition period, the relevant graph-theoretic quantity is the square root of the resistance of the comparison graph. Specifically, we provide an algorithm that is minimax optimal. The algorithm has a relative error decay that scales with the square root of the graph resistance, and provide a matching lower bound (up to log factors). The performance guarantee of our algorithm, both in terms of the graph and the skewness of the item quality distribution, outperforms earlier results.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research, Graph Learning, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

In Graph Learning

In Statistical Learning Theory

Citations in the corpus

Generalized Results for the Existence and Consistency of the MLE in the Bradley-Terry-Luce Model (2021, methodology): “Instead, the sharper rate of the lowerbound is achieved by the (cid:96) 2 rate implication of Theorem 1, Hendrickx et al. (2019); compare, e.g., the examples in Section 4.1, Shah et al. (2016) and Table 1, Hendrickx et al. (2019).”
Minimax Rate for Learning From Pairwise Comparisons in the BTL Model (2020, methodology): “This problem formulation is standard in the literature; in particular, its analysis has been the subject of a number of recent papers, e.g., (Negahban et al. , 2012; Rajkumar & Agarwal, 2014; Negahban et al. , 2016; Agarwal et al. , 2018; Hendrickx et al. , 2019).”