Moritz Hardt at Theory Lunch

Theory lunch talk: Friday October 16th.

On the Geometry of Differential Privacy

Moritz Hardt, Princeton University

Abstract:
We consider the noise complexity of differentially private mechanisms in the setting where the user asks d linear queries f:R^n->R non-adaptively. Here, the database is represented by a vector in R^n. Proximity between databases is measured in the l1-metric.

We show that the noise complexity is determined by two geometric parameters of a convex body associated with the set of queries. Using this connection we give tight upper and lower bounds on the noise complexity of random linear queries for any d

Quantitatively, our result shows that it is necessary and sufficient to add l2-error \Theta(min{d\sqrt{\log n},d\sqrt{d}}) to achieve differential privacy. The best previous upper bound (Laplacian mechanism) gives a bound of O(d\sqrt{d}), while the best known lower bound was \Omega(d). In contrast, our lower bound is strong enough to separate differential privacy from the notion of approximate differential privacy where an upper bound of O(d) can be achieved.

Joint work with Kunal Talwar.