Anonymized Histograms in Intermediate Privacy Models

We study the problem of privately computing the \emph{anonymized histogram} (aka \emph{unattributed histogram}), which is defined as the histogram without item labels. Previous works have provided algorithms with $\ell_1$ and $\ell_2$ errors of $O_\eps(\sqrt{n})$ in the central model of differential privacy (DP). In this work, we provide an algorithm with a nearly matching error guarantee of $\tilde{O}_\eps(\sqrt{n})$ in the shuffle and pan private DP 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 estimating several symmetric properties of distributions such as the entropy and support size.

• Machine Intelligence

• Algorithms and Theory