The Geometry of Differential Privacy: The Small Database and Approximate Cases
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 given set of $d$ linear queries $A$ over a database $x \in \mathbb{R}^N$ we seek to find the differentially private mechanism that has the minimum mean squared error relative to the true answer $Ax$ For pure differential privacy, Hart and Talwar and Bhaskara et al. give an $O(\log^2 d) approximation to the optimal mechanism. Our first contribution is to give an $O(\log^2 d) approximation guarantee for the case of \varepsilon,\delta) approximate differential privacy. Our mechanism adds carefully chosen correlated Gaussian noise to the answers and runs in time polynomial in $d$ and $N$ The mechanism is based on a recursive construction of a "small" enclosing ellipsoid of the sensitivity polytope $AB_1^N$ where $B_1^N$ denotes the $N$ dimensional \ell_1$ b.
SIAM J. Comput.