Friday, March 27, 2026
Lecture room B6
Institute for Exact Sciences
Sidlerstr. 5
CH-3012 Bern
14:30-15:20 h
Statistical and computational challenges in unsupervised learning: focus on ranking
Ranking problems are prevalent in modern statistical, machine learning, and computer science literature. This includes a variety of practical situations ranging from ranking experts/workers in crowd-sourced data, ranking players in a tournament or equivalently sorting objects based on pairwise comparisons. A main challenge in this field is to construct an estimator of the rank of the experts, based on incomplete and noisy data.
In this talk, we focus on understanding the problem of ranking both from an informational - namely, characterizing the fundamental statistical thresholds for optimal estimation - and a computational - namely, also characterising the fundamental limits of computationally efficient estimation - perspective. A core question for these problems is on whether statistical optimality is compatible with computational efficiency.
To do that, we first consider the simpler sub-problem of sub-matrix detection and estimation, which is useful to apprehend the more complex problem of ranking - and we will particularly focus on computational lower bounds. Based on results for this problem, we explain how they can be used to solve the more challenging problem of ranking.
