Heavy Hitters and the Structure of Local Privacy

DOI10.1145/3344722MaRDI QIDQ4973047zbMATH OpenOpenAlexWikidataFDO

Authors Mark Bun, Jelani Nelson, Uri Stemmer

Publication date 2 December 2019

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.04740

zbMATH Keywords

differential privacyheavy hitterslocal model

Mathematics Subject Classification ID

Privacy of data (68P27)

Abstract: We present a new locally differentially private algorithm for the heavy hitters problem which achieves optimal worst-case error as a function of all standardly considered parameters. Prior work obtained error rates which depend optimally on the number of users, the size of the domain, and the privacy parameter, but depend sub-optimally on the failure probability. We strengthen existing lower bounds on the error to incorporate the failure probability, and show that our new upper bound is tight with respect to this parameter as well. Our lower bound is based on a new understanding of the structure of locally private protocols. We further develop these ideas to obtain the following general results beyond heavy hitters. $$ Advanced Grouposition: In the local model, group privacy for $k$ users degrades proportionally to $approxsqrtk$, instead of linearly in $k$ as in the central model. Stronger group privacy yields improved max-information guarantees, as well as stronger lower bounds (via "packing arguments"), over the central model. $$ Building on a transformation of Bassily and Smith (STOC 2015), we give a generic transformation from any non-interactive approximate-private local protocol into a pure-private local protocol. Again in contrast with the central model, this shows that we cannot obtain more accurate algorithms by moving from pure to approximate local privacy.

Recommendations

• Practical locally private heavy hitters
• Distributed private heavy hitters
• Extremal mechanisms for local differential privacy
• On robustness and local differential privacy
• Exponential Separations in Local Privacy
• On the structure of the privacy hierarchy
• Exponential Separations in Local Differential Privacy
• Corrupt bandits for preserving local privacy

Cited in

(12)

• Empirical risk minimization in the non-interactive local model of differential privacy
• PAC learning halfspaces in non-interactive local differential privacy model with public unlabeled data
• Fast Private Norm Estimation and Heavy Hitters
• Channel simulation: theory and applications to lossy compression and differential privacy
• On distributed differential privacy and counting distinct elements
• Distributed private heavy hitters
• Local, private, efficient protocols for succinct histograms
• Forty years of frequent items
• Amplification by shuffling: from local to central differential privacy via anonymity
• Practical locally private heavy hitters
• On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy
• Pure-DP aggregation in the shuffle model: error-optimal and communication-efficient

This page was built for publication: Heavy Hitters and the Structure of Local Privacy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4973047)