# Learning from Pairwise Comparisons

The Learning from Pairwise Comparison project focuses on learning problems in which a set of values have to be learned based on noisy information about pairs of these values (e.g. their ratio, product), a framework that applies to large classes of problems including for example

The initial length is one-year (full time) with a possibility of expansion up to two years. The postdoctoral salary is free of tax and the hired candidate will be covered by the Belgian Healthcare System.
If you are interested please contact Pascale Premereur at pascale.premereur@uclouvain.be with mentioning the name of the project and include (at least) a CV,
a list of publications, and the name of two referees. If you have any questions please contact us at julien.hendrickx@uclouvain.be or
at balint.daroczy@uclouvain.be.

In Proceedings of the 37th International Conference on Machine Learning (ICML 2020), PMLR 119:4193-4202, 2020.

We consider the problem of learning the qualities w_1, ... , w_n 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 w_i/(w_i + w_j). We are interested in how the expected error in estimating
the vector w = (w_1, ... , 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.

In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics (AISTATS 2020), PMLR 108:3426-3436, 2020.

We consider the problem of recovering a rank-one matrix when a perturbed subset of its entries is revealed.
We propose a method based on least squares in the log-space and show its performance matches the lower bounds that we derive for this problem in the small-perturbation regime,
which are related to the spectral gap of a graph representing the revealed entries. Unfortunately, we show that for larger disturbances, potentially exponentially growing errors
are unavoidable for any consistent recovery method. We then propose a second algorithm relying on encoding the matrix factorization in the stationary distribution of a certain Markov chain.
We show that, under the stronger assumption of known upper and lower bounds on the entries of the true matrix, this second method does not have exponential error growth for large disturbances.
Both algorithms can be implemented in nearly linear time.

In Proceedings of the 36th International Conference on Machine Learning (ICML 2019), PMLR 97:2702-2711, 2019.

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 show that, asymptotically, the relevant graph-theoretic quantity is the square root of the resistance
of the comparison graph. Specifically, we provide an algorithm with relative error decay that scales with the square root of the graph resistance, and provide a lower bound showing that (up to log factors) a better
scaling is impossible. The performance guarantee of our algorithm, both in terms of the graph and the skewness of the item quality distribution, significantly outperforms earlier results.