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


Superchapter: Joint Chapter of Communications, Information Theory, and Signal Processing Societies










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 and Time




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

Staticmap?size=250x200&sensor=false&zoom=14&markers=43.260879%2c 79
  • Chair, Hamilton Superchapter


Prof. Vincent Tan

Prof. Vincent Tan of National University of Singapore


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


Vincent Tan was born in Singapore in 1981. He is currently an Associate Professor in the Department of Electrical and Computer Engineering  and the Department of Mathematics at the National University of Singapore (NUS). He received the B.A. and M.Eng. degrees in Electrical and Information Sciences from Cambridge University in 2005 and the Ph.D. degree in Electrical Engineering and Computer Science (EECS) from the Massachusetts Institute of Technology in 2011. His research interests include information theory and machine learning.

Dr. Tan received the MIT EECS Jin-Au Kong outstanding doctoral thesis prize in 2011, the NUS Young Investigator Award in 2014, the NUS Engineering Young Researcher Award in 2018, and the Singapore National Research Foundation (NRF) Fellowship (Class of 2018). He is also a Distinguished Lecturer of the IEEE Information Theory Society (2018/9). He has authored a research monograph on "Asymptotic Estimates in Information Theory with Non-Vanishing Error Probabilities" in the Foundations and Trends in Communications and Information Theory Series (NOW Publishers). He is currently an Editor of the IEEE Transactions on Signal Processing.