Timezone: »
The Randomized Response algorithm (RR) [Warner] is a classical technique to improve robustness in survey aggregation, and has been widely adopted in applications with differential privacy guarantees. We propose a novel algorithm, \emph{Randomized Response with Prior} (RRP), which can provide more accurate results while maintaining the same level of privacy guaranteed by RR. We then apply RRP to learn neural networks with \emph{label} differential privacy (LDP), and show that when only the label needs to be protected, the model performance can be significantly improved over the previous state-of-the-art private baselines. Moreover, we study different ways to obtain priors, which when used with RRP can additionally improve the model performance, further reducing the accuracy gap between private and non-private models. We complement the empirical results with theoretical analysis showing that LDP is provably easier than protecting both the inputs and labels.
Author Information
Badih Ghazi (Google)
Noah Golowich (Massachusetts Institute of Technology)
Ravi Kumar (Google)
Pasin Manurangsi (Google Research)
Chiyuan Zhang (Google Research)
More from the Same Authors
-
2021 : User-Level Private Learning via Correlated Sampling »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2023 : Counterfactual Memorization in Neural Language Models »
Chiyuan Zhang · Daphne Ippolito · Katherine Lee · Matthew Jagielski · Florian Tramer · Nicholas Carlini -
2023 : On the Reproducibility of Data Valuation under Learning Stochasticity »
Jiachen Wang · Feiyang Kang · Chiyuan Zhang · Ruoxi Jia · Prateek Mittal -
2023 Poster: Can Neural Network Memorization Be Localized? »
Pratyush Maini · Michael Mozer · Hanie Sedghi · Zachary Lipton · Zico Kolter · Chiyuan Zhang -
2023 Poster: Bandit Online Linear Optimization with Hints and Queries »
Aditya Bhaskara · Ashok Cutkosky · Ravi Kumar · Manish Purohit -
2023 Poster: On User-Level Private Convex Optimization »
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi · Raghu Meka · Chiyuan Zhang -
2022 Workshop: Knowledge Retrieval and Language Models »
Maithra Raghu · Urvashi Khandelwal · Chiyuan Zhang · Matei Zaharia · Alexander Rush -
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: 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 -
2021 Spotlight: 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 -
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: Understanding Invariance via Feedforward Inversion of Discriminatively Trained Classifiers »
Piotr Teterwak · Chiyuan Zhang · Dilip Krishnan · Michael Mozer -
2021 Poster: Light RUMs »
Flavio Chierichetti · Ravi Kumar · Andrew Tomkins -
2021 Poster: Characterizing Structural Regularities of Labeled Data in Overparameterized Models »
Ziheng Jiang · Chiyuan Zhang · Kunal Talwar · Michael Mozer -
2021 Spotlight: Understanding Invariance via Feedforward Inversion of Discriminatively Trained Classifiers »
Piotr Teterwak · Chiyuan Zhang · Dilip Krishnan · Michael Mozer -
2021 Spotlight: Light RUMs »
Flavio Chierichetti · Ravi Kumar · Andrew Tomkins -
2021 Oral: Characterizing Structural Regularities of Labeled Data in Overparameterized Models »
Ziheng Jiang · Chiyuan Zhang · Kunal Talwar · Michael Mozer -
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: Machine Theory of Mind »
Neil Rabinowitz · Frank Perbet · Francis Song · Chiyuan Zhang · S. M. Ali Eslami · Matthew Botvinick -
2018 Poster: Learning a Mixture of Two Multinomial Logits »
Flavio Chierichetti · Ravi Kumar · Andrew Tomkins -
2018 Oral: Machine Theory of Mind »
Neil Rabinowitz · Frank Perbet · Francis Song · Chiyuan Zhang · S. M. Ali Eslami · Matthew Botvinick -
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