Private and Non-private Uniformity Testing for Ranking Data
Dec 6, 2021
Speakers
Róbert Busa-Fekete
Speaker · 0 followers
Dimitris Fotakis
Speaker · 0 followers
Manolis Zampetakis
Speaker · 0 followers
About
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(max{ 1/ϵ_0, 1/√(m)}) where ϵ_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.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 sta…
Organizer
NeurIPS 2021
Account · 1.9k followers
About NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Occlusion-Aware Crowd Navigation Using People as Sensors
Watch later
Ye-Ji Mun, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Learning Transferable Features for Point Cloud Detection via 3D Contrastive Co-training
Watch later
Zeng Yihan, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Intuitive physics: no one tool for the job
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Drop-DTW: Aligning Common Signal Between Sequences While Dropping Outliers
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Class-agnostic Reconstruction of Dynamic Objects from Videos
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Scaling Gaussian Process Regression with Derivative Information Using Variational Inference
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%