# Discrete Distribution Estimation under Local Privacy

arXiv: https://arxiv.org/abs/1602.07387 · HTML: https://mlsanity.com/paper/1602.07387/

## Key facts

- Cited by 59 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2016.

## Built on by (most cited first, 30 of 59)

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation](https://mlsanity.com/paper/2102.06387/) (2021)
- [Deep Learning with Label Differential Privacy](https://mlsanity.com/paper/2102.06062/) (2021)
- [The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning](https://mlsanity.com/paper/2203.03761/) (2022)
- [Lossless Compression of Efficient Private Local Randomizers](https://mlsanity.com/paper/2102.12099/) (2021)
- [Differentially Private Regret Minimization in Episodic Markov Decision Processes](https://mlsanity.com/paper/2112.10599/) (2021)
- [Optimal Compression of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2111.00092/) (2021)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [A Survey on Privacy in Graph Neural Networks: Attacks, Preservation, and Applications](https://mlsanity.com/paper/2308.16375/) (2023)
- [Local Differential Privacy Is Equivalent to Contraction of Eγ-Divergence](https://mlsanity.com/paper/2102.01258/) (2021)
- [Privacy-Aware Compression for Federated Data Analysis](https://mlsanity.com/paper/2203.08134/) (2022)
- [Discrete Distribution Estimation under User-level Local Differential Privacy](https://mlsanity.com/paper/2211.03757/) (2022)
- [On the Renyi Differential Privacy of the Shuffle Model](https://mlsanity.com/paper/2105.05180/) (2021)
- [Private Graph Extraction via Feature Explanations](https://mlsanity.com/paper/2206.14724/) (2022)
- [Privately Learning Mixtures of Axis-Aligned Gaussians](https://mlsanity.com/paper/2106.02162/) (2021)
- [You Are What You Write: Preserving Privacy in the Era of Large Language Models](https://mlsanity.com/paper/2204.09391/) (2022)
- [XRand: Differentially Private Defense against Explanation-Guided Attacks](https://mlsanity.com/paper/2212.04454/) (2022)
- [Towards Sparse Federated Analytics: Location Heatmaps under Distributed Differential Privacy with Secure Aggregation](https://mlsanity.com/paper/2111.02356/) (2021)
- [SoK: Differential Privacy on Graph-Structured Data](https://mlsanity.com/paper/2203.09205/) (2022)
- [Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacy](https://mlsanity.com/paper/2202.10209/) (2022)
- [Private Frequency Estimation via Projective Geometry](https://mlsanity.com/paper/2203.00194/) (2022)
- [Federated Analytics: A survey](https://mlsanity.com/paper/2302.01326/) (2023)
- [Contraction of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2210.13386/) (2022)
- [Renyi Differential Privacy of the Subsampled Shuffle Model in Distributed Learning](https://mlsanity.com/paper/2107.08763/) (2021)
- [Nonparametric extensions of randomized response for private confidence sets](https://mlsanity.com/paper/2202.08728/) (2022)
- [A Systematic and Formal Study of the Impact of Local Differential Privacy on Fairness: Preliminary Results](https://mlsanity.com/paper/2405.14725/) (2024)
- [Robust Testing and Estimation under Manipulation Attacks](https://mlsanity.com/paper/2104.10740/) (2021)
- [Robust Estimation of Discrete Distributions under Local Differential Privacy](https://mlsanity.com/paper/2202.06825/) (2022)
- [Group privacy for personalized federated learning](https://mlsanity.com/paper/2206.03396/) (2022)
- [(Local) Differential Privacy has NO Disparate Impact on Fairness](https://mlsanity.com/paper/2304.12845/) (2023)

## Abstract (arXiv)

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.