Timezone: »
Poster
Private and Non-private Uniformity Testing for Ranking Data
Róbert Busa-Fekete · Dimitris Fotakis · Emmanouil Zampetakis
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.
Author Information
Róbert Busa-Fekete (Google Research)
Dimitris Fotakis (National Technical University of Athens)
Emmanouil Zampetakis (UC Berkeley)
More from the Same Authors
-
2021 : Population Level Privacy Leakage in Binary Classification wtih Label Noise »
Róbert Busa-Fekete · Andres Munoz Medina · Umar Syed · Sergei Vassilvitskii -
2021 : On the Pitfalls of Label Differential Privacy »
Andres Munoz Medina · Róbert Busa-Fekete · Umar Syed · Sergei Vassilvitskii -
2021 : Estimation of Standard Asymmetric Auction Models »
Yeshwanth Cherapanamjeri · Constantinos Daskalakis · Andrew Ilyas · Emmanouil Zampetakis -
2021 : Estimation of Standard Asymmetric Auction Models »
Yeshwanth Cherapanamjeri · Constantinos Daskalakis · Andrew Ilyas · Emmanouil Zampetakis -
2022 Poster: Private and Communication-Efficient Algorithms for Entropy Estimation »
Gecia Bravo-Hermsdorff · Róbert Busa-Fekete · Mohammad Ghavamzadeh · Andres Munoz Medina · Umar Syed -
2022 Poster: Linear Label Ranking with Bounded Noise »
Dimitris Fotakis · Alkis Kalavasis · Vasilis Kontonis · Christos Tzamos -
2022 Poster: Regret Bounds for Multilabel Classification in Sparse Label Regimes »
Róbert Busa-Fekete · Heejin Choi · Krzysztof Dembczynski · Claudio Gentile · Henry Reeve · Balazs Szorenyi -
2022 Poster: Perfect Sampling from Pairwise Comparisons »
Dimitris Fotakis · Alkis Kalavasis · Christos Tzamos -
2021 : Population Level Privacy Leakage in Binary Classification wtih Label Noise »
Róbert Busa-Fekete · Andres Munoz Medina · Umar Syed · Sergei Vassilvitskii -
2021 : Spotlight 4: Estimation of Standard Asymmetric Auction Models »
Yeshwanth Cherapanamjeri · Constantinos Daskalakis · Andrew Ilyas · Emmanouil Zampetakis -
2021 Poster: Identity testing for Mallows model »
Róbert Busa-Fekete · Dimitris Fotakis · Balazs Szorenyi · Emmanouil Zampetakis -
2021 : On the Pitfalls of Label Differential Privacy »
Andres Munoz Medina · Róbert Busa-Fekete · Umar Syed · Sergei Vassilvitskii -
2020 Poster: Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent »
Dimitris Fotakis · Thanasis Lianeas · Georgios Piliouras · Stratis Skoulakis -
2018 Poster: A no-regret generalization of hierarchical softmax to extreme multi-label classification »
Marek Wydmuch · Kalina Jasinska-Kobus · Mikhail Kuznetsov · Róbert Busa-Fekete · Krzysztof Dembczynski -
2018 Poster: Distributed Stochastic Optimization via Adaptive SGD »
Ashok Cutkosky · Róbert Busa-Fekete -
2015 Poster: Online F-Measure Optimization »
Róbert Busa-Fekete · Balázs Szörényi · Krzysztof Dembczynski · Eyke Hüllermeier -
2015 Poster: Online Rank Elicitation for Plackett-Luce: A Dueling Bandits Approach »
Balázs Szörényi · Róbert Busa-Fekete · Adil Paul · Eyke Hüllermeier