Mutual Information Optimally Local Private Discrete Distribution Estimation

Abstract

Consider statistical learning (e.g. discrete distribution estimation) with local $\epsilon$-differential privacy, which preserves each data provider's privacy locally, we aim to optimize statistical data utility under the privacy constraints. Specifically, we study maximizing mutual information between a provider's data and its private view, and give the exact mutual information bound along with an attainable mechanism: $k$-subset mechanism as results. The mutual information optimal mechanism randomly outputs a size $k$ subset of the original data domain with delicate probability assignment, where $k$ varies with the privacy level $\epsilon$ and the data domain size $d$. After analysing the limitations of existing local private mechanisms from mutual information perspective, we propose an efficient implementation of the $k$-subset mechanism for discrete distribution estimation, and show its optimality guarantees over existing approaches.

submitted to NIPS2016

References in corpus (5)

• Differential Privacy: An Economic Method for Choosing Epsilon
• Discrete Distribution Estimation under Local Privacy
• Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application
• Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation
• What Can We Learn Privately?

Cited by in corpus (18)

• A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis
• Local Differential Privacy and Its Applications: A Comprehensive Survey
• Breaking the Communication-Privacy-Accuracy Trilemma
• Locally Differentially Private Frequency Estimation with Consistency
• Optimal Schemes for Discrete Distribution Estimation under Locally Differential Privacy
• Information-theoretic metrics for Local Differential Privacy protocols
• Lower Bounds for Learning Distributions under Communication Constraints via Fisher Information
• Asymptotically optimal private estimation under mean square loss
• Private Identity Testing for High-Dimensional Distributions
• Locality Sensitive Hashing with Extended Differential Privacy
• Differentially Private Assouad, Fano, and Le Cam
• Revealing the True Cost of Locally Differentially Private Protocols: An Auditing Perspective
• Context-Aware Local Differential Privacy
• Exactly Optimal and Communication-Efficient Private Estimation via Block Designs
• Lossless Compression of Efficient Private Local Randomizers
• Fair and Differentially Private Distributed Frequency Estimation
• Privately Learning Mixtures of Axis-Aligned Gaussians
• Optimal locally private estimation under ${\ell }_p$ loss for $1\le p\le 2$