Title: Unconditionally Differentially Private Mechanisms for Linear Queries
Speaker: Aditya Bhaskara, Princeton University
Date: Wednesday, April 18, 2012 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
I will talk about the problem of designing differentially private mechanisms for a set of $d$ linear queries over a database represented as a vector, while adding as little error as possible. Hardt and Talwar~\cite{HT} related this problem to geometric properties of a convex body defined by the set of queries and gave a $O(\log^3 d)$-approximation to the minimum $\ell_2^2$ error, assuming a conjecture from convex geometry called the {\em Slicing} or the {\em Hyperplane} conjecture. I will show a mechanism that works unconditionally, and also gives an improved $O(\log^2 d)$ approximation to the expected $\ell_2^2$ error.
We remove the dependence on the Slicing conjecture by using a result of Klartag~\cite{Klartag} that shows that any convex body is "close" to one for which the conjecture holds; we modify this result to make sure this body satisfies central symmetry, and make the proof constructive. The improvement in approximation ratio relies on a stronger lower bound we derive on the optimum. This new lower bound goes beyond the packing argument that has traditionally been used in Differential Privacy and allows us to {\em add} the packing lower bounds obtained from orthogonal subspaces. We are able to achieve this via a {\em symmetrization} argument which argues that there always exists a near optimal differentially private mechanism which adds noise that is \emph{independent of the input database!} We believe this result should be of independent interest.
(Joint work with Daniel Dadush, Ravishankar Krishnaswamy and Kunal Talwar)