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.