Source-linked AI summary
Discrete Distribution Estimation under Local Privacy
Peter Kairouz, Keith Bonawitz, Daniel Ramage
TL;DR
The paper asks how to estimate discrete distributions while protecting individuals through local privacy rather than collecting raw data. It studies privacy–utility trade-offs, proves optimality results, and develops hashed randomized-response mechanisms. The results establish regime-dependent order optimality and report strong empirical utility for the new mechanisms, while noting that raw-data collection is not yet fully replaceable.
Problem
The paper addresses how providers can obtain useful discrete-distribution statistics without collecting raw user data, amid privacy risks from data retention and compromise.
Method
The paper combines theoretical analysis of locally private distribution estimation with randomized-response mechanisms, cohort-style hashing, and sparse hashed-output encoding.
Results
RAPPOR is order optimal in the high privacy regime, k-RR in the low privacy regime, and O-RR empirically meets or exceeds existing mechanisms across stated privacy settings.
Takeaways & Limitations
O-RR offers a single mechanism whose parameters can be adjusted to provide maximal privacy at a desired utility level for a fixed report count.
Takeaways & Limitations
The paper leaves nonstationary distributions, unequal privacy requirements across responses, and complete replacement of un-noised data for future work.
Abstract
from arXiv · showhide
The collection and analysis of user data drives improvements in the app and web ecosystems, but comes with risks to privacy. This paper examines discrete distribution estimation under local privacy, a setting wherein service providers can learn the distribution of a categorical statistic of interest without collecting the underlying data. We present new mechanisms, including hashed K-ary Randomized Response (KRR), that empirically meet or exceed the utility of existing mechanisms at all privacy levels. New theoretical results demonstrate the order-optimality of KRR and the existing RAPPOR mechanism at different privacy regimes.
1. Introduction
The paper studies discrete distribution estimation under local privacy to retain population-level utility without collecting raw user data. It establishes optimality results for randomized response mechanisms and introduces hashed mechanisms with strong empirical performance across privacy regimes.
- Motivation: Local privacy lets providers estimate categorical distributions while sharing only noised versions of users’ raw data.The motivation is to obtain usage statistics and count-based machine-learning capabilities while reducing privacy risks from raw-data collection.
- Theoretical results: Warner’s randomized response is globally optimal for binary alphabets under every loss function and privacy level.
- Theoretical results: RAPPOR is order optimal at high privacy but strictly sub-optimal at low privacy, whereas k-RR has the reverse pattern for ℓ1 and ℓ2 losses.
- Empirical results: For skewed distributions, the projected estimator offers the best utility across broad privacy levels and sample sizes.
- New mechanisms: O-RR extends k-RR with hash functions and cohorts for open alphabets, meeting or exceeding RAPPOR empirically across many privacy settings.
- New mechanisms: For closed k-ary alphabets, O-RR replaces hashing with permutations and meets or exceeds k-RR and RAPPOR in low and high privacy regimes.
2. Preliminaries
The preliminaries formulate private distribution estimation as recovering a population distribution from independently privatized observations. They characterize the privacy–utility trade-off and show that high-privacy estimation incurs an alphabet-size-dependent effective sample-size penalty.
- Local differential privacy: An ε-locally private mechanism maps each discrete input to a randomized output, represented as a row-stochastic matrix.
- Private distribution estimation: The private multinomial problem estimates p from privatized observations distributed according to m = pQ rather than the original distribution p.
- Privacy versus utility: The analysis formalizes privacy–utility trade-offs by minimizing minimax risk over all ε-locally differentially private mechanisms.
- Privacy versus utility: Minimax estimation is generally intractable, and even the non-private minimax estimator under ℓ1 loss remains unknown.
- Privacy versus utility: For ε ≤1, local privacy reduces effective sample size from n to nε^2/k, requiring a factor of k/ε^2 more samples for equal minimax risk.
3. Binary Alphabets
For binary distributions, the paper analyzes Warner’s randomized response and proves it achieves the optimal privacy–utility trade-off for minimax estimation under every loss and privacy level.
- Warner’s randomized response: Warner’s randomized response asks either a binary predicate or its negation according to a privately flipped biased coin.
- Warner’s randomized response: With η = e^ε for ε ≥0, Warner’s randomized response is represented by a 2 × 2 row-stochastic matrix.
- Optimality: Warner’s randomized response is optimal for every binary distribution, loss function, and privacy level.
- Optimality: The proof uses a strong Markovian dominance result and the data processing inequality to show no binary private mechanism has lower risk.
4. k-ary Alphabets
For k-ary alphabets, k-RR and k-RAPPOR have complementary privacy-regime strengths: k-RR is order optimal at low privacy, while k-RAPPOR is order optimal at high privacy. Simulations further show that decoding performance depends on the distribution shape, with projected decoding generally strongest for skewed distributions.
- Theoretical comparison: k-RAPPOR is order optimal in the high privacy regime but sub-optimal in the low privacy regime, while k-RR shows the converse pattern.These conclusions hold under both ℓ1 and ℓ2 losses.
- Theoretical comparison: For small ε, k-RR effectively reduces the sample size to nε^2/k^2, whereas for ε approximately ln k it reduces it to n/4.The latter regime is order optimal, although k-RR is not optimal for small ε.
- Theoretical comparison: For small ε, k-RAPPOR effectively reduces the sample size to nε^2/4k, while for ε approximately ln k it reduces it to n/k.This makes k-RAPPOR order optimal in the high privacy regime but strictly sub-optimal in the moderate-to-low privacy regime.
- Decoding: The projected decoder substantially outperforms normalized and maximum-likelihood alternatives for both k-RR and k-RAPPOR on skewed distributions across tested k and ε values.This result held across user counts from 30 to 10^6 and all evaluated distributions except the least-skewed Dirichlet distribution.
- Decoder comparison: The best k-RAPPOR decoder outperforms the best k-RR decoder for relatively large k and low ε, while k-RR is slightly better when k < e^ε.As the number of users increases, k-RR’s low-privacy advantage shrinks.
5. Open Alphabets, Hashing, and Cohorts
The paper extends k-RR and RAPPOR to open alphabets using hashing and cohorts, then adapts them to closed alphabets with permutations. Across experiments, O-RR matches or exceeds competing mechanisms, especially with projected decoding and minimal perfect hashing.
- 5.1. Open-Alphabet Mechanisms: Open alphabets are handled by combining hash functions with randomly assigned cohorts, giving each cohort an independent view of the underlying distribution.Each cohort hashes symbols into k subsets before privatization.
- 5.1.1. Encoding and Decoding: The hashed representation forms a sparse kC × S binary matrix H with exactly C nonzero entries in each column.This matrix encodes each candidate symbol’s hashed outputs across cohorts.
- 5.1.1. Encoding and Decoding: O-RR decoding estimates the candidate distribution from the expected privatized output using least-squares inversion, followed by projection onto the probability simplex.The simplex projection is used because empirical estimates can contain negative entries and performs best in the reported experiments.
- 5.3. Open-Alphabet Evaluation: For unknown alphabets, O-RR matches O-RAPPOR at very low and high privacy and exceeds it at intermediate privacy settings.This result is reported for a geometric distribution with n = 10^6 users.
- 5.4. Improved Utility for Closed Alphabets: For closed alphabets, replacing hash functions with minimal perfect hashes significantly improves O-RR, which meets or exceeds all other mechanisms at every considered ε.O-RAPPOR benefits little from the same replacement, while k-RAPPOR and O-RAPPOR have nearly indistinguishable utility.
6. Conclusion
The paper argues that locally private distribution estimation can retain data-driven utility without collecting raw data. Its results identify cohort-style hashing combined with k-ary randomized response as a practical approach, while future work remains for changing distributions and heterogeneous privacy needs.
- Conclusion: Local-private distribution estimation aims to provide population-level statistics without collecting raw user data.The paper frames this as a response to privacy risks from storing and analyzing user datasets.
- Conclusion: For fixed user populations and required utility, O-RR may provide a single mechanism whose privacy level is adjusted through its parameters.The conclusion presents this as a practical implication for differential privacy practitioners.
- Conclusion: Future work includes estimating nonstationary distributions and handling cases where some responses require more privacy than others.The authors also state that eliminating the collection of un-noised data entirely requires further work.
A. Proof of Theorem 2
The proof establishes that applying a differentially private mechanism cannot reduce the non-private minimax risk lower bound. It does so by showing that any private estimator can be converted into a randomized non-private estimator with the same risk.
- Proof strategy: The proof reduces the theorem to a data-processing inequality stating that post-processing a mechanism cannot improve its minimax risk.For every row-stochastic matrix W, the risk of WQ is at least the risk of Q.
- Proof strategy: A private estimator achieving rℓ,ε,k,n(Q) can be composed with Q to form a randomized estimator on raw observations having the same risk.This directly yields rℓ,k,n ≤ rℓ,ε,k,n(Q).
- Limit argument: If the private minimax risk is not attained, a sequence of estimators approaching it supplies the corresponding limiting argument.Taking the limit establishes the non-private risk lower bound and completes the proof.
B. Proof of Proposition 3
For k-RR with the empirical estimator, the proof derives an explicit risk expression from the mechanism’s privatized observations. This expression supports the paper’s effective-sample-size characterization in the high-privacy regime.
- Risk calculation: The proof specializes the minimax-risk analysis to QKRR with the empirical estimator defined earlier.It then expands the resulting expression in terms of ε, k, n, and the distribution coordinates.
C. Proof of Proposition 4
The proof fixes k-RAPPOR and its empirical estimator, introduces notation linking ε to estimator parameters, and derives the corresponding expression used in the argument.
- It defines A and B from e^(ε/2), then sets C = BA and relates 1 − B to e^(ε/2)B.
- Using m_i = p_iC + B, the proof rewrites the estimator-related quantities in terms of p_i, C, and B.
- The proof fixes Q to Q_k-RAPPOR and uses the empirical estimator for p.
D. Proof of Proposition 5
The section formalizes discrete distribution estimation and compares empirical-estimator behavior under ℓ1 and ℓ2 loss, including the role of the uniform distribution as a worst case.
- Problem setup: Discrete distribution estimation observes n i.i.d. samples from p ∈ S_k and estimates the probability vector p.
- Problem setup: An estimator maps the observations to S_k, and its performance is measured with a loss such as ℓ1 or ℓ2 distance.
- Empirical estimation: The maximum-likelihood estimator equals the empirical estimator, with estimate p̂_i = T_i/n, and is unbiased.
- Empirical estimation: Under ℓ2 loss, the empirical estimator’s risk scales as 1/n.
- Empirical estimation: The uniform distribution is the worst distribution for the empirical estimator under both ℓ1 and ℓ2 loss.
E.2. Minimax estimation
This section contrasts minimax and empirical estimation, then describes constrained private decoders and the parameter conditions needed for accurate open-alphabet recovery.
- Minimax estimation: The minimax estimator minimizes expected loss under the worst distribution, but its ℓ1 form is not known.
- Minimax estimation: The minimax estimator is not asymptotically unbiased and improves only slightly over the empirical estimator under the worst-case uniform distribution.
- Minimax estimation: The empirical estimator’s worst-case loss is roughly as good as the minimax risk under ℓ1 loss.
- Private decoding: For k-RR, maximum-likelihood decoding constrains estimates to the probability simplex by zeroing negative entries and recomputing a normalization parameter.
- Open-alphabet recovery: Accurate open-alphabet decoding requires distinguishable encoded strings, at least S independent equations, and enough users to control estimator variance.