Source-linked AI summary
Local, Private, Efficient Protocols for Succinct Histograms
Raef Bassily, Adam Smith
TL;DR
The paper addresses efficient frequency estimation and succinct heavy-hitter histograms under local differential privacy. It combines efficient protocol constructions with information-theoretic lower bounds and a public-coin one-bit transformation. The resulting protocols achieve error that the paper shows is optimal for local protocols, including when one item is significantly frequent.
Problem
The paper studies how to estimate frequencies and represent heavy hitters privately when users randomize their own data and prior protocols were inefficient or had weaker error guarantees.
Method
The paper combines a private frequency oracle, an efficient unique-heavy-hitter construction, a reduction to general succinct histograms, and lower-bound techniques adapted from local minimax estimation.
Results
The efficient succinct-histogram protocols achieve error that matches the paper’s lower bound, while public-coin pure-ε-LDP protocols can be transformed so each user sends 1 bit.
Takeaways & Limitations
The paper establishes efficient, error-optimal local protocols for succinct histograms and shows that one-bit communication suffices in the public-coin setting.
Takeaways & Limitations
The efficient frequency-oracle construction assumes public randomness for a succinct projection description, and the minimax formulation assumes users’ items are drawn independently from a distribution.
Abstract
from arXiv · showhide
We give efficient protocols and matching accuracy lower bounds for frequency estimation in the local model for differential privacy. In this model, individual users randomize their data themselves, sending differentially private reports to an untrusted server that aggregates them. We study protocols that produce a succinct histogram representation of the data. A succinct histogram is a list of the most frequent items in the data (often called "heavy hitters") along with estimates of their frequencies; the frequency of all other items is implicitly estimated as 0. If there are $n$ users whose items come from a universe of size $d$, our protocols run in time polynomial in $n$ and $\log(d)$. With high probability, they estimate the accuracy of every item up to error $O\left(\sqrt{\log(d)/(ε^2n)}\right)$ where $ε$ is the privacy parameter. Moreover, we show that this much error is necessary, regardless of computational efficiency, and even for the simple setting where only one item appears with significant frequency in the data set. Previous protocols (Mishra and Sandler, 2006; Hsu, Khanna and Roth, 2012) for this task either ran in time $Ω(d)$ or had much worse error (about $\sqrt[6]{\log(d)/(ε^2n)}$), and the only known lower bound on error was $Ω(1/\sqrt{n})$. We also adapt a result of McGregor et al (2010) to the local setting. In a model with public coins, we show that each user need only send 1 bit to the server. For all known local protocols (including ours), the transformation preserves computational efficiency.
1 Introduction
The paper develops efficient local-DP protocols for succinct histograms and proves matching error lower bounds, while showing that public-coin protocols can use one-bit reports.
- Problem setting: The local model has users randomize their data before sending privacy-protected reports to an untrusted aggregating server.The model keeps control of private data in users’ hands.
- Problem setting: A succinct histogram lists heavy hitters with estimated frequencies and implicitly assigns zero frequency to all omitted items.Its accuracy is measured by maximum absolute frequency error across the universe.
- Contributions: The protocols target computation, communication, and storage polynomial in n and log(d), addressing prior inefficiency or weaker error guarantees.Earlier constructions either required time polynomial in d or had much worse error, while some sublinear-communication constructions used approximate rather than pure privacy.
- Contributions: The paper provides an efficient private succinct-histogram construction by combining a private frequency oracle with a unique-heavy-hitter protocol and a reduction to the general problem.The unique-heavy-hitter protocol uses noisy error-correcting encodings, while the general reduction uses parallel hashed channels.
- Contributions: The paper proves that local protocols require error matching the efficient construction, regardless of computation time and communication.The lower-bound instances contain one unknown item with frequency η and uniformly random remaining inputs; the bound applies to both worst-case and minimax error.
- Contributions: In the public-coin model, every pure-ε-LDP local protocol can be transformed so each user sends one bit, efficiently when its randomizer’s conditional probabilities are efficiently computable.The paper states that all known local protocols, including its efficient heavy-hitter protocol, satisfy this condition.
2 Building Blocks
The paper develops privacy-preserving building blocks for efficient frequency estimation, including a basic randomizer and a Johnson–Lindenstrauss-based frequency oracle. These components provide pure ε-LDP, unbiased estimation, computational efficiency, and high-probability error guarantees.
- Basic randomizer: The randomizer accepts either a hypercube encoding of an item or the all-zero vector representing no information.It randomly selects and privatizes one coordinate, returning the selected index and randomized value.
- Basic randomizer: The basic randomizer R converts encoded item vectors into ε-LDP reports while preserving unbiasedness and running in O(m) time.Its output can be represented using ⌈log m⌉+1 bits.
- Private frequency oracle: The frequency oracle uses Johnson–Lindenstrauss projections to estimate frequencies in dimension O(n), rather than the much larger dimension used previously.Independent basic randomizers provide pure ε-differential privacy, and the projection can be generated efficiently with succinct public randomness.
- Private frequency oracle: A frequency estimate can be computed efficiently for any fixed item from the constructed oracle.The estimator is implemented by the AFO procedure.
- Private frequency oracle: The oracle is ε-differentially private and supplies an estimator for any queried item through an inner product with the aggregate randomized measurement.Its utility guarantee holds with probability at least 1−β over the projection and user-randomizer randomness.
3 Efficient Error-Optimal Construction of Private Succinct Histograms
The paper combines private frequency estimation with error-correcting encodings to construct efficient succinct histograms, first for a unique-heavy-hitter promise and then for general data. The resulting protocols are private, computationally efficient, and achieve the paper’s error guarantees, while a separate transformation reduces public-coin reports to 1 bit.
- General construction: The construction combines a private frequency oracle with a unique-heavy-hitter protocol to solve the general succinct-histogram problem.The modular design preserves efficiency and uses the component privacy and utility guarantees.
- Unique heavy hitter: Under the promise that one unknown item occurs in at least an η fraction of users’ inputs, the protocol encodes items with an error-correcting code before privatization.The server aggregates noisy reports, rounds the aggregate to a hypercube vertex, decodes the item, and estimates its frequency.
- Unique heavy hitter: The promise-problem protocol is ε-differentially private and, with high probability, recovers the common item together with a frequency estimate.Its reports have length O(log(log(d))) bits, and its computation is polynomial in n and log(d).
- General construction: The general protocol is ε-differentially private and provides estimates for heavy hitters while using hashing to isolate them across channels.The construction’s overall worst-case cost is O(n^5/2 poly(log(d)) log(1/β)).
4 The Full Protocol
The paper transforms private distributed protocols into protocols where each user sends one bit, preserving privacy, efficiency, and—under sampling resilience—the original error guarantees. Applied to succinct histograms, this yields an efficient 1-bit protocol with the same privacy and optimal-error guarantees as PROT-S-Hist.
- Generic 1-bit transformation: The generic transformation replaces each user’s original report with a single bit while adding O(nτ) public-randomness bits when original reports have length τ.The server reconstructs a report subset and runs the original estimation algorithm on the collected reports.
- Efficiency: If the acceptance probabilities are efficiently computable, the transformation preserves the original protocol’s computational efficiency.For PROT-S-Hist, each user computes only T+1 item-dependent probabilities rather than all KT+1 channel components.
- Privacy: The transformed protocol is ε-LDP because the acceptance probability is constructed from the original local randomizer’s privacy guarantee.The proof bounds the relevant probability ratios using ε-differential privacy.
- Application to succinct histograms: The application to PROT-S-Hist produces an efficient 1-bit succinct-histogram protocol with the same privacy and error guarantees as PROT-S-Hist.The paper states these guarantees as ε-differential privacy and the error bound from Theorem 3.2.
5 Tight Lower Bound on the Error
The paper proves tight lower bounds for private histogram estimation by reducing estimation difficulty to information loss under degrading channels. The lower bound matches the achievable error for frequency oracles and succinct histograms, including under meaningful approximate-local-privacy parameters.
- Main result: The same asymptotic lower bound holds for pure ε-LDP and (ε,δ)-LDP when δ=o(1/n), so approximate privacy gives no asymptotic accuracy advantage in these settings.The paper notes δ≈1/n^γ with γ≥2 as a standard meaningful regime.
- Main result: The lower bound matches the upper bound for both frequency oracles and succinct histograms, establishing optimal error for the efficient constructions.It also identifies earlier constructions with optimal error, although some are computationally inefficient for succinct histograms.
- Proof strategy: The lower-bound strategy first derives a minimax lower bound for distribution estimation, then transfers it to maximum frequency error using concentration bounds.The argument uses the expected worst-case error and Hoeffding’s inequality to obtain a lower bound for actual frequencies.
- Proof strategy: An η-degrading channel preserves the input item with probability η and otherwise outputs a uniform item, amplifying privacy to O(ηε) and O(ηδ).This reduces the information available in reports and supports the minimax lower bound.
- Main theorem: Theorem 5.2 states that for ε=O(1) and δ=o(1/n), every private histogram estimator has a worst-case distribution with expected error bounded below at the paper’s stated asymptotic rate.The theorem quantifies the lower bound over arbitrary local randomizers and estimators.
- Proof strategy: The proof also analyzes a common-item instance, where all users share one item and degradation plus Fano’s inequality limits recovery of that item.This connects the lower bound to the simple heavy-hitter setting.