Estimation from Pairwise Comparisons: Statistical and Computational aspects

Nihar B. Shah
Graduate Student, UC Berkeley
Date: Apr. 29th, 2016


Data in the form of noisy pairwise comparisons arises in many domains such as sports, crowdsourcing and operations research. Some fundamental inferential questions include estimating a total or partial order of the items, or estimating the set of underlying pairwise-comparison probabilities. Prior works on these topics often rely on restrictive "parametric" models, that often provide poor fits to the data. Instead, we consider much richer models that rely on "permutations" rather than parameters. We establish tight statistical (information-theoretic) guarantees on estimation under these models, showing that this increased flexibility in the models yields a significantly higher robustness to the estimation procedures, while remarkably, increasing the worst case risk by only logarithmic factors. We also discuss various associated computational challenges.

(Joint work with Sivaraman Balakrishnan, Adityanand Guntuboyina and Martin J. Wainwright)


Nihar B. Shah is a fifth year PhD student at UC Berkeley, working with Martin Wainwright and Kannan Ramchandran. His research interests include statistics, machine learning and information theory, with applications to crowdsourcing. He is the recipient of the Berkeley fellowship 2011-13, the Microsoft Research PhD fellowship 2014-16, the IEEE Data Storage Best paper and Best student paper awards for the years 2011/2012, and the SVC Aiya Medal from the Indian Institute of Science in 2010.