Timezone: »

 
Poster
Private and Non-private Uniformity Testing for Ranking Data
Róbert Busa-Fekete · Dimitris Fotakis · Emmanouil Zampetakis

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
in Poster Session 6 »
We study the problem of uniformity testing for statistical data that consists of rankings over $m$ items where the alternative class is restricted to Mallows models with single parameter. Testing ranking data is challenging because of the size of the large domain that is factorial in $m$, therefore the tester needs to take advantage of some structure of the alternative class. We show that uniform distribution can be distinguished from Mallows model with $O(m^{-1/2})$ samples based on simple pairwise statistics, which allows us to test uniformity using only two samples, if $m$ is large enough. We also consider uniformity testing with central and locally differential private (DP) constraints. We present a central DP algorithm that requires $O\left(\max \{ 1/\epsilon_0, 1/\sqrt{m} \} \right)$ where $\epsilon_0$ is the privacy budget parameter. Interestingly, our uniformity testing algorithm is straightforward to apply in the local DP scenario by its nature, since it works with binary statistics that is extracted from the ranking data. We carry out large-scale experiments, including $m=10000$, to show that these testing algorithms scales very gracefully with the number of items.
Keywords: Privacy

Author Information

Róbert Busa-Fekete (Google Research)
Dimitris Fotakis (National Technical University of Athens)
Emmanouil Zampetakis (UC Berkeley)

More from the Same Authors