Source-linked AI summary
On the Geometry of Differential Privacy
Moritz Hardt, Kunal Talwar
TL;DR
The paper studies privacy-preserving analysis of sensitive databases and uses convex geometry to derive lower bounds and nearly matching mechanisms. It obtains lower bounds including Ω(d/ε) per answer for certain linear queries, while general tightness depends on an open convex-geometric conjecture.
Problem
Privacy-preserving data analysis must support statistical analysis of sensitive individual data while providing strong privacy guarantees against adversaries with auxiliary information.
Method
The paper uses methods from convex geometry to establish lower bounds on error and construct a mechanism whose error nearly matches those bounds.
Results
Ω(d/ε) per answer is required for the stated ε-private query settings, and the paper gives better upper bounds for databases whose dimension equals the number of individuals.
Takeaways & Limitations
The results connect differential-privacy error to geometric structure and provide nearly optimal privacy–error trade-offs in the studied settings.
Takeaways & Limitations
General convex bodies remain difficult to analyze: the relevant parameter has best known upper bound O(d^1/4), while the conjectured bound is O(1).
Abstract
from arXiv · showhide
We consider the noise complexity of differentially private mechanisms in the setting where the user asks $d$ linear queries $f\colon\Rn\to\Re$ non-adaptively. Here, the database is represented by a vector in $\Rn$ and proximity between databases is measured in the $\ell_1$-metric. We show that the noise complexity is determined by two geometric parameters associated with the set of queries. We use this connection to give tight upper and lower bounds on the noise complexity for any $d \leq n$. We show that for $d$ random linear queries of sensitivity~1, it is necessary and sufficient to add $\ell_2$-error $Θ(\min\{d\sqrt{d}/ε,d\sqrt{\log (n/d)}/ε\})$ to achieve $ε$-differential privacy. Assuming the truth of a deep conjecture from convex geometry, known as the Hyperplane conjecture, we can extend our results to arbitrary linear queries giving nearly matching upper and lower bounds. Our bound translates to error $O(\min\{d/ε,\sqrt{d\log(n/d)}/ε\})$ per answer. The best previous upper bound (Laplacian mechanism) gives a bound of $O(\min\{d/\eps,\sqrt{n}/ε\})$ per answer, while the best known lower bound was $Ω(\sqrt{d}/ε)$. In contrast, our lower bound is strong enough to separate the concept of differential privacy from the notion of approximate differential privacy where an upper bound of $O(\sqrt{d}/ε)$ can be achieved.
1 Introduction
The paper studies error in differentially private answers to non-adaptive linear queries and uses convex geometry to derive nearly optimal mechanisms and bounds. Its results are tight for random queries and extend to broader linear-query settings under geometric conditions.
- Differential privacy protects sensitive data while permitting statistical analysis, even against adversaries with arbitrary auxiliary information.
- A database is a vector in ℜn, queries are linear maps F:ℜn→ℜd with coefficients in [−1,1], and d≤n.
- The paper relates privacy noise to geometric properties of the query polytope K=FBn_1 and develops matching lower and upper bounds.
- For random Bernoulli ±1 query matrices, convex-geometric results make the upper and lower bounds match up to constant factors.The associated polytope is a random polytope whose volume and average Euclidean norm can be bounded sharply.
- For arbitrary linear maps, the K-norm mechanism is nearly optimal for approximately isotropic K, with a gap governed by the isotropic constant LK.The Hyperplane Conjecture asserts LK=O(1); non-isotropic bodies require a recursive mechanism and generalized lower bound, within O(log^(3/2)d).
2 Preliminaries
The paper formalizes differential privacy for linear queries on ℓ1-neighboring databases, defines error and sensitivity, and reviews standard mechanisms and geometric preliminaries. It also frames optimization through a linear program, while noting computational and asymptotic limitations.
- Privacy definitions: ε-differential privacy requires neighboring databases at ℓ1 distance at most 1 to induce output distributions differing by at most a multiplicative exp(ε) factor.Approximate privacy relaxes this condition by adding an additive δ term.
- Error and sensitivity: The paper measures worst-case expected error using the Euclidean norm unless another loss function is specified.Sensitivity is defined by the maximum ℓ1 norm of F x over x in the ℓ1 unit ball, with sensitivity d in the stated setting.
- Baseline mechanisms: The Laplacian mechanism gives an established upper bound for pure differential privacy, while the Gaussian mechanism provides a guarantee for approximate privacy.The cited theorems apply to mappings of sensitivity d.
- Technical preliminaries: Isotropic position and the Gamma distribution are introduced as convex-geometric and probabilistic tools used in the paper’s analysis.Every convex body admits a volume-preserving transformation into isotropic position.
- Optimization and geometry: An exponential-size linear program characterizes the optimal mechanism, but its size and unclear asymptotic behavior limit direct analysis.The work reports a constant approximation for random ±1 matrices and an O(log^(3/2) d)-approximation otherwise.
3 Lower bounds via volume estimates
The paper derives lower bounds on private-query error from geometric properties of the image K = F B_1^n, especially its volume and lower-dimensional projections. Packing arguments yield general bounds, and volume estimates make them tight in important regimes.
- General volume lower bound: Volume lower bounds on F B_1^n translate directly into lower bounds on the noise of any ε-differentially private mechanism.The paper denotes the resulting quantity by VolLB(F, ε).
- General volume lower bound: Every ε-differentially private mechanism must add error Ω(ε^-1 d^(1/2) Vol(K)^(1/d)) for K = F B_1^n.The bound follows by packing K with separated points and comparing the probability mass of disjoint output balls.
- Projected volume bounds: Projected volumes strengthen the lower bound when K is close to a lower-dimensional subspace.The generalized quantity GVolLB(F, ε) takes the supremum over dimensions and orthogonal projections.
- Domain extension: The volume lower-bound argument initially uses mechanisms defined on all real databases, but it can be extended to integer databases under Hamming distance.The extension is described as applying when the mechanism domain is restricted to integer vectors.
- Small-query regime: For d ⩽ log n, all matrices F ∈ [−1,1]^(d×n) satisfy Vol(F B_1^n)^(1/d) ⩽ O(1), and an explicit matrix attains maximum volume.This shows the standard upper bound is optimal when d ⩽ log(n).
4 The K-norm mechanism
The K-norm mechanism samples noise shaped by the query-dependent convex body K = F B_1^n. It is ε-differentially private, and its error is controlled by the average Euclidean norm of points in K.
- Definition and geometry: The K-norm mechanism is a new differentially private mechanism whose noise geometry is determined by K = F B_1^n.Its query dependence comes from using the Minkowski norm with K as unit ball.
- Sampling procedure: Sampling draws r from Gamma(d + 1, ε^-1), then samples a uniformly from F x + rK.This gives a concrete procedure for generating the mechanism’s output distribution.
- Guarantee: The K-norm mechanism is ε-differentially private and satisfies an error bound expressed through the expected distance of a random point in K from the origin.The privacy proof uses the triangle inequality for the K-norm and the fact that F x lies in K for ℓ1-neighboring changes.
5 Matching bounds for random queries
For random query matrices, convex-geometric volume and norm bounds make the privacy lower bound and K-norm mechanism match, while also separating exact from approximate differential privacy.
- Random queries: Random query matrices yield matching lower and upper error bounds up to constant factors.The associated polytope is a random symmetric convex hull whose volume and average Euclidean norm are controlled by results on random polytopes.
- Random queries: An explicit construction of n points in {−1, 1}^d achieves the same convex-hull volume bound as random points.This construction accompanies the random-polytope theorem and shows the volume estimate is not limited to probabilistic existence.
- Random queries: The random polytope’s normalized volume can be tiny relative to the infinity ball when d ≫ log n.Its volume is proportional to that of a Euclidean ball of an appropriate radius, becoming comparatively small in high dimension.
- Separation result: Approximate differential privacy admits error o(ε^-1√log(n/d)), whereas exact differential privacy requires Ω(ε^-1√log(n/d)) under the stated parameter regime.For d ≤ log(n) and constant δ, the exact-privacy lower bound is a factor √d larger than the approximate-privacy upper bound.
- Random queries: The K-norm mechanism is ε-differentially private for almost all random matrices with the stated upper error bound.This upper bound follows from the random-polytope average-norm estimate and Jensen’s inequality.
6 Approximately isotropic bodies
For approximately isotropic query bodies, the K-norm mechanism is nearly optimal; matching bounds for arbitrary such bodies depend on the Hyperplane conjecture.
- Approximately isotropic bodies: Random symmetric convex hulls from the hypercube are O(1)-approximately isotropic and have L_K = O(1).More generally, the K-norm mechanism is approximately optimal whenever the query body is nearly isotropic.
- Approximately isotropic bodies: The K-norm mechanism is ε-differentially private with error at most O(cL_K) · VolLB(F, ε) for c-approximately isotropic bodies.The proof bounds the mechanism’s expected Euclidean error using the body’s covariance structure and Jensen’s inequality.
- Hyperplane conjecture: The Hyperplane conjecture asserts that L_K is bounded by an absolute constant for every convex body.The best known general upper bound is L_K ≤ O(d^1/4), while the conjectured bound is L_K = O(1).
- Hyperplane conjecture: Assuming the Hyperplane conjecture, the upper and lower bounds match for approximately isotropic convex bodies.The assumption removes the remaining isotropic-constant factor in the comparison.
7 Non-isotropic bodies
For non-isotropic query bodies, the paper develops a recursive mechanism based on covariance eigenspaces and obtains near-optimal error under the Hyperplane conjecture.
- Motivation: The K-norm mechanism can be far from optimal when the query body is far from isotropic.In the example, it adds O(d/ε) noise to one coordinate while the Laplacian mechanism adds O(1/ε), and both mechanisms can remain far from optimal after rotation.
- Mechanism: The recursive NIM mechanism partitions the body using the covariance matrix’s middle eigenvalue and descends recursively on one part.It applies the K-norm mechanism on the other part and acts differently on subspaces associated with different eigenvalue scales.
- Privacy analysis: NIM satisfies (ε log d)-differential privacy because it composes ε-private K-norm mechanisms across at most log d recursive steps.Each recursive body is a lower-dimensional image of the ℓ1-ball, so the K-norm mechanism provides ε-differential privacy at that step.
- Geometric analysis: The analysis transforms non-isotropic bodies into isotropic position while tracking how the transformation changes projected volumes.Covariance eigenvalues, eigenspaces, and projection-volume relationships support the recursive error analysis.
- Near optimality: Under the Hyperplane conjecture, NIM’s lower and upper bounds are both within O(log^3/2 d) of optimal.The paper’s corollary supplies the corresponding ε-differentially private mechanism and error guarantee for arbitrary linear maps.
8 Efficient implementation of our mechanism
The section develops an efficient implementation of the K-norm mechanism using approximate sampling and handles both isotropic and non-isotropic bodies. The resulting Grid Walk mechanism preserves ε-differential privacy and achieves essentially the same error.
- Isotropic implementation: Sampling a radius from Gamma(d, ε^-1) is straightforward, while sampling uniformly from K is addressed using rapidly mixing random walks.The Grid Walk samples nearly uniformly from a grid inside K.
- Isotropic implementation: Membership testing and boundedness are the two requirements imposed on K for the Grid Walk.The stated bounds are B_d^2 ⊆ K ⊆ dB_d^2.
- Isotropic implementation: The Grid Walk yields an ε-differentially private mechanism with error err(M′, F) = err(M, F) + O(1).Here M denotes the K-norm mechanism.
- Non-isotropic implementation: For non-isotropic K, the mechanism computes query-dependent subspaces using an approximation to K’s covariance matrix.With O(d^4 log d) approximately uniform samples, the sample covariance approximates the covariance matrix well.
- Non-isotropic implementation: The approximate transformation preserves the needed geometric containment and volume bounds up to negligible error.The analysis establishes ||T̃ − T||_2 = neg(d) and transfers the volume lower bound to the transformed body.
9 Generalizations of our mechanism
The K-norm mechanism extends beyond linear queries over ℓ1-databases to arbitrary database domains with a distance function. Convexity of the associated sensitivity body is the essential property for privacy.
- General domain: For an arbitrary database domain and distance function, the sensitivity set K is formed from normalized query differences and convexified.The resulting K-norm mechanism is private with respect to the domain distance.
- General domain: The exponential-mechanism score based on the K-norm has sensitivity bounded by the database distance.This directly yields differential privacy for the generalized mechanism.
- General domain: When K is difficult to characterize, any convex body K′ containing K can be used instead.
- Related settings: Under Euclidean database proximity, the associated K is an ellipsoid for any linear query.This setting includes transformations that map neighboring databases within Euclidean distance R.
- Local sensitivity: The paper notes a local-sensitivity analogue of the K-norm mechanism for nonlinear queries.This connects the construction to smooth sensitivity, which can improve on global sensitivity when local sensitivity is smaller.
A.1 Weak separation oracle
A weak separation oracle supports approximate sampling from a body close to K, and this approximation is sufficient to retain the mechanism’s privacy guarantee.
- Weak-oracle sampling: A β-weak separation oracle enables sampling in time poly(d, β^-1) from a body ˆK satisfying K ⊆ ˆK ⊆ (1 + β)K.The output distribution is within ℓ∞-distance β of uniform over ˆK.
- Privacy analysis: The approximate mechanism samples r ∼ Gamma(d + 1, ε^-1) and outputs Fx + rz using β = min(ε/d, 1/r).
- Privacy analysis: The volume of the sampled body satisfies Vol(ˆK) = (1 ± ε)Vol(K) under the chosen approximation parameter.
- Privacy analysis: The approximate density remains controlled by the K-norm radius through the inclusion thresholds for (a/r) in ˆK.The analysis bounds the density using the conditions r ≥ R and r < R/(1 + β).
- Privacy analysis: The resulting density is within an exp(O(ε)) factor of the ideal density, and the algorithm has expected running time polynomial in d and ε^-1.
B Lower bounds for Differential Privacy with respect to Hamming Distance
The paper extends its lower bounds from ℓ1-differential privacy to the usual Hamming-distance setting by representing databases through nonnegative integer histograms. For suitable ±1 linear maps, strong lower bounds therefore apply to sensitivity-1 queries.
- Reduction to histograms: A database with categorical entries can be represented by its histogram, converting Hamming-distance privacy into ℓ1-privacy on nonnegative integer vectors.A linear query on the histogram is a sensitivity-1 query on the original database.
- Reduction to histograms: The ℓ1 lower-bound proof transfers to histograms after minor modifications for the nonnegative integer constraint.
- Lower bound: For F ∈ {−1, 1}^{d×n}, every ε-differentially private mechanism computing G(w) = Fx(w) must satisfy the stated lower bound.The theorem applies when ε < c d Vol(K)^(1/d)/√n.
- Lower-bound proof: The packing argument constructs many separated query answers and uses disjoint error balls to contradict an overly small error guarantee.Randomized rounding preserves the needed histogram and query-separation properties with constant probability.
- Lower bound: The translated lower bound holds for N = Ω(nd/ε).
- Lower bound: For d ≤ log n, there exists a ±1 linear map whose private computation requires the stated lower-bound error.
C Dilated Ball containment
Lemma C.1 shows that if a convex body contains the unit Euclidean ball up to an r-radius expansion with r < 1, then it contains a ball of radius 1 − r.
- If B^d_2 ⊆ A + rB^d_2 for r < 1, then (1 − r)B^d_2 ⊆ A.
- The proof fixes a unit vector z and assumes z′ = (1 − r)z lies outside A.
- A separating hyperplane for z′ and A supplies a unit normal w and scalar b used to construct v = z′ + rw.
- The triangle inequality gives ∥v∥ ≤ 1, and applying the assumed containment for arbitrary z completes the argument.