MRA-based Statistical Learning from Incomplete Rankings Stéphan Clémençon.

Summary Statistical analysis of rank data describing preferences over small and variable subsets of a potentially large ensemble of items {1,. . , n} is a very challenging problem. It is motivated by a wide variety of modern applications, such as recommender systems or search engines. However , very few inference methods have been documented in the literature to learn a ranking model from such incomplete rank data. The goal of this paper is twofold: it develops a rigorous mathematical framework for the problem of learning a ranking model from incomplete rankings and introduces a novel general statistical method to address it. Based on an original concept of multi-resolution analysis (MRA) of incomplete rank-ings, it finely adapts to any observation setting, leading to a statistical accuracy and an algorith-mic complexity that depend directly on the complexity of the observed data. Beyond theoretical guarantees, we also provide experimental results that show its statistical performance.