Source-linked AI summary
Heavy Hitters and the Structure of Local Privacy
Mark Bun, Jelani Nelson, Uri Stemmer
TL;DR
The paper addresses sub-optimal failure-probability dependence in locally private heavy hitters and related gaps in understanding local privacy. It combines a new private reduction with structural analyses of local protocols, obtaining optimal heavy-hitters error and broader results on group privacy and pure versus approximate privacy.
Problem
Prior LDP heavy-hitters algorithms were optimal in n, |X|, and ε but had sub-optimal dependence on failure probability β.
Method
The paper combines a locally private heavy-hitters algorithm with a non-private reduction, strengthens lower bounds, and transforms non-interactive approximate-private protocols into pure-private ones.
Results
The new LDP heavy-hitters algorithm achieves optimal worst-case error in n, |X|, ε, and β, while the lower bound is tight in β.
Takeaways & Limitations
In the local model, group privacy degrades by approximately √k and approximate privacy cannot yield more accurate non-interactive protocols than pure privacy.
Takeaways & Limitations
The paper focuses on non-interactive local protocols, with the heavy-hitters protocol using one local-oracle response per user.
Abstract
from arXiv · showhide
We present a new locally differentially private algorithm for the heavy hitters problem which achieves optimal worst-case error as a function of all standardly considered parameters. Prior work obtained error rates which depend optimally on the number of users, the size of the domain, and the privacy parameter, but depend sub-optimally on the failure probability. We strengthen existing lower bounds on the error to incorporate the failure probability, and show that our new upper bound is tight with respect to this parameter as well. Our lower bound is based on a new understanding of the structure of locally private protocols. We further develop these ideas to obtain the following general results beyond heavy hitters. $\bullet$ Advanced Grouposition: In the local model, group privacy for $k$ users degrades proportionally to $\approx \sqrt{k}$, instead of linearly in $k$ as in the central model. Stronger group privacy yields improved max-information guarantees, as well as stronger lower bounds (via "packing arguments"), over the central model. $\bullet$ Building on a transformation of Bassily and Smith (STOC 2015), we give a generic transformation from any non-interactive approximate-private local protocol into a pure-private local protocol. Again in contrast with the central model, this shows that we cannot obtain more accurate algorithms by moving from pure to approximate local privacy.
1 Introduction
The paper studies locally private heavy hitters, where users send randomized reports and the server identifies frequent domain elements. It introduces an optimal-error protocol and develops broader results on local group privacy, lower bounds, and pure versus approximate privacy.
- Problem: Local heavy hitters identify domain elements held by many users from one randomized message per user.The protocol must also estimate reported frequencies and limit the output list size.
- Motivation: Heavy-hitters algorithms support median estimation, convex optimization, clustering, and deployed privacy-preserving analytics.Examples include Google Chrome and Apple iOS-10.
- Main result: The new efficient LDP algorithm achieves optimal worst-case error in n, |X|, ε, and failure probability β while preserving other complexities.Prior methods either had sub-optimal β dependence or runtime at least linear in |X|.
- Lower bound: The lower bound incorporates failure probability and matches the new upper bound.The argument is based on a new understanding of local privacy structure.
- Advanced Grouposition: In the local model, group privacy degrades by approximately √k rather than linearly in k, strengthening max-information bounds and packing-based lower bounds.The stronger guarantee is described as a mixed blessing because it also yields stronger lower bounds.
- Pure vs. Approximate LDP: A generic transformation converts any non-interactive approximate-private local protocol into a pure-private protocol with the same utility guarantees.The paper argues that approximate privacy cannot provide more accurate non-interactive local algorithms.
2 Preliminaries from Differential Privay
The preliminaries formalize differential privacy for databases and local randomizers. They define LDP through per-user oracle access and restrict the paper’s focus to non-interactive protocols with one response per user.
- Differential privacy: Differential privacy limits how much changing one database record can alter an algorithm’s output distribution.The formal definition uses neighboring datasets and parameters ε and δ.
- Local model: In the local model, each individual releases only privacy-preserving computations applied to their own data.The algorithm accesses entries separately through differentially private local randomizers.
- Local randomizers: A local randomizer maps one user’s input to a randomized output, while the LR oracle returns that output for a selected user.The oracle is parameterized by a user index and a local randomizer.
- Protocol model: The paper focuses on non-interactive protocols, and its heavy-hitters protocol invokes the local oracle once per user.Non-interactive algorithms prepare all oracle queries before receiving answers.
3 A Heavy-Hitters Protocol with Optimal Error
The paper formulates heavy hitters through frequency estimation and reduces the task to constructing a frequency oracle. Its private reduction achieves optimal dependence across the standard parameters, including failure probability.
- Problem definition: A heavy-hitters protocol outputs O(n/∆) element-estimate pairs, estimates each reported frequency within ∆, and includes every element with frequency at least ∆.These guarantees hold with probability at least 1 − β.
- Frequency-oracle reduction: A frequency oracle provides a data structure that estimates every domain element’s frequency within ∆ with probability at least 1 − β.The heavy-hitters task can be addressed by querying such an oracle across the domain, ignoring runtime.
- Prior work: Prior frequency-oracle reductions achieved sub-optimal dependence on β, despite matching lower bounds for the underlying frequency-estimation error.The paper identifies failure probability as the missing optimization dimension.
- New reduction: The new private reduction from heavy hitters to frequency oracles achieves error optimal in all parameters.It is a private variant of a recent non-private algorithm and uses the frequency oracle of [3].
3.1 Existing Techniques
Existing reductions use frequency-oracle estimates, hashing, and list-recoverable codes to identify heavy hitters. The prior private reduction incurs sub-optimal dependence on failure probability, while the non-private construction uses coordinate-wise hashing and unique-list recovery.
- Reduction with Sub-Optimal Dependence on the Failure Probability: The frequency-oracle reduction identifies potential heavy hitters by hashing domain elements and recovering their symbols coordinate by coordinate.A sufficiently large hash range isolates heavy hitters, allowing frequency estimates to identify each symbol.
- Reduction with Sub-Optimal Dependence on the Failure Probability: High-probability collision avoidance requires a hash range of roughly √n/β, which is unacceptable when β is exponentially small.Repeating the reduction increases error by a factor of √log(1/β) because repeated private computations degrade privacy.
- Reduction with Sub-Optimal Dependence on the Failure Probability: Bassily et al. obtained an ε-LDP list of length ˜O(√n) with probability 1 − β and per-estimate error stated in their theorem.The supplied theorem passage gives the list-size and success-probability guarantees, while the adjacent result passage contains the error expression.
- A Non-Private Reduction Based on List-Recoverable Codes [22]: Independent hash functions for each coordinate make each heavy hitter fail on only a small fraction of coordinates except with exponentially small probability.This permits recovery of most symbols rather than repeating one globally failing hash function.
- A Non-Private Reduction Based on List-Recoverable Codes [22]: List-recoverable decoding recovers codewords agreeing with at least a (1 − α) fraction of coordinate lists, while unique-list-recoverable codes output a bounded list.The construction encodes each domain element using coordinate-wise hash values and auxiliary symbols.
- A Non-Private Reduction Based on List-Recoverable Codes [22]: The code construction provides Enc(x) = (h_1(x), g_Enc(x)_1), ..., (h_M(x), g_Enc(x)_M) with list size L ≤ C·ℓ and auxiliary range Z ≤ (|X|^1/M · Y)^C.Encoding is evaluated in linear time and space beyond hash-function calls, while decoding uses linear space and polynomial time.
3.2 Additional Preliminaries
This section introduces Hashtogram as the frequency-oracle subroutine and records probabilistic tools used in the protocol analysis. These tools include Poisson approximation, Poisson tails, limited-independence Chernoff bounds, and limited-independence Bernstein inequalities.
- Frequency Oracle: Hashtogram is an ε-LDP frequency oracle that answers a fixed domain query with probability at least 1 − β.Its server memory is ˜O(√n), per-query time is ˜O(1), and each user uses ˜O(1) resources.
- Frequency Oracle: A union bound extends Hashtogram’s fixed-query guarantee to every fixed set of w queries.The excerpt introduces this extension but does not include its resulting bound.
- Frequency Oracle: The min{n, |X|} factor in the Hashtogram guarantee is unnecessary in some parameter regimes or with slightly larger runtime or memory.The small-domain analysis is presented as a relevant special case.
- Frequency Oracle: For small domains satisfying |X|^2 = ˜O(n), Hashtogram has an alternative analysis whose server memory is ˜O(|X|).The supplied passages state that this small-domain version is used together with both Hashtogram accuracy guarantees.
- Probabilistic Preliminaries: Poissonization approximates bin loads by independent Pois(n/R) variables, with an expectation comparison controlling the exact occupancy process.Theorem 3.9 bounds exact expectations by e^√n times the Poissonized expectation.
- Probabilistic Preliminaries: The analysis also invokes Poisson upper-tail bounds, limited-independence Chernoff bounds, and limited-independence Bernstein inequalities.These tools control tails for Poisson variables and sums of bounded, partially independent variables.
3.3 The Full Protocol
PrivateExpanderSketch combines public partitioning, multiple hash functions, unique-list-recoverable coding, and Hashtogram estimates. It returns a short list with high-probability accuracy, completeness for heavy elements, and near-linear server runtime under n ≤ |X|.
- Protocol construction: PrivateExpanderSketch first applies Hashtogram to partitioned, encoded user data, extracts dominant symbols, decodes candidate lists, and refines candidates with a final frequency-oracle pass.The protocol splits privacy across intermediate and final Hashtogram uses.
- Protocol construction: The construction uses M = C_M·log|X|/log log|X| partitions, Y = log^C_Y|X| hash ranges, and ℓ = C_ℓ·log|X| code parameters.It uses public random partitioning, pairwise-independent h_1,...,h_M, and a limited-independent g.
- Guarantees: Theorem 3.13 returns a list Est of length ˜O(√n) with probability 1 − β, together with per-entry accuracy and inclusion guarantees.The supplied theorem fragments state the list length, success probability, estimation-error clause, and heavy-element inclusion clause.
- Guarantees: ˜O(√n) server memory and ˜O(n) server time are achieved while each user uses ˜O(1) runtime, memory, and communication.For n > |X|, applying Hashtogram to every domain item gives the same resource guarantees.
- Utility analysis: The analysis defines heavy items, bounds their bucket concentration, and controls non-heavy mass through events E1 and E2.These events provide the hash-bucket and partition-load conditions used later in the utility proof.
- Utility analysis: Events E5 and E6 control hash collisions among heavy items and collisions from non-heavy items in the same encoded buckets.Pairwise independence and conditional concentration bounds yield the required per-bucket guarantees.
- Utility analysis: Event E7 uses Hashtogram accuracy on most partitions to ensure reliable estimates for encoded bucket-symbol pairs.Its analysis conditions on balanced partitions from E4 and bounds bad partitions using the small-domain frequency-oracle guarantee.
4 Advanced Grouposition and Max-Information
The paper shows that local differential privacy provides advanced group privacy, with degradation proportional to about √k, and uses this to derive stronger max-information guarantees and lower bounds.
- Advanced Grouposition: The proof obtains the bound by concentrating cumulative privacy loss from independent local randomizers around its smaller expected loss.Each randomizer has expected privacy loss O(ε^2), substantially below the worst-case ε.
- Advanced Grouposition: Group privacy for k users under pure ε-LDP degrades with ε′ = kε^2/2 + ε√(2k ln(1/δ)), rather than linearly in k.The bound applies when two inputs differ in at most k entries and gives Pr[A(x) ∈ T] ≤ e^ε′ Pr[A(x′) ∈ T] + δ.
- Advanced Grouposition: For (ε, δ)-LDP, the corresponding group-privacy parameter is ε′ = kε^2/2 + ε√(2k ln(1/δ′)), with additive failure term δ + kδ′.This extends the advanced group-privacy guarantee to approximate local privacy.
- Max-Information: The improved group-privacy bound yields strong max-information guarantees for LDP protocols, supporting generalization in adaptive data analysis.Max-information measures how much an algorithm reveals about a randomly chosen input.
- Max-Information: Under arbitrary nonproduct input distributions, ε-LDP protocols have the same max-information behavior as ε-DP algorithms on product distributions.The paper connects this behavior to composition with arbitrary low-max-information algorithms while retaining generalization guarantees.
5 Composition for Randomized Response
This section constructs an approximate composition of randomized response that preserves the original distribution with high probability while achieving advanced-composition privacy guarantees.
- Construction and guarantee: For k randomized-response instances, the construction achieves privacy scaling as O(ε√(k ln(1/β))).The resulting distribution is β-close in statistical distance to the k-fold composition of randomized response.
- Construction and guarantee: The algorithm identifies a good output set G_x containing randomized-response outcomes with probability at least 1 − β.It returns the original outcome inside G_x and otherwise samples uniformly outside G_x.
- Scope: The result applies in the typical regime ε^2k ≤ ε, because it does not include the usual additive O(ε^2k) term from advanced composition.This is the stated scope limitation of the construction.
- Theorem: Theorem 5.1 guarantees pure differential privacy and, conditioned on an event of probability at least 1 − β, an output distribution identical to the composed randomized response.The theorem assumes ε^2k ln(1/β) ≤ 1.
- Privacy argument: The privacy proof shows that outputs outside G_x are sampled with probabilities comparable to those for outputs inside G_x.This comparison is the central step in establishing differential privacy for the modified mechanism.
6 From Approximate-Privacy to Pure-Privacy: A Generic Transformation with Short Reports
The paper gives a generic rejection-sampling transformation from non-interactive approximate-private local protocols to pure-private protocols with essentially the same utility, using short user reports.
- Transformation: The transformation converts any non-interactive (ε, δ)-LDP protocol into an O(ε)-LDP protocol with essentially the same utility guarantees.It is based on rejection sampling and extends a transformation of Bassily and Smith.
- Transformation: Removing the sample-resilience restriction increases per-user communication to O(log log n) bits.The transformation avoids requiring that the protocol remain well-approximated when run on a random subset of users.
- Implication: For non-interactive local protocols, approximate privacy therefore cannot provide more accurate algorithms than pure local privacy.The paper states this as the formal consequence of the generic transformation.
- Privacy guarantee: The resulting protocol satisfies pure 10ε-LDP, under ε ≤ 1/4 and T ≥ 5 ln(1/ε).This is the privacy guarantee established for Algorithm GenProt.
- Utility and communication: With δ ≤ εβ/[48n ln(2n/β)] and T = 2 ln(2n/β), the transformed protocol has total variation distance at most β from the original protocol and uses O(log log n) bits per user.The transformation therefore preserves the original protocol up to the stated statistical-distance bound.
- Utility and communication: The transformation increases any event probability by at most β + 6nTδe^ε.The analysis relates the transformed execution to the original protocol through high-probability good and privacy events.
7 A Lower Bound via Anti-Concentration
The section strengthens locally private frequency-estimation lower bounds to depend tightly on failure probability. Its proof combines approximate-to-pure privacy conversion, advanced grouposition, low mutual information, conditional independence, and anti-concentration.
- Motivation and result: The lower bound incorporates failure probability β and matches the new upper bound's dependence on β.The result strengthens prior lower bounds and establishes tightness with respect to failure probability.
- Proof strategy: The proof reduces approximate-LDP counting to a pure ε-LDP protocol estimating the number of ones with error Δ and success probability 1 − β.A generic transformation permits assuming pure privacy without loss of generality.
- Proof strategy: The reduction expands m = Cε^2n random bits into an n-user database by repeating each bit across approximately n/m users.The protocol's estimate is renormalized to estimate the number of ones in the original m-bit database.
- Proof strategy: Advanced composition makes each bit's transcript nearly private, yielding low mutual information and leaving many bits approximately unbiased and independent conditioned on the transcript.For sufficiently large C2, each bit satisfies I(Xj; Bj(r, Xj)) ≤ 1.
- Proof strategy: Anti-concentration then shows that the transcript cannot estimate the random database's number of ones accurately with failure probability below the stated β range.The argument applies a conditional anti-concentration bound to many good, independent coordinates.
A Simple Variant of Corollary 7.6
This section develops a simpler anti-concentration argument for independent Bernoulli variables whose expectations may differ but remain near one-half. It reduces the heterogeneous case to a two-type or binomial setting.
- Setup: The analysis targets sums of independent Bernoulli variables with probabilities bounded around one-half.The assumption is 1/2 − c ≤ pi ≤ 1/2 + c for every variable.
- Reduction: A replacement lemma converts one Bernoulli variable at a time to an extremal expectation, without decreasing the probability that the sum leaves an interval.Each replacement uses expectation 1/2 + c or 1/2 − c.
- Reduction: Applying the replacement iteratively yields independent variables whose expectations take only the two values 1/2 + c and 1/2 − c.At least half of the variables share one of these two types.
- Binomial reduction: Variables outside the majority type are replaced by constants, shifting the interval while preserving its length and reducing the problem to a binomial anti-concentration bound.The resulting interval has the same length as the original interval.
- Conclusion: The resulting theorem gives anti-concentration for independent, not necessarily identically distributed Bernoulli variables over failure probabilities β ≥ 2^-bn and sufficiently short intervals.The section supplies a simpler proof for the special case needed in the lower-bound application.
B Proof of Theorem 3.6 [22]
The proof constructs a unique-list-recoverable code using error-correcting codes, spectral expanders, and clustering. A heavy item's mostly correct coordinate encodings form a recoverable spectral cluster despite corrupted coordinates.
- Code guarantee: An (α, ℓ, L)-unique-list-recoverable code maps each domain element to M coordinate pairs and decodes it from lists containing most coordinates.The decoder returns a list of at most L candidates when each coordinate list contains distinct first components.
- Construction: The construction partitions a standard error-correcting encoding into M chunks and combines each chunk with a d-regular spectral expander.The expander has constant degree and controlled second eigenvalue.
- Decoder: The decoder builds a layered graph from list entries, treating each entry as suggestions for edges between coordinate-labelled vertices.Edges are retained when both endpoints suggest them.
- Cluster structure: With all correct encodings present, the vertices representing an element form an isolated copy of the expander; with at most αM bad coordinates, they form an O(α)-spectral cluster.Bad coordinates delete or add only a controlled number of internal and crossing edges.
- Recovery: A polynomial-time clustering algorithm recovers an approximate cluster, after which low-degree pruning and error correction recover the encoded domain element.The recovered cluster differs from the target by a sufficiently small fraction of encoding entries.
- List size: The number of identified elements remains O(ℓ), because each recovered cluster consumes a constant fraction of the graph's available volume.This controls the decoder's output list size.