Discrete Distribution Estimation under Local Privacy

Abstract

The collection and analysis of user data drives improvements in the app and web ecosystems, but comes with risks to privacy. This paper examines discrete distribution estimation under local privacy, a setting wherein service providers can learn the distribution of a categorical statistic of interest without collecting the underlying data. We present new mechanisms, including hashed K-ary Randomized Response (KRR), that empirically meet or exceed the utility of existing mechanisms at all privacy levels. New theoretical results demonstrate the order-optimality of KRR and the existing RAPPOR mechanism at different privacy regimes.

23 pages, 12 figures, submitted to ICML 2016 (under review)

Cited by in corpus (41)

• LoPub: High-Dimensional Crowdsourced Data Publication with Local Differential Privacy
• Context-Aware Generative Adversarial Privacy
• A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis
• Mutual Information Optimally Local Private Discrete Distribution Estimation
• Local Differential Privacy and Its Applications: A Comprehensive Survey
• Breaking the Communication-Privacy-Accuracy Trilemma
• Improving the utility of locally differentially private protocols for longitudinal and multidimensional frequency estimates
• Fair Learning with Private Demographic Data
• The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation
• On the Power of Multiple Anonymous Messages
• Differentially Private Testing of Identity and Closeness of Discrete Distributions
• Differential Privacy Techniques for Cyber Physical Systems: A Survey
• BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model
• Learning discrete distributions: user vs item-level privacy
• Utility-Optimized Local Differential Privacy Mechanisms for Distribution Estimation
• Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy
• Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible
• Lower Bounds for Learning Distributions under Communication Constraints via Fisher Information
• Federated Heavy Hitters Discovery with Differential Privacy
• Asymptotically optimal private estimation under mean square loss
• Toward Evaluating Re-identification Risks in the Local Privacy Model
• Locally Differentially Private Analysis of Graph Statistics
• Private Identity Testing for High-Dimensional Distributions
• Locality Sensitive Hashing with Extended Differential Privacy
• Differentially Private Assouad, Fano, and Le Cam
• Aggregating Votes with Local Differential Privacy: Usefulness, Soundness vs. Indistinguishability
• Deep Learning with Label Differential Privacy
• Data Poisoning Attacks to Local Differential Privacy Protocols
• Context-Aware Local Differential Privacy
• Lossless Compression of Efficient Private Local Randomizers
• Local Information Privacy and Its Application to Privacy-Preserving Data Aggregation
• Privacy-preserving Stochastic Gradual Learning
• Local Differential Privacy for Regret Minimization in Reinforcement Learning
• Building a Collaborative Phone Blacklisting System with Local Differential Privacy
• Communication-Efficient Triangle Counting under Local Differential Privacy
• Optimal locally private estimation under ${\ell }_p$ loss for $1\le p\le 2$
• Strong Privacy and Utility Guarantee: Over-the-Air Statistical Estimation
• Designing a Location Trace Anonymization Contest
• Optimal Compression of Locally Differentially Private Mechanisms
• Preventing Manipulation Attack in Local Differential Privacy using Verifiable Randomization Mechanism
• Partial sensitivity analysis in differential privacy