Timezone: »
We study the Renyi Differential Privacy (RDP) for general discrete local mechanisms in the {\em shuffle} privacy model, where clients randomize their responses using a local differentially private (LDP) mechanism and the untrusted server only receives a random permutation (shuffle) of the client responses without association to each client. The principal result in this paper is the \emph{first} non-trivial RDP guarantee for general discrete local randomization mechanisms in the shuffled privacy model, and we develop new analysis techniques for deriving our results which could be of independent interest. In applications, such an RDP guarantee is most useful when we use it for composing several private interactions. We numerically demonstrate that, for important regimes, with composition our bound yields a significant improvement in privacy guarantee over the state-of-the-art approximate Differential Privacy (DP) guarantee (with standard composition) for shuffled models.
Author Information
Antonious Girgis (University of California, Los Angeles)
Deepesh Data (UCLA)
Suhas Diggavi (University of California, Los Angeles)
Ananda Theertha Suresh (Google Research)
Peter Kairouz (Google)
More from the Same Authors
-
2021 : Neural Network-based Estimation of the MMSE »
Mario Diaz · Peter Kairouz · Lalitha Sankar -
2021 : The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation »
Peter Kairouz · Ziyu Liu · Thomas Steinke -
2021 : Flexible Accuracy for Differential Privacy »
Aman Bansal · Rahul Chunduru · Deepesh Data · Manoj Prabhakaran -
2021 : Remember What You Want to Forget: Algorithms for Machine Unlearning »
Ayush Sekhari · Ayush Sekhari · Jayadev Acharya · Gautam Kamath · Ananda Theertha Suresh -
2021 : Practical and Private (Deep) Learning without Sampling orShuffling »
Peter Kairouz · Hugh B McMahan · Shuang Song · Om Dipakbhai Thakkar · Abhradeep Guha Thakurta · Zheng Xu -
2021 : Learning with User-Level Privacy »
Daniel A Levy · Ziteng Sun · Kareem Amin · Satyen Kale · Alex Kulesza · Mehryar Mohri · Ananda Theertha Suresh -
2021 : Industrial Booth (Google) »
Zheng Xu · Peter Kairouz -
2022 : Fair Universal Representations using Adversarial Models »
Monica Welfert · Peter Kairouz · Jiachun Liao · Chong Huang · Lalitha Sankar -
2023 : Unleashing the Power of Randomization in Auditing Differentially Private ML »
Krishna Pillutla · Galen Andrew · Peter Kairouz · Hugh B McMahan · Alina Oprea · Sewoong Oh -
2023 : Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation »
Wei-Ning Chen · Dan Song · Ayfer Ozgur · Peter Kairouz -
2023 : Federated Heavy Hitter Recovery under Linear Sketching »
Adria Gascon · Peter Kairouz · Ziteng Sun · Ananda Suresh -
2023 : Distributed Mean Estimation for Multi-Message Shuffled Privacy »
Antonious Girgis · Suhas Diggavi -
2023 : SpecTr: Fast Speculative Decoding via Optimal Transport »
Ziteng Sun · Ananda Suresh · Jae Ro · Ahmad Beirami · Himanshu Jain · Felix Xinnan Yu · Michael Riley · Sanjiv Kumar -
2023 : Panel Discussion »
Peter Kairouz · Song Han · Kamalika Chaudhuri · Florian Tramer -
2023 Workshop: Federated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Opportunities »
Zheng Xu · Peter Kairouz · Bo Li · Tian Li · John Nguyen · Jianyu Wang · Shiqiang Wang · Ayfer Ozgur -
2023 Poster: Subset-Based Instance Optimality in Private Estimation »
Travis Dick · Alex Kulesza · Ziteng Sun · Ananda Suresh -
2023 Poster: Federated Heavy Hitter Recovery under Linear Sketching »
Adria Gascon · Peter Kairouz · Ziteng Sun · Ananda Suresh -
2023 Poster: Private Federated Learning with Autotuned Compression »
Enayat Ullah · Christopher Choquette-Choo · Peter Kairouz · Sewoong Oh -
2023 Poster: Algorithms for bounding contribution for histogram estimation under user-level privacy »
Yuhan Liu · Ananda Suresh · Wennan Zhu · Peter Kairouz · Marco Gruteser -
2022 Poster: The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning »
Wei-Ning Chen · Christopher Choquette Choo · Peter Kairouz · Ananda Suresh -
2022 Poster: The Poisson Binomial Mechanism for Unbiased Federated Learning with Secure Aggregation »
Wei-Ning Chen · Ayfer Ozgur · Peter Kairouz -
2022 Spotlight: The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning »
Wei-Ning Chen · Christopher Choquette Choo · Peter Kairouz · Ananda Suresh -
2022 Oral: The Poisson Binomial Mechanism for Unbiased Federated Learning with Secure Aggregation »
Wei-Ning Chen · Ayfer Ozgur · Peter Kairouz -
2022 Poster: Correlated Quantization for Distributed Mean Estimation and Optimization »
Ananda Suresh · Ziteng Sun · Jae Ro · Felix Xinnan Yu -
2022 Spotlight: Correlated Quantization for Distributed Mean Estimation and Optimization »
Ananda Suresh · Ziteng Sun · Jae Ro · Felix Xinnan Yu -
2021 : Industrial Panel »
Nathalie Baracaldo · Shiqiang Wang · Peter Kairouz · Zheng Xu · Kshitiz Malik · Tao Zhang -
2021 : Contributed Talks Session 1 »
Marika Swanberg · Samuel Haney · Peter Kairouz -
2021 Poster: Practical and Private (Deep) Learning Without Sampling or Shuffling »
Peter Kairouz · Brendan McMahan · Shuang Song · Om Dipakbhai Thakkar · Abhradeep Guha Thakurta · Zheng Xu -
2021 Poster: The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation »
Peter Kairouz · Ziyu Liu · Thomas Steinke -
2021 Spotlight: A Discriminative Technique for Multiple-Source Adaptation »
Corinna Cortes · Mehryar Mohri · Ananda Theertha Suresh · Ningshan Zhang -
2021 Spotlight: The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation »
Peter Kairouz · Ziyu Liu · Thomas Steinke -
2021 Spotlight: Practical and Private (Deep) Learning Without Sampling or Shuffling »
Peter Kairouz · Brendan McMahan · Shuang Song · Om Dipakbhai Thakkar · Abhradeep Guha Thakurta · Zheng Xu -
2021 Poster: Byzantine-Resilient High-Dimensional SGD with Local Iterations on Heterogeneous Data »
Deepesh Data · Suhas Diggavi -
2021 Poster: A Discriminative Technique for Multiple-Source Adaptation »
Corinna Cortes · Mehryar Mohri · Ananda Theertha Suresh · Ningshan Zhang -
2021 Spotlight: Byzantine-Resilient High-Dimensional SGD with Local Iterations on Heterogeneous Data »
Deepesh Data · Suhas Diggavi -
2021 Spotlight: Relative Deviation Margin Bounds »
Corinna Cortes · Mehryar Mohri · Ananda Theertha Suresh -
2021 Poster: Relative Deviation Margin Bounds »
Corinna Cortes · Mehryar Mohri · Ananda Theertha Suresh -
2020 Poster: SCAFFOLD: Stochastic Controlled Averaging for Federated Learning »
Sai Praneeth Reddy Karimireddy · Satyen Kale · Mehryar Mohri · Sashank Jakkam Reddi · Sebastian Stich · Ananda Theertha Suresh -
2020 Poster: Context Aware Local Differential Privacy »
Jayadev Acharya · Kallista Bonawitz · Peter Kairouz · Daniel Ramage · Ziteng Sun -
2020 Poster: FedBoost: A Communication-Efficient Algorithm for Federated Learning »
Jenny Hamer · Mehryar Mohri · Ananda Theertha Suresh -
2019 Poster: Agnostic Federated Learning »
Mehryar Mohri · Gary Sivek · Ananda Suresh -
2019 Oral: Agnostic Federated Learning »
Mehryar Mohri · Gary Sivek · Ananda Suresh -
2017 Poster: Distributed Mean Estimation with Limited Communication »
Ananda Theertha Suresh · Felix Xinnan Yu · Sanjiv Kumar · Brendan McMahan -
2017 Poster: A Unified Maximum Likelihood Approach for Estimating Symmetric Properties of Discrete Distributions »
Jayadev Acharya · Hirakendu Das · Alon Orlitsky · Ananda Suresh -
2017 Poster: Maximum Selection and Ranking under Noisy Comparisons »
Moein Falahatgar · Alon Orlitsky · Venkatadheeraj Pichapati · Ananda Theertha Suresh -
2017 Talk: A Unified Maximum Likelihood Approach for Estimating Symmetric Properties of Discrete Distributions »
Jayadev Acharya · Hirakendu Das · Alon Orlitsky · Ananda Suresh -
2017 Talk: Distributed Mean Estimation with Limited Communication »
Ananda Theertha Suresh · Felix Xinnan Yu · Sanjiv Kumar · Brendan McMahan -
2017 Talk: Maximum Selection and Ranking under Noisy Comparisons »
Moein Falahatgar · Alon Orlitsky · Venkatadheeraj Pichapati · Ananda Theertha Suresh