# Anonymized Histograms in Intermediate Privacy Models

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 51 references that are in the map.
- First posted on arXiv 27 Oct 2022.

## Builds on (most cited first, 23 of 23)

- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity](https://mlsanity.com/paper/1811.12469/) (2018)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Minimax Optimal Procedures for Locally Private Estimation](https://mlsanity.com/paper/1604.02390/) (2016)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Private Summation in the Multi-Message Shuffle Model](https://mlsanity.com/paper/2002.00817/) (2020)
- [LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale](https://mlsanity.com/paper/2002.05839/) (2020)
- [Differentially Private Testing of Identity and Closeness of Discrete Distributions](https://mlsanity.com/paper/1707.05128/) (2017)
- [Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead](https://mlsanity.com/paper/2106.04247/) (2021)
- [Pure Differentially Private Summation from Anonymous Messages](https://mlsanity.com/paper/2002.01919/) (2020)
- [Connecting Robust Shuffle Privacy and Pan-Privacy](https://mlsanity.com/paper/2004.09481/) (2020)
- [Priv'IT: Private and Sample Efficient Identity Testing](https://mlsanity.com/paper/1703.10127/) (2017)
- [Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributions](https://mlsanity.com/paper/1504.07912/) (2015)
- [On Distributed Differential Privacy and Counting Distinct Elements](https://mlsanity.com/paper/2009.09604/) (2020)
- [PriPeARL: A Framework for Privacy-Preserving Analytics and Reporting at LinkedIn](https://mlsanity.com/paper/1809.07754/) (2018)
- [Pan-Private Uniformity Testing](https://mlsanity.com/paper/1911.01452/) (2019)
- [Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation](https://mlsanity.com/paper/1905.08448/) (2019)
- [The Broad Optimality of Profile Maximum Likelihood](https://mlsanity.com/paper/1906.03794/) (2019)
- [INSPECTRE: Privately Estimating the Unseen](https://mlsanity.com/paper/1803.00008/) (2018)
- [Pure Differential Privacy from Secure Intermediaries](https://mlsanity.com/paper/2112.10032/) (2021)
- [Differentially private anonymized histograms](https://mlsanity.com/paper/1910.03553/) (2019)
- [Tight Bounds for Differentially Private Anonymized Histograms](https://mlsanity.com/paper/2111.03257/) (2021)

## Abstract (arXiv)

We study the problem of privately computing the anonymized histogram (a.k.a. unattributed histogram), which is defined as the histogram without item labels. Previous works have provided algorithms with ℓ1- and ℓ22-errors of O_varepsilon(√n) in the central model of differential privacy (DP). In this work, we provide an algorithm with a nearly matching error guarantee of tildeO_varepsilon(√n) in the shuffle DP and pan-private models. Our algorithm is very simple: it just post-processes the discrete Laplace-noised histogram! Using this algorithm as a subroutine, we show applications in privately estimating symmetric properties of distributions such as entropy, support coverage, and support size.