F Nous contacter


H 1 Statistical optimality and algorithms for top-K and total ranking - Lecture 1

Auteurs : Gao, Chao (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : In this short course, we will discuss the problem of ranking with partially observed pairwise comparisons in the setting of Bradley-Terry-Luce (BTL) model. There are two fundamental problems: 1) top-K ranking, which is to select the set of K players with top performances; 2) total ranking, which is to rank the entire set of players. Both ranking problems find important applications in web search, recommender systems and sports competition.
    In the first presentation, we will consider the top-K ranking problem. The statistical properties of two popular algorithms, MLE and rank centrality (spectral ranking) will be precisely characterized. In terms of both partial and exact recovery, the MLE achieves optimality with matching lower bounds. The spectral method is shown to be generally sub-optimal, though it has the same order of sample complexity as the MLE. Our theory also reveals the essentially only situation when the spectral method is optimal. This turns out to be the most favorable choice of skill parameter given the separation of the two groups.
    The second presentation will be focused on total ranking. The problem is to find a permutation vector to rank the entire set of players. We will show that the minimax rate of the problem with respect to the Kendall’s tau loss exhibits a transition between an exponential rate and a polynomial rate depending on the signal to noise ratio of the problem. The optimal algorithm consists of two stages. In the first stage, games with very high or low scores are used to partition the entire set of players into different leagues. In the second stage, games that are very close are used to rank the players within each league. We will give intuition and some analysis to show why the algorithm works optimally.

    Keywords : minimax rate; BTL model; pairwise comparison

    Codes MSC :
    62C20 - Minimax procedures
    62F07 - Ranking and selection
    62J12 - Generalized linear models

      Informations sur la Vidéo

      Réalisateur : Hennenfent, Guillaume
      Langue : Anglais
      Date de publication : 11/01/2021
      Date de captation : 15/12/2020
      Collection : Research talks ; Probability and Statistics
      Durée : 01:02:25
      Domaine : Probability & Statistics
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2020-12-15_Gao.mp4

    Informations sur la Rencontre Virtuelle

    Nom de la rencontre : Meeting in Mathematical Statistics / Rencontres de statistique mathématique
    Organisateurs de la rencontre : Butucea, Cristina ; Minsker, Stanislav ; Pouet, Christophe ; Spokoiny, Vladimir
    Dates : 14/12/2020 - 18/12/2020
    Année de la rencontre : 2020
    URL Congrès : https://conferences.cirm-math.fr/2536.html

    Citation Data

    DOI : 10.24350/CIRM.V.19692203
    Cite this video as: Gao, Chao (2020). Statistical optimality and algorithms for top-K and total ranking - Lecture 1.CIRM . Audiovisual resource. doi:10.24350/CIRM.V.19692203
    URI : http://dx.doi.org/10.24350/CIRM.V.19692203

    Voir aussi