PaperlayerView exact revision on arXiv

Source-linked AI summary

The Geometry of Differential Privacy: the Sparse and Approximate Cases

Aleksandar Nikolov, Kunal Talwar, Li Zhang

arXiv:1212.0297v1cs.DS

TL;DR

The paper asks how accurately linear queries over histograms can be answered under differential privacy while efficiently approximating the optimal mechanism, including when databases are sparse. It develops Gaussian-noise and regression-based mechanisms with polylogarithmic approximation guarantees for pure and approximate privacy, and uses hereditary discrepancy to approximate a matrix invariant. The conclusions leave near-optimal sparse-case ℓ∞ mechanisms and improved approximation ratios open.

  • Problem

    The paper studies the accuracy–privacy trade-off for linear queries and asks whether optimal mechanisms can be efficiently approximated in dense and sparse database settings.

  • Method

    The paper combines correlated Gaussian noise, linear regression for sparse databases, convex-geometric lower bounds, and hereditary discrepancy.

  • Results

    The mechanisms achieve polylogarithmic approximations to optimal error under both (ε,δ)-DP and ε-DP, while the privacy-mechanism connection yields a polylogarithmic approximation to hereditary discrepancy.

  • Takeaways & Limitations

    Near-optimal mechanisms are available for arbitrary linear queries in dense and sparse databases under both pure and approximate differential privacy.

  • Takeaways & Limitations

    The paper leaves open better lower bounds and approximation ratios for (ε,δ)-DP mechanisms, as well as near-optimal sparse-case ℓ∞ mechanisms.

Abstract

from arXiv · show

In this work, we study trade-offs between accuracy and privacy in the context of linear queries over histograms. This is a rich class of queries that includes contingency tables and range queries, and has been a focus of a long line of work. For a set of $d$ linear queries over a database $x \in \R^N$, we seek to find the differentially private mechanism that has the minimum mean squared error. For pure differential privacy, an $O(\log^2 d)$ approximation to the optimal mechanism is known. Our first contribution is to give an $O(\log^2 d)$ approximation guarantee for the case of $(\eps,δ)$-differential privacy. Our mechanism is simple, efficient and adds correlated Gaussian noise to the answers. We prove its approximation guarantee relative to the hereditary discrepancy lower bound of Muthukrishnan and Nikolov, using tools from convex geometry. We next consider this question in the case when the number of queries exceeds the number of individuals in the database, i.e. when $d > n \triangleq \|x\|_1$. It is known that better mechanisms exist in this setting. Our second main contribution is to give an $(\eps,δ)$-differentially private mechanism which is optimal up to a $\polylog(d,N)$ factor for any given query set $A$ and any given upper bound $n$ on $\|x\|_1$. This approximation is achieved by coupling the Gaussian noise addition approach with a linear regression step. We give an analogous result for the $\eps$-differential privacy setting. We also improve on the mean squared error upper bound for answering counting queries on a database of size $n$ by Blum, Ligett, and Roth, and match the lower bound implied by the work of Dinur and Nissim up to logarithmic factors. The connection between hereditary discrepancy and the privacy mechanism enables us to derive the first polylogarithmic approximation to the hereditary discrepancy of a matrix $A$.

1 Introduction

The paper studies efficient approximations to optimal differentially private mechanisms for linear queries, including dense and sparse histograms, under pure and approximate privacy. It also connects these mechanisms to hereditary discrepancy and derives polylogarithmic approximation results.

  • Motivation: Differential privacy creates an inherent trade-off between privacy and accuracy when answering many counting or linear queries.Adversarial query answering can permit reconstruction of private information when error is too small.
  • Problem setting: The paper represents a histogram database x ∈ R^N and answers d linear queries using a matrix A, with performance measured by worst-case expected squared ℓ2 error.Counting queries are the special case A ∈ {0,1}^{d×N}.
  • Research questions: Question 1 asks whether the optimal (ε,δ)-DP mechanism for any query matrix A can be efficiently approximated.This extends earlier competitive-analysis results for ε-DP mechanisms.
  • Research questions: Question 2 asks how large the gap between optimal ε-DP and (ε,δ)-DP mechanisms can be for linear queries.Prior work exhibited an Ω(log(N/d)) gap in some settings.
  • Dense-case results: O(log^2 d log 1/δ) · L_A approximates the dense-case optimum for (ε,δ)-DP, using an efficient mechanism and efficiently computable lower bound L_A.Every (ε,δ)-DP mechanism has error at least L_A.
  • Dense-case results: Ω(1/(log^O(1)(d) log(N/d))) · err_M*(A) lower-bounds the error of any (ε,δ)-DP mechanism relative to the ε-DP generalized K-norm mechanism.The result shows the known ε-DP versus approximate-DP gap is essentially worst possible up to polylogarithmic factors.
  • Sparse-case results: The sparse-case mechanisms approximate the optimum for databases with ∥x∥_1 ≤ n under both (ε,δ)-DP and ε-DP, using lower bounds L_A,n.The stated approximation factors are polylogarithmic in d and N, with the ε-DP theorem giving O(log^O(1) d · log^3/2 N) · L_A,n.
  • Sparse-case results: The ε-DP sparse mechanism gives err_M(A,n) = ˜O(dn) for every counting-query matrix A.This answers the paper’s counting-query sparse-case question affirmatively and improves the cited prior upper bound up to logarithmic factors.

2 Preliminaries

The preliminaries establish notation for linear queries, databases, convex geometry, and error, then define differential privacy and introduce the geometric and statistical tools used later.

  • Convex geometry: The geometric framework uses symmetric convex bodies, polar bodies, Minkowski norms, ellipsoids, volume, projections, and singular values.John’s theorem characterizes the unique minimum-volume enclosing ellipsoid, while restricted invertibility supplies approximately orthogonal contact points in a key case.
  • Statistical estimation: Least-squares estimation is used for noisy query answers, with Lemma 1 bounding squared estimation error by the smaller of Euclidean and polar-norm noise terms.The bound is ∥ŷ − y∥2^2 ≤ min{4∥w∥2^2, 4∥w∥L◦}.
  • Privacy: Differential privacy bounds how much output probabilities can change between neighboring databases, with (ε, δ)-DP relaxing pure ε-DP by an additive δ.The definitions require the bound for every measurable output set, and δ = 0 gives pure differential privacy.
  • Notation: A database is represented by a histogram x ∈ R^N, and a workload A gives exact query answers y = Ax.Neighboring databases correspond to histograms differing by ℓ1 distance at most 1.
  • Error: Mechanism performance is measured by worst-case expected total squared ℓ2 error over the allowed database set.The error maximizes expected squared deviation over databases and averages only over the mechanism’s internal randomness.

3 Algorithms for Approximate Privacy

The approximate-privacy algorithms decompose query space geometrically, then add noise tailored to the resulting orthogonal subspaces. A least-squares refinement further improves accuracy for sparse databases while preserving differential privacy.

  • Base decomposition: The algorithms handle dense and sparse databases using recursively computed orthonormal bases derived from the minimum volume enclosing ellipsoid of A’s columns.The decomposition partitions R^d into O(log d) mutually orthogonal subspaces.
  • Dense case: The dense-case mechanism adds correlated unbiased Gaussian noise to Ax using the geometric decomposition.Its expected error matches the spectral lower bound up to polylogarithmic factors.
  • Dense case: The Gaussian mechanism is (ε, δ)-differentially private and nearly optimal for sufficiently small ε and δ relative to ε.The privacy proof uses the ellipsoidal geometry of projected query columns and the selected noise scales.
  • Sparse case: The sparse-case algorithm combines the noise distribution with least-squares estimation to reduce error when n = o(d/ε).Privacy comes from noise addition, while regression exploits the database-size bound.

4 Results for Pure Privacy

The pure-privacy results extend the geometric approach to sparse databases and clarify the relationship between pure and approximate privacy. They use tailored noise distributions and least-squares estimation to obtain near-optimal mechanisms.

  • Pure-privacy guarantees: The geometric approach bounds the gap between optimal approximate-privacy and pure-privacy errors, then extends the construction to sparse databases.The sparse pure-privacy mechanism nearly matches the guarantees of the approximate-privacy sparse mechanism.
  • Geometric ingredient: The minimum-volume ellipsoid argument identifies d vertices whose determinant captures a significant fraction of the query polytope’s volume.Theorem 15 states det(A|S)^(1/d) = Ω(vrad(E)) for a size-d subset S.
  • Sparse case: The pure-privacy sparse mechanism uses database-oblivious noise tailored to A followed by least-squares estimation.The construction replaces Gaussian noise with a generalized K-norm distribution because Gaussian noise does not preserve pure differential privacy.
  • Sparse case: The resulting mechanism is (ε, 0)-differentially private and satisfies polylogarithmic error guarantees relative to both approximate- and pure-privacy optima.The stated bounds are O(log^4 d log^(3/2) N) optε,δ(A,n) + O(log^5 d log N) optε,0(A,n).

5 Universal bounds

The paper derives universal error bounds for counting queries by combining geometric projections, noise mechanisms, and least-squares estimation. It also compares its total-error bound with prior work.

  • Universal bounds: For sensitivity-1 linear queries, the columns of A have bounded ℓ2 norm, supporting universal bounds on errε,δ(A,n) and errε,0(A,n).The sensitivity condition constrains the aggregate column norms used in the mechanisms’ analyses.
  • Approximate privacy: The simple approximate-privacy mechanism adds Gaussian noise scaled to the maximum column norm and applies least-squares estimation.The mechanism is stated to be (ε, δ)-differentially private.
  • Comparison: The paper’s bound improves the prior comparison by an O(log d) factor, but it bounds total ℓ2 error rather than expected squared error for every query.The cited comparison identifies this as the trade-off with the stronger per-query guarantee in prior work.
  • Pure privacy: For pure privacy, the mechanism substitutes the generalized K-norm distribution for Gaussian noise before least-squares estimation.The resulting mechanism is (ε, 0)-differentially private.

6 Extensions

The paper extends its dense-case mechanisms to expected worst-case ℓ∞ error and connects private mechanisms to polylogarithmic hereditary-discrepancy approximation.

  • 6.1 Expected ℓ∞ Error: An additional O(log d) competitive-ratio loss extends the dense-case results from total squared error to expected worst-case ℓ∞ error.The extension first controls coordinatewise squared error, then applies a black-box construction for expected ℓ∞ error.
  • 6.1 Expected ℓ∞ Error: O(log^4 d log((log d)/δ)) bounds the expected ℓ∞ error relative to specLB(PA) and (optℓ∞(A))^2.The mechanism uses O(log d) independent copies and takes coordinatewise medians.
  • 6.1 Expected ℓ∞ Error: The median construction preserves privacy only after scaling the parameters to (Lε, Lδ), where L = Ω(log d).The output is postprocessed from L approximate-DP mechanisms, but it is not necessarily (ε, δ)-DP with the original parameters.
  • 6.2 Approximating Hereditary Discrepancy: Theorem 26 gives a polynomial-time O(log^2 d log N√log log d) approximation to herdiscℓ∞(A).The proof sandwiches hereditary discrepancy between a determinant-based lower bound and the private mechanism's efficiently computable expected error, using semidefinite-programming and discrepancy results.
  • 6.2 Approximating Hereditary Discrepancy: The mechanism provides an efficiently computable and verifiable witness for an upper bound on hereditary discrepancy.The construction is specified by a distribution over O(log d) Gaussian noise-addition mechanisms.

7 Conclusions

The paper concludes that its mechanisms are near optimal for linear queries on dense and sparse databases under pure and approximate differential privacy, while identifying open problems and implementation work.

  • 7 Conclusions: The paper presents near-optimal mechanisms for any linear query on dense and sparse databases under both pure and approximate differential privacy.The mechanisms are described as simple and efficient.
  • 7 Conclusions: The authors leave implementation and comparison with existing techniques as an instructive direction for future work.
  • 7 Conclusions: The hereditary-discrepancy lower bound applies only for sufficiently small constant ε and δ, producing an O(log(1/δ)) term in the approximation ratio.The authors leave better lower bounds and approximation ratios for (ε, δ)-DP mechanisms open.
  • 7 Conclusions: Near-optimal ℓ∞-error mechanisms for the sparse case remain an open problem because the paper directly establishes ℓ2 bounds there.Dense-case ℓ2 bounds can be translated to ℓ∞ bounds, but the sparse-case analogue is left unresolved.

A Concentration of Log concave measures

This appendix introduces Brunn–Minkowski inequality as a tool for proving concentration results for log-concave measures.

  • A Concentration of Log concave measures: Theorem 28 states Brunn–Minkowski inequality for measurable sets under a log-concave measure and coefficients α, β with α + β = 1.
  • A Concentration of Log concave measures: The inequality is used to prove Borell’s lemma for arbitrary log-concave distributions.The proof approach follows Gia03.
  • A Concentration of Log concave measures: Applying Brunn–Minkowski and rearranging establishes the stated concentration result.

B From Concentration to Expectation

This appendix formalizes the step from exponential upper-tail bounds to expectation bounds.

  • B From Concentration to Expectation: An exponential upper-tail bound implies an expectation bound: if Pr[X ≥ αC] ≤ exp(−α/c2) for α ≥ c1, then E[X] ≤ (c1 + c2)C.
  • B From Concentration to Expectation: The expectation claim follows by linearity of expectation.

C Hardness of Approximating Hereditary Discrepancy

The paper establishes constant-factor hardness of approximating hereditary discrepancy in the ℓ∞ norm. The hardness follows from a reduction from 2-colorability of 3-uniform hypergraphs to incidence matrices.

  • Constant hardness of approximation holds for herdiscℓ∞.
  • Prior work established strong inapproximability for discrepancy in both ℓ2 and ℓ∞ norms, while this work proves constant hardness for hereditary discrepancy in ℓ∞.
  • NP-hardness distinguishes herdiscℓ∞(A) ≤ 2 from discℓ∞(A) ≥ 3 for a family of binary input matrices.
  • The proof maps each 3-uniform hypergraph to its vertex-edge incidence matrix.
  • A 2-coloring witnessed by a transversal yields ℓ∞ discrepancy at most 2 for every column restriction.
  • If the hypergraph is not 2-colorable, every ±1 coloring has ℓ∞ discrepancy at least 3.
Loading 1212.0297v1…