PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimizing Histogram Queries under Differential Privacy

Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, Andrew McGregor

arXiv:0912.4742v2cs.DBcs.CR

TL;DR

Answering correlated query workloads optimally remains an open problem because standard approaches can be suboptimal. The paper develops the matrix mechanism and a linear-query framework, then formulates optimal strategy selection as a rank-constrained semidefinite program and studies approximations and existing strategies.

  • Problem

    Optimal mechanisms for answering multiple correlated queries are not known, although correlated workloads arise naturally in shared-budget and structured-query settings.

  • Method

    The paper privately answers a strategy of linear counting queries, derives workload answers using an optimal consistent estimator, and analyzes strategy error geometrically.

  • Results

    The paper formulates minimum-error strategy selection as a rank-constrained semidefinite program, proposes efficient approximations, and uses the framework to analyze range-query techniques.

  • Takeaways & Limitations

    Designing strategy queries can answer correlated counting workloads more accurately while preserving differential privacy.

  • Takeaways & Limitations

    The paper has not yet produced optimal or approximately optimal strategies for specific workloads, and the semidefinite-program approach has high computational complexity.

Abstract

from arXiv · show

Differential privacy is a robust privacy standard that has been successfully applied to a range of data analysis tasks. Despite much recent work, optimal strategies for answering a collection of correlated queries are not known. We study the problem of devising a set of strategy queries, to be submitted and answered privately, that will support the answers to a given workload of queries. We propose a general framework in which query strategies are formed from linear combinations of counting queries, and we describe an optimal method for deriving new query answers from the answers to the strategy queries. Using this framework we characterize the error of strategies geometrically, and we propose solutions to the problem of finding optimal strategies.

1. INTRODUCTION

Differential privacy protects released data while providing accuracy guarantees, but answering correlated query workloads optimally remains unresolved. The paper introduces the matrix mechanism, formulates strategy selection as a rank-constrained semidefinite program, and analyzes related techniques through this framework.

  • Differential privacy protects individuals while offering precise accuracy guarantees for released data analyses.
  • The Laplace mechanism is optimal for a single query, but no optimal mechanism is known for multiple query answers.
  • Correlated queries can increase sensitivity and noise, making straightforward Laplace answers suboptimal for workloads such as range queries.Duplicate queries illustrate the issue: their pair sensitivity doubles, so averaging their noisy answers is less accurate than asking once.
  • The matrix mechanism answers a workload of linear counting queries by privately querying a separate strategy and deriving workload estimates from its noisy answers.Histograms, marginals, and data cubes can be represented as workloads of linear counting queries.
  • Its correlated noise can yield more accurate results for correlated workloads while preserving differential privacy.
  • The paper models minimum-total-error strategy selection as a rank-constrained semidefinite program and proposes two efficient approximations plus a strategy-improvement heuristic.It also uses the framework to analyze two range-query techniques and prove new error bounds.
  • The paper organizes its contributions around formal error analysis, strategy optimization, approximations, and comparisons with existing methods.

2. BACKGROUND

The paper represents databases as frequency vectors and queries as linear algebraic objects, then reviews differential privacy through sensitivity and Laplace noise. Query matrices organize multiple linear queries, while example matrices illustrate identity, hierarchical, and wavelet strategies.

  • 2.1 Linear queries: The analyst projects a relational database onto selected attributes and represents the resulting counts as a frequency vector x.The vector has one entry for each element of the selected attributes’ domain.
  • 2.1 Linear queries: A linear query computes a weighted sum of the counts in x, and a query matrix arranges multiple linear queries as rows.
  • 2.1 Linear queries: For a query matrix Q, the answer vector is obtained by the matrix product Qx.
  • 2.2 The Laplace mechanism: Differential privacy releases noisy query answers so outputs remain statistically close for neighboring databases differing by one record.
  • 2.2 The Laplace mechanism: Figure 1 compares full-rank identity, hierarchical, and Haar-wavelet query matrices over the four-element domain.I4 returns unit counts, H4 computes seven hierarchical sums, and W4 is based on the Haar wavelet.
  • 2.2 The Laplace mechanism: For the example matrices, sensitivities are ΔI4 = 1 and ΔH4 = ΔY4 = 3 because each count contributes to three hierarchical or wavelet queries.
  • 2.2 The Laplace mechanism: The Laplace mechanism adds independent noise whose scale depends on the privacy parameter and query-matrix sensitivity.For a matrix, sensitivity is the maximum L1 norm of a column.

3. THE MATRIX MECHANISM

The matrix mechanism answers a workload indirectly through a separately chosen query strategy, deriving consistent workload estimates from noisy strategy answers. Its reconstruction is based on linear algebra, with least squares providing the minimum-variance unbiased estimate, while strategy design controls sensitivity and error.

  • Query strategies and workloads: A query strategy is a matrix of linear queries used to derive estimates for a separate workload matrix.A strategy supports a workload query when that query is a linear combination of the strategy rows.
  • Query strategies and workloads: Full-rank strategies support all linear queries, while rank-deficient workloads can instead use a strategy whose row space spans the workload.The paper also describes adding a scaled identity or reducing dimensionality when needed.
  • Deriving query answers: The mechanism first estimates the true counts from noisy strategy answers, then computes each workload estimate as w x̂_A.For square strategies this reconstruction uses A^-1; for rectangular strategies it uses the pseudoinverse and least squares.
  • Deriving query answers: The least-squares estimate x̂_A is unbiased and has minimum variance among unbiased estimates linear in the noisy strategy answers.This provides a unique, consistent estimate even when multiple derivations of the counts are possible.
  • The matrix mechanism: The matrix mechanism remains differentially private while transforming independent Laplace noise into workload noise through the reconstruction matrix.Its potential accuracy advantage comes from scaling by strategy sensitivity and allowing correlated noise across workload answers.

4. THE ANALYSIS OF ERROR

The matrix mechanism’s error can be computed in closed form and understood through a strategy’s sensitivity and error profile. This analysis shows how covariance structure, workload geometry, and profile-equivalent strategies affect accuracy.

  • 4.1 The error of query estimates: For a full-rank strategy A, workload-query estimates are unbiased, and their mean squared error has a closed-form expression.The analysis derives corresponding expressions for individual queries and total workload error.
  • 4.2 Understanding error: A strategy’s error separates into a squared sensitivity term and a query-dependent profile term w(AtA)^-1w^t.Sensitivity uniformly scales error, while the profile determines how error varies across queries.
  • 4.2 Understanding error: Negative off-diagonal covariance terms can make a strategy accurate for aggregate queries even when its individual-count errors are relatively high.For H4 and Y4, higher sensitivity is offset for queries involving many counts, such as [1, 1, 1, 1].
  • 4.2 Understanding error: Good strategies balance sensitivity against the profile trace: the identity has sensitivity 1, while using the workload itself can produce low trace but high sensitivity.The paper uses these extremes to motivate strategies lying between them; directly answering the workload is worse than the matrix mechanism when m > n.
  • 4.3 Strategy matrix decomposition: The error profile is a positive-definite matrix whose quadratic form defines an ellipsoid, with eigenvalues controlling axis stretch and eigenvectors controlling rotation.This geometric representation characterizes how a strategy distributes error across the query space.

5. OPTIMIZATION

The section formulates optimal strategy selection as a rank-constrained semidefinite program and develops iterative, approximate, and heuristic methods. It also characterizes strategy error through sensitivity and error-profile matrices, with formal guarantees for optimal and approximate solutions.

  • Optimization problem: MinError asks for the strategy A minimizing TotalError_A(W) for a workload matrix W.
  • Optimization problem: MinError is difficult because sensitivity uses a nondifferentiable maximum of column L1 norms and the feasible strategy set is non-convex.
  • Exact optimization: MinError can be expressed as a semidefinite program with rank constraints, solvable through iterative pairs of related semidefinite programs.
  • Approximation methods: Two efficient approximations bound sensitivity using A^tA, effectively selecting an error profile and default rotation; rotations reducing sensitivity can further improve them.The methods are the L2 approximation and singular value bound approximation.
  • Exact optimization: Theorem 3 shows Program 5.1 returns an m × n strategy minimizing total error among all m × n strategies for an n × n workload.The rank constraint enforces Z = A^tA, while the objective upper-bounds total error up to constant factors.
  • Guarantees: n^2 bounds the number of queries in an optimal strategy when workload coefficients lie in {−1, 0, 1}.
  • Limitations: The rank-constrained semidefinite program has complexity at least O(m^3n^3), and its convergence iteration count is not bounded by known results.
  • Approximation methods: The L2 approximation is optimal when the optimal strategy contains only uncorrelated queries, while its L1 and L2 bounds otherwise differ by norm inequalities.

6. APPLICATIONS

The section applies the matrix-mechanism framework to hierarchical and wavelet strategies for one-dimensional range queries. These strategies exhibit closely related error behavior, with workload-dependent differences and analytically characterized bounds.

  • Strategy behavior: The hierarchical and wavelet approaches have low but non-minimal sensitivity, high accuracy for range queries, and worse accuracy for non-range queries.
  • Strategy constructions: The hierarchical strategy H_n recursively partitions the domain and contains 2n − 1 queries, whereas the wavelet strategy Y_n uses n queries.H_n answers are derived by linear regression, while Y_n answers are derived by inverting the strategy matrix.
  • Sensitivity: ΔY_n = ΔH_n = log_2 n + 1, while decomposition-based modifications improve sensitivity to log n + 0.64 for H_n and log_2 n + 2 − 4 for Y_n.The paper suspects further improvements may be possible through alternative rotations.
  • Error profiles: The two strategies have asymptotically equivalent error profiles and closely equivalent error for any linear counting query.The stated equivalence concerns the binary hierarchical strategy; higher branching factors can lower hierarchical error relative to the wavelet technique.
  • Error bounds: For W_R, maximum error is Θ(log^3 n/ϵ^2) for H_n and Y_n versus Θ(n/ϵ^2) for I_n.For W_01, maximum error is Θ(n log^2 n/ϵ^2) for H_n and Y_n versus Θ(n/ϵ^2) for I_n.
  • Error bounds: For W_R, total error is Θ(n^2 log^3 n/ϵ^2) for H_n and Y_n versus Θ(n^3/ϵ^2) for I_n.For W_01, total error is Θ(n2^n log^2 n/ϵ^2) for H_n and Y_n versus Θ(n2^n/ϵ^2) for I_n.
  • Error profiles: H_n tends to have lower error for larger range queries, whereas Y_n has lower error for unit counts and smaller range queries.

7. RELATED WORK

The related work situates the matrix mechanism among prior approaches for private query answering, including wavelet, hierarchical, Fourier, VC-dimension, interactive, and experimental-design methods. The paper’s closest predecessors address range queries, while this work unifies them in a broader framework.

  • Range-query mechanisms: The wavelet and hierarchical range-query approaches are the closest prior techniques, and the paper unifies them as instances of the matrix mechanism.
  • Related mechanisms: Fourier-based work targets integral consistency for low-order marginals, preserving non-negative integer values and cross-marginal consistency without significant accuracy loss.
  • Related mechanisms: A mechanism based on VC-dimension supports arbitrary workloads but is inefficient with exponential runtime; its efficient range-query strategy is less accurate than wavelet or hierarchical approaches.
  • Related mechanisms: The k-norm mechanism tailors noise to sets of linear queries, while the median mechanism addresses interactive queries arriving without knowledge of future queries.
  • Related optimization: Optimal experimental design similarly chooses noisy experiments to minimize estimation error, and a relaxed version can be formulated as a semidefinite program.

8. CONCLUSION

The paper presents the matrix mechanism and develops optimization and equivalence results for private query strategies. It also identifies unresolved work, including computing optimal strategies for specific workloads and extending the framework.

  • Conclusion: The matrix mechanism derives workload answers from noisy answers to a different set of strategy queries.The strategy queries are designed for the workload to improve accuracy for correlated counting queries.
  • Limitations and future work: The paper has not yet produced optimal or approximately optimal strategies for specific workloads.It identifies interactive query answering and matching known differential-privacy lower bounds as planned directions.
  • Strategy properties: Scaling every coefficient in a query strategy by a nonzero scalar leaves every query's error unchanged.The sensitivity scaling is compensated by the corresponding scaling of the error profile.
  • Strategy properties: Any unequal-noise strategy can be simulated by an equal-noise strategy with the same output distribution.The construction rescales the strategy matrix and transforms equal-scale Laplace noise to reproduce the original unequal scales.

C. SINGULAR VALUE BOUND APPROXIMATION

This section derives approximation bounds for the singular value bound and characterizes an optimal solution within that approximation. The analysis uses ellipsoid geometry and singular values of the strategy and workload matrices.

  • C. SINGULAR VALUE BOUND APPROXIMATION: The section theoretically computes approximation rates for the singular value bound approximation and its optimized solution.These rates quantify the approximation analyzed in this section.
  • Ellipsoid geometry: v^tZ^-1v describes a tangent hyperplane of the ellipsoid defined by x^tZx = 1.The accompanying proof relates the hyperplane representation to a point on the ellipsoid.
  • Approximation bound: For a matrix A with singular values δ_1,...,δ_n, the bound gives √nΔ_A as an upper bound on the relevant singular-value expression.The theorem states 1 + δ_2^2 + ... + δ_n^2 ≤ √nΔ_A.
  • Approximation bound: The analysis concludes that the approximation's sensitivity can be bounded by √nΔ_A.The derivation uses equality of matrix norms and the relationship ||A||_2 ≤ Δ_A.
  • Optimal solution: The singular value bound is optimized by aligning the strategy with the workload's singular-vector basis and selecting the stated diagonal singular-value matrix.Theorem 7 specifies P_A = P_W and gives the corresponding optimal D_A.

D. COMPLETING DEFICIENT COLUMNS

This section studies augmenting deficient strategy columns and establishes when adding strategy rows preserves or changes query error. It also proves equivalence between two Haar wavelet representations.

  • D. COMPLETING DEFICIENT COLUMNS: The section completes the proof concerning augmentation of deficient strategy columns.The argument uses eigenvalue relationships for transformed matrices.
  • Augmenting a strategy: Adding rows to a full-rank strategy cannot increase the quadratic error expression for any query.Equality holds only for queries in {A^tAw | Bw = 0}, a nonempty set exactly when B lacks full column rank.
  • Augmenting a strategy: The proof reduces the augmentation claim to positive semidefiniteness of (Q^tQ)^-1 − (Q^tQ + B^tB)^-1.It then establishes the condition through eigenvalue bounds.
  • Haar wavelet representations: The paper's matrix representation of Haar wavelet queries differs from the original presentation but is shown to be equivalent.The equivalence is established at the level of the resulting estimate distributions.
  • Haar wavelet representations: The Haar construction represents coefficients as rows of an n × n matrix and adds independent Laplace noise with coefficient-dependent scales.Each row corresponds to a tree coefficient, with scales determined by its subtree weight.

F. ANALYSIS OF THE HIERARCHICAL AND WAVELET STRATEGIES

This section presents the results of applying the matrix mechanism to hierarchical and wavelet schemes, followed by a detailed analysis of those results.

  • F. ANALYSIS OF THE HIERARCHICAL AND WAVELET STRATEGIES: The section applies the matrix mechanism to hierarchical and wavelet schemes.It reports the results of that application before providing their detailed analysis.
  • F. ANALYSIS OF THE HIERARCHICAL AND WAVELET STRATEGIES: The section provides detailed analysis of the hierarchical and wavelet results.The analysis follows the presentation of the application results.
  • F. ANALYSIS OF THE HIERARCHICAL AND WAVELET STRATEGIES: The hierarchical and wavelet strategies are analyzed within the matrix-mechanism framework.The passage identifies this framework as the basis for the section's analysis.

F.1 Eigen-decomposition of Hn and Yn

The section derives eigenvalues and eigenvectors for the hierarchical and Haar query strategies, establishing the decompositions used to analyze their error and sensitivity. It shows that the resulting sensitivity of the hierarchical strategy is always smaller than that of Hn.

  • Comparison: The decompositions of Hn and Yn have remarkably similar eigenvalue distributions, each with log n + 1 distinct eigenvalues of geometrically increasing frequency.The decomposition of In instead yields an identity diagonal matrix and a spherical error profile.
  • Hn eigen-decomposition: Theorem 13 gives the eigenvalues and corresponding eigenvectors of Ht2kH2k for n = 2k, with the proof proceeding by induction.
  • Yn eigen-decomposition: The eigenvalues and eigenvectors of Yt2kY2k are derived similarly by induction, with additional eigenvectors completing the decomposition.
  • Sensitivity: The sensitivity of DHSPH is always smaller than the sensitivity of Hn.This follows from the positive inequality f(k) > 0 for every positive integer k.

F.2 Error analysis

The section analyzes query error through strategy decompositions and compares hierarchical, Haar, and identity strategies on range and 0-1 workloads. It obtains matching asymptotic bounds for Hn and Yn, while In has different scaling.

  • Hn versus Yn: For Hn and Yn, the error ratio for any query w lies in [1The comparison uses their shared eigenvectors and corresponding eigenvalue ratios in [1/2, 2].
  • Workload error bounds: Θ(log3 n/ϵ2) is the maximum error for WR under both Hn and Yn, versus Θ(n/ϵ2) under In.The corresponding total errors for WR are Θ(n2 log3 n/ϵ2), Θ(n2 log3 n/ϵ2), and Θ(n3/ϵ2), respectively.
  • Workload error bounds: Θ(n log2 n/ϵ2) is the maximum error for W01 under both Hn and Yn, versus Θ(n/ϵ2) under In.The corresponding total errors for W01 are Θ(n2n log2 n/ϵ2), Θ(n2n log2 n/ϵ2), and Θ(n2n/ϵ2), respectively.
  • Per-query analysis: The maximum error for any query in WR is Θ(log3 n), while the maximum error for any query in W01 is Θ(n log2 n).The latter follows from an upper bound for 0-1 queries and a query attaining the matching lower bound.

G.1 The geometry of the error profile

The error profile M = (AtA)^-1 is a positive definite quadratic form whose shape and orientation determine directional error. Strategy design can choose stretching and rotation, but sensitivity must be optimized alongside the profile.

  • Error-profile geometry: Each point on an error-profile ellipse represents a query w = [c1, c2] satisfying wMwt = 1.M1 is a circle, whereas M2 is a stretched ellipse rotated 45° toward y = x.
  • Directional error: Queries near and along y = x have wM2wt < wM1wt, so M2 gives a lower profile value in that direction.M2 has eigenvalues (7/2, 1/2), with its major axis stretched and rotated to align with y = x.
  • Strategy design: A desired error profile can be designed by selecting diagonal values and a rotation, but the resulting error also depends on sensitivity.Rotating the strategy can change sensitivity without changing the error profile; minimizing sensitivity becomes a smallest-enclosing-L1-ball problem for the strategy columns.
  • Strategy design: A2 has higher sensitivity than A1, so its greater accuracy along y = x is less pronounced than Figure 5 suggests.
Loading 0912.4742v2…