mlsanityData to 7 Oct 2026

Anonymized Histograms in Intermediate Privacy Models

arXiv 2210.15178 ↗First posted 27 Oct 2022cs.DS cs.CR cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

23 of 51 references.

References · 23

  1. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  2. 2018Amplification by Shuffling: From Local to Central Differential Privacy via Anonymitycited by 163
  3. 2017Collecting Telemetry Data Privatelycited by 147
  4. 2018Distributed Differential Privacy via Shufflingcited by 115
  5. 2016Minimax Optimal Procedures for Locally Private Estimationcited by 103
  6. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  7. 2020Private Summation in the Multi-Message Shuffle Modelcited by 34
  8. 2020LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scalecited by 26
  9. 2017Differentially Private Testing of Identity and Closeness of Discrete Distributionscited by 25
  10. 2021Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overheadcited by 16
  11. 2020Pure Differentially Private Summation from Anonymous Messagescited by 15
  12. 2020Connecting Robust Shuffle Privacy and Pan-Privacycited by 12
11 more
  1. 2017Priv'IT: Private and Sample Efficient Identity Testingcited by 10
  2. 2020On Distributed Differential Privacy and Counting Distinct Elementscited by 8
  3. 2015Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributionscited by 7
  4. 2018PriPeARL: A Framework for Privacy-Preserving Analytics and Reporting at LinkedIncited by 7
  5. 2019Pan-Private Uniformity Testingcited by 6
  6. 2019Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimationcited by 5
  7. 2019The Broad Optimality of Profile Maximum Likelihoodcited by 5
  8. 2018INSPECTRE: Privately Estimating the Unseencited by 4
  9. 2021Pure Differential Privacy from Secure Intermediariescited by 4
  10. 2019Differentially private anonymized histogramscited by 2
  11. 2021Tight Bounds for Differentially Private Anonymized Histogramscited by 2

Built on by

Not cited yet.