Learning from Pariwise Comparisons

Context: 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 analaysis of the algorithm and in the development of minimax lower bounds.
Contact Julien Hendrickx, (Homepage)

The learning from pairwise comparions project is funded by an incentive grant (MIS) of the F.R.S-FNRS for the period 2020-2022.

Open Postdoc Positions:

I am looking for two postdocs with a strong mathematical background. Ideal candidates have an expertise in at least one of the following fields: Graphs and Networks, Probabilities, Machine Learning, Online Learning, Optimization, Information Theory. The positions are available immediately.

How to apply: Sending an email to pascale.premereur@uclouvain.be mentioning the project name.


Our paper on Minimax Rank-1 matrix factorization will be presented at AISTAT 2020 . Our paper on Minimax Rate for Learning From Pairwise Comparisons has been accepted at ICML 2020 .

Project Publications and Preprints:

  • Julien M. Hendrickx, Alex Olshevsky and Venkatesh Saligrama, Minimax Rate for Learning From Pairwise Comparisons, to be presented at ICML 2020. [PDF]

  • Julien M. Hendrickx, Alex Olshevsky and Venkatesh Saligrama, Minimax Rank-1 Factorization, to be presented at AISTATS 2020. [PDF]

  • Julien M. Hendrickx, Alex Olshevsky and Venkatesh Saligrama, Graph Resistance and Learning from Pairwise Comparisons, ICML 2019. [PDF]

Responsible : Julien Hendrickx