This talk considers problems in unsupervised learning, a field in which trade-off between statistical efficiency and computational efficiency are of importance. We focus in particular on crowd-sourcing models. We have n experts and d tasks. The average ability of each expert for each task is stored in an unknown matrix M, from which we have incomplete and noisy observations. We make no (semi) parametric assumptions, but assume that both experts and tasks can be perfectly ordered: so that if an expert A is better than an expert B, the ability of A is higher than that of B for all tasks - and that the same holds for the tasks. This implies that if the matrix M, up to permutations of its rows and columns, is bi-isotonic. We focus on the problems of ranking the experts by ability, and aim at finding computationally efficient procedure which are also statistically optimal. We prove that in some instances of this problem, this is feasible, disproving some long-standing conjectures on computational gaps.

This talk is based on a joint works with Max Graf, Emmanuel Pilliat and Nicolas Verzelen.

Links to the underlying papers:

https://epubs.siam.org/doi/abs/10.1137/1.9781611977912.116

https://projecteuclid.org/journals/annals-of-statistics/volume-51/issue-3/Optimal-Permutation-Estimation-in-CrowdSourcing-problems/10.1214/23-AOS2271.short

https://arxiv.org/abs/2408.15356

Personal website of Alexandra Carpentier