Source-linked AI summary
Distributed Private Heavy Hitters
Justin Hsu, Sanjeev Khanna, Aaron Roth
TL;DR
The paper studies how to identify a heavy hitter while protecting individual data when people interact directly with an algorithm and there is no trusted aggregator. It develops information-theoretic bounds and efficient algorithms, showing a separation between local and centralized privacy guarantees.
Problem
How accurately can a heavy hitter be identified with formal privacy guarantees when individuals interact directly with the algorithm and no trusted party aggregates their data?
Source: §1 · pp. 1–2Method
The paper uses random projections and concentration of measure for accuracy bounds, with compressed sensing and pairwise-independent-hash group testing for efficient algorithms.
Source: §1.1 · p. 2, §1.2 · p. 3Results
Ω(√ n) accuracy is necessary locally even for approximate heavy-hitter counts, versus O(1) centrally; efficient algorithms do not generally attain the paper’s tight information-theoretic bound.
Source: §5 · p. 18Takeaways & Limitations
The paper characterizes local-model accuracy and leaves open whether efficient algorithms can match its information-theoretic bounds.
Source: §1 · p. 2The bucket mechanism guarantees the exact heavy hitter only when its frequency exceeds the ℓ2-norm of the other frequencies; otherwise it gives no guarantee.
Source: §4.2 · p. 18
Abstract
from arXiv · showhide
In this paper, we give efficient algorithms and lower bounds for solving the heavy hitters problem while preserving differential privacy in the fully distributed local model. In this model, there are n parties, each of which possesses a single element from a universe of size N. The heavy hitters problem is to find the identity of the most common element shared amongst the n parties. In the local model, there is no trusted database administrator, and so the algorithm must interact with each of the $n$ parties separately, using a differentially private protocol. We give tight information-theoretic upper and lower bounds on the accuracy to which this problem can be solved in the local model (giving a separation between the local model and the more common centralized model of privacy), as well as computationally efficient algorithms even in the case where the data universe N may be exponentially large.
1 Introduction
The paper asks how to identify a most-common element while protecting each person’s data when individuals interact with the algorithm separately and no trusted aggregator is available. It develops accuracy bounds and efficient methods for this local-privacy heavy hitters problem.
1 Introduction
- The motivating task is to identify a popular referring site without exposing visitors’ individual sources or relying on a trusted party to aggregate them.The formal model has n individuals, each holding one element from a potentially large universe, and seeks the most frequent element or one occurring almost as often.Source: §1 · pp. 1–2
1.1 Our Results
- In the local model, no algorithm achieves α-accuracy for α = Ω(√ n), even when |N| = 2.The paper also gives an almost matching information-theoretic upper bound, achieved by an algorithm linear in N.Source: §1.1 · p. 2
- The efficient compressed-sensing algorithm is α-accurate for α = ˜O(n5/6 log1/6 N), while group testing returns the exact heavy hitter when its frequency exceeds the ℓ2-norm of the other frequencies.Depending on the frequency distribution, the latter condition corresponds to α-accuracy ranging from O(√ n) to O(n).Source: §1.1 · p. 2
1.2 Our Techniques
- Random projections approximately preserve the counts used to identify the heavy hitter, but the information-theoretic method must enumerate all |N| candidates; efficient variants use compressed sensing or invertible pairwise-independent hash projections.The projection-based lower bound uses anti-concentration: conditioned on private messages, counts remain approximately uniform and normally distributed, yielding an Ω(√ n) lower bound.Source: §1.2 · p. 3
1.3 Related Work
- Prior local-model work studied learning and query release, while this paper establishes a local-versus-centralized separation specifically for heavy hitters.Related pan-private streaming work estimates counts rather than identifying a universe element; local privacy also implies pan-privacy, but the paper’s lower bounds need not apply to pan-privacy alone.Source: §1.3 · pp. 3–4
2 Preliminaries
The preliminaries represent individuals’ data as a histogram and define accuracy by how close a returned element’s frequency is to the maximum. They introduce differential privacy, the local access model, and probabilistic tools used in the analysis.
2 Preliminaries
- A database can be represented as a histogram whose coordinates count occurrences, and an (α, β)-accurate algorithm returns an element within α of the heavy hitter’s frequency with probability at least 1 − β.The heavy hitter is the most frequent universe element.Source: §2 · pp. 4–5
2.1 Differential Privacy
- Differential privacy limits how much an individual’s data change can affect an algorithm’s output, while the local model requires each person’s data to be accessed independently through private interactions.The preliminaries also describe composing privacy guarantees across steps and using Laplace noise for low-sensitivity queries.Source: §2.1 · pp. 5–6
2.2 Probabilistic Tools
- The probabilistic tools include Johnson–Lindenstrauss embeddings, which preserve pairwise distances in a lower-dimensional space, and tail bounds for sums of Laplace random variables.The embedding dimension is logarithmic in the number of points being embedded.Source: §2.2 · p. 6
3 Information Theoretic Upper and Lower Bounds.
Section 3 gives information-theoretic upper and lower bounds for private heavy hitters in the fully distributed model. Its upper-bound construction uses Johnson–Lindenstrauss projections, while its lower-bound argument uses anti-concentration.
3.1 An Upper Bound via Johnson-Lindenstrauss Projections
- JL-HH estimates each element’s count from noisy projected inner products, then returns the element with the largest estimated count.The projection approximately preserves inner products, while noise is added because the private data cannot be accessed directly.Source: §3.1 · p. 7
- For any β>0, JL-HH is (α,β)-accurate and (ε,δ)-private in the local model.The theorem passage does not specify the value of α.Source: §3.1 · pp. 7–8
- Clients compress their histograms so JL-HH communicates O(log N) information rather than the naive method’s O(N), with similar accuracy.JL-HH still runs in time linear in N.Source: §3.1 · p. 9
3.2 A Lower Bound via Anti-Concentration
- After conditioning on local messages, the lower-bound proof retains independent, approximately uniform data elements and uses anti-concentration to show uncertainty in their counts remains.This supports the lower bound even with an algorithm’s estimate of the heavy hitter.Source: §3.2 · pp. 9, 11
- For ε≤1/2 and δ bounded away from 1, no local (ε,δ)-private mechanism is (α,β)-accurate for α=Ω(√n), even when |N|=2.The lower-bound argument uses the uncertainty that remains after conditioning on private interaction messages, then applies anti-concentration.Source: §3.2 · p. 9
4 Efficient Algorithms
The section presents two algorithms with running time polynomial in n and logarithmic in the universe size: GLPS sparse recovery and a group-testing Bucket mechanism. The Bucket mechanism can return the exact heavy hitter under a frequency condition, while the section also establishes local privacy and efficiency guarantees.
4.1 GLPS Sparse Recovery
- GLPS sparse recovery reconstructs an approximation from linear measurements and runs in time O((s/γ) log^c N).Its measurement count is O(s log(N/s)/γ), with s a sparsity parameter and γ a tunable approximation level.Source: §4.1 · p. 11
- GLPS-HH adds Laplace noise to measurements computed independently by each party, supporting local differential privacy.Each party answers m linear queries of sensitivity 1, with noise sufficient for (ε,δ)-differential privacy.Source: §4.1 · p. 12
- GLPS-HH achieves its stated accuracy with probability at least 3/4−β and operates in the local model with (ε,δ)-differential privacy.The supplied theorem gives the accuracy as (α, 3/4−β), but does not include the expression for α.Source: §4.1 · pp. 12–13
4.2 The Bucket mechanism
- The Bucket mechanism uses repeated trials of pairwise-independent hash functions, identifies candidates in majority buckets, and takes a majority vote across trials.The hash family maps binary element labels to {0,1}; finding an element matching target buckets reduces to solving a linear system modulo 2.Source: §4.2 · p. 13
- The Bucket mechanism is (ε,δ)-differentially private and runs in time O(n log(1/β) log^3 N).Its privacy analysis adds noise to each party’s 1-sensitive queries.Source: §4.2 · p. 15
- Under its frequency condition, the Bucket mechanism returns the exact heavy hitter with probability at least 1−β.The condition is roughly that the heavy hitter’s frequency exceeds the ℓ2 norm of the other elements’ frequencies; without it, the mechanism has no accuracy guarantee.Source: §4.2 · pp. 17–18
5 Discussion and Open Questions
The paper establishes an almost tight information-theoretic accuracy characterization for private heavy hitters in the local model, separating it from centralized privacy. Its efficient algorithms do not generally attain the information-theoretic bound, leaving efficient algorithms at that accuracy as an open question.
5 Discussion and Open Questions
- The local model cannot release even an approximate heavy-hitter count to accuracy better than Ω(√n), whereas the centralized model can achieve O(1) accuracy.The paper says its information-theoretic accuracy characterization is almost tight.Source: §5 · p. 18
- The efficient algorithms do not generally achieve the information-theoretic ˜O(√(n log |N|)) accuracy bound, leaving efficient attainment of that bound open.The paper asks whether efficient local-model algorithms can reach the bound established as possible in principle.Source: §5 · p. 18