Timezone: »
We study the privacy limitations of label differential privacy, which has emerged as an intermediate trust model between local and central differential privacy, where only the label of each training example is protected (and the features are assumed to be public). We show that the guarantees provided by label DP are significantly weaker than they appear, as an adversary can "un-noise" the perturbed labels. Formally we show that the privacy loss has a close connection with Jeffreys' divergence of the conditional distribution between positive and negative labels, which allows explicit formulation of the trade-off between utility and privacy in this setting. Our results suggest how to select public features that optimize this trade-off. But we still show that there is no free lunch---instances where label differential privacy guarantees are strong are exactly those where a good classifier does not exist. We complement the negative results with a non-parametric estimator for the true privacy loss, and apply our techniques on large-scale benchmark data to demonstrate how toachieve a desired privacy protection.
Author Information
Andres Munoz Medina (Google)
Róbert Busa-Fekete (Google Research)
Umar Syed (Google Research)
Sergei Vassilvitskii (Google)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 : On the Pitfalls of Label Differential Privacy »
Tue. Dec 7th 07:30 -- 07:45 PM Room
More from the Same Authors
-
2021 : A Joint Exponential Mechanism for Differentially Private Top-k Set »
Andres Munoz Medina · Matthew Joseph · Jennifer Gillenwater · Monica Ribero Diaz -
2021 : Population Level Privacy Leakage in Binary Classification wtih Label Noise »
Róbert Busa-Fekete · Andres Munoz Medina · Umar Syed · Sergei Vassilvitskii -
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: 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: Algorithms with Prediction Portfolios »
Michael Dinitz · Sungjin Im · Thomas Lavastida · Benjamin Moseley · Sergei Vassilvitskii -
2022 Poster: Learning Predictions for Algorithms with Predictions »
Misha Khodak · Maria-Florina Balcan · Ameet Talwalkar · Sergei Vassilvitskii -
2022 Affinity Workshop: LatinX in AI »
Maria Luisa Santiago · Juan Banda · CJ Barberan · MIGUEL GONZALEZ-MENDOZA · Caio Davi · Sara Garcia · Jorge Diaz · Fanny Nina Paravecino · Carlos Miranda · Gissella Bejarano Nicho · Fabian Latorre · Andres Munoz Medina · Abraham Ramos · Laura Montoya · Isabel Metzger · Andres Marquez · Miguel Felipe Arevalo-Castiblanco · Jorge Mendez · Karla Caballero · Atnafu Lambebo Tonja · Germán Olivo · Karla Caballero Barajas · Francisco Zabala -
2021 : Population Level Privacy Leakage in Binary Classification wtih Label Noise »
Róbert Busa-Fekete · Andres Munoz Medina · Umar Syed · Sergei Vassilvitskii -
2021 Poster: Robust Online Correlation Clustering »
Silvio Lattanzi · Benjamin Moseley · Sergei Vassilvitskii · Yuyan Wang · Rudy Zhou -
2021 Poster: Identity testing for Mallows model »
Róbert Busa-Fekete · Dimitris Fotakis · Balazs Szorenyi · Emmanouil Zampetakis -
2021 Poster: Private and Non-private Uniformity Testing for Ranking Data »
Róbert Busa-Fekete · Dimitris Fotakis · Emmanouil Zampetakis -
2021 Oral: Faster Matchings via Learned Duals »
Michael Dinitz · Sungjin Im · Thomas Lavastida · Benjamin Moseley · Sergei Vassilvitskii -
2021 Social: Latinx in AI Social »
Andres Munoz Medina · Maria Luisa Santiago -
2021 Poster: Faster Matchings via Learned Duals »
Michael Dinitz · Sungjin Im · Thomas Lavastida · Benjamin Moseley · Sergei Vassilvitskii -
2021 : Closing Remarks »
Andres Munoz Medina -
2021 : Q&A Oral presentations »
Matias Valdenegro-Toro · Andres Munoz Medina · Johan Obando Ceron · Anil Batra -
2021 Affinity Workshop: LatinX in AI (LXAI) Research @ NeurIPS 2021 »
Maria Luisa Santiago · Andres Munoz Medina · Laura Montoya · Karla Caballero Barajas · Isabel Metzger · Jose Gallego-Posada · Juan Banda · Gabriela Vega · Amanda Duarte · Patrick Feeney · Lourdes Ramírez Cerna · Walter M Mayor · Omar U. Florez · Rosina Weber · Rocio Zorrilla -
2019 Poster: Differentially Private Covariance Estimation »
Kareem Amin · Travis Dick · Alex Kulesza · Andres Munoz Medina · Sergei Vassilvitskii -
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 -
2017 Poster: Revenue Optimization with Approximate Bid Predictions »
Andres Munoz Medina · Sergei Vassilvitskii -
2017 Poster: Statistical Cost Sharing »
Eric Balkanski · Umar Syed · Sergei Vassilvitskii -
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 -
2014 Poster: Repeated Contextual Auctions with Strategic Buyers »
Kareem Amin · Afshin Rostamizadeh · Umar Syed -
2014 Poster: Multi-Class Deep Boosting »
Vitaly Kuznetsov · Mehryar Mohri · Umar Syed -
2013 Poster: Learning Prices for Repeated Auctions with Strategic Buyers »
Kareem Amin · Afshin Rostamizadeh · Umar Syed