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
The Information Theory Forum (IT-Forum) at Stanford ISL is an interdisciplinary academic forum which focuses on mathematical aspects of information processing. With a primary emphasis on information theory, we also welcome researchers from signal processing, learning and statistical inference, control and optimization to deliver talks at our forum. We also warmly welcome industrial affiliates in the above fields. The forum is typically held in Packard 202 every Friday at 1:00 pm during the academic year.
The Information Theory Forum is organized by graduate students Jiantao Jiao and Yanjun Han. To suggest speakers, please contact any of the students.
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.