Source-linked AI summary
Locally Differentially Private Frequency Estimation with Consistency
Tianhao Wang, Milan Lopuhaä-Zwakenberg, Zitao Li, Boris Skoric, Ninghui Li
TL;DR
Frequency-oracle designs that target unbiased, low-variance individual estimates may not be optimal for varied queries. The paper applies consistency-based post-processing to frequency estimates and finds that different methods suit individual, frequent-value, and subset queries.
Problem
Frequency-oracle estimates can be suboptimal for subset queries, where simply summing individual estimates is far from optimal, especially for large domains.
Source: §I · p. 1Method
The paper compares 10 post-processing methods that exploit non-negativity and the requirement that estimated frequencies sum to one.
Source: §I · pp. 1–2Results
The best method varies by task: non-negativity for individual values, sum-to-one for frequent values, and both constraints with Power for subset values.
Source: §I · p. 2Takeaways & Limitations
The paper recommends Base-Cut for full-domain estimation, Norm for most-frequent-value queries, and PowerNS or a synthetic-data optimum for set-value queries.
Source: §VII · p. 14Power requires knowledge or an assumption about the distribution, and noise or a mismatched distribution can lead to poor accuracy.
Source: E. Least Expected Square Error · p. 7
Abstract
from arXiv · showhide
Local Differential Privacy (LDP) protects user privacy from the data collector. LDP protocols have been increasingly deployed in the industry. A basic building block is frequency oracle (FO) protocols, which estimate frequencies of values. While several FO protocols have been proposed, the design goal does not lead to optimal results for answering many queries. In this paper, we show that adding post-processing steps to FO protocols by exploiting the knowledge that all individual frequencies should be non-negative and they sum up to one can lead to significantly better accuracy for a wide range of tasks, including frequencies of individual values, frequencies of the most frequent values, and frequencies of subsets of values. We consider 10 different methods that exploit this knowledge differently. We establish theoretical relationships between some of them and conducted extensive experimental evaluations to understand which methods should be used for different query tasks.
I. INTRODUCTION
FO protocols target unbiased, low-variance estimates of individual frequencies, but that design can be suboptimal for varied queries. The paper studies consistency-based post-processing and finds that the best method depends on the query task.
II. PROBLEM SETTING
- The setting has users perturbing private values before sending reports to an aggregator, which estimates the population distribution without seeing each user's actual value.Source: §I · p. 1, §II · p. 2
I. INTRODUCTION
- FO protocols estimate value frequencies, but unbiased estimates with minimized variance can still perform poorly for some query tasks.Source: §I · p. 1
- Subset-frequency queries matter for tasks such as comparing emoji categories, and summing individual estimates can be far from optimal, especially for large domains.Source: §I · p. 1
- Consistency uses the facts that frequencies are non-negative and sum to one, although exploiting these constraints can introduce bias that affects query types differently.Source: §I · p. 1
- For individual values, non-negativity alone performs best; for frequent values, sum-to-one alone performs best; for subsets, enforcing both with Power performs best.Source: §I · p. 2
- The paper introduces consistency properties and 10 post-processing methods, and establishes theoretical relationships between Constrained Least Squares and Maximum Likelihood Estimation.Source: §I · p. 2
II. PROBLEM SETTING
- Because randomized reports make estimated frequencies inaccurate, the paper evaluates estimates across individual-value, most-frequent-value, and subset queries using mean squared error.Source: §II · p. 2
III. FREQUENCY ORACLE PROTOCOLS
The paper reviews frequency-oracle protocols that let an aggregator estimate values from randomized reports, then describes how their encoding and randomization affect accuracy and communication. OLH balances hashing and randomization through its domain-size parameter.
A. Generalized Random Response (GRR)
- GRR reports the true value with probability p and a randomly selected alternative otherwise; its estimation variance grows linearly with domain size d.Source: A. Generalized Random Response (GRR) · pp. 2–3
B. Optimized Local Hashing (OLH)
- OLH hashes values into a smaller domain before randomized response, and its variance is minimized at g = e^ϵ + 1 or the closest integer.Source: B. Optimized Local Hashing (OLH) · p. 3
C. Other FO Protocols
- Optimized Unary Encoding has OLH's p and q and the same estimation variance, but its communication cost is linear in d.Source: C. Other FO Protocols · p. 3
- Subset Selection has lower variance than OLH, but for large domains offers essentially the same accuracy at higher communication cost.Source: C. Other FO Protocols · p. 3
- Hadamard Response uses a compressed subset for constant-size reports and faster aggregation than OLH, but is sub-optimal when g = 2 is sub-optimal.Source: C. Other FO Protocols · p. 3
D. Accuracy of Frequency Oracles
Frequency-oracle estimates can be post-processed to trade bias against variance using prior knowledge about the distribution. The paper examines these methods and starts from an unprocessed baseline.
D. Accuracy of Frequency Oracles
- When d is large and ϵ is not too large, the variance component involving the true frequency can be dominated by the other component, supporting an approximation that ignores the true frequency.Source: D. Accuracy of Frequency Oracles · p. 3
IV. TOWARDS CONSISTENT FREQUENCY ORACLES
- Post-processing can reduce variance by exploiting non-negativity, but setting negative estimates to zero creates positive bias; enforcing a total of one makes biases sum to zero without eliminating them.Source: §IV · p. 4
- The baseline applies the standard frequency oracle without post-processing, and has no bias with analytically computable variance.Source: §IV · p. 4
A. Baseline Methods
Baseline methods address negative frequency estimates or threshold out noise, while normalization methods impose a sum-to-one constraint, sometimes together with non-negativity. These choices redistribute bias: methods enforcing both constraints make low-frequency estimates positively biased, and the normalization variants differ in how they distribute bias.
A. Baseline Methods
- Base-Pos replaces negative estimates with zero, reducing variance for individual values but introducing positive bias that can grow significant for larger-range subset queries.Its estimates are at least as accurate as the Base method for each individual value.Source: A. Baseline Methods · p. 4
- Post-Pos clips negative query results to zero, matching Base-Pos for single values while producing smaller positive bias for subset queries.It can give inconsistent answers: a disjoint union's result may differ from the sum of its parts.Source: A. Baseline Methods · p. 4
- Base-Cut zeroes estimates below a sensitivity threshold, but its estimates need not sum to one and can reflect both negative and positive bias.The paper reports that α = 5% performs poorly when the population or ϵ is not large, and chooses α = 2 to target around two false positives.Source: A. Baseline Methods · pp. 4–5
B. Normalization Method
- Norm adds the same δ to each estimate to make their total one; it is unbiased but does not enforce non-negativity.It does nothing for GRR, Hadamard Response, and Subset Selection, whose estimates already sum to one, but changes OLH estimates.Source: B. Normalization Method · p. 5
- Any method that makes estimates non-negative and sums them to one gives positive bias to values sufficiently close to zero.Because total bias across the domain must sum to zero, methods enforcing both constraints differ in how they distribute bias.Source: B. Normalization Method · p. 5
- Norm-Mul scales zero-clipped estimates to sum to one, Norm-Sub adds an offset after clipping, and Norm-Cut zeros low estimates to address Norm-Sub's larger negative biases on higher-frequency items.Norm-Mul can perform poorly on skewed distributions; Norm-Sub distributes bias more evenly, while Norm-Cut may leave the total below one.Source: B. Normalization Method · pp. 5–6
C. Constrained Least Squares
Constrained Least Squares (CLS) treats frequency recovery as constraint inference: it finds estimates that minimize least-squares error while enforcing non-negativity and a sum of one. Norm-Sub is the CLS solution.
C. Constrained Least Squares
- CLS recovers frequencies from standard FO estimates by minimizing least-squares error subject to non-negativity and sum-to-one constraints.The paper frames this as a constraint-inference problem.Source: C. Constrained Least Squares · p. 6
- Norm-Sub is the solution to the CLS formulation, with δ set to −1 divided by the number of values in D1.D1 is one of the two disjoint parts into which the KKT solution partitions the domain.Source: C. Constrained Least Squares · p. 6
D. Maximum Likelihood Estimation
The section presents maximum likelihood estimation as distribution recovery from LDP reports, using a uniform prior and constraints on the recovered frequencies. It relates the approximate MLE to Norm-Sub and CLS under stated conditions.
D. Maximum Likelihood Estimation
- MLE seeks the frequency distribution that maximizes the likelihood of the FO estimates, using a uniform prior because the paper assumes no prior distribution.The estimates are modeled as independent Gaussian variables centered on the original frequencies.Source: D. Maximum Likelihood Estimation · p. 6
- MLE-Apx uses standard FO estimates and maximizes likelihood subject to non-negativity and sum-to-one constraints.The paper uses KKT conditions to obtain an efficient solution.Source: D. Maximum Likelihood Estimation · p. 6
- Norm-Sub and MLE-Apx give very close results when γ is approximately 1, and CLS is equivalent to MLE when the frequency component in the variance is dominated by the other component.The paper describes MLE-Apx as a hybrid of Norm-Sub and Norm-Mul.Source: D. Maximum Likelihood Estimation · pp. 6–7
E. Least Expected Square Error
The Power method fits a distribution to FO estimates and minimizes expected squared error, while PowerNS applies Norm-Sub afterward to make results consistent. Power depends on the assumed distribution and can be inaccurate under heavy noise or model mismatch.
E. Least Expected Square Error
- Power fits a Power-Law distribution to FO estimates and minimizes expected squared error to recover frequencies.The approach assumes a Power-Law or Gaussian distribution whose one or two parameters are fitted from the estimates.Source: E. Least Expected Square Error · p. 7
- Power requires a distribution assumption; too much noise or a mismatched distribution can lead to poor accuracy, and Power alone does not ensure estimates sum to one.PowerNS applies Norm-Sub after Power to make the results consistent.Source: E. Least Expected Square Error · p. 7
F. Summary of Methods
The methods enforce non-negativity, a sum of one, or both, with some also using a power-law assumption. Experiments compare these methods across datasets and query tasks, while bias and variance analyses show how post-processing changes estimation behavior.
F. Summary of Methods
- The methods preserve frequency order and fall into non-negativity-only, sum-to-one-only, or combined-constraint classes; Norm-Sub is equivalent to MLE-Apx under the stated variance condition.Power and PowerNS additionally exploit a power-law assumption.Source: F. Summary of Methods · p. 7
A. Experimental Setup
- Experiments use synthetic Zipf and real Emoji data, simulate OLH, and evaluate full-domain, set-value, and frequent-value estimation.The evaluation compares mean squared error across the three query scenarios.Source: A. Experimental Setup · pp. 7–8
B. Bias-variance Evaluation
- Base and Norm are unbiased on Zipf, while Base-Pos adds positive bias; Norm-Sub and Power primarily alter low-frequency estimates, with rank-dependent effects.For Norm-Sub, subtraction affects high-frequency values more, while zeroing negative estimates affects low-frequency values; Power changes low-frequency estimates more than top estimates.Source: B. Bias-variance Evaluation · pp. 8–9
- Variance is similar across values for Base and Norm, with Norm slightly lower; for the other methods, variance decreases with rank as low-frequency estimates are mostly zero.Source: B. Bias-variance Evaluation · p. 9
C. Full-domain Evaluation
Full-domain, set-value, and frequent-value queries favor different post-processing methods. The evaluations show that both the query task and the method’s adjustments affect which approach performs best.
C. Full-domain Evaluation
- PowerNS, Base-Cut, Norm-Sub, MLE-Apx, and Power perform similarly on full-domain MSE, while Base-Cut is recommended for unknown distributions and PowerNS for power-law-like ones.Norm-Sub and MLE-Apx perform almost identically; on the evaluated datasets, PowerNS performs best.Source: C. Full-domain Evaluation · p. 9, Figure 4 · p. 11
- PowerNS achieves the best full-domain performance in the evaluated methods and can save around 90% of users compared with unprocessed data.The user-saving comparison uses the equivalent sample size without post-processing.Source: C. Full-domain Evaluation · p. 10, Figure 5 · p. 11
D. Set-value Evaluation
- For small random subsets, errors increase with set size and approach full-domain performance as ρ becomes small; Norm-Cut can outperform Base-Cut, especially when ρ ≥ 2.Norm-Mul is an exception among sum-to-one methods because multiplication biases large estimates.Source: D. Set-value Evaluation · p. 11
- At ρ = 90, PowerNS outperforms non-normalizing methods by at least 2 orders of magnitude in set-value MSE; normalizing methods show symmetric error around ρ = 50.The symmetry follows because, after normalization, estimating a set above 50% is equivalent to estimating its complement.Source: D. Set-value Evaluation · p. 10, Figure 6 · p. 12
E. Frequent-value Evaluation
- For frequent-value queries, Base, Base-Pos, Post-Pos, and Norm perform consistently across k, while Norm-Mul has at least 10× worse MSE than the other methods.Base-Cut’s threshold trades off frequent-value and set-value accuracy; when the desired k is known, the threshold can be set to the kth-highest estimate.Source: E. Frequent-value Evaluation · p. 12
F. Discussion
The discussion recommends choosing post-processing by query type: Base-Cut for single values, Norm for frequent values, and PowerNS or synthetic-data selection for set queries. The paper relates several methods and concludes that consistency constraints should be selected according to the task.
F. Discussion
- Norm-Sub and MLE-Apx perform similarly, as do Base and Norm.The paper reports these empirical similarities when verifying connections among methods.Source: F. Discussion · p. 13
- When many values have low frequency, converting low estimates to zero benefits single-value query utility.The discussion recommends Base-Cut for this task.Source: F. Discussion · p. 13
VI. RELATED WORK
- Prior LDP frequency-oracle work includes OLH, Hadamard Response, and Subset Selection; Subset Selection improves accuracy over OLH at higher communication cost.The related-work discussion also describes post-processing for centralized DP and other LDP settings, including consistency-related methods.Source: §VI · p. 14
VII. CONCLUSION
- For full-domain estimation, use Base-Cut; for frequent values, use Norm; and for set-value queries, use PowerNS or select a method using synthetic data.These are the paper’s task-specific recommendations.Source: F. Discussion · p. 13, §VII · p. 14
APPENDIX A SOLUTION FOR CLS
The appendix derives the CLS solution using KKT conditions and characterizes an iterative procedure for identifying values whose estimates are set to zero.
APPENDIX A SOLUTION FOR CLS
- The CLS derivation augments the optimization target with KKT conditions and uses convexity to find the minimum through partial derivatives.The derivation notes that b = 0 and a = μ is constant, leaving the minimizing condition unchanged.Source: Appendix A · p. 16
- For a proposed zero-estimate set D0, the derivation solves for estimates on D1 = D \ D0 while assigning zero to values in D0.The supplied passage introduces this partition and describes the resulting estimate assignment.Source: Appendix A · p. 16
APPENDIX B SOLUTION FOR MLE-APX
The appendix derives the approximate MLE by simplifying its objective and solving for estimates under a partition into zero and positive values.
APPENDIX B SOLUTION FOR MLE-APX
- The appendix simplifies the exponent by substituting the variance expression from Equation (3) and introducing x_v as temporary notation.The displayed derivation proceeds from the resulting equation using x_v.Source: Appendix B · p. 16
- The exponent’s squared term makes it vary most with f′ for large n, dominating the coefficient term.This is the stated rationale for the exponent’s form.Source: Appendix B · p. 16
- The MLE-Apx derivation uses KKT conditions, then takes partial derivatives of the convex target to obtain its minimizing conditions.With b = 0 and a = μ constant, the minimizing condition is unchanged.Source: Appendix B · p. 16
- For a partition with zero estimates in D0 and positive estimates in D1, the solution for x_v on D1 is shared across values and is found by summing their estimates.The method computes estimates for D1 from x_v, sets estimates in D0 to zero, and iteratively moves values with negative a_x into D0.Source: Appendix B · p. 16