Learning from Pairwise Comparisons

Project leader: Dr. Julien Hendrickx

Funded by: Mandat d’impulsion scientifique - MIS, F.R.S.-FNRS

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
    Recovering weights from comparison results in a Bradley-Terry-Luce model, with applications as diverse as modelling customer preferences, online advertisement, ranking quality of sport teams or evaluating patient reaction to medications

    Determining experts' abilities without knowing the ground truth of their actions e.g. in a Dawid-Skene based model

    General rank-1 matrix completion with perturbed data.

Objective and approach: We aim at developing generic ultra-rapid near-linear algorithms with minimax optimality guarantees for these learning problems. Our algorithms rely on formulating these problems as weighted least-square systems that are linear in the estimates but highly non-linear in the data, and exploiting the graph structure of the data to solve these systems in near linear time. The data can indeed be represented by a weighted graph in which two variables are connected when information on that pair is available, and this graph plays a major role both in the analysis of the algorithm and in the development of minimax lower bounds.

News

    26/10/2021: We are looking for two postdoc researchers to join us!
    Please check out the call: postdoc_call.pdf

    How to apply: send an email with title “[Postdoc Pairwise]” to Julien Hendrickx (julien.hendrickx_at_uclouvain.be), containing a CV, list of publications, and the name of at least two referees.

    26/10/2021: We are looking for MSc and PhD candidates to join us!

    09/11/2020: We welcome our new member, Bálint Daróczy as a postdoctoral research fellow.

    26/08/2020: AISTATS 2020 oral presentation of paper "Minimax Rank-1 Matrix Factorization" [link]

Members

    Project leader: Prof. Julien Hendrickx [link]

    Postdoctoral researcher: Bálint Daróczy [link]

Papers

    "Minimax Rate for Learning From Pairwise Comparisons in the BTL Model" by Julien Hendrickx, Alex Olshevsky, Venkatesh Saligrama

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

    [Link]

    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.

    "Minimax Rank-1 Matrix Factorization" by Venkatesh Saligrama, Alexander Olshevsky, Julien Hendrickx

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

    [Link]

    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.

    "Graph Resistance and Learning from Pairwise Comparisons" by Julien Hendrickx, Alexander Olshevsky, Venkatesh Saligrama

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

    [Link]

    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.