Locally Private Histograms in All Privacy Regimes

Clément L. Canonne, Abigail Gentle

TL;DR

While local differential privacy (LDP) theory has long focused on high-privacy settings ($\varepsilon \ll 1$), real-world systems often deploy algorithms with large $\varepsilon$. This paper proves near-tight $\ell_\infty$ error bounds across all privacy regimes, revealing that standard protocols like RAPPOR and Projective Geometry Response (PGR) achieve an exponential improvement in error as $\varepsilon$ grows—out of the box, with zero algorithmic changes. As an immediate payoff, shuffling PGR yields a state-of-the-art shuffle DP histogram protocol with only a single, logarithmic-length message per user.

What Problem Does This Paper Address?

In locally private frequency estimation (histograms), $n$ users hold items from an alphabet of size $k$ and randomize their data before sending it to an untrusted server. Quality is evaluated using the worst-case maximum coordinate error ($\ell_\infty$ error), which is central to downstream tasks like identifying heavy hitters and distribution learning.

Theory has pinned down the minimax $\ell_\infty$ error in the high-privacy regime ($\varepsilon \le 1$) as $\Theta\left(\sqrt{\frac{\log k}{n \varepsilon^2}}\right)$. However, practical deployments (such as Apple's and Google's telemetry pipelines) commonly run with medium-to-large values of $\varepsilon$ ($\varepsilon \ge 1$) to preserve utility. Prior analyses suggested large-$\varepsilon$ error decayed as $O\left(\sqrt{\frac{\log k}{n \varepsilon}}\right)$ or hit constant error floors. The authors address whether this represents a fundamental bottleneck or merely loose analysis, establishing the true optimal rates when privacy constraints are relaxed.

Methods

Rather than designing new, complex algorithms, the authors revisit existing protocols—RAPPOR and Projective Geometry Response (PGR):

  • Beyond Sub-Gaussian Concentration: In the low-privacy regime ($\varepsilon \ge 1$), randomization probabilities approach $0$ or $1$. Standard sub-Gaussian bounds are too crude for highly biased Bernoullis. The authors instead treat deviations as sub-gamma random variables, leveraging modern local Glivenko–Cantelli concentration inequalities (Cohen & Kontorovich, 2023).
  • Coupling Lemma for Heterogeneous Sums: Because users hold different inputs, their randomized vectors are independent but not identically distributed. The authors prove a stochastic domination lemma (via Jensen's inequality and convex ordering) showing that taking the maximum over identical binomials with maximal trials upper-bounds the heterogeneous case.
  • Information-Theoretic Lower Bounds: Using the $\chi^2$-contraction framework and Fano’s inequality over perturbed uniform distributions, they establish matching lower bounds across both small- and large-$\varepsilon$ regimes.
  • Amplification by Shuffling: They translate their low-privacy LDP bounds into the shuffle DP model using the amplification framework of Feldman, McMillan, and Talwar (2021).

Datasets

Not discussed in this conference version of the paper. (The authors note that empirical evaluations across synthetic configurations and privacy regimes are deferred to the full arXiv version.)

Key Insights and Ideas

  • The $O(\sqrt{\log k / (n\varepsilon)})$ bound is not tight: Intuition suggested that $\varepsilon$ only enters linearly under the square root. The paper shows the error actually drops exponentially in $\varepsilon$—scaling with $e^{-\varepsilon/2}$ (for RAPPOR) and $e^{-\varepsilon}$ (for PGR).
  • Existing protocols are already optimal: Practitioners do not need to rewrite their pipelines or deploy multi-message wrappers. Existing implementations of RAPPOR and PGR achieve near-optimal rates without modification.
  • Best of all worlds in the shuffle model: Prior shuffle DP histogram protocols with state-of-the-art error required either $k^{\Omega(1)}$ messages per user or $k+1$ interactive rounds. By feeding PGR into a shuffler, one gets optimal shuffle DP error with a single message of $O(\log k)$ bits per user.

Key Results

  • PGR Error Rate (Theorem 18): For $\varepsilon \ge 1$, PGR achieves: $$\mathbb{E}[\|\hat{q} - q\|_\infty] = \tilde{O}\left(\max\left\{\sqrt{\frac{\log k}{n e^\varepsilon}},\, \frac{\log k}{n \varepsilon}\right\}\right)$$ using only $O(\log k)$ bits of communication per user.

  • RAPPOR Error Rate (Theorem 14): RAPPOR achieves $\tilde{O}\left(\max\left\{\sqrt{\frac{\log k}{n e^{\varepsilon/2}}},\, \frac{\log k}{n \varepsilon}\right\}\right)$ using $k$ bits of communication.

  • Matching Lower Bound (Theorem 24): Any non-interactive LDP protocol must incur worst-case error $\Omega\left(\sqrt{\frac{\log k}{n\varepsilon^2}}\right)$ for $\varepsilon \le 1$, and: $$\Omega\left(\max\left\{\sqrt{\frac{\log k}{n e^\varepsilon}},\, \frac{\log k}{n \varepsilon}\right\}\right) \quad \text{for } \varepsilon \ge 1.$$
  • Shuffle DP Histograms (Theorem 27): For $n = \Omega\left(\frac{\log(1/\delta)}{\varepsilon^2}\right)$, shuffled PGR achieves expected $\ell_\infty$ error: $$O\left(\frac{\sqrt{\log(k) \log(1/\delta)}}{n\varepsilon}\right)$$ with 1 message of $O(\log k)$ bits per user.

Limitations and Future Work

  • Extraneous Logarithmic Term: The upper bounds include an extra $\log n$ factor stemming from the local Glivenko–Cantelli framework. Recent refinements (Blanchard & Voracek, 2024) may help eliminate this gap.
  • Shuffle Parameter Restriction: The single-message shuffle DP guarantee requires $n = \Omega(\log(1/\delta)/\varepsilon^2)$, whereas central DP requires only a linear dependence on $1/\varepsilon$.
  • Extending to Other LDP Protocols: While demonstrated for RAPPOR and PGR, extending these sub-gamma techniques to other schemes (e.g., Subset Selection or Hadamard Response) remains open.

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 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 𝓁_∞ error in the high-privacy (small ε) 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 ε), 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 𝓁_∞ 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.
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},
}

Loading related content...

Figure