Timezone: »
Local differential privacy has recently surfaced as a strong measure of privacy in contexts where personal information remains private even from data analysts. Working in a setting where the data providers and data analysts want to maximize the utility of statistical inferences performed on the released data, we study the fundamental tradeoff between local differential privacy and information theoretic utility functions. We introduce a family of extremal privatization mechanisms, which we call staircase mechanisms, and prove that it contains the optimal privatization mechanism that maximizes utility. We further show that for all information theoretic utility functions studied in this paper, maximizing utility is equivalent to solving a linear program, the outcome of which is the optimal staircase mechanism. However, solving this linear program can be computationally expensive since it has a number of variables that is exponential in the data size. To account for this, we show that two simple staircase mechanisms, the binary and randomized response mechanisms, are universally optimal in the high and low privacy regimes, respectively, and well approximate the intermediate regime.
Author Information
Peter Kairouz (Google)
Peter Kairouz is a Google Research Scientist working on decentralized, privacy-preserving, and robust machine learning algorithms. Prior to Google, his research largely focused on building decentralized technologies for anonymous broadcasting over complex networks, understanding the fundamental trade-off between differential privacy and utility of learning algorithms, and leveraging state-of-the-art deep generative models for data-driven privacy and fairness.
Sewoong Oh (University of Washington)
Pramod Viswanath (UIUC)
More from the Same Authors
-
2021 : Communication Efficient Federated Learning with Secure Aggregation and Differential Privacy »
Wei-Ning Chen · Christopher Choquette-Choo · Peter Kairouz -
2023 Competition: NeurIPS 2023 Machine Unlearning Competition »
Eleni Triantafillou · Fabian Pedregosa · Meghdad Kurmanji · Kairan ZHAO · Gintare Karolina Dziugaite · Peter Triantafillou · Ioannis Mitliagkas · Vincent Dumoulin · Lisheng Sun · Peter Kairouz · Julio C Jacques Junior · Jun Wan · Sergio Escalera · Isabelle Guyon -
2022 : Invited Talk: Peter Kairouz - The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning »
Peter Kairouz -
2021 Poster: Pointwise Bounds for Distribution Estimation under Communication Constraints »
Wei-Ning Chen · Peter Kairouz · Ayfer Ozgur -
2021 Poster: The Skellam Mechanism for Differentially Private Federated Learning »
Naman Agarwal · Peter Kairouz · Ken Liu -
2020 Tutorial: (Track1) Federated Learning and Analytics: Industry Meets Academia Q&A »
Peter Kairouz · Brendan McMahan · Virginia Smith -
2020 Poster: Privacy Amplification via Random Check-Ins »
Borja Balle · Peter Kairouz · Brendan McMahan · Om Thakkar · Abhradeep Guha Thakurta -
2020 Poster: Breaking the Communication-Privacy-Accuracy Trilemma »
Wei-Ning Chen · Peter Kairouz · Ayfer Ozgur -
2020 Tutorial: (Track1) Federated Learning and Analytics: Industry Meets Academia »
Brendan McMahan · Virginia Smith · Peter Kairouz -
2019 : Lunch break and poster »
Felix Sattler · Khaoula El Mekkaoui · Neta Shoham · Cheng Hong · Florian Hartmann · Boyue Li · Daliang Li · Sebastian Caldas Rivera · Jianyu Wang · Kartikeya Bhardwaj · Tribhuvanesh Orekondy · YAN KANG · Dashan Gao · Mingshu Cong · Xin Yao · Songtao Lu · JIAHUAN LUO · Shicong Cen · Peter Kairouz · Yihan Jiang · Tzu Ming Hsu · Aleksei Triastcyn · Yang Liu · Ahmed Khaled Ragab Bayoumi · Zhicong Liang · Boi Faltings · Seungwhan Moon · Suyi Li · Tao Fan · Tianchi Huang · Chunyan Miao · Hang Qi · Matthew Brown · Lucas Glass · Junpu Wang · Wei Chen · Radu Marculescu · tomer avidor · Xueyang Wu · Mingyi Hong · Ce Ju · John Rush · Ruixiao Zhang · Youchi ZHOU · Françoise Beaufays · Yingxuan Zhu · Lei Xia -
2019 Poster: Turbo Autoencoder: Deep learning based channel codes for point-to-point communication channels »
Yihan Jiang · Hyeji Kim · Himanshu Asnani · Sreeram Kannan · Sewoong Oh · Pramod Viswanath -
2018 Poster: Estimators for Multivariate Information Measures in General Probability Spaces »
Arman Rahimzamani · Himanshu Asnani · Pramod Viswanath · Sreeram Kannan -
2018 Poster: Deepcode: Feedback Codes via Deep Learning »
Hyeji Kim · Yihan Jiang · Sreeram Kannan · Sewoong Oh · Pramod Viswanath -
2017 : New perspective from Blackwell's "comparisons of experiments" on generative adversarial networks »
Sewoong Oh -
2017 Poster: Deanonymization in the Bitcoin P2P Network »
Giulia Fanti · Pramod Viswanath -
2017 Poster: Optimal Sample Complexity of M-wise Data for Top-K Ranking »
Minje Jang · Sunghyun Kim · Changho Suh · Sewoong Oh -
2017 Poster: Estimating Mutual Information for Discrete-Continuous Mixtures »
Weihao Gao · Sreeram Kannan · Sewoong Oh · Pramod Viswanath -
2017 Poster: Matrix Norm Estimation from a Few Entries »
Ashish Khetan · Sewoong Oh -
2017 Spotlight: Estimating Mutual Information for Discrete-Continuous Mixtures »
Weihao Gao · Sreeram Kannan · Sewoong Oh · Pramod Viswanath -
2017 Spotlight: Matrix Norm Estimation from a Few Entries »
Ashish Khetan · Sewoong Oh -
2017 Poster: Discovering Potential Correlations via Hypercontractivity »
Hyeji Kim · Weihao Gao · Sreeram Kannan · Sewoong Oh · Pramod Viswanath -
2016 Poster: Breaking the Bandwidth Barrier: Geometrical Adaptive Entropy Estimation »
Weihao Gao · Sewoong Oh · Pramod Viswanath -
2016 Poster: Computational and Statistical Tradeoffs in Learning to Rank »
Ashish Khetan · Sewoong Oh -
2016 Poster: Achieving budget-optimality with adaptive schemes in crowdsourcing »
Ashish Khetan · Sewoong Oh -
2015 Workshop: Non-convex Optimization for Machine Learning: Theory and Practice »
Anima Anandkumar · Niranjan Uma Naresh · Kamalika Chaudhuri · Percy Liang · Sewoong Oh -
2015 Poster: Secure Multi-party Differential Privacy »
Peter Kairouz · Sewoong Oh · Pramod Viswanath -
2015 Poster: Collaboratively Learning Preferences from Ordinal Data »
Sewoong Oh · Kiran Thekumparampil · Jiaming Xu -
2014 Workshop: Analysis of Rank Data: Confluence of Social Choice, Operations Research, and Machine Learning »
Shivani Agarwal · Hossein Azari Soufiani · Guy Bresler · Sewoong Oh · David Parkes · Arun Rajkumar · Devavrat Shah -
2014 Poster: Provable Tensor Factorization with Missing Data »
Prateek Jain · Sewoong Oh -
2014 Poster: Minimax-optimal Inference from Partial Rankings »
Bruce Hajek · Sewoong Oh · Jiaming Xu -
2014 Poster: Learning Mixed Multinomial Logit Model from Ordinal Data »
Sewoong Oh · Devavrat Shah -
2012 Poster: Iterative ranking from pair-wise comparisons »
Sahand N Negahban · Sewoong Oh · Devavrat Shah -
2012 Spotlight: Iterative ranking from pair-wise comparisons »
Sahand N Negahban · Sewoong Oh · Devavrat Shah -
2011 Poster: Iterative Learning for Reliable Crowdsourcing Systems »
David R Karger · Sewoong Oh · Devavrat Shah -
2011 Oral: Iterative Learning for Reliable Crowdsourcing Systems »
David R Karger · Sewoong Oh · Devavrat Shah -
2009 Poster: Matrix Completion from Noisy Entries »
Raghunandan Keshavan · Andrea Montanari · Sewoong Oh