Source-linked AI summary
Boosting the Accuracy of Differentially-Private Histograms Through Consistency
Michael Hay, Vibhor Rastogi, Gerome Miklau, Dan Suciu
TL;DR
Differentially private histogram workloads can produce noisy answers that are inconsistent or less accurate than necessary. The paper chooses query sets with known consistency constraints and post-processes private outputs into the closest consistent answers. The resulting techniques significantly improve accuracy for graph degree sequences and arbitrary-range histograms while retaining differential privacy.
Problem
Differentially private query workloads can involve accuracy trade-offs, inconsistent answers, and accumulated noise that limits universal histograms for larger ranges.
Method
The paper selects queries with useful consistency constraints and applies constrained inference to compute the closest consistent solution from differentially private noisy answers.
Results
Unattributed-histogram error is at least an order of magnitude lower than existing techniques, while universal-histogram error for larger ranges can decrease by 45-98%.
Takeaways & Limitations
Consistency constraints can boost histogram accuracy without diminishing the differential privacy guarantee, including for graph degree sequences and arbitrary range queries.
Takeaways & Limitations
Accuracy gains depend on the input database and privacy parameters, and may be absent when noisy answers already satisfy the constraints.
Abstract
from arXiv · showhide
We show that it is possible to significantly improve the accuracy of a general class of histogram queries while satisfying differential privacy. Our approach carefully chooses a set of queries to evaluate, and then exploits consistency constraints that should hold over the noisy output. In a post-processing phase, we compute the consistent input most likely to have produced the noisy output. The final output is differentially-private and consistent, but in addition, it is often much more accurate. We show, both theoretically and experimentally, that these techniques can be used for estimating the degree sequence of a graph very precisely, and for computing a histogram that can support arbitrary range queries accurately.
1. INTRODUCTION
The paper improves differentially private histogram accuracy by selecting queries with consistency constraints and post-processing noisy answers into the closest consistent solution. It applies this strategy to unattributed and universal histograms, reporting substantial accuracy gains while preserving privacy.
- Motivation: Differential privacy answers queries with calibrated random noise, but workloads can create trade-offs between component accuracy, aggregate accuracy, and consistency.Requesting only grade-category counts causes noise to accumulate when computing totals, while requesting all related counts increases sensitivity and noise.
- Overview of Approach: The approach chooses queries whose answers satisfy known consistency constraints, sends them through a standard differentially private mechanism, and post-processes the noisy output.Constrained inference finds the closest answer set satisfying the constraints, without accessing the private database.
- Contributions: The inferred answers can be significantly more accurate than the noisy answers, with unattributed-histogram error at least an order of magnitude lower and universal-histogram error reductions of 45-98% for larger ranges.The paper reports theoretical error bounds, efficient closed-form inference techniques, and experiments on real datasets.
- Overview of Approach: Constrained inference preserves differential privacy because it uses only noisy answers and public query constraints as post-processing.A constraint such as xp = xA + xB + xC + xD follows from the query definitions rather than database-specific information.
- Contributions: Accuracy gains depend on the input database and privacy parameters; inference never reduces accuracy, but may provide no improvement when noisy answers already satisfy the constraints.The paper reports that many real datasets have distributions where the techniques significantly improve accuracy.
- Histogram tasks: The paper studies unattributed histograms, including graph degree sequences, and universal histograms that support arbitrary interval counts.Unattributed histograms return only a multiset of frequencies, whereas universal histograms retain statistics sufficient for irregular and overlapping ranges.
2. BACKGROUND
The paper formulates private histogram tasks as query sequences, adds calibrated Laplace noise, and then uses constrained inference to produce consistent answers without weakening privacy.
- Query sequences: Histogram tasks are represented as query sequences whose entries are counting queries over ranges, with database evaluation returning a vector of non-negative integers.The conventional unit-range histogram queries every unit-length range.
- Differential privacy: The Laplace mechanism answers query sequences by adding independent zero-mean noise scaled to query sensitivity and the privacy parameter ϵ.For the unit-range sequence L with sensitivity 1, the total mean squared error is 2n/ϵ^2.
- Constrained inference: Constrained inference finds the minimum-L2 answer vector satisfying known query constraints while remaining closest to the noisy vector.The constraints describe properties of the query, such as xp = xA + xB + xC + xD, rather than properties requiring access to the private database.
- Privacy guarantee: Post-processing the noisy answers preserves ϵ-differential privacy because the inference step uses only the noisy output and public constraints.The paper states this formally: if ˜Q is ϵ-differentially private, then the inferred process Q is also ϵ-differentially private.
3. UNATTRIBUTED HISTOGRAMS
For unattributed histograms, the paper sorts unit-range counts before adding noise, creating ordering constraints that constrained inference can exploit. Accuracy improves especially when many true counts repeat, while privacy and initial noise remain unchanged.
- 3. UNATTRIBUTED HISTOGRAMS: Unattributed histograms need the multiset of unit-range counts but not each count’s association with a particular range, so the paper queries counts in sorted order.For example, ⟨2, 0, 10, 2⟩ becomes ⟨0, 2, 2, 10⟩.
- 3. UNATTRIBUTED HISTOGRAMS: The sorted query sequence S has sensitivity 1, so its differentially private noisy answers have the same noise magnitude and accuracy as those for L.Sorting introduces inequality constraints S[i] ≤ S[i + 1] that identify out-of-order noisy values as inconsistencies.
- 3.1 Constrained Inference: Computing S: Constrained inference computes the closest ordered sequence to the noisy sorted counts, using the unique minimum-L2 solution characterized by Theorem 1.The optimization minimizes ||˜s − s||2 subject to s[i] ≤ s[i + 1].
- 3.2 Utility Analysis: the Accuracy of S: Uniform subsequences are effectively averaged toward their true value, whereas a unique count may remain unchanged by constrained inference.In the example, positions 1–20 are uniform and refined, while the unique count at position 21 satisfies s[21] = ˜s[21].
- 3.2 Utility Analysis: the Accuracy of S: The error bound depends on the number and multiplicities of distinct true counts: error(S) = O(d log3 n/ϵ^2), compared with error(˜S) = Θ(n/ϵ^2).When d ≪ n, the paper reports substantially lower error and observes orders-of-magnitude improvements on real data; when d = n, both errors scale linearly in n.
4. UNIVERSAL HISTOGRAMS
Universal histograms use hierarchical interval queries and constrained inference to produce consistent estimates that support accurate range queries under differential privacy.
- The conventional unit-length strategy becomes unreliable for large ranges because noise accumulates under summation.
- The hierarchical query sequence adds larger-granularity intervals, enabling range queries to combine only a small number of noisy counts.Its intervals form a k-ary tree whose leaves are unit-length ranges.
- The hierarchical sequence has sensitivity ℓ, so its differentially private mechanism adds more noise than the unit-length sequence.
- Constrained inference finds the minimum-L2 consistent estimate from noisy hierarchical counts, using a least-squares interpretation and a linear-time tree recurrence.The computation uses bottom-up and top-down scans.
- ˜L is better for small ranges, but ˜H becomes preferable for large ranges because its error grows poly-logarithmically rather than linearly with range size.H can also outperform ˜H on some queries and can reduce error in sparse regions through a non-negativity heuristic.
- The consistent estimator H is unbiased, minimizes mean squared error among linear unbiased estimators derived from ˜h, and has error O(ℓ3/ϵ2) for every range query.
5. EXPERIMENTS
Experiments on three real datasets evaluate constrained inference for unattributed histograms and universal histograms across privacy levels and query sizes.
- 5.1 Unattributed Histograms: The experiments use NetTrace, Social Network, and Search Logs, with average squared error measured over 50 randomized mechanism outputs.
- 5.1 Unattributed Histograms: The improvement over rounding and sorting suggests that constrained inference contributes beyond enforcing integrality and non-negativity alone.
- 5.1 Unattributed Histograms: Constrained inference reduces unattributed-histogram error by at least an order of magnitude across all datasets and tested ϵ settings.
- 5.2 Universal Histograms: Figure 6 compares ˜L, ˜H, and H across range sizes, privacy settings, and the NetTrace and Search Logs datasets on log-scaled axes.
- 5.2 Universal Histograms: For ranges larger than about 2000 units, ˜H outperforms ˜L, with ˜L error 4-8 times larger for the largest ranges.
- 5.2 Universal Histograms: H has uniformly lower error than ˜H across range sizes, privacy settings, and datasets, with greater relative benefit at smaller ϵ.H can also outperform ˜L on small ranges when histograms contain sparse regions.
6. RELATED WORK
The paper builds on prior consistency post-processing, synthetic-data, hierarchical, wavelet, matrix-mechanism, and continual-release approaches while distinguishing its accuracy and scaling properties.
- Barak et al. introduced post-processing for consistent marginals, but did not show that post-processing improves accuracy.
- Blum et al.’s synthetic-data method scales slightly better in domain size, while the hierarchical histogram has lower fixed-domain error and avoids database-size growth.
- The paper relates H to Haar-wavelet and matrix-mechanism formulations, noting equivalent error for binary H queries.
- Related work also includes adaptive hierarchical querying and differentially private counters for continual release.
7. CONCLUSIONS
The conclusions present consistency-preserving post-processing and carefully designed query sets as ways to improve accuracy under differential privacy without weakening privacy guarantees.
- The approach combines query-set design, consistency constraints, and closest-consistent-solution inference to boost accuracy.
- Histogram query strategies admit closed-form solutions for efficiently computing consistent answers.
- Conventional differential privacy approaches can add more noise than the privacy condition strictly requires, motivating constraints as a route toward optimal query-answering strategies.
B. DISCUSSION OF MAIN RESULTS
The discussion shows that consistency-based inference improves histogram accuracy while preserving differential privacy, with benefits and limitations depending on the task and constraints.
- Unattributed histograms: Degree-sequence estimation improves error by an order of magnitude over the baseline technique.The sorted-query approach benefits from inequality constraints and works best when counts are duplicated.
- Future work includes graphicality constraints for degree sequences and extensions of universal histograms to multidimensional queries.The authors also identify higher branching factors as a possible optimization.
- Universal histograms: For universal histograms, hierarchical queries trade higher sensitivity for constraints that can outweigh the additional noise on some data sets and privacy levels.Hierarchical methods are more accurate for all but the smallest ranges in some cases.
- Universal histograms: Large, sparse domains limit the practical value of small-range accuracy because privacy noise can overwhelm unit-length query signals.In such settings, no differentially private technique can provide meaningful unit-length answers.
- Across both histogram tasks, the estimators achieve greater accuracy without sacrificing privacy.The improved estimators imply more accurate noise distributions than independent Laplace noise, although optimal query-set mechanisms remain open.
- The approach may extend beyond histograms, but useful low-sensitivity constraints and efficient constrained inference are difficult to obtain generally.The optimization problem is NP-Hard in general, whereas the constraint sets used for S and H admit efficient closed-form solutions.
C. ADDITIONAL EXPERIMENTS
The additional experiments examine privacy-preserving graph and search datasets, illustrate why sorted-sequence inference reduces error, and provide supporting proof details for the query mechanisms.
- NetTrace protects individual network connections, while Social Network protects friendships in a graph of roughly 11,000 university students.The Social Network experiments assume the graph size is public knowledge.
- Figure 7 compares NetTrace ground truth with the average errors of S and ˜S for ϵ = 1.0.The sequence is sorted in descending order; uniform-count stretches and count transitions are visually distinguished.
- Search Logs experiments use a synthetic dataset combining published summary statistics with shorter-period actual logs.Ground truth refers to this synthetic dataset, and privacy prevents associating entities with particular search terms.
- Unattributed histograms: Inference reduces error most strongly inside long uniform subsequences, reaching zero at positions between count changes.Larger error remains near the beginning and around transition points.
- Unattributed histograms: Theorem 2’s error behavior is also observed locally in subsequences containing few distinct counts.This matters for real degree sequences because power-law data contain very large uniform subsequences.
- Adding or removing a tuple changes one count in L but affects ℓ tree counts in the hierarchical mechanism, giving sensitivity ℓ.The affected counts correspond to the leaf and its path to the root.
- The minimum L2 solution for a sorted sequence is uniquely characterized by bounds Lk and Uk, with s[k] = Lk = Uk.The proof derives these bounds using means of noisy subsequences and contradiction arguments.
D.2 Proof of Theorem 2
Theorem 2 bounds the error of the inferred sorted histogram in terms of the number of distinct counts, contrasting it with the error of independent noisy answers.
- Theorem 2 states that constants c1 and c2 independent of n and d bound the inferred sequence’s error.Here n is the number of values and d is the number of distinct values in S(I).
- error(S) = O(d log3 n/ϵ2) whereas error(˜S) = Θ(n/ϵ2).The proof decomposes the error across repeated distinct values and bounds each contribution using noisy subsequence means.
- The analysis exploits the unique minimum L2 solution characterized by Theorem 1 and translation-invariant per-position error.This permits treating a selected true count as zero before bounding the inferred value.
- The proof bounds upper and lower deviations using events controlling noisy subsequence means and applies probabilistic lemmas to obtain expected-error bounds.The resulting bounds depend logarithmically on distances to the repeated-count block’s endpoints.
D.3 Proof of Theorem 3
Theorem 3 derives a recurrence for the unique minimum L2 solution on a hierarchical query tree by reducing constrained optimization to subtree-wise calculations.
- Theorem 3 gives the unique minimum L2 solution h as a recurrence based on each node’s parent and auxiliary quantity z.The recurrence is obtained from the noisy hierarchical sequence ˜h = ˜H(I).
- The root value is solved first, then each subtree is optimized after its parent value has been fixed.Values outside the relevant subtree do not affect the node’s calculation once the parent is known.
- For a leaf, the first-order equations correspond to matching sums along its path to the root.Summing these path equations yields the root-level relation used to compute h[r].
- Lagrange multipliers solve the subtree minimization subject to the constraint that the child leaves sum to the fixed parent value.The derivation introduces a multiplier, solves for it, and substitutes it into the node equations.
D.4 Proof of Theorem 4
Theorem 4 establishes that H is unbiased and optimal among linear unbiased estimators, while providing error bounds and an example where it substantially outperforms the noisy estimator.
- H is a linear unbiased estimator of the original leaf counts.The proof establishes unbiasedness inductively for every tree node, then for H itself.
- H has no greater error than any other linear unbiased estimator for every query q.This follows by modeling the noisy counts as observations and applying the Gauss-Markov theorem to the ordinary least squares estimator.
- For every query q, error(Hq) = O(ℓ^3/ϵ^2).Any query can be answered using at most kℓ tree nodes, while each node estimate has bounded error.
- For some query q, H achieves error(Hq) ≤ 3/[2(ℓ−1)(k−1)−k] error(˜Hq).The proof uses a query summing all leaves except the two extreme leaves; H uses the root and those two leaf estimates, whereas ˜H sums many noisy counts.
E. COMPARISON WITH BLUM ET AL.
The comparison evaluates ˜H against the Blum et al. binary-search histogram for differential-privacy usefulness on arbitrary range queries. ˜H has database-size-independent absolute-error bounds and scales better with ϵ.
- ˜H is compared with Blum et al.’s binary search equidepth histogram using (ϵ, δ)-usefulness for range queries.Usefulness requires every query in the class to have absolute error at most ϵN with probability at least 1−δ.
- Both techniques scale at most poly-logarithmically with the domain size.
- ˜H achieves the same utility guarantee with a database smaller by a factor of O(1/ϵ^2).
- For ˜Hq, the absolute-error bound is independent of database size and depends only on ϵ, α, and the range size.The error is analyzed as the magnitude of a sum of Laplace random variables associated with at most 2ℓ subtrees, followed by a union bound over all range queries.
- For Blum et al., absolute error increases with database size at rate O(N^2/3).