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.