Timezone: »

 
Poster
Identity testing for Mallows model
Róbert Busa-Fekete · Dimitris Fotakis · Balazs Szorenyi · Emmanouil Zampetakis

Thu Dec 09 04:30 PM -- 06:00 PM (PST) @
in Poster Session 7 »

In this paper, we devise identity tests for ranking data that is generated from Mallows model both in the \emph{asymptotic} and \emph{non-asymptotic} settings. First we consider the case when the central ranking is known, and devise two algorithms for testing the spread parameter of the Mallows model. The first one is obtained by constructing a Uniformly Most Powerful Unbiased (UMPU) test in the asymptotic setting and then converting it into a sample-optimal non-asymptotic identity test. The resulting test is, however, impractical even for medium sized data, because it requires computing the distribution of the sufficient statistic. The second non-asymptotic test is derived from an optimal learning algorithm for the Mallows model. This test is both easy to compute and is sample-optimal for a wide range of parameters. Next, we consider testing Mallows models for the unknown central ranking case. This case can be tackled in the asymptotic setting by introducing a bias that exponentially decays with the sample size. We support all our findings with extensive numerical experiments and show that the proposed tests scale gracefully with the number of items to be ranked.

Keywords:

Author Information

Róbert Busa-Fekete (Google Research)
Dimitris Fotakis (National Technical University of Athens)
Balazs Szorenyi (Yahoo Research)

* 2018 - Research Scientist at Yahoo Research * 2014-2017 Academic visitor at Technion * 2012-2013 Postdoc at Inria Lille * 2008-2009 Postdoc at Ruhr-University Bochum * 2003-2017 Research Assistant/Fellow at Research Group on AI at the University of Szeged Industrial projects: * developing/implementing ML solutions for prediction in online advertising Academic interests: * theoretical problems in machine learning * bandits * reinforcement learning

Emmanouil Zampetakis (UC Berkeley)

More from the Same Authors