Timezone: »
Poster
Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message
Badih Ghazi · Ravi Kumar · Pasin Manurangsi · Rasmus Pagh · Amer Sinha
The shuffle model of differential privacy has attracted attention in the literature due to it being a middle ground between the well-studied central and local models. In this work, we study the problem of summing (aggregating) real numbers or integers, a basic primitive in numerous machine learning tasks, in the shuffle model. We give a protocol achieving error arbitrarily close to that of the (Discrete) Laplace mechanism in central differential privacy, while each user only sends 1 + o(1) short messages in expectation.
Author Information
Badih Ghazi (Google)
Ravi Kumar (Google)
Pasin Manurangsi (Google Research)
Rasmus Pagh (University of Copenhagen)
Amer Sinha (Google)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Spotlight: Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message »
Fri. Jul 23rd 01:20 -- 01:25 AM Room
More from the Same Authors
-
2021 : Differentially private sparse vectors with low error, optimal space, and fast access »
Martin Aumüller · Christian Lebeda · Rasmus Pagh -
2021 : Randomized Response with Prior and Applications to Learning with Label Differential Privacy »
Badih Ghazi · Noah Golowich · Ravi Kumar · Pasin Manurangsi · Chiyuan Zhang -
2021 : User-Level Private Learning via Correlated Sampling »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2022 Poster: Parsimonious Learning-Augmented Caching »
Sungjin Im · Ravi Kumar · Aditya Petety · Manish Purohit -
2022 Poster: RUMs from Head-to-Head Contests »
Matteo Almanza · Flavio Chierichetti · Ravi Kumar · Alessandro Panconesi · Andrew Tomkins -
2022 Spotlight: RUMs from Head-to-Head Contests »
Matteo Almanza · Flavio Chierichetti · Ravi Kumar · Alessandro Panconesi · Andrew Tomkins -
2022 Spotlight: Parsimonious Learning-Augmented Caching »
Sungjin Im · Ravi Kumar · Aditya Petety · Manish Purohit -
2022 Poster: Faster Privacy Accounting via Evolving Discretization »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi -
2022 Spotlight: Faster Privacy Accounting via Evolving Discretization »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi -
2021 Poster: CountSketches, Feature Hashing and the Median of Three »
Kasper Green Larsen · Rasmus Pagh · Jakub Tětek -
2021 Spotlight: CountSketches, Feature Hashing and the Median of Three »
Kasper Green Larsen · Rasmus Pagh · Jakub Tětek -
2021 Poster: Locally Private k-Means in One Round »
Alisa Chang · Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2021 Oral: Locally Private k-Means in One Round »
Alisa Chang · Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2021 Poster: Light RUMs »
Flavio Chierichetti · Ravi Kumar · Andrew Tomkins -
2021 Spotlight: Light RUMs »
Flavio Chierichetti · Ravi Kumar · Andrew Tomkins -
2020 Poster: Online Learning with Imperfect Hints »
Aditya Bhaskara · Ashok Cutkosky · Ravi Kumar · Manish Purohit -
2020 Poster: Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi · Rasmus Pagh -
2019 Poster: Faster Algorithms for Binary Matrix Factorization »
Ravi Kumar · Rina Panigrahy · Ali Rahimi · David Woodruff -
2019 Oral: Faster Algorithms for Binary Matrix Factorization »
Ravi Kumar · Rina Panigrahy · Ali Rahimi · David Woodruff -
2018 Poster: Learning a Mixture of Two Multinomial Logits »
Flavio Chierichetti · Ravi Kumar · Andrew Tomkins -
2018 Oral: Learning a Mixture of Two Multinomial Logits »
Flavio Chierichetti · Ravi Kumar · Andrew Tomkins -
2017 Poster: Algorithms for $\ell_p$ Low-Rank Approximation »
Flavio Chierichetti · Sreenivas Gollapudi · Ravi Kumar · Silvio Lattanzi · Rina Panigrahy · David Woodruff -
2017 Talk: Algorithms for $\ell_p$ Low-Rank Approximation »
Flavio Chierichetti · Sreenivas Gollapudi · Ravi Kumar · Silvio Lattanzi · Rina Panigrahy · David Woodruff