17 April – Alexandra Carpentier: Statistical and computational challenges in unsupervised learning: focus on ranking
Ranking problems are prevalent in the modern statistics, 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 from both an informational perspective – characterising the fundamental statistical thresholds for optimal estimation – and a computational one – characterising the fundamental limits of computationally efficient estimation. A core question for these problems is whether statistical optimality is compatible with computational efficiency.
To address this, we first consider the simpler sub-problem of sub-matrix detection and estimation, which is useful to understand the more complex problem of ranking – and we will focus in particular 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.
Alexandra Carpentier is a French mathematical statistician and machine learning researcher working mostly in high- or infinite-dimensional statistics, sequential learning theory, and more recently unsupervised learning and statistical/computational trade-offs. She works in Germany as a professor at the University of Potsdam where she is head of the Mathematical Statistics and Machine Learning research group.