Towards new challenges related to ranking data of complex structure.

Presentation in Mathematics

Ranking random observations has become essential to many data analysis problems, ranging from recommendation systems, computational biology, to information retrieval for instance, wherein the information acquisition processes nowadays often involve various and poorly controlled sources, leading to datasets possibly exhibiting strong sampling bias. Fundamental to learning-to-rank algorithms and nonparametric hypothesis testing when the observations are drawn from multiple independent distributions, its study in high-dimension is the subject of much attention, especially due to the lack of natural relation order in the underlying space. 
In this talk, we will discuss an approach for ranking random observations of complex structure, when drawn from (two) unknown distributions, relying on a generalization of two-sample linear rank statistics. We will show how this new class encompasses and naturally extends classic univariate rank test statistics, as well as ranking performance criteria for related algorithms through the concept of Receiver Operating Characteristic (ROC) curve. Beyond preserving fundamental properties from the univariate setting, we will prove new concentration bounds for collections of rank statistics, and apply them to developing new methodologies in hypothesis testing with finite sample guarantees of testing errors. Convincing experimental studies will illustrate the advantages of this approach compared to state-of-the art methods. We will finally discuss important challenges for future research on specific structures of data.