Skip to main content
Upcoming Events:

Recent Advances in Ranking: Adversarial Respondents and Lower Bounds on the Bayes Risk

Date & Time:
   Add All to Calendar
Location:

ITB-A113

Event Contact:

Kerri Hastings, Administrative Coordinator for the Department of Electrical & Computer Engineering

hastings@mcmaster.ca

Dr. Vincent Tan, National University of Singapore

Overview

This talk first introduces a standard generative model in ranking (or recommender) systems, namely, the Bradley-Terry-Luce (BTL) model in which the chance of item i beating item j is proportional to the relative score of item i to item j. We consider two different problems related to this model. First, we study the top-K ranking problem where the goal is to recover the set of top-K ranked items out of a large collection of items based on partially revealed preferences. We consider an adversarial crowdsourced setting where there are two population sets. Pairwise comparison samples drawn from one of the populations follow the standard BTL model, while in the other population, the corresponding chance is inversely proportional to the relative score. We derive information-theoretic limits for the recovery of the top-K set and efficient algorithms for doing so. Second, for the Bayesian BTL model, we derive information-theoretic lower bounds on the Bayes risk of estimators for norm-based distortion functions. We draw parallels between pairwise comparisons in the BTL model and inter-player games represented as edges in a graph and analyze the effect of various graph structures on the lower bounds.