On the Geometry of Differential Privacy
- Moritz Hardt ,
- Kunal Talwar
STOC |
Published by Association for Computing Machinery, Inc.
Longer version
We consider the noise complexity of differentially private mechanisms in the setting where the user asks d linear queries fcolon Rn to Re non-adaptively. Here, the database is represented by a vector in Rn and proximity between databases is measured in the ℓ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 ≤ n. We show that for d random linear queries of sensitivity 1, it is necessary and sufficient to add ℓ2-error Θ(min {d√d/ε,d√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/ε,√dlog (n/d)/ε}) per answer. The best previous upper bound (Laplacian mechanism) gives a bound of O(min {d/ε,√n/ε}) per answer, while the best known lower bound was Ω(√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(√d/ε) can be achieved.
Copyright © 2007 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org. The definitive version of this paper can be found at ACM's Digital Library --http://www.acm.org/dl/.