Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation

Abstract

We provide a detailed study of the estimation of probability distributions---discrete and continuous---in a stringent setting in which data is kept private even from the statistician. We give sharp minimax rates of convergence for estimation in these locally private settings, exhibiting fundamental tradeoffs between privacy and convergence rate, as well as providing tools to allow movement along the privacy-statistical efficiency continuum. One of the consequences of our results is that Warner's classical work on randomized response is an optimal way to perform survey sampling while maintaining privacy of the respondents.

27 pages, 1 figure

References in corpus (2)

• Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates
• Convergence Rates for Differentially Private Statistical Estimation

Cited by in corpus (30)

• Mobile Sensor Data Anonymization
• Collecting Telemetry Data Privately
• Discrete Distribution Estimation under Local Privacy
• Distributed Statistical Machine Learning in Adversarial Settings: Byzantine Gradient Descent
• Context-Aware Generative Adversarial Privacy
• Mutual Information Optimally Local Private Discrete Distribution Estimation
• Collecting and Analyzing Multidimensional Data with Local Differential Privacy
• Local Differential Privacy based Federated Learning for Internet of Things
• Reviewing and Improving the Gaussian Mechanism for Differential Privacy
• Locally Differentially Private Frequency Estimation with Consistency
• Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy
• Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible
• Locally Differentially Private (Contextual) Bandits Learning
• Asymptotically optimal private estimation under mean square loss
• FedXGBoost: Privacy-Preserving XGBoost for Federated Learning
• Locally Private Hypothesis Testing
• To Split or Not to Split: The Impact of Disparate Treatment in Classification
• Mobile Privacy-Preserving Crowdsourced Data Collection in the Smart City
• Locally Differentially-Private Randomized Response for Discrete Distribution Learning
• Federated Extra-Trees with Privacy Preserving
• Answering Multi-Dimensional Range Queries under Local Differential Privacy
• Locally differentially private estimation of nonlinear functionals of discrete distributions
• Integral Privacy for Sampling
• LocationSafe: Granular Location Privacy for IoT Devices
• Anonymized Local Privacy
• PAS-MC: Privacy-preserving Analytics Stream for the Mobile Cloud
• Participation Cost Estimation: Private Versus Non-Private Study
• Pufferfish Privacy Mechanisms for Correlated Data
• Distributed Differential Privacy By Sampling
• A Minimax Distortion View of Differentially Private Query Release