Locally Private Histograms in All Privacy Regimes

Clément L. Canonne, Abigail Gentle

Abstract

Frequency estimation, a.k.a. histograms, is a workhorse of data analysis, and as such has been thoroughly studied under differentially privacy. In particular, computing histograms in the local model of privacy has been the focus of a fruitful recent line of work, and various algorithms have been proposed, achieving the order-optimal $\ell_\infty$ error in the high-privacy (small $\varepsilon$) regime while balancing other considerations such as time- and communication-efficiency. However, to the best of our knowledge, the picture is much less clear when it comes to the medium- or low-privacy regime (large $\varepsilon$), despite its increased relevance in practice. In this paper, we investigate locally private histograms, and the very related distribution learning task, in this medium-to-low privacy regime, and establish near-tight (and somewhat unexpected) bounds on the $\ell_\infty$ error achievable. As a direct corollary of our results, we obtain a protocol for histograms in the shuffle model of differential privacy, with accuracy matching previous algorithms but significantly better message and communication complexity. Our theoretical findings emerge from a novel analysis, which appears to improve bounds across the board for the locally private histogram problem. We back our theoretical findings by an empirical comparison of existing algorithms in all privacy regimes, to assess their typical performance and behaviour beyond the worst-case setting.

Introduction

Frequency estimation (building histograms) is fundamental to data science. In the Local Differential Privacy (LDP) model, users perturb their own data before sending it to a central server, ensuring the server never sees the raw values. The privacy parameter $\epsilon$ controls the trade-off: small $\epsilon$ means high privacy but noisy data; large $\epsilon$ means low privacy but higher accuracy.

Historically, theoretical research has focused on the "high-privacy" regime ($\epsilon \ll 1$), where error typically scales with $1/\epsilon$. However, real-world deployments (e.g., by Apple and Google) often use much larger values of $\epsilon$. This paper addresses the gap in understanding how these algorithms behave when privacy is relaxed, providing a near-tight theoretical characterization across all privacy regimes.

Methods

The research combines rigorous information-theoretic analysis with empirical simulations. The theoretical approach moves beyond standard "worst-case" sub-Gaussian tail bounds, which become loose when $\epsilon$ is large. Key methodological components include:

  • Refined Concentration Bounds: Utilization of "Local Glivenko-Cantelli" results and sub-gamma analysis to capture the behavior of "highly biased" random variables that occur when $\epsilon$ is large and noise becomes infrequent.
  • Algorithm Analysis: Detailed analysis of two primary protocols: RAPPOR (a classic bit-flipping approach) and Projective Geometry Response (PGR) (a communication-efficient protocol based on finite geometry).
  • Lower Bounds: Application of the "chi-square contraction" framework to prove that the new upper bounds are essentially optimal for any LDP protocol.

Empirical evaluation used synthetic datasets, specifically Zipf Distributions with varying $\alpha$ parameters (0 to 2000) to test sensitivity to data "shape," with universe sizes ($k$) up to 50,000 and user counts ($n$) up to 20,000.

Key Insights

  • "Out-of-the-Box" Excellence: A surprising finding is that standard protocols like RAPPOR do not require modification for low-privacy regimes; they already achieve near-optimal error, which was previously unproven due to loose mathematical bounds.
  • Exponential Scaling: In the low-privacy regime, error for protocols like PGR scales with $1/\sqrt{n e^\epsilon}$, an exponential improvement over the linear $1/\epsilon$ "rule of thumb."
  • Distribution Independence: RAPPOR's error distribution is invariant to input data. Conversely, "subset-based" protocols (e.g., Subset Selection) perform better on uniform data than on concentrated "heavy hitter" data.
  • Efficiency and Accuracy: PGR emerges as a "best of three worlds" solution, achieving optimal error with only $O(\log k)$ communication and high computational efficiency.

Key Results

The paper establishes that for $\epsilon \geq 1$, the optimal $\ell_\infty$ error is $\tilde{O}\left(\max\left(\sqrt{\frac{\log k}{n e^\epsilon}}, \frac{\log k}{n\epsilon}\right)\right)$. Notably, RAPPOR is shown to achieve an error of $O(\sqrt{\log k / n \min(\epsilon, \epsilon^2)})$ across all regimes.

Comparison of LDP protocols for frequency estimation across different privacy regimes.

Furthermore, by applying these LDP results to the Shuffle Model, the authors obtain a protocol matching state-of-the-art accuracy while using only one message of logarithmic length per user—a significant improvement over previous multi-message or high-communication protocols.

Limitations and Future Work

Current upper bounds include a $\log n$ factor from the Glivenko-Cantelli analysis; determining if this factor is fundamental remains an open question. Additionally, the shuffle model results require a sufficiently large user base ($n = \Omega(\log(1/\delta)/\epsilon^2)$); extending these guarantees to smaller $n$ is a promising future direction. Finally, the "chi-square contraction" techniques may be applicable to other LDP problems beyond histograms.

Summary updated

Abstract

Frequency estimation, a.k.a. histograms, is a workhorse of data analysis, and as such has been thoroughly studied under differentially privacy. In particular, computing histograms in the \emph{local} model of privacy has been the focus of a fruitful recent line of work, and various algorithms have been proposed, achieving the order-optimal $\ell_\infty$ error in the high-privacy (small $\varepsilon$) regime while balancing other considerations such as time- and communication-efficiency. However, to the best of our knowledge, the picture is much less clear when it comes to the medium- or low-privacy regime (large $\varepsilon$), despite its increased relevance in practice. In this paper, we investigate locally private histograms, and the very related distribution learning task, in this medium-to-low privacy regime, and establish near-tight (and somewhat unexpected) bounds on the $\ell_\infty$ error achievable. As a direct corollary of our results, we obtain a protocol for histograms in the \emph{shuffle} model of differential privacy, with accuracy matching previous algorithms but significantly better message and communication complexity. Our theoretical findings emerge from a novel analysis, which appears to improve bounds across the board for the locally private histogram problem. We back our theoretical findings by an empirical comparison of existing algorithms in all privacy regimes, to assess their typical performance and behaviour beyond the worst-case setting.
BibTeX
@inproceedings{canonne2025locally,
  author = {Clément L. Canonne and Abigail Gentle},
  title = {{Locally Private Histograms in All Privacy Regimes}},
  booktitle = {ITCS},
  year = {2025},
  url = {https://openreview.net/forum?id=FyvjPsWqkN},
}
Figure