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

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.  

This talk is based on joint work with Changho Suh (KAIST), Renbo Zhao, Mine Alsan and Ranjitha Prasad (NUS)

• Date: 15 June 2018
• Time: 02:00 PM to 03:00 PM
• All times are Canada/Eastern
• Add to Google Calendar

• 1280 Main Street West
• McMaster University
• Hamilton, Ontario
• Canada L8S 4K1
• Building: ITB
• Room Number: A113

---

• Chair, Hamilton Superchapter